Tetrahedron orientation for triangle meshes

Question

I have 2 triangles and vertices p0, p1, p2, p3. These two triangle share an edge. From these two triangle I want to make a tetrahedron given by the 4 vertices. The library which I work with requires that "the 4 vertices should be given such that the four vertex triples defining the tetrahedron faces in the drawing appear in counter-clockwise order when being viewed at from the outside" drawing . Assuming one of the two triangles is p0, p1, p2 I calculate the normal as being (p1-p0) (cross) (p2-p0). Can someone please tell me a way to ensure that this condition is met ?

It's a shame you went to all the trouble to provide a very clear diagram and then used the wrong labels for the vertices in the text of your question. The first time I read it I was very confused. — High Performance Mark
You would generally need some other way to decide on outside - often this comes from the meshing algorithm (marching cubes etc) — Martin Beckett
If both triangles have the normals calculated in the same way as mentioned in the description couldn't I just pick one side (the one the normal is pointing) and consider it front or behind? — Ray
Short short answer: yes, as long as you take the points in a consistent order... — comingstorm

comingstorm comingstorm · Accepted Answer · 2012-05-16T22:44:01

Short answer:

The condition is that p3 must be on the correct side of the plane determined by (p0, p1, p2).

So, after computing the normal for this plane, you need to determine if the vector from (say) p0 to p3 is pointing in the same direction of the normal, or the opposite direction, by taking the dot product dot(normal, p3-p0).

More mathematically speaking:

You need to find the determinant of the 4x4 matrix formed by the homogeneous coordinates of the four points. The sign of the determinant determines if the condition is met; the appropriate sign depends on the exact conventions used, but ideally it should be positive:

require:
  0 < det(p0, p1, p2, p3)

  == det [ p0.x p0.y p0.z 1 ]
         [ p1.x p1.y p1.z 1 ]
         [ p2.x p2.y p2.z 1 ]
         [ p3.x p3.y p3.z 1 ]

If a particular ordered set of points has a negative determinant, you can fix it by swapping any two of the points (which will negate the determinant):

e.g., swapping p0 and p2:

det(p0, p1, p2, p3) = - det(p2, p1, p0, p3)
     ^       ^               ^       ^

or, more generally, switching between even and odd permutations of the four vertices.

If the determinant is zero, the four points are co-planar, and cannot be fixed like this.

Finally, the code:

A relatively simple way to compute this determinant with 3-d vector math:

let:  v1 = p1 - p0
      v2 = p2 - p0
      v3 = p3 - p0
      norm12 = cross(v1, v2)
   -> determinant = dot(norm12, v3)

The final determinant is also known as the "triple product" of v1, v2, and v3.

Note that I have hesitated to try to decode the exact sign convention (i.e., whether you need the determinant to be positive or negative) from your question: the wording and diagram you supply is more than a bit confusing.

Since you have the original library and its documentation, though, you are in the best position to answer this question. As a last resort, you can try the empirical method: try both signs, and pick the one that doesn't blow up...

Tetrahedron orientation for triangle meshes

1 Answers