[vtkusers] Constrainted Delaunay in 2D and 3D

[Will Schroeder]

Hi David-

At 09:44 AM 7/19/00 -0400, David (Chuin-Shan) Chen wrote:
>Hi All,
>
>I have used Delaunay2D for the constrainted Delaunay Meshing in 2D and are quite
>happy with the results. However, I can only find the implementation in VTK
>mentioned once in Will's email and can't find it anywhere in the VTK books. I will
>appreciate if someone can:


>1. briefly indicate the references used for the constrainted Delaunay
>implementation and

The implementation is a home-grown algorithm that I came up with....I've never seen
any references describing this technique. The algorithm is as follows:
1. generate delaunay triangulation
2. recover constraint edges
3. if constraint polygons are present, determine inside/outside and delete
triangles that are outside.

The recover edges algorithm looks like:
1. For each constraint edge (p1,p2), and constraint edge not present in the mesh
2. find triangle connected to starting point p1 and containing
a portion of the edge.
3. find the (edge neighbor) triangle connected to current triangle and containing edge.
4. continue until last triangle is found that uses the ending point p2.
5. The collection of triangles containing the edge defines two "polygons" -
one polygon is defined by the + edges (edges on one side of (p1,p2) and (p1,p2);
the second polygon is defined by the - edges and (p1,p2). These two polygons
are then triangulated vtkPolygon::Triangulate().

An alternative approach - edge swapping - is not as easy as it sounds. There are
pathological cases the complicates the algorithm.


>2. briefly compare Delaunay2D with Triangle, especially for the contrainted
>Delaunay stuff.

I assume you meant vtkPolygon::Triangulate. Triangulate is faster. The Delaunay approach
can handle polygons with holes.


>I also realize that it is not a trivial task to extend the constrainted Delaunay
>from 2D to 3D, but are wondering if there is any ongoing implemetation in VTK
>toward this direction.

I'd like to get the 3D version really solid first...there are still numerical problems.
The problem with constrained 3D is how to describe the constraints (a polyhedra??)
and then creating/identifying robust algorithms for recovering faces. 

This can all be done, but it takes a lot of time. There is interest, but no real activity
here at Kitware other than the occasional support question that allows us to
extend/fix the software.

Will