Phase 1: Summary
This simple architecture of multiple simplification objects executing on each vertex to
determine whether it contributes to the terrain or not was proven to work quite effectively.
Simplification objects for maintaining continuity, mountain peaks, roads, building locations, etc could easily be added. These objects could easily draw upon information from other databases for making their determinations (like where buildings are located.)
With these techniques, restrictions on acceptible vertices could be automatically (or manually) loosened for lower and lower levels of detail of the terrain.
Phase 2: Constrained Delaunay Triangulation
Phase 2 consisted of adding support for constrained Delaunay Triangulation. The algorithm no longer uses Bourke's super triangle but instead has constraint support for boundaries. The importance of adding this support is that we need to be able to guarantee that we
have kept specific edges in the final triangulation because the triangulation must meet nicely with other geometry in the scene.
Phase 3: Iterative TIN, Local Error Metric, & RMS
The simplification algorithm from phase 1 works more on a local basis, testing whether a vertex should be included or not.
This doesn't lend itself to producing triangulations exactly of a specific number of vertices, or minimal triangulations
for a given error reduction. The next phase of this project addressed these types of issues by using Garland's Local
error metric (distance between the actual terrain height and the real value in the heightmap) to determine which vertices
will eliminate the most error first, such that the generation of the TIN can be stopped when the error reaches a given threshold.
These topics and this phase of the project were a part of the iTIN Project which can be read about by
clicking here.
References:
- Garland and Heckbert, Fast Polygonal Approximation of Terrains and Height Fields, CMU-CS-95-181
glenn@raudins.com
|