Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Utility Patent
1998-01-07
2001-01-02
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Utility Patent
active
06169549
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer graphics, and more particularly, to a constrained progressive mesh representation coupled with a supporting, run-time, dual-use topological adjacency data structures that enables real-time, scalable continuous level of detail (LOD).
2. Description of the Related Art
In computer graphics, objects are typically modeled offline by a modeling process, then transmitted from a server to a client to be rendered during run-time. During offline processing, conventional modeling systems produce tesselated polygonal approximations or meshes. These polygons may be even further converted to triangles by triangulation. During run-time, it is desirable to render the object by transforming the mesh into a visual display using several levels of detail (LOD). For example, when the object is close to the viewer, a detailed mesh is used. As the object recedes from the viewer, coarser approximations are substituted. Storing representations of modeled objects requires memory space, transmitting them from servers to clients requires bandwidth, and rendering them quickly and efficiently requires processor horsepower, all of which issues are directly or indirectly tied to the amount of data required at each step.
Statically-generated, coarse-grained, discrete LODs have been widely used in real-time graphics for many years because they are relatively simple to generate and then utilize at run-time. The use of discrete LODs, however, has undesirable effects on visual and frame-rate continuity. For example, when transitioning between different discrete LODs, the observer perceives an instantaneous switching or “popping.” Continuous LODs do not cause these problems because they allow fine-grained modifications in geometric representations of objects, and thus scenes, on a per-frame basis. This increased detail elision resolution allows the renderer to minimize variance in frame-rate and visual fidelity.
In a paper entitled “Progressive Meshes,” published in
Computer Graphics
(
SIGGRAPH '
96
Proceedings
), (1996), pp. 99-108, Hugues Hoppe describes a scheme for providing continuous LODs wherein a mesh simplification procedure is used to reduce a complex, highly detailed mesh M into a coarse approximation M
0
(base mesh), along with a sequence of n detail records that indicate how to incrementally refine the base mesh M
0
exactly back into the original mesh M=M
n
. Hoppe introduced a simplification transformation called the “edge collapse,” and its inverse refinement transformation called the “vertex split.” In addition to storing the base mesh M
0
and the n detail records, topological adjacency and attribute (e.g., normals) information is stored for performing these transformations. With this information, a LOD builder process can perform changes to the base mesh to obtain any desired incremental level of detail between the base mesh and the original mesh.
While Hoppe's continuous LODs offer a solution to the problem of mesh representation, a robust and scalable implementation of his scheme has its challenges. First, to construct LODs dynamically on a per-frame basis, topological adjacency information must be available to the LOD builder. This information comes at a significant memory cost that is incurred on a per-object basis. Either this cost must be reduced or the benefits reaped therefrom must be increased. As will be described in more detail below, the present invention achieves the latter by, inter alia, utilizing the adjacency information to optimize rendering speed.
Second, since an object's topological connectivity (i.e., its mesh) is changing dynamically, it is difficult to maintain a partitioning of the mesh that can be used to optimize rendering. There are two mesh partitionings that are widely supported by graphics APIs (e.g. OpenGL, Direct3D): triangle strip and triangle fan (or cycle) partitionings. High-quality strip and fan partitionings must be generated offline because they are too computationally expensive to be generated in real-time. Therefore, in real-time, as the mesh changes dynamically, high-quality partitionings are difficult to achieve.
One possible solution to this problem is to compute the partitioning for the base mesh offline and then apply incremental updates at run-time. However, this results in poor quality partitionings for higher resolution LODs, as the generation of high quality partitionings is a global, not local, optimization problem. A better solution, as offered by the present invention and described in more detail below, is to generate a multiresolution mesh that preserves the partitioning at all resolutions.
Mesh discontinuities present further challenges. A discontinuity is a crease, corner or other manifestation of non-smoothness on the surface of a mesh. More formally, a discontinuity exists at the boundary of two surface primitives when the inner product of the tangent vectors is not zero—i.e., the derivatives are not collinear. Discontinuity representation is an essential component of realistic rendering. Unfortunately, discontinuities have their cost both in space, time and programming complexity.
Currently, however, there is no data representation that allows for efficient processing, storing and rendering of discontinuities for continuous LODs. Rendering a mesh as a collection of independent triangles provides for maximum flexibility in rendering discontinuities but is inefficient in both time and space. Vertex pools, in current implementations in such graphics APIs as OpenGL, are only useful for rendering smooth objects because the normal indices cannot be specified separately from the coordinate indices. Accordingly, only per-vertex normals bindings can be used, whereas per-vertex, per-face binding is needed with independent triangles. Per-vertex, per-face (i.e. per-corner) bindings are possible, but vertices have to be duplicated, and this makes the implementation of continuous LODs very difficult.
Therefore, there remains a need for an implementation for providing continuous LODs that effectively manages the aforementioned space and time challenges while also allowing the rendering of mesh discontinuities. The present invention fulfills this need.
SUMMARY OF THE INVENTION
Accordingly, an object of the present invention is to provide continuous LODs without incurring unnecessary and wasteful storage requirements.
Another object of the present invention is to provide a method and apparatus for providing continuous LODs that effectively manages mesh partitionings to optimize rendering.
Another object of the present invention is to provide a method and apparatus for providing continuous LODs that allows rendering of mesh discontinuities.
The present invention describes the offline generation of, and run-time evaluation process for, continuous LODs that accomplishes these objectives, among others. In a preferred form, the invention modifies and constrains the offline multiresolution generation process such that a representation for continuous LODs is created that allows properly designed run-time topological data structures to be overloaded, thus supporting both LOD construction and optimized rendering. More specifically, the offline generation process initially preprocesses the mesh to generate a covering composed of only complete triangle cycles. The multiresolution generation process is then constrained to maintain this complete cycle covering for every interim mesh. For run-time evaluation, a topological adjacency representation is used that can serve the dual use described above. The multiresolution representation can be generated so as to allow discontinuities to be rendered at some cost to rendering performance.
Accordingly, the present invention enables the rendering of continuous LODs using a triangle-cycle or triangle-fan covering. This method differs from conventional techniques in at least two respects. The first is that the triangle cycles in this method are of higher quality than the triangle strips used in convention
iEngineer.com, Inc.
Nguyen Phu K.
Pillsbury Madison & Sutro LLP
LandOfFree
Method and apparatus for providing continuous level of detail 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 apparatus for providing continuous level of detail, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing continuous level of detail will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2554892