Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-10-10
2003-02-11
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S421000
Reexamination Certificate
active
06518964
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of geometric modeling. More specifically, the invention relates to computation, visualization and/or annotation of geometric models.
BACKGROUND OF THE INVENTION
In CAD/CAM and other areas, one needs to view and interact with 3D models obtained from a local machine or a remote server. These 3D models contain both geometry to define their shapes and surface features, such as color and annotations. Some annotations correspond to a two-dimensional figure mapped onto the surface of the geometric model. In order to improve performance, there is also a growing need to represent these complex three-dimensional models by simplified versions that are less expensive to store in memory on a computer, faster to transmit across a network from one computer to another computer, and faster to render on a computer. To address this, many techniques have been developed to simplify a model with minimal loss in perceived quality. See, for example, U.S. Pat. No. 5,929,860 or the article “Surface Simplification Using Quadric Error Metrics,” by M. Garland and P. Heckbert, in Computer Graphics Proceedings, Annual Conference Series, 1997, pages 209-216. Such techniques attempt to reduce the geometry of the model so that when the simplified model is rendered on a computer, the viewer will be able to perceive few, if any, differences as compared to a rendering of the original model. To accomplish this goal, many of the simplification techniques take the attributes of the model into account as well when simplifying the geometry. See, for example, U.S. Pat. No. 6,100,902; P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno, “A General Method for Preserving Attribute Values on Simplified Meshes”, Proceedings of IEEE Visualization, pages 59-66, 1998; M. Garland and P. Heckbert, “Simplifying Surfaces with Color and Texture Using Quadric Error Metrics,” Proceedings of IEEE Visualization, pages 264-269, 1998; and H. Hoppe, “New Quadric Metric for Simplifying Meshes with Appearance Attributes,” Proceedings of IEEE Visualization, pages 59-66, 1999. These techniques let the attributes guide the simplification process so that the geometry and the attributes of the simplified model appear the same as in the original model. To further preserve the overall appearance of the model, the annotations must be mapped onto the simplified model when simplification techniques are utilized, since the annotations can convey a significant amount of information.
A conventional way to perform the mapping from an image to the surface of an object is called, “texture mapping” and is commonly used to represent features with high detail on a surface containing few polygons. If the object to be mapped onto a nearby surface corresponds to a geometric mesh, comprised of vertices connected by lines, then the use of texture mapping to depict that mesh on the new surface would require rendering the mesh and then texture mapping it onto the surface. Although there are established techniques for texture mapping surface features onto an object, they do not separate the annotative texture from the contextual texture. Texture mapping, thoroughly described by P. Heckbert in “Survey of Texture Mapping”, IEEE Computer Graphics and Applications, volume 6, number 11, pages 56-67, November 1986, refers to a technique for mapping an image onto the surface of a model. Texture mapping has been commonly used to map annotations onto the surface of a model. To accomplish this, the annotations are first rendered as an image and stored in the memory of a computer. When the model is being viewed, the texture map of the annotations is applied to the surface of the model to convey the additional information provided by the annotations. Using such an approach, the annotations of a model can be mapped onto the original or simplified surface of the model, since they are stored in the form of an image.
D. Eu and G. T. Toussaint, in “On approximating polygonal curves in two and three dimensions.” CVGIP: Graph. Models Image Process., 56(3):231-246, May 1994, describe techniques for simplifying paths in space using a “parallel strip” concept that results in a simplified version of the original path in three-dimensions that does not depart from the original path by more than the allowed tolerance. G. Barequet, D. Chen, O. Daescu, M. Goodrich, and J. Snoeyink in “Efficiently approximating polygonal paths in three and higher dimensions,” Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 317-326, 1998, describe a refined algorithm for simplifying paths in three-dimensions more efficiently.
PROBLEMS WITH THE PRIOR ART
Texture mapping requires specialized graphics hardware for adequate performance during viewing, and that hardware is not currently guaranteed to be present on all computers. In addition, texture mapping requires rendering one or more views of the annotations from different viewpoints, and projecting the rendered images onto the surface via texture coordinates. When multiple images are used to represent the annotations of the model at the same time, differences in rendering parameters between images may result in a discontinuity where the images border each other and this discontinuity can stand out as a disturbing artifact. Annotations that do not appear seamless may be hard to interpret because the eye is drawn to the abrupt changes in surface characteristics rather than the actual features on the surface. Consequently, the annotations may become an ineffective means for conveying the additional information to the viewer.
Texture maps also suffer from blurring and pixelization at high magnification. Since the annotations are stored as an image, they are recorded at a fixed resolution. Typically the resolution of the image is measured in terms of the number of pixels in width and height. If the viewer zooms into the model to see the surface details more closely, the annotations texture map will appear blurry and unnatural. When surface annotations become blurred at high magnifications, they lose their impact as informative surface markup, and instead appear as an unnatural image pasted onto the surface. When the annotations are integral with the texture map, they lose their visual impact as surface markup and merge with the background features in a way that detracts from, rather than enhances, their visual importance. The end result is that the information conveyed by the annotations will be lost by the viewer.
Texture maps are most efficient for simple geometric models. For complex models, many additional images, from different viewpoints, will be required. This will greatly exacerbate the discontinuity problem mentioned previously.
Existing techniques for simplifying paths in two- and three-dimensions do not account for paths that are attached to surfaces, nor do they allow different sensitivities to error tangent and perpendicular to the surface. This leads to annotations that are either under-simplified, or prone to penetrate or float above the surface in an artificial manner.
OBJECTS OF THE INVENTION
An object of this invention is an improved system and method to simplify annotations on a surface.
An object of this invention is an improved system and method to simplify the number of line segments used as annotations on a surface.
An object of this invention is an improved system and method to simplify the number of line segments used as annotations on a surface using a directed asymmetric tolerance window that allows a different degree of simplification in the plane tangent to the surface, compared to the tolerance perpendicular to the surface.
SUMMARY OF THE INVENTION
The present invention is a computer system and method for simplifying annotations on a surface. A tolerance process creates a tolerance window lying in a plane and centered on the query point at the end of a test edge and perpendicular to the test edge. The tolerance window is defined by a first tolerance that specifies an amount of first error measured by the distance from a simplified path to an original path in the plane tangent
Horn William P.
Klosowski James T.
Lecina Gerard
Suits Frank
Herzberg Louis P.
Vo Cliff N.
LandOfFree
Apparatus, system, and method for simplifying annotations on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus, system, and method for simplifying annotations on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus, system, and method for simplifying annotations on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3131944