An Algorithm for Triangulating Multiple 3D Polygons

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


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

Abstract

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.

Downloads

+ 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]

Licenses

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.

Acknowledgements

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

BibTeX

@article{CGF32-5:157-166:2013,
journal = {Computer Graphics Forum},
title = {{An Algorithm for Triangulating Multiple 3D Polygons}},
author = {Ming Zou and Tao Ju and Nathan Carr },
pages = {157-166},
volume= {32},
number= {5},
year = {2013},
URL = {http://diglib.eg.org/EG/CGF/volume32/issue5/v32i5pp157-166.pdf},
DOI = {10.1111/cgf.12182}
}