Server Help Forum Index Server Help
Community forums for Subgame, ASSS, and bots
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   StatisticsStatistics   RegisterRegister 
 ProfileProfile   Login to check your private messagesLogin to check your private messages   LoginLogin (SSL) 

Server Help | ASSS Wiki (0) | Shanky.com
Cylinder vs Box collision detection

 
Post new topic   Reply to topic Printable version
 View previous topic  MrBrain can u fix ur zone map so ppl d... Post :: Post My first mini rap!  View next topic  
Author Message
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Mon May 17, 2010 4:30 pm   Post maybe stupid    Post subject: Cylinder vs Box collision detection Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Mon May 17, 2010 4:45 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
Back to top
View users profile Send private message Add User to Ignore List
Dr Brain
Flip-flopping like a wind surfer


Age:38
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Mon May 17, 2010 4:50 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Dr Brain
Flip-flopping like a wind surfer


Age:38
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Mon May 17, 2010 5:02 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Mon May 17, 2010 5:07 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
Dr Brain
Flip-flopping like a wind surfer


Age:38
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Mon May 17, 2010 5:17 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Dr Brain
Flip-flopping like a wind surfer


Age:38
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Mon May 17, 2010 5:30 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Mon May 17, 2010 5:32 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
Dr Brain
Flip-flopping like a wind surfer


Age:38
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Mon May 17, 2010 5:38 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

Projection isn't the right word, I'm sorry. I meant the intersection of the cylinder with the plane.
Back to top
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Mon May 17, 2010 5:44 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

ooooooooooooooooooooh

ok
Back to top
View users profile Send private message Add User to Ignore List
Cheese
Wow Cheese is so helpful!


Joined: Mar 18 2007
Posts: 1017
Offline

PostPosted: Mon May 17, 2010 5:45 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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


i disagree icon_biggrin.gif
_________________
SSC Distension Owner
SSCU Trench Wars Developer
Back to top
View users profile Send private message Add User to Ignore List Visit posters website AIM Address
Dr Brain
Flip-flopping like a wind surfer


Age:38
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Mon May 17, 2010 5:53 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Mon May 17, 2010 5:55 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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 tongue.gif
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
View users profile Send private message Add User to Ignore List
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Mon May 17, 2010 6:10 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

Anyway... tired now... thanks man
Back to top
View users profile Send private message Add User to Ignore List
L.C.
Server Help Squatter


Age:33
Gender:Gender:Male
Joined: Jan 03 2003
Posts: 574
Location: Missouri, US
Offline

PostPosted: Wed May 19, 2010 2:09 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

Samapico wrote:
Anyway... tired now... thanks man
pwn't.
Back to top
View users profile Send private message Add User to Ignore List Send email Visit posters website AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Wed May 19, 2010 5:10 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

I hate you all, immature Internet people!
Back to top
View users profile Send private message Add User to Ignore List
Blocks
Novice


Joined: Jul 13 2006
Posts: 95
Location: California
Offline

PostPosted: Tue May 25, 2010 1:55 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List Send email AIM Address MSN Messenger
K'
You can win any war if you start a year early


Gender:Gender:Male
Joined: Jul 13 2006
Posts: 271
Location: Southtown
Offline

PostPosted: Tue May 25, 2010 5:07 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

3D is just cpu taxing heavy. Stick to 2D. Elipses and rectangles. Work best.
Back to top
View users profile Send private message Add User to Ignore List
Samapico the Great
Guest


Offline

PostPosted: Tue May 25, 2010 5:35 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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

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 tongue.gif

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

PostPosted: Wed May 26, 2010 11:28 am   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
Back to top
L.C.
Server Help Squatter


Age:33
Gender:Gender:Male
Joined: Jan 03 2003
Posts: 574
Location: Missouri, US
Offline

PostPosted: Tue Jun 01, 2010 3:43 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List Send email Visit posters website AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Tue Jun 01, 2010 5:36 pm   Post maybe stupid    Post subject: Reply to topic Reply with quote

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
View users profile Send private message Add User to Ignore List
Display posts from previous:   
Post new topic   Reply to topic    Server Help Forum Index -> Trash Talk All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
View online users | View Statistics | View Ignored List


Software by php BB © php BB Group
Server Load: 1035 page(s) served in previous 5 minutes.

phpBB Created this page in 0.691981 seconds : 49 queries executed (65.0%): GZIP compression disabled