Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

share|improve this question
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. – melak47 May 8 '12 at 10:19
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. – uorbe001 May 8 '12 at 10:44

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
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) – uorbe001 May 8 '12 at 14:32
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. – melak47 May 8 '12 at 23:25
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. – uorbe001 May 9 '12 at 11:04
@uorbe001 Maybe compare your implementation against the D3D one: msdn.microsoft.com/en-us/library/windows/desktop/… – melak47 May 9 '12 at 15:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.