Server Help :: View topic - Cylinder vs Box collision detection

Server Help

Trash Talk - Cylinder vs Box collision detection

Samapico - Mon May 17, 2010 4:30 pm
Post subject: Cylinder vs Box collision detection

I know there are some math freaks in here... I need to program something (in LabView) that will detect if a cylinder intersects with an axis-aligned bounding box (the cylinder is not axis-aligned). With some searching around it seems the cylinder is a particularly hard problem in game physics and such, and that they mostly use "capsules" (cylinders with spherical caps) to make it easier.
I need to make the test with a flat-capped cylinder, though... But I don't need the algorithm to tell me where the intersection is, I just need a Yes/No output.

The cylinder/box test searches an octree, and I'll eventually need to test cylinder vs triangles...

The algorithm doesn't need to be super fast, it's not executed continuously like in a physics engine... But it can't be super slow either.

Any ideas?

Samapico - Mon May 17, 2010 4:45 pm
Post subject:

Found this, but I don't quite understand everything in there, being more or less of a newbie at these things.

http://www.insomniacgames.com/tech/articles/0907/files/cylinderCollision.pdf

Dr Brain - Mon May 17, 2010 4:50 pm
Post subject:

It took me a while to understand the problem.

It seems to me like the easiest way to break it up is to rotate the space so the cylinder is in the standard cylindrical coordinates, and then do intersection testing on the six faces of the rectangular prism (if any one intersects, then there is a collision, otherwise there is no collision).

I'm not sure where to go from there, though. Seems like you have to break it up into a bunch of cases.

Dr Brain - Mon May 17, 2010 5:02 pm
Post subject:

Ok, I've thought about it a bit more, and here is what I have:

The projection of an infinite cylinder on a plane is an ellipse. The projection of an finite cylinder on a plane is an ellipse with possible truncation perpendicular with the long axis of the ellipse.

Case 1: Full ellipse
Case 2: Truncated ellipse on one side
Case 3: Truncated ellipse on two sides
Case 4: No intersection with plane

Then all you have to do is figure out how to do intersections between a quadrilateral (rotated rectangle, in this case) and a truncated ellipse.

This helps to transform the three dimensional problem into six simpler two dimensional problems.

Samapico - Mon May 17, 2010 5:07 pm
Post subject:

hmmmm, the projection of a circle on a plane is an ellipse... wouldn't the projection of cylinder be... some kind of:
_____
(_____)
kind of long ellipse? (instead of () being the projection of a circle)

Also... the bounding box is already axis-aligned, so the cylinder cannot be shifted to be axis-aligned as well; unless the box becomes oriented (OBB)

Dr Brain - Mon May 17, 2010 5:17 pm
Post subject:

Aha, since a truncated ellipse is the boolean AND of an ellipse and a rectangle, it's easier. Just do the intersection calculation for both vs. the translated face, and if they're both true, it's intersecting.

I'll post a picture in a moment.

Dr Brain - Mon May 17, 2010 5:30 pm
Post subject:

Here:

Blue is the face of the bounding prism.
Red is the projection of the cylinder on the plane.
Green takes the height of the cylinder into account.
Yellow is the actual shape to check for intersection with blue.

Samapico - Mon May 17, 2010 5:32 pm
Post subject:

I don't think projections are enough... posting pic soon

