Constrained Delaunay Triangulation
Constrained Delaunay Triangulation
This is a robust C# implementation of constrained delaunay triangulation of Random surfaces using Ruppert's & Bowyer-Watson Incremental algorithm.
References
•A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Jim Ruppert (NASA Ames Research Center)
https://www.cis.upenn.edu/~cis610/ruppert.pdf
•Delaunay Refinement Algorithms for Triangular Mesh Generation,onathan Richard Shewchuk jrs@cs.berkeley.edu (May 21, 2001)
https://people.eecs.berkeley.edu/~jrs/papers/2dj.pdf
•Guranteed-Quality Mesh Generation for curved surfaces L.Paul Chew Cornell University Ithaca, NY
https://kogs-www.informatik.uni-hamburg.de/~tchernia/SR_papers/chew93.pdf
https://ecommons.cornell.edu/handle/1813/6899
•There Are Planar Graphs Almost as Good as the Complete Graph L.Paul Chew
Bowyer watson incremental algorithm
Bowyer Watson incremental algorithm is the best algorithm to use to implement constrained Delaunay refinement using Ruppert’s or Paul Chew’s algorithm.
The steps of incremental algorithm are
•Add a super triangle to cover the domain.
•Add points of the domain one by one.
•If the point lie inside a triangle that triangle is removed and split into new three triangles with the new point is shared by all new three triangles.
•If the point lie on an edge then the edge is removed and split into to two edges and the two triangles sharing the edge also removed with new four triangles added.
The most important step of this algorithm is the flip_edge routine.
This is a routine which recursively flip edges which are associated with bad triangles added by the new point. Bad triangles are triangles which doesn’t satisfy the Delaunay condition which is the circum circle of the triangle will not contain any other point.
recursive flip edge
The first step in filp_edge routine is to find the edge which is not connected to the newly added point, the other triangle which shares this edge and the other point of the other triangle which is not connected to the edge
The below picture shows the variables used in flip_edge
•The test to confirm whether the new triangle is valid is by checking whether the circum circle of new triangle encroaches the other point. Only the other point has to be checked because if all the triangles added are valid the closest point to the newly added triangle will always be the other point.
•If the other point lies inside the new triangle’s circum circle then the common edges is flipped which means the new triangle and the other triangle are removed with new two triangle added.
•Now the new triangles are tested recursively by fed into the flip edge routine recursively.
The below pictures gives more details
BEFORE constrained delaunay REFINEMENT
Before starting the meshing process, the following details of the surface being meshed needs to be defined.
•A surface consists of closed non intersecting outer edges which are all connected to form a single loop. A surface might also contains one or more inner closed edges which each forming a single loop.
•Now considering the surface outer loop and inner loop(s) can be discretized as line segments, we will have list of points connecting these edges.
•The list of points can be used to have an initial Delaunay triangulation. However by recursively splitting the edges whose diametrical circle encroaches other points, will provide good initial Delaunay triangulation.
The below images explain the idea
CDT ALGORITHM
Build the constrained Delaunay triangulation for the set of points & edges from the previous step
•Step 1 : Grade the triangle with (1) ratio circumcenter to shortest edge and (2) well sized. If there is no bad triangles halt.
•Step 2: Select the worst triangle. Note the circumcenter of this worst triangle.
•Step 3: Check whether the circumcenter encroaches diametrical circle of any outer or inner edges. If yes, then split the edge and add the new point (not the circumcenter) to the mesh and go to step 2. If no encroachment go to step 4.
•Step 4: Add the worst triangle’s circumcenter as the new point to the mesh and go to step 2.
Continue the steps until no bad triangles.
____________________________________________________________END____________________________________________________________