In some algorithms to refine tetrahedron, we need to calculate the longest edge.


If exist a tetrahedron with node ABCD, it has edges AB,AC,AD,BC,BD,CD.

Suppose AB is the longest edge, and E is the middle point of edge AB, the tetrahedron can be split into two tetrahedrons, that is, BCDE and ACDE.

My problem is, how to deal with the situation that has many longest edges?

To demonstrate much detail:

Suppose there exist two tetrahedrons ABCP and ABCQ, they share the face ABC.

Suppose AB=AC and they are the longest edges in each tetrahedron.

If ABCP chooses AB to split and ABCQ chooses AC to split, the grid will be incompatible, it will lead to an error in FEM calculation.

If ABCP chooses AB to split and ABCQ also chooses AB to split, the grid still compatible.

So how to make sure ABCP and ABCQ choose the same edge to split?

How to deal with the irregular case?


The easiest thing is to ensure a consistent (although arbitrary) tie-breaking scheme. If your nodes/vertices indexed, this usually means preferring the split edge with the lowest index of its lowest vertex. If the edges share the same lowest index vertex, then check the other vertex and choose the one with the lowest index.

So in your situation, imaging the vertices are indexed such that A<B<C. And to make things worse, imagine AB=BC=AC so the algorithm could choose to split any of the three edges of the shared triangle between the two tetrahedra. Now edges AB and AC will be preferred over BC since A<B. Then AB is preferred over AC since after seeing they share the lowest vertex, the other vertex is compared (and B<C).

Both tetrahedra will perform the same checks and come to the same conclusion: AB is the preferred segment to split.

It is important that each tetrahedra has identical coordinates for the vertices (ideally, indexed into the same data structure holding the vertex coordinates) and perform the same floating-point precision computations to compare the lengths before getting to the tie-breaking steps. If there is any slight difference in how the lengths are computed, floating point inconsistency can prevent the tie-breaking from kicking in.

For more general situations, simulation of simplicity is a framework for dealing with degeneracy / tiebreaking in these kinds of geometric comparisons.

Edelsbrunner, Herbert; Mücke, Ernst Peter, Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms, ACM Trans. Graph. 9, No. 1, 66-104 (1990). ZBL0732.68099.

  • $\begingroup$ Wow, sir, it is fantastic! $\endgroup$ – Xu Hui Sep 28 '20 at 0:49

Sir Alex already give a fantastic answer.

I just add some of my comments how to using Sir Alex's proposal in the distributed cases.

If the algorithm is distributed. For example, the ABCP and ABCQ are be stored in different processes, and the A,B,C,P,Q here is the global index of the node.

Suppose ABCP is stored in process 0, where its local index is 0,1,2,3.

Suppose ABCQ is stored in process 1, where its local index is 0,2,1,3.

We can see that face ABC have different index order in each process. In process 0, A<B<C, but in process 1, A<C<B.

We should not use the local index to do the refining procedure unless the node index order can be ensured. If the index order can not be ensured, the global index is preferred.

However, sometimes calculate the global index have great overhead.

We can give the index to ABC by coordinates at run time. Once we can obtain a compare rule to coordinates, we can give indexes to the nodes. Follow is an example of a compare rule.

First, we can compare x coordinate. If x1>x2 thus node1 > node_2. then compare y coordinates, finally compare z coordinates.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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