Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Thesis.pdf (9.75 MB)

ETD Abstract Container

Abstract Header

Scalable Algorithms for Delaunay Mesh Generation

Slatton, Andrew G
http://rave.ohiolink.edu/etdc/view?acc_num=osu1406758013

Abstract Details

2014, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Delaunay refinement is a useful tool for sampling and meshing. Pioneered by Ruppert and Chew for piecewise-linear complexes in R^2, Delaunay refinement has been extended to myriad classes of shapes including smooth 1- and 2-manifolds, volumes bounded by smooth 2-manifolds, and piecewise-smooth complexes. Delaunay refinement algorithms often carry certain guarantees regarding the geometric and topological closeness of output to input, as well as guarantees of the quality of mesh elements, making meshes generated via Delaunay refinement a natural choice for simulation and rendering. A major shortcoming of Delaunay refinement is its scalability: as the size of the mesh grows, the data structures necessary to carry out Delaunay refinement efficiently (such as the Delaunay triangulation and its dual, the Voronoi diagram) also grow, and this incurs memory thrashing when generating dense meshes. In this dissertation, we improve Delaunay refinement in two main capacities: (1) we improve the memory scalability of Delaunay refinement to allow for the generation of truly huge meshes, and (2) we improve the time scalability of Delaunay refinement by developing a novel parallel algorithm. To address the issue of memory scalability, we developed a localized refinement method embodying a divide-and-conquer paradigm for meshing smooth surfaces. The algorithm divides the sampling of the input domain via octree and meshes one node of the octree at a time, thus reducing memory requirements. Our theoretical results show that the algorithm terminates, and that the output is not only consistent, but also is geometrically close to the input and is a subcomplex of the Delaunay triangulation of the sampling restricted to the input surface. Our initial work nicely addresses the aforementioned shortcoming of Delaunay refinement, but only for smooth 2-manifolds. In later work, we extended this technique to another important input class: volumes bounded by smooth 2-manifolds. It is not immediately clear how the localization framework can be adapted to prevent arbitrarily small inter-point distances in our sample for this class of inputs. We again prove termination, consistency, geometric and topological closeness of output to input, and that the output is a subcomplex of the sampling restricted to the input. Later, we extended localized Delaunay refinement to piecewise-smooth complexes, a vast class of surfaces often encountered in engineering applications. It was initially difficult to see whether this could be accomplished, due to the use of the weighted Delaunay triangulation and the use of complicated methods to handle the refinement along ridges joining smooth surface patches in previous work on piecewise smooth complexes. The theoretical results we obtain here are similar to those seen in our previous works on localized refinement, though the details of the proofs are vastly different. Most recently, we have developed a parallel algorithm for meshing smooth surfaces based on this localized refinement technique. The change from sequential to parallel required modifications to various parts of the algorithm and a method for finding sets of octree nodes that could be processed in parallel. We again prove termination and geometric and topological closeness of output to input.
Tamal Dey (Advisor)
Yusu Wang (Committee Member)
Rephael Wenger (Committee Member)
110 p.
Computer Science
Mesh generation; Delaunay; Parallel algorithms; Scalable algorithms

Recommended Citations

Citations

  • Slatton, A. G. (2014). Scalable Algorithms for Delaunay Mesh Generation [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1406758013

    APA Style (7th edition)

  • Slatton, Andrew. Scalable Algorithms for Delaunay Mesh Generation. 2014. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1406758013.

    MLA Style (8th edition)

  • Slatton, Andrew. "Scalable Algorithms for Delaunay Mesh Generation." Doctoral dissertation, Ohio State University, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=osu1406758013

    Chicago Manual of Style (17th edition)

osu1406758013
666
© 2014, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.