Author's School

School of Engineering & Applied Science

Author's Department/Program

Computer Science and Engineering

Language

English (en)

Date of Award

Winter 12-1-2013

Degree Type

Thesis

Degree Name

Master of Science (MS)

Chair and Committee

Tao Ju

Abstract

In this thesis, 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 opti- mality. 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.

DOI

https://doi.org/10.7936/K7H9937S

Comments

Permanent URL: http://dx.doi.org/10.7936/K7H9937S

Share

COinS