
The Cutting Pattern Problem for Tetrahedral MeshGeneration
Yin, Xiaotian, Wei Han, Xianfeng Gu, and ShingTung Yau
20th International Meshing Roundtable, SpringerVerlag, pp.217236, October 2326 2011

IMR PROCEEDINGS

20th International Meshing Roundtable
Paris, France
October 2326, 2011
Mathematics Department, Harvard University, MA, U.S.A., Computer Science Department, Stony Brook University,
NY, U.S.A.
Email:{xyin,weihan,yau}@math.harvard.edu, gu@cs.sunysb.edu
Summary
In this work we study the following cutting pattern problem. Given a triangulated surface
(i.e. a twodimensional simplicial complex), assign each triangle with a triple of ±1, one integer per
edge, such that the assignment is both complete (i.e. every triangle has integers of both signs) and
consistent (i.e. every edge shared by two triangles has opposite signs in these triangles). We show
that this problem is the major challenge in converting a volumetric mesh consisting of prisms into a
mesh consisting of tetrahedra, where each prism is cut into three tetrahedra. In this paper we provide
a complete solution to this problem for topological disks under various boundary conditions ranging
from very restricted one to the most flexible one. For each type of boundary conditions, we provide
efficient algorithms to compute valid assignments if there is any, or report the obstructions otherwise.
For all the proposed algorithms, the convergence is validated and the complexity is analyzed.
Download Full Paper (PDF Format)
Contact author(s) or publisher for availability and copyright information on above referenced article
