Visibility calculations for 3d computer graphics

• US 6,618,047 B1
• Filed: 01/20/2000
• Issued: 09/09/2003
• Est. Priority Date: 06/28/1991
• Status: Expired due to Fees

• Current Assignee: FuzzySharp Technologies Incorporated
• Original Assignee: FuzzySharp Technologies Incorporated
• Inventors: Lim, Hong Lip
• Primary Examiner(s): BRIER, JEFFERY A
• Application Number:
  US09/490,288
• Time in Patent Office: 1,328 Days
• Field of Search: 345/419, 345/421, 345/425, 345/114, 345/139, 345/422, 345/418, 345/424
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

Disclosed is a method of reducing the complexity of hidden surface removal in 3D graphics systems. A fuzzy projection (FF) of a surface (SU) as seen from a number of viewpoints (VP) in a bounding box (BB) is stored in a buffer (FA) having elements (FE). A combination of all the patches (PT) of the surface (SU) viewed form a fuzzy region (FR) where surfaces can be either visible, hidden, or unable to be determined with certainty as to whether or not visible/hidden. A non-fuzzy region (NF) describes those patches (PT) that are always visible.

Claims

1. A method of reducing the visibility related computations in 3-D computer graphics, the visibility related computations being performed on 3-D surfaces or their sub-elements, or a selected set of both, the method comprising:

identifying grid cells which arc under or related to the projections or extents of projections associated with at least one of said 3-D surfaces or their sub-elements;

comparing data associated with said at least one of 3-D surfaces or their sub-elements with stored data associated with the grid cells;

determining which of said at least one of 3-D surfaces or their sub-elements is always invisible or always visible to a viewpoint or a group of viewpoints by projection based computations prior to a visibility computation; and

ignoring said determined at least one of the 3-D surfaces or their sub-elements during said visibility computation.

2. The method of claim 1 wherein the projection based computations comprise:

defining one or more projection planes for generating projections with respect to a viewpoint or a group of viewpoints;

identifying regions on the projection planes that are or are related to the projections or the extents of projections associated with selected 3-D surfaces.

3. The method of claim 2 wherein said identifying step comprises dividing each projection plane into one or more grids;

and storing the data of said projections on the grids in computer storage.

4. The method of claim 3 wherein said grid or grids are either regular or irregular.

5. The method of claim 3 wherein the structure of said computer memory is based on a z-buffer or a quadtree.

6. The method of claim 3 wherein some or all of said data are or are related to the depths of said 3-D surfaces or their sub-elements.

7. The method of claim 3 wherein some or all of said data are or are related to the shortest depths of said 3-D surfaces or their sub-elements.

8. The method of claim 3 wherein some or all of said data are or are related to the largest depths of said 3-D surfaces or their sub-elements.

9. The method of claim 1 wherein at least one of the data to be compared with said stored data is a value related to the depth value, the largest depth value, or the smallest depth value related to one of said 3-D surfaces or said sub-elements.

10. The method of claim 1 wherein said visibility related computations are speeded up by using cache memory.

11. A method of reducing a step of visibility computations in 3-D computer graphics from a perspective of a viewpoint, the method comprising:

computing, before said step and from said perspective, the visibility of at least one entity selected from 3-D surfaces and sub-elements of said 3-D surfaces, wherein said computing step comprises at least a comparison between a pair of depth-related numbers to determine which of the surfaces or the sub-elements of the surfaces associated with said numbers is closer to said viewpoint and said 3-D surfaces are arranged in a hierarchy represented by patches in varying levels of details; and

skipping, at said step, at least an occlusion relationship calculation for at least one entity that has been determined to be invisible in said computing step.

12. A method of reducing a step of visibility computations in 3-D computer graphics from a perspective of a viewpoint, the method comprising:

computing, before said step and from said perspective, the visibility of at least one entity selected from 3-D surfaces and sub-elements of said 3-D surfaces, wherein said computing step comprises;

employing at least one projection plane for generating projections with said selected set of 3-D surfaces and said sub-elements with respect to said perspective;

identifying regions on said at least one projection plane, wherein said regions are related to the projections associated with said selected 3-D surfaces, said sub-elements, or bounding volumes of said 3-D surfaces or said sub-elements;

updating data related to said regions in computer storage; and

deriving the visibility of at least one of said 3-D surfaces or said sub-elements from the stored data in said computer storage; and

skipping, at said step of visibility computations, at least an occlusion relationship calculation for at least one entity that has been determined to be invisible in said computing step.

13. The method of claim 12, wherein at least one of said bounding volumes is a volume containing a 3-D surface, or a volume containing a 3-D surface and at least one of the sub-elements of said 3-D surface.

