Need raysphere intersection code
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* pseudocode, 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...
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* pseudocode, 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.
Check out the E3Ray3D_IntersectSphere() function in the Quesa library. It's in the E3Math.c file. Quesa is here.
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 (CV) vector onto the D vector. (project (CV) on D)=CV'
2. Find the vector perpendicular to D that points to C: ((CV)  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.
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 (CV) vector onto the D vector. (project (CV) on D)=CV'
2. Find the vector perpendicular to D that points to C: ((CV)  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.
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!
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: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.
Glad you got a handle on it. But let me pile on with one more link (even though its a little late)  <http://wildmagic.com/>. Eberly's library has tons of collision/intersection code. If you find it useful make sure to buy his book!
cheers
cheers
The wildmagic license is clearcut: 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.
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.
Here is the code I use for sphere intersection, maybe it helps.
.johan
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: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.
magicsofware.com .... gee they aint lying
* MacFiend has been touched by God
* MacFiend has been touched by God
Quote:Originally posted by MacFiendyeah  and his game physics book/cd/library comes out in December!
magicsofware.com .... gee they aint lying
Codemattic (who is saving his pennies)
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 squareroot 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.
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 squareroot 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.
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 crossproduct 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 axisaligned 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.
The circle part of a cylinder can be handled with the same mathematics as with the sphere, except that the crossproduct 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 axisaligned 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.
Actually, the sphere is the very thing I'm intersecting with, it's not a bounding box. Aren't simplifying assumptions grand?
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!
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.
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
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
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
Lighting a sphere with OpenGL lights (normals wrong?)  cecilkorik  3  9,487 
Dec 27, 2007 02:40 PM Last Post: _ibd_ 

2d Polygon Intersection  bizimCity  6  8,063 
Aug 31, 2006 05:29 PM Last Post: reubert 

seeing the inside of a sphere  Najdorf  10  5,715 
Jul 17, 2006 09:19 PM Last Post: OneSadCookie 

Space Box/Sphere  misteranderson  1  3,039 
May 12, 2006 10:48 AM Last Post: TomorrowPlusX 

texture mapped sphere  dave05  5  4,262 
May 8, 2006 05:43 PM Last Post: dave05 