Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
1998-07-14
2002-07-30
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
C345S423000, C345S473000, C345S475000
Reexamination Certificate
active
06426750
ABSTRACT:
COPYRIGHT AUTHORIZATION
A portion of this disclosure may contain copyrighted material. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights.
FIELD OF THE INVENTION
The present invention relates generally to geometric modeling using polygonal meshes for computer graphics, and more particularly relates to techniques for optimizing computer resource (e.g., memory, CPU, etc.) requirements for the manipulation of large-scale meshes.
BACKGROUND AND SUMMARY OF THE INVENTION
Rendering real-time views on a complex model is a computation-intensive task. Current methods generally rely on encoding real-world objects in a complex three-dimensional geometric model which approximates the surfaces, textures and locations of the real-world objects. Objects are usually represented as a collection of polygons (but can be a mathematical description, fractal or the like) which are collected together to form a mesh having the shape and visual and/or tactile characteristics of the encoded real-world object. Realistic models of any reasonable size, e.g., simulating large-scale terrain meshes (see FIG.
2
), can contain hundreds of meshes with millions of polygons to represent a realistic view of reality. Consequently, enormous computer resources are required to manipulate large meshes.
To simplify processing when rendering views of such detailed scenes, view-dependent progressive-meshes (VDPM) were developed. Hoppe shows a VDPM framework that represents an arbitrary delta-mesh (base mesh plus deltas required to produce a more detailed mesh)as a hierarchy of geometrically optimized transformations. A series of geomorph operations can be performed to convert between differing levels of detail of the progressive mesh. (For further information, see Hoppe,
Progressive Meshes,
Computer Graphics Proceedings, Annual Conference Series (ACM SIGGRAPH), pp. 99-108 (1996); Hoppe,
View
-
Dependent Refinement of Progressive Meshes,
ACM SIGGRAPH, pp. 189-198 (1997).)
In accordance with Hoppe's VDPM framework, a front across a progressive mesh hierarchy is defined. The Hoppe VDPM framework uses a progressive mesh representation of the original mesh model, which represents the mesh model as a simplified base mesh and a sequence of mesh refinement transformations (i.e., vertex splits) that, when applied to the base mesh, exactly reconstruct the original fully-detailed mesh. The front is developed by incrementally applying mesh refinement and coarsening operations subject to certain legality considerations. The legality conditions disallow some refinement operations unless other refinements operations are performed, and disallow some coarsening operations unless other coarsening operations are performed first
In addition, for a given mesh, a viewpoint is defined with respect to the mesh. The viewpoint can correspond to what a user/viewer might see of a mesh, or it can be the portions of the mesh visible in a viewport. The phrase “selectively refined mesh” (SRM) corresponds to a mesh that is altered based on satisfying certain viewing criteria, such as changes in the viewport. The result is view-dependent level of detail (LOD) applied to different portions of a mesh. For example, viewing conditions may depend on the location of a flight simulator pilot in a mesh model, so that mesh detail centers on those portions of the mesh near the pilot's plane. For a view-dependent LOD, the active front is traversed for each frame being rendered, and every vertex of the front is either coarsened or refined based on the view-dependent refinement criteria. Examples of view-dependent criteria affecting the occurrence of a vsplit (vertex split) operation is whether a vertex's neighborhood intersects the view frustum (see FIG.
7
), has a Gauss map not strictly oriented away, or has a screen-projected deviation from M that exceeds a pre-determined (user-specified) pixel tolerance. (M represents an original fully-detailed mesh that has been deconstructed into a base mesh, to which delta operations are applied to obtain successively detailed meshes.)
It is understood by those skilled in the art that view dependencies concern the relationship between a viewpoint (e.g., camera location, user's eye, etc.), a defined viewing frustum (see FIG.
7
), and a “current mesh” defined by a base mesh M
0
+a set of refinement operations. When adjusting a SRM's coarseness, the change is either effected instantly, or geomorphed (interpolated) over time. Which method is used depends on whether an affected mesh region is entering, leaving, or staying within a particular viewing frustum. Only portions of a mesh remaining in view (i.e., within the frustum) need to be geomorphed to avoid “popping” the mesh alteration into place. In fact, geomorphs should be avoided for vertices entering and leaving the frustum, as discussed later.
Preferably, vertices entering and leaving the frustum are instantly adjusted, and vertices remaining in view are geomorphed over time. In addition, polygon orientation and distance from the frustum can be used to determine whether a local region of the mesh should be further refined or coarsened. For example, those polygons identified as facing away from a viewing position, or having too little impact on the display device, can be ignored without affecting output. The impact of a triangle's rendering to an output device (e.g., display monitor or video output) is dependent on the resolution of the device; if rendering only changes one or two pixels on the output device, rendering the triangle may cost more in computer time and resources than the visual benefit obtained from the rendering.
In addition, another significant problem with prior art mesh-based rendering systems is that notwithstanding using simplified meshes, these systems consume computer resources proportional to the size of the fully-detailed mesh M
n
. That is, in the prior art, if M
n
has p faces, but has been simplified into a simpler mesh M
0
having only q faces, where q<<p (much less than), memory and other computer resources are allocated on a scale proportional with the connectivity of the larger mesh M
n
. For example, to compute a geomorph between two selectively refined meshes procured from the progressive mesh hierarchy, prior art methods may require geomorph computations involving all active vertices, rather than on just those vertices needed for a view-dependent computation. And, once begun, the geomorph had to complete (or be reverted) before a new geomorph operation can be initiated. Consequently, computer resources (e.g. CPU speed, time, and storage space) to store and process the fully-detailed mesh are required even though the view is rendered based on only a small subset of its vertices.
For further information regarding techniques for constructing and using progressive meshes, view-dependent progressive meshes, and geomorphs, see: U.S. Patent AA for Encoding And Progressive Transmitting Of Progressive Meshes, bearing application Ser. No. 08/586,953 and filed Jan. 11, 1996; U.S. Patent BB for Selective Refinement Of Progressive Meshes, bearing application Ser. No. 08/797,501 and filed Feb. 7, 1997; U.S. Patent CC for View-Dependent Refinement Of Progressive Meshes, bearing application Ser. No. 08/826,570 and filed Apr. 3, 1997; U.S. Patent DD for Adaptive Refinement Of Progressive Meshes, bearing application Ser. No. 08/826,573 and filed Apr. 3, 1997; and U.S. Patent EE for a Method For Creating Progressive Simplicial Complexes, bearing application Ser. No. 08/880,090 and filed Jun. 20, 1997. These patents are incorporated herein by reference.
To overcome these limitations of prior art systems, the invention optimizes storage requirements by utilizing dynamic data structures for storing and manipulating a mesh that allocate storage based on the active vertices of the mesh (determined according to view-dependent criteri
Klarquist & Sparkman, LLP
Microsoft Corporation
Stevenson Philip H.
Zimmerman Mark
LandOfFree
Run-time geomorphs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Run-time geomorphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Run-time geomorphs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2911358