3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Do you mean "over" the triangle in the context of a fixed global "up"/"down" direction (i.e., is your nav mesh aligned to a plane at all times?), or do you want to know if the point is "over" the triangle in the sense that it would be inside the volume created by extending the triangle into a prism along it's normal / perpendicular to the surcace? In either case, you could use a projection matrix to reduce the problem from 3D to 2D, in one case you would just need to use one matrix, in the other one per triangle. \$\endgroup\$ Commented May 8, 2012 at 10:19
  • \$\begingroup\$ I meant "over" as in extending the triangle into a prism along it's normal, I think in most cases the nav mesh will be aligned to a plane, but I don't want to limit my possibilities with this. \$\endgroup\$ Commented May 8, 2012 at 10:44

2 Answers 2

Reset to default
0
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ I've tried this using the orthocenter of the triangle as the eye position, and it doesn't seem to work, what are you referring to with the center of the triangle? (based onthis implementation of lookAt) \$\endgroup\$ Commented May 8, 2012 at 14:32
  • \$\begingroup\$ Hmm. Make sure that if you use the orthocenter, as eye position, that you use normalize(vertexPos - orthocenter) as the up direction, and orthocenter + normalDirection as the target position. \$\endgroup\$ Commented May 8, 2012 at 23:25
  • \$\begingroup\$ I haven't been able to build the projection matrix using lookUp, as far as I can tell it should indeed work, but I must have some mistake on the matrix implementation. I'll look into it later. For the time being, I've been able to build the projection matrix by setting the matrix diagonal to (1 - normal.x, 1 - normal.y, 1 - normal - z, 1). I'm not sure this works for all the normals though, so I'll probably have to change it soon enough. \$\endgroup\$ Commented May 9, 2012 at 11:04
  • \$\begingroup\$ @uorbe001 Maybe compare your implementation against the D3D one: msdn.microsoft.com/en-us/library/windows/desktop/… \$\endgroup\$ Commented May 9, 2012 at 15:39
  • \$\begingroup\$ How do you perform a 2D check to see if the point lies in the triangle? \$\endgroup\$ Commented Sep 25, 2023 at 4:43
3
\$\begingroup\$

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)); }
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.