14. The method of claim 12, wherein at least one of said bounding volumes defines a space containing all likely occurrence of said 3-D surface, or said 3-D surface and at least one of said sub-elements.

15. The method of claim 12, wherein said identifying step comprises:

dividing each projection plane into at least one grid; and

identifying the cell or cells of said at least one gird which are related to each of said regions or extents of said regions.

16. The method of claim 15, wherein said at least one grid is regular.

17. The method of claim 16, wherein the structure of said computer storage is based on a z-buffer.

18. The method of claim 15, wherein said at least one grid is irregular.

19. The method of claim 18, wherein the structure of said computer storage is based on a quadtree.

20. The method of claim 12, wherein said updating step comprises:

performing a depth comparison test between data associated with each of said identified cell or cells with said stored data in an element of said computer storage, wherein said element is the one associated with said cell; and

if said test indicates that update is necessary for said cell, writing said data associated with said cell into said associated element.

21. The method of claim 20, wherein the data to be compared with said stored data is related to the depth of one of said 3-D surfaces or one of said sub-elements of said 3-D surfaces, wherein the projection region or the extent of projection region of said one of said 3-D surfaces or said one of said sub-elements of said 3-D surfaces is related to said cell.

22. The method of claim 20, wherein the data to be compared with said stored data is related to the shortest depth of said 3-D surface or said sub-element.

23. The method of claim 20, wherein the data to be compared with said stored data is related to the largest depth of said 3-D surface or said sub-element.

24. The method of claim 20, wherein the data to be compared with said stored data is related to the bounding volume associated with said 3-D surface or said sub-element.

25. The method of claim 24, wherein at least one of said bounding volume is a volume containing a 3-D surface, or a volume containing a 3-D surface and at least one of the sub-elements of said 3-D surface.

26. The method of claim 24, wherein at least one of said bounding volumes defines a space containing all likely occurrence of said 3-D surface, or said 3-D surface and at least one of said sub-elements.

27. The method of claim 12, wherein said computer storage is accelerated by cache memory.

28. A method of reducing visibility computations in 3-D computer graphics, the method comprising:

computing the visibility of a set of entities selected from 3-D surfaces and sub-elements of said 3-D surfaces from the perspective of a group of a plurality of viewpoints, wherein said computing step comprises at least a comparison between a pair of depth-related numbers to determine which of the surfaces or the sub-elements of the surfaces associated with said numbers is closer to said group of a plurality of viewpoints and said 3-D surfaces are arranged in a hierarchy represented by patches in varying levels of details; and

skipping at least an occlusion relationship calculation at subsequent steps of visibility computations for at least one entity Eat has been determined to be invisible in said computing step, wherein said visibility computations in each step is from the perspective of each viewpoint from said group, or from the perspective of each subset of viewpoints from said group.

29. A method of reducing visibility computations in 3-D computer graphics, the method comprising:

computing the visibility of a set of entities selected from 3-D surfaces and sub elements of said 3-D surfaces from the perspective of a group of a plurality of viewpoints, wherein said computing step comprises;

employing at least one projection plane for generating projections with said selected set of 3-D surfaces and said sub-elements with respect to the perspective of a group of a plurality of viewpoints;

identifying regions on said at least one projection plane, wherein said regions are related to the projections associated with said selected 3-D surfaces, said sub-elements, or bounding volumes of said selected 3-D surfaces or said sub-elements from said perspective;

updating data related to said regions in computer storage; and

deriving the visibility of at least one of said 3-D surfaces or said sub-elements from the stored data in said computer storage; and

skipping at least an occlusion relationship calculation at subsequent steps of visibility computations for at least one entity that has been determined to be invisible in said computing step, wherein said visibility computations in each step is from the perspective of each viewpoint from said group, or from the perspective of each subset of viewpoints from said group.

30. The method of claim 29, wherein at least one of said bounding volumes is a volume containing a 3-D surface, or a volume containing a 3-D surface and at least one of the sub-elements of said 3-D surface.

31. The method of claim 29, wherein at least one of said bounding volumes defines a space containing all likely occurrence of said 3-D surface, or said 3-D surface and at least one of said sub-elements.

32. The method of claim 29, wherein said identifying step comprises:

dividing each projection plane into at least one grid; and

identifying the cell or cells of said at least one grid which are related to each of said regions or extents of said regions.

33. The method of claim 32, wherein said at least one grid is regular.

34. The method of claim 33, wherein the structure of said computer storage is based on a z-buffer.

35. The method of claim 32, wherein said at least one grid is irregular.

36. The method of claim 35, wherein the structure of said computer storage is based on a quadtree.

37. The method of claim 29, wherein said updating step comprises:

