Archived

This topic is now archived and is closed to further replies.

billybob

ray-cylinder test

Recommended Posts

I''m having trouble with a ray-cylinder intersection test, i''ve been able to test if it hits the radius, because the cylinder is always vertical. so i just extracted the horizontal parts of the ray and cylinder (disregarded the y part of everything), and did a distance check with the center of the cylinder, and checked if it was less than the radius. but, how to do the vertical part?

Share this post


Link to post
Share on other sites
If the line has a limited length, find its endpoints. If either of them is closer than the radius of the cylinder to the line, and has vertical component within the range of the cylinder, then the line must intersect the cylinder.

If both endpoints are above or both are below the vertical range of the cylinder, then the line does not intersect.

Next, find the points in space where the line passes through the vertical heights which are equal to the vertical limits of the cylinder. If these points are a distance less than the radius of the cylinder from the central line, then the line passes through the side of cylinder.

Next, find the points in space where the line is a distance equal to the radius of the cylinder away from the central line. If the vertical heights of these points are within the range of the cylinder, then the line intersects, if not, then not.

... I think that should cover all cases..?

Share this post


Link to post
Share on other sites
I''d say you do a line-plane collision test between the line and cylinder bases, and check if the intersection points are within the overhead projected circle. Keep ones that are. The good news is that once you reach two intersections, you can stop the check because that''s the maximum you could ever have. So if the line-plane tests both return good points, you''re done! Otherwise, you do the regular side collision test (I assume you''re using line-circle collision for that).

Share this post


Link to post
Share on other sites
actually zipster, expanding on that, i found a way to do it with only one test per cap (i think the way alone would have required a check with the vertical part of the cylinder also). i intersect the plane of the top of the cylinder with the ray, and then check if it is within the radius of the cylinder * the run / rise of the ray. i know this will fail if the ray comes nearly vertical on the cylinder, but the earlier test i do on the distance of the center of the cylinder's horizontal components with the horizontal components of the ray should cover the raycasts which have a run / rise of less than 1.

edit: forgot to say it seems to work, but i haven't tested it really.

[edited by - billybob on August 9, 2003 6:52:22 PM]

Share this post


Link to post
Share on other sites
cylinder equation

((P - C) x D)^2 = r^2

P is a point on the cylinder, C is a point on the cylinder core (the centre of the cylinder, or the base), D is the direction of the cylinder, r is the radius. Pretty much like a sphere equation.

so develop with a ray equation (P = O + S.t), and you get

((O - C) x D + (S x D).t)^2 = r2

((O - C) x D)^2 - r^2 + 2 * ( ((O - C)xD) * (S x D) ).t + (S x D)^2 . t^2 = 0

second order equation in the form

a.t^2 + b.t + c = 0

where

a = (S x D)^2
b = 2 * ( ((O - C) x D) . (S x D) )
c = ((O - C)xD)^2 - r^2

determinant is

d = (b*b - 4.a.c)

if (d < 0), the ray does not intersect

else the solutions are
t0 = (-b-sqrt(d)) / 2.a
t1 = (-b+sqrt(d)) / 2.a

and

tcylmin = min(t0, t1)
tcylmax = max(t0, t1)


now, the intersection points with the bottom and top caps. I assume the cylinder has the point C as the centre of the cylinder, and the cylinder is of length l.

ttop = ((C - O) * D + l/2) / (S * D)
tbot = ((C - O) * D - l/2) / (S * D)

and

tcapmin = min(ttop, tbot)
tcapmax = max(ttop, tbot)


if (tcapmin > tcylmax) || (tcapmax < tcylmin) the ray does not intersect

else the ray intersects at the overlapping interval between [tcylmin, tcylmax] and [tcapmin, tcapmax].

there are optimisations to be made, like you only need to test one cap if the origin of the ray is above or below the cylinder, and no cap if the origin of the ray is ''leveled'' with the cylinder.

Share this post


Link to post
Share on other sites
another way is to transform the ray into the cylinder space, and find the intersection there, then transform the points back into world space. First, you need to find the quaternion (or 3x3 rotation matrix) to rotate the ray from it''s direction back into an axis (X, Y or Z axis). If you have the cylinder orientation stored as a matrix instead of a directional vector, it''s simply the transpose of the matrix to get the inverse transform.

Cylinder (C, Ori, l)
Ray (P, S)

Q = (P - C) * Ori.Transpose();
T = S * Ori.Transpose();


then with Q and T, you have the cylinder aligned with an axis (as if the cylinder never rotated), and the ray relative to that cylinder. And you can do the cylinder/ray test virtually in 2D.

Share this post


Link to post
Share on other sites
Sorry to bring up an old disscussion, but I''m having trouble understanding the notation.

a = (S x D)^2
b = 2 * ( ((O - C) x D) . (S x D) )
c = ((O - C)xD)^2 - r^2

x = crossProduct?
. = dotProduct?
* = multiply
- = minus

if the above is correct, then ''(S x D)^2'' means ''(S cross D) squared''. How do you square a vector and get a scalar?

Thanks for answering this super easy question.

Robbie

Share this post


Link to post
Share on other sites
my guess would be multiplying by itself, ie taking the dotproduct with itself, so vector^2 == vector.vector

im not 100% sure, but thats the only thing that makes sense.

Share this post


Link to post
Share on other sites
yeah, I though that was quite standard as a notation. It's the dot product of a vector by itself, or it's squared magnitude.

x is cross product
. is dot product
* is multiplication
- is substraction
+ is addiciton

and I also use '*' as the dot product sometimes. so, in c++


struct Vector
{
float x, y, z;

Vector(float _x, float _y, float _z)
: x(_x)
, y(_y)
, z(_z)
{}

Vector& operator += (const Vector& V) { x += V.x; y += V.y; z += V.z; return *this; }
Vector& operator -= (const Vector& V) { x -= V.x; y -= V.y; z -= V.z; return *this; }
Vector& operator *= (float k) { x *= k; y *= k; z *= k; return *this; }
Vector& operator /= (float k) { return (*this) *= 1.0f / k; }

float operator * (const Vector& V) { return x*V.x + y*V.y + z*V.z; } // dot product

Vector operator -(void) const { return Vector(-x, -y, -z); }

Vector& operator ^=(const Vector &V) // Cross product

{
float Tempx = (y * V.z) - (z * V.y);
float Tempy = (z * V.x) - (x * V.z);
z = (x * V.y) - (y * V.x);
x = Tempx;
y = Tempy;

return *this;
}

Vector operator + (const Vector& V) const { Vector Temp(*this); return Temp += V; }
Vector operator - (const Vector& V) const { Vector Temp(*this); return Temp -= V; }
Vector operator * (float k) const { Vector Temp(*this); return Temp *= k; }
Vector operator / (float k) const { Vector Temp(*this); return Temp /= k; }
Vector operator ^ (const Vector& V) const { Vector Temp(*this); return Temp ^= V; }

friend Vector operator * (float k, const Vector& V) { return V * k; }

float MagnitudeSquared(void) const { return (*this) * (*this); }

float Magnitude(void) const { return (float) sqrt(MagnitudeSquared()); }
};


[edited by - oliii on December 6, 2003 9:07:40 AM]

Share this post


Link to post
Share on other sites