3
$\begingroup$

I have a delaunay triangulation for a 2d box with say an airfoil inside. If I uniformly refine this mesh by subdividing each triangle in the mesh into 4 triangles by halving each edge, is the resultant mesh still delaunay? I have been assuming so, but I have no proof this is the case.

$\endgroup$
2
  • $\begingroup$ It might be interesting to read here: cse.ust.hk/~scheng/book/Delmesh/chapter2.pdf, specifically page 33. $\endgroup$ Jan 15, 2020 at 21:01
  • $\begingroup$ I came across this in my previous research, but didn't see how it answered my question. Am I missing something? Thanks. $\endgroup$
    – EMP
    Jan 15, 2020 at 23:45

2 Answers 2

3
$\begingroup$

You can have a near-180° obtuse triangle in a Delaunay triangulation, if all other vertices in the mesh are far from the long edge. However, after subdivision, the obtuse vertex may lie inside the circumcircle of the central subtriangle.

$\endgroup$
6
  • 1
    $\begingroup$ Is there a proof for this? Thanks! $\endgroup$
    – EMP
    Jan 17, 2020 at 11:47
  • $\begingroup$ Consider the triangle with vertices $(-1,0),(1,0),(0,\epsilon)$. After subdivision the midpoints are $(0,0),(-\frac12,\frac\epsilon2),(\frac12,\frac\epsilon2)$. The vertex $(0,\epsilon)$ lies inside the circumcenter of the triangle formed by the midpoints. $\endgroup$
    – user3883
    Jan 17, 2020 at 12:05
  • $\begingroup$ Thanks! I checked off this, and even for this simple case, there are a surprising large set of tris that when subdivided won't be delaunay. $\endgroup$
    – EMP
    Jan 17, 2020 at 12:24
  • $\begingroup$ Nice question. Do we know what type of Delaunay triangulation will remain Delaunay upon such a subdivision ? What additional property is required for this ? $\endgroup$
    – cfdlab
    Jan 19, 2020 at 2:56
  • $\begingroup$ Well an equilateral one would remain delaunay, but that can't be all. I assume there is a weaker condition that remains delaunay when subdivided $\endgroup$
    – EMP
    Jan 19, 2020 at 20:38
0
$\begingroup$

I hope I'm not overlooking something, but it seems obvious that the mesh so refined will not be Delaunay.


EDIT: Turns out I misunderstood the procedure, and you are actually generating a fresh mesh through trimming curves/edge flips/equivalent.


Essentially you are adding vertices to the midpoints of each edge of a triangle; these midpoints lie inside the circumcircle of the original triangle. This is a violation of the Delaunay condition. You will additionally need to re-triangulate and remove some edges of the original triangle to make it Delaunay. This is not a trivial operation, and will take O(n) time.

Even so, this is not a preferred strategy for Delaunay refinement - most approaches instead add vertices at the circumcentre and proceed from there. I don't know the comparative merits of both approaches, it could be worth looking into. You may like reading this : https://www.cs.cmu.edu/~quake-papers/delaunay-refinement.pdf

Additionally, since you are halving all edges, rather than selecting which edges should be halved, you are very likely to run into problems with 'skinny triangles'. These have one edge much larger than the other, and pose a problem to Delaunay triangulation. If the edges are selectively halved, using for instance Ruppert's algorithm, then you would convert a skinny triangle into smaller, less skinny triangles.On the other hand, if you half all edges, you preserve the skinny nature of the triangle.

This is easily shown mathematically; halving each edge yields you four triangles, three sharing a vertex with the original triangle. Each of these three triangles is similar to the original triangle by the SAS criterion (one common angle between two sides sharing the same ratio. In this case the ratio will be 1:2). Thus, you are creating equally skinny triangles, and three of them. So if your original mesh had x poor-quality (i.e. skinny beyond some threshold) elements, you will now have atleast 3x poor-quality elements, which is naturally undesirable.

$\endgroup$
5
  • 1
    $\begingroup$ The midpoints lie inside the circumcircle of the original triangle, but the original triangle is no longer part of the subdivided mesh. You would have to show that the midpoints lie inside the circumcircles of the four smaller subtriangles. $\endgroup$
    – user3883
    Jan 17, 2020 at 10:14
  • $\begingroup$ @Rahul- The original triangle will be part of the subdivided mesh, unless the original mesh is altered and the edges are flipped or it is re-meshed, which OP hasn't included in the question. $\endgroup$ Jan 17, 2020 at 12:23
  • $\begingroup$ I say in the question that the edges are halved. So the original triangle no longer exists. $\endgroup$
    – EMP
    Jan 17, 2020 at 16:08
  • $\begingroup$ @EMP- I guess we differ in terminology then. As I understand, you are not only halving the edges, but also trimming the edges (trimming curves) and generating a new mesh. This is, atleast computationally not trivial, hence my answer. Anyway, I have updated it with this new information. :) $\endgroup$ Jan 18, 2020 at 13:41
  • 1
    $\begingroup$ Thanks for the additional info. I need to do the uniform refinement for certain algorithms, but I don't do the actual AMR like that, because you'd get bad quality as you stated. I was just curious because I was subdividing every edge and then running an incircle predicate to improve mesh quality and when I tested it on the uniform mesh the incircle predicate swapped some edges, and I wasn't sure if that was an indication of a bug or a misunderstanding on my part. $\endgroup$
    – EMP
    Jan 19, 2020 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.