Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-02-14
2004-12-14
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000, C345S423000
Reexamination Certificate
active
06831638
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. For example, U.S. Pat. No. 6,285,372, issued Sep. 4, 2001 in the name of inventors L. C. Cowsar et al. and entitled “Multiresolution Adaptive Parameterization of Surfaces,” which is incorporated by reference herein, discloses particularly efficient and advantageous techniques for generation of a multi-level parameterization which maps points in a coarse base domain mesh to points in an irregular connectivity dense mesh.
Digital geometry processing (DGP) is the field concerned with the construction of signal processing style algorithms for meshes. A basic element of DGP algorithms is the establishment of a smooth parameterization for a given mesh. Due to the non-Euclidean nature of the mesh, the construction of DGP algorithms is fundamentally more difficult than the construction of classical signal processing algorithms for one-dimensional, two-dimensional and three-dimensional signals. For example, sound (1D), images (2D) and video (3D) are readily parameterized onto a Euclidean space. More particularly, with regard to images, such signals are always sampled using a Cartesian grid, and are specified by an irradiance function over a section of the 2D plane. As a result, is it easy to perform operations such as averaging two images or computing the norm of their difference. Unfortunately, the same is not true for meshes, due to their non-Euclidean nature and generally differing sampling patterns and connectivity.
DGP algorithms involving different meshes generally require a common parameterization and a common sampling pattern for each of the meshes. Computing a global parameterization and a corresponding remesh for a dense mesh is a difficult problem in itself and has received considerable attention since it is a fundamental step in many algorithms from texture mapping and shape blending to physical simulation, compression, and data analysis.
Conventional parameterization algorithms often start with a triangle mesh having irregular connectivity, and generate therefrom a set of patches or a semi-regular mesh. Another known technique, described in the above-cited U.S. Pat. No. 6,285,372, employs mesh simplification with constraints to accommodate any user supplied data in the construction of the parameterization during an otherwise fully automatic process.
None of the above-noted approaches have adequately addressed the issue of building parameterizations for different meshes simultaneously. This problem arises naturally in the context of morphing when a mapping correspondence between two different meshes is the explicit goal. A technique described in A. Lee et al., “Multiresolution Mesh Morphing,” Proceedings of SIGGRAPH '99, pp. 343-350, 1999, which is incorporated by reference herein, independently establishes parameterizations for two different meshes and then solves the correspondence problem on the base domains. However, the two parameterizations are not consistent, that is, the base domains of the two parameterizations are different. Moreover, the technique is not readily extendible to n-way simultaneous parameterizations, i.e., generation of consistent parameterizations for any desired number n of meshes.
Another technique, described in S. Marschner et al., “Modeling and Rendering for Realistic Facial Animation,” Rendering Techniques 2000: 11th Eurographics Workshop on Rendering, pp. 231-242, 2000, which is incorporated by reference herein, involves animating a number of different faces via a single, prototype patch layout. Since their prototype face, i.e., the embedding of the prototype layout, is already very close to a given face, Marschner et al. report a simple least squares fitting procedure to work well. However, this simple least squares matching approach is generally not suitable for use in applications involving the simultaneous parameterization of meshes which are not geometrically similar.
It is therefore apparent that a need exists for techniques for generating consistent parameterizations for an arbitrary set of meshes.
SUMMARY OF THE INVENTION
The present invention provides techniques for generating consistent parameterizations for a set of meshes, e.g., irregular connectivity meshes representing surfaces of arbitrary topology.
By providing consistent parameterizations for a set of meshes, the invention greatly facilitates mesh processing operations in a wide variety of DGP applications, including, for example, principle mesh components analysis, transfer of textures or wavelet details between meshes, and shape blending.
In accordance with one aspect of the invention, consistent parameterizations are generated for a set of meshes each of which includes data points representative of a corresponding surface. The consistent parameterizations share the same base domain, and are generated using a net tracing algorithm. The net tracing algorithm involves determining for each of the meshes a net of paths having a connectivity substantially the same as that of the base domain.
In an illustrative embodiment of the invention, the net tracing algorithm as applied to a given one of the meshes includes determining, for each edge in the base domain, a tentative path for use in the net of paths corresponding to the mesh. The tentative paths are then prioritized based on length, and selected ones of the tentative paths are used to construct a spanning tree of the base domain. One or more swirl detection operations are preferably performed as part of the spanning tree construction, with the results of the swirl detection operations being utilized in selecting particular ones of the tentative paths for use in the spanning tree. The net of paths is completed by adding one or more additional paths to the spanning tree, followed by applying a straightening operation to one or more of the paths in the net.
In accordance with another aspect of the invention, the consistent parameterizations can be utilized to generate same-connectivity remeshes of the original meshes, thereby facilitating implementation of the above-noted DGP applications.
Advantageously, the techniques of the present invention overcome one or more of the previously-described problems associated with conventional approaches. For example, the invention may be utilized to provide n-way simultaneous parameterizations, and is suitable for use with meshes which are not geometrically similar.
REFERENCES:
Guenter et al., “Making Faces”, In Computer Graphics (SIGGRAPH 1998 Proceedings), pp. 55-67, Jul. 1998.
Praun Emil C.
Schroeder Peter
Sweldens Wim
LandOfFree
Method and apparatus for generation of consistent... 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 generation of consistent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generation of consistent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3296167