[ODE] Box - Cylinder collision?

[Pierre Terdiman]

> Are you claiming that nobody has ever implemented this?

Errr, no. I even said AERO may have an implementation. I'm saying it's not
obvious. Certainly not as common as box-box.

> It's not that
> it's impossible, or even difficult.  It's probably easier than box-box
> collision in fact.  (Capped cylinders are easy to intersect with things.
> In fact, that's the only reason for spherical caps.)

Wait, are we speaking about cylinders or LSS (a.k.a. capsules) ? I assume
you're thinking about a capsule when you say "spherical caps". In that case,
that's very easy indeed. All the code you want in, say Magic. But for real
cylinders, it's not obvious, it's not common, it's not easy.

Attached below is an old post from the GD-Algorithm list, thread named
"Cylinder vs everything collision detection". Huge thread. Bottom line is,
nobody really had a solution for box-cylinder.

> If you're comfortable with the math and kinematics, why don't you
> implement it and contribute it?  You could base it on sphere-box.  We
> could all use it...

I don't see how to implement it easily, no. And I've enough work already for
Opcode 1.3 :)

Pierre

=[ attached mail below ]===========================

Greetings!

I'm implementing collision detection for a 3D engine at the momement, and
I've decided that a cylinder around the characters in the world will
probably be the best way to handle their collision detection against the
geometry of the world.  This way they can rotate in place without changing
what they are colliding with (unlike object oriented bounding boxes, OOBB).
So I have found myself looking for collision detection algorithms that check
against cylinders, but unfortunately I can't seem to find much info out
there.  If anyone can point me in the right direction for finding out this
info, I would be mucho appreciative.  Below are the checks I'll probably
have to do, and my current thinking as to how to solve them.  My cylinder is
currently defined as an endpoint, a normalized vector giving the direction
of the axis, a height along that axis, and a radius.


** Cylinder vs point **

  Here I can find the closest point on the axis to the point via a dot
product with the axis vector.  This will tell me if the point is within the
height of the cylinder.  If it is, then I check the distance between the
point and the calculated point on the axis, and compare that against the
radius.  No problem here.

** Cylinder vs ray/line segment **

  Graphics Gems IV had an algorithm for this.  Basically you find a vector
that is perpendicular to both the axis and the ray.  Then you take a vector
from the endpoint of the cylinder to a point on the ray.  You then project
this vector onto your perpendicular vector, and compare that length against
the radius.   If you have a hit, you also have to check the collision points
to make sure either the point it enters or leaves the cylinder is within the
cylinder length, or that the ray goes through the endcap at the bounding
plane.  No real problem here.


** Cylinder vs sphere **

  Perform the same cylinder vs point test with the center of the sphere.  If
the point is within the height of the cylinder, then you check the distance
vs the radius of the sphere plus the radius of the cylinder.  If the point
lies greater than the radius of the sphere away from the endpoints, then you
have a miss.  Otherwise you have to check for a collision with the endcap.
One way to do this would be to find the nearest point on the plane to the
sphere center, and get the distance from the sphere center to that point.
With that distance plus the radius of the sphere, we can find the radius of
the circle where the sphere intersects the endcap plane.  Then you compare
the distance between the sphere center and the axis (previously calculated)
vs the radius of the cylinder plus the radius of the intersection circle.

  I'm not sure if this is the most efficient way to go or not, but it seems
like it should work pretty well.  Comments?


** Cylinder vs plane **

  Here I can plug the two endpoints of the cylinder into the plane equation.
If they are on opposite sides of the plane, we have a definite collision.
Otherwise we take the endpoint nearest the plane and do some further
calculation.  A cross product with the cylinder axis and the plane normal
will give us the normal to a plane that cuts through the center of the
cylinder and is perpendicular to the plane (and tell us if the cylinder axis
is parallel to the plane normal or not).  Another cross product with the
normal of the perpendicular plane and the cylinder axis will give us the
vector from the cylinder endpoint to the nearest point on the edge of the
cylinder to the plane (or directly away from this point).  Then we can
either calculate the two cylinder edge points (the one nearest and the one
farthest from the plane) and see if they are on opposite sides of the plane
from the cylinder endpoint, or perform a ray vs plane intersection and check
the distance to the intersection point for comparison to the cylinder
radius.  Either way we can determine if we have a collision with the plane.

  I worked this approach out myself, so I'm not sure if there is a more
efficient one out there or not.  Also it only tells us if there is a
collision or not; it doesn't give the amount of the collision and only gives
its general location (at most a point intersection).  This matters in the
cylinder vs OOBB approach, because you can't easily just do a check against
the 6 planes of the bounding box to see if you are colliding with it or not.


** Cylinder vs tri **

  Here I would transform the three vertices of the tri into cylinder object
space (radius in the x,y plane, axis pointing up the z axis).  Then I clip
the tri to the endcap bounding planes which gives me an edge/vertex list.
This is projected to the x/y plane by dropping the z value, and then you
find the minimum distance between the line segments and the origin.  Then
you compare each distance against the cylinder radius to see if an edge
intersects.  If no edge intersects then you still might have the polygon
completely surrounding the cylinder, so you do a point-in-poly check with
the origin against all the edges, which should be quick to figure out with
an edge crossing test.

  Again, this is an approach I worked out myself, so I don't know if there
is a better approach or not.  Comments?


** Cylinder vs OOBB **

  Here I get kinda stumped.  I'm using a separating axis approach for my
OOBB vs OOBB test, and I suppose a similar approach could work with OOBB vs
Cylinder.  But do you use the same 15 axis to check against as you would in
the OOBB vs OOBB test?  I have a feeling I'll have to go through and resolve
the calculations for the size of the cylinder projected on the axis (lots of
additional math to work out by hand and reduce... blech).  I haven't found a
single piece of code or paper describing how to handle this kind of
collision, and I will probably be making it quite often in my code.  Also I
don't know if surrounding the cylinder with an OOBB as a first check against
the other OOBB would be a speedup or not.  I REALLY need advice on this one.


** Cylinder vs Cylinder **

  Not 100% certain about this one either.  You might try to solve it like
the ray vs cylinder test, but you have to take into consideration that they
are both bound volumes.  I haven't done much thought on this one yet.  Of
course if the cylinders have parallel axis, then it is simply a distance
between line test and a top/bottom bounding plane test on the remaining
axis.  I'd appreciate any thoughts on this one too.


Thanks in advance for any input.  Rather than just throw out my questions, I
thought I'd cover what I've already thought out so I can contribute
something positive to the list while at the same time picking everyone's
collective brains. (^_^)

Thanks,
Michael Duffy