Fast Ray Sphere collision code [closed]

Question

I am looking at here and while it's well organized a lot of links are broken: http://www.realtimerendering.com/intersections.html

I am trying to find fast code that will give me the hit point and the normal of the hit point on the sphere. I saw a lot of functions that only checks if there is collision but nothing else.

I looked at Real Time Collision Detection book but it doesn't seem to have it either.

Any ideas?

Answer 1

Real Time Collision Detection does indeed have this information - look at section '5.3.2 Intersecting Ray or Segment Against Sphere', page 178/179 in my copy.

I'm not sure if it is okay to reproduce the code but I found many copies of it online (google books, for example) - here it is verbatim from Real Time Collision Detection:

UPDATE: The following sample returns the interval T along the ray and the point of intersection Q.

You can calculate the normal of the contact by subtracting the center point of the sphere from the contact point and normalizing it.

// Intersects ray r = p + td, |d| = 1, with sphere s and, if intersecting, 
// returns t value of intersection and intersection point q 
int IntersectRaySphere(Point p, Vector d, Sphere s, float &t, Point &q) 
{
Vector m = p - s.c; 
float b = Dot(m, d); 
float c = Dot(m, m) - s.r * s.r; 

// Exit if r’s origin outside s (c > 0) and r pointing away from s (b > 0) 
if (c > 0.0f && b > 0.0f) return 0; 
float discr = b*b - c; 

// A negative discriminant corresponds to ray missing sphere 
if (discr < 0.0f) return 0; 

// Ray now found to intersect sphere, compute smallest t value of intersection
t = -b - Sqrt(discr); 

// If t is negative, ray started inside sphere so clamp t to zero 
if (t < 0.0f) t = 0.0f; 
q = p + t * d; 

return 1;
}

Answer 2

Here's something off the top of my head, trying to minimize expensive operations, without resorting to approximation hacks (ie. with infinite precision real numbers, the algorithm below is exactly correct, although in practice finite precision will introduce numerical errors). Recommendations/edits to improve performance are welcome.

Let s be the start point of the ray, and d a unit vector in the direction of the ray.

Let c be the center point of the sphere, and r its radius.

For simplicity, I'll assume that you only want points on the ray where it enters or kisses the sphere, forward from the start point. Intersections behind the start point, or exiting the sphere, are ignored (this means a ray originating inside the sphere detects no collision).

// Calculate ray start's offset from the sphere center
float3 p = s - c;

float rSquared = r * r;
float p_d = dot(p, d);

// The sphere is behind or surrounding the start point.
if(p_d > 0 || dot(p, p) < rSquared)
 return NO_COLLISION;

// Flatten p into the plane passing through c perpendicular to the ray.
// This gives the closest approach of the ray to the center.
float3 a = p - p_d * d;

float aSquared = dot(a, a);

// Closest approach is outside the sphere.
if(aSquared > rSquared)
  return NO_COLLISION;

// Calculate distance from plane where ray enters/exits the sphere.    
float h = sqrt(rSquared - aSquared);

// Calculate intersection point relative to sphere center.
float3 i = a - h * d;

float3 intersection = c + i;
float3 normal = i/r;
// We've taken a shortcut here to avoid a second square root.
// Note numerical errors can make the normal have length slightly different from 1.
// If you need higher precision, you may need to perform a conventional normalization.

return (intersection, normal);

Answer 3

Given a ray defined as:

x = x1 + (x2 - x1)*t = x1 + i*t
y = y1 + (y2 - y1)*t = y1 + j*t
z = z1 + (z2 - z1)*t = z1 + k*t

$$ \begin{align} x &= x_1 + t(x_2 - x_1) = x_1 + it \\ y &= y_1 + t(y_2 - y_1) = y_1 + jt \\ z &= z_1 + t(z_2 - z_1) = z_1 + kt \end{align} $$

and a sphere defined as:

(x - l)**2 + (y - m)**2 + (z - n)**2 = r**2

$$ (x - l)^2 + (y - m)^2 + (z - n)^2 = r^2 $$

Substituting in gives the quadratic equation:

a*t**2 + b*t + c = 0

$$ at^2 + bt + c = 0 $$

where:

a = i**2 + j**2 + k**2
b = 2*i*(x1 - l) + 2*j*(y1 - m) + 2*k*(z1 - n)
c = (x1-l)**2 + (y1-m)**2 + (z1-n)**2 - r**2;

$$ \begin{align} a &= i^2 + j^2 + k^2 \\ b &= 2i(x_1 - l) + 2j(y_1 - m) + 2k(z_1 - n) \\ c &= (x_1-l)^2 + (y_1-m)^2 + (z_1-n)^2 - r^2 \end{align} $$

If the discriminant of this equation is less than 0, the line does not intersect the sphere. If it is zero, the line is tangential to the sphere and if it is greater than zero it intersects at two points. Solving the equation and substituting the values of t into the ray equation will give you the points.

Source (copy-paste from): http://www-labs.iro.umontreal.ca/~sherknie/articles/faq_Divers/graphics-algorithms-faq.txt