Re: [Algorithms] Constrained Delaunay Triangulations

[David K. <da...@ik...>]

John,

> The calculations look a
> little heavy though: you could just check if the intersection of AB lies
> sufficiently within EC (by some delta) before flipping.  [Since my code is
> tesselating enormous meshes in real time in a real game without any
> noticeable hit, it can't be too bad an approach].

Tell me if I'm wrong, but just checking the intersection sounds a little bit
weak to me,
especially with for a CDT. The intersection test works in most of the cases but
does
not garantee that you have a Delaunay triangulation (if you insert vertices
only) and does not
garantee as well that you have infinite loops in your insert/delete function.
How about incircle tests?
How do you select the vertices that you put in your triangulation?
Is your CDT incremental?
How fast is it?
You talked about enormous meshes in realtime: How big? How fast?

> If you have the time you may wish to use slightly more rigorous metrics.
> Jonathan Shewchuk's papers are very sane references.  He has spent a lot of
> time thinking about it.

J.D Boissonat & O. Devillers  have a lot of interesting papers about these
topics at INRIA:
http:// www.inria.fr

Regards,

David Kornmann.
--