9

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$?

Håkon Hægland
  • 403

2 Answers2

10

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=\left[(\vec{u}\times\vec{w})\cdot\vec{n}\right]/\vec{n}^2$
  • $\beta=\left[(\vec{w}\times\vec{v})\cdot\vec{n}\right]/\vec{n}^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$.
amWhy
  • 209,954
Håkon Hægland
  • 403
  • Are there any corner cases where this should fail? The paper doesn't say anything to it – Basit Anwer Nov 29 '17 at 11:41
  • Doesn't this only work if point P already lies on the plane created by the triangle [P1,P2,P3]? – MasterHD Oct 25 '18 at 08:59
  • @MasterHD The point is projected onto the plane, so it does not have to lie on the plane. – Håkon Hægland Oct 25 '18 at 09:11
  • Quick question... in the equations for gamma and beta, what on earth is this "[" and this "]".

    I imagine it must mean "signed magnitude" and explicitly not just magnitude (for the author would have written | or || , plus Craig's answer below codes it as such), but I can't find something online to confirm what [ and ] are meaning here.

     – Xenial Dec 08 '19 at 05:07
  • 1
    @Xenial They are just the ordinary grouping brackets. Note that they are not necessary in this case. – Håkon Hægland Dec 08 '19 at 08:10
  • What is $/\vec{n}^2$? The square root of n squared? What does it mean to square a vector in this context? – Aaron Franke Sep 25 '23 at 04:36
4

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));
}
Craig Reynolds
  • 151
  • 2
    This can be done more easily without cross products. See https://gamedev.stackexchange.com/questions/23743/whats-the-most-efficient-way-to-find-barycentric-coordinates – drawnonward Jan 27 '18 at 22:17