Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-01-15
2001-08-21
Segley, Lance W. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000, C345S428000
Reexamination Certificate
active
06278457
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data processing systems that store, manipulate and display three-dimensional (3-D) geometric models, and more particularly to those systems and methods that employ simplified 3-D geometric models.
BACKGROUND OF THE INVENTION
It is often necessary to generate simplified versions of geometric models. Such simplified models can be used, for example, to display scenes having a polygon count that exceeds the capacity of graphics hardware. The use of simplified models is also advantageous when transmitting a model over a network having a limited bandwidth.
Several algorithms for automatic simplification are currently known in the art. When dealing with curved, finely tessellated surfaces one technique iteratively removes a vertex and incident polygons, and then retessellates the “hole” that is formed. The sequence of vertices considered for removal can be chosen based on simple heuristics or on complex optimization strategies. While this conventional technique normally preserves the topology of the original model its use is, however, restricted to objects with a well defined topology (often to two-manifolds only). Furthermore, this technique cannot, in general, enable a significant reduction in polygon count. Several variants of this method are described in the literature, e.g. by Hughes Hoppe et al. Mesh Optimization, Proc. of SIGGRAPH '93, pp. 19-26.
A different approach is based on collapsing nearby vertices to a single representative vertex, and removing polygons whose area becomes zero. By repeating this process on groups of vertices of increasing size, a hierarchy of simplified models is obtained. This method is fast and can readily handle ill-defined models. The resulting simplified models, however, may not have a desired quality for a particular application. Reference in this regard can be had to commonly assigned U.S. Pat. No. 5,448,686, entitled “Multi-Resolution Graphic Representation Employing at Least One Simplified Model for Interactive Visualization Applications”, by Paul Borrel and Jaroslaw R. Rossignac.
While these conventional techniques may be suitable for use for many model simplification problems, it is desirable to provide an improved method that is capable of operating at high speed while providing a simplified model that accurately and faithfully represents an original, more complex model.
OBJECTS AND ADVANTAGES OF THE INVENTION
It is a first object and advantage of this invention to provide an improved geometric model simplification method.
It is a further object and advantage of this invention to provide a method for simplifying a geometric model that samples one or more rendered images of the model, and that derives the simplified model from the sampled images.
SUMMARY OF THE INVENTION
The foregoing and other problems are overcome and the objects and advantages are realized by methods and apparatus in accordance with embodiments of this invention, wherein a technique is disclosed for the automatic synthesis of three-dimensional geometric models. The approach taken by the inventors is based on collecting a number of sample points on a surface of a model, and then reconstructing an approximation of the surface's shape from the samples. Depending on the density of the sampling, simplified models of varying accuracy and complexity can be generated.
More particularly, a presently preferred computer implemented method for generating a simplified version of a geometric model includes a first step of visualizing a geometric model from at least one viewpoint and then sampling surfaces of the visualized geometric model to generate a set of primary sample points. A next step executes a polyhedral synthesis technique using the set of primary sample points by the steps of computing a three dimensional Delaunay triangulation of the primary sample points to generate triangles; extracting an alpha-solid using the generated triangles; and obtaining the simplified model from the boundary of the extracted alpha-solid. An optional step refines the simplified model using a set of secondary sample points.
REFERENCES:
patent: 5448686 (1995-09-01), Borrel et al.
patent: 5633951 (1997-05-01), Moshfeghi
patent: 5923333 (1999-07-01), Stroyan
Edelsbrunner et al., “Three-Dimensional Alpha Shapes”, Jan. 1994.*
Garcia, “Fast Approximation of Range Images by Triangular Meshes Generated through Adaptive Randomized Sampling”, 1995.*
Garcia, Miquel Angel, “Fast Approximation of Range Images by Triangular Meshes Generated through Adaptive Randomized Sampling”, IEEE, Japan, 1995, 6 pages.
Hoppe, Hugues et al., “Mesh Optimization”, Computer Graphics, 1993, pp. 19-25.
Edelsbrunner, Herbert et al., “Three-Dimensional Alpha Shapes”, ACM Transactions on Graphics, vol. 13, No. 1, Jan. 1994, pp. 43-72.
Bernardini Fausto
Borrel Paul
Menon Jai P.
August Casey P.
International Business Machines - Corporation
Perman & Green LLP
Segley Lance W.
LandOfFree
Methods and apparatus for performing sampling based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for performing sampling based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for performing sampling based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2475760