0
$\begingroup$

In my game I have 3 points that create a triangular plane similar to the image below but with uniform coordinates:

enter image description here

Each tringle is made of 3 points e.g.

P0 (x,y,z)

P1 (x,y,z)

P2 (x,y,z)

I also have the point:

P (x,y,z)

As shown in the diagram below, is is possible to tell if the plane created by P0, P1 & P2 passes through P?

enter image description here

I have looked online however all results do not seem to fit the problem in a programming orientated approach. Ideally i'd like to pass the coordinates to a function/equation and get a true/false result.

Thanks

$\endgroup$
2
  • $\begingroup$ Do you know how to solve the equation of a plane given 3 points? $\endgroup$ Dec 27, 2017 at 19:37
  • $\begingroup$ Do you also want to test if the point lies within the triangle or just whether or not it’s on the triangle’s plane? $\endgroup$
    – amd
    Dec 27, 2017 at 19:50

3 Answers 3

2
$\begingroup$

The solution has two phases:

  1. Find if the point belongs to the plane. The easiest way is to calculate the distance of point to the plane, by projecting along the plane normal $\mathbf{n} = {\rm UnitVector}[ \mathbf{P}_0 \times \mathbf{P}_1 + \mathbf{P}_1 \times \mathbf{P}_2 + \mathbf{P}_2 \times \mathbf{P}_0] $ $$ d= \mathbf{n} \cdot (\mathbf{P}-\mathbf{P}_0) \approx 0 $$ NOTE: here $\cdot$ is the vector dot product and $\times$ the vector cross product.

  2. Find the barycentric coordinates of the point $w_0$, $w_1$ and $w_2$ and check if all values are between zero and one, $0 \le w_i \le 1$.

    This is accomplished using a matrix $\mathcal{A}$ with columns the homogeneous coordinates of the three points $$\mathcal{A} = \left| \matrix{x_0 & x_1 & x_2 \\ y_0 & y_1 & y_2 \\ z_0 & z_1 & z_2 \\ 1 & 1 & 1 } \right| $$

    The barycentric coordinates are found with the pseudo-inverse of $\pmatrix{\mathbf{P} \\ 1} = \mathcal{A} \mathbf{w}$ $$ \pmatrix{w_0 \\ w_1 \\ w_2} = \left(\mathcal{A}^\top \mathcal{A} \right)^{-1} \mathcal{A}^\top \pmatrix{x\\y\\z\\1} $$ where $\pmatrix{x&y&z&1}^\top$ are the homogeneous coordinates of the point in question.

Example:

  • $\mathbf{P}_0 = \pmatrix{1 & 1 & 1}^\top$, $\mathbf{P}_1 = \pmatrix{5 & 1 & 1}^\top$, $\mathbf{P}_2 = \pmatrix{2 & 3 & 5}^\top$ and $\mathbf{P} = \pmatrix{3 & 2 & 3}^\top$

pic

  • Find normal vector $$ \mathbf{n} = \frac{ (\mathbf{P}_1-\mathbf{P}_0) \times (\mathbf{P}_2-\mathbf{P}_0)}{ \| (\mathbf{P}_1-\mathbf{P}_0) \times (\mathbf{P}_2-\mathbf{P}_0) \| } = \pmatrix{0 \\ -\frac{2}{\sqrt{5}} \\ \frac{1}{\sqrt{5}} }$$

  • Check that distance to plane is zero $$d = \mathbf{n} \cdot (\mathbf{P}-\mathbf{P}_1) = 0\;\checkmark$$

  • Build coefficient matrix $$\mathcal{A} = \left| \matrix{\mathbf{P}_0 & \mathbf{P}_1 & \mathbf{P}_2 \\ 1 & 1 & 1} \right| = \left| \matrix{1 & 5 & 2\\ 1 & 1 & 3 \\ 1 & 1 & 5 \\ 1 & 1 & 1} \right| $$

  • Find barycentric coordinates

