3 Out-of-core Multiresolution Terrain Modeling
59
an internal cell stores a vertex v and the triangles are removed from the representation
when v is collapsed.
The mesh indexed in the leaves of the resulting multiresolution model is the
one generated by the first simplification step. Thus, the original full-resolution mesh
cannot be reconstructed. The multiresolution model is completely built on disk.
View-dependent refinement is performed by two threads: one extracts the variableresolution mesh, according to an approximate breadth-first octree traversal of the
tree, while the other thread renders the mesh. Disk paging is left to the operating
system. This is a reasonable choice, since data are sorted in a cache coherent way,
but the technique could be further improved by an explicit paging scheme.
Shaffer and Garland’s approach [43] is to develop a design for a data structure that offers explicit access to the original mesh. On the other hand, Lindstrom’s
method has the benefit of working completely out of core, while Shaffer and
Garland’s method keeps a hash table that refers only to non-empty cells of the grid
in the memory. This could be a problem for very dense meshes filling the space.
Moreover, hash keys are stored in 32 bits, and each key is composed of the three vertex coordinates. This bounds the size of the uniform grid to 1024
3 . For out-of-core
terrain modeling, both approaches can be simplified by using a quadtree to describe
the vertex clustering. In this scenario, Lindstrom’s approach could be definitely more
efficient, since their performances are not affected by the percentage of full cells in
the domain decomposition.
In [45], Yoon et al. propose an out-of-core multiresolution model for viewdependent rendering of massive triangle meshes describing 3D scenes. The multiresolution model is called a clustered hierarchy of progressive meshes (CHPMs), and
it consists of a hierarchy of clusters that are spatially localized mesh regions and of
linear sequences of edge collapses, each associated with a cluster, that simplify the
corresponding meshes. Each cluster consists of a mesh formed by a few thousand triangles. The clusters are used to perform coarse-grained view-dependent refinement
of the model, while the linear sequences of edge collapses are used for fine-grained
local refinement. The cluster hierarchy is enhanced with dependencies among clusters that act as constraints to be able to generate crack-free meshes. A CHPM is
computed in three steps. First, the vertices of the mesh at full resolution are organized into clusters containing almost the same number of vertices. A regular grid is
superimposed on the set of vertices and a graph G = (N, A) is computed, in which
the nodes correspond to the non-empty cells of the grid, while any arc in A connects
a node in N and its k-nearest neighboring cells. Graph G is partitioned into clusters,
and a new graph is computed in which the nodes are associated with clusters, and two
nodes are connected by an arc if the corresponding clusters share vertices or if they
are within a threshold distance of each other. Then, the cluster hierarchy is generated
top-down by recursively partitioning the cluster graph into halves, thus producing a
binary hierarchy. Finally, the triangles of the full-resolution mesh are associated with
the clusters in the hierarchy and a mesh simplification process is applied bottom-up
on the hierarchy of clusters by performing half-edge collapses. During each pass of
simplification only the cluster is simplified and the clusters with which it shares vertices must be resident in the memory. When performing view-dependent refinement,
59
an internal cell stores a vertex v and the triangles are removed from the representation
when v is collapsed.
The mesh indexed in the leaves of the resulting multiresolution model is the
one generated by the first simplification step. Thus, the original full-resolution mesh
cannot be reconstructed. The multiresolution model is completely built on disk.
View-dependent refinement is performed by two threads: one extracts the variableresolution mesh, according to an approximate breadth-first octree traversal of the
tree, while the other thread renders the mesh. Disk paging is left to the operating
system. This is a reasonable choice, since data are sorted in a cache coherent way,
but the technique could be further improved by an explicit paging scheme.
Shaffer and Garland’s approach [43] is to develop a design for a data structure that offers explicit access to the original mesh. On the other hand, Lindstrom’s
method has the benefit of working completely out of core, while Shaffer and
Garland’s method keeps a hash table that refers only to non-empty cells of the grid
in the memory. This could be a problem for very dense meshes filling the space.
Moreover, hash keys are stored in 32 bits, and each key is composed of the three vertex coordinates. This bounds the size of the uniform grid to 1024
3 . For out-of-core
terrain modeling, both approaches can be simplified by using a quadtree to describe
the vertex clustering. In this scenario, Lindstrom’s approach could be definitely more
efficient, since their performances are not affected by the percentage of full cells in
the domain decomposition.
In [45], Yoon et al. propose an out-of-core multiresolution model for viewdependent rendering of massive triangle meshes describing 3D scenes. The multiresolution model is called a clustered hierarchy of progressive meshes (CHPMs), and
it consists of a hierarchy of clusters that are spatially localized mesh regions and of
linear sequences of edge collapses, each associated with a cluster, that simplify the
corresponding meshes. Each cluster consists of a mesh formed by a few thousand triangles. The clusters are used to perform coarse-grained view-dependent refinement
of the model, while the linear sequences of edge collapses are used for fine-grained
local refinement. The cluster hierarchy is enhanced with dependencies among clusters that act as constraints to be able to generate crack-free meshes. A CHPM is
computed in three steps. First, the vertices of the mesh at full resolution are organized into clusters containing almost the same number of vertices. A regular grid is
superimposed on the set of vertices and a graph G = (N, A) is computed, in which
the nodes correspond to the non-empty cells of the grid, while any arc in A connects
a node in N and its k-nearest neighboring cells. Graph G is partitioned into clusters,
and a new graph is computed in which the nodes are associated with clusters, and two
nodes are connected by an arc if the corresponding clusters share vertices or if they
are within a threshold distance of each other. Then, the cluster hierarchy is generated
top-down by recursively partitioning the cluster graph into halves, thus producing a
binary hierarchy. Finally, the triangles of the full-resolution mesh are associated with
the clusters in the hierarchy and a mesh simplification process is applied bottom-up
on the hierarchy of clusters by performing half-edge collapses. During each pass of
simplification only the cluster is simplified and the clusters with which it shares vertices must be resident in the memory. When performing view-dependent refinement,