Image drawing system and method with real-time occlusion culling

• US 6,259,452 B1
• Filed: 03/20/1998
• Issued: 07/10/2001
• Est. Priority Date: 04/14/1997
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Coorg, Satyan R., Teller, Seth J.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/045,295
• Time in Patent Office: 1,208 Days
• Field of Search: 345/421, 345/418, 345/419, 345/420, 345/427
• US Class Current: 345/421
• CPC Class Codes: G06T 15/405 using Z-buffer

Abstract

To avoid needless processing of non-visible portions of a 3D scene, an occlusion culling method which dynamically identifies large occluders as the viewpoint moves is applied to discard non-visible polygons early in the graphics pipeline, i.e., in object space. The method is conservative, i.e., it overestimates the set of visible polygons; it exploits spatial coherence by using a hierarchical data structure; and it exploits temporal coherence by reusing visibility information such as supporting and separating computed for previous viewpoints. Objects are called from a three-dimensional object database if they are fully occluded from sight of the viewpoint due to either occluders near the viewpoint or occluders near the objects themselves. Objects which have not been called are drawn. Supporting planes tangential to an occluder and object set are used to determine occlusion.

Claims

1. A method of drawing an image constructed, relative to a viewpoint and a field of view, from a three-dimensional object data base comprising:

in object space, dynamically identifying individual occluders within the field of view;

in object space, determining and culling objects from the object data base which are within the field of view, but fully occluded from sight of the viewpoint by the identified occluders; and

drawing objects which have not been culled from the object data base relative to the point of view.

2. A method as claimed in claim 1 wherein the object data base is partitioned into cells and objects are culled by determining whether cells which contain the objects are fully occluded from sight.

3. A method as claimed in claim 1 wherein an object is culled by defining a viewing region of object space from which the object is occluded from sight, and culling the object when the point of view is within the defined region.

4. A method as claimed in claim 3 further comprising:

dynamically determining information about viewing regions of object space from which objects are occluded and retaining this information for reuse by subsequent culling operations corresponding to a changed viewpoint.

5. A method as claimed in claim 4 wherein a region is defined by supporting planes which are tangential to an occluder and an object set.

6. A method as claimed in claim 5 wherein the object set is a cell partitioned from the object space.

7. A method as claimed in claim 5 wherein the object set is a single object.

8. A method as claimed in claim 1, further comprising identifying significant occluders by statically identifying potential occluders based on apparent size and dynamically selecting significant occluders based on current viewing direction.

9. A method as claimed in claim 8 wherein a determination of apparent size of an occluder is based on an estimate of the solid angle the potential occluder subtends relative to the viewpoint.

10. A method as claimed in claim 8 wherein a determination of apparent size of an occluder is based on an estimate of the solid angle the potential occluder subtends relative to a center of an object set.

11. A method as claimed in claim 1 wherein the step of culling comprises:

identifying a potential occluder relative to an object set from the object database;

defining a region of space from which the object set is occluded from sight by the potential occluder; and

culling the object set when the point of view is within the defined region.

12. A method of drawing an image constructed relative to a viewpoint and a field of view, from a three-dimensional object data base comprising:

in object space, culling objects from the object data base through tests including;

determining and culling objects which are fully occluded from sight of the viewpoint due to occluders near to the point of view, and

determining and culling objects which are fully occluded from sight of the viewpoint due to occluders near to the objects; and

drawing objects which have not been culled from the object data base relative to the point of view.

13. A method as claimed in claim 12 wherein a region is defined by supporting planes which are tangential to an occluder and an object set.

14. A method as claimed in claim 13 wherein the object set is a cell partitioned from the object space.

15. A method as claimed in claim 13 wherein the object set is a single object.

16. A method as claimed in claim 12 further comprising:

retaining information about regions of object space from which each object is occluded for reuse by subsequent culling operations corresponding to a changed viewpoint.

17. A system for drawing an image constructed, relative to a viewpoint and a field of view, from a three-dimensional object data base comprising:

an occluder identifier which in object space, dynamically identifies individual occluders within the field of view;

a culler which in object space, determines and culls objects from the object data base which are within the field of view, but fully occluded from sight of the viewpoint by the identified occluders; and

a drawer which draws objects which have not been culled from the object data base relative to the point of view.

18. The system of claim 17 wherein the object data base is partitioned into cells and culled objects are selected from the object data base by determining whether cells which contain the objects are fully occluded from sight.

19. The system of claim 17 wherein an object from the object data base is identified as a culled object when the point of view is within a viewing region of object space from which the object is occluded from sight.

20. The system of claim 19 wherein information about viewing regions of object space from which objects are occluded is dynamically determined and retained for reuse by subsequent identification of culled objects for a changed viewpoint.

21. The system of claim 20 wherein a region is defined by supporting planes which are tangential to an occluder and an object set.

22. The system of claim 21 wherein the object set is a cell partitioned from the object space.

23. The system of claim 21 wherein the object set is a single object.

24. The system of claim 17 wherein occluders are dynamically identified by first statically identifying potential occluders based on apparent size, and then selecting significant occluders from among the potential occluders based on current viewing direction.

25. An article of manufacture, comprising:

a computer-readable medium;

on the computer-readable medium, a computer-implemented program for drawing an image constructed, relative to a viewpoint and a field of view, from a three-dimensional object data base, the program comprising;

an occluder identifier which in object space, dynamically identifies individual occluders within the field of view;

a culler which in object space, determines and culls objects from the object data base which are within the field of view, but fully occluded from sight of the viewpoint by the identified occluders; and

a drawer which draws objects which have not been culled from the object data base relative to the point of view.

26. The article of claim 25 wherein the object data base is partitioned into cells and objects are culled by determining whether cells which contain the objects are fully occluded from sight.

27. The article of claim 25 wherein an object is culled by defining a viewing region of object space from which the object is occluded from sight, and culling the object when the point of view is within the defined region.

28. The article of claim 27 further comprising dynamically determining information about viewing regions of object space from which objects are occluded and retaining this information for reuse by subsequent culling operations corresponding to a changed viewpoint.

29. The article of claim 28 wherein a region is defined by supporting planes which are tangential to an occluder and an object set.

30. The article of claim 29 wherein the object set is a cell partitioned from the object space.

31. The article of claim 29 wherein the object set is a single object.

32. The article of claim 25 wherein the occluder identifier dynamically identifies significant occluders by first statically identifying potential occluders based on apparent size and then dynamically selecting significant occluders based on current viewing direction.

33. The article of claim 32 wherein a determination of apparent size of an occluder is based on an estimate of the solid angle the potential occluder subtends relative to the viewpoint.

34. The article of claim 32 wherein a determination of apparent size of an occluder is based on an estimate of the solid angle the potential occluder subtends relative to a center of an object set.

35. The article of claim 25 wherein the culler culls objects dynamically by:

identifying a potential occluder relative to an object set from the object database,

defining a region of space from which the object set is occluded from sight by the potential occluder, and

culling the object set when the point of view is within the defined region.

36. An article of manufacture, comprising:

a computer-readable medium;

in the computer-readable medium, a computer-implemented method for drawing an image constructed, relative to a viewpoint and a field of view, from a three-dimensional object data base, the method comprising the steps of;

culling, in object space, objects from the object data base through tests including;

determining and culling objects which are fully occluded from sight of the viewpoint due to occluders near to the point of view, and

determining and culling objects which are fully occluded from sight of the viewpoint due to occluders near to the objects; and

drawing objects which have not been culled from the object data base relative to the point of view.