Hierarchical triangulation using terrain features

A hierarchical triangulation built from a digital elevation model in grid form is described. The authors present an algorithm that produces a hierarchy of triangulations in which each level of the hierarchy corresponds to a guaranteed level of accuracy. The number of very thin triangles (slivers) is significantly reduced. Such triangles produced undesirable effects in animation. In addition the number of levels of the triangulated irregular network (TIN) tree is reduced. This speeds up searching within the data structure. Tests on data with digital elevation input have confirmed the theoretical expectations. On eight such sets the average sliveriness with the method was between 1/5 and 1/10 of old triangulations and number of levels was about one third. There was an increase in the number of descendants at each level, but the total number of triangles was also lower