Hi guys,

I have this problem:

I have a point as vector3 (x,y,z) in 3d space, and its direction (vector3 x,y,z).

In the scene there are also many triangles eachone with 3 vertex (each vertex as a vector3)

this point moves along its direction, how can I know:

1. what triagle is hitted (I have many of them)

2. where exactly is hitted, as x,y,z coordinates

I'm using c++ for my project.

Thanks

Search ray triangle intersection in google. Usually first you need to solve a plane x ray intersection, then you need to check whether the point is in the triangle or outside of it. There are numerous methods to do it and plenty of articles and code about it.

EDIT:

And here's what I would do:

Using analytical geometry, first I define a ray v = v0 + t*d, where v0 is the point in 3d where the ray starts, d is the directional vector of the ray and t>=0.

Let's assume that the triangle has vertices p0,p1,p2 we can get the normal by n = (p1-p0)x(p2-p0)

After that we can get a plane equation from this normal and the coordinate of one of the vertices:

Let's assume (ux,uy,uz) is a point on the plane defined by the normal n = (nx,ny,nz) and the point p0 = (p0x,p0y,p0z) then:

nx*(ux-p0x) + ny*(uy-p0y) + nz*(uz-p0z) = 0, or n*(u-p) = 0, where * is the dot product.

So by taking the ray equation and the plane equation we solve for t.

v = v0+ t*d

n*(u-p) = 0

if v is a point of the plane then:

n*(v0+t*d-p) = 0 => t = n*(p-v0)/(n*d) (remember to check for the cases where the ray lies in the plane = infinite number of solutions, or where the ray is parallel to the plane = no intersection)

And that's half the problem solved. Next you just decide whether the point with t = n*(p-v0)/(n*d) is inside the triangle or not (use barycentric coordinates, or you can do it with vector products).

P.S. I am pretty sure there was even an article on this on gamedev.net. Here it is: http://www.gamedev.net/page/resources/_/technical/math-and-physics/intersection-math-algorithms-learn-to-derive-r3033 , http://www.gamedev.net/page/resources/_/technical/math-and-physics/advanced-intersection-test-methods-r3536

check out the raypick demo in directx sdk. it does exactly that.

mouse click defines a ray from the pinhole camera into the scene. the demo then does an intersect test with a complex mesh, returning the submesh #, triangle index, and the coords of intersection (as i recall).

If speed is a consideration, a fast implementation is the Moller-Trumbore algorithm. It requires only 2 cross products per triangle test, and returns the distance from the ray origin to the triangle. The hit position can then be calculated as origin + hitDistance * normalized(ray-direction), after the triangle of interest is found.

If you want to keep track of which triangle was hit (assuming you want the closest hit):

// assume function raycast is your implementation of the algorithm, and returns true or false for a hit.
// rayDirection must be normalized (i.e., length = 1)
// v0, v1 and v2 comprise the triangle to be tested
bool raycast(Vector3 v0, Vector3 v1, Vector3 v2, Vector3 rayOrigin, Vector3 rayDirection, float* distance);

float minDistance = FLT_MAX;
float hitDistance;
int hitTriangle = -1;
Vector3 hitPosition;

for(int i=0; i < numTriangles; ++i)
{
   if( raycast( triangles[ i ].v0, triangles[ i ].v1, triangles[ i ].v2, rayOrigin, rayDirection, &hitDistance ) && hitDistance < minDistance )
   {
      minDistance = hitDistance;
      hitTriangle = i;
   }
}
if( hitTriangle > -1 )
{
   hitPosition = rayOrigin + hitDistance * rayDirection;
}
// results in a hit IF hitTriangle > -1, and hitPosition as required.

To speed up the collision detection for a large number of triangles, at the expense of memory, you can pre-compute a bounding sphere for each triangle when the mesh is loaded. Do a ray-sphere collision test (much faster than a ray-triangle test) for each triangle. Perform the ray-triangle test only if the ray-sphere collision test returns true.

Common practice is to perform broad-phase tests for groups of triangles (bounding box or bounding sphere) before testing individual triangles.

Thanks a lot for all the answers guys, tomorrow I'l try to do all