3 Out-of-core Multiresolution Terrain Modeling
49
Table 3.1. Comparison among simplification algorithms for triangle meshes
data set
partitioning
simplification
multires
space
Lindstrom [27]
tri mesh
regular grid
vertex clustering
no
O(out)
Lindstrom et al. [28]
tri mesh
regular grid
vertex clustering
no
O(1)
Shaffer et al. [42]
tri mesh
BSP tree
vertex clustering
no
O(out)
Garland et al. [17]
tri mesh
regular grid
clust.+collapse
yes
O(out)
Hoppe [20]
DEM
space part.
edge collapse
yes
O(1)
Prince [37]
TIN
space part.
edge collapse
no
O(1)
El-Sana et al. [12]
tri mesh
greedy dec.
edge collapse
yes
O(1)
Magillo et al. [33]
tri mesh
user defined
vertex removal
yes
O(1)
Cignoni et al. [3]
tri mesh
space part.
edge collapse
yes
O(1)
Isenburg et al. [23]
tri mesh
streaming
various
no
3.3.4 Comparison
Table 3.1 summarizes the main features of out-of-core simplification techniques. For
each method, we list the following: the type of input (Data set); the type of space
partition adopted (Partitioning); the type of approach (Simplification); the possibility to build a multiresolution model based on the specific simplification technique
(Multires); and the space requirements in main memory (Space). The algorithms
by Hoppe [20], Prince [37], and Magillo and Bertocci [33] are designed for either
regular or irregular terrain data, while all the other techniques can handle arbitrary
triangle meshes describing the boundary of 3D objects. When applied to terrain simplification, algorithms based on space partitioning should be modified by replacing
the octree that partitions 3D space with a simpler quadtree partition of the 2D domain
of the TIN. Note that only methods based on space partitioning are suitable to build
multiresolution models.
3.4 Out-of-core Representation of Regular
Multiresolution Models
Multiresolution terrain models that work on data regularly distributed on a grid have
been proposed in the literature [10, 13, 18, 25, 26, 35]. Such models are based on
a nested subdivision that starts from a simple regular tiling of the terrain domain
into regular triangles and is generated through a refinement process defined by the
uniform subdivision of a triangle into scaled copies of it. The two most common
refinement operators used for generating regular multiresolution models are triangle
quadrisection and triangle bisection.
The quadrisection of a triangle t consists of inserting a new vertex on each edge
of t in such a way that the original triangle t is split into four subtriangles (see
Fig. 3.1 (a,b)). The resulting (nested) hierarchy of triangles is encoded as a quadtree,
called a “triangle quadtree” (see Fig. 3.1 (c)). A triangle quadtree is used for terrain
49
Table 3.1. Comparison among simplification algorithms for triangle meshes
data set
partitioning
simplification
multires
space
Lindstrom [27]
tri mesh
regular grid
vertex clustering
no
O(out)
Lindstrom et al. [28]
tri mesh
regular grid
vertex clustering
no
O(1)
Shaffer et al. [42]
tri mesh
BSP tree
vertex clustering
no
O(out)
Garland et al. [17]
tri mesh
regular grid
clust.+collapse
yes
O(out)
Hoppe [20]
DEM
space part.
edge collapse
yes
O(1)
Prince [37]
TIN
space part.
edge collapse
no
O(1)
El-Sana et al. [12]
tri mesh
greedy dec.
edge collapse
yes
O(1)
Magillo et al. [33]
tri mesh
user defined
vertex removal
yes
O(1)
Cignoni et al. [3]
tri mesh
space part.
edge collapse
yes
O(1)
Isenburg et al. [23]
tri mesh
streaming
various
no
3.3.4 Comparison
Table 3.1 summarizes the main features of out-of-core simplification techniques. For
each method, we list the following: the type of input (Data set); the type of space
partition adopted (Partitioning); the type of approach (Simplification); the possibility to build a multiresolution model based on the specific simplification technique
(Multires); and the space requirements in main memory (Space). The algorithms
by Hoppe [20], Prince [37], and Magillo and Bertocci [33] are designed for either
regular or irregular terrain data, while all the other techniques can handle arbitrary
triangle meshes describing the boundary of 3D objects. When applied to terrain simplification, algorithms based on space partitioning should be modified by replacing
the octree that partitions 3D space with a simpler quadtree partition of the 2D domain
of the TIN. Note that only methods based on space partitioning are suitable to build
multiresolution models.
3.4 Out-of-core Representation of Regular
Multiresolution Models
Multiresolution terrain models that work on data regularly distributed on a grid have
been proposed in the literature [10, 13, 18, 25, 26, 35]. Such models are based on
a nested subdivision that starts from a simple regular tiling of the terrain domain
into regular triangles and is generated through a refinement process defined by the
uniform subdivision of a triangle into scaled copies of it. The two most common
refinement operators used for generating regular multiresolution models are triangle
quadrisection and triangle bisection.
The quadrisection of a triangle t consists of inserting a new vertex on each edge
of t in such a way that the original triangle t is split into four subtriangles (see
Fig. 3.1 (a,b)). The resulting (nested) hierarchy of triangles is encoded as a quadtree,
called a “triangle quadtree” (see Fig. 3.1 (c)). A triangle quadtree is used for terrain