46
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
techniques have been developed mainly for simplification of triangle meshes bounding 3D objects, and can easily be adapted in order to simplify TINs that are usually
simpler to handle. Out-of-core simplification algorithms can be roughly subdivided
into the following three major classes:
• Methods based on vertex clustering
• Methods based on space partition
• Streaming techniques
In the following subsections, we review the main contributions in each class.
3.3.1 Algorithms Based on Clustering
Rossignac and Borrel [39] proposed an in-core method for the simplification of triangle meshes embedded in the three-dimensional Euclidean space. Their algorithm
subdivides the portion of 3D space on which the mesh is embedded into buckets by
using a uniform grid and collapses all vertices inside each bucket to a new vertex,
thus modifying the mesh accordingly. In [27], Lindstrom proposes an out-of-core
version of the above method that has a lower time and space complexity, and improves mesh quality. The input mesh is kept in secondary memory, while only the
portion of the mesh within a single bucket is loaded in main memory. However, the
whole output mesh is assumed to fit in main memory. In [28], Lindstrom and Silva
propose further improvements over the method in [27] that increase the quality of approximation further and reduce memory requirements. The new algorithm removes
the constraint of having enough memory to hold the simplified mesh, thus supporting
simplification of really huge models. The work in [28] also improves the quality of
the mesh, preserving surface boundaries and optimizing the position of the representative vertex of a grid cell.
Another extension of Rossignac and Borrel’s approach is the algorithm by Shaffer and Garland [42]. This algorithm makes two passes over the input mesh. During
the first pass, the mesh is analyzed and an adaptive space partitioning, based on a
BSP tree, is performed. Using this approach, a larger number of samples can be allocated to more detailed portions of the surface. However, their algorithm requires
more RAM than the algorithm by Lindstrom to maintain a BSP tree and additional
information in-core.
Garland and Shaffer in [17] present a technique that combines vertex clustering
and iterative edge collapse. This approach works in two steps: the first step performs
a uniform vertex clustering, as in the methods described above. During the second
step, edge collapse operations are performed iteratively to simplify the mesh further,
according to an error-driven criterion. The assumption is that the mesh obtained after
the first step is small enough to perform the second step in main memory.
Note that all these methods have been developed for simplifying triangle meshes
representing objects in 3D space. Adaptation to terrain data is straightforward; it
is sufficient to simplify the triangle mesh subdividing the domain that describes
the structure of the TIN, while elevation values are used just to perform error
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
techniques have been developed mainly for simplification of triangle meshes bounding 3D objects, and can easily be adapted in order to simplify TINs that are usually
simpler to handle. Out-of-core simplification algorithms can be roughly subdivided
into the following three major classes:
• Methods based on vertex clustering
• Methods based on space partition
• Streaming techniques
In the following subsections, we review the main contributions in each class.
3.3.1 Algorithms Based on Clustering
Rossignac and Borrel [39] proposed an in-core method for the simplification of triangle meshes embedded in the three-dimensional Euclidean space. Their algorithm
subdivides the portion of 3D space on which the mesh is embedded into buckets by
using a uniform grid and collapses all vertices inside each bucket to a new vertex,
thus modifying the mesh accordingly. In [27], Lindstrom proposes an out-of-core
version of the above method that has a lower time and space complexity, and improves mesh quality. The input mesh is kept in secondary memory, while only the
portion of the mesh within a single bucket is loaded in main memory. However, the
whole output mesh is assumed to fit in main memory. In [28], Lindstrom and Silva
propose further improvements over the method in [27] that increase the quality of approximation further and reduce memory requirements. The new algorithm removes
the constraint of having enough memory to hold the simplified mesh, thus supporting
simplification of really huge models. The work in [28] also improves the quality of
the mesh, preserving surface boundaries and optimizing the position of the representative vertex of a grid cell.
Another extension of Rossignac and Borrel’s approach is the algorithm by Shaffer and Garland [42]. This algorithm makes two passes over the input mesh. During
the first pass, the mesh is analyzed and an adaptive space partitioning, based on a
BSP tree, is performed. Using this approach, a larger number of samples can be allocated to more detailed portions of the surface. However, their algorithm requires
more RAM than the algorithm by Lindstrom to maintain a BSP tree and additional
information in-core.
Garland and Shaffer in [17] present a technique that combines vertex clustering
and iterative edge collapse. This approach works in two steps: the first step performs
a uniform vertex clustering, as in the methods described above. During the second
step, edge collapse operations are performed iteratively to simplify the mesh further,
according to an error-driven criterion. The assumption is that the mesh obtained after
the first step is small enough to perform the second step in main memory.
Note that all these methods have been developed for simplifying triangle meshes
representing objects in 3D space. Adaptation to terrain data is straightforward; it
is sufficient to simplify the triangle mesh subdividing the domain that describes
the structure of the TIN, while elevation values are used just to perform error