mouse to ray - sphere collision detection

Question

I have been trying to get a working algorithm that detects intersection between a ray (representing the bullets from a gun) and a sphere around the enemy.... I tried a few found on the net but none seems to work properly, maybe I am doing something wrong...

This is the one I am currently using:

    //// Ray-sphere intersection. 
    // p=(ray origin position - sphere position),
    // d=ray direction,
    // r=sphere radius,
    // Output:
    // i1=first intersection distance,
    // i2=second intersection distance
    // i1<=i2
    // i1>=0
    // returns true if intersection found,false otherwise.// 


    bool Player::RaySphereIntersect(const Vector3 &p, const Vector3 &d, double r,                 double  &i1, double &i2){ 
double det,b;   
b = -Vector3::dot(p,d); 
det = b*b - Vector3::dot(p,p) + r*r;    
if (det<0){     
    return false;   
}   
det= sqrt(det); 
i1= b - det;    
i2= b + det;    

// intersecting with ray?   
if(i2<0) 
    return false;   
if(i1<0)
    i1=0;   
return true;
    }

Where I use the position of the enemy as sphere position, roughly the position of the player's gun as ray origin and the projected mouse coordinates for ray direction... This is the OpenGL code I am using to project the mouse coords to the the far plane:

    Vector3 projectedMouse(float mx, float my){

GLdouble model_view[16];
GLint viewport[4];
GLdouble projection[16];

GLfloat winX, winY, winZ;
GLdouble dx, dy, dz, bx, by, bz;

glGetDoublev(GL_MODELVIEW_MATRIX, model_view);
glGetDoublev(GL_PROJECTION_MATRIX, projection);
glGetIntegerv(GL_VIEWPORT, viewport);

winX = (float)mx;
 winY = (float)viewport[3] - (float)my;

glReadPixels ((int)mx, (int)winY, 1, 1, GL_DEPTH_COMPONENT, GL_FLOAT, &winZ); 
gluUnProject(winX, winY, 1, model_view, projection, viewport, &dx, &dy, &dz);

projectedAim = Vector3(dx, dy, dz);

return projectedAim;
    }

Which seems right cos I am drawing a GL Line with it and it looks fine... So maybe it's the intersection code, but nothing seems to work.... I tried this other one that should return the intersection point distance, but for any given enemy position, it still gives me very random results:

    double intersectRaySphere(Vector3 rO, Vector3 rV, Vector3 sO, double sR) 
       Vector3 Q = sO-rO;
       double c = Q.magnitude();
       double v = Vector3::dot(Q,rV);
       double d = sR*sR - (c*c - v*v);

       // If there was no intersection, return -1
       if (d < 0.0) return (-1.0f);

       // Return the distance to the [first] intersecting point
       return (v - sqrt(d));

they have both been slightly modified to match the Math function in the library that I am using.... can anyone spot something wrong with them, or suggest another one? this is driving me crazy....

Thank you!

Narrow it down: Is the problem in your intersection code or your OpenGL state read/interpretation? — genpfault
it's the intersection for sure as the a line is being drawn as it should, therefore the mouse coordinates and the projection seems ok! — Alex

EnabrenTane EnabrenTane · Accepted Answer · 2011-11-04T21:50:12

It looks like you are doing something with Cramer's rule to solve for intersection. Consider substitution. The roots of the polynomial will tell you the points of intersection.

Starting with the 2D case what we want is to see if the orthogonal (and thus the minimum) distance of the point P located at the center of circle C has a distance less than the radius R of the circle C.

Basically. We find the minimum distance between the center of the circle and your ray/line. How do we do this? There are a few ways.

We know the shortest distance is a straight line that has the orthogonal slope (in R2 negative recip ) to our ray starting at the middle of the circle. We then find the intersection between our two lines. if we had to go more than length R we are outside and we don't care how far it is.

http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html

Solving the intersection of two lines and seeing it the intersection is further than R may not be the most efficient approach but fortunately wolfram has a better way to do essentially the same thing using higher level math.

Now considering a ray in R3 intersecting a sphere its basically the same thing, but "orthogonal" is harder to please than in R2, so we use double cross products. and solve parametric equations.

http://www.cs.umbc.edu/~olano/435f02/ray-sphere.html

This is a clever way to see if any portion of our ray satisfies the equation of our sphere as a constraint.

float a = Vector3::dot(d,d);
float b = Vector3::dot(d * 2, p); 
float c = Vector3::dot(p,p) - r*r
// if the discriminant of the quadratic formula is positive
// we have at least one intersection
return (b*b - 4 * a * c) >= 0

In short. I only found Cramer's rule helpful in differential equations when my columns were functions and its derivitives. Usually when finding the Wronskian.

mouse to ray - sphere collision detection

1 Answers