48
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
Magillo and Bertocci [33] present a method specific to a TIN. It subdivides the
TIN into patches that are small enough to be simplified individually in-core. They
take a different approach to preserve interpatch boundaries. The skeleton of edges
that defines the boundary of the patches in the decomposition is simplified first
through an algorithm for line simplification based on vertex removal. This maintains
the consistency of patch boundaries through different levels of detail. The history of
simplification of each chain of edges forming a boundary line is maintained. Then the
interior of each patch is also simplified independently through vertex removal. Removal of internal and boundary vertices can be interleaved to obtain a more uniform
simplification process.
Cignoni et al. [3] propose a simplification method for triangle meshes in 3D space
based on a hierarchical partition of the embedding space through the use of octrees.
Octree subdivision stops when the set of triangles associated with a leaf fits in a disk
page. The portion of the triangle mesh contained in each octree leaf is independently
simplified through iterative edge collapse. Once the leaves are simplified, they can
be merged and simplified further. The problem caused by avoiding performing edge
collapses on the boundary of the patches, as in [19], is overcome. Vertices and edges
of the mesh do not lie on the faces of quadtree blocks, while only edges that cross the
boundary between adjacent blocks may exist. Such interblock edges cannot be collapsed while independently simplifying the patches, but they can be either stretched
or identified in pairs because of the other edge collapses occurring inside the patches.
Thus, the independent simplification of the interior of one patch is interleaved with
some simplification on the strip of triangles joining it to its adjacent patches, thus
preserving interpatch consistency. This method can be easily adapted to the special
case of terrain data by using quadtrees instead of octrees to partition the domain of
the TIN. Note that the input data need not be regularly distributed. In general, the
vertices of the mesh will not lie on the boundary of quadrants of the quadtree.
3.3.3 Streaming Algorithms
The philosophy underlying streaming techniques is that a strictly sequential processing order is followed, where each datum is loaded only once to main memory such
that the result is written to secondary memory as soon as possible.
Isenburg et al. [23] present a simplification technique for triangle meshes that
takes a sequential indexed representation of the mesh as input in which vertices
and triangles are suitably interleaved. This representation may also be built from
more common mesh data structures, such as triangle soups or indexed data structures, through preprocessing techniques also based on streaming [22]. The algorithm
streams very large meshes through main memory, but at each step, only a small portion of the mesh is kept in-core. Mesh access is restricted to a fixed traversal order,
but full connectivity and geometry information is available for the active elements
of the traversal. The simplification step is performed only on the portion of the mesh
loaded in main memory.
Note that streaming algorithms, as those based on clustering, are not progressive
and cannot be used to build multiresolution models.
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
Magillo and Bertocci [33] present a method specific to a TIN. It subdivides the
TIN into patches that are small enough to be simplified individually in-core. They
take a different approach to preserve interpatch boundaries. The skeleton of edges
that defines the boundary of the patches in the decomposition is simplified first
through an algorithm for line simplification based on vertex removal. This maintains
the consistency of patch boundaries through different levels of detail. The history of
simplification of each chain of edges forming a boundary line is maintained. Then the
interior of each patch is also simplified independently through vertex removal. Removal of internal and boundary vertices can be interleaved to obtain a more uniform
simplification process.
Cignoni et al. [3] propose a simplification method for triangle meshes in 3D space
based on a hierarchical partition of the embedding space through the use of octrees.
Octree subdivision stops when the set of triangles associated with a leaf fits in a disk
page. The portion of the triangle mesh contained in each octree leaf is independently
simplified through iterative edge collapse. Once the leaves are simplified, they can
be merged and simplified further. The problem caused by avoiding performing edge
collapses on the boundary of the patches, as in [19], is overcome. Vertices and edges
of the mesh do not lie on the faces of quadtree blocks, while only edges that cross the
boundary between adjacent blocks may exist. Such interblock edges cannot be collapsed while independently simplifying the patches, but they can be either stretched
or identified in pairs because of the other edge collapses occurring inside the patches.
Thus, the independent simplification of the interior of one patch is interleaved with
some simplification on the strip of triangles joining it to its adjacent patches, thus
preserving interpatch consistency. This method can be easily adapted to the special
case of terrain data by using quadtrees instead of octrees to partition the domain of
the TIN. Note that the input data need not be regularly distributed. In general, the
vertices of the mesh will not lie on the boundary of quadrants of the quadtree.
3.3.3 Streaming Algorithms
The philosophy underlying streaming techniques is that a strictly sequential processing order is followed, where each datum is loaded only once to main memory such
that the result is written to secondary memory as soon as possible.
Isenburg et al. [23] present a simplification technique for triangle meshes that
takes a sequential indexed representation of the mesh as input in which vertices
and triangles are suitably interleaved. This representation may also be built from
more common mesh data structures, such as triangle soups or indexed data structures, through preprocessing techniques also based on streaming [22]. The algorithm
streams very large meshes through main memory, but at each step, only a small portion of the mesh is kept in-core. Mesh access is restricted to a fixed traversal order,
but full connectivity and geometry information is available for the active elements
of the traversal. The simplification step is performed only on the portion of the mesh
loaded in main memory.
Note that streaming algorithms, as those based on clustering, are not progressive
and cannot be used to build multiresolution models.