$$\pmatrix{w_0 \\ w_1 \\ w_2} = \left( \left| \matrix{1 & 5 & 2\\ 1 & 1 & 3 \\ 1 & 1 & 5 \\ 1 & 1 & 1} \right|^\top \left| \matrix{1 & 5 & 2\\ 1 & 1 & 3 \\ 1 & 1 & 5 \\ 1 & 1 & 1} \right| \right)^{-1} \left| \matrix{1 & 5 & 2\\ 1 & 1 & 3 \\ 1 & 1 & 5 \\ 1 & 1 & 1} \right|^\top \pmatrix{3\\2\\3\\1} = \pmatrix{\frac{1}{8} \\ \frac{3}{8} \\ \frac{1}{2} } $$

  • Since all coordinates $w_0$, $w_1$ and $w_2$ are postive and less than one the point is inside the triangle.

You can find the barycentric coordinates $w_0$, $w_1$ and $w_2$ from the above system of equations after some of the linear algebra is worked out

$$ \begin{bmatrix} 1 + \mathbf{P}_0 \cdot \mathbf{P}_0 && 1 + \mathbf{P}_0 \cdot \mathbf{P}_1 && 1 + \mathbf{P}_0 \cdot \mathbf{P}_2 \\ 1 + \mathbf{P}_1 \cdot \mathbf{P}_0 && 1 + \mathbf{P}_1 \cdot \mathbf{P}_1 && 1 + \mathbf{P}_1 \cdot \mathbf{P}_2 \\ 1 + \mathbf{P}_2 \cdot \mathbf{P}_0 && 1 + \mathbf{P}_2 \cdot \mathbf{P}_1 && 1 + \mathbf{P}_2 \cdot \mathbf{P}_2 \end{bmatrix} \begin{pmatrix} w_A \\ w_B \\ w_C \end{pmatrix} = \begin{pmatrix} 1 + \mathbf{P}_0 \cdot \mathbf{P} \\ 1 + \mathbf{P}_1 \cdot \mathbf{P} \\ 1 + \mathbf{P}_2 \cdot \mathbf{P} \end{pmatrix} $$


See related answer on how to check if a point is inside a triangle in 2D.

$\endgroup$
2
$\begingroup$

Compute the volume $V$ of the tetrahedron formed by $P, P_1, P_2, P_3$ by any formula you know. e.g. $$V = \frac16 |(P_1 - P)\cdot((P_2 - P)\times(P_3 - P))| = \frac16\left\|\begin{matrix} x_1 - x & x_2 - x & x_3 - x\\ y_1 - y & y_2 - y & y_3 - y\\ z_1 - z & z_2 - z & z_3 - z\end{matrix}\right\|$$ The point $P$ falls into the plane if and only if $V$ is $0$.

Assume $P$ falls within the plane. If you need to further test whether $P$ is inside $\triangle_{P_1P_2P_3}$, you can compute the area of the four triangles $\triangle_{PP_1P_2}$, $\triangle_{PP_2P_3}$, $\triangle_{PP_3P_1}$ and $\triangle_{P_1P_2P_3}$ by any formula you know, e.g.

$$A_{PP_1P_2} = \verb/Area/(\triangle_{PP_1P_2}) = \frac12| (P_1 - P)\times(P_2 - P)|$$ Point $P$ will be on or within the triangle if and only if

$$A_{PP_1P_2} + A_{PP_2P_3} + A_{PP_3P_1} = A_{P_1P_2P_3}$$

$\endgroup$
3
  • $\begingroup$ Nice... but do we really need the factor of one sixth for this problem? ;) $\endgroup$ Dec 27, 2017 at 20:03
  • $\begingroup$ @ColmBhandal for the test, the 1/6 factor is not needed. It is here just to show the geometric origin of the test. $\endgroup$ Dec 27, 2017 at 20:06
  • $\begingroup$ Yeah cool I just want to make sure that the computer program this guy is writing does not become inefficient! $\endgroup$ Dec 27, 2017 at 20:07
1
$\begingroup$

Here is, at a high level, what you need to do in your program:

  1. Calculate the equation of the plane using the three points. You can use linear algebra i.e. matrices to do this.
  2. Plug the point you're checking into the equation. If it satisfies the equation, it's in the plane, else it's not.

As a programmer, you'd need to be concerned about accuracy here. Computers can only solve things to finite precision, so just remember that when doing your calculations!

EDIT: As amd correctly points out- this calculates whether the point is in the same plane as the triangle. It doesn't tell you that the point is within the triangle itself.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .