Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-09-23
2001-03-06
Powell, Mark R. (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S428000, C345S440000
Reexamination Certificate
active
06198486
ABSTRACT:
BACKGROUND
1. Field
The present invention relates generally to graphics for display systems and, more specifically, to multi-resolution modeling of scenes or objects in display systems.
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 the single position, links all incident edges to one of the vertices of the mesh, 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. Reducing the number of polygons in a model can make the difference between slow display and real time display.
A surface simplification process is described by Michael Garland and Paul S. Heckbert in “Surface Simplification Using Quadric Error Metrics”, SIGGRAPH 97 Proceedings, pages 209-216, August, 1997, although the invention is not limited in scope in this respect. Garland and Heckbert describe a process for producing simplified versions of polygonal models that is based on the iterative contraction of vertex pairs (which is a generalization of edge contraction). In this process, a geometric error approximation is maintained at each vertex of the current model. The error approximation is used as the determining factor in identifying the order for iterative edge contractions. According to Garland and Heckbert, the error approximation is represented using quadric matrices. The quadrics stored with the final vertices can also be used to characterize the overall shape of the model's surfaces. In this process, ten floating point numbers are used for storing the error approximation at each vertex.
This process was extended by Michael Garland and Paul S. Heckbert in “Simplifying Surfaces With Color And Texture Using Quadric Error Matrics”, Proceedings Visualization 1998, to models having material properties such as colors, textures, and surface normals, although, again, the invention is not limited in scope in this respect. The quadric error metric was modified to account for a range of vertex attributes. However, the generalized error metric incurred additional space and processing overhead when implemented on a computer system because the size of the quadric matrix grows quadratically in the size of the attributes. For example, the number of unique coefficients according to this method for each vertex of the model becomes 21 with a model having a geometry and two-dimensional texture, 28 with a model having a geometry and color, and 28 with a model having a geometry and surface normals.
In addition, the methods disclosed by Garland and Heckbert often make mistakes in simplifying a model, particularly when dealing with objects having long, skinny features such as claws and tails, for example. Their methods tend to remove or shorten these features of the model prematurely.
Therefore, an improved iterative edge contraction process for simplifying multi-resolution models is desired which reduces storage and processing utilization and produces more accurate simplifications.
SUMMARY
An embodiment of the present invention is a method of generating a first mesh from a second mesh representing a scene or object. This embodiment includes collapsing edges of the second mesh in a first order defined by a surface area error metric to produce a third mesh, and collapsing edges of the third mesh in a second order defined by a combination quadric and surface area error metric to produce the first mesh.
REFERENCES:
patent: 5929860 (1999-07-01), Hoppe
patent: 5963209 (1999-10-01), Hoppe
patent: 5966133 (2000-04-01), Hoppe
patent: 6046744 (2000-04-01), Hoppe
patent: 6108006 (2000-08-01), Hoppe
Garland, Michael, et al., “Simplifying Surfaces with Color and Texture using Quadric Error Metrics,” Proceedings Visualization 1998, 8 pages.
Garland, Michael, et al., “Surface Simplification Using Quadric Error Metrics” SIGGRAPH 97 Proceedings, Aug. 1997, pp. 209-216.
Junkins Stephen
MacPherson Mike B.
Harrison Chante E.
Intel Corporation
Powell Mark R.
Skabrat Steven P.
LandOfFree
Method of using a hybrid error metric for multi-resolution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of using a hybrid error metric for multi-resolution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of using a hybrid error metric for multi-resolution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521481