Ray-cylinder intersection (and others)

Started by
2 comments, last by haegarr 8 years, 12 months ago
Hi,

I'm trying to figure out how to add cylinders to a path tracer, and I was wondering if I was correct in thinking that the equation of a cylinder is this:

r^2 = |(p - a) x b|^2

Where r is the cylinder radius, p is any point on the cylinder's surface, and a/b are the location of a point on the line defining the cylinder's axis and the direction of the axis respectively (ie a and b define the line along which the cylinder lies).

So in order to find where a ray intersects the cylinder I would substitute p = u + t*v (the equation of the ray) into the above and solve for t?

Also, I've only been able to find decent descriptions for ray-sphere and ray-plane intersection so far - is there a book or site anyone could recommend for other geometric shape intersection algorithms? One for a torus would be pretty awesome :)

Thanks!
Advertisement

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323

NBA2K, Madden, Maneater, Killing Floor, Sims http://www.pawlowskipinball.com/pinballeternal

You could also consider rotating the cylinder along z axis, and reduce the beginning of the test to ray to circle. If you hit the circle, compute point of impact and see if it's between the two capsule end-sphere centers. Otherwise, compute point of impact against nearest sphere.

In the days back when I programmed a ray tracer (we wrote the year 2000 as I've seen in my documents), I had used a method similar to what Randy Gaul has mentioned above: Intersection computations started with transforming the problem into a normalized local object space. This puts down intersections of translated / rotated / scaled objects to their respective standard form. The transformation is applied just to the origin and direction of the parametric ray. It would appear in a full intersection formula anyway, so does not enhance the computational costs.

In case of a cylinder the standard form, as was used in my ray tracer, meant: The axis of the cylinder is is the local y axis, the basic area is circular, the height is symmetrical to the x/z plane. In this case the cylinder could be hollow if either or both of the ceiling and floor planes are omitted. The belonging code is this (please don't look too close to the coding style):


Bool RegCylinderShape::check(const Ray& aRay,SpanList& Spans) const {
   Bool HitExists = false;
   // localize ray
   this->applyInvToPoint(aRay.Origin,_localRay.Origin);
   this->applyInvToVector(aRay.Direction,_localRay.Direction);
   // compute parameters
   register Real64 T1 = _localRay.Origin.x/_Rx;
   register Real64 T2 = _localRay.Origin.z/_Rz;
   register Real64 T3 = _localRay.Direction.x/_Rx;
   register Real64 T4 = _localRay.Direction.z/_Rz;
   register Real64 C0 = T1*T1+T2*T2-1.0;
   register Real64 C1 = T1*T3+T2*T4;
   register Real64 C2 = T3*T3+T4*T4;
   C0 = C1*C1-C0*C2;
   // if C0 is greater than zero, the ray hits the infinitely long cylinder
   if(C0>0.0) {
      register Bool B1p,B1n,B2p,B2n;
      // compute the travel coordinates of the near and far hits
      C0 = sqrt(C0);
      T1 = (-C1-C0)/C2;
      T2 = (-C1+C0)/C2;
      // compute y components of both hits in local coordinates
      C1 = T1*_localRay.Direction.y+_localRay.Origin.y;
      C2 = T2*_localRay.Direction.y+_localRay.Origin.y;
      // check whether or not the ray enters/leaves through ceiling/floor planes
      B1p = C1<=_halfHeight;
      B2p = C2<=_halfHeight;
      B1n = C1>=-_halfHeight;
      B2n = C2>=-_halfHeight;
      // if the ray hits the finite cylinder shape ...
      if((B1p||B2p)&&(B1n||B2n)) {
         _HitCode = 0x0;
         // if the ray enters through the ceiling or else the floor plane, the corresponding travel
         // coordinate is adapted accordingly; necessity of adapting is reported in setting the hit
         // code bit #0
         if(!B1p) {
            _HitCode |= 0x1;
            T1 = (_halfHeight-_localRay.Origin.y)/_localRay.Direction.y;
         } else if(!B1n) {
            _HitCode |= 0x1;
            T1 = (-_halfHeight-_localRay.Origin.y)/_localRay.Direction.y;
         }
         // if the ray leaves through the ceiling or else the floor plane, the corresponding travel
         // coordinate is adapted accordingly; necessity of adapting is reported in setting the hit
         // code bit #1
         if(!B2p) {
            _HitCode |= 0x2;
            T2 = (_halfHeight-_localRay.Origin.y)/_localRay.Direction.y;
         } else if(!B2n) {
            _HitCode |= 0x2;
            T2 = (-_halfHeight-_localRay.Origin.y)/_localRay.Direction.y;
         }
         // if the ceiling or floor plane exists, or the ray hits the cylinder outside these planes
         // (either when entering or when leaving), then real hits occur which must be reported to
         // the span list
         if((_HitCode!=0x3)||_Ceiling||_Floor) {
            HitExists = true;
            // if either the ceiling or the floor plane lacks existance, but the ray hits those
            // plane, the corresponding travel coordinate and hit code must be adapted
            if(!((B1p||_Ceiling)&&(B1n||_Floor))) {
               T1 = T2;
               _HitCode &= 0x2;
               _HitCode |= _HitCode>>1;
            } else if(!((B2p||_Ceiling)&&(B2n||_Floor))) {
               T2 = T1;
               _HitCode &= 0x1;
               _HitCode |= _HitCode<<1;
            }
            _HitSeparation = 0.5*(T1+T2);
            // report hits to span list
            Spans.addNewSpan(*this,T1,T2);
         }
      }
   }
   return HitExists;
}

Some explanations: The result of an intersection computation is a SpanList. Here a span is the distance from the ray's origin along its direction until the ray enters and then leaves a volume. If the object is hollow, then the span's enter and leave distances are the same. (This concept was chosen to allow even for multiple intersection as might occur for e.g. a torus.) The SpanList then is an ordered list of spans.

The distances along the ray are stored as multiples of the ray's direction vector. This allows to apply the distances in any space, since the ray's direction vector is not re-normalized after transforming into a local space. So the actual intersection points in e.g. world space are calculated by setting in the distances as the world space's ray parameter.

This topic is closed to new replies.

Advertisement