How to find if a 3d point is in/on/outside of tetrahedron

Question

How can I find if a 3d point is in/on/outside of tetrahedron defined by 3d coordinates (the point and the tetrahedron)? This is what I found on ethernet:

You now just check if a point $P$ is on the other side of the plane. The normal of each plane is pointing away from the center of the tetrahedron. So you just have to test against $4$ planes. Your plane equation looks like this: $ax+by+cz+d=0$ Just fill in the point values $(x,y,z)$. If the sign of the result is $>0$ the point is of the same side as the normal, result $== 0$, point lies in the plane, and in your case you want the third option: $<0$ means it is on the backside of the plane. If this is fulfilled for all $4$ planes, your point lies inside the tetrahedron.

So if this is correct, I'm struggling to understand the equation $ax+by+cz+d=0$. If I'm correct the $x,y,z$ stand for the point coordinates, what do $a,b,c,d$ stand for ?

Answer 1

Convex polyhedra can be defined as the intersection of the half-spaces formed by their face planes. Tetrahedron is one of these.

A half-space is really just a plane, that splits space into "inside" and "outside", determined by which side the plane normal points to. The equation of a plane (and a half-space) in 3D is $$x_n x + y_n y + z_n z = d$$ or equivalently $x_n x + y_n y + z_n z - d = 0$. Here, $(x_n, y_n, z_n)$ is the plane normal (vector perpendicular to the plane), and $d$ is its signed distance from origin (measured in lengths of the normal vector, or $\sqrt{x_n^2 + y_n^2 + z_n^2}$). If the signed distance is negative, the plane is in the direction opposite to the normal; if positive, in the same direction as the normal. And by "distance from origin", we mean the minimum distance between the plane and the origin.

If we use $\vec{n} = (x_n , y_n, z_n)$ and $\vec{p} = (x, y, z)$, we can write the above using basic vector algebra as $$\vec{n} \cdot \vec{p} = d$$ or equivalently $\vec{n} \cdot \vec{p} - d = 0$.

For example: $$\left\lbrace ~ \begin{aligned} -1 x +0 y +0 z &= 0 \\ 0 x -1 y +0 z &= 0 \\ 0 x +0 y -1 z &= 0 \\ +1 x +1 y +1 z &= 1 \\ \end{aligned} \right. \quad \iff \quad \left\lbrace ~ \begin{aligned} (-1, 0, 0) \cdot \vec{p} &= 0 \\ ( 0,-1, 0) \cdot \vec{p} &= 0 \\ ( 0, 0,-1) \cdot \vec{p} &= 0 \\ ( 1, 1, 1) \cdot \vec{p} &= 1 \\ \end{aligned} \right.$$ define a tetrahedron whose faces are (planes) $x = 0$, $y = 0$, $z = 0$, and $x + y + z = 1$. (Its vertices happen to be $(0, 0, 0)$, $(1, 0, 0)$, $(0, 1, 0)$, and $(0, 0, 1)$, but that's not important, we'll get to vertices further below.)

Let's name the part of the space the normal vectors point to, "outside". Then, a point $(x, y, z)$ is within that tetrahedron, if and only if $$\left\lbrace ~ \begin{aligned} -1 x +0 y +0 z &\le 0 \\ 0 x -1 y +0 z &\le 0 \\ 0 x +0 y -1 z &\le 0 \\ +1 x +1 y +1 z &\le 1 \\ \end{aligned} \right. \quad \iff \quad \left\lbrace ~ \begin{aligned} (-1, 0, 0) \cdot \vec{p} &\le 0 \\ ( 0,-1, 0) \cdot \vec{p} &\le 0 \\ ( 0, 0,-1) \cdot \vec{p} &\le 0 \\ ( 1, 1, 1) \cdot \vec{p} &\le 1 \\ \end{aligned} \right.$$ are all true. If any one of them is false, the point is outside the tetrahedron. The four faces have normal vectors $(-1, 0, 0)$, $(0, -1, 0)$, $(0, 0, -1)$, and $(1, 1, 1)$, with corresponding signed distances $0$, $0$, $0$, and $1$.

Let's assume you have the coordinates for the four vertices of the tetrahedron, $$\begin{aligned} \vec{v}_1 &= (x_1, y_1, z_1) \\ \vec{v}_2 &= (x_2, y_2, z_2) \\ \vec{v}_3 &= (x_3, y_3, z_3) \\ \vec{v}_4 &= (x_4, y_4, z_4) \\ \end{aligned}$$ There is a very simple procedure to find the four planes/half-spaces defining it from the vertices alone, because three points (that are not collinear) suffice to define a plane.

