3 Out-of-core Multiresolution Terrain Modeling
47
computation. Therefore, for terrains, it is sufficient to partition the domain of the
TIN with a 2D grid subdividing its domain into buckets.
Methods based on clustering are fast, but they are not progressive. The resolution
of the simplified mesh is a priori determined by the resolution of the regular grid of
buckets and no intermediate representations are produced during simplification. For
this reason, the algorithms in this class are not suitable to support the construction of
multiresolution models that will be discussed in Sect. 3.5.
3.3.2 Algorithms Based on Space Partitioning
The approach to simplification based on space partitioning consists of subdividing
the mesh into patches, each of which can fit into main memory, and then simplifying
each patch with standard techniques. Attention must be paid to patch boundaries to
maintain the topological consistency of the simplified mesh.
The method proposed by Hoppe [20] starts from a regular grid and partitions the
domain by using a PR quadtree subdivision based on the data points. The quadtree
is built in such a way that data points in each leaf node fit in main memory. Simplified TINs are built bottom-up as described below. A full-resolution TIN is built by
connecting the vertices of the input grid inside each leaf, and this is simplified iteratively by applying edge collapse. Only internal edges can be collapsed, while edges
on the boundary of each patch are left unchanged. Once the meshes corresponding to
the four siblings of a node A in the quadtree are reduced to a manageable size, they
are merged into a mesh that will be associated with node A, and the simplification
process is repeated recursively. The fact that edges on the boundaries of the quadtree
blocks are frozen leads to a somehow unbalanced simplification, because data along
the boundaries between adjacent blocks are maintained at full resolution even in the
upper levels of the quadtree.
This technique was later generalized by Prince [37] to arbitrary TINs, whose
vertices do not necessarily lie on a regular grid. While conceptually simple, the time
and space overhead of partitioning the TIN and of later stitching the various pieces
together leads to an expensive in-core simplification process, making such method
less suitable for simplifying very large meshes.
El-Sana and Chiang [12] propose an algorithm that works on irregularly distributed data. They partition the mesh at full resolution into patches, where each
patch is bounded by chains of edges of the triangle mesh. Patches are sized in such
a way that a few of them can be loaded in main memory if necessary. Simplification
of a single patch is performed by iteratively collapsing the shortest internal edge of
the corresponding triangle mesh. Simplification of a patch is interrupted when its
shortest edge lies on its boundary to preserve matching between adjacent patches.
Once all patches have been simplified independently, the shortest edge of the mesh
lies on the common boundary between two patches. Two such patches are merged
in main memory and edge collapse is restarted. In this way, the result of simplification is consistent with that obtained in-core by collapsing at each step the shortest
edge of the mesh. This method has been used to build a multiresolution model as
described in Sect. 3.5.
47
computation. Therefore, for terrains, it is sufficient to partition the domain of the
TIN with a 2D grid subdividing its domain into buckets.
Methods based on clustering are fast, but they are not progressive. The resolution
of the simplified mesh is a priori determined by the resolution of the regular grid of
buckets and no intermediate representations are produced during simplification. For
this reason, the algorithms in this class are not suitable to support the construction of
multiresolution models that will be discussed in Sect. 3.5.
3.3.2 Algorithms Based on Space Partitioning
The approach to simplification based on space partitioning consists of subdividing
the mesh into patches, each of which can fit into main memory, and then simplifying
each patch with standard techniques. Attention must be paid to patch boundaries to
maintain the topological consistency of the simplified mesh.
The method proposed by Hoppe [20] starts from a regular grid and partitions the
domain by using a PR quadtree subdivision based on the data points. The quadtree
is built in such a way that data points in each leaf node fit in main memory. Simplified TINs are built bottom-up as described below. A full-resolution TIN is built by
connecting the vertices of the input grid inside each leaf, and this is simplified iteratively by applying edge collapse. Only internal edges can be collapsed, while edges
on the boundary of each patch are left unchanged. Once the meshes corresponding to
the four siblings of a node A in the quadtree are reduced to a manageable size, they
are merged into a mesh that will be associated with node A, and the simplification
process is repeated recursively. The fact that edges on the boundaries of the quadtree
blocks are frozen leads to a somehow unbalanced simplification, because data along
the boundaries between adjacent blocks are maintained at full resolution even in the
upper levels of the quadtree.
This technique was later generalized by Prince [37] to arbitrary TINs, whose
vertices do not necessarily lie on a regular grid. While conceptually simple, the time
and space overhead of partitioning the TIN and of later stitching the various pieces
together leads to an expensive in-core simplification process, making such method
less suitable for simplifying very large meshes.
El-Sana and Chiang [12] propose an algorithm that works on irregularly distributed data. They partition the mesh at full resolution into patches, where each
patch is bounded by chains of edges of the triangle mesh. Patches are sized in such
a way that a few of them can be loaded in main memory if necessary. Simplification
of a single patch is performed by iteratively collapsing the shortest internal edge of
the corresponding triangle mesh. Simplification of a patch is interrupted when its
shortest edge lies on its boundary to preserve matching between adjacent patches.
Once all patches have been simplified independently, the shortest edge of the mesh
lies on the common boundary between two patches. Two such patches are merged
in main memory and edge collapse is restarted. In this way, the result of simplification is consistent with that obtained in-core by collapsing at each step the shortest
edge of the mesh. This method has been used to build a multiresolution model as
described in Sect. 3.5.