CMU-CS-09-156Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-09-156
Todd Phillips August 2009 Ph.D. Thesis
Keywords: Computational geometry, scientific computing, mesh
generationThe mesh generation problem is to output a set of tetrahedra that discretize an input geometry. The input is given as a piecewise linear complex (PLC), a set of points, lines, and polygons to which the output tetrahedra must conform. Additionally, a mesh generation algorithm must make guarantees on the quality and number of output tetrahedra. Downstream applications in scientific computing and visualization necessitate these guarantees on the mesh.
Recent advances have led to provably correct algorithms for a number of input
classes. Particular difficulties arise when the input contains creases,
regions where input segments or polygons meet at acute angles. When the
input is without creases, the mesh generation problem is better understood.
Algorithms for such inputs exist with near-optimal runtimes of
Correct algorithms to handle inputs with creases involve explicitly
constructing a system of specially designed collars around the creases.
These collars must be specifically sized according to the input geometry.
I give a new procedure to compute the needed collar sizes in near-optimal
Central to the analysis is the "Scaffold-Sizing Theorem", a structural result governing the number of vertices created during mesh generation. The theorem is general enough to have an added benefit of retroactively improving the analysis of almost all existing meshing algorithms. 105 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |