4
\$\begingroup\$

I am using the Möller-Trumbore method as part of my (still very basic) collision detection system.

The information I'm craving about is the distance from the ray origin and intersection point. The intersection point would be fine too obviously.

I probably wrongly assumed t in the code below is actually the distance from the ray origin to the intersection point. If it actually is, then I don't know what's wrong with my code.

I have got a simulation with a mesh and "bullets", sometimes firing a collision acurately, and sometimes not (bullets passing thru mesh, or firing a colision before it actually should hit).

bool rayTriangleIntersect(const XMFLOAT3 &orig, const XMFLOAT3 &dir, const XMFLOAT3 &v0, const XMFLOAT3 &v1, const XMFLOAT3 &v2, float &t, float &u, float &v) {
// http://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/moller-trumbore-ray-triangle-intersection

    float kEpsilon = 0.000001f;
    XMFLOAT3 v0v1 = v1 - v0;
    XMFLOAT3 v0v2 = v2 - v0;
    XMFLOAT3 pvec = XMFLOAT3Cross(dir, v0v2);

    float det = XMFLOAT3Dot(v0v1, pvec);

    if (det < kEpsilon) return false;

    float invDet = 1.0f / det;

    XMFLOAT3 tvec = orig - v0;
    u = XMFLOAT3Dot(tvec, pvec) * invDet;
    if (u < 0 || u > 1) return false;

    XMFLOAT3 qvec = XMFLOAT3Cross(tvec, v0v1);
    v = XMFLOAT3Dot(dir, qvec) * invDet;
    if (v < 0 || u + v > 1) return false;

    t = XMFLOAT3Dot(v0v2, qvec) * invDet;

    return true;
}

Is t really the distance im looking for ? If not how do I get it, or the intersection point. I've heard of baricentric coordinates in a triangle related to u and v - is it the way to go ? If yes I'd be thankful for an example or link related to the Möller-Trumbore method.

Thanks!

\$\endgroup\$
2
+50
\$\begingroup\$

One issue with your implementation is that you only check if det is smaller kEpsilon, but there is no guarantee that det is positive. You want to check

if(det<kEpsilon && det>-kEpsilon)

So that might explain the false positives. The way this algorithm works is by basically figuring out "when" the ray will hit the triangles plane and then checking if the position of the ray at that time is inside the triangle by transforming into barycentric coordinates.

You should be able to calculate the intersection point as:

intersection = v0+u*v0v2+v*v0v1;

That being said t should be the distance you are looking for anyway, so you might have an implementation problem.

There seems to be an excellent explanation here: http://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/moller-trumbore-ray-triangle-intersection

\$\endgroup\$
  • \$\begingroup\$ I thought det is positive when the ray is facing the visible (not culled) face of a triangle ? That is why I stripped checking det's sign. \$\endgroup\$ – PinkTurtle Jan 22 '16 at 10:36
  • \$\begingroup\$ It is, or should be depending on the orientation of your triangles. The sign definitely determines which side it's on. \$\endgroup\$ – Nils Ole Timm Jan 22 '16 at 11:22
  • \$\begingroup\$ Something is wrong in my implementation - I didn't figure out what yet. To detect a collision I'm asserting that the distance from a vertex last position to vertex current position must be bigger than t, with the ray given by both positions hitting the triangle obviously. Digging :) \$\endgroup\$ – PinkTurtle Jan 22 '16 at 11:27
  • \$\begingroup\$ An easy way to test this would be to draw the ray you are testing as well as the result from your intersection test. \$\endgroup\$ – Nils Ole Timm Jan 22 '16 at 11:32
  • 1
    \$\begingroup\$ Yo I switched from XMFLOAT data types with homemade cross and dot products to XMVECTOR and MS implemented methods. Now things look all right. Not sure where I failed but thanks for the help so far! I must have screwed my 3D math ;p \$\endgroup\$ – PinkTurtle Jan 22 '16 at 21:15
1
\$\begingroup\$

A standard parametric ray equation is r(t) = p + td. The origin point is p and d is the ray direction. So, that algorithm gives you t and you know p and d already. Therefore you can compute ray (or vector) r(t), and then take its magnitude |r(t)| to obtain the distance to triangle (intersection).

PS. You may need to normalize your direction vector d first. That is, ensure its of unit length. (The link you provided isn't clear if that's necessary though.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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