SVR: provably fast mesh refinement
Traditional mesh refinement codes are largely concerned with producing
quality meshes, at almost any runtime cost. The assumption is that a
single mesh will be used in many (often hundreds) of finite element
simulations, and so what matters is not the meshing time, but the mesh
quality and mesh size. Increasingly, however, we want to remesh during a
simulation -- as often as every timestep -- as the domain changes or needs
to be refined. Furthermore, some pathological examples (which are not as
far-fetched as one might hope) cause traditional algorithms to use
quadratic space, running out of memory quite quickly. Quad-tree and
oct-tree refinement algorithms are provably fast, but in practice produce
large meshes.
The SVR algorithm is the first Delaunay refinement algorithm to be provably
fast, but still produce the small meshes associated with Delaunay
refinement. This page describes and distributes an implementation of SVR,
which we have shown is faster than the TetGen or Pyramid codes when
computing quality meshes of point-cloud inputs.
What is SVR good for?
For point sets in three dimensions, SVR is mature and robust, and is the
fastest mesh refinement algorithm we know of even on non-pathological
inputs. No input is pathological for SVR, unlike for most prior codes,
which can be made to run out of memory on even relatively small examples of
a few thousand points. SVR produces meshes of about the same size as
Shewchuk's Pyramid code, and slightly smaller than TetGen. It also has a
much richer API than those codes for manipulating the output, which should
make it easier to write post-processing passes. For point sets in two
dimensions, Shewchuk's Triangle is rather faster on most inputs, except on
some pathological examples that SVR can handle.
SVR also works on proper Piecewise Linear Complex (PLC) inputs, though that
code is still of research quality. On inputs legal for SVR, the code will
always terminate with a small mesh, but the work to make this fast has not
yet been done. Of course, on inputs pathological for prior codes, SVR will
indeed terminate much faster.
Using the Li-Teng technique, SVR can eliminate slivers, in practice
producing a mesh with no worse dihedral angles than about 10 or 170
degrees, and often rather better. Using the Li-Teng technique may cause
the algorithm to fail when asking for any reasonable angle bounds, so it is
off by default. Provably eliminating slivers with good angle bounds is
still an open research question.
You will not find a mode for computing the Delaunay triangulation of an
input without refining it, because this would open up SVR to pathological
examples. Nevertheless, if adding only a very small number of points is
acceptable, you can set parameters to approximate a Delaunay-only mode (by
setting k very close to 1.0, and by setting rho and
rhoprime very large, see Running SVR).
This may be quite slow, depending on the input geometry.
Maturity
SVR is still in development, and has a low version number to reflect this.
On point-cloud input (a .node file), with
the default arguments, SVR is very stable and robust. Sliver elimination
(by setting sigma) is very runtime-expensive, and the algorithm
itself is imperfect, but SVR generally can eliminate slivers on point
clouds, as mentioned above. On PLC inputs, SVR appears to work on most
inputs, but is slow. There is a list of known bugs.
If you notice a problem not covered in that list, contact Benoît Hudson.
License
SVR is cost-free unless you intend to include SVR in a product you are
selling. It is not free software, with the exception of three files:
geometry/predicates.c and utilities/lookup3.h are in
the public domain, and geometry/x87control.h is under the GNU
Lesser General Public License. Contact Benoît Hudson with any questions.
Also, if you are using SVR, I'd love to hear about your experience with it.
Last modified by Benoît Hudson
Fri Oct 19 19:20:25 CDT 2007