## Need ray-sphere intersection code

Moderator
Posts: 455
Joined: 2002.09
Post: #16
Is the purpose to present easily understandable/implementable methods, rather than speed? Seems worthwhile to me.

Note that there may be a cheaper way to test whether a point V is in a triangle (Px,Py,Pz). From memory, I think you can add up the angles that the point V makes with each pair of triangle vertices. I.e.
acos( PxV dot VPy ) + acos( PyV dot VPz ) + acos ( PzV dot VPx )

If the point is in the triangle, the angles add up to 360 degrees (2*pi). Cost is 3 acos's, plus some dot products.

First, I don't know if that's a cheaper solution overall than yours, and second, if the point "in" the triangle isn't exactly coplanar with the triangle vertices you won't get exactly 360 degrees. Nonetheless, I thought I'd mention this... (Hmm, maybe there's an even faster way by checking the dot products directly rather than taking the acos. In effect, you just want to know that V is "in between" every pair of triangle legs.)

Well I guess someone's always going to know a faster algorithm. I just googled and found one that uses cross products and supposedly beats the pants off the 360-degree test:
http://www.blackpawn.com/texts/pointinpoly/default.html
Not sure what you want to do about this though. To not be seen as trying to compete with the magicsoftware's and Graphic Gem's of the world, maybe you just need to make your purpose clear that you are not necessarily going after speed. At the same time, people will want to know that your solutions aren't hideously slow, yes? In which case you may want to glance at Fundamentals of Comp Graphics, or Real Time Rendering, or Graphics Gems, just to make sure there isn't some widely known solution that you hadn't considered.

But if the point of the exercise is that you feel like working this stuff out for yourself, then ignore the above ramblings.

Measure twice, cut once, curse three or four times.
Moderator
Posts: 869
Joined: 2003.01
Post: #17
Quote:Originally posted by MattDiamond
Is the purpose to present easily understandable/implementable methods, rather than speed? Seems worthwhile to me.

Note that there may be a cheaper way to test whether a point V is in a triangle (Px,Py,Pz). From memory, I think you can add up the angles that the point V makes with each pair of triangle vertices. I.e.
acos( PxV dot VPy ) + acos( PyV dot VPz ) + acos ( PzV dot VPx )

If the point is in the triangle, the angles add up to 360 degrees (2*pi). Cost is 3 acos's, plus some dot products.

Doesnt work that way, because you have to take the unit length vectors for the acos() to work. Thats where the normalization comes from, though it is only a single division in the end, not 6 per acos(). The 3 sqrt() and 4 acos() are the expensive parts. But as said in the paper, this is the very last step and infrequently executed, so i dont know how much optimizing it brings.

Quote:But if the point of the exercise is that you feel like working this stuff out for yourself, then ignore the above ramblings.

Yea, I am implementing all this, and I have to write it down, wont remember it in a few months otherwise. I am writing things for me to understand, basically, but of course it would be nice if its useful to others. Simple stuff first, and who is ready can dig (and understand) the advanced stuff.

PS: I looked at that other test, and it seems like he is just shifting the sqrt to another part to the SameSide(p,a, b,c) because he has to use vector projection against the normal to find out what is on the same side. Though it seems like no more acos(). I will look into this, too, seems worthwile to do.
lpetrich
Unregistered

Post: #18
First, I wish to apologize to MattDiamond for misunderstanding what he had wanted to do. In a bboard dedicated to game creation, I'd expected the discussion to be about simplified ways of handling 3D models, and ball-shaped objects are usually not the most common objects in such games.

As to the triangle problem, there are several ways to do it.

One way is to see whether a point is on the same side of all the sides. Here is a sidedness test:

Triangle has vertices v1, v2, and v3

Sidedness relative to v1-v2, v2-v3, and v3-v1 sides:

S1 = (v - v1)x(v2 - v1)
S2 = (v - v2)x(v3 - v2)
S3 = (v - v3)x(v1 - v3)

where x is the 2D cross product.

For v to be inside the triangle, S1, S2, and S3 must have the same sign. Which sign will depend on whether one had done a clockwise or counterclockwise choice of vertices v1, v2, and v3.

The area of this triangle is (1/2)(v2 - v1)x(v3 - v1) with the sign depending on the vertex direction.

The above can easily be generalized to convex polygons with any number of vertices; one can even test for the convexity at a vertex by finding the area of the triangle with it and its two neighbors.
Jesse
Unregistered

Post: #19
The most robust and efficient way I've found of doing ray-triangle intersections is to use Plucker coordinates. I haven't done any tests, but I assume it's faster than the other methods 'cause it doesn't involve any sqrts or trig functions. It also makes for nice, clean code. Best of all, it's very robust in that there are no special cases, and rays don't fall 'in the cracks' between tris.

On another topic, I'm also trying to come up with some code for ray-cylinder intersection. I gather that there are some quadratic equations involved, but I've never solved these in code and I'm not sure how to do it. I'm working through Dave Eberly's code, but haven't quite deciphered it yet. So I too would be interested in any info on ray-cylinder intersection algorithms.
Moderator
Posts: 869
Joined: 2003.01
Post: #20
Quote:Originally posted by Jesse

On another topic, I'm also trying to come up with some code for ray-cylinder intersection. I gather that there are some quadratic equations involved, but I've never solved these in code and I'm not sure how to do it. I'm working through Dave Eberly's code, but haven't quite deciphered it yet. So I too would be interested in any info on ray-cylinder intersection algorithms.

I was thinking about this. my approach would be to project the cylinder and ray into a plane for which the normal is the center line of the cylinder.

Then the solution is reduced to finding a circle with a line intersection, which is really simple.

The same works for two cylinders, in which case we'd get a circle and a box.
Jesse
Unregistered

Post: #21
Quote:I was thinking about this. my approach would be to project the cylinder and ray into a plane for which the normal is the center line of the cylinder.

Then the solution is reduced to finding a circle with a line intersection, which is really simple.

The same works for two cylinders, in which case we'd get a circle and a box.

This would only give you true-false, right, not the points of intersection in 3D? I'm hoping to get the points of intersection also...

Eberly's approach first transforms the ray into local space, in which the cylinder axis is the z axis. This simplifies things somewhat, but it's still pretty complicated.
Moderator
Posts: 869
Joined: 2003.01
Post: #22
Quote:Originally posted by Jesse
This would only give you true-false, right, not the points of intersection in 3D? I'm hoping to get the points of intersection also...

Eberly's approach first transforms the ray into local space, in which the cylinder axis is the z axis. This simplifies things somewhat, but it's still pretty complicated.

No, it would actually give the intersection coordinates, and from what you say, Eberly's way is the exact same thing I suggested.

You know the length of the ray/line segment in local coordinates, and the intersection points. You can get the ratio of intersection to segment length, which you can apply to the original distance vector of the ray to find the intersection points in 3D space.
lvnguyen
Unregistered

Post: #23
lpetrich Wrote: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.

Does anyone know if this derivation is from a paper or text? I want to be able to reference it
Nibbie
Posts: 1
Joined: 2009.08
Post: #24
lpetrich Wrote: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.

I found this thread through google looking for sphere/line or sphere/ray intersection logic (after, too, finding lots of unhelpful-for-gaming algebra answers), and wanted to add that this was exactly what I needed, and solved my problem in around 10 seconds.

Thank you very much, and here's to bumping this up in pagerank for anyone else with the same problem.