Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
2001-04-12
2003-10-28
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
Reexamination Certificate
active
06639599
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of computer graphics, and more particularly to generating rendering elements while dynamically varying viewing parameters and frame rate requirements.
BACKGROUND OF THE INVENTION
In real-time graphics applications, such as games and physical simulations, numerous techniques are known to automatically generate models in the form of polygon meshes. Common generation techniques include laser range scanning and triangulation of implicit functions. Often, the resultant meshes include more polygons that can be rendered by standard rendering engines at real-time frame rates.
Therefore, in order to reduce the number of polygons in the models, multiresolution triangle meshes are frequently used. These methods typically use two approaches for generating level-of-detail (LOD) meshes. In the static approach, a set of static LOD meshes are pre-computed before use in an application. At run-time, a member of the set is selected, based on viewing parameters and frame rate requirements, and displayed. In the dynamic approach, a single dynamic mesh is generated before use in the application, and then the mesh is adapted by a series of transformations according to the viewing parameters and the frame rate requirements, see Garland “
Multiresolution Modeling: Survey and Future Opportunities,”
Eurographics '99 State of the Art Reports, pp. 111-131, 1999.
Known dynamic meshing methods, such as view dependent progressive meshes (VDPM), and hierarchical dynamic simplification (HDS), generate hierarchical data structures that can be refined and decimated to reduce the number of polygons in the meshes. The hierarchy in the VDPM is formed by generating a new parent vertex for every pair of vertices combined by an edge collapse operation, see Hoppe “
View
-
Dependent Refinement of Progressive Meshes,”
Proceedings of SIGGRAPH 1997, pp. 189-198, 1997. The HDS hierarchy is formed by spatially subdividing a scene into cells, and grouping vertices in each cell into a single representative vertex, see Luebke et al. “
View
-
Dependent Simplification of Arbitrary Polygonal Environments,”
Proceedings of SIGGRAPH 1997, pp. 199-208, 1997. In both methods, a screen space error and normal cones are used to determine when to refine and decimate the mesh.
However, these techniques can still produce more polygons than needed. Furthermore, their processing time is dependent on the number of polygons in the original model, which can be prohibitively slow for large models. Finally, these methods can produce poor quality models when the polygon count is small.
Therefore, there is a need to provide a method and system for automatically generating real-time dynamic meshes that match viewing parameters and desired frame rates.
The use of normal cones for determining visibility is known in the art, see Hoppe and Luebke et al. as described above. In both systems, normal cones are constructed from the initial geometry of the model and placed in a data structure such as an octree. There, the range, or spread, of normals in an octree cell is a function of where the geometry lies with respect to the octree grid. For example, a leaf cell of the octree can have a large spread of normals simply because the geometry within that cell has a large degree of curvature. This type of normal cone construction can cause a rendering engine to draw many more polygons than necessary because polygons that should be classified as invisible, e.g., back-facing, are instead classified as visible since the polygons are grouped in a leaf cell with a large spread of normals indicating, erroneously, that they are visible.
Therefore, there is a need to provide a method for automatically generating detail directed visibility elements, e.g., detailed directed normal cones, that will more accurately classify geometry such as polygons according to visibility, thus avoiding unnecessary processing such as the rendering of polygons as described above.
SUMMARY OF THE INVENTION
It is an object of the present invention to enable the real-time generation of viewpoint-dependent dynamic rendering elements, such as triangles and points, from adaptively sampled distance fields.
It is another object of the present invention to produce rendering elements that are of high visual quality, and a low quantity of rendering elements in invisible areas.
The present invention provides a method for dynamically generating rendering elements for a graphics model. The model is first converted to an adaptively sampled distance field including surface cells representing a surface of the model. A visibility element is determined for each surface cell. A set of active cells is determined, where each active cell is associated with one of the surface cells of the adaptively sample distance field, and each active cell has a corresponding visibility element. Rendering elements are determined for each active cell.
Active cells are added and deleted dynamically from the set of active cells according to a weight determined for each active cell by a weighting function. The weight of each active cell can depend on viewing and shading parameters. Rendering elements are dynamically generated when active cells are added to the set of active cells and dynamically deleted when active cells are deleted from the set of active cells.
REFERENCES:
patent: 6300956 (2001-10-01), Apodaca et al.
patent: 6300960 (2001-10-01), DeRose et al.
patent: 6396492 (2002-05-01), Frisken et al.
patent: 6483518 (2002-11-01), Perry et al.
Frisken et al., “Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics”, Proceedings for SIGGRAPH 2000, pp. 249-254, 2000.
Michael Garland, “Multiresolution Modeling: Survey & Future Opportunities”; Eurographics '99, State of the Art Reports, pp. 111-131, 1999.
Hugues Hoppe, “View-Dependent Refinement of Progressive Meshes”; Proceedings of SIGGRAPH 1997, pp. 189-198, 1997.
Luebke et al., “View-Dependent Simplification of Arbitrary Polygonal Environments”; Proceedings of SIGGRAPH 1997, pp. 199-208, 1997.
Frisken Sarah F.
Perry Ronald N.
Pope Jackson W. J.
Brinkman Dirk
Mitsubishi Electric Research Laboratories Inc.
Santiago Enrique L
Zimmerman Mark
LandOfFree
Method and system for dynamically generating view dependent... 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 and system for dynamically generating view dependent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for dynamically generating view dependent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3125957