3
\$\begingroup\$

I'm trying to perform ray triangle intersection on a mesh made of triangles. The below code seems to work fine but only about 50% of the time. The ray often gets into positions where no intersection is detected when there definitely should be. Is there something wrong in my function that isn't checking for intersection under all circumstances.

bool rayTriangleIntersect(Vector3 rayOrigin, 
                          Vector3 rayDirection, 
                          Vector3 vert0, 
                          Vector3 vert1, 
                          Vector3 vert2, 
                          ref Vector3 intersectionPosition)
{
    // this originally comes from http://www.graphics.cornell.edu/pubs/1997/MT97.pdf

     float u, v, t, det, inv_det;          
     Vector3 edge1, edge2, pvec, tvec, qvec;

    Vector3 direction = rayDirection;
    direction.Normalize();
    t = v = u = 0f;
    edge1 = vert1 - vert0;
    edge2 = vert2 - vert0;
    pvec = Vector3.Cross(direction, edge2);
    det = Vector3.Dot(edge1, pvec);

    if (det > -0.00001f)
        return false;

    inv_det = 1.0f / det;
    tvec = rayOrigin - vert0;
    u = Vector3.Dot(tvec, pvec) * inv_det;

    if (u < -0.001f || u > 1.001f)
        return false;

    qvec = Vector3.Cross(tvec, edge1);
    v = Vector3.Dot(direction, qvec) * inv_det;

    if (v < -0.001f || u + v > 1.001f)
        return false;

    t = Vector3.Dot(edge2, qvec) * inv_det;

    float rayMagnitude = rayDirection.magnitude;

    if (t <= 0f || t >= rayMagnitude)
        return false;

    intersectionPosition = rayOrigin + (rayDirection * (t / rayMagnitude)); // percent along ray 

    return true;
}

and im calling it with

