Greedy Cuts: An advancing front terrain triangulation algorithm

Abstract

We apply an advancing front technique to the problem of simplification of dense digitized terrain models. While most simplification algorithms have been based on either incremental refinement or decimation techniques, our Greedy-Cuts algorithm uses a simple triangulation-growth procedure. We improve on our earlier advancing-front technique, which was not able to backtrack in its triangulation decisions, resulting in triangulations that may have low quality. The new algorithm we propose overcomes this shortcoming by maintaining two "fronts", a real front and a virtual front, that bound between them a region of the terrain that has only a tentative triangulation. By allowing simple local operations (edge collapses and edge flips) in the tentative triangulation, we are able to avoid many of the artifacts of the earlier advancing-front technique, while not significantly affecting memory usage. GcTin, our terrain triangulation tool, is publicly available for research purposes. The original version of GcTin has been in use at several commercial and non-commercial sites since 1995. The new algorithms described here are integrated in the latest release and result in substantially improved triangulations.