0

I'm struggling with implementing a robust ray sphere intersection routine in 2d. I hacked a rather hudge function together which I'm unable to properly debug since it runs on the GPU. I got my inspiration from: Circle line-segment collision detection algorithm? and http://paulbourke.net/geometry/sphereline/. I have no idea where I should look for the error. Am I missing something obvious? The case where I check if the circle encloses the line is returned as a intersection since I'm interested in actual circle segment collision.

Here's the relevant code snippet:

bool CircleSegmentIntersection2d(float2 x0, float2 x1, float2 center, float r) {

float2 d = x1-x0;
float2 f = x0-center;

float a = dot2d(d,d);
float b = 2*dot2d(f,d);
float c = dot2d(f,f)-r*r;

float discriminant = b*b-4*a*c;

if( discriminant < 0 ) {
      // no intersection
      return false;
} else {
    discriminant = sqrt(discriminant);
    // either solution may be on or off the ray so need to test both
    float sol1 = (-b + discriminant)/(2*a);
    float sol2 = (-b - discriminant)/(2*a);

    float t0 = min(sol1, sol2);
    float t1 = max(sol1, sol2);

    if (t1 < 0)
        return false;

    // Line segment doesn't intersect and on outside of sphere, in which case both values of t will either be less than 0 or greater than 1.
    if (0 < t0 && 0 < t1 || t0 > 1 && t1 > 1)
        return false;

    // Line segment doesn't intersect and is inside sphere, in which case one value of t will be negative and the other greater than 1.
    if (t0 < 0 && t1 > 1) {
        return true;
    }

    // Line segment intersects at one point, in which case one value of t will be between 0 and 1 and the other not.
    if (t0 < 0 && 0 <= t1 && t1 <= 1) {
        return true;
    }

    // Line segment intersects at two points, in which case both values of t will be between 0 and 1.
    if (0 <= t1 && t1 <= 1 && 0 <= t0 && t0 <= 1) {
        return true;
    }

    // Line segment is tangential to the sphere, in which case both values of t will be the same and between 0 and 1.
    if (length(t0-t1) < 0.005f) {
        return true;
    }
}

return false;

}

where dot2d is defined by:

float dot2d(float2 a, float2 b) {
return a.x*b.x+a.y*b.y;
}

Thanks for your time!

Olivier Moindrot
  • 27,908
  • 11
  • 92
  • 91
anopheles
  • 434
  • 1
  • 9
  • 19
  • Do you know which corner case fails? – Blender Jul 08 '12 at 05:17
  • I think I forgot a case where it says: `// Line segment intersects at one point, in which case one value of t will be between 0 and 1 and the other not.` I've added `if ((t1 > 1 && 0 <= t0 && t0 <= 1)) {` but it still doesnt seem to work. – anopheles Jul 09 '12 at 04:01
  • This seems to cause the issue: `if ((0 < t0 && 0 < t1) || (t0 > 1 && t1 > 1))` It should actually be: `if ((0 > t0 && 0 > t1) || (t0 > 1 && t1 > 1))` – anopheles Jul 09 '12 at 04:12

0 Answers0