Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-01-05
2004-02-17
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06693631
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of geometric modeling and smoothing models using fairing operators.
BACKGROUND OF THE INVENTION
In recent years, models of graphics applications are becoming more complex. Recent trends in graphics visualization include an increasing complexity of datatests, increasing sophistication of computational models, real time performance and scalability, interactive exploration and analysis, and quantitative analysis and error control. Driven by the need to manage model complexity there has been a convergence of graphics and modeling technologies. The design of multi-resolution mesh representations of three-dimensional models is no exception. Two different types three-dimensional models are manifold and non-manifold models.
These models are based on the principles of Euclidean geometry and specifically, Euclidean space. A manifold, in general, is defined as a topological space in which every point has a neighborhood that is homeomorphic to the interior of a sphere in Euclidean space of the same number of dimensions. Being homeomorphic means that there exists a one-to-one mapping between sets (in this case, a neighborhood and the interior of a sphere) such that both the function and its inverse are continuous and that topology exists for geometric figures which can be transformed one into the other by an elastic deformation. A basic non-manifold model (
12
) is shown in
FIG. 2A and a
two-manifold model (
10
) is shown in
FIG. 2B. A
surface is two-manifold (
10
) if all of it points have an open neighborhood homeomorphic to
2
. This definition can be extended to two-manifold surfaces with boundaries, where every point has an open neighborhood homeomorphic to either
2
or
+
2
. If a surface does not satisfy these criteria, then it is called a non-manifold (
12
) as represented by a horizontal and a vertical surface together in FIG.
2
A. Examples of non-manifold surfaces (
12
) include, for instance, self-intersecting surfaces or T-junctions. Most of the following research is directed toward the handling of arbitrary, two-manifold models (
10
). Research has not been directed towards the handling of non-manifold models (
12
).
Two key ingredients in the design of multi-resolution mesh representations include 1) a fairing or subdivision method and 2) a mesh simplification algorithm.
A subdivision method starts with a triangle mesh. The mesh is refined by subdivision and the mesh is smoothed by moving vertices. This method is accomplished by generating infinite subdivisions. In signal processing terms, it is upsampling followed by relaxation. An example of a subdivision method is Loop subdivision for the estimation of high resolution mesh from the simplified representation. See, D. Zorin, P. Schröder, and W. Sweldens, “Interactive Multiresolution Mesh Editing”, 1995.
A fairing method is a process of removing high frequency components from geometry. Fairing is an extension of low pass filtering in signal processing to meshes. An example of a fairing method is devised by L. Kobbelt, who is the first to demonstrate the advantages of discrete fairing method as a fairing operator for mesh editing. He combines a very fast multilevel smoother with a progressive mesh simplification algorithm. See L. Kobbelt, “Interactive Multi-resolution Modeling on Arbitrary Meshes”, 1998.
Examples of mesh simplification algorithms are numerous. First is a progressive mesh that computes a sequence of progressively refineable meshes by successive application of an edge collapse operator. See H. Hoppe, “Progressive Meshes”, 1996. In combination with appropriate data structures and error metrics, this method provides a very powerful representation for triangle meshes. Another method uses a vertex removal strategy with a local remeshing method to successively simplify an initially dense mesh. See W. Schröder, J. Zarge, and W. Lorensen, “Decimation of Triangle Meshes”, 1992.
Mesh fairing is the most efficient way to enhance the smoothness of the mesh after simplification. Unlike geometrically motivated approaches to fairing that involve costly minimization of fairing functionals, G. Taubin uses a signal processing approach to mesh fairing. He is the first to map standard filtering techniques to meshes with arbitrary connectivity. This approach generalizes the notion of “frequency” to meshes of arbitrary connectivity by taking eigenfunctions of discretized Laplacian operator. Smoothing is accomplished by attenuation of the eigenvalues associated with the “high frequencies” of the mesh. This type of “low-pass” filtering band-limits the mesh and produces visually appealing models. Because the storage and computational cost is linear in the number of vertices, this approach is popular for mesh filtering. See, G. Taubin, “A Signal Processing Approach to Fair Surface Design”, 1995.
Building on the research of Taubin, the next development uses an implicit fairing method using a backward Euler integration. Rather than using discretized Laplacian operators as the flow operator, a discrete curvature flow operator is used. These enhancements allow the construction of a more robust algorithm to smooth meshes with arbitrary topology and reduce the need of human supervision during the smoothing process. The algorithm also obtains better results, both with respect to the quality of the smoothing and the shape of the triangles in the mesh. See, M. Desbrun, M. Meyer, P. Schröder, and A. H. Barr, “Implicit Fairing of Irregular Meshes using Diffusion and Curvature Flow”, 1999.
The next development is provided by Guskov and W. Sweldens. They combine non-uniform subdivision with a fairing algorithm to transform an arbitrary mesh into a multi-resolution representation. The details influence the mesh on an increasingly simplified scale with this multi-resolution representation, thereby resulting in an extension of the signal processing approach to triangle meshes. The most important difference between this new approach and the approaches of Taubin and Kobbelt is that the Laplacian operators not only approximate the topological information, but also consider the geometric information.
Different fairing operators may be used when fairing a mesh. A fairing operator is applied to intersected triangle meshes in a manifold or non-manifold model to achieve a smooth model. In rating the overall performance of the different operators, a trade-off between the speed and quality of the operators exists. The faster the operator performs the task, the quality of the operation declines. Also, as the quality of the operation performed by the operator increases, the speed declines since the complexity of the formula to accomplish the fairing requires much additional computational cost. There are four commonly accepted fairing operators. A comparison of the smoothing effect of each of the operators is shown in
FIGS. 1A-1E
. A non-smoothed sphere (
8
) is shown in
FIG. 1A
as a starting point for each of the listed operators.
FIG. 1B
shows the smoothing effect of an umbrella operator (
1
). The smoothing effect of the improved umbrella operator (
2
) is shown in FIG.
1
C. The smoothing effect of the curvature flow operator (
4
) is shown in FIG.
1
D. The smoothing effect of the second order divided differences operator (
6
) is shown in FIG.
1
E. The fairing operator with the fastest speed and lowest quality is the improved umbrella operator (
2
). The best quality results are generated by the curvature flow operator (
4
) and the second order differences operator (
6
), but they are also the slower and more complex operators.
SUMMARY OF THE INVENTION
In one aspect, the invention is a system and method of fairing a non-manifold model that starts by determining the features of the model. A fairing operator is then applied to the features to smooth the model and remove noise.
An embodiment of the invention includes manipulating triangle meshes that define the non-manifold model at different levels of resolution.
An embodiment of the invention includes a local volume preservation meth
Gross Markus H.
Hammersley Richard P.
Hubeli Andreas G. P.
ETH Zurich
Jankus Almis R.
LandOfFree
System and method for multi-resolution fairing of... 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 multi-resolution fairing of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for multi-resolution fairing of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3341091