Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-03-18
2001-05-15
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S426000
Reexamination Certificate
active
06232980
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer graphics, and more particularly to the generation of planar maps of three-dimensional surfaces.
2. Related Art
The problem of flattening a three dimensional (3-D) surface into a two-dimensional (2-D) domain is age old and takes several forms.
For example, one of the central concerns of cartography is the representation of a sphere as a planar map. As is well known, it is impossible to represent such a surface in 2-D without distortion and discontinuity. In a Mercator projection, for example, Greenland appears much larger than it really is in relation to more southern countries. Cartographers mitigate this problem either by cutting the surface of the globe into segments, thus trading off increased discontinuity for decreased distortion, or by using other projections which trade off size distortions for shape distortions.
Other application areas involve surface flattening, or the inverse problem, the construction of 3-D surfaces from originally flat components. An example of flattening involves taking the hide of an animal and creating flat pieces of leather or fur. An example of the inverse process is the construction of apparel such as shoes and garments out of pieces of leather, fur, or cloth. Going in either direction involves stretching/shrinking (distortion) and the alteration of discontinuity/continuity (e.g., by cutting or sewing).
The problem of correspondences between flat and curved surfaces arises in computer graphics software. A technique known as texture mapping is used to give 3-D surfaces character and realism. Whenever there exists a mapping from a 3-D surface to a 2-D region, an arbitrary image can be identified with the 2-D region so that rendered attributes of the surface (e.g., color, shininess, displacement) are controlled by the image's values. An image used in this way is called a texture map.
For 3-D surfaces such as bicubic patches, the mapping from surface to a 2-D region is intrinsic. However, for 3-D surfaces composed of polygons, an a priori mapping does not exist. The construction of such mappings, known as parameterization, has been a problem in computer graphics for several years because without a parameterization a polygonal surface is not amenable to texture mapping. Parameterization is equivalent to flattening.
Some conventional parameterization methods involve 1) selecting a boundary on a 3-D surface, 2) mapping the boundary to a planar convex polygon, and 3) using relaxation methods to calculate a mapping of interior points of the surface to interior points of the convex polygon. To visualize this process, imagine the 3-D surface to be a rubber sheet whose boundary is stretched around the perimeter of the polygon.
A drawback with these methods is that the planar convex polygon (e.g., a circle or square) does not necessarily reflect the shape of the surface boundary, thus increasing the possibility that the mapping will introduce shape distortions, particularly in polygons close to the boundary. A need therefore exists for an improved system and method for creating a planar boundary which inherits the geometry of a given surface boundary.
SUMMARY OF THE INVENTION
Briefly stated, the present invention is directed to a system and method for generating planar maps which reflect the distances and angles of a 3-D surface, where the user can manually adjust the balance between discontinuity and distortion.
A preferred embodiment of the present invention includes receiving a 3-D surface, defining a surface boundary on the 3-D surface, and generating a planar map based on the 3-D surface and the defined surface boundary. An edge-and-angle proportional mapping is preferably used to map the surface boundary to a map boundary. Those surface vertices not forming the surface boundary are then relaxed to create the map vertices not forming the map boundary.
A feature of the present invention is that a user selectively adjusts the balance between discontinuity and distortion in the planar map.
Another feature is that the present invention allows for the creation of planar maps such that each point on the 3-D surface corresponds to a unique point on the planar map. As a result, operations may be performed on the simpler 2-D planar map rather than the more complex 3-D map, and the result of the operations may be uniquely mapped to the 3-D surface.
Another feature of the present invention is that the majority of the vertices on a 3-D surface are mapped automatically, even though the user maintains a high degree of control over the mapping process via altering the 3-D surface boundary.
Another feature of the present invention is that user-selected map vertices may be pinned to a user-selected location, and held fixed while a conventional relaxation technique is applied. This provides the user with a greater degree of control over the relaxation process.
Another feature of the present invention is that a map boundary interpolation can be performed to generate alternate planar maps. These alternate planar maps may be superior in some respect to non-interpolated planar maps.
Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.
REFERENCES:
patent: 5107444 (1992-04-01), Wu
patent: 5319744 (1994-06-01), Kelly et al.
patent: 5448687 (1995-09-01), Hoogerhyde et al.
patent: 5903270 (1999-05-01), Gentry et al.
patent: 5949425 (1999-09-01), Willis
patent: 5986664 (1999-11-01), Dijkstra et al.
patent: 08287286 (1996-11-01), None
IBM TDB, Mar. 1, 1991, vol. 33, issue 10B, pp. 463-468.*
IBM TDB, May 1, 1973, vol. 15, issue 12, pp. 3726-3729.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
Vo Cliff N.
Zimmerman Mark
LandOfFree
System and method for generating planar maps 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 generating planar maps of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating planar maps of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444157