Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-08-30
2004-08-03
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06771261
ABSTRACT:
BACKGROUND
1. Field
The present invention relates generally to computer graphics and, more specifically, to mesh simplification of multi-resolution models.
2. Description
In computer graphics, a model is a structured digital representation of an object or scene. Many computer graphics applications employ complex, detailed models of scenes or objects to maintain a convincing level of realism for a user. Consequently, models are often created or acquired at a resolution to accommodate this desire for detail. However, depending on the application, this complexity of such models may be excessive, and since the computational cost of using a model is typically related to its complexity, it is often useful to have simpler versions of complex models. Hence, methods of automatically and efficiently producing simplified models are desirable.
A goal of multi-resolution modeling is to extract the details from complex models that are desirable for rendering a scene and to remove other, excessive details. A multi-resolution model is a model which captures a wide range of levels of detail of an object and which can be used to reconstruct any one of those levels. Such models are typically represented as a mesh of many triangles, each triangle having three vertices and three edges. A mesh may be represented by a data structure stored in a data storage device. One area of research in multi-resolution modeling has been the development of iterative edge contraction techniques. An edge contraction (also known as an edge collapse) takes the two endpoints (vertices) of a target edge within a mesh, moves them to a single position, links all incident edges to one of the vertices of the mesh at the position, deletes the other vertex, and removes any faces that have degenerated into lines or points. Typically, this removes two triangular faces per edge contraction, thereby simplifying the model. Edge contraction processes work by iteratively contracting edges of the mesh until a desired resolution is achieved. Differences in such processes lie primarily in how a particular edge to be contracted is chosen.
Surface simplification is a restricted form of edge contraction in multi-resolution modeling. In polygonal surface simplification, a goal is to take a polygonal model as input data and generate a simplified model (e.g., an approximation of the original) as output data. The focus of such simplification is on polygonal models represented as meshes comprising only triangles (e.g., wire frame models). This implies no loss of generality, because every polygon in an original model can be triangulated as part of a pre-processing phase.
Simplification is useful in order to make storage, transmission, computation, and display of models more efficient. A compact approximation of a model can reduce disk and memory utilization and can speed network transmission. It can also accelerate a number of computations involving shape information, such as finite element analysis, collision detection, visibility testing, shape recognition, and display. In sum, reducing the number of polygons in a model can make the difference between slow display and real time display.
REFERENCES:
patent: 6630932 (2003-10-01), Grzeszczuk
Garland et al., “Simplifying Surfaces with Color and Texture Using Quadric Error Metrics,” SIGGRAPH 1997 Proceedings, Aug. 1997, pp. 209-216.*
Hugues Hoppe, “View-Dependent Refinement of Progressive Meshes”, Proceedings of SIGGRAPH, ACM SIGGRAPH Aug. 1997, Computer Graphics Proceedings, Annual Conference Series, pp. 189-197, ACM Press.
Peter Lindstrom, Greg Turk, “Fast and Memory Efficient Polygonal Simplification”, IEEE, Visualization 1998 Proceedings, 1998, pp. 279-286.
Paul S. Heckbert, Michael Garland, “Survey of Polygonal Surface Simplification Algorithms”, SIGGRAPH 1997, 1997, pp. 1-29.
Michael Garland, Paul S. Heckbert, “Surface Simplification Using Quadric Error Metrics”, SIGGRAPH 1997 Proceedings, Aug. 1997, pp. 209-216.
Michael Garland, Paul S. Heckbert, “Simplifying Surfaces with Color and Texture using Quadric Error Metrics”, Visualization 1998 Proceedings, pp. 263-269.
Intel Corporation
Sealey Lance W.
Skabrat Steven P.
Zimmerman Mark
LandOfFree
Error metric for mesh simplification processing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Error metric for mesh simplification processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error metric for mesh simplification processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3359860