Robust Incremental Polygon Triangulation for Fast Surface Rendering
Subodh Kumar · Digital Library (University of West Bohemia) · 2000
This paper presents a simple, robust and practical, yet fast algorithm for triangulation of trimmed Bzier surfaces. Points on the surface are input to our algorithm by a sampling scheme. A set of polygons (more generically, a planar straight-line graph, or PSLG) is formed from these samples, which are then triangulated. We also show how to update the triangulation when the samples, and hence the polygons, are updated. The output of the algorithm is a set of triangle strips. The algorithm avoids long and thin triangles. In addition, it also detects if the sampling of the trimming curve forms any non-simple polygons and corrects the triangulation by adding more samples. We report an implementation of the algorithm and its performance on extensive simulation.