Automatic Construction of Coarse, High-Quality Tetrahedralizations that Enclose and Approximate Surfaces for Animation

Author/Creator ORCID

Date

2013-11-06

Department

Program

Citation of Original Publication

David A. Stuart, Joshua A. Levine, et.al, Automatic Construction of Coarse, High-Quality Tetrahedralizations that Enclose and Approximate Surfaces for Animation , Proceeding MIG '13 Proceedings of Motion on Games Pages 213-222 Dublin 2, Ireland, November 06 - 08, 2013, DOI: 10.1145/2522628.2522648

Rights

This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.

Abstract

Embedding high-resolution surface geometry in coarse control meshes is a standard approach to achieving high-quality computer animation at low computational expense. In this paper we present an effective, automatic method for generating such control meshes. The resulting high-quality, tetrahedral meshes enclose and approximate an input surface mesh, avoiding extrapolation artifacts and ensuring that the resulting coarse volumetric meshes are adequate collision proxies. Our approach comprises three steps: we begin with a tetrahedral mesh built from the body-centered cubic lattice that tessellates the bounding box of the input surface; we then perform a sculpting phase that carefully removes elements from the lattice; and finally a variational vertex adjustment phase iteratively adjusts vertex positions to more closely approximate the surface geometry. Our approach provides explicit trade-offs between mesh quality, resolution, and surface approximation. Our experiments demonstrate the technique can be used to build high-quality meshes appropriate for simulations within games.