Hierarchical triangulation using cartographic coherence

Triangulated Irregular Networks (TINs) approximate surfaces for many applications. For those that require different resolutions, TINs may be stored in a hierarchical structure. In the past, techniques have been emphasized where a coarse triangulation is refined by focusing on plane geometry using very little of the surface data. For example a new point is introduced where the surface deviates farthest from the plane of the triangle, and the triangle is subdivided into three new ones. Variants of Delaunay triangulations have also been used. We propose a technique where we take into account that deviations of a terrain surface from planarity do not occur at isolated points but they occur coherently along ridges, valleys, peaks and other features. If, for example, a ridge cuts across a triangle, that triangle is divided by a line along the ridge and the remaining quadrilateral gets split into the two most nearly equilateral triangles. In this way the number of very thin triangles (slivers) is significantly reduced. Such triangles produce undesirable effects in animation. In addition the number of levels of the TIN tree is reduced which speeds up searching within the data structure. Our tests on digital elevation data have confirmed the above theoretical expectations. Results show that average "sliveriness" with our new method is between 1 5 and 1 10 that of triangulations produced with DeFloriani's first method. The resulting number of levels in the hierarchy is about one third and although there is an increase in the number of descendants at each level, the total number of triangles is also lower.