3 Out-of-core Multiresolution Terrain Modeling
57
ancestors of u are visited recursively if they have not been visited before. These
criteria simulate the strategies used in a selective refinement algorithm.
We have also defined and implemented two spatial grouping strategies. The first
strategy is based on the R*-tree [1], while the second strategy is based on a Point
Region k-d (PR k-d) tree for partitioning in space combined with a PK-tree [44] as a
grouping mechanism.
Finally, we have designed and implemented a class of strategies that combines
space grouping with DAG traversals (according to depth). At a lower resolution, we
are interested in having clusters that span the whole domain, while, as the resolution
increases, we are looking for clusters associated with finer space subdivisions. In
order to achieve this goal, we have developed techniques that interleave the effect of
a sorting rule and a space partitioning rule similar to a PR k-d tree. A description of
such techniques can be found in [6].
In all our experiments, the GrB outperforms the other clustering techniques. It
is interesting to note that even with a small cache (about 1% the size of the whole
model), a clustering technique based on GrB exhibits a very limited overhead, compared to loading the whole model just once in main memory.
3.5.2 Methods Based on Domain Partitioning
In [20], Hoppe describes an out-of-core multiresolution model generated through
edge collapse, called a progressive mesh (PM) quadtree, which is built through
the simplification method described in Sect. 3.3. The model works on gridded data
(DEM). The input grid is triangulated and then partitioned into square blocks in such
a way that the content of each block fits in the main memory. Simplification is performed bottom-up, and a quadtree is built where every quadrant contains a simplified
representation of the terrain represented by its four children. The resulting data structure is a sort of pyramid, where each block contains a sequence of vertex splits, that
inverts the sequence of edge collapses that produced the mesh associated with that
block. When selective refinement is performed, only the blocks of the quadtree that
are interested in the query are transferred to the main memory. Also this model was
designed specifically for visualization.
In [4], Cignoni et al. propose an out-of-core multiresolution model based on the
decomposition of the domain into a nested triangle mesh described as a triangle bintree. Each triangle in the bintree, which we call a macrotriangle, contains an irregular
mesh, formed by a relatively large number of triangles (typically between 256 and 8k
triangles). Leaves of the triangle bintree are associated with portions of the mesh at
full resolution, while internal nodes are associated with simplified meshes. This multiresolution representation is created during a fine-to-coarse simplification process,
based on Hoppe’s method [21] and adopted in order to keep boundary coherence
among adjacent macrotriangles. The meshes associated with the macrotriangles are
carefully created during the simplification process, so that, when assembled together,
they form a conforming triangle mesh. As in Hoppe’s approach, this multiresolution
model is targeted at out-of-core terrain visualization. To enhance rendering performances, each mesh associated with a macrotriangle is organized into triangle strips.
57
ancestors of u are visited recursively if they have not been visited before. These
criteria simulate the strategies used in a selective refinement algorithm.
We have also defined and implemented two spatial grouping strategies. The first
strategy is based on the R*-tree [1], while the second strategy is based on a Point
Region k-d (PR k-d) tree for partitioning in space combined with a PK-tree [44] as a
grouping mechanism.
Finally, we have designed and implemented a class of strategies that combines
space grouping with DAG traversals (according to depth). At a lower resolution, we
are interested in having clusters that span the whole domain, while, as the resolution
increases, we are looking for clusters associated with finer space subdivisions. In
order to achieve this goal, we have developed techniques that interleave the effect of
a sorting rule and a space partitioning rule similar to a PR k-d tree. A description of
such techniques can be found in [6].
In all our experiments, the GrB outperforms the other clustering techniques. It
is interesting to note that even with a small cache (about 1% the size of the whole
model), a clustering technique based on GrB exhibits a very limited overhead, compared to loading the whole model just once in main memory.
3.5.2 Methods Based on Domain Partitioning
In [20], Hoppe describes an out-of-core multiresolution model generated through
edge collapse, called a progressive mesh (PM) quadtree, which is built through
the simplification method described in Sect. 3.3. The model works on gridded data
(DEM). The input grid is triangulated and then partitioned into square blocks in such
a way that the content of each block fits in the main memory. Simplification is performed bottom-up, and a quadtree is built where every quadrant contains a simplified
representation of the terrain represented by its four children. The resulting data structure is a sort of pyramid, where each block contains a sequence of vertex splits, that
inverts the sequence of edge collapses that produced the mesh associated with that
block. When selective refinement is performed, only the blocks of the quadtree that
are interested in the query are transferred to the main memory. Also this model was
designed specifically for visualization.
In [4], Cignoni et al. propose an out-of-core multiresolution model based on the
decomposition of the domain into a nested triangle mesh described as a triangle bintree. Each triangle in the bintree, which we call a macrotriangle, contains an irregular
mesh, formed by a relatively large number of triangles (typically between 256 and 8k
triangles). Leaves of the triangle bintree are associated with portions of the mesh at
full resolution, while internal nodes are associated with simplified meshes. This multiresolution representation is created during a fine-to-coarse simplification process,
based on Hoppe’s method [21] and adopted in order to keep boundary coherence
among adjacent macrotriangles. The meshes associated with the macrotriangles are
carefully created during the simplification process, so that, when assembled together,
they form a conforming triangle mesh. As in Hoppe’s approach, this multiresolution
model is targeted at out-of-core terrain visualization. To enhance rendering performances, each mesh associated with a macrotriangle is organized into triangle strips.