Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-03-22
2004-07-06
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06760023
ABSTRACT:
TECHNICAL FIELD
This invention relates in general to the field of computer graphics and more particularly to the field of simplification of geometrical representations of objects.
BACKGROUND OF THE INVENTION
Geometric models, usually represented by a collection of triangles, are becoming increasingly complex, as acquisition systems improve. The performance of interactive environments using or displaying the data can be improved by reducing the size of the data. This data size reduction is the objective of surface simplification techniques. Such techniques accept surfaces as input and return arbitrarily simplified surfaces as output.
One data modeling technique is modeling three-dimensional surfaces as height fields. In a height field a two-dimensional grid has a corresponding value in a third dimension, i.e., for each (x,y) coordinate there is a corresponding height, z. Height field data is an important geometric representation in many fields, such as geoscience.
One problem is how to simplify height field data which contains missing values, in particular, how to generate topologically correct continuous level of detail (LOD) approximations efficiently. A topologically correct simplification is one that does not have self-intersections of boundaries in parameter space in any approximation and also preserves the genus of the surface. A configuration demonstrating a self-intersecting simplification is shown in FIG.
2
. The standard simplification operators presented in the literature cannot handle the self-intersection problem well, and consequently they cannot guarantee intersection-free approximation in image space. This problem has previously been attacked using two different strategies:
I. Explicitly checking whether a simplification operation introduces self-intersections (O. G. Staadt and M. H. Gross, “Progressive tetrahedralizations,”
Proceedings IEEE Visualization '
98, pp. 397-402, IEEE, 1998.). However, these check operations are global in nature, and although they can be accelerated, slow the simplification algorithms down.
II. Detecting self-intersections using local operations by triangulating the holes present in the surface. Depending on the simplification operator used, a self-intersection can be detected by analyzing the neighbor triangles defined over the hole. For example, if the vertex x
ij
of
FIG. 2
a
was to be removed using an edge collapse operation (described in greater detail below and in H. Hoppe, “Progressive meshes,” In H. Rushmeier, editor,
SIGGRAPH
96
Conference Proceedings,
Annual Conference Series, pages 99-108, ACM SIGGRAPH, Addison Wesley, August 1996.) onto the vertex x
k,l
, the self-inter-section that would be introduced could be detected by noting that the gray triangle
201
flipped as illustrated by the triangles
201
′ and
201
″ of
FIG. 2
b
during the operation.
Surface simplification is an important core technology in many applications, and as a consequence many different research groups have focused on creating flexible and efficient frameworks to handle large data sets. One approach is introduced in W. J. Schröder, J. A. Zarge, and W. E. Lorensen. “Decimation of triangle meshes.” In E. E. Catmull, editor,
ComputerGraphics
(
SIGGRAPH '
92
Proceedings
), volume 26, pages 65-70, July 1992 and further described in U.S. Pat. No. 5,590,248, to Jonathan A. Zarge and William J. Schroeder, “Method for Reducing the Complexity of a Polygonal Mesh, filed Feb. 24, 1995, continuation of Ser. No. 815,772, Jan. 2, 1992, abandoned. In that article, the authors introduced the fundamental vertex removal operator. Using this operator, surfaces are simplified by removing one vertex at a time, and then re-triangulating the hole introduced by removal operation. This operator, in conjunction with a divide and conquer triangulation strategy, is powerful enough to handle complex surfaces, such as general two-manifolds. The operator was subsequently used as one approach to construct multiresolution representations of height field data.
The second fundamental operator of edge collapse was introduced in H. Hoppe. “Progressive meshes.” In H. Rushmeier, editor,
SIGGRAPH
96
Conference Proceedings
, Annual Conference Series, pages 99-108. ACM SIGGRAPH, Addison Wesley, August 1996, held in New Orleans, La., Aug. 04-09, 1996. This technique is also described in U.S. Pat. No. 5,929,860 to Hoppe; Hugues H., entitled “Mesh simplification and construction of progressive meshes,” filed Feb. 7, 1997, continuation of Ser. No. 08/586,953, filed Jan. 11, 1996.
The edge-collapse operator simplifies meshes by collapsing the pair of vertices joined by an edge. The advantage of this approach is that there is no need to re-triangulate holes as in the case of vertex removal algorithms. On the downside, meshes generated by this approach might have poor characteristics, unless the set of allowable edge collapses are chosen carefully.
While the previous operators are generally applicable to two-manifold surfaces, much effort has been spent in constructing representations for height field data stored in regular grids. In M. H. Gross, O. G. Staadt, and R. Gatti. “Efficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structures.”
IEEE Transactions on Visualization and Computer Graphics,
2(2):130-143, June 1996, the authors used a wavelets representation of height fields coupled with a look-up table to construct multi-resolution approximations of data defined on a regular domain. In R. Pajarola. “Large scale terrain visualization using the restricted quadtree triangulation.”
In Proceedings IEEE Visualization'
98, pages 19-26. IEEE, 1998, a quadtree was used to store the data. By restricting the choice of the vertices present in any approximation, Pajarola could define a look-up table that not only could triangulate the chosen vertices, but could also generate a single triangle strip. Both of these approaches have the advantage of being fast, since they are optimized for height field data, but they have the disadvantage that they work best with grids whose size is a power of two. If this is not the case, then it is necessary to extend the basic algorithms to handle many different special cases. For the same reason, it would be extremely difficult to let these structures handle height fields with missing values.
All of the representations discussed in this section are capable of guaranteeing that a simplification operation will not change the topology of the surface locally. However, none of them is capable of guaranteeing that a simplification operation will not introduce a self-intersection. With avoidance of self-intersection as a requirement, one of the two approaches described above would need to be implemented.
For these reasons there is an unmet need for an efficient surface simplification method that accepts a height field as input and that produces a topologically correct surface simplification.
REFERENCES:
patent: 5590248 (1996-12-01), Zarge et al.
patent: 5847711 (1998-12-01), Kaufman et al.
patent: 5929860 (1999-07-01), Hoppe
Devillers, O., “On deletion in dulanay triangulation,”Technical Report RR-3451, Inria, Institut National de Recherche en Informatique et en Automatique, 1999.
Dey, T. et al., “Topology preserving edge contraction,”Technical Report, Raindrop Geomagic Inc., Research Triangle Park, North Carolina, 1998.
Gross, M. H. et al., “Efficient Triangular Surface Approximations using Wavelets and Quadtree Data Structures,”IEEE Transactions on Visualization and Computer Graphics, 2(2):130-143, Jun. 1996.
Hammersley, R. et al., “Decremental Delaunay Triangulation.” In ACM, editor,SIGGRAPH 99, Proceedings of the 1999 SIGGRAPH annual conference: Conference abstracts and applications, Computer Graphics, pp. 238-238, New York, NY 10036, USA, 1999. ACM Press.
Hoppe, H., “Progressive Meshes.” In H. Rushmeier, editor,SIGGRAPH 96 Conference Proceedings, Annual Conference Series, pp. 99-108. ACM SIGGRAPH, Addison Wesley, Aug. 1996. Held in New Orleans, Louisana, Aug. 4-9, 1996.
Midtbo, T., “Removing points from
Hammersley Richard P.
Hubeli Andreas G. P.
Nguyen Phu K.
Schlumberger Technology Corporation
Schlumberger Technology Corporation
LandOfFree
System and method for correctly decimating height fields... 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 correctly decimating height fields..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for correctly decimating height fields... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3211403