Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-05-08
2001-09-04
Sealey, Lance W. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000
Reexamination Certificate
active
06285372
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to techniques for processing data representative of surfaces having an arbitrary topology, and more particularly to processing techniques which utilize a mesh of interconnected data points to characterize a surface in three or more dimensions.
BACKGROUND OF THE INVENTION
Dense meshes of interconnected data points are used to represent surfaces of arbitrary topology in numerous applications. For example, such meshes routinely result from three-dimensional data acquisition techniques such as laser range scanning and magnetic resonance volumetric imaging. These meshes are often configured in the form of a large number of triangles, and typically have an irregular connectivity, i.e., the vertices of the mesh have different numbers of incident triangles. Because of their complex structure and potentially tremendous size, dense meshes of irregular connectivity are difficult to handle in such common processing tasks as storage, display, editing, and transmission.
It is known that multiresolution representations of dense meshes can be used to facilitate these processing tasks. One approach to constructing multiresolution representations extends classical multiresolution analysis and subdivision techniques to arbitrary topology surfaces, as described in, for example, M. Lounsbery et al., “Multiresolution analysis for surfaces of arbitrary topological type,” Transactions on Graphics 16:1, pp. 34-73, January 1997, and D. Zorin et al., “Interpolating subdivision for meshes with arbitrary topology,” in Computer Graphics (SIGGRAPH '96 Proceedings), pp. 189-192, 1996. Another more general approach is based on sequential mesh simplification, e.g., progressive meshes (PM), as described in, for example, H. Hoppe, “Progressive meshes,” in Computer Graphics (SIGGRAPH '96 Proceedings), pp. 99-108, 1996. Additional mesh simplification techniques are described in P. S. Heckbert and M. Garland, “Survey of polygonal surface simplification algorithms,” Tech. rep., Carnegie Mellon University, 1997.
In both classical multiresolution analysis and mesh simplification, the basic objective is generally to represent meshes in an efficient and flexible manner, and to use this representation in algorithms which address the processing challenges mentioned above. An important element in the design of such algorithms is the construction of “parameterizations,” i.e., functions mapping points on a coarse “base domain” mesh to points on a finer original mesh. Once a surface is characterized in this manner, as a function between a base domain and a space of three or more dimensions, many techniques from fields such as approximation theory, signal processing, and numerical analysis may be used to process data representing the surface.
A conventional approach to building parameterizations for meshes representing surfaces of arbitrary topology is based on approximation of a set of samples, as described in, for example, V. Krishnamurthy and M. Levoy, “Fitting smooth surfaces to dense polygon meshes,” in Computer Graphics, (SIGGRAPH '96 Proceedings), pp. 313-324, 1996. A significant drawback of this type of approach is that the number of triangles in the base domain depends heavily on the geometric complexity of the surface to be characterized. Another problem is that the user may be required to define the entire base domain rather than only selected features. Additionally, in conventional remeshing techniques that work from coarse to fine mesh levels, it is possible for the procedure to “latch” onto the wrong surface in regions of high curvature.
Another conventional approach to building parameterizations for surfaces of arbitrary topology is based on remeshing an existing mesh with the goal of applying classical multiresolution analysis. A technique implementing this approach is described in M. Eck et al., “Multiresolution analysis of arbitrary meshes,” in Computer Graphics (SIGGRAPH '95 Proceedings), pp. 173-182, 1995. A problem with algorithms of this type is that processing run times can be long because a large number of harmonic map computations are involved. Although this problem can be alleviated by reducing the harmonic map computations through hierarchical preconditioning, other problems remain. For example, there is generally no explicit control over the number of triangles in the base domain or the placement of boundaries. In addition, these and other remeshing algorithms typically generate only uniformly subdivided meshes which are subsequently made sparser through wavelet thresholding methods. Many extra subdivided levels may be needed to resolve one small local feature, and each additional level approximately quadruples the amount of computation and storage required to process the resulting mesh. This can lead to the intermediate construction of many more triangles than were contained in the original mesh, which unduly complicates the mesh processing operations.
SUMMARY OF THE INVENTION
The present invention provides techniques for generating parameterizations of irregular connectivity meshes representing surfaces of arbitrary topology. An illustrative embodiment uses multi-level mesh simplification in conjunction with conformal mapping to efficiently construct a parameterization of an original mesh comprising a large number of triangles over a base domain comprising a smaller number of triangles. The parameterization in the illustrative embodiment corresponds to the inverse of a function mapping each point in the original mesh to one of the triangles of the base domain, such that the original mesh can be reconstructed from the base domain and the parameterization. The mapping function is generated as a combination of a number of sub-functions, each of which relates data points in a mesh of one level in a simplification hierarchy to data points in a mesh of the next coarser level of the simplification hierarchy. An initial parameterization constructed in this manner can be further improved through a hierarchical smoothing procedure applied in the parameter domain so as to produce a smooth parameterization of high visual and numerical quality.
The procedure for generating the parameterization can be made fully automatic, but also allows for user intervention in the form of, for example, specifying point or path features in the original mesh such that a corresponding feature in the base domain maps exactly to the specified feature in the original mesh. Although a parameterization constructed in accordance with the invention is particularly well suited for use in remeshing applications, it is also useful in a wide variety of other applications, including, for example, multiresolution editing, texture mapping and morphing.
In accordance with another aspect of the invention, a remeshing process is provided which utilizes the above-described parameterization to convert an irregular connectivity mesh of arbitrary topology into a regular connectivity mesh meeting specified error bounds. The remeshing process may be made adaptive by computing error values for each of the triangles of the base domain, and subdividing any base domain triangles which have an error value above a specified threshold. The error computing and subdividing operations are then repeated until all of the triangles of the adaptive mesh represent the original mesh data points within the specified error bounds. Unlike conventional remeshing techniques, the remeshing of the present invention can directly construct an adaptively subdivided mesh, thereby avoiding the excessive computation and storage costs associated with the conventional approach of uniform subdivision followed by sparsification.
REFERENCES:
patent: 5602979 (1997-02-01), Loop
patent: 5966133 (1999-10-01), Hoppe
Canales et al., “An Adaptive Mesh Refinement Procedure for Shape Optimal Design”, 1994.*
H. Hoppe, “Progressive meshes,” in Computer Graphics (SIGGRAPH '96 Proceedings), pp. 99-108, 1996.
P. S. Heckbert and M. Garland, “Survey of polygonal surface simplification algorithms,” Tech. rep.,
Cowsar Lawrence C.
Dobkin David
Lee Aaron W. F.
Schroder Peter
Sweldens Wim
Ryan & Mason & Lewis, LLP
Sealey Lance W.
LandOfFree
Multiresolution adaptive parameterization of surfaces does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiresolution adaptive parameterization of surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiresolution adaptive parameterization of surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546464