carrier image

SVR: Practical Engineering of a Fast 3D Meshing Algorithm

Acar, Umut A., Benoit Hudson, Gary L. Miller, and Todd Phillips

Proceedings, 16th International Meshing Roundtable, Springer-Verlag, pp.45-62, October 14-17 2007


16th International Meshing Roundtable
Seattle, Washington, U.S.A.
October 14-17, 2007

Toyota Technological Institute
Carnegie Mellon University

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.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article