(12) United States Patent
`Burr
`
`US006169549B1
`US 6,169,549 B1
`Jan. 2, 2001
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR
`PROVIDING CONTINUOUS LEVEL OF
`DETAIL
`
`(75) Inventor: Timothy J. Burr, San Jose, CA (US)
`
`(73) Assignee: iEngineer.c0m, Inc., Sunnyvale, CA
`(Us)
`
`( * ) Notice:
`
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(21) Appl. No.: 09/003,863
`(22) Filed:
`Jan. 7, 1998
`
`(51) Int. Cl.7 .................................................... .. G06F 15/00
`(52) US. Cl. ............................................................ .. 345/419
`(58) Field of Search ................................... .. 345/440, 441,
`345/433, 428, 118, 121, 419, 421, 427
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`8/1997 Durward et a1. ................... .. 395/329
`5,659,691
`10/1997 Freedman et a1. .
`395/129
`5,675,721
`5,917,494 * 4/2000 Arai et a1. .... ..
`345/419
`6,049,625 * 4/2000 Sakamoto ........................... .. 345/419
`
`OTHER PUBLICATIONS
`
`Li, J. et al; “Progressive compression of 3D graphic mod
`els,” Proc. IEEE Intl Conference on Multimedia Computing
`and Systems, Apr. 1997.
`Deering, M; “Geometry Compression,” Computer Graphics
`Proc., Los Angeles CA, Aug. 1995, pp. 13—20.
`Evans, F. et al.; “Optimizing Triangle Strips for fast Ren
`dering,” Proc. of the Visualization Conference, San Fran
`cisco, CA, Oct. 1996, pp. 319—326.
`Popovic, J. et al.; “Progressive Simplicial Complexes,”
`Computer Graphics Proc., Siggraph 97, Los Angeles, CA,
`Aug. 1997, pp. 217—224.
`
`Taubin, G., et al.; “Geometric Compression through Topo
`logical Surgery,” Research Report RC—20340 (#89924), Jan.
`16, 1996, pp. 1—32; http://www.researchibm.com/vrml/bi
`nary/pdfs/ibm20340r1.pdf.
`ArikaWa, M. et al., “Dynamic LoD for QoS Management in
`the Next Generation VRML,” Proceedings of the Intl. Conf.
`on Multimedia Computing and Systems, Jun. 17, 1996.
`Hoppe, H., Progressive Meshes, Computer Graphics Pro
`ceedings, Annual Conference Series, 1996, pp. 99—108.
`Funkhouser, TA. and Sequin, C.H., “Adaptive Display
`Algorithm for Interactive Frame Rates during Visualization
`of Complex Virtual Environments,” Computer Graphics
`Proceedings, Annual Conf. Series 1993, pp. 247—254.
`* cited by examiner
`Primary Examiner—Phu K. Nguyen
`(74) Attorney, Agent, or Firm—Pillsbury Madison & Sutro,
`LLP
`(57)
`
`ABSTRACT
`
`Amethod and apparatus that provides for off-line generation
`of, and run-time evaluation for, continuous LODs. The
`off-line multiresolution generation process is modi?ed and
`constrained such that a progressive mesh representation for
`continuous LODs is created that alloWs properly designed
`run-time topological data structures to be overloaded to
`support both LOD construction and optimized rendering.
`More speci?cally, the offline generation process initially
`preprocesses the mesh to generate a triangle-fan covering
`composed of only complete 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 dual uses. This supportive run-time
`representation is partitioned so as to alloW efficient access by
`the renderer to the subset of the adjacency information that
`is the fan covering. The multiresolution representation can
`be generated so as to alloW discontinuities to be rendered at
`some cost to rendering performance.
`
`37 Claims, 18 Drawing Sheets
`
`BASE MESH
`
`/
`
`\
`
`VERTEX
`LIST
`
`VERTEX-
`VERTEX
`CYCLES
`
`CVL‘ST
`
`NORMAL
`LIST
`
`DCVLIST
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 1 of 18
`
`US 6,169,549 B1
`
`03
`
`$22
`
`V
`
`mwmmczwm
`
`P @E
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`M§QE>
`v \ ‘£1 4
`Avaé‘d
`
`FIG. 3(5)
`(Av
`\ ‘lag
`‘RV
`
`.
`
`
`
`FIG. 3(A)
`
`‘ aw“ kw iv‘v
`‘45!
`
`E;
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 4 of 18
`
`US 6,169,549 B1
`
`@m .wm
`
`om?
`
`on?
`
`m2.
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 5 of 18
`
`US 6,169,549 B1
`
`Nam
`
`§\
`
`. wow o2.
`
`an .QE
`
`3?
`
`we
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 6 6f 18
`
`US 6,169,549 B1
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 7 0f 18
`
`US 6,169,549 B1
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 8 of 18
`
`US 6,169,549 B1
`
`AV
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 9 of 18
`
`US 6,169,549 B1
`
`-
`
`8 LD
`
`00
`CD
`LO
`
`N
`8
`
`%
`
`s
`<1
`Q
`
`LL
`
`0
`
`G)
`E
`
`3
`
`L0
`
`%
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 10 of 18
`
`US 6,169,549 B1
`
`mom
`
`man J
`
`omm
`
`a: .wm
`
`own
`
`an
`
`in
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 12 of 18
`
`US 6,169,549 B1
`
`502
`
`540
`
`504
`
`526
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 13 of 18
`
`US 6,169,549 B1
`
`_Q \ 310
`
`302
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 14 of 18
`
`US 6,169,549 B1
`
`com
`
`Em
`
`Nmm
`
`Em
`
`Nmm
`
`aa 0;
`
`wmm
`
`wmm
`
`New
`
`com
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 15 0f 18
`
`US 6,169,549 B1
`
`I NS
`
`56 .wm 6a a;
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`US 6,169,549 B1
`
`m, I?
`
`
`
`m IN? ST N?
`
`m Li
`
`‘In
`
`5: .wm a: .wm
`
`J 5
`
`a d
`
`3v 2.‘
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`U.S. Patent
`
`Jan. 2, 2001
`
`Sheet 18 of 18
`
`US 6,169,549 B1
`
`
`
`2H0.‘ A||
`
`
`
`N004 A||
`
`
`
`mac; AII
`
`
`
`Amszag?gi ANSBZSEEEEX
`
`
`
`c004 A||
`
`
`
`Acsiéééég .ESBZEEEEEX
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`US 6,169,549 B1
`
`1
`METHOD AND APPARATUS FOR
`PROVIDING CONTINUOUS LEVEL OF
`DETAIL
`
`BACKGROUND OF THE INVENTION
`
`2
`reduced or the bene?ts 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 dif?cult 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): tri
`angle 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 gen
`erated 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 incre
`mental 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 partition
`ing at all resolutions.
`Mesh discontinuities present further challenges. Adiscon
`tinuity 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 primi
`tives 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 render
`ing. 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
`?exibility in rendering discontinuities but is inef?cient in
`both time and space. Vertex pools, in current implementa
`tions in such graphics APIs as OpenGL, are only useful for
`rendering smooth objects because the normal indices cannot
`be speci?ed separately from the coordinate indices.
`Accordingly, only per-vertex normals bindings can be used,
`Whereas per-vertex, per-face binding is needed With inde
`pendent triangles. Per-vertex, per-face (i.e. per-corner) bind
`ings are possible, but vertices have to be duplicated, and this
`makes the implementation of continuous LODs very dif?
`cult.
`Therefore, there remains a need for an implementation for
`providing continuous LODs that effectively manages the
`aforementioned space and time challenges While also alloW
`ing the rendering of mesh discontinuities. The present inven
`tion ful?lls 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 render
`ing.
`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
`
`1. Field of the Invention
`The present invention relates to computer graphics, and
`more particularly, to a constrained progressive mesh repre
`sentation 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 tesse
`lated 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 ef?ciently
`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 ?ne-grained modi?cations 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
`?delity.
`In a paper entitled “Progressive Meshes,” published in
`Computer Graphics (SIGGRAPH ’96 Proceedings), (1996),
`pp. 99—108, Hugues Hoppe describes a scheme for provid
`ing continuous LODs Wherein a mesh simpli?cation proce
`dure is used to reduce a complex, highly detailed mesh M
`into a coarse approximation MO (base mesh), along With a
`sequence of n detail records that indicate hoW to incremen
`tally re?ne the base mesh MO exactly back into the original
`mesh M=M”. Hoppe introduced a simpli?cation transfor
`mation called the “edge collapse,” and its inverse re?nement
`transformation called the “vertex split.” In addition to stor
`ing the base mesh MO 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, topologi
`cal adjacency information must be available to the LOD
`builder. This information comes at a signi?cant memory cost
`that is incurred on a per-obj ect basis. Either this cost must be
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`

`

`Bradium Technologies LLC Exhibit 2010
`
`