Sign in to follow this  
Hnefi

Collision between line and sphere?

Recommended Posts

Heyall. I have an object - a sphere - represented as a point (pos.x, pos.y, pos.z) and a radius (rad). I have another object - a line - represented as an origin (orig.x, orig.y, orig.z) and a direction (dir.x, dir.y, dir.z). I need to know if and where these two intersect, preferrably using standard linear algebra. I don't know how. Any help is greatly appreciated.

Share this post


Link to post
Share on other sites
Just google 'ray sphere intersection', 'sphere raytrace', 'line sphere intersection', or something of the sort. The solution reduces to solving a simple quadratic, and is well documented online. (You might be able to find it in the articles section here on gdnet as well - I'm not sure.)

Share this post


Link to post
Share on other sites

//this is the code to get the distance between a line and a point (v1):
//---------------------------------------------------------------------

distance = crossProduct(line.directionVector, (v1-line.point)).length();

/*Note that the directionVector must be normalized first.
If the result of this is less than the radius, the line must intersect with the sphere.*/


//To get the coordinates of the points:
//-------------------------------------

point1 = line.point + [dotProduct((v1-line.point), line.directionVector)-sqrt(distance²-radius²)]*line.directionVector;
point2 = line.point + [dotProduct((v1-line.point), line.directionVector)+sqrt(distance²-radius²)]*line.directionVector;

//Note that also here the directionVector must be normalized first.


If you are going to do more of these vector calculations, you better start writing a math3D.cpp file. Or is there already such a thing out there?
If the speed of the collision code matters (is called MANY times) there is probably a better way.
(I havent tested this yet, but i'm quite sure it's not faulty)
Hope this helps.

[Edited by - Kwak on May 2, 2006 7:58:05 AM]

Share this post


Link to post
Share on other sites
Here's the code I use in my projects. It tells if, but not where...

bool RayIntersectsSphere( D3DXVECTOR3 raypt, D3DXVECTOR3 raydir, D3DXVECTOR3 spherept, float radius )
{
// get the vector from the raypoint to the position of the sphere
D3DXVECTOR3 v1 = spherept - raypt;
// get the dot product of the ray direction and v1
float dot = v1.x*raydir.x + v1.y*raydir.y + v1.z*raydir.z;
// get the point on the line
D3DXVECTOR3 linept = raypt + (raydir * dot);

// now check the distance between the line point and the sphere point (squared)
float dx = linept.x-spherept.x;
float dy = linept.y-spherept.y;
float dz = linept.z-spherept.z;
float dist = dx*dx + dy*dy + dz*dz;

// and compare
return (dist <= (radius*radius));
}

Share this post


Link to post
Share on other sites
It's easy to derive...

Where P is a point on the sphere and C and R are the center and radius of sphere.

(P.x - C.x)^2 + (P.y - C.y)^2 + (P.z - C.z)^2 = R^2
(P - C).(P - C) = R^2

Rewrite in terms of point on the ray (or "line").. D is ray direction, O is origin...

((O + t*D) - C).((O + t*D) - C) = R^2
((O-C) + t*D).((O-C) + t*D) = R^2
(O-C).(O-C) + 2*t*(O-C).D + t^2 * (D.D) = R^2
t^2 * [D.D] + t * [2 * (O-C).D] + [(O-C).(O-C) - R^2] = 0

So you have a quadratic formula situation...
A = D.D
B = 2 * (O-C).D
C = (O-C).(O-C) - R^2

Check the term under the radical (B^2 - 4AC) for a negative number first (if it's negative there is no intersection). If it is zero, your ray is tangent to the sphere. Otherwise, you have two intersections... unless you are inside of the sphere, you want to use the lower of the two.

Share this post


Link to post
Share on other sites
This site helped me a lot:
http://www.softsurfer.com/Archive/algorithm_0102/algorithm_0102.htm

Here's my implementation:

float LineSphereIntersection(CVector3 vOrigin, CVector3 vDirection, CVector3 vCenter, float Radius)
{
float t = Dot(vCenter - vOrigin, vDirection);
CVector3 closest = vOrigin + vDirection*t;
float dist_squared = LengthSquared(vCenter - closest);
if (dist_squared <= Radius * Radius)
{
return t;
}
else
{
return -1;
}

}

Share this post


Link to post
Share on other sites
well since this is the maths forum I'd suggest you to think about an mathematical approach by taking the lines vector as the normal vector for a plane/surface with the center of your sphere as a point, you have with the point and the vector of you line all information needed to create a plane/surface which you can check for intersection with the line in 3D space and then checking if the collision point on the plane/surface is within the 2D-circle with the radius of the sphere

sorry if not everything is clear but since englisch is not my mothertongue I don't know the proper terms

although I hope you can understand my approach and that it will help you somehow

cheers,
marcel

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this