Practical Delaunay triangulation algorithms for surface reconstruction and related problems

The Delaunay triangulation is one of the fundamental problems in computational geometry, dual to the well-known Voronoi diagram. It has numerous applications in various disciplines such as computer graphics, computer vision, and robotics. This thesis deals with a number of interrelated questions arising in modeling shapes by computing Delaunay triangulations. We give algorithms for surface reconstruction, computing Delaunay triangulations given surfaces, and computing Delaunay triangulations in general. Given a set of samples from a surface, the surface reconstruction problem is to construct a piecewise linear approximation of the original surface. We give two surface reconstruction algorithms with guarantees of both geometric and topological correctness using the 3D Delaunay triangulation of the input samples. The first algorithm selects a set of Delaunay triangles using a simple geometric test and extracts a manifold from it. It is the first surface reconstruction algorithm with topological guarantee of correctness. The second algorithm improves the robustness using the weighted Voronoi diagrams called power diagram. When the surface on which the samples lie are known, we can use the connectivity of the surface to speed up the Delaunay triangulation. We give an O(n log∗ n) expected time algorithm to compute the 3D Delaunay triangulation given the surface on which the samples lie, under some realistic assumptions. It improves upon O(n log n) expected time usual randomized incremental algorithm in this case. The algorithm can be useful for mesh generation and medial axis construction. The randomized incremental algorithm for Delaunay triangulation is theoretically optimal in expected time but suffers from serious thrashing because of its random memory access pattern when the data structure gets too large to fit in memory. We propose a new insertion order called biased randomized insertion order (BRIO) which removes enough randomness to significantly improve performance, but leaves enough randomness so that the algorithm remains theoretically optimal. We show by experiments that the size of input data we can compute in a given machine increases dramatically using BRIO instead of the total random order.