EG99 Tutorial 1 L
O D
M O D E L S (2)
Level of Detail (LOD) Models Part Two
L O D
M O D E L S
Classification
o Nested models
mbased on a nested subdivisions of the surface domain meach cell in the subdivision is refined independently
o Evolutionary models
mbased on the evolution of a mesh through local modifications
EG99 Tutorial 3 L
O D
M O D E L S (2)
Nested models
o Root mesh at coarse resolution
o General refinement rule: each region in the mesh is refined independently into a local mesh
o An arc links a region to the local mesh refining it
L O D
M O D E L S (2)
…Nested models...
o Cracks can appear in the surface if one node is refined independently from its neighbors
o Cracks are due to edges that split during refinement
EG99 Tutorial 5 L
O D
M O D E L S (2)
Nested models as MTs
o A node of the tree is not necessarily a node of the MT
o Nodes of the MT are obtained by node clustering
o Clustering rule: if an edge e of a triangle t splits during refinement, then
m the same split must occur in refining triangle t’ adjacent to t along e
mthe meshes refining t and t’ must be clustered
o Propagation: many nodes of the tree can be clustered to form one node of the MT because of edge splits
L O D
M O D E L S
…Nested models as MTs...
EG99 Tutorial 7 L
O D
M O D E L S (2)
Quadtree-like models
o Models based on regular nested subdivisions
o Suitable for explicit surfaces, data on a regular grid
o Quadtree: recursive subdivision of a square universe into quadrants
L O D
M O D E L S (2)
Quadtree surface
o Surface within each quadrant approximated through a bilinear patch
o Each patch interpolates data at its four vertices
o A mesh formed of quadrants from different levels has cracks
EG99 Tutorial 9 L
O D
M O D E L S (2)
... Quadtree surface ...
o All quadrants of a given level must be clustered to form a single component
o Complete levels are the only possible conforming meshes
o It is not possible to change resolution through space
L O D
M O D E L S
... Quadtree surface ...
Octree [Wilhelms and Van Gelder, 1994]
o Extension of quadtree to volume data mSubdivision of a cubic universe into octants
mData field within each octant approximated through tri-linear patch
o Same problems as quadtree with cracks between octants of different levels
EG99 Tutorial 11 L
O D
M O D E L S (2)
Restricted quadtree [Von Herzen & Barr, 1987]
Merging triangles from different levels without cracks:
mAdjacent quadrants can differ by one level mEach quadrant is triangulated
mLinear interpolation is used on each triangle
L O D
M O D E L S (2)
...Restricted quadtree...
o Each quadrant can be triangulated in 16 possible patterns
o Triangulation pattern depends on levels of adjacent quadrants
o Mesh is always conforming: no cracks
o The number of regions is higher than in the original quadtree
EG99 Tutorial 13 L
O D
M O D E L S (2)
...Restricted quadtree...
Restricted quadtree and wavelets [Gross et al., 1996]
o Quadtree subdivision naturally adapt to computation of wavelet coefficients at grid vertices
o LOD refers to detail relevance in wavelet space, rather than absolute approximation error on surface
o Selective refinement: vertices are selected according to their LOD, and the resulting quadtree is triangulated a posteriori
o Two quadtree levels are allowed between adjacent quadrants
o More complex lookup table is necessary to obtain all triangulation patterns
L O D
M O D E L S
Hierarchy of right triangles
[Lindstrom et al., 1996, Evans et al., 1997, Duchaineau et al., 1997, Pajarola, 1998]
Each triangle is recursively bisected by splitting it along its longest edge
EG99 Tutorial 15 L
O D
M O D E L S (2)
...Hierarchy of right triangles...
MT corresponding to a hierarchy of right triangles:
o cluster triangles of the same level that share a short edge
o each node is formed of four triangles (except at the boundary)
o two types of nodes:
msquares mdiamonds
o each node has two parents and four sons (except at the boundary, root, and leaves)
L O D
M O D E L S (2)
...Hierarchy of right triangles...
Corresponding hierarchy of vertices:
o each node in the MT is identified with central vertex of fragment
o each vertex depends on two other vertices
o selective refinement: mesh must contain all vertices needed to achieve the LOD, plus all their ancestors
EG99 Tutorial 17 L
O D
M O D E L S (2)
…Hierarchy of right triangles...
o Different models are characterized by:
mdata structures merror evaluation mtraversal algorithms
o Trade-off between space complexity and time efficiency
L O D
M O D E L S
…Hierarchy of right triangles...
[Lindstrom et al., 1996]
o Data structure: matrix of input values
o Error: on-the-fly estimate of error in screen space
o Selective refinement: bottom-up vertex reduction
s no overhead for multiresolution data structure
EG99 Tutorial 19 L
O D
M O D E L S (2)
…Hierarchy of right triangles...
[Duchaineau et al., 1997, Evans et al., 1997]
o Data structure: binary tree of triangles
o Error: a priori evaluation
o Selective refinement: top-down traversal of the tree, by forcing splits where necessary
s no need for numerical computation during refinement
t expensive data structure
L O D
M O D E L S (2)
…Hierarchy of right triangles...
An implicit data structure:
o Matrix of input values
o An array of errors, one for each triangle
o Each triangle, and each component can be identified by a unique code
o All topological and hierarchical relations involving vertices, triangles, and fragments can be evaluated by algebraic manipulation of codes
o The array of errors is addressed directly through codes
s Very efficient time performance with a moderate overhead
EG99 Tutorial 21 L
O D
M O D E L S (2)
…Hierarchy of right triangles...
o Codes for triangles [Hebert, 1995]
mReference domain: unit square [0,1]x[0,1]
mQuadtree subdivision:
Ga quadrant is identified by its center
Gthe center of a quadrant at level m is encoded by a sequence of m quaternary digits (2m bits)
where all are pairs of signs: (-1,-1) (-1,1) (1,-1) (1,1)
L O D
M O D E L S
…Hierarchy of right triangles...
mFor each level of the quadtree there are two levels in the tree of triangles: each quadrant is subdivided in two possible ways mTriangles in a quadrant are identified by a pair of digits (l,t)
where l is the type of subdivision, and t is the index of a triangle in the subdivision (total 4 bits)
EG99 Tutorial 23 L
O D
M O D E L S (2)
…Hierarchy of right triangles...
o Topological relations are evaluated by algebraic manipulation of codes. From a triangle we can obtain:
mvertices mparent triangle msons
m adjacent triangles at the same level madjacent triangle at the previous level madjacent triangles at the next level
L O D
M O D E L S (2)
…Hierarchy of right triangles...
o Codes for nodes of the MT:
mtwo kinds of nodes: squares and diamonds ma node is encoded by its center
ma square coincides with a quadtree quadrant Ü same code ma diamond is encoded with a similar formula that identifies its
center vertex
EG99 Tutorial 25 L
O D
M O D E L S (2)
…Hierarchy of right triangles...
o Relations among triangles and nodes are evaluated by algebraic manipulation of codes. From a node we can obtain:
mtriangles in it mtriangles in its floor mparent nodes mchild nodes
The algorithm for selective refinement for MT can be implemented efficiently on a hierarchy of right triangles encoded by the implicit data structure
L O D
M O D E L S
…Hierarchy of right triangles...
Results of selective refinement with view frustum, and error increasing with distance from viewpoint
EG99 Tutorial 27 L
O D
M O D E L S (2)
... Hierarchy of right triangles ...
Multi-tetra framework [Maubach, 1994, Zhou et al., 1997]
o Extension of hierarchy of right triangles to volume data:
mSubdivision of a cubic universe into twelve tetrahedra mRecursive bisection of each tetrahedron at the midpoint of its
longest edge
o Implicit data structure as in the 2D case [Hebert, 1994]
L O D
M O D E L S (2)
Quaternary triangulations
o Recursive subdivision of a triangular domain into four triangles by joining the edge midpoints
o Applicable as a refinement scheme to an arbitrary surface mesh at low resolution
o Topological constraints on positions of vertices (needs re-meshing)
o Supports methods based on wavelets
o A mesh made of triangles from different levels has cracks
EG99 Tutorial 29 L
O D
M O D E L S (2)
...Quaternary triangulations...
o Different levels of the hierarchy can be merged through a posteriori triangulation of non-conforming meshes
o Eight triangulation patterns
o Patterns less regular than those used for restricted quadtrees
o Model completed with such triangulation patterns is not an MT
L O D
M O D E L S
...Quaternary triangulations...
Extension to 3D [Grosso & Ertl, 1997, Grumpf, 1997]
o Recursive partition of a tetrahedron into eight tetrahedra by splitting each edge at its midpoint
o 8-ary tree
o Tetrahedra from different levels made conforming through subdivision patterns analogous to those in 2D
EG99 Tutorial 31 L
O D
M O D E L S (2)
Adaptive hierarchical triangulations
o Based on irregular triangulations
o Suitable for sparse data sets
o Error driven subdivision rule: refine a triangle by inserting vertices that cause the largest errors
o Vertices can be inserted inside a triangle and/or on its edges
s More adaptive than models based on fixed subdivision rules
t May contain elongated triangles (slivers)
L O D
M O D E L S (2)
...Adaptive hierarchical triangulations...
[Pavlidis and Scarlatos, 1990/92]
o Find the vertex causing the largest error inside the triangle and the vertices causing the largest error along each edge
o Select only vertices whose error is beyond a given threshold
o Use predefined subdivision patterns [De Floriani and Puppo, 1992/95]
o Insert the vertex causing the largest error until a given accuracy is achieved
o At each insertion compute the
EG99 Tutorial 33 L
O D
M O D E L S (2)
Evaluation of tree-like models
Regular subdivisions
s Pros:
measy to handle
mcompact data structures mregular shape of regions msupport wavelets t Cons:
monly regular data:
topological constraints mquadtrees and right
triangles only for terrain mless adaptive than irregular
triangulations
Irregular subdivisions
s Pros:
msuitable for arbitrary data and for arbitrary surfaces
mmore adaptive than regular subdivisions
t Cons:
melongated triangles
mcumbersome data structures mselective refinement not easy
L O D
M O D E L S
Evolutionary models
Store the evolution of a mesh through either refinement or simplification algorithm based on local modifications
o Partial order is given by relations among components of the mesh (vertices, faces, etc…) before and after each local modification
o Different models characterized by:
mtypes of surfaces supported mconstruction method
EG99 Tutorial 35 L
O D
M O D E L S (2)
...Evolutionary models...
o Models based on vertex insertion / vertex decimation m[De Floriani, 1989]
m[de Berg and Dobrindt, 1995]
m[Cignoni et al., 1995/97]
m[Brown, 1996/97]
m[Klein and Strasser, 1996]
m[De Floriani et al., 1996/97/98]
L O D
M O D E L S (2)
...Evolutionary models...
o Models based on vertex split / edge collapse m[Hoppe, 1996/97/98]
m[Xia et al., 1996/97]
m[Maheswari et al., 1997]
m[Gueziec et al., 1998]
m[Kobbelt et al., 1998]
EG99 Tutorial 37 L
O D
M O D E L S (2)
Construction through refinement
o Method applied only to build models based on vertex insertion mStart from a coarse mesh at low resolution built on a small subset
of data
mPerform iterative local refinements until all data have been inserted as vertices of the mesh
o The initial mesh is the root of an MT
o Each local refinement generates a node of an MT formed of new triangles inserted in the mesh
o Difficult to apply to generic manifold surfaces
L O D
M O D E L S
...Construction through refinement...
o Node generated by vertex insertion: a star of triangles surrounding the new vertex
o Floor of a node: a star-shaped triangulated polygon
o Key issues:
mselection of vertices to insert mtriangulation method
EG99 Tutorial 39 L
O D
M O D E L S (2)
...Construction through refinement...
o Greedy refinement:
mat each step, insert vertex causing the largest error
mmesh update based on either Delaunay or data dependent triangulation
sgood heuristic to reduce the number of points to achieve a given accuracy sinserting vertices of bounded degree
guarantees linear growth
tmethod cannot guarantee that accuracy improves at every refinement step tfragments may pile-up in a high hierarchy:
low expressive power
low performance of traversal algorithms
L O D
M O D E L S (2)
...Construction through refinement...
Extension to 3D [Cignoni et al., 1994/1997]
o Iterative insertion of vertices in a Delaunay tetrahedrization
o Vertex selection rule as in 2D
o Applicable to convex and curvilinear volume data sets
EG99 Tutorial 41 L
O D
M O D E L S (2)
Construction through simplification
o Any local simplification rule can be used (vertex decimation, edge collapse, etc.)
mStart from mesh at full resolution, based on all data mPerform iterative local simplifications
o The final mesh is the root of an MT
o Each simplification step generates a node formed of triangles eliminated from the mesh
o The new portion of mesh generated by a simplification step is the floor of the corresponding node
o Applicable to generic manifold surfaces
L O D
M O D E L S
...Construction through simplification...
o Vertex decimation:
mnode: a star of triangles surrounding the removed vertex
mfloor of a node: a star-shaped triangulated polygon
o Key issues:
mselection of vertices to remove mtriangulation method
EG99 Tutorial 43 L
O D
M O D E L S (2)
...Construction through simplification...
o Greedy decimation:
mat each step, remove vertex causing the least error increase
mmesh update based on either Delaunay triangulation or heuristics
u result similar to greedy refinement sremoving vertices of bounded degree
guarantees linear growth tcomponents may pile-up in an
unbalanced DAG
L O D
M O D E L S (2)
...Construction through simplification...
o Decimation of independent sets of vertices:
mat each iteration remove a set vertices such that all vertices Ghave bounded degree
Gare mutually independent (no two vertices share an edge) mvertices to remove selected with a greedy technique giving
highest priority to vertices causing the least error increase meach vertex defines a different fragment
mholes triangulated with Delaunay or data-dependent rule smethod guarantees linear growth, bounded width and
logarithmic height
EG99 Tutorial 45 L
O D
M O D E L S (2)
...Construction through simplification...
L O D
M O D E L S
...Construction through simplification...
o Edge collapse on midpoint:
mnode: cycle of triangles surrounding the collapsed edge
mfloor: star of triangles surrounding the vertex resulting from collapse
o Edge collapse on endpoint:
mnode: star of triangles
EG99 Tutorial 47 L
O D
M O D E L S (2)
...Construction through simplification...
Illegal edge collapse: one or more triangles flip over because of collapse operation.
L O D
M O D E L S (2)
...Construction through simplification...
o Edge collapsing rules:
mGreedy: collapse an edge at each step:
Gthe shortest edge
Gthe edge causing the least error increase Gan edge surrounded by almost coplanar faces mIndependent set:
Gtwo edges are independent if they have disjoint influence regions Gselect a maximal set of independent edges and collapse them all
together
u Results similar to decimation:
sremoving vertices of bounded degree guarantees bounded width and linear growth
sremoving an independent set guarantees logarithmic height tin greedy collapse fragments may pile-up in a high hierarchy
EG99 Tutorial 49 L
O D
M O D E L S (2)
...Construction through simplification...
Extension to 3D [Cignoni et al., 1997]
o Edge collapse in a tetrahedrization: collapse an edge and the star of tetrahedra surrounding it
o Edge selection as in 2D
o Applicable to all kinds of volume data sets
L O D
M O D E L S
...Construction through simplification...
Decimation
s smaller influence regions
s more regular triangles
s always possible for any vertex
Collapse
s simple update rules
s supports geo-morphing
t larger influence regions
t slivers
EG99 Tutorial 51 L
O D
M O D E L S (2)
Data structures
Relevant information on evolutionary models
o Geometry: coordinates of vertices
o Connectivity: triples of vertices forming triangles
o Topology: adjacency, boundary, co-boundary relations mlocal topology: among elements of a single node
mglobal topology: among components of different nodes
o Spatial interference: relations among nodes and triangles that have spatial interference
o Additional information: accuracy, material, surface normal, etc.
L O D
M O D E L S (2)
...Data structures...
o Different data structures characterized by the amount of information stored
o Trade-off between spatial complexity and efficiency mcompact data structures more suitable to storage and
transmission
mextended data structures more suitable to complex operations:
Gselective refinement Gspatial queries
o Compactness can be achieved by exploiting properties of special models
EG99 Tutorial 53 L
O D
M O D E L S (2)
...Data structures...
Linear sequences: store sequences of local modifications that produce a refined mesh starting at a coarse mesh
o List of vertices [Klein & Strasser, 1996] :
mstore initial mesh plus sequence of vertices in suitable order meach vertex in the sequence is inserted iteratively to refine mesh mmesh is updated with Delaunay (implicit) rule at each insertion
svery compact
tsuitable only to explicit and parametric surfaces tlocal update requires numerical computation tselective refinement is computationally expensive tno connectivity, topological, and interference information
maintained
L O D
M O D E L S
...Data structures...
o List of triangles [Cignoni et al., 1995] :
mstore all triangles appearing during refinement/simplification meach triangle is tagged with a life: range of accuracies through
which it “survives” during refinement/simplification mlife is used to extract meshes at a given (uniform) LOD mextended to 3D for volume data [Cignoni et al., 1997]
sapplicable to all kinds of surface
EG99 Tutorial 55 L
O D
M O D E L S (2)
...Data structures...
o Progressive Meshes [Hoppe, 1996/98] :
mstore initial coarse mesh plus a sequence of vertex splits (inverse operation of edge collapse) in suitable order
meach vertex split is maintained in compressed format meach vertex split gives a node of a corresponding MT
ma uniform LOD is extracted by expanding the sequence up to the desired level
scompact
sextraction of a uniform LOD efficient without numerical computation
ssuitable additional structures to maintain attributes tselective refinement needs additional information tno connectivity, topology and interference maintained
L O D
M O D E L S (2)
...Data structures...
o Sequence of vertex insertions [De Floriani et al., 1998]:
mstore initial mesh plus a set to vertex insertions in suitable order manalogous to PM but based on vertex insertion rather than split msupports arbitrary triangulations including:
GDelaunay triangulation
GConstrained Delaunay triangulation GData dependent triangulations smore flexible than PM
tslightly more expensive than PM
EG99 Tutorial 57 L
O D
M O D E L S (2)
...Data Structures...
Explicit MT representation [De Floriani et al., 1996/98]
o Geometry: vertex coordinates
o Connectivity:
mfor each triangle: error + references to its three vertices o DAG structure:
mfor every arc (Tj,Ti): links to source and destination node, link to the set of triangles of Tj which form the floor of Ti
mfor every node: link to the sets of its incoming and outcoming arcs
L O D
M O D E L S
...Data Structures...
EG99 Tutorial 59 L
O D
M O D E L S (2)
...Data structures...
...Explicit MT representation...
sSupports selective refinement efficiently sSupports spatial queries efficiently
tHigh storage cost tNo topology
L O D
M O D E L S (2)
...Data structures...
Compressed hierarchies:
o Key ideas:
meach node of an MT is a local modification that can be encoded in compressed form
mhierarchical links among nodes are encoded explicitly
o Different structures for models based on edge collapse (PM):
m[Xia et al., 1996/97]
m[Hoppe, 1997]
m[Gueziec et al., 1998]
o One structure for models based on vertex decimation:
m
EG99 Tutorial 61 L
O D
M O D E L S (2)
...Data structures...
Compressed hierarchies for PMs Vertex tree (forest) [Xia et al., 1996/97]
mBinary forest of vertices
Gtopmost level: vertices of the base mesh Gchildren of a vertex: vertices resulting from split mVertex split can be encoded in compressed form
mRule for selective refinement: a vertex can split if and only if all boundary vertices of the corresponding fragment belong to the current mesh Ü need for additional interference links
mFor each vertex:
Gparent-child relation in forest
Gadditional links to vertices that must exist in order to allow split sMore compact than explicit MT
tLess general than explicit MT tNo control on accuracy of triangles
L O D
M O D E L S
...Data structures...
Extended PM structure [Hoppe, 1997]
mSame hierarchy as in [Xia et al.], but vertices are renamed at each split mArray of vertices - for each vertex:
Gcompressed split information Gparent-child information
Gconstant number of dependencies for split/collapse with triangles and vertices of influence region
mArray of faces - for each face:
Gindexes of vertices
EG99 Tutorial 63 L
O D
M O D E L S (2)
...Data structures...
Example of illegal split
L O D
M O D E L S (2)
...Data structures...
Collapse DAG [Gueziec et al., 1998]
mDAG of edge collapse operations: one node per collapse mEdge collapse always on endpoint Ü one vertex survives mAlmost the same hierarchy as MT
mDependencies maintained in hash tables u Cost and performances similar to [Xia et al.]
EG99 Tutorial 65 L
O D
M O D E L S (2)
...Data structures...
Compressed hierarchies for MT based on decimation Implicit MT [De Floriani et al., 1997/98]
mEach node corresponds to vertex insertion/decimation mPartial order of nodes is maintained
mArray of vertices, each entry storing vertex coordinates mArray of arcs - for every arc a:
Gindexes of source and destination nodes Gindex of next arc with same destination node mArray of nodes - for every node n:
Gindex of first outgoing and incoming arcs Gnumber of outgoing arcs
Gmaximum error of its triangles
Gcompressed information to perform vertex insertion/decimation
L O D
M O D E L S
...Data structures...
…Implicit MT...
o Storage cost:
s3.5 times cheaper than Explicit MT
u Comparable with vertex tree, and collapse DAG o Selective refinement:
tSlower than Explicit MT
tAccuracy not stored for each triangle Ü resulting mesh not minimal (about twice the size of mesh obtained from Explicit MT)
EG99 Tutorial 67 L
O D
M O D E L S (2)
...Data structures...
Hypertriangulation [Cignoni et al., 1995/97]
o Interpretation of an MT in a higher dimensional space:
triangles of a new node are lifted along a “resolution axis” and welded on floor at the node boundary
L O D
M O D E L S (2)
...Data structures...
...Hypertriangulation...
o Data structure based on topological information (global adjacency)
stopology is maintained explicitly
sefficient support of queries requiring navigation of domain sinteractive mesh editing
thigh storage cost
tno interference information
tselective refinement super-linear and possible only for some LOD functions
EG99 Tutorial 69 L
O D
M O D E L S (2)
Selective refinement
o Top-down traversal of hierarchy:
mon generic MT [Puppo, 1996, De Floriani et al., 1997/98]
mon PM [Hoppe, 1997, Xia et al., 1997]
mon restricted quadtrees [Von Herzen and Barr, 1987, Gross et al., 1996]
mon hierarchy of right triangles [Evans et al., 1997, Duchaineau et al., 1997]
mon hierarchy of irregular triangles [De Floriani & Puppo, 1995]
o Bottom-up traversal of hierarchy:
mon PM [Xia et al., 1996]
mon hierarchy of right triangles [Lindstrom et al., 1996]
o Breadth-first traversal of surface:
mon hypertriangulation [Cignoni et al., 1995/97]
mon hierarchical triangulation [De Floriani & Puppo, 1995]
L O D
M O D E L S
…Selective refinement...
Top-down on MT
o Visit DAG starting at cut just below its root
o Recursively move cut below a node n when a triangle labeling an arc entering n has accuracy worse than LOD
Algorithm on explicit MT:
sOptimally efficient (on MT with linear growth) sApplicable to all models
tNeeds expensive data structure
EG99 Tutorial 71 L
O D
M O D E L S (2)
…Selective refinement...
Top-down on PM (vertex forest or DAG)
o Visit forest/DAG starting at topmost level
o Recursively expand a vertex when accuracy worse than LOD
o Find all vertices that constrain selected vertices
o Perform all splits corresponding to selected vertices in the default order
s Fast
t Needs expensive data structure
L O D
M O D E L S (2)
…Selective refinement...
Top-down on restricted quadtrees
o Visit tree starting at its root
o Recursively expand a quadrant when accuracy worse than LOD
o Balance quadtree
o Triangulate each quadrant according to its neighbors
s Fast
t No control on error of triangles generated a posteriori
t Needs suitable procedures for neighbor finding
EG99 Tutorial 73 L
O D
M O D E L S (2)
…Selective refinement...
Top-down on tree of right triangles
o Visit tree starting at its root
o Recursively refine a triangle when accuracy worse than LOD
o Propagate vertex dependencies to obtain a conforming mesh
s Easy and fast if all vertex dependencies are available Top-down on trees of irregular triangles
o Visit tree starting at its root
o Recursively expand a triangle when accuracy worse than LOD
o Triangulate mesh a posteriori to make it conforming
s Easy and fast
t No control on error of triangles generated a posteriori
L O D
M O D E L S
…Selective refinement...
Bottom-up on PM (vertex forest):
o Visit forest starting at leaves
o Recursively discard leaves that can be collapsed
o Perform splits corresponding to selected vertices in default order
Bottom-up on hierarchy of right triangles:
o Visit tree starting at leaves
o Recursively merge sibling leaves when possible
EG99 Tutorial 75 L
O D
M O D E L S (2)
…Selective refinement...
Breadth-first traversal of domain on hypertriangulations and on hierarchical triangulations
o Start with a triangle where highest LOD is required
o Incrementally add triangles adjacent to the boundary of current triangulation through global adjacencies
o Each time a boundary edge e is crossed, select a triangle which is as coarse as possible, satisfied the LOD, and is compatible with current mesh
s Supports dynamic local refinement/abstraction of detail (resolution editing)
s Ideal for propagating LOD through the surface rather than through space
t Applicable only for LOD monotonically decreasing with distance from a given point
t Computational complexity is super-linear
t Needs expensive data structure
L O D
M O D E L S (2)
Discussion
Taxonomy
o Modeling issues:
mtypes of surfaces supported mdata distribution
mexpressive power mshape of triangles mstorage
o Processing issues:
mselective refinement mprogressive transmission mnavigation
mgeometric queries
EG99 Tutorial 77 L
O D
M O D E L S (2)
...Discussion...
Types of surfaces supported
o All types:
mMT, PM, HyT, quaternary triangulations
o Explicit and parametric surfaces only:
mquadtrees, restricted quadtrees, hierarchies of right triangles (problems with trimming curves)
mAdaptive hierarchical triangulations
L O D
M O D E L S
...Discussion...
Data distribution
o Data distribution: irregular distribution vs regular grid
Irregular
MT, HyT, PM, Adaptive hierarchical triangulations
Quaternary triangulations (with remeshing)
EG99 Tutorial 79 L
O D
M O D E L S (2)
...Discussion...
Expressive power
o Number of different meshes that can be extracted
o Possibility to adapt a mesh to arbitrary LOD
o Ratio accuracy/size More expressive,
higher ratio
Less expressive, lower ratio
Explicit MT PM, Implicit MT HyT
Quaternary triangulations Hierarchy of right triangles,
quadtree,restricted quadtree, Adaptive hierarchical triangulations
L O D
M O D E L S (2)
...Discussion...
Shape
o Regions with regular shape are desirable
o Slivers cause numerical errors, and unpleasant visual effects More regular Quadtree, restricted quadtree,
hierarchy of right triangles Quaternary triangulation HyT, MT
PM
EG99 Tutorial 81 L
O D
M O D E L S (2)
...Discussion...
Storage
o Compact data structures are desirable
o Increasing complexity: geometry, connectivity, interference, topology
More expensive
Less expensive
Adaptive hierarchical triangulations HyT
Explicit MT, vertex hierarchies Implicit MT
Linear sequences (linear PM) Quadtree, quaternary triangulation,
hierarchy of right triangles
L O D
M O D E L S
...Discussion...
Selective refinement
o High efficiency is desirable
More efficient Explicit MT
Hierarchy of right triangles PM vertex hierarchies Implicit MT
HyT
EG99 Tutorial 83 L
O D
M O D E L S (2)
...Discussion...
Progressive transmission
o Compact coding and fast decompression at client are relevant
More efficient
Less efficient
Quadtree, hierarchy of right triangles Linear PM
Implicit MT, PM vertex hierarchies Other linear sequences
Explicit MT
Restricted quadtree, quaternary triangulation
L O D
M O D E L S (2)
...Discussion...
Navigation
o Ability to move across surface and through LOD
More efficient Quadtree, hierarchy of right triangles Restricted quadtree, quaternary Adaptive hierarchical triangulation HyT
Explicit MT
Implicit MT, PM vertex hierarchies
EG99 Tutorial 85 L
O D
M O D E L S (2)
...Discussion...
Geometric queries
o Point location, windowing, segment intersection, ray shooting, clip, etc…
o Bounded width and logarithmic height are relevant More efficient
Less efficient
Quadtree, hierarchy of right triangles Restricted quadtree, quaternary Adaptive hierarchical triangulation Explicit MT
HyT
Implicit MT, PM vertex hierarchies Linear sequences
L O D
M O D E L S
...Discussion...
Construction
o Lower time complexity of construction algorithm is desirable
o Easy-to-code algorithms are desirable More complex,
more difficult
Adaptive hierarchical triangulations HyT
MT, PM vertex hierarchies
