ElectroDruid 122 Report post Posted October 9, 2007 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 :) 0 Share this post Link to post Share on other sites
strtok 191 Report post Posted October 9, 2007 Just the other day I found something about cylinder collision here:http://www.insomniacgames.com/tech/techpage.phpYou'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. 0 Share this post Link to post Share on other sites
ElectroDruid 122 Report post Posted October 10, 2007 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->QX = 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 rootsBased on the distance from P if < 0 or > |Q-P| we further test against the endcap 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? 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted October 12, 2007 It's using the ray equation and the clyinder equation. SImilar to thisray : P(t) = P + V * tcyl : (((P(t) - O) x D)^2 = r^2O 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)) 0 Share this post Link to post Share on other sites
Zipster 2377 Report post Posted October 12, 2007 Quote:Parametrically solve for line intersecting infinite cylinder and check if it hits end caps.Line A->B and Cylinder center end points P->QX = 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 rootsBased on the distance from P if < 0 or > |Q-P| we further test against the endcap 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. 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted October 13, 2007 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 productVector VxAB = (V ^ AB); // cross productfloat ab2 = (AB * AB); // dot productfloat a = (VxAB * VxAB); // dot productfloat b = 2 * (VxAB * AOxAB); // dot productfloat c = (AOxAB * AOxAB) - (r*r * ab2);// solve second order equation : a*t^2 + b*t + c = 0 0 Share this post Link to post Share on other sites
ElectroDruid 122 Report post Posted October 29, 2007 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 checks2 - 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? 0 Share this post Link to post Share on other sites
jyk 2094 Report post Posted October 29, 2007 Quote:Original post by ElectroDruid1 - 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 checksOnce 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. 0 Share this post Link to post Share on other sites
ElectroDruid 122 Report post Posted October 31, 2007 Hi jyk, thanks for the adviceI 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? 0 Share this post Link to post Share on other sites