Sign in to follow this  

Ray/Cylinder intersection

This topic is 3701 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm writing a raytracer, and I'd like to add cylinders as a primitive. I want to be able to define them by a start and end point (i.e, as points in world space; I want these to be arbitrarily rotatable rather than aligned to a specific axis), and a radius. My rays are defined as a start point and a direction, with another float value representing the maximum distance along the ray I want to test. All the intersection tests for my other primitives return a boolean to indicate whether there was an intersection, and set the length float to indicate how far along the ray the first intersection with the primitive occurred. I'm rather rusty on the maths. I gather that the best approach is similar to how you find the closest point of intersection between two line segments (something like what's demonstrated here: http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm )... Except of course that I don't want the closest intersection, I want the point where the distance between the ray and the line running through the cylinder is the same as the cylinder's radius (measured perpendicular to the line through the cylinder). If that makes any sense... I don't know how I need to adapt the algorithm to go from giving me the closest point between the lines to giving me the intersection point on a cylinder. For what it's worth, I find descriptions and explanations of stuff in code or pseudocode a lot easier to understand than in mathematical notation. I can follow a bit of maths, but it's not as easy for me as following code. Any kind of help is much appreciated, though :)

Share this post


Link to post
Share on other sites
Just the other day I found something about cylinder collision here:

http://www.insomniacgames.com/tech/techpage.php

You've probably heard of these guys (Resistance: Fall of Man). I haven't read it myself, but they claim to have some novel approaches so it's probably worth checking out.

Share this post


Link to post
Share on other sites
Here's what that pdf has to say about line/cylinder intersection:

Quote:
Parametrically solve for line intersecting infinite cylinder and check if it hits end caps.
Line A->B and Cylinder center end points P->Q
X = A + t(B-A);
T = (X-P);
T’ = T – T.(Q-P); (component perpendicular to Q-P);
T’.T’ = r^2; (would result in quadratic equation in t)
If eqn has 1 or more roots
Based on the distance from P if < 0 or > |Q-P| we further test against the end
cap of interest (circle plane vs line test)


I'm not entirely sure what's going on here, although it looks a bit like code. I presume A, B, P, Q, X, T and T' are vectors. It also looks like t(B-A) is a vector, although I have no idea what t is. Could it be "time", which in this case would presumably mean t was some fraction of the distance along the line A->B? Given that that's what I'm trying to find out, I don't really follow what I'm supposed to do here. Do I try to plug that into the Quadratic formula ( x=(-b±sqrt(b²-4ac))/2a ) somehow? If so, which terms in the above stuff equate to a, b and c in the quadratic formula? Am I barking up completely the wrong tree?

Share this post


Link to post
Share on other sites
It's using the ray equation and the clyinder equation. SImilar to this

