Computer graphics processing and selective visual display system – Computer graphics processing – Animation
Reexamination Certificate
2001-04-04
2004-06-08
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Animation
C345S420000, C345S426000
Reexamination Certificate
active
06747651
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATION
The subject matter of this application is related to U.S. application Ser. No. 09/065,488 filed Apr. 24, 1998, entitled “Multi-Resolution Graphic Representation Generated By Weight-Controlled Vertex Clustering For Interactive Visualization Applications” assigned to the assignee of this invention, and incorporated herein by reference.
FIELD OF THE INVENTION
The present invention relates generally to computer graphics and virtual reality. More specifically, the invention relates to systems and methods for generating bounding volume hierarchies for use in the checking of collisions among objects in complex interactive computer environments or in ray tracing computation to generate photo-realistic computer images.
BACKGROUND OF THE INVENTION
Fast rendering and collision detection are two fundamental goals of many interactive 3D graphics applications. Many realistic-looking 3D models, containing millions of polygons all of which may be visible in a complex scene, cannot be effectively rendered at interactive frame rates. A solution for this problem is to use multi-resolution or level-of-detail modeling, in which each object has a series of geometric approximations with increasingly lower rendering cost, while still resembling the original models from all directions. On the other hand, navigation in a complex scene requires extensive interference detection between models and thus needs support from very efficient collision detection data structures to achieve interactive frame rates.
There is an interest in interactive visualization and manipulation of architectural, mechanical and CAD models in applications such as computer simulation, computer game, object modeling, and virtual prototyping. Such applications may be standalone, distributed or over the world-wide-web. Systems and methods that detect collisions have been described in:
U.S. Pat. No. 5,572,634, “Method and Apparatus for Spatial Simulation Acceleration” issued to Jerome Duluk, Jr., Nov. 5, 1996;
U.S. Pat. No. 5,515,489, “Collision Detector Utilizing Collision Contours” issued to Larry Yaeger, May 7, 1996;
U.S. Pat. No. 4,888,707, “Object Collision Detection Method and Apparatus” issued to Kenji Shimada, Dec. 19, 1989;
European Patent No. 780798, “Method and Apparatus for Object Identification and Collision Detection in Three Dimensional Graphics Space” issued to Devic Goran, Jan. 7, 1998.
Systems and methods for utilizing spherical or voxel models of objects to assist collision detection in specific application areas are described in:
U.S. Pat. No. 5,548,694, “Collision Avoidance System for Voxel-Based Object Representation” issued to Sarah Frisken Gibson, Aug. 20, 1996;
U.S. Pat. No. 5,347,459, “Real Time Collision Detection” issued to Michael Greenspan et. al., Sep. 13, 1994;
U.S. Pat. No. 5,056,031, “Apparatus for Detecting the Collision of Moving Objects” issued to Masaru Nakano et. al., Oct. 8, 1991.
The above teachings concentrate on the process of collision detection and the applications to specific domains. On the other hand, the present invention is a method for processing an arbitrary collection of objects, in a simulated computer environment, into hierarchies of bounding volumes. The following teachings are most relevant to the present invention:
(1) U.S. Pat. No. 5,613,049, “Method for Creating Spatially Balanced Bounding Volume Hierarchies for Use in a Computer Generated Display of a Complex Structure” issued to Brechner et al., Mar. 18, 1997;
(2) G. Barequet, B. Chazelle, L. Guibas, J. Mitchell and A. Tal, “
BOXTREE:: A Hierarchical Representation for Surfaces in
3
D
”, Proceedings Eurographics '96, Vol. 15(3), pp. C-387-396, C-484, August 1996;
(3) S. Gottschalk, M. C. Lin and D. Manocha, “
OBBTree:: A Hierarchical Structure for Rapid Interference Detection
”, Computer Graphics (SIGGRAPH '96 Proceedings), pp. 171-179, 1996;
(4) J. Klosowski, M. Held, J. Mitchell, H. Sowizral and K. Zikan, “
Efficient Collision Detection Using Bounding Volume Hierarchies of k
-
DOPs
”, IEEE Transactions on Visualization and Computer Graphics, vol. 4 (1), 1998, pp 21-36.
Although the above documents provide significant advances in constructing good bounding volume hierarchies, there still remains many controversial design issues, such as top-down verses bottom-up construction approaches; choices between the types of bounding volumes, and various splitting rules for building the hierarchies (see, for example, Klosowski et. al.,1998). Some of these choices involve expensive computation. It is not readily apparent which choices are better.
Many popular approaches are based either on the hierarchies of bounding volumes that successively approximate parts of the input model until the exact geometry of the model is reached, or spatial decomposition of the space occupied by the model. Both ideas are aiming to reduce the number of pairs of objects or primitives that need to be checked for contact.
Besides collision detection, bounding volume hierarchies are also utilized to accelerate ray tracing process to generate photo-realistic computer images (see Arvo and Kirk, “A Survey of Ray Tracing Acceleration Techniques”, in An Introduction to Ray Tracing, A. S. Glassner, ed., pp. 201-262, Academic Press, 1990). Relevant teachings include:
(1) J. Goldsmith and J. Salmon, “Automatic Creation of Object Hierarchies for Ray Tracing”, IEEE Computer Graphics and Applications, vol. 7(5), pp.14-20, May 1987;
(2) I. Scherson and E. Caspary, “Data Structures and the Time Complexity of Ray Tracing”, The Visual Computer, vol. 3, pp. 201-213, 1987 (see Section 5);
(3) A. Glassner, “Spacetime Ray Tracing for Animation”, IEEE Computer Graphics and Applications, vol. 8(3), pp. 60-70, March 1988 (see pp. 62-63);
(4) F. Sillion and G. Drettakis, “Feature-based control of Visibility Error: A Multi-Resolution Clustering Algorithm for Global illumination”, Computer Graphics (SIGGRAPH'95 Proceedings), pp. 145-152, August 1995 (see pp. 149);
(5) K. Whang, J. Song, J. Chang, J. Kim, W. Cho, C. Park and
1
. Song, “Octree-R: An Adaptive Octree for Efficient Ray Tracing”, IEEE Transactions on Visualization and Computer Graphics, vol. 1(4), December 1995;
(6) U.S. Pat. No. 5,613,049, “Method for Creating Spatially Balanced Bounding Volume Hierarchies for Use in a Computer Generated Display of a Complex Structure” issued to Brechner et al., Mar. 18, 1997;
(7) K. Klimaszewski and T. Sederberg, “Faster Ray Tracing Using Adaptive Grids”, IEEE Computer Graphics and Applications, vol. 17(1), pp. 42-51, 1997.
In Kay and Kajiya, “Ray Tracing Complex Scenes”, Computer Graphics (SIGGRAPH'86 Proceedings), pp. 269-278, August 1986 (see Section 3.1), the authors mentioned several interrelated properties that would seem to distinguish a good hierarchy from a bad one. These include (i) any given sub-tree in the hierarchy should contain objects that are near each other; (ii) the bounding volume of each node should be minimal; (iii) the sum of all bounding volume should be minimal; and (iv) the construction of the tree should concentrate on the nodes nearer the root of the tree. To date, finding close to optimal hierarchy remains a partially solved problem.
SUMMARY AND OBJECTS OF THE INVENTION
It is thus an object of this invention to provide a new system and method to generate effective bounding volume hierarchy. The current invention exploits shape information obtainable from simplified models to partition input model into its natural components so as to generate effective bounding volume hierarchy.
Specifically the inventive method includes first a step of generating simplified models; second, deriving various components of the input model from clues in simplified models; third, joining various components into a hierarchy to form the top few levels of the eventual bounding volume hierarchy; and then finally partitioning parts of each minimal sub-component into the bounding volume hierarchy.
This invention can be used to build a software system or an apparatus that generates effective bounding volume hierarchies for c
Chong Ket Fah
Low Kok Lim
Tan Tiow Seng
Birch & Stewart Kolasch & Birch, LLP
National University of Singapore
Sealey Lance W
Zimmerman Mark
LandOfFree
System and method for creating bounding volume hierarchies... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for creating bounding volume hierarchies..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for creating bounding volume hierarchies... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3365479