Sampling and Meshing a Surface with Guaranteed Topology and Geometry

This paper presents an algorithm for sampling and triangulating a generic C²-smooth surface Σ⊂ R³ that is input with an implicit equation. The output triangulation is guaranteed to be homeomorphic to Σ. We also prove that the triangulation has well-shaped triangles, large dihedral angles, and a small size. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely, computations of the intersection points of a line and Σ, computations of the critical points in a given direction, and computations of certain silhouette points.