From: David Kormann <david@ik...>  20001102 21:35:18

> However this approach (which was the one that I used first) gives no > information about how close B and C are to AD, in other words an automatic > metric about how sliverlike the constructed triangles will be is given by > the method I currently use. This is a win (in terms of processor cycles in > the way that I have been approaching the problem), because I don't need to > do golden ratio type checks to prevent more sliver triangles being created. True. > 3.2 triangles are being flipped per constraint. High of 25. Bound to be > different with a different dataset. > Plus, I seem to be doing closer to 1300 edges per frame than 3000 most of > the time. I may peak at around 3000, but possibly if I was running at that > the whole time I might notice a hit on the slower machines  I haven't > checked. That's pretty nice anyway! > A mesh is a mesh is a mesh (just imagine lots of blue triangles with red > constrained edges)... Just curious!... > No. I do use a modified mesh walk using the sign of a rough triangle area > and a couple of tie break metrics though. What modifications are you using > (asked in the hope that you have a neat trick which will fix my occasional > bad case :))? Most of my speed comes from some tricks to pick a good > starting triangle to walk from. Well I noticed that to avoid the infinite loop with contrained edges, instead of computing the the sign of the determinant for one of the edges, I compute the sign for both edges sharing the triangles where I may jump into. The one which has the largest determinant is the best one to go to... and now it never hangs anymore! Cheers, David.  
From: John Harries <jharries@di...>  20001030 22:29:58

CDT is tricky to keep robust. A VERY important thing to remember is that your constrained mesh is no longer "Delaunay compliant". You will end up with some concave quads (that I can't draw well in ASCII art), where you can not flip the joining edge, because your flipped edge would cross out of both triangles (passing through previously constrained edges). Check for this, some of the code publically available on the net manages not to do this, and it is wrong. This paper (which I wish I had read when I wrote my code) is clearly trying to save you from the pain of this. 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]. You will also end up with slivers. There is nothing you can do about this. You will need to have a sufficient delta on your calculations to cope with this. This delta will be different depending upon the scale of your data and upon the precision you require. 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. John Original Message From: Dave Smith [mailto:Dave.Smith@...] Sent: Monday, October 30, 2000 2:46 PM To: gdalgorithmslist@... Subject: [Algorithms] Constrained Delaunay Triangulations I'm planning to implement the Flip Algorithm that is described in Bern & Eppsteins '85 paper, pg 12.(Sorry don't have the title at the moment). My question is the following: For an edge e, not an input edge & not on the convex hull, denote Qe the quadrilateral formed by the two triangles on each side of e. Qe is 'reversed' if e is not in the CDT of the 4 outside edges of the quadrilateral. Or, in other words, Qe is 'reversed' (1) if the angles at its uncut corners sum to more than 180, or (2) if e forms a smaller minimum angle with the outside edges than the other diagonal does. So for (1) to be true I assume for this picture: /E\F/ / \ B/ / \ / e is the diagonal in this picture. / \ / /_A_____D_\C/ A+B > 180 ....easy enough, I hope :/ And for (2) to be true, with the above picture: MIN{D,C,E,F} < MIN{G,H,I,J} where G,H,I,and J are the angles that would cut the outside edges if another diagonal was drawn that intersected angles A and B. Does that sound ok? I'll probably be implementing this shortly but I thought maybe somebody who has gone through the pain, may catch something I may be doing wrong. Also, any other references to fairly easy to implement CDT algorithms are welcome. Thanks, DaveS ps. Thanks to PeterPike Sloan for the Computational Geometry links. They fixed some of my problems. _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist 
From: John Harries <jharries@di...>  20001031 13:47:52

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 10003000 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 CMUCS96140] 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:david@...] Sent: Tuesday, October 31, 2000 4:10 AM To: gdalgorithmslist@... 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:// http://www.inria.fr Regards, David Kornmann.  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist 
From: David Kormann <david@ik...>  20001031 20:37:21

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 10003000 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  
From: John Harries <jharries@di...>  20001031 22:56:17

