Ray - cylinder intersection

nabulsr2
Unregistered
 
Post: #1
Hi,

I know how to check if a ray intersects with a sphere and a polygon. I am now trying to do the same for a cylinder.

The best idea I've come up with so far is quite similar to my solution for ray-sphere intersection: substitute the equation of the ray into the equation of the sphere and solving quadratically.
The problem with this is that the equation of the cylinder assumes that the cylinder is at the origin and that it is a unit cylinder. My cylinders have undergone transformations such as rotations and translations (so it's not necessarily based at the origin) and are not unit cylinders. My source for this is:

ray-cylinder intersection site

Can anyone please help me with this? If not, can anyone give me info about alternative ray-cylinder intersection techniques (preferably simple and accurate ones)? Any help is greatly appreciated.

Thanks,
Ramsey
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #2
Well, you could always transform the ray by the inverse transformations and try that... It should work in theory.
Quote this message in a reply
kberg
Unregistered
 
Post: #3
Yeah, the easiest way is to plug the ray values into the quadratic equation for the cylinder and solve. If your cylinder is not centered it's pretty easy to offset the origin of the ray by the same amount to achieve the same result...

For any arbitrary set of transformations, the easiest way is to transform the ray by the objects transformation matrix. If you do not re-normalise your ray's direction vector, the the parametric t distance value you get out of solving the quadratic equation will be correct! Of course points, vectors, and normals all get transformed differently which was something that tripped me up the first time I wrote a ray-tracer. Vectors of course ignore any translation data, and normals are transformed by the inverse-transpose of the transformation matrix (again using only the upper-left 3x3 matrix).

The not-so easy way is to solve the transformed cylinder for the multitude of coefficients in the fundamental quadratic form removing the need to transform the ray into object space and transform the hit point and normal back into object space.
Quote this message in a reply
nabulsr2
Unregistered
 
Post: #4
Thanks for your responses. I will look into it after I have pursued my own solution to the problem that I came up with:

Imagine a vector that runs through the cylinder (through its centre). The first point of the vector is at one end of the cylinder and the other point of the vector is at the other end of the cylinder. You've basically got a ray running through the cylinder. If I was to place spheres at intervals along the ray then you would end up with a cylinder whose internal space is almost entirely filled with spheres. I could then check for intersection with the cylinder by checking for intersection with each of these spheres. This approach isn't 100% accurate (there will be some internal space in the cylinder that isn't covered due to the gaps between adjacent spheres), however you can increase the accuracy by decreasing the distance between adjoining spheres. Obviously the greater the number of spheres (and thus the accuracy) the greater the number of calculations.
I have started work on this approach and am having a problem: when I rotate my cylinder and vector about the x-axis by -45 degrees, the vector running through the cylinder is shrinking slightly and being rotated by slightly more than -45 degrees (so it's no longer running through the centre of the cylinder). Here is my code:

**********************************************
Code:
// angle to rotate cylinder and vector by
float angle = -45.0;

GLUquadricObj    *q;

// used to convert radians to degrees
#define PI 3.14159265


// draw cylinder
glPushMatrix();
    glColor3f(0.0f,0.0f,1.0f);
    q = gluNewQuadric();
    glRotated(angle, 1.0, 0.0, 0.0);
    gluQuadricDrawStyle(q, GLU_LINE);
    gluCylinder(q, 0.1f, 0.1f, 1, 6, 6);
glPopMatrix();


// coordinates of the two points making up the
// vector
float ax = 0.0, ay = 0.0, az = 0.0;
float bx = 0.0, by = 0.0, bz = 1.0;

// apply the manual rotate calculations to the
// points of the vector. Multiplying by PI and
// then diving by 180 converts radians to degrees
ax = ax;
ay = ay*cos((angle*PI)/180) -
       az*sin((angle*PI)/180);
az = ay*sin((angle*PI)/180) +  
       az*cos((angle*PI)/180);

bx = bx;
by = by*cos((angle*PI)/180) -
       bz*sin((angle*PI)/180);
bz = by*sin((angle*PI)/180) +
       bz*cos((angle*PI)/180);


// draw the vector running through the cylinder
glColor3f(1.0f,0.0f,0.0f);
glBegin(GL_LINES);
    glVertex3f(ax, ay, az);
    glVertex3f(bx, by, bz);
glEnd();


**********************************************

When I use the glRotated() method on the vector instead of manually calculating the points myself, the problem disappears. Why are my manual rotate calculations on the vector causing these problems?
I need to calculate the two points of the vector manually because I need to store these points so that I can place the spheres along the ray. I got all my maths for calculating the rotation from the following page:

rotations tutorial

Thanks,
Ramsey
Quote this message in a reply
kberg
Unregistered
 
Post: #5
At first glance the math does appear ok, so I would guess your problem is bad precision caused by the implicit conversion to integers...

Instead of /180, try /180.0f forcing the compiler to treat your constants as floats.
Quote this message in a reply
kberg
Unregistered
 
Post: #6
Oh shoot, I see your problem...

You need to cache the values of ay and by... You are updating the value in ay before you calculate the new position for az, which is responsible for the skew you are experiencing.
Quote this message in a reply
nabulsr2
Unregistered
 
Post: #7
yep, that did the trick. thanks kberg!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Need ray-sphere intersection code MattDiamond 23 14,724 Aug 31, 2009 02:28 PM
Last Post: Gengar003
  2d Polygon Intersection bizimCity 6 6,681 Aug 31, 2006 05:29 PM
Last Post: reubert
  Math question: deriving rotation by plane intersection TomorrowPlusX 6 3,905 Jan 24, 2006 07:28 AM
Last Post: TomorrowPlusX
  Ray cone intersection nabulsr2 1 8,166 May 15, 2005 09:05 AM
Last Post: phydeaux
  Intersection with arbitrary solid hamishl 2 2,858 Sep 17, 2004 01:41 PM
Last Post: codemattic