A Simple Recursive Tessellator for Adaptive Surface Triangulation
Adrian J. Chung, Anthony J. Field · Journal of Graphics Tools · 2000
Sometimes there is a need to create a triangular mesh approximation of a parametric surface. If the parameterization is nonuniform (compressed in some areas, stretchy in others), a uniform grid in parameter space becomes distorted and provides a bad approximation. We describe how to create an adaptive triangulation of such a surface, provided the user of the algorithm provides a routine split_edge() which indicates whether a particular edge is close enough to the surface or requires splitting, and optionally a routine flat_enough() which t ells whether a triangle whose edges appear adequate is indeed flat enough, or requires further subdivision. Our contribution is a simple algorithm for guaranteeing that the topology of the resulting mesh is well formed in the sense that there ar e no cracks between triangles (i.e., T-junctions), and for ensuring that subdivision halts at a given point. There is also rudimentary support from trimmed surfaces. Source code for the algorithm is available online.