Author |
Message |
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Mon May 17, 2010 4:30 pm Post maybe stupid 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? _________________ (Insert a bunch of dead links here)
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
|
Back to top |
|
|
Dr Brain Flip-flopping like a wind surfer
Age:38 Gender: Joined: Dec 01 2002 Posts: 3502 Location: Hyperspace Offline
|
Posted: Mon May 17, 2010 4:50 pm Post maybe stupid 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. _________________ Hyperspace Owner
Smong> so long as 99% deaths feel lame it will always be hyperspace to me
|
|
Back to top |
|
|
Dr Brain Flip-flopping like a wind surfer
Age:38 Gender: Joined: Dec 01 2002 Posts: 3502 Location: Hyperspace Offline
|
Posted: Mon May 17, 2010 5:02 pm Post maybe stupid 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.
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Mon May 17, 2010 5:07 pm Post maybe stupid 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)
Last edited by Samapico on Mon May 17, 2010 5:18 pm, edited 1 time in total |
|
Back to top |
|
|
Dr Brain Flip-flopping like a wind surfer
Age:38 Gender: Joined: Dec 01 2002 Posts: 3502 Location: Hyperspace Offline
|
Posted: Mon May 17, 2010 5:17 pm Post maybe stupid 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.
|
|
Back to top |
|
|
Dr Brain Flip-flopping like a wind surfer
Age:38 Gender: Joined: Dec 01 2002 Posts: 3502 Location: Hyperspace Offline
|
Posted: Mon May 17, 2010 5:30 pm Post maybe stupid 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.
intersection.png - 6.5 KB
File downloaded or viewed 34 time(s)
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Mon May 17, 2010 5:32 pm Post maybe stupid 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?)
cyl coll.png - 7.21 KB
File downloaded or viewed 29 time(s)
|
|
Back to top |
|
|
Dr Brain Flip-flopping like a wind surfer
Age:38 Gender: Joined: Dec 01 2002 Posts: 3502 Location: Hyperspace Offline
|
Posted: Mon May 17, 2010 5:38 pm Post maybe stupid Post subject: |
|
|
|
|
Projection isn't the right word, I'm sorry. I meant the intersection of the cylinder with the plane.
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Mon May 17, 2010 5:44 pm Post maybe stupid Post subject: |
|
|
|
|
ooooooooooooooooooooh
ok
|
|
Back to top |
|
|
Cheese Wow Cheese is so helpful!
Joined: Mar 18 2007 Posts: 1017 Offline
|
Posted: Mon May 17, 2010 5:45 pm Post maybe stupid Post subject: |
|
|
|
|
Samapico wrote: | (No, these DO NOT look like penises, ok?) |
i disagree _________________ SSC Distension Owner
SSCU Trench Wars Developer
|
|
Back to top |
|
|
Dr Brain Flip-flopping like a wind surfer
Age:38 Gender: Joined: Dec 01 2002 Posts: 3502 Location: Hyperspace Offline
|
Posted: Mon May 17, 2010 5:53 pm Post maybe stupid 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.
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Mon May 17, 2010 5:55 pm Post maybe stupid 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...
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Mon May 17, 2010 6:10 pm Post maybe stupid Post subject: |
|
|
|
|
Anyway... tired now... thanks man
|
|
Back to top |
|
|
L.C. Server Help Squatter
Age:33 Gender: Joined: Jan 03 2003 Posts: 574 Location: Missouri, US Offline
|
Posted: Wed May 19, 2010 2:09 pm Post maybe stupid Post subject: |
|
|
|
|
Samapico wrote: | Anyway... tired now... thanks man | pwn't.
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Wed May 19, 2010 5:10 pm Post maybe stupid Post subject: |
|
|
|
|
I hate you all, immature Internet people!
|
|
Back to top |
|
|
Blocks Novice
Joined: Jul 13 2006 Posts: 95 Location: California Offline
|
Posted: Tue May 25, 2010 1:55 am Post maybe stupid 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.
|
|
Back to top |
|
|
K' You can win any war if you start a year early
Gender: Joined: Jul 13 2006 Posts: 271 Location: Southtown Offline
|
Posted: Tue May 25, 2010 5:07 pm Post maybe stupid Post subject: |
|
|
|
|
3D is just cpu taxing heavy. Stick to 2D. Elipses and rectangles. Work best.
|
|
Back to top |
|
|
Samapico the Great Guest
Offline
|
Posted: Tue May 25, 2010 5:35 pm Post maybe stupid 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.
|
|
Back to top |
|
|
Samapico the Awesome Guest
Offline
|
Posted: Wed May 26, 2010 11:28 am Post maybe stupid 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
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
|
|
Back to top |
|
|
L.C. Server Help Squatter
Age:33 Gender: Joined: Jan 03 2003 Posts: 574 Location: Missouri, US Offline
|
Posted: Tue Jun 01, 2010 3:43 pm Post maybe stupid 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.
|
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Tue Jun 01, 2010 5:36 pm Post maybe stupid 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)
Cylinder3.png - 27.34 KB
File downloaded or viewed 63 time(s)
Cylinder2.png - 26.44 KB
File downloaded or viewed 51 time(s)
Cylinder1.png - 22.84 KB
File downloaded or viewed 51 time(s)
|
|
Back to top |
|
|
|