for (z = 0; z < LENGTH - 1; z++)
{
     for (x = 0; x < WIDTH - 1; x++)
     {
           v0 = verts[(z * WIDTH) + x];
           v1 = verts[((z + 1) * WIDTH) + x];
           v2 = verts[(z * WIDTH) + x + 1];
           v3 = verts[((z + 1) * WIDTH) + x + 1];

           if(rayTriangleIntersect(rayOrigin, rayDirection, v0, v1, v2, ref intersectPosition) ||   
              rayTriangleIntersect(rayOrigin, rayDirection, v1, v2, v3, ref intersectPosition))
           {  
                 Debug.log(Intersection found at : " intersectPosition);  
           }
    }
}

I'm really stuck on this one so any guidance would really be appreciated.

Edit

The triangle are defined like this:

 for (z = 0; z < LENGTH - 1; z++)
   {
        for (x = 0; x < WIDTH - 1; x++)
        {
            triangles[index++] = (z * WIDTH) + x;
            triangles[index++] = ((z + 1) * WIDTH) + x;
            triangles[index++] = (z * WIDTH) + x + 1;

            triangles[index++] = ((z + 1) * WIDTH) + x;
            triangles[index++] = ((z + 1) * WIDTH) + x + 1;
            triangles[index++] = (z * WIDTH) + x + 1;
        }
    }
\$\endgroup\$
6
  • \$\begingroup\$ Could you isolate such a circumstance? \$\endgroup\$
    – Bart
    Mar 6, 2012 at 12:51
  • \$\begingroup\$ I'm guessing this is checking against height mapped terrain? \$\endgroup\$ Mar 6, 2012 at 12:54
  • \$\begingroup\$ Same question, multiple sites? stackoverflow.com/q/9583831/925580 \$\endgroup\$
    – Lucius
    Mar 6, 2012 at 12:55
  • \$\begingroup\$ I'm working on it \$\endgroup\$
    – user346443
    Mar 6, 2012 at 13:10
  • 3
    \$\begingroup\$ Please don't crosspost. \$\endgroup\$
    – Ripped Off
    Mar 8, 2012 at 17:11

4 Answers 4

3
\$\begingroup\$

Try changing

 if (det > -0.00001f)
        return false;

to,

 if (det > -0.00001f && det < 0.00001f)
        return false;

Currently, your code only checks one side of the triangle

\$\endgroup\$
0
4
\$\begingroup\$

Your code seems to use quads and it seems that you don't use the two triangles from the quad but two overlapping ones (say the second one is wrong), try this instead (see the "v2, v3, v0" part) :

          if(rayTriangleIntersect(rayOrigin, rayDirection, v0, v1, v2, ref intersectPosition) ||   
          rayTriangleIntersect(rayOrigin, rayDirection, v2, v3, v0, ref intersectPosition))

If that doesn't work, you could try v0,v3,v1 or v1,v3,v2 or check out how your quads are actually built and figure it out.

\$\endgroup\$
6
  • \$\begingroup\$ Good point! He does seem to be using the wrong pair of triangles. \$\endgroup\$ Mar 6, 2012 at 13:14
  • \$\begingroup\$ I've added how the triangles are defined. \$\endgroup\$
    – user346443
    Mar 6, 2012 at 13:19
  • \$\begingroup\$ Then I think the second line should be v1, v3, v2 \$\endgroup\$
    – Valmond
    Mar 6, 2012 at 13:31
  • \$\begingroup\$ I've also tried each to the vertex combinations with no success. \$\endgroup\$
    – user346443
    Mar 6, 2012 at 13:38
  • \$\begingroup\$ @user346443 If different vertex combinations didn't work, have you verified if you're fetching the right vertices from the array? You could be indexing it incorrectly. \$\endgroup\$ Mar 6, 2012 at 13:50
4
\$\begingroup\$

I don't know what's the problem with your implementation, but I have used the method below (taken directly from this sample) on a raytracer and it worked correctly and performed well too. So you might consider swapping to this implementation:

/// <summary>
/// Checks whether a ray intersects a triangle. This uses the algorithm
/// developed by Tomas Moller and Ben Trumbore, which was published in the
/// Journal of Graphics Tools, volume 2, "Fast, Minimum Storage Ray-Triangle
/// Intersection".
/// 
/// This method is implemented using the pass-by-reference versions of the
/// XNA math functions. Using these overloads is generally not recommended,
/// because they make the code less readable than the normal pass-by-value
/// versions. This method can be called very frequently in a tight inner loop,
/// however, so in this particular case the performance benefits from passing
/// everything by reference outweigh the loss of readability.
/// </summary>
static void RayIntersectsTriangle(ref Ray ray,
                                  ref Vector3 vertex1,
                                  ref Vector3 vertex2,
                                  ref Vector3 vertex3, out float? result)
{
    // Compute vectors along two edges of the triangle.
    Vector3 edge1, edge2;

    Vector3.Subtract(ref vertex2, ref vertex1, out edge1);
    Vector3.Subtract(ref vertex3, ref vertex1, out edge2);

    // Compute the determinant.
    Vector3 directionCrossEdge2;
    Vector3.Cross(ref ray.Direction, ref edge2, out directionCrossEdge2);

    float determinant;
    Vector3.Dot(ref edge1, ref directionCrossEdge2, out determinant);

    // If the ray is parallel to the triangle plane, there is no collision.
    if (determinant > -float.Epsilon && determinant < float.Epsilon)
    {
        result = null;
        return;
    }

    float inverseDeterminant = 1.0f / determinant;

    // Calculate the U parameter of the intersection point.
    Vector3 distanceVector;
    Vector3.Subtract(ref ray.Position, ref vertex1, out distanceVector);

    float triangleU;
    Vector3.Dot(ref distanceVector, ref directionCrossEdge2, out triangleU);
    triangleU *= inverseDeterminant;

    // Make sure it is inside the triangle.
    if (triangleU < 0 || triangleU > 1)
    {
        result = null;
        return;
    }

    // Calculate the V parameter of the intersection point.
    Vector3 distanceCrossEdge1;
    Vector3.Cross(ref distanceVector, ref edge1, out distanceCrossEdge1);

    float triangleV;
    Vector3.Dot(ref ray.Direction, ref distanceCrossEdge1, out triangleV);
    triangleV *= inverseDeterminant;

    // Make sure it is inside the triangle.
    if (triangleV < 0 || triangleU + triangleV > 1)
    {
        result = null;
        return;
    }

    // Compute the distance along the ray to the triangle.
    float rayDistance;
    Vector3.Dot(ref edge2, ref distanceCrossEdge1, out rayDistance);
    rayDistance *= inverseDeterminant;

    // Is the triangle behind the ray origin?
    if (rayDistance < 0)
    {
        result = null;
        return;
    }

    result = rayDistance;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ +1 Nice sharing. I'm using the "c2005" code which works well for my collision detections :-) \$\endgroup\$
    – Valmond
    Mar 6, 2012 at 13:33
  • \$\begingroup\$ Cheers Dave. The functions are exactly the same so it proves that the function must be correct. So the issues must lay else where. \$\endgroup\$
    – user346443
    Mar 6, 2012 at 13:39
  • \$\begingroup\$ @user346443 Alright, I think it's safe to assume then that the problem is not with the intersection code but with the data you're passing it. Have you checked if the values of v0-v3 are really what you expect them to be? \$\endgroup\$ Mar 6, 2012 at 13:43
1
\$\begingroup\$

Without looking at the code in much detail, I'm going to take a guess that your triangle intersection routine only works from one side of the triangle, but your triangle "mesh" describes triangles with opposite "handedness" (if v0,v1,v2 is clockwise, then v1,v2,v3 is anticlockwise as seen by a ray from the same direction). This could be confirmed by e.g permuting the order of the latter to v1,v3,v2 and seeing if all or none of the tests succeed. If that is indeed the problem, and it's desired to have an intersection test succeed from either side of the triangle (rather than "back face culling"), then you probably need to handle the case of a negative "det" better.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .