Need ray-sphere intersection code

Moderator
Posts: 434
Joined: 2002.09
Post: #1
This is going to sound incredibly lazy, but I really need code to compute the intersection of a ray and sphere. I can convert whatever structures it uses to my own, never fear.

There are a billion descriptions of how to do this on the 'net. Half of them describe an algebraic solution (solve a quadratic equation) which I suspect isn't as good for me as the geometric approach which uses vectors, dot products and so on. Most of the references have no code; some seem to disagree on whether they need to check for certain special cases explicitly or not. I found a function somewhere but my testing indicates there may be a problem.

I could write my own given a little more time and a little more sleep but I'm out of both of those. :-( So, please, debugged code or *robust* pseudo-code, anyone?

Or, I could post what I'm using and someone can tell me whether it looks reasonable or not.

Thanks! Just a few more hurdles and I'll finally be able to post an alpha version of Asteroid Rally for people to try out...

Measure twice, cut once, curse three or four times.
Quote this message in a reply
Jammer
Unregistered
 
Post: #2
Check out the E3Ray3D_IntersectSphere() function in the Quesa library. It's in the E3Math.c file. Quesa is here.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #3
I'll give it a shot.

Basically, the dot product and cross product approach is all you need.

The center of the sphere is at C, its radius is r, your ray starts at V and has direction D


