Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1998-07-17
2001-10-09
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06300958
ABSTRACT:
TECHNICAL FIELD
The present invention pertains to the field of three dimensional model generation, and more particularly to a method for reducing distortion of a feature when the feature is mapped onto a contoured surface.
BACKGROUND OF THE INVENTION
Texture mapping is widely used to improve the visual richness of 3D surfaces in computer generated images. Each 3D surface is put in correspondence with a planar image through a function called a mapping. Such a mapping assigns a pair of coordinates (u,v) referring to a pixel of the planar image to each point of a surface. Thus, for instance, the latitude and longitude can define a trivial mapping of a sphere. This technique was described by E. Catmull in A Subdivision Algorithm for Computer Display of Curved Surfaces, PhD thesis, Dept. of Computer Sciences, University of Utah, December 1974, which is hereby incorporated by reference. This technique was first applied to bicubic patches using a recursive subdivision algorithm. Unfortunately, these methods often produce highly distorted textures in the resulting images, similar to
FIG. 10
(which is not prior art, but is only referred to for illustrative purposes).
First attempts to minimize these distortions were described by R. Darwyn Peachey in Solid Texturing of Complex Surfaces,
SIGGRAPH
85
Conference Proceedings
, volume 19, pages 287-296, ACM, July 1985, and E. Bier and K. Sloan in Two-Part Texture Mapping,
IEEE Computer Graphics and Applications
, pages 40-53, September 1986, both of which are incorporated herein by reference. These attempts involved separating the process into two steps. The texture pattern is first applied to a simple intermediate surface such as a box or a cylinder for which texture mapping is trivial. Then, this intermediate surface is projected on the target object. The choice of the intermediate surface and its orientation, together with the projection method selected, dramatically affect the results, and great deal of user interaction was therefore required.
Marcel Samek, C. Slean, and H. Weghorst in Texture Mapping and Distortions in Digital Graphics,
The Visual Computer
, 2(5):313-320, September 1986, which is hereby incorporated by reference, taught that assigning texture coordinates to any surface is equivalent to flattening it. That method consists of unfolding a polygonal surface from a user selected seed. A similar technique was dislosed by C. Bennis, J. M. V'ezien, and G.Igl'esias in Piecewise Surface Flattening for Non-Distorted Texture Mapping,
SIGGRAPH
91
Conference Proceedings
, volume 25, pages 237-246, ACM, July 1991, which is hereby incorporated by reference. This latter method means a parametric surface may be unfolded by allowing cuts to appear on the mapped texture when the discrepancy of the geodesic curvature goes beyond a given threshold.
Minimizing the distortions induced by texture mapping can be also realized using optimization techniques. In the method described by S. D. Ma and H. Lin in Optimal Texture Mapping,
EUROGRAPHICS'
88, pages 421-428, September 1988, which is incorporated herein by reference, a mapping of any surface is constructed by starting from a grid of points sampled on the surface. The grid is then iteratively optimized by minimizing a global distortion criterion. V. Krishnamurthy and M. Levoy in Fitting Smooth Surfaces to Dense Polygon Meshes,
SIGGRAPH
96
Conference Proceedings
, pages 313-324, ACM, August 1996, and incorporated herein by reference, disclosed a similar approach for converting a triangulated mesh into a set of B-Spline surfaces. It is also possible to construct a mapping by assigning (u,v) coordinates to the vertices of the mesh. This naturally leads to the use of harmonic maps, as described by M. Eck, T. DeRose, T. Duchamp, H. Hoppes, M. Lounsbery and W. Stuetzle in Multiresolution Analysis of Arbitrary Meshes,
SIGGRAPH
95
Conference Proceedings
, pages 173-182, ACM, August 1995, which is hereby incorporated herein by reference. This method consists of minimizing a metric dispersion criterion. Unfortunately, this does not always preserve angles accurately. Another approach disclosed by M. S. Floater in Parametrization and Smooth Approximation of Surface Triangulations,
Computer Aided Geometric Design
, 14(3):231-250, April 1997, and incorporated herein by reference, generalizes the barycentric mapping method described by W. T. Tutte in Convex Representation of Graphs,
Proc. London Math. Soc
., volume 10, 1960, also incorporated herein by reference. The (u,v) texture coordinates are found to be the solution of a linear system, where each (u,v) point is a convex combination of its neighbors. M. S. Floater (referenced above) taught a method for choosing the coefficients of these convex combinations to mimic the chord length parametrization for curves. These global methods give good results for most simple surfaces, but suffer from several limitations when applied to more complex surfaces. Further, since the criterion to be minimized is integral to the optimization algorithm, it is often difficult to take into account user defined information. For instance, as most surfaces are not developable, distortions will still remain, and the user may want to specify the distribution of these distortions.
Additionally, it is desirable to have a mapping function that handles “cuts” in the surface, such as for example are found when mapping a geological surface, which may represent a faulted stratigraphic grid. One technique for handling this is described by J. Bloomenthal in Modeling the Mighty Maple,
SIGGRAPH
85
Conference Proceedings
, volume 19, pages 305-311, ACM, July 1985. Bloomenthal uses several distinct “patches” on the surface and makes the edges of the patches match to provide continuity of a texture over the discontinuity (“cut”). This is a computationally intense method, and it is desirable to provide a simpler method for dealing with discontinuities along a line in the surface.
Prior interactive mapping methods, where the parametrization is partially or completely defined by the user, are described by H. K. Pedersen in Decorating Implicit Surfaces,
SIGGRAPH
95
Conference Proceedings
, pages 291-300, ACM, 1995, P. Litwinowicz and G. Miller in Efficient Techniques for Interactive Texture Placement,
SIGGRAPH
94
Conference Proceedings
, pages 119-122, ACM, July 1994, and J. Maillot, H. Yahia, and A. Verroust in Interactive Texture Mapping,
SIGGRAPH
93
Conference Proceedings
, volume 27, ACM, 1993, all of which are hereby incorporated herein by reference.
Therefore, what is needed in the art is a method for texture mapping onto a surface which reduces distortion of the texture, and which preferably allows for user input to distribute any remaining distortion to preferred regions. Additionally, it is desirable to have a texture mapping method which is capable of handling discontinuities in the surface.
SUMMARY OF THE INVENTION
The invention discloses a novel global optimization method, and more particularly, a texture mapping method which reduces distortion encountered by prior texture mapping methods. Contrary to the prior art, the method disclosed herein is based on a modular approach enabling the way the mapping is constructed to be customized. For instance, it is possible to tune the perpendicularity and homogeneous spacing of isoparametric curves over the entire surface, thus specifying the surface zones where distortions should be minimized in order of preference. The disclosed method also allows the user to make the mapping respect a set of user specified isoparametric curves. Moreover, the mapping can be made continuous through cuts, hence allowing the mapping of a texture on a complex cut surface in a single step. The method can be extended relatively easily to honor other kinds of linear constraints. All these constraints allow the method to take into account user specified information while being much more automatic than prior interactive mapping methods, where the parametrization is partially or completely defined by the user.
The disclosed m
Nguyen Phu K.
Reid John S.
Reidlaw, L.L.C.
T-Surf Corp.
LandOfFree
Global constrained parameterization of triangulated 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 Global constrained parameterization of triangulated surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Global constrained parameterization of triangulated surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598173