Newsgroups: comp.graphics,comp.graphics.algorithms
From: herron@cs.washington.edu (Gary Herron)
Subject: Re: point within a tetrahedron
Date: Wed, 23 Feb 94 21:52:45 GMT

obrecht@imagen.com (Doug Obrecht) writes:

Can someone point me to an algorithm that determines if a point is within a tetrahedron?

Let the tetrahedron have vertices

```        V1 = (x1, y1, z1)
V2 = (x2, y2, z2)
V3 = (x3, y3, z3)
V4 = (x4, y4, z4)
```

```        P = (x, y, z).
```

Then the point P is in the tetrahedron if following five determinants all have the same sign.

```             |x1 y1 z1 1|
D0 = |x2 y2 z2 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

|x  y  z  1|
D1 = |x2 y2 z2 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

|x1 y1 z1 1|
D2 = |x  y  z  1|
|x3 y3 z3 1|
|x4 y4 z4 1|

|x1 y1 z1 1|
D3 = |x2 y2 z2 1|
|x  y  z  1|
|x4 y4 z4 1|

|x1 y1 z1 1|
D4 = |x2 y2 z2 1|
|x3 y3 z3 1|
|x  y  z  1|
```

• If by chance the D0=0, then your tetrahedron is degenerate (the points are coplanar).

• If any other Di=0, then P lies on boundary i (boundary i being that boundary formed by the three points other than Vi).

• If the sign of any Di differs from that of D0 then P is outside boundary i.

• If the sign of any Di equals that of D0 then P is inside boundary i.

• If P is inside all 4 boundaries, then it is inside the tetrahedron.

• As a check, it must be that D0 = D1+D2+D3+D4.

• The pattern here should be clear; the computations can be extended to simplicies of any dimension. (The 2D and 3D case are the triangle and the tetrahedron).

• If it is meaningful to you, the quantities bi = Di/D0 are the usual barycentric coordinates.

• Comparing signs of Di and D0 is only a check that P and Vi are on the same side of boundary i.