In other words, we'll consider the four following cases: $$\begin{array}{ccc|c} \vec{v}_A & \vec{v}_B & \vec{v}_C & \vec{v}_D \\ \hline \vec{v}_1 & \vec{v}_2 & \vec{v}_3 & \vec{v}_4 \\ \vec{v}_1 & \vec{v}_2 & \vec{v}_4 & \vec{v}_3 \\ \vec{v}_1 & \vec{v}_3 & \vec{v}_4 & \vec{v}_2 \\ \vec{v}_2 & \vec{v}_3 & \vec{v}_4 & \vec{v}_1 \\ \end{array}$$ Each case produces one face normal vector $\vec{n}$ and corresponding signed distance factor $d$, via $$\left\lbrace ~ \begin{aligned} \vec{t} &= \left( \vec{v}_B - \vec{v}_A \right) \times \left( \vec{v}_C - \vec{v}_A \right) \\ \vec{n} &= \begin{cases} \vec{t}, & \text{ if } \vec{t} \cdot \vec{v}_D \lt 0 \\ -\vec{t}, & \text{ otherwise } \\ \end{cases} \\ d &= \vec{n} \cdot \vec{v}_A = \vec{n} \cdot \vec{v}_B = \vec{n} \cdot \vec{v}_C \\ \end{aligned} \right.$$ where $\cdot$ denotes the dot product, and $\times$ cross product, and $\vec{t}$ is just a temporary vector. $\vec{t} = (0, 0, 0)$ if the tetrahedron is degenerate: all vertices on the same plane, same line, or at the same point. Depending on the order in which the vertices are defined, the sign of the normal vector needs to be corrected to make sure it points "outside".

For several reasons, it is often useful to make sure $\vec{n}$ are unit vectors, i.e. $\left\lVert\vec{n}\right\rVert = \sqrt{\vec{n}\cdot\vec{n}} = 1$. Then, use $$\left\lbrace ~ \begin{aligned} \vec{t} &= \left( \vec{v}_B - \vec{v}_A \right) \times \left( \vec{v}_C - \vec{v}_A \right) \\ \vec{n} &= \begin{cases} \displaystyle \frac{\vec{t}}{\left\lVert\vec{t}\right\rVert}, & \text{ if } \vec{t} \cdot \vec{v}_D \lt 0 \\ -\displaystyle \frac{\vec{t}}{\left\lVert\vec{t}\right\rVert}, & \text{ otherwise } \\ \end{cases} \\ d &= \vec{n} \cdot \vec{v}_A = \vec{n} \cdot \vec{v}_B = \vec{n} \cdot \vec{v}_C \\ \end{aligned} \right.$$ but note that you need to check if $\lVert\vec{t}\rVert = 0$ to avoid division-by-zero; it will be zero (or very small with floating-point numbers) if the tetrahedron is degenerate.

Also, you do not need to check the three possible values for $d$, they will all match to within rounding error, so you can just use any one of the three safely.

As an example of why unit normal vectors are useful, $\vec{n}\cdot\vec{p}-d$ tells you how far point $\vec{p}$ is "outside" the face determined by the unit normal $\vec{n}$ and signed distance $d$. If it is positive, the point is "outside", and the value is the actual distance how far. If it is zero, the point is exactly on the face. If it is negative (or zero), the point is "inside", and the magnitude (absolute value) is the distance.

Without normalizing the normal vectors to unit length, those distances are in units of the corresponding normal lengths. Sometimes it does not matter (for example, plain point-in-convex-polyhedron tests), but sometimes it is useful.

Answer 2

Here is a recipe which should be straightforward to program. Let's say the vertices of the tetrahedon are $A$, $B$, $C$, and $D$, and the point to be tested is $P$. All points are given by their 3-dimensional coordinates.

We start by testing that $D$ and $P$ are on the same side of the plane $ABC$. Consider each point as a 3 by 1 column vector and compute the determinant of the 3 by 3 matrix $[B-A, C-A, D-A]$. Also compute the determinant of $[B-A, C-A, P-A]$. If these two determinants have the same sign (both positive or both negative), then $D$ and $P$ lie on the same side of the plane $ABC$. If the second of the two determinants is zero, then $P$ actually lies on the plane, regardless of the sign of the first determinant.

Test similarly to check that $C$ and $P$ are on the same side of $ABD$, that $B$ and $P$ are on the same side of $ACD$, and that $A$ and $P$ are on the same side of $BCD$. If all tests are passed, then $P$ is on or inside the tetrahedron. If the tests show that $P$ lies on one of the planes, as determined by a zero determinant, but otherwise passes all tests, then $P$ lies on the boundary of the tetrahedron.

The theory: Each determinant is the signed volume of a parallelepiped. The sign of the volume depends on the orientation of the edges of the parallelepiped.

Answer 3

One simple approach arises from the fact that a tetrahedron is a 3-simplex. This is a 3d analogue of a common technique used to check if a point is inside a triangle, widely used in computer graphics.