ray : P(t) = P + V * t
cyl : (((P(t) - O) x D)^2 = r^2

O is point on cylinder core, D is direction of cylinder (normalised), r is radius.

then you combine the two equations and you get a second order equation you solve for (t), composed of cross products and dot products.

with end points B and A...

(((P(t) - A) x (B - A))^2 = r^2 * ((B - A) . (B - A))

Share this post


Link to post
Share on other sites
Quote:
Parametrically solve for line intersecting infinite cylinder and check if it hits end caps.
Line A->B and Cylinder center end points P->Q
X = A + t(B-A);
T = (X-P);
T’ = T – T.(Q-P); (component perpendicular to Q-P);
T’.T’ = r^2; (would result in quadratic equation in t)
If eqn has 1 or more roots
Based on the distance from P if < 0 or > |Q-P| we further test against the end
cap of interest (circle plane vs line test)

Um yeah, ignore this. I mean, T' = T - T.(Q-P)? A vector minus a scalar? The correct comment is no good if the math is all wrong. Just listen to oliii.

Share this post


Link to post
Share on other sites
I'll pseudo code.


//--------------------------------------------------------------------------
// Ray : P(t) = O + V * t
// Cylinder [O, D, r].
// point Q on cylinder if ((Q - O) x D)^2 = r^2
//
// Cylinder [A, B, r].
// Point P on infinite cylinder if ((P - A) x (B - A))^2 = r^2 * (B - A)^2
// expand : ((O - A) x (B - A) + t * (V x (B - A)))^2 = r^2 * (B - A)^2
// equation in the form (X + t * Y)^2 = d
// where :
// X = (O - A) x (B - A)
// Y = V x (B - A)
// d = r^2 * (B - A)^2
// expand the equation :
// t^2 * (Y . Y) + t * (2 * (X . Y)) + (X . X) - d = 0
// => second order equation in the form : a*t^2 + b*t + c = 0 where
// a = (Y . Y)
// b = 2 * (X . Y)
// c = (X . X) - d
//--------------------------------------------------------------------------
Vector AB = (B - A);
Vector AO = (O - A);
Vector AOxAB = (AO ^ AB); // cross product
Vector VxAB = (V ^ AB); // cross product
float ab2 = (AB * AB); // dot product
float a = (VxAB * VxAB); // dot product
float b = 2 * (VxAB * AOxAB); // dot product
float c = (AOxAB * AOxAB) - (r*r * ab2);

// solve second order equation : a*t^2 + b*t + c = 0

Share this post


Link to post
Share on other sites
Heya,

Thanks for the help oliii. Sorry to revive this thread after a couple of weeks, but life has been manic and I haven't had a lot of chance to look at this for a while.

I wrapped my head around your technique, and implemented your pseudocode. and I can see something that looks a bit like it might be an infinitely long cylinder onscreen. It seems to point in the direction and have the radius that I'd expect. So, I have two problems, both of which stem from be being kinda dumb with the maths.

1 - I need the cylinder to be a finite length. I don't need circular end caps on it, but I do need to be able to specify either both end points, or an origin, direction and a length (the latter seems more likely). I don't really know how to add these checks

2 - Given a point of intersection on the cylinder, I need to be able to calculate a normal. As a first pass, I tried making the normal always (0,0,-1) (My camera always points down the z axis), which should give me a flat bright looking thing as a test, but I just see weird speckly stuff.

I can post the code I wrote if it'll help. The speckliness tells me that maybe my code to resolve the equations has some kind of problem with it? I just solve for both roots and choose the smallest one (ie the closest intersection). Is that right?

Share this post


Link to post
Share on other sites
Quote:
Original post by ElectroDruid
1 - I need the cylinder to be a finite length. I don't need circular end caps on it, but I do need to be able to specify either both end points, or an origin, direction and a length (the latter seems more likely). I don't really know how to add these checks
Once you've computed the intersection point with the infinite cylinder, project this point onto the cylinder axis. You can then check the resulting parametric value to see if the intersection point lies on the surface of the finite cylinder (what range to check it against depends on how your cylinder is represented).
Quote:
2 - Given a point of intersection on the cylinder, I need to be able to calculate a normal. As a first pass, I tried making the normal always (0,0,-1) (My camera always points down the z axis), which should give me a flat bright looking thing as a test, but I just see weird speckly stuff.
The normal is the normalized vector from the point on the cylinder axis closest to the intersection point (which can be found using the parametric value computed earlier) to the intersection point itself.

Share this post


Link to post
Share on other sites
Hi jyk, thanks for the advice

I can see how getting the parametric value could be used to test where on the infinite cylinder the ray hits (and so whether it hit on the segment I'm interested in), and I can see how I'd compute the normal from that value as well... But I'm being slow and can't work out how you'd project the intersection point onto the axis in the first place. I can imagine a way of working this out involving some kind of matrix or quaternion based transformation, but I'm guessing that there's a simpler approach that I haven't figured out. Is there?

Share this post


Link to post
Share on other sites

This topic is 3701 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this