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)

and your test point be

        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|

Some additional notes:

• 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.