Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Delaunay Methods for Approximating Geometric Domains

Levine, Joshua Aaron

Abstract Details

2009, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.

The Delaunay triangulation is used extensively for representing geometric domains. Since its definition in 1934, researchers have applied it and its dual structure, the Voronoi diagram, to algorithms for surface reconstruction, mesh generation, simplification, and feature computation. Its universality can be explained by the mathematical properties it naturally optimizes, the provable guarantees it lends to algorithm analysis, and the design simplicity it provides for algorithms.

We consider the use of the Delaunay triangulation to approximate three different domains. We begin by developing a technique for simplifying vector field datasets using Delaunay triangulations. Piecewise-linear interpolation over Delaunay triangulations gives good approximations for scalar fields, motivating our approach on vector-valued data. We remove vertices from the Delaunay triangulation using a local error metric which is biased to preserve critical points of the field and to prevent topological changes during simplification. Experimental results show the effectiveness of this technique on both two and three dimensional datasets.

We next present an algorithm, DelIso, for building Delaunay meshes to approximate smooth surfaces defined by the isosurface of a volume datasets. DelIso employs a two stage algorithm which discards the need to maintain the full 3D Delaunay triangulation in the second stage. Implementation results have shown that by using this optimization we can obtain a 2-3 times speedup over its one stage counterpart. The resulting meshes are different from those produced by more common isosurfacing techniques (e.g. Marching Cubes) in that they are well graded and their topology is provably correct.

The third domain we investigate is piecewise smooth complexes (PSCs). We have designed DelPSC, an algorithm to build Delaunay meshes that approximate PSCs as well as the volumes contained within them. DelPSC was designed to be easily implementable, removing the need for many of the expensive computations that previously made Delaunay meshing for PSCs impractical. Its meshing strategy employs a protection scheme for sharp features that covers them with protecting balls whose radius mimics the feature size. Unfortunately, feature size computations can be costly, so we propose a novel protection method which first places balls along each curve and then iteratively shrinks them until they maintain a set of protection properties. We guarantee that with this set of protection properties our Delaunay refinement terminates and that by reducing a single scale parameter, the correct topology is achieved as well.

The approach used in DelPSC allows for meshing a wide variety of objects such as non-smooth CAD parts and non-manifold objects. We found with DelIso that Delaunay meshing for smooth surfaces could be adopted to mesh isosurfaces of volume datasets. Similarly, the strategy for Delaunay meshing of PSCs can be used to build meshes of the interface surfaces that multi-label volume datasets define. Our final contribution discusses the application of DelPSC to this form of data, commonly produced by segmenting MRI or CT datasets. We show the effectiveness of this technique on data from a variety of medical fields and discuss the its ability to control the quality and size of the output meshes.

Tamal K. Dey, PhD (Advisor)
Yusu Wang, PhD (Committee Member)
Rephael Wenger, PhD (Committee Member)
156 p.

Recommended Citations

Citations

  • Levine, J. A. (2009). Delaunay Methods for Approximating Geometric Domains [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1253632319

    APA Style (7th edition)

  • Levine, Joshua. Delaunay Methods for Approximating Geometric Domains. 2009. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1253632319.

    MLA Style (8th edition)

  • Levine, Joshua. "Delaunay Methods for Approximating Geometric Domains." Doctoral dissertation, Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1253632319

    Chicago Manual of Style (17th edition)