A modified longest side bisection triangulation

Fast and efficient exploration of large terrains in a vir-tual reality manner requires different levels of detail to speedup processing of terrain parts in background. Thus, the triangulation refinement problem has become an impor-tant issue in processing terrain data. The longest side bisection of triangles is one possible way to subdivide a triangle in a couple of subtriangles. In the larger context of triangulations, this subdivision can be seen as an approach of the triangulation refinement prob-lem. This particular triangulation refinement yields a strong hierarchical triangulation, which itself is an approach of a multiresolution model for terrain surfaces. In its pure form, the longest side bisection of a triangle t (assume is a smallest angle in t) and its descendants only produces triangles whose smallest angles are always greater or equal to In this paper we show that with a small modification, the lower bound on the smallest angles can be increased to , without increasing the total number of subtriangles produced in two consecutive refinement steps. Even the new vertices inserted in the triangulation are exactly the same. 1