Simplical Mesh Generation With Applications
Moore, Douglas W.
Many problems in computer graphics and in engineering analysis require for their solution the construction of a mesh of simple polytopal elements that approximately fill the interior of an object or cover its boundary. The simplest polytopes are the simplexes, and simplicial meshes have particular advantages when solving interpolation problems, graphically rendering objects approximated by boundary meshes, and in many other applications. Boxes are often used where simplexes should be considered because the properties of boxes are more familiar. This dissertation develops several techniques that aid in the construction of simplicial meshes in any dimension. It presents the essential combinatorial and geometric properties of simplexes, and presents simple techniques for decomposing simplexes into smaller simple objects. It describes the simplicial quadtree, a useful representation in the construction of simplicial meshes, and presents a technique for converting an arbitrary simplicial quadtree into a balanced quadtree, then into a triangulation. It also describes mesh displacement, a technique for improving the quality of a boundary triangulation while reducing its size. Several degenerate behaviors can arise from mesh displacement, and the dissertation discusses methods for detecting and compensating for these degeneracies. Simplicial mesh generation techniques can be applied to many kinds of problems. To illustrate this, the final chapters describe the implementation of a polygonalizer for algebraic sets and a system that applies the operations of constructive solid geometry to sets defined algebraically.
computer science; technical report
Previously Published As