Re: Intersection of two cylinders

[Henningsen <alg@glinx.com>]

>    Does anyone know a fast algorithm to calculate the volume of the 
>intersection of two cylinders, or wher eI might find one? All the examples I 
>have so far been able to dig up through google requires some pretty 
>heavy-duty number crunching just to get an approximation :(

If you've made a solid search, I would assume that there simply is no simple
formula. The volume is given by a double integral, and if it cannot be
solved by a formula you will have to numerically approximate that integral,
which will require substantial computation irrespective of what type of
numerical integration method you choose.

>    I need to me able to detect when, and by how much, two cylinders defined 
>by a fixed point, a vector and a radius intersect as part of one of the 
>calculations my game needs to do for a high energy vortex simulation..

It's easy to find when they intersect: Just compute the distance between the
two central axes and compare with the sum of the radii. The difference
between the sum of the radii and the distance also gives you a measure of
how much they intersect, although a very different one from the volume you
want: Two parallel cylinders will intersect with an infinite volume when
they intersect at all, whereas the volume will be smallest when the axes are
at right angles. If it is important for your application to use the actual
volume of the intersection, you will need to do a numeriacl approximation to
the integral describing the volume. You could speed up that process
substantially by using a large steplength in your numerical integration
method. The steplengths you see in mathematical texts will usually go for a
*very* close approximation to the actual integral, whereas you could
probably get by with a very crude one, and use steplengths in the order of a
tenth of your cylinder radii, maybe. However, it would be easiest if you
could just get by with a measure of how close the central axes of the
cylinders come to each other. I'd suggest you examine your game design
closely to see whether you can evolve it in this manner.

Peter Henningsen
alifegames.com