RE: [Algorithms] Constrained Delaunay Triangulations

[John H. <jha...@di...>]

In crunch, so I will be sparse in my replies (and possibly wrong, due to
tiredness :-)):

I was only specifically addressing a quick way around the fact that
constrained triangulations give you cases that look like (and here I attempt
ASCII art):
                     B
                    /||\
                   / || \
                  /  ||  \
                 /  , C.  \
                / ,     .  \
               /,         . \
              A             D

You have just made triangle ABC by inserting vertex A in some adjacent
triangle.  Edges BD and CD have previously beeen constrained.  Yet vertex D
lies within the circumcircle of ABC.  This situation only happens because of
the constraints.  Clearly we can't delete BC and make an edge AD.  I was
suggesting a simple and fast supplement to the standard circumcircle check
(which I posted to an earlier post).  It works for me.  You are obviously
getting slivers at this point!

My text should have read: updating tesselations in enormous meshes (100,000
vertex+). My only excuse is that I was doing too many other things while
writing that earlier sentence, it is very inaccurate. Typically I am adding
and deleting 1000-3000 constrained edges per frame into these meshes.  This
is not a significant cost on today's base hardware (P2 450). I am using an
incremental insertion method, which is, I suspect, the best real time
approach with modifying large meshes.  Actually the important part for me
isn't the speed, it is the stability.  If you want really fast speed and you
do not intend to dynamically modify the mesh, then there are allegedly
faster approaches (I haven't done benchmarks).

The biggest problem BY FAR is the rapid location of the containing triangle
(or edge, or vertex) for an inserted point.  When you have degeneration in
the form of slivers this can make standard mesh walks hard to make robust
(and fast), and it still annoys me that I occasionally have to fall back to
a brute force scan.

General things that help speed a lot (this is a far from exhaustive list):

-	Randomised insertion
-	As tiny a mesh structure as you can make
-	Memory aligned elements in your mesh structure
-	Preallocate working memory
-	Localise adjacent triangles in memory where possible
-	Fast predicates (duh)
-	Good, memory friendly, history structures if you know you will be
deleting a set of edges (I'm not going to go into this, but the Boissonat
and Devillers papers are a good place to start even if you end up using a
different solution due to your special circumstances).

Some robustness comes from:

-	Reasonably loose checking if an inserted vertex already exists in
the mesh (in the scale I'm working in that means a distance of 0.0001 - an
arbitrarily picked value that no doubt will differ depending on the
implementation).
-	Loose checking for if an inserted vertex lies along an edge, and
then snapping the vertex to the edge before actually adding it.
-	Aggregating sliver triangles into their adjacent triangle's edges if
detected

I hope this helps.  I found writing a fast robust triangulator to be an
incredible pain in the ass.  Floating point precision is your enemy whenever
doing this kind of thing.  Sadly for me, using Shewchuk's [Adaptive
Precision Floating Point Arithmetic and Fast Robust Geometric Predicates
CMU-CS-96-140] was not an option due to where I was using the code.  If you
are doing this at all offline you will save yourself a lot of frustration by
using them.

cheers,

John
(More of an engineer than an expert...}

-----Original Message-----
From: David Kormann [mailto:da...@ik...]
Sent: Tuesday, October 31, 2000 4:10 AM
To: gda...@li...
Subject: Re: [Algorithms] Constrained Delaunay Triangulations




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.
--

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list