Easy way to project point onto triangle (or plane)

Question

I have a mesh of triangles (navigation mesh), and a point in 3d space. This point should be "over" one of the triangles all the times. I'm trying to determine which triangle is the one the point is "over", but I can't quite figure it out.

I have found a way to tell if the point is in the triangle using one of the techniques described here, but I can't quite figure out how to project the point on the triangle (or the plane the triangle is in, for that matter). I've been looking online but I can't find anything helpful.

Does anyone know how to project a point onto a triangle (or plane)?

Also, if someone knows of a better way to test which triangle is the one the point is over, it would be appreciated.

Answer 1

In that case, create an orthogonal projection matrix oriented along that normal, then transform the triangle's vertices and your point through multiplication, and it should becomes a simple 2D check to see if the point lies in the triangle (volume).

Additionally, you would aso have a Z value you could use to discard points too high above the triangle.

LookAtLH is how you could do this in D3D/XNA for example, EyePosition could be the center of your triangle, Focus would be EyePosition + normal, and updirection should be anything perpendicular to that, i.e. any of the vertices of the triangle should work.

I'm sure you can find the source for a similar LookAt transformation matrix with a little googling if you don't want to use a whole library just for one function.

Answer 2

There is an excellent answer to this question on the Math community of Stack Exchange: Determine if projection of 3D point onto plane is within a triangle. Which is, in turn, just a summary of this paper in Journal of Graphics Tools: Wolfgang Heidrich, 2005, Computing the Barycentric Coordinates of a Projected Point, Journal of Graphics Tools, pp 9-12, 10(3).

The transformation of the original query point to barycentric coordinates can be thought of allowing a simple conversion to a point (P’) on the plane of the triangle, or equivalently, of testing whether the query point is within an infinite triangular prism extending perpendicularly from the triangle. Here is some C++ code using the Eigen library, returning a boolean value based on four points: the query point and the vertices of the triangle. (The comments come directly from the math.stackexchange.com page cited above, except that \$\vec u\$ is written as \$u\$ because of typesetting issues.)

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));
}