1. Map the (C-V) vector onto the D vector. (project (C-V) on D)=CV'
2. Find the vector perpendicular to D that points to C: ((C-V) - CV')=R
3. if the magnitude of R is less than the radius of the sphere, you have an intersection. if (abs® <= r) then intersection

I cannot remember how to find the exact points of intersection, but this should get you started. The point (C+R) should mark the middle of the 2 intersections, and I guess there is some trig to figure out the rest.
Quote this message in a reply
Moderator
Posts: 434
Joined: 2002.09
Post: #4
Amazing! Both your answers are better than anything I found with Google. I've had pretty good luck getting hints via Google for most topics, but for some reason I came up short on this one. Too much of a hurry, maybe.

I'll poke around with these (and any other answers I get) tonight, and hopefully this will get me past my hump! Fingers crossed...

Thanks!

Measure twice, cut once, curse three or four times.
Quote this message in a reply
Moderator
Posts: 434
Joined: 2002.09
Post: #5
Quote:Originally posted by DoooG

I cannot remember how to find the exact points of intersection, but this should get you started. The point (C+R) should mark the middle of the 2 intersections, and I guess there is some trig to figure out the rest.


Yes, that much I had figured out. One method is that the distance d from (C+R) to the intersection points can be computed from the Pythagoras theorem:
d = sqrt(r^2 - len(C+R)^2)
Maybe there are ways I could avoid taking the square root but for the number of collisions I expect each frame (usually 0, sometimes 1 or 2) it's not a problem.

It's weird, I had the worst time with this problem. I knew the pieces but I could not for the life of me put together the whole solution. "Mental block" is the only way to describe it. Now I can feel the block falling away. I may or may not use the Quesa code, but either way I feel much better now that I understand how to do it myself. Thanks, Dooog and Jammer...

Measure twice, cut once, curse three or four times.
Quote this message in a reply
Member
Posts: 304
Joined: 2002.04
Post: #6
Glad you got a handle on it. But let me pile on with one more link (even though its a little late) - <http://wild-magic.com/>. Eberly's library has tons of collision/intersection code. If you find it useful make sure to buy his book!

cheers
Quote this message in a reply
Moderator
Posts: 434
Joined: 2002.09
Post: #7
The wild-magic license is clear-cut: I can use the code, period. I may yet do that. But using theirs would require more work. The Quesa code is very close to what I need, but their license doesn't seem to talk about the terms under which I can use that one function, whether as is, or with modifications. They seem more concerned with the library as a whole...

Does anyone know whether I can crib this one function from Quesa, and under what terms? I want to do the right thing. I will be changing the data structures and adding a case for the end of my line segment, but the logic would be mostly theirs.

Measure twice, cut once, curse three or four times.
Quote this message in a reply
Apprentice
Posts: 5
Joined: 2009.01
Post: #8
Here is the code I use for sphere intersection, maybe it helps.
Code:
float ray_sphereIntersection(sphere_t* sphere, ray_t* ray) {
    float b = vdot(ray->d, vsub(ray->o, sphere->p));
    float c = vsquaredist(ray->o, sphere->p) - (sphere->r * sphere->r);
    float d = b * b - c;

    if (d < 0.0f) {
        return -1.0f;
    }
    return -b - sqrt(d);
}

.johan
Quote this message in a reply
Jammer
Unregistered
 
Post: #9
Quote:Originally posted by MattDiamond
I will be changing the data structures and adding a case for the end of my line segment, but the logic would be mostly theirs.


Actually, "the logic" is not theirs as it comes from 'Real Time Rendering', section 10.3.2., as they note at the top of the function. Frankly, as long as you are making changes to the code, and you will have to to get your structures to fit, then I think you're fairly safe since the whole library is LGPL'd anyway.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #10
magicsofware.com .... gee they aint lying Rasp
* MacFiend has been touched by God Wow
Quote this message in a reply
Member
Posts: 304
Joined: 2002.04
Post: #11
Quote:Originally posted by MacFiend
magicsofware.com .... gee they aint lying Rasp
yeah - and his game physics book/cd/library comes out in December!

Codemattic (who is saving his pennies)
Quote this message in a reply
lpetrich
Unregistered
 
Post: #12
OK, I'll give the complete formulas here:

I'll Use DoooG's notation:

sphere with center C and radius R
line with point V and direction D

The vector from the sphere's center to the line point S = V - C

The distance along the line is

L = - (S.D)/(D.D) +/- sqrt((R^2-(S.S))/(D.D) + ((S.D)/(D.D))^2)

and the intersection point's position is V + L*D

The square-root term can be expressed in a way that may be more convenient for calculation, if the line's direction is close to its point's direction to the circle's center.

Let p = (S x D)^2 -- the absolute square of the cross product of S and D. Then

L = ( - (S.D) +/- sqrt((D.D)*R^2 - P) )/(D.D)

The discriminant (the term in the square root) can be used as a test for intersection.
Quote this message in a reply
lpetrich
Unregistered
 
Post: #13
I'm guessing that the sphere is being used as a bounding box. Other shapes have been used as bounding boxes, notably vertical cylinders and rectangular solids.

The circle part of a cylinder can be handled with the same mathematics as with the sphere, except that the cross-product is a scalar, not a vector quantity:

a x b = a[1]*b[2] - a[2]*b[1]

An object with a bounding box can have its bounding box follow its rotations by making its bounding box also be rotated (oriented bounding box). One has to calculate a collision with each of its six bounding planes, thoough the calculation is somewhat simplified by those planes coming in parallel pairs.

One can simplify a bit further by constructing an axis-aligned one; find the minimum and maximum coordinate values of all the vertices of an oriented bounding box and use those to construct a new bounding box with bounding planes along the coordinate axes.
Quote this message in a reply
Moderator
Posts: 434
Joined: 2002.09
Post: #14
Actually, the sphere is the very thing I'm intersecting with, it's not a bounding box. Aren't simplifying assumptions grand? Smile

In the end I got the Quesa/Real Time Rendering version of the algorithm working very quickly. Thanks to everyone's help I've finally posted a playable version of Asteroid Rally (see thread in the uDG 2003 forum for info.)

Thanks, all!

Measure twice, cut once, curse three or four times.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #15
As it happens, I am working on the subject, and have just finished a tidbit about intersection detection.

http://web.axelero.hu/g5d6/yag/collision...sphere.pdf

It has ray/triangle and ray/sphere collision details, outlining the steps to be taken, on a whole 3 pages. No code, but implementing it should be easy. I don't know if the paper contains the fastest methods, but I think they are logically correct.

If there is interest, I am planning on implementing ray/cylinder, sphere/triangle, cylinder/sphere, cylinder/triangle, ray/box, box/cylinder, sphere/box, and I would document it too, in a similar format, some graphs thrown in when I get the chance to make them.

Any feedback welcome, cheers
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Lighting a sphere with OpenGL lights (normals wrong?) cecilkorik 3 8,135 Dec 27, 2007 02:40 PM
Last Post: _ibd_
  2d Polygon Intersection bizimCity 6 6,776 Aug 31, 2006 05:29 PM
Last Post: reubert
  seeing the inside of a sphere Najdorf 10 4,176 Jul 17, 2006 09:19 PM
Last Post: OneSadCookie
  Space Box/Sphere misteranderson 1 2,441 May 12, 2006 10:48 AM
Last Post: TomorrowPlusX
  texture mapped sphere dave05 5 3,134 May 8, 2006 05:43 PM
Last Post: dave05