Localized Delaunay Refinement for Sampling and Meshing

Simple item page
dc.contributor.authorTamal K. Deyen_US
dc.contributor.authorJoshua A. Levineen_US
dc.contributor.authorAndrew Slattonen_US
dc.date.accessioned2015-02-23T17:15:43Z
dc.date.available2015-02-23T17:15:43Z
dc.date.issued2010en_US
dc.description.abstractThe technique of Delaunay renement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the renement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.en_US
dc.description.number5en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume29en_US
dc.identifier.doi10.1111/j.1467-8659.2010.01781.xen_US
dc.identifier.pages1723-1732en_US
dc.identifier.urihttps://diglib.eg.org/handle/10.2312/CGF.v29i5pp1723-1732en_US
dc.identifier.urihttps://diglib.eg.org/handle/10.2312/CGF.v29i5pp1723-1732
dc.titleLocalized Delaunay Refinement for Sampling and Meshingen_US
Files
Collections
29-Issue 5
SGP10: Eurographics Symposium on Geometry Processing