We present an algorithm for obtaining a triangulation of multiple, non-planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non-manifold outputs for two and more input polygons without compromising optimality. For better performance on real-world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.
|Number of pages
|Published - Jul 3 2013
|11th Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, SGP 2013 - Genova, Italy
Duration: Jul 3 2013 → Jul 5 2013
|11th Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, SGP 2013
|07/3/13 → 07/5/13