performing a depth comparison test between data associated with each of said identified cell or cells with said stored data in an element of said computer storage, wherein said element is the one associated with said cell; and

if said test indicates that update is necessary for said cell, writing said data associated with said cell into said associated element.

38. The method of claim 37, wherein the data to be compared with said stored data is related to the depth of one of said 3-D surfaces or one of said sub-elements of said 3-D surfaces, wherein the projection region or the extent of projection region of said one of said 3-D surfaces or said one of said sub-elements of said 3-D surfaces is related to said cell.

39. The method of claim 37, wherein the data to be compared with said stored data is related to the shortest depth of said 3-D surface or said sub-element.

40. The method of claim 37, wherein the data to be compared with said stored data is related to the largest depth of said 3-D surface or said sub-element.

41. The method of claim 37, wherein the data to be compared with said stored data is related to the bounding volume associated with said 3-D surface or said sub-element.

42. The method of claim 41, where at least one of said bounding volume is a volume containing a 3-D surface, or a volume containing a 3-D surface and at least one of the sub-elements of said 3-D surface.

43. The method of claim 41, wherein at least one of said bounding volumes defines a space containing all likely occurrence of said 3-D surface, or said 3-D surface and at least one of said sub-elements.

44. The method of claim 29, wherein said computer storage is accelerated by cache memory.

45. A method of reducing visibility computations in 3-D computer graphics, the method comprising:

computing the visibility of a set of entities selected from 3-D surfaces and sub-elements of said 3-D surfaces from the perspective of a group of at least one viewpoint, wherein said computing step comprises at least a comparison between a pair of depth-related numbers to determine which of the surfaces or the sub-elements of the surfaces associated with said numbers is closer to said group of at least one viewpoint and said 3-D surfaces are arranged in a hierarchy represented by patches in varying levels of details; and

skipping at least an occlusion relationship calculation at each of subsequent step or steps of visibility computations, wherein said visibility computations in each of said step or steps is from the perspective of each viewpoint from said group, or from the perspective of a subset of viewpoints from said group, for at least one entity that has been determined to be visible in said computing step.

46. A method of reducing visibility computations in 3-D computer graphics, the method comprising:

computing the visibility of a set of entities selected from 3-D surfaces and sub-elements of said 3-D surfaces from the perspective of a group of at least one viewpoint, wherein said computing step comprises;

employing at least one projection plane for generating projections with said selected set of 3-D surfaces and said sub-elements with respect to said perspective of a group of at least one viewpoint;

identifying regions on said at least one projection plane;

wherein said regions are related to the projections associated with said 3-D surfaces, said sub-elements, or bounding volumes of said 3-D surfaces or said sub-elements from said perspective;

updating the data related to said regions in computer storage; and

deriving the visibility of at least one of said 3-D surfaces or said sub-elements from the data stored in said computer storage, and

skipping at least an occlusion relationship calculation at each of subsequent step or steps of visibility computations, wherein said visibility computations in each of said step or steps is from the perspective of each viewpoint from said group, or from the perspective of a subset of viewpoints from said group, for at least one entity that has been determined to be visible in said computing step.

47. The method of claim 46, wherein at least one of said bounding volumes is a volume containing a 3-D surface, or a volume containing a 3-D surface and at least one of the sub-elements of said 3-D surface.

48. The method of claim 46, wherein at least one of said bounding volumes defines a space containing all likely occurrence of said 3-D surface, or said 3-D surface and at least one of said sub-elements.

49. The method of claim 46, wherein said identifying step comprises:

dividing each projection plane into at least one grid; and

identifying the cell or cells of said at least one grid which are related to each of said regions or extents of said regions.

50. The method of claim 49, wherein said at least one grid is regular.

51. The method of claim 50, wherein the structure of said computer storage is based on a z-buffer.

52. The method of claim 49, wherein said at least one grid is irregular.

53. The method of claim 52, wherein the structure of said computer storage is based on a quadtree.

54. The method of claim 46, wherein said updating step comprises:

performing a depth comparison test between data associated with each of said identified cell or cells with said stored data in an element of said computer storage, wherein said element is the one associated with said cell; and

if said test indicates that update is necessary for said cell, writing said data associated with said cell into said associated element.

55. The method of claim 46, wherein said computer storage is accelerated by cache memory.

56. A method of reducing visibility computations in 3-D computer graphics with respect to a viewpoint, the method comprising:

employing at least one projection plane for generating projections with respect to a perspective of said viewpoint;

dividing said at least one projection plane into at least one grid, wherein said at least one grid is irregular;