David, > > 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. However this approach (which was the one that I used first) gives no information about how close B and C are to AD, in other words an automatic metric about how sliverlike the constructed triangles will be is given by the method I currently use. This is a win (in terms of processor cycles in the way that I have been approaching the problem), because I don't need to do golden ratio type checks to prevent more sliver triangles being created. > 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? Hmmm, quick, fairly unscientific check... 3.2 triangles are being flipped per constraint. High of 25. Bound to be different with a different dataset. Plus, I seem to be doing closer to 1300 edges per frame than 3000 most of the time. I may peak at around 3000, but possibly if I was running at that the whole time I might notice a hit on the slower machines  I haven't checked. I suspect a lot of the speed comes from early outs in the code and good cache performance due to a compact localised mesh representation. > > Do you have any shots??? A mesh is a mesh is a mesh (just imagine lots of blue triangles with red constrained edges)... > 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. No. I do use a modified mesh walk using the sign of a rough triangle area and a couple of tie break metrics though. What modifications are you using (asked in the hope that you have a neat trick which will fix my occasional bad case :))? Most of my speed comes from some tricks to pick a good starting triangle to walk from. > Have you tried hierarchical Delaunay > triangulation? It appears > to be > be most efficient point location method by now.. The memory it uses up is my biggest issue with it. Sure helps with deletions though. cheers, John 
From: David Kormann <david@ik...>  20001102 21:35:18

> However this approach (which was the one that I used first) gives no > information about how close B and C are to AD, in other words an automatic > metric about how sliverlike the constructed triangles will be is given by > the method I currently use. This is a win (in terms of processor cycles in > the way that I have been approaching the problem), because I don't need to > do golden ratio type checks to prevent more sliver triangles being created. True. > 3.2 triangles are being flipped per constraint. High of 25. Bound to be > different with a different dataset. > Plus, I seem to be doing closer to 1300 edges per frame than 3000 most of > the time. I may peak at around 3000, but possibly if I was running at that > the whole time I might notice a hit on the slower machines  I haven't > checked. That's pretty nice anyway! > A mesh is a mesh is a mesh (just imagine lots of blue triangles with red > constrained edges)... Just curious!... > No. I do use a modified mesh walk using the sign of a rough triangle area > and a couple of tie break metrics though. What modifications are you using > (asked in the hope that you have a neat trick which will fix my occasional > bad case :))? Most of my speed comes from some tricks to pick a good > starting triangle to walk from. Well I noticed that to avoid the infinite loop with contrained edges, instead of computing the the sign of the determinant for one of the edges, I compute the sign for both edges sharing the triangles where I may jump into. The one which has the largest determinant is the best one to go to... and now it never hangs anymore! Cheers, David.  
From: Dave Smith <Dave.S<mith@sd...>  20001031 02:23:36

In the words of Troy McClure: "That's fantastic, Baby!" Really, thanks. That was a quick reply for something that specific. I have some more questions below, if you don't mind. > > CDT is tricky to keep robust. A VERY important thing to remember is that > your constrained mesh is no longer "Delaunay compliant". You will end up > with some concave quads (that I can't draw well in ASCII art), where you can > not flip the joining edge, because your flipped edge would cross out of both > triangles (passing through previously constrained edges). How could a flipped edge end up outside both triangles? I thought the choice was either diagonal of the quad? > This paper (which I wish I had read when I wrote my code) is > clearly trying to save you from the pain of this. When you say "this paper" are you referring to Bern & Eppsteins "Mesh Generation and Optimal Triangulation" or Schewchuks? (I finally got home to read the title. :P ) > You will also end up with slivers. There is nothing you can do about this. > You will need to have a sufficient delta on your calculations to cope with > this. This delta will be different depending upon the scale of your data > and upon the precision you require. How big a range of delta's are we talking about? Just some examples, 10e5 to 10e1 for example. > > 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. > I saw it float by yesterday on ACM. We'll see if I find time. :) Thanks again, DaveS 
From: David Kormann <david@ik...>  20001031 10:13:10

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:// http://www.inria.fr Regards, David Kornmann.  