Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-02-27
2004-11-30
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000
Reexamination Certificate
active
06825839
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer graphics and solid modeling, and more particularly, to methods and apparatuses for representing and displaying an object of its skeleton, atomic parts, and hierarchy.
BACKGROUND OF THE INVENTION
The quest for ease of modeling in three-dimensional computer graphics has led to the development of several well-known techniques, such as constructive solid geometry, free-form deformation, non-uniform rational B-splines, or more recently, implicit surfaces. Today's graphics hardware, however, is only capable of dealing with polygons efficiently. Hence, models are often tessellated before display for efficient rendering.
Related to 3D modeling is 3D model acquisition. The difficulty of obtaining a good 3D model has led to development in this area, using methods such as laser range scanners and turntable techniques. Such methods produce massive point sets representing points on the model's surface and require further processing such as 3D triangulation. The result is again a polygon mesh.
A tradeoff has to be established between having a high quality model with a high polygon count, and fast rendering with fewer polygons. The ever-increasing number crunching capability of today's processors tends to push the envelope of polygon count for efficient rendering, making it feasible to use more complex models.
Working on the premise of polygon mesh, however, leads to many difficulties. A polygon mesh is inherently unstructured, making it expensive to perform geometric operations such as intersection tests in collision detection and ray tracing. In the present invention, we are interested in object representation as in its object hierarchy.
The object hierarchy is most natural in terms of the human concept of shape. This has to do with the fact that cognition works best for hierarchically organized systems. In fact, 3D modelers often exhibit this phenomenon unknowingly when they organize an object in a top-down fashion. Although the object hierarchy is a natural representation of shape, it is often non-unique and designer-specific. Even so, the variations are usually minor and do not affect the conceptualization of the model on the whole. The present invention describes an algorithm for determining first a collection of atomic parts of an input polygon mesh and for determining a unique hierarchy from the atomic parts.
It is conceivably easy to obtain an object hierarchy from certain representations of models, for instance, constructive solid geometry models. However, the same cannot be said of geometric models, particularly B-rep models, which are by far the most prevalent. UCOLLIDE [TAN99] is a collision detection system that makes use of simplification to compute bounding volume hierarchies. The novelty of this work lies in the use of cluster-based simplification [LOW97] for extracting shape, and the use of this shape information for computing bounding volume hierarchies. Traditionally, bounding volume hierarchies are generated by top-down partitioning or bottom-up merging. Bottom-up methods only work well for organizing objects in a scene, and not polygons per se. Top-down methods perform poorly when the object to be partitioned consists of many sparsely arranged parts. Hence, it is difficult to achieve optimal or near optimal bounding volume hierarchies using either method.
[TAN99] uses simplification and shape analysis to extract the major components (or atomic parts) of an object. Further shape analysis on the simplified model yields the components of the model. Partitioning on each component can then be done using traditional top-down methods.
For complex models with numerous interconnected parts, it is insufficient to use only one simplified model or also called level-of-details (LOD) for shape analysis. This is because it is difficult to pinpoint one LOD that captures all the essential features of a model. By using a few LODs, the decomposition of a model can be guided along each node of the parent LOD and a hierarchy is naturally obtained. Although reasonably good results can be obtained using this method, there are some issues that remain to be addressed:
(i) the association of polygons in a lower LOD to a higher one may not be straightforward;
(ii) it is not clear what is the desired number of LOD and how to choose them;
(iii) different LODs produce different results; and
(iv) vertex clustering can cause topology change in the model. How this affects decomposition is unclear.
In addition, simplification using vertex clustering is not incremental. The algorithm needs to be invoked a number of times for LOD generation and this can cause a performance penalty. In light of all these issues, an alternative formulation of shape extraction is developed in the current invention.
SUMMARY AND OBJECTS OF THE INVENTION
The invention described herein satisfies the above-identified needs and overcomes the limitations of the prior invention by [TAN99]. The present invention describes a new system and method to effectively generate object hierarchies, for purposes of various interactive applications such as:
(i) Organizing an arbitrary mesh for scene management and view-dependent simplification;
(ii) Providing an alternative structure to one given by modeler;
(iii) Visualizing complex models;
(iv) Mesh-mapping; for morphing, establishing correspondence; and
(v) Building bounding volume hierarchy (BVH) for intersection tests in collision detection and ray tracing.
Specifically, disclosed herein is a method for execution by a data processor that generates effective object hierarchies. The method includes the following steps:
(1) Preprocessing. This is to prepare data structures for subsequent processes.
(2) Skeletonization. This is the process of deriving a skeleton of the input model, where skeleton is a fully collapsed body of the model.
(3) Generating Atomic Parts. This is the process of obtaining various features (which is a part of the model that is distinctively autonomous from its connected or neighboring body) from the skeleton.
(4) Postprocessing. This process connects various atomic parts obtained from previous step into a hierarchy.
Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.
REFERENCES:
patent: 5825369 (1998-10-01), Rossignac et al.
patent: 5894308 (1999-04-01), Isaacs
patent: 6054991 (2000-04-01), Crane et al.
patent: 6563500 (2003-05-01), Kim et al.
patent: 0854441 (1998-07-01), None
Computing Bounding Volume Hierarchies Using Model Simplification; Tan, Chong and Low; 1999; ACM Symposium; pp. 63-69.*
Space Sweep Solves Intersection of Convex Polyhedra; Hertel, Mantyla, Mehlhorn, and Nievergelt; 1984.*
Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, 1983, pp. 428-448, ACM 0004 5411/83/0700-0428.*
Jaromczyk et al., A note on Relative Neighborhood Graphs, 1987, pp. 233-241, ACM 0-89791-231-4/87/0006/0233.*
Shewchuk, Sweep Algorithms for Constructing Hlgher-Dimensional Constrained Delaunay Triangulations, pp. 350-359, ACM 2000 1-58113-224-7/0/6.*
Franklin, Polygon Properties Calculated From the Vertex Neighborhoods, pp. 110-118, ACM 0-89791-231-4/87/0006/0110.*
Nievergelt, “PLane-Sweep Algorithms for Intersecting Geometric Figures”, pp. 739-747, ACM 0001-0782/82/1000-0739.*
Computers & Graphics, vol. 22(6), Dec. 1, 1998, pp. 667-674 A. Schilling and R. Klein “Rendering of Multiresolution Models With Texture”.
Computers & Graphics, Voume 23(1) Jan. 2, 1999, pp. 59-72, D. Shikare, S. Gopalsamy et al. Zeus: Surface Modeling, Surface Grid Generation, Tetrahedral Volume Discretization.
[BARE96&rs
Huang Zhiyong
Li Xuetao
Tan Tiow Seng
Woon Tong Wing
Birch & Stewart Kolasch & Birch, LLP
The National University of Singapore
Wallace Scott
Zimmerman Mark
LandOfFree
Method and apparatus for generating atomic parts of graphic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating atomic parts of graphic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating atomic parts of graphic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3309767