Carnegie Mellon University
file.pdf (395.4 kB)

SVR: Practical Engineering of a Fast 3D Meshing Algorithm

Download (395.4 kB)
journal contribution
posted on 2011-09-01, 00:00 authored by Umut A. Acar, Benoit Hudson, Gary L. Miller, Todd Phillips
The recent Sparse Voronoi Refinement (SVR) Algorithm for mesh generation has the fastest theoretical bounds for runtime and memory usage. We present a robust practical software implementation of the SVR for meshing a piecewise linear complex in 3 dimensions. Our software is competitive in runtime with state of the art freely available packages on generic inputs, and on pathological worse cases inputs, we show SVR indeed leverages its theoretical guarantees to produce vastly superior runtime and memory usage. The theoretical algorithm description of SVR leaves open several data structure design options, especially with regard to point location strategies. We show that proper strategic choices can greatly effect constant factors involved in runtime.


Publisher Statement

© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.



Usage metrics


    Ref. manager