The 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 O(n log Δ + m), where n and m are the size of the input and output, and Δ is the ratio of largest-to-smallest distances in the input geometry. The principle result of this thesis is to extend this result to the general case of piecewise linear complexes with creases.

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 O(n log Δ + c), where c is the description complexity of the collar system. Additionally, I give a procedure for implicitly constructing a collar system on the fly, so that a complete meshing algorithm for a PLC can be run in one pass with total work in O(n log Δ + m) and space usage in O(m).

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
School of Computer Science

This page maintained by reports@cs.cmu.edu