3 Out-of-core Multiresolution Terrain Modeling
55
1
3
2
4
5
6
1
3
2
4
5
6
1
3
2
4
5
6
1
3
2
4
5
6
start
add 1
add 3
add 6 and 2
Fig. 3.5. Selective refinement with a top-down depth-first approach
the base mesh all and only those updates that are necessary to achieve a given, userdefined LOD in a user-defined region of interest. Figure 3.5 shows the behavior of
selective refinement with a top-down depth-first approach. The update without label
denotes the dummy modification corresponding to creating the base mesh. White
updates satisfy the user criterion, gray updates do not. The dashed line encloses the
current set of updates.
There are two main strategies to organize data into clusters that fit disk pages.
The first approach consists of clustering nodes of the hierarchy, corresponding to
atomic updates. The second approach consists of clustering data by spatial proximity.
We will follow this classification to describe the various methods in the following
subsections.
3.5.1 Methods Based on Clustering of Atomic Updates
In [12], El-Sana and Chiang build an out-of-core multiresolution model based on
edge collapse, which is generated through the simplification algorithm described in
Sect. 3.3, and targeted to support view-dependent rendering. The dependency relation among updates is represented as a binary forest of vertices, called a “viewdependent tree.” If an edge e = (v 1 , v 2 ) is collapsed into a vertex v, then the node
corresponding to v will be the parent of the two nodes corresponding to vertices v 1
and v 2 , respectively. There is a one-to-one relation between vertices in the forest and
nodes in the DAG of the general model. Arcs of the binary tree are not sufficient to
encode all dependencies in the DAG. However, a vertex enumeration mechanism is
associated with the vertices in the binary forest to correctly represent the dependency
relation among updates, as described in [11].
The binary vertex forest is clustered in subtrees of height h, and thus, each subtree
contains at most 2h−1 nodes of the tree. The value h is selected to maximize disk page
filling. The selective refinement algorithm keeps in memory the set of subtrees that
store the vertices belonging to the extracted mesh, and keeps in cache their parents
and children also. If prefetched subtrees exceed cache size, the first prefetched page,
not used by the extracted mesh, is removed from the cache. Figure 3.6 shows a simple
binary vertex forest clustered in subtrees of height 2.
Pajarola in [36] proposes a compact representation for multiresolution models
built through half-edge collapse, that is, by contracting an edge e = (v 1 , v 2 ) to one of
its extreme vertices, let us say v 1 . The multiresolution model encodes a binary forest
of half-edge collapses. This forest is obtained from the forest of binary vertices by
55
1
3
2
4
5
6
1
3
2
4
5
6
1
3
2
4
5
6
1
3
2
4
5
6
start
add 1
add 3
add 6 and 2
Fig. 3.5. Selective refinement with a top-down depth-first approach
the base mesh all and only those updates that are necessary to achieve a given, userdefined LOD in a user-defined region of interest. Figure 3.5 shows the behavior of
selective refinement with a top-down depth-first approach. The update without label
denotes the dummy modification corresponding to creating the base mesh. White
updates satisfy the user criterion, gray updates do not. The dashed line encloses the
current set of updates.
There are two main strategies to organize data into clusters that fit disk pages.
The first approach consists of clustering nodes of the hierarchy, corresponding to
atomic updates. The second approach consists of clustering data by spatial proximity.
We will follow this classification to describe the various methods in the following
subsections.
3.5.1 Methods Based on Clustering of Atomic Updates
In [12], El-Sana and Chiang build an out-of-core multiresolution model based on
edge collapse, which is generated through the simplification algorithm described in
Sect. 3.3, and targeted to support view-dependent rendering. The dependency relation among updates is represented as a binary forest of vertices, called a “viewdependent tree.” If an edge e = (v 1 , v 2 ) is collapsed into a vertex v, then the node
corresponding to v will be the parent of the two nodes corresponding to vertices v 1
and v 2 , respectively. There is a one-to-one relation between vertices in the forest and
nodes in the DAG of the general model. Arcs of the binary tree are not sufficient to
encode all dependencies in the DAG. However, a vertex enumeration mechanism is
associated with the vertices in the binary forest to correctly represent the dependency
relation among updates, as described in [11].
The binary vertex forest is clustered in subtrees of height h, and thus, each subtree
contains at most 2h−1 nodes of the tree. The value h is selected to maximize disk page
filling. The selective refinement algorithm keeps in memory the set of subtrees that
store the vertices belonging to the extracted mesh, and keeps in cache their parents
and children also. If prefetched subtrees exceed cache size, the first prefetched page,
not used by the extracted mesh, is removed from the cache. Figure 3.6 shows a simple
binary vertex forest clustered in subtrees of height 2.
Pajarola in [36] proposes a compact representation for multiresolution models
built through half-edge collapse, that is, by contracting an edge e = (v 1 , v 2 ) to one of
its extreme vertices, let us say v 1 . The multiresolution model encodes a binary forest
of half-edge collapses. This forest is obtained from the forest of binary vertices by