Friday, October 9, 2009

Ray - Circle intersection test.

If you are writing a game or any computer graphics applications you may want to check for intersections like triangle-triangle, triangle-ray, sphere-ray-sphere-sphere,Box-Triangle etc...There exists different algorithms for finding this.. Separating Axis theorem (SAT) seems to be a good option.

Following code written in c++ find intersection between a circle and line ( or ray-circle ). it will return true if there is intersection.Other function parameters are described in next lines.
vOrginCircle : center of the circle , r is the radius , vtLineStart: Line start point, vtLineEnd : Line end point, outIp : intersecting point..

As you can see it is easy to extend this method for finding ray-sphere intersection. just add a 'z' coordinate :)

bool IntersectLineCircle(vector vOrginCircle, double r,vector vtLineStart, vector vtLineEnd, vector& outIp)
{
vector vOrginNew = vOrginCircle - vtLineStart;
vector vtRay = (vtLineEnd - vtLineStart).normalize();
double b = vOrginNew.x* vtRay.x + vtRay.y * vOrginNew.y;
double c = r*r - ( vOrginNew.Norm2() );
double a = vtRay.Norm2(); // Norm2() is x*x + y*y

double diva = 1.0F/a;
// Negative doesn't have square root.
if( (b*b + a * c ) <= 0 ) return false;
double b4ac = sqrt( (b*b + a * c ) );
double l1 = (b - b4ac) * diva;
double l2 = (b + b4ac) * diva;

// we need the closest intersection point.. so find smaller l.
// To get the other end , just change the comparison operator.
double l = l1 <>

// find the intersecting point
outIp = (vtRay * l) + vtLineStart;

return true;
}