0
\$\begingroup\$

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?

\$\endgroup\$

closed as unclear what you're asking by doppelgreener, Gnemlock, Engineer, Alexandre Vaillancourt, Anko Jun 15 '17 at 21:06

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks but I meant it doesn't have the info where the function returns the hit point on the sphere. \$\endgroup\$ – Joan Venge Mar 12 '15 at 18:09
  • \$\begingroup\$ Haha, neat - I wasn't looking at this code when I wrote my answer (I've sadly never read Real Time Collision Detection) but it's remarkable how similar they are. I hope that means I'm on a good track with regard to efficiency. ;) \$\endgroup\$ – DMGregory Mar 12 '15 at 19:06
  • \$\begingroup\$ @JoanVenge the hit point, q, is passed back by reference. Also, it can be constructed from the ray with the ray and the hit distance t. \$\endgroup\$ – stephen Jul 21 '18 at 1:09
2
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ I always get the other side of the sphere as the result, not the actual first hit. What can I do about this? -- Edit: After thinking about what the code actually does, the answer was pretty simple. I just had to turn i = a - h * d into i = a + h * d :) \$\endgroup\$ – Niklas R Jan 26 '17 at 14:27
  • \$\begingroup\$ I just noticed I passed d pointing into the opposite direction (away from the sphere). Now that I pass in the correct direction, i don't get any hits because p_d = dot(p, d) is below zero. It works again if I do if (p_d > 0 || p.dot(p) < rSquared) instead.. I'm a bit confused why, but now it works. pastebin.com/QmAPwyTs \$\endgroup\$ – Niklas R Jan 26 '17 at 15:33
  • \$\begingroup\$ @NiklasR Good catch, I think this was a typo on my part a couple years ago. If I've read this correctly, the test should indeed be p_d > 0 - which expresses the case that the starting point is past the sphere's center along the ray direction (ie. the sphere is behind the ray). I've fixed this with an edit. \$\endgroup\$ – DMGregory Jan 26 '17 at 19:43
  • \$\begingroup\$ Why NO_COLLISION if the sphere is surrounding the start point? There should be one intersection point! \$\endgroup\$ – zwcloud Mar 23 at 3:02
  • \$\begingroup\$ It's conventional to treat game colliders as one-sided, so we only hit them on the way in, not on the way out. I mention that here: '"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)." If you're using a different convention, you can skip that early-out and compute an intersection for that case instead. \$\endgroup\$ – DMGregory Mar 23 at 3:05
0
\$\begingroup\$

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

and a sphere defined as:

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

Substituting in gives the quadratic equation:

a*t**2 + b*t + 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;

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

\$\endgroup\$
  • \$\begingroup\$ Please state your sources if you copy-paste. \$\endgroup\$ – Alexandre Vaillancourt Feb 26 '16 at 13:57
  • \$\begingroup\$ What does ** stands for ? pow ? \$\endgroup\$ – kittikun May 23 '16 at 5:42
  • \$\begingroup\$ x**2 or x^2 both stands for pow(x,2) \$\endgroup\$ – tinyfiledialogs Jun 2 '16 at 18:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.