[vtkusers] vtkDelaunay3D numeric error

[Will Schroeder]

Hi Alex / Jeff -

At 01:49 PM 9/14/2000 -0300, Alex Jesus Cuadros Vargas wrote:
>In vtkDelaunay3D class documentation talk about a numeric error. I
>would like to know if have some way to avoid this error.

Two things. First, about 2-3 weeks ago I checked in a major overhaul of 
vtkDelaunay3D.
It is now about 10x faster and much more robust. Get them from the nightlies.

Second, the Delaunay algorithm implemented in vtk uses a point insertion 
process. Each
point is added to an existing Delaunay triangulation, and every tetrahedron 
whose circumspheres
contain the point are deleted leaving a star-convex cavity. The faces of 
the cavity are connected to
the point forming new tetrahedron. All goes well except that the 
determination of the circumsphere
and circumradius requires a solution to a linear system. This, coupled with 
situations where points
are badly positioned (creating needles or pancakes) can lead to numerically 
unstable situations. The
result is that the circumsphere/radius are not quite accurate. This means 
the cavity when generated may
not be star convex...and newly created tetrathedra can interpenetrate the 
triangulation. So what's the
numerical error? ... it depends on both the configuration and order in 
which points are inserted. You might
try randomizing points if you have problems.

There are solutions out there...either use integer arithmetic (essentially 
perturbing the point positions to
avoid degenerate situations). There are also symbolic solutions (exact 
arithmetic). These are much more
complex and tend to be slower.

Will