Method for displaying a graphic model

• US 6,088,035 A
• Filed: 02/23/1998
• Issued: 07/11/2000
• Est. Priority Date: 08/16/1996
• Status: Expired due to Term

• Current Assignee: OptiTex Ltd. (Constellation Software Incorporated), Mental Images GmbH (NVIDIA Corporation)
• Original Assignee: Virtue Ltd.
• Inventors: Sudarsky, Oded, Gotsman, Graig J.
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): CAO, VAN B
• Application Number:
  US09/000,462
• Time in Patent Office: 869 Days
• Field of Search: 345/420, 345/421, 345/422, 345/356, 345/475
• US Class Current: 345/421
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

In a process for rendering a 3-dimensional graphics scene made up of a plurality of static and/or dynamic objects composed of geometrical elements, a method for obviating redundant processing and communications involved with hidden dynamic objects, so as to accelerate the rendering of successive images of the scene and to reduce communications requirements (FIG. 6C). The method includes in respect of each occluded dynamic object: (a) predicting a time period during which the object is expected to remain occluded; (b) generating a volume that contains the object during the time period; (c) inserting the volume into a spatial data structure used by an occlusion culling technique; (d) applying the occlusion culling technique so as to output-sensitively render the scene, yet not rendering or updating the occluded dynamic object during the time period, provided the occlusion culling technique does not find the volume to be visible.

Claims

1. In a process for rendering a 3-dimensional graphics scene comprising a plurality of static and/or dynamic objects composed of geometrical elements, a method for accelerating the rendering of successive images of said scene comprising the steps of:

(a) in an initialization step;

(i) determining which of the dynamic objects are visible and which are hidden at their initial positions,

(ii) creating temporal bounding volumes for the hidden dynamic objects consequent to projected motion thereof during a respective time period Δ

t not necessarily identical for all dynamic objects,

(iii) constructing a spatial data structure containing the static objects, the visible dynamic objects at their initial positions and the hidden dynamic objects'"'"' temporal bounding volumes, and

(iv) maintaining an event queue of the times at which the temporal bounding volumes are no longer assured to contain their respective dynamic objects,

(b) inserting the hidden dynamic objects which are no longer assured to be contained within their respective temporal bounding volumes, either because the event queue so reported or because the objects'"'"' motion violated some assumption by which the temporal bounding volumes were created, into the spatial data structure instead of the respective temporal bounding volumes,

(c) output-sensitively processing the spatial data structure so as to render its visible parts and so as to replace visible temporal bounding volumes by their respective dynamic objects,

(d) creating temporal bounding volumes for the hidden dynamic objects which do not already have temporal bounding volumes, inserting said temporal bounding volumes into the spatial database instead of the hidden dynamic objects and inserting into the event queue the times at which the temporal bounding volume will no longer be assured to contain their respective dynamic objects, and

(e) repeating steps (b) to (d) for each image to be rendered.

2. For use with the method according to claim 1, an initialization step comprising:

(i) determining which of the dynamic objects are visible and which are hidden at their initial positions,

(ii) creating temporal bounding volumes for the hidden dynamic objects consequent to projected motion thereof during a respective time period Δ

t not necessarily identical for all dynamic objects,

(iii) constructing a spatial data structure containing the static objects, the visible dynamic objects at their initial positions and the hidden dynamic objects'"'"' temporal bounding volumes, and

(iv) maintaining an event queue of the times at which the temporal bounding volumes are no longer assured to contain their respective dynamic objects.

3. For use with the method according to claim 1, a processing step comprising:

(b) inserting the hidden dynamic objects which are no longer assured to be contained within their respective temporal bounding volumes, either because the event queue so reported or because the objects'"'"' motion violated some assumption by which the temporal bounding volumes were created, into the spatial data structure instead of the respective temporal bounding volumes,

(c) output-sensitively processing the spatial data structure so as to render its visible parts and so as to replace visible temporal bounding volumes by their respective dynamic objects,

(d) creating temporal bounding volumes for the hidden dynamic objects which do not already have temporal bounding volumes, inserting said temporal bounding volumes into the spatial database instead of the hidden dynamic objects and inserting into the event queue the times at which the temporal bounding volume will no longer be assured to contain their respective dynamic objects, and

(e) repeating steps (b) to (d) for each image to be rendered.

4. The method according to claim 1, wherein a potentially visible dynamic object list is created of all potentially visible dynamic objects and step (a) includes the steps of:

(i) initializing the potentially visible dynamic object list to contain all dynamic objects and the event queue to be empty, and

(ii) if said scene contains static objects, constructing a spatial data structure containing the static objects; and

step (b) comprises the steps of;

(iii) inserting the hidden dynamic objects which are no longer assured to be contained within their respective temporal bounding volumes, either because the event queue so reported or because the objects'"'"' changes violated some assumption by which the temporal bounding volumes were created, into the potentially visible dynamic object list, and

(iv) obtaining the current position of every object in the potentially visible dynamic object list and inserting it into the spatial data structure;

there being further included the steps of constantly updating the potentially visible dynamic object list as previously hidden dynamic objects become visible and as previously visible dynamic objects become hidden.

5. The method according to claim 1, wherein a potentially visible dynamic object list is created of all potentially visible dynamic objects and step (a) includes the steps of:

(i) initializing the potentially visible dynamic object list to contain all dynamic objects and the event queue to be empty, and