Given a non-degenerated tetrahedron whose four vertices are non-coplanar points $P_0,P_1,P_2,P_3\in\mathbb{R}^3$ and a point $P\in\mathbb{R}^3$, there is a unique way to represent $P$ using barycentric coordinates: $$ P = u_0 P_0 + u_1 P_1 + u_2 P_2 + u_3 P_3 \text{,} $$ where $u_0,u_1,u_2,u_3\in\mathbb{R}$ and $u_0+u_1+u_2+u_3=1$. Knowing that all these coefficients sum up to $1$ we can replace $u_0$ by $1-u_1-u_2-u_3$ and transform the above equation to the following form: $$ u_1 (P_1-P_0) + u_2 (P_2-P_0) + u_3 (P_3-P_0) = (P-P_0) \text{.} $$ This linear equation is pretty straightforward to solve. Having all the coefficients computed, we may perform the test:

• $P$ is inside the tetrahedron $\iff$ all of $u_0,u_1,u_2,u_3$ are positive;
• $P$ is in outside of the tetrahedron $\iff$ any of $u_0,u_1,u_2,u_3$ is negative;
• $P$ is on a face of the tetrahedron $\iff$ one of $u_0,u_1,u_2,u_3$ is $0$ and all the other are positive;
• $P$ is on an edge of the tetrahedron $\iff$ two of $u_0,u_1,u_2,u_3$ are $0$ and all the other are positive;
• $P$ is a vertex of the tetrahedron $\iff$ three of $u_0,u_1,u_2,u_3$ are $0$ and the other one is positive ($=1$).

Answer 4

Let $p_1$, $p_2$, $p_3$ and $p_4$ be the vertices of the tetrahedron. Let $A$ be the $3\times 3$-matrix $\begin{pmatrix} p_1-p_4 & p_2-p_4 & p_3 - p_4\end{pmatrix}$ and $B = A^{-1}$.

For $(x,y,z) \in \mathbb{R}^3$, let $p=(x,y,z)$ and define $w = B(p-p_4)$ and $h = w_1+w_2+w_3$. Then the tetrahedron is the isosurface defined by $$\max(h - 1, -h, -w_1, -w_2, -w_3) = 0.$$ A point is inside the tetrahedron if and only if $\max(h - 1, -h, -w_1, -w_2, -w_3) \leqslant 0$.

Answer 5

Given the four vertices $A,B,C,D$ of a tetrahedron, you have the following four faces: ABC, ABD, ACD, BCD. Compute the normal vectors of the four faces, respectively, as follows

$n_1 = (B - A) \times (C - A) $

$n_2 = (B - A) \times (D - A) $

$ n_3 = (C - A) \times (D- A) $

$n_4 = (C - B) \times (D - B) $

Now we want all these normal vectors to be pointing outward. So what you do, is compute the centroid of the tetrahedron which is simply

$G = \dfrac{1}{4} (A + B + C + D) $

Remember the four faces are: ABC, ABD, ACD, BCD, so let $P_i = A$ for $i = 1,2,3$ , and $P_4 = B$

Now compute $\alpha_i = (G - P_i) \cdot n_i $

Since we want $n_i$ to be pointing outward, then we want $\alpha_i \lt 0 $ for all $i$. If $\alpha_i \gt 0 $ for some $i$ , then we reverse the direction of $n_i$.

Now we're done. Now given an arbitrary point $Q$, we can determine whether it is inside the tetrahedron, on the tetrahedron, or outside the tetrahedron by computing the following $\beta_i$'s

$ \beta_i = (Q - P_i) \cdot n_i $

If all $\beta_i \lt 0 $, then point $Q$ is inside the tetrahedron.

If one of the $\beta_i$'s is zero, and the other three are negative, then $Q$ is on a face of the tetrahedron.

If two of the $\beta_i$'s are zero, and the other two are negative, then $Q$ is on an edge of the tetrahedron.

If three of the $\beta_i$'s are zero, then $Q$ is at a vertex of the tetrahedorn.

If all the above conditions are not true, then $Q$ is outside the tetrahedron.

This last statement is equivalent to saying: If at least one of $\beta_i$'s is positive, then $Q$ is outside the tetrahedron.

Answer 6

From a coding point of view, the following is probably the easiest approach. Let’s denote the tetrahedron’s vertex coordinates by $P_i = (x_i, y_i, z_i)$, and denote the point we want to test by $P = (x, y, z)$. Use your favorite linear equation solving function to solve the system $$ \left[\begin{matrix} x_1 & x_2 & x_3 & x_4 \\ y_1 & y_2 & y_3 & y_4 \\ z_1 & z_2 & z_3 & z_4 \\ 1 & 1 & 1 & 1 \end{matrix}\right] \left[\begin{matrix} u_1 \\ u_2 \\ u_3 \\ u_4 \\ \end{matrix}\right] = \left[\begin{matrix} x \\ y \\ z \\ 1 \\ \end{matrix}\right] $$ This is just an alternative way of computing the barycentric coordinates $u_1, u_2, u_3, u_4$, and it’s trivial to implement if you already have (or can find) code to solve linear systems. Then test the values $u_1, u_2, u_3, u_4$ as in the answer from @mwt.