Re: [Algorithms] Constrained Delaunay Triangulations

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

John,


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

True!. And the diagonal edges intersection is one way. Now there is another one
 that I am using which so far seems to be very robust that I would like to share
with you:
The in_circle test is *oriented* so in other words, the result of the
determinant will be
negative or positive depending on the orientation of the 3 vertices (CW, CCW).
Let's assume that the triangles are oriented CCW.
In your drawing, if I want to know whether I should build AD, I take the
circumcircle based
on ACD (not ADC) and test B against it. The test will return true which means
that B is inside
the circle oriented ACD and therefore BC must remain. You can try it with any of
the circumcircle
possible, it works. BAC vs D, ACD vs B, CDB vs A and DBA vs C.


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

Wow, pretty good!... So this means roughly 100k edges per second?
How big are your constraints? Can you insert edges of arbitrary length
in the triangulation or do you select your dataset so that you will never have
more than 2 triangles to flip to get the constraint inserted?

Do you have any shots???


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

Which method are you using for the point location? Guibas & Stolfi's algorithm?
Personally, I use a modified version of this algorithm since it fails with
constrained
triangulations. Have you tried hierarchical Delaunay triangulation? It appears
to be
be most efficient point location method by now..


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

That's right!... A gold mine for Delaunay fans...

Thanks!

David Kornmann.
http://www.iki.fi/david
--