In 3D, given three points $P_1$, $P_2$, and $P_3$ spanning a non-degenerate triangle $T$. How to determine if the projection of a point $P$ onto the plane of $T$ lies within $T$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
The question is a slight extension of the question given here: Check whether a point is within a 3D Triangle
There is an elegant solution to this given by W. Heidrich, Journal of Graphics, GPU, and Game Tools,Volume 10, Issue 3, 2005.
Let $\vec{u}=P_2-P_1$, $\vec{v}=P_3-P_1$, $\vec{n}=\vec{u}\times\vec{v}$, $\vec{w}=P-P_1$. We then have directly the barycentric coordinates of the projection $P'$ of $P$ onto $T$ as
- $\gamma=(\vec{u}\times\vec{w})\cdot\vec{n}/\left\lVert\vec{n}\right\rVert^2$
- $\beta=(\vec{w}\times\vec{v})\cdot\vec{n}/\left\lVert\vec{n}\right\rVert^2$
- $\alpha=1-\gamma-\beta$
The coordinates of the projected point is
- $P'=\alpha P_1+\beta P_2 +\gamma P_3$
The point $P'$ lies inside $T$ if
- $0\leq\alpha\leq 1$,
- $0\leq\beta\leq 1$, and
- $0\leq\gamma\leq 1$.
$\begingroup$
$\endgroup$
2
Thanks to Håkon Hægland for asking and answering this question, and especially for providing the key information from the hard-to-obtain paper: Wolfgang Heidrich, 2005, Computing the Barycentric Coordinates of a Projected Point, Journal of Graphics Tools, pp 9-12, 10(3).
I was web searching for exactly this information. Among the top hits were a question on the gamedev.stackexchange.com site, and this one. After implementing the technique presented here by Håkon, I posted that code and a link to this question at the game dev site: Easy way to project point onto triangle (or plane). Later it occurred that the C++/Eigen implementation might be useful to readers of this question:
bool pointInTriangle(const Eigen::Vector3f& query_point,
const Eigen::Vector3f& triangle_vertex_0,
const Eigen::Vector3f& triangle_vertex_1,
const Eigen::Vector3f& triangle_vertex_2)
{
// u=P2−P1
Eigen::Vector3f u = triangle_vertex_1 - triangle_vertex_0;
// v=P3−P1
Eigen::Vector3f v = triangle_vertex_2 - triangle_vertex_0;
// n=u×v
Eigen::Vector3f n = u.cross(v);
// w=P−P1
Eigen::Vector3f w = query_point - triangle_vertex_0;
// Barycentric coordinates of the projection P′of P onto T:
// γ=(u×w)⋅n/‖n‖²
float gamma = u.cross(w).dot(n) / n.dot(n);
// β=(w×v)⋅n/‖n‖²
float beta = w.cross(v).dot(n) / n.dot(n);
float alpha = 1 - gamma - beta;
// The point P′ lies inside T if:
return ((0 <= alpha) && (alpha <= 1) &&
(0 <= beta) && (beta <= 1) &&
(0 <= gamma) && (gamma <= 1));
}
-
3$\begingroup$ This can be done more easily without cross products. See gamedev.stackexchange.com/questions/23743/… $\endgroup$drawnonward– drawnonward2018-01-27 22:17:40 +00:00Commented Jan 27, 2018 at 22:17
-
1$\begingroup$ Even if you use cross products like this, the code here has a bit of overkill: the <=1 tests aren't needed; and if you get rid of those, then the scaling of alpha,beta,gamma doesn't matter so you can omit the
/n.dot(n)s (but then replace the 1 byn.dot(n)in the expression for alpha). $\endgroup$Don Hatch– Don Hatch2025-07-01 13:23:39 +00:00Commented Jul 1 at 13:23