identifying, from said perspective, grid cells which are related to the projections or extents of the projections, said projections are related to 3-D surfaces, sub-elements of said 3-D surfaces, bounding volumes of said 3-D surfaces, or bounding volumes of said sub-elements, wherein said identified grid cells are represented by a data structure based on a quadtree;

computing visibility of at least one of said surfaces or said sub-elements from said perspective, based on information derived from the identified grid cells; and

ignoring, in a subsequent step of visibility computations, at least one of said 3-D surfaces or said sub-elements that has been determined to be invisible in said computing step, wherein said step is with respect to said perspective.

60. The method of claim 56, wherein the data to be compared with the data of said computer storage are related to the shortest depths of said 3-D surfaces or said sub-elements.

57. A method of reducing visibility computations in 3-D computer graphics with respect to a viewpoint, the method comprising:

employing at least one projection plane for generating projections with respect to a perspective of said viewpoint;

dividing said at least one projection plane into at least one grid;

wherein said at least one grid is regular;

identifying, from said perspective, grid cells which are related to the projections or extents of the projections;

said projections are related to 3-D surfaces, sub-elements of said 3-D surfaces, bounding volumes of said 3-D surfaces, or bounding volumes of said sub-elements, wherein said identified grid cells are represented by a data structure based on a z-buffer;

computing visibility of at least one of said surfaces or said sub-elements from said perspective, based on information derived from the identified grid cells; and

ignoring, in a subsequent step of visibility computations, at least one of said 3-D surfaces or said sub-elements that has been determined to be invisible in said computing step;

wherein said step is with respect to said perspective.

58. The method of claim 57 further comprising, after the step of identifying grid cells, updating data related to said 3-D surfaces or said sub-elements in a computer storage related to said identified grid cells.

59. The method of claim 58, wherein the data to be compared with the data of said computer storage are related to the depths of said 3-D surfaces or said sub-elements.

61. The method of claim 58, wherein the data to be compared with the data of said computer storage are related to the largest depths of said 3-D surfaces or said sub-elements.

62. The method of claim 58, wherein at least some of the data to be compared with the data of said computer storage are related to the bounding volumes of said 3-D surfaces or said sub-elements.

63. The method of claim 58, wherein the computer storage is accelerated by cache memory.

64. A method of reducing the visibility related computations in 3-D computer graphics, said visibility related computations being performed on 3-D surfaces or their sub-elements, or a selected set of both, said visibility related computations is from the perspective of a viewpoint, the method comprising:

prior to a visibility computation, identifying grid cells which are under or related to at least one projection or at least one extent of projection that is associated with at least one of said 3-D surfaces or their sub-elements, said at least one projection or at least one extent of projection is from the perspective of said viewpoint;

comparing the data associated with at least one of said 3-D surfaces, their sub-elements, bounding volumes of said 3-D surfaces, or bounding volumes of said sub-elements with the stored data associated with the grid cells;

determining which of said at least one of said 3-D surfaces, or sub-elements is invisible to said viewpoint; and

if said at last one of said 3-D surfaces or sub-elements is determined to be invisible to said viewpoint, ignoring the entity or entities during said visibility computation.

65. A method in 3-D computer graphics for processing the visibility of 3-D surfaces before a subsequent step of visibility computations, said method comprising:

for each selected 3-D surface or sub-element of a 3-D surface, identifying grid cells on a projection plane which are under or related to a projection associated with said selected 3-D surface or sub-element, said projection and said subsequent step of visibility computations are from the perspective of a same viewpoint;

for each of said grid cells, accessing the corresponding z-buffer element; and

computing the visibility of the part of said selected 3-D surface or sub-element that projects onto said each of said grid cells by comparing the depth-related data stored in said corresponding z-buffer element with the depth-related value associated with said part.

66. The method of claim 65, further includes the step of using the visibility information computed for said selected 3-D surface or sub-element to reduce the computation for said selected 3-D surface or sub-element in said subsequent step of visibility computations.

67. A method in 3-D computer graphics for processing the visibility of 3-D surfaces before a subsequent step of visibility computations, said method comprising:

for each selected 3-D surface or sub-element of a 3-D surface, identifying grid cells on a projection plane which are under or related to a projection associated with the bounding volume of said selected 3-D surface or sub-element, said projection and said subsequent step of visibility computations are from the perspective of a same viewpoint;

for each of said grid cells, accessing the corresponding z-buffer element; and

computing the visibility of the part of the bounding volume that projects onto said each of said grid cells by comparing the depth-related data stored in said corresponding z-buffer element with the depth-related value associated with said part.

68. The method of claim 67, fixer includes the step of using the visibility information computed for said selected 3-D surface or sub-element to reduce the computation for said selected 3-D surface or sub-element in said subsequent step of visibility computations.