An Algorithm for Triangulating Multiple 3D Polygons

Computer Graphics Forum 32(5), Proceedings of Eurographics Symposium on Geometry Processing (SGP) 2013
Ming Zou1, Tao Ju1, Nathan Carr2
1Washington University in St. Louis, 2Adobe

Examples of triangulations of multiple polygons, minimizing the total dihedral angles.
Triangulations computed by our algorithm on sketched curves and hole boundaries with islands (Left).
Filling a model with numerous holes (Right).


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.


+ Paper
[PDF 2.3M]
+ Code
[EXE 290K]   [SRC 1.4M]   (Latest Version: 1.1.0 Updated: Feb 27, 2014)
+ Data
[ZIP 6.8M]
+ Slides
[KEYNOTE 37M]   [PDF 10M]


The source code is currently distributed under the license MPL2, which is a simple weak copyleft license.
Please check the MPL2 FAQ for more information, and contact me if you have any question.

Release Notes

Our source code as well as an executable file are provided for research use.
The code is written in C++ and tested on 64-bit Windows 7.

Version 1.1.0:
+ Fixed a bug on normal handling.
+ Fixed bugs on triangulating with all possible triples of vertices.
+ Included the tetgen head file and library in the source code.

Version 1.0.0:
+ The first version. Use command line to run. A README is included.


This work is supported in part by NSF grant IIS-0846072 and a gift from Adobe.


title={An algorithm for triangulating multiple 3D polygons},
author={Zou, Ming and Ju, Tao and Carr, Nathan},
booktitle={Computer graphics forum},
organization={Wiley Online Library}