(ii) if said scene contains static objects, constructing a spatial data structure containing the static objects.

6. The method according to claim 1, wherein a potentially visible dynamic object list is created of all potentially visible dynamic objects and step (b) includes the steps of:

(i) inserting the hidden dynamic objects which are no longer assured to be contained within their respective temporal bounding volumes, either because the event queue so reported or because the objects'"'"' changes violated some assumption by which the temporal bounding volumes were created, into the potentially visible dynamic object list, and

(ii) obtaining the current position of every object in the potentially visible dynamic object list and inserting it into the spatial data structure;

there being further included the steps of constantly updating the potentially visible dynamic object list as previously hidden dynamic objects become visible and as previously visible dynamic objects become hidden.

7. The method according to claim 1, wherein the spatial data structure is hierarchical and step (c) is performed recursively.

8. The method according to claim 7, wherein the spatial hierarchical data structure is an octree.

9. The method according to claim 7, wherein the spatial hierarchical data structure is an Binary Space Partitioning (BSP) tree.

10. The method according to claim 7, wherein the spatial hierarchical data structure is a k-D tree.

11. The method according to claim 1, wherein the spatial data structure is a regular grid and step (c) is performed iteratively.

12. The method according to claim 1, wherein step (d) is based on a predetermined object script in respect of at least one of the dynamic objects.

13. The method according to claim 1, wherein step (d) is based on predetermined motion and/or deformation constraints in respect of at least one of the dynamic objects.

14. The method according to claim 1, for eliminating unnecessary communications in a distributed system.

15. The method according to claim 1, for ray tracing a graphic object which is not necessarily seen directly but may be reflected by another graphic object or seen through another semi-transparent object or casts a shadow on another object.

16. The method according to claim 1, further including the step of displaying the resulting graphic images on a computer screen.

17. The method according to claim 1, wherein:

the scene is viewed from a stationary viewpoint,

most of the hidden dynamic objects are hidden by static objects, and

the time periods Δ

t are calculated exactly by starting with an initial time period Δ

t of one frame, repeatedly doubling the time period Δ

t until the bounding volume is no longer hidden by static objects, and then using binary search to find the exact moment at which the bounding volume starts to become visible.

18. The method according to claim 1, wherein the scene is viewed from a non-stationary viewpoint, and the time period Δ

t is reduced from an initial maximum value suitable for a stationary viewpoint so as to reduce the bounding volumes and thereby increase the time required for the hidden dynamic object to be revealed.

19. The method according to claim 1, wherein the time period Δ

t is adapted in order that if a previous time period for a dynamic object'"'"'s temporary bounding volume were too short such that the temporary bounding volume expired before the dynamic object was revealed, then a successive temporary bounding volume for the same dynamic object is created for a longer validity period, and vice versa.

20. The method according to claim 1, wherein the time period Δ

t is constant.

21. The method according to claim 1, wherein the time period Δ

t is set equal to a remaining time duration of the scene.

22. The method according to claim 1, wherein the time period Δ

t is set equal to a random time duration.

23. The method according to claim 1, wherein the time period Δ

t is inversely proportional to the velocity of the respective dynamic object.

24. The method according to claim 1, wherein steps (b) and (d) are based on probabilistic motion and/or deformation constraints:

i.e. constraint which the objects are not necessarily guaranteed to obey at all times, but only assumed to obey with some degree of probability.

25. A memory medium containing a spatial data structure accessible to a user application program for accelerating the rendering of successive images of a scene;

the spatial data structure comprising;

static objects and/or visible dynamic objects; and

temporal bounding volumes each relating to a projected motion of a respective hidden dynamic object during a respective time period Δ

t not necessarily identical for all dynamic objects.

26. A memory medium containing a user application program for accelerating the rendering of successive images of a scene;

the user application program utilizing a spatial data structure comprising static objects, visible dynamic objects, and temporal bounding volumes each relating to a projected motion of a respective hidden dynamic object during a respective time period Δ

t not necessarily identical for all dynamic objects;

said user application program performing the following steps;

(a) inserting the hidden dynamic objects which are no longer assured to be contained within their respective temporal bounding volumes, either because the event queue so reported or because the objects'"'"' motion violated some assumption by which the temporal bounding volumes were created, into the spatial data structure instead of the respective temporal bounding volumes,

(b) output-sensitively processing the spatial data structure so as to render its visible parts and so as to replace visible temporal bounding volumes by their respective dynamic objects,

(c) creating temporal bounding volumes for the hidden dynamic objects which do not already have temporal bounding volumes, inserting said temporal bounding volumes into the spatial database instead of the hidden dynamic objects and inserting into the event queue the times at which the temporal bounding volume will no longer be assured to contain their respective dynamic objects, and

(d) repeating steps (a) to (c) for each image to be rendered.

27. In a process for rendering a 3-dimensional graphics scene comprising a plurality of static and/or dynamic objects composed of geometrical elements, a method for obviating redundant processing of hidden dynamic objects in successive images of said scene so as thereby to accelerate the rendering of successive images of said scene;

the method including in respect of each hidden dynamic object;

(a) predicting a time period Δ

t during which said hidden dynamic object is assumed to remain hidden; and

(b) during said time period Δ

t, not rendering said hidden dynamic object so as to output-sensitively process the scene.