Reliable Implicit Surface Polygonization using Visibility Mapping

Abstract

We present a new algorithm to compute a topologically and geometrically accurate triangulation of an implicit surface. Our approach uses spatial subdivision techniques to decompose a manifold implicit surface into star-shaped patches and computes a visibilty map for each patch. Based on these maps, we compute a homeomorphic and watertight triangulation as well as a parameterization of the implicit surface. Our algorithm is general and makes no assumption about the smoothness of the implicit surface. It can be easily implemented using linear programming, interval arithmetic, and ray shooting techniques. We highlight its application to many complex implicit models and boundary evaluation of CSG primitives.