Imagine a cube, place a cylinder with a relatively large radius on the corner of the cube, flat face touching it (with a 0.1mm gap, let's say). You could look at it from any axis-aligned point of view (i.e. looking straight at the faces of the cube), and you will always see a 'collision' on the 3 planes.
You have to look at the cylinder so you don't see it's flat face to see the gap between the box and cylinder.

(No, these DO NOT look like penises, ok?)

Dr Brain - Mon May 17, 2010 5:38 pm
Post subject:

Projection isn't the right word, I'm sorry. I meant the intersection of the cylinder with the plane.

Samapico - Mon May 17, 2010 5:44 pm
Post subject:

ooooooooooooooooooooh

ok

Cheese - Mon May 17, 2010 5:45 pm
Post subject:

Samapico wrote:

(No, these DO NOT look like penises, ok?)

i disagree

Dr Brain - Mon May 17, 2010 5:53 pm
Post subject:

Yeah, there's a heck of a lot of trig involved in actually getting everything into an ellipse, box and rectangle. And don't forget to check for divide by zeros when your cylinder is aligned with an axis. But once you're there, it's easy.

Samapico - Mon May 17, 2010 5:55 pm
Post subject:

So... you'd make that check for each of the 6 faces of the box... hmmm

It all makes sense, not quite sure how to get that intersection ellipse though... in ma... OUCH FUCK OUCH I just bit my lip pretty hard... not exactly the lip.. kind of inside.. but.. it tastes like blood.. ugh... damn chewing gum...

I was saying... in maths the cylinder would be some kind of function like x^2+y^2 < r^2, somehow defined with lower and upper limits... My cylinder has radius, height, x, y, z, and a rotational matrix....

I managed to understand the stuff in:
http://www.insomniacgames.com/tech/articles/0907/files/cylinderCollision.pdf
At page 14... but the last line of the page, and the stuff after it, he lost me

The rest before is actually pretty easy with the values I have at hand... Well except his 'ClosestPointsLineVsAABB' function that I didn't check yet...

Samapico - Mon May 17, 2010 6:10 pm
Post subject:

Anyway... tired now... thanks man

L.C. - Wed May 19, 2010 2:09 pm
Post subject:

Samapico wrote:

Anyway... tired now... thanks man

pwn't.

Samapico - Wed May 19, 2010 5:10 pm
Post subject:

I hate you all, immature Internet people!

Blocks - Tue May 25, 2010 1:55 am
Post subject:

The two times I've come across bounding boxes and collision detection, cylinders have always been approximated as regular right prisms. Octagonal is actually pretty good (4 boxes), 16agonal is very good (8 boxes). It's a lot simpler just to keep all your bounding boxes as ... boxes.

K' - Tue May 25, 2010 5:07 pm
Post subject:

3D is just cpu taxing heavy. Stick to 2D. Elipses and rectangles. Work best.

Anonymous - Tue May 25, 2010 5:35 pm
Post subject:

... What if I need that 3rd dimension?

Computing the 2D cross-section / intersection would be just as hard

And as I said, this isn't a game or anything, I don't care if it takes a millisecond to compute (OH NOES, I HAS A SQUARE ROOT)

Also... I found a way to do it in the Programming Gems book, but it's actually to quickly eliminate non-visible cylinders in a frustum (truncated square-based pyramid Field of View), and it gives some false-positives in some cases... But I think I could add a check with a plane vs axis-aligned box check

That one's probably much easier, but my day at work is done, so... if you want to have fun, find me a plane vs box intersect test

To quickly explain the solution I'm using:
Take the 2 endpoints of the cylinder;
For each of the 6 box planes:
-Adjust the plane with the 'effective radius', which is the dot product of the cylinder's axis and the plane's normal, multiplied by the actual radius.
-Test both endpoints with each of these planes

It works fine except when the cylinder is near a corner, where you kind of detect a "collision" with both adjusted planes... But I want to add a condition that the cylinder's cap plane must also intersect with the box.
I'll show images when I have some time.

Anonymous - Wed May 26, 2010 11:28 am
Post subject:

Just found this... Seems like a pretty simple cylinder vs plane test... And if I just test against 6 planes, it should work

Code: Show/Hide

template <typename Real>
bool IntrPlane3Cylinder3<Real>::Test ()
{
// Compute extremes of signed distance Dot(N,X)-d for points on the
// cylinder. These are
// min = (Dot(N,C)-d) - r*sqrt(1-Dot(N,W)^2) - (h/2)*|Dot(N,W)|
// max = (Dot(N,C)-d) + r*sqrt(1-Dot(N,W)^2) + (h/2)*|Dot(N,W)|
Real sDist = mPlane->DistanceTo(mCylinder->Axis.Origin);
Real absNdW = Math<Real>::FAbs(mPlane->Normal.Dot(
mCylinder->Axis.Direction));
Real root = Math<Real>::Sqrt(Math<Real>::FAbs((Real)1 - absNdW*absNdW));
Real term = mCylinder->Radius*root +
((Real)0.5)*mCylinder->Height*absNdW;

// Intersection occurs if and only if 0 is in the interval [min,max].
return Math<Real>::FAbs(sDist) <= term;
}

Though I'd have to tweak it cause I want it to be anywhere inside all of the 6 planes, while this (I think) checks if a cylinder really intersects the plane. If my cylinder is completely below a plane, I want it to consider it as an intersection

L.C. - Tue Jun 01, 2010 3:43 pm
Post subject:

Useless information, but for a sphere:

Origin + Radius + Direction its heading = Single test to see if it's colliding

Learned that from a buddy. You probably know it.

Samapico - Tue Jun 01, 2010 5:36 pm
Post subject:

Spheres are obviously easy...

But anyway, I went the easy road and generated N oriented bounding boxes to estimate my cylinder, it works just fine.

There are 2 ways to surround the cylinder with OBB's... one is to form a regular polygon around it (image 1):
length = 2*r
width = r*tan(pi/(2n))

The other way allows to reduce slightly the "wasted" space by reducing the width of each box so two adjacent boxes will have a junction right on the perimeter of the cylinder (image 2):
length = 2*r
width = r*sin(pi/(2n))

When n grows higher (4 boxes and more), the difference between the 2 is so small it doesn't matter much. But if you're using only 2 boxes, having a regular polygon around the cylinder would mean the 2 boxes would have a square base and would be completely overlapping, while if you use the 2nd way, both boxes would be forming a + kind of thing.

As for the OBB/AABB collision test code, I translated this guy's library:
http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html
(well, just the few functions I needed)