Archived

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

AvengerDr

Ray - Finite Cylinder Intersection Test

Recommended Posts

AvengerDr    751
Hello there! I've been reading alot about cylinder ray intersection test and so far I was able to implement (after reading some posts here on these forums) a Ray -> Infinite Cylinder Intersection test. In order to solve this problem I found an algorithm (Graphics Gem IV Ray-Cylinder test) which computes the intersection by calculating the entering and leaving distance of the ray in the cylinder (or something like that).. But after having this in/out distance what do I need to do to know if I have "hit" the finite cylinder or the imaginary half-infinite cylinder extending from the cylinder's top and bottom faces? This is the code I currently have:
// pOrigin - Origin of the Ray

// vRay - Ray Vector

// e - object containing cylinder information


  public static boolean fireAtEdge(Point3D pOrigin, Vector3 vRay, Edge e) {

    vRay = vRay.norm();

// Cylinder Base Point

    Point3D pBase = e.getStartN().getPos();

// Vector from Ray Source to Cylinder Base

    Vector3 vSource = new Vector3(pOrigin.sub(pBase));

// Normalized cylinder Axis

    Vector3 vCylAxis = e.getVector().norm();

// I don't fully understand what this represents.. 

// it is the normal between the Cylinder Axis and the Ray Vector

// (obviously) and it's used later to calculate the projection 

// of the radius, isn't it?


    Vector3 vCrossNormal = new Vector3(vRay.crossProduct(vCylAxis));

// length of vector

    double ln = vCrossNormal.magnitude();

    vCrossNormal = vCrossNormal.norm();

// shortest distance from Cylinder

    double d = Math.abs(vSource.dotProduct(vCrossNormal));

// if d<Cylinder Radius then I have hit the infinite cylinder

    boolean hit = (d <= Edge.cylRadius);

    if (hit) {

// If I have hit the infinite cylinder this algorithm

// calculates the entering and leaving distances

// I think that it is intersecting the line with the cylinder

// in order to know the intersection points

// What are these distances? Distance from what?


      Vector3 vU = new Vector3(vSource.crossProduct(vCylAxis));
      double t = -vU.dotProduct(vCrossNormal) / ln;
      
      Vector3 vO = new Vector3(vCrossNormal.crossProduct(vCylAxis).norm());
      double s = Math.abs(Math.sqrt(Edge.cylRadius * Edge.cylRadius - d * d) /
                          vRay.dotProduct(vO));
      double in = t - s;
      double out = t + s;
      return true;
    }
    else {
      return false;
    }
Anyway since I don't see any reference to the actual cylinder length I don't think that I'm on the right track.. Anyone care for a little explanation of what I did (if it has been done right) and what do I need to do in order to continue? I also thought that I could forget this entering/leaving distance stuff and try to intersect the ray with the planes built from the top/bottom cylinder faces. But how can I build the equation of these two planes and their normal? The normal of these two planes would have to point each other. If the line would be in front of either plane the ray would have then hit the finite cylinder, right? But how can I do this? What it the more efficient way? Thanks in advance! [edited by - AvengerDr on January 16, 2004 9:00:02 PM] [edited by - AvengerDr on January 16, 2004 9:00:38 PM]

Share this post


Link to post
Share on other sites
oliii    2196
basically, it''s calculating the distance between the ray line and the cylinder core. if distance < radius (d <= Edge.cylRadius), you have an intersection. Then it does some maths trickery to calculate the point. Similar to a sphere-ray intersection test.

the values t0, t1 are the parameters of intersection, as you pointed. if your ray as length l, and (t1 < 0.0f && t0 > l), the ray is too short and does not intersect.

for capped cylinders, you also compute the parameters of intersection with the capped planes. say c0 and c1.

if (c0 > t1 || c1 < t0), then the ray misses the capped cylinder. Basically, the intervals [c0, c1] and [t0, t1] have to overlap.

You can apply the same algorithm for ray box intersection test. you find the parameters of intersection with the pair of planes on X, Y and Z axis, (say you found [x0, x1], [y0, y1], [z0, z1]), and if the intervals are not overlapping (and not overlapping [0, l], paraneters of the ray), then the ray misses the box.

an example in 2D


// misss

/////////////

| |
* | |
\ | |
------.---+----+-------
y0 \ | |
\ | |
---------.+----+-------
y1 . x0 |
|\ |
| \ |
| \ |
| \|
| . x1
\
*
// y1 < x0

// => [x0, x1] not intersecting [y0, y1]. no intersection



// HIT

///////


| |
* | |
\y0| |
--------.-+----+-------
\| |
x0. |
----------+.---+-------
| y1 |
| \ |
| \|
| .x1
| |\
| \
*

// y1 in range [x0, x1]

// => [x0, x1] intersects [y0, y1]. the ray crosses the rectangle




you can see the rectangles as being cylinders seen from the side.



the other solution is, once you computed the point on the cylinder cap planes, see if the points are in the circle on the plane (distance of intersection point to cap centre < radius).


using algorithm one, and testing intervals [0, l], [t0, t1], and [c0, c1], then you solve the problem in one go. But you need to compute intersections with the cylinder cap planes and the infinite cylinder to get the intervals. For a more optimium test, you can determine what would be the most probable feature of the cylinder that''s gonna get hit (if ray origin ''inside'' the infinite cylinder, then you only need to test against one cap, if origin inside capped cylinder, either return 0, or calculate t0 or t1, if origin between the two caps planes, only need to test against the infinite cylinder, ...).

Share this post


Link to post
Share on other sites
higherspeed    230
I''ve always found the best way to be sure when thinking about intersections is to list all the possible ways the objects can intersect. In this case it''s very simple, because there are only 3 different surfaces. So the possibilities are few:

1) enters and leaves through the curved surface.
2) passes though a cap and the curved surface.
3) passes through both caps.

Obviously first you''ll want to do an infinite cylinder test as it''s very cheap. Next you obtain the closest point to the axis. If this lies inbetween the caps then option 1 is accounted for. The only remaining possibility is that the ray passes through a cap. So the final thing is just a couple of ray-circle tests.

Share this post


Link to post
Share on other sites
AvengerDr    751
Thanks for your replies! I checked the ray against the planes and everything worked! I did not realize that I could simply build the planes equation for the top and bottom faces simply using the Cylinder Axis (and the negated axis for the other one) I did not need to check for the ray passing through the caps because at the end of the cylinder there will always be a sphere, and that would get selected first.

Thanks again!

Share this post


Link to post
Share on other sites