Sign in to follow this  
RPTD

capsule (or swept-sphere) - box collision

Recommended Posts

RPTD    340
to allow players to pick up an item directly in their line-of-sight i thought using a line segment or a ray would be best (and chosing the closes object as the one). now with my current collision framework i would have to implement a 'line/ray' collision volume to keep my generic code the way it is, which does not please me alot. that's where i though to 'misuse' capsules or swept spheres for it. in fact using a capsule of a small radius (or even 0) would yield the same as a ray and a capsule itself would be usefull at other places (my dragon would better fit in capsules than aabb's). now i tried coming up with an algorithme for capsule-aabb but somehow could not wrap my head around it. also google did not help me at all leaving me now a bit in the void. one thing that i found on google is that an idea would be to get the distance from a line-segment to an aabb and comparing this to the capsule radius. that's logical to me but i can't wrap my head around how to get this distance. i know geometric-tools has sources for such things but i do not want to dig down into the code and simply 'copy' it as i want to understand what's going on (c&p anybody can do). reducing all to a ray-aabb would place me at the same problem: i need the minimal distance of the ray to the aabb like in the capsule case. hence no matter how i turn it i end up at the same problem. somebody can give me some pointers in the right direction?

Share this post


Link to post
Share on other sites
jyk    2094
Couple of comments. First of all, intersecting a ray (with no radius) with an AABB doesn't require a ray-AABB distance function. If you need the actual intersection point, it can be done straightforwardly with slab intersections. If you only need a boolean result, it can be done even more straightforwardly with a quick SAT test. Neither of these algorithms is particularly difficult to code.

If you want the ray or segment to have a 'radius', that's another story. You're correct that a capsule-AABB test requires a segment-AABB distance test, which is a little complicated. The one piece of advice I would give about that would be to first code and test a segment-segment distance test, as that will likely be a necessary support function for the segment-AABB distance test. The segment-segment test will also give you capsule-capsule intersection for free, more or less.

There are some other ways this problem could be approached, and the capsule-AABB test could be a useful thing to have available. However, I'll also mention that if the aim is just to have a 'fat' ray for the purpose of object selection, an easier if less exact solution would be to just expand the object AABB by some amount.

Share this post


Link to post
Share on other sites
RPTD    340
it it not just the selection i want to use it for, espacially also to have better collision shapes for organic models. i use octrees and hence capsule-aabb would be a damn good thing to have. currently i have a visitor system to do collision detection, hence i pump in an arbitrary collision volume and get all colliders visited. with a small capsule i don'tt have to change this as the capsule i have already as stub in my collision system. for a ray though i need a bit more.

i tried to look already for a segment-segment distance method to get a capsule-capsule test but i got rather ugly things with quadratic equations and alike. is it really that tricky to have a segment-segment check?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by RPTD
i tried to look already for a segment-segment distance method to get a capsule-capsule test but i got rather ugly things with quadratic equations and alike. is it really that tricky to have a segment-segment check?
Don't be put off by the quadratic equations. No matter how you approach it, the first step in finding the distance between any two linear components (line, ray, segment) is to find the closest points between the infinite lines that support them. There are several ways to approach this problem conceptually (including the aforementioned quadratic minimization) but they all reduce to exactly the same thing: a simple system of 2 equations in 2 unknowns.

If you're working with rays or segments, the next step is to deal with the fact that the closest points on the supporting lines may not actually lie on the rays or segments. There are various ways to deal with this also, some more intuitive than others. The quadratic approach is elegant, but it does require digging into the calculus a bit (specifically, analyzing gradients and/or solving partial derivatives), so you might find the geometrical approach to be a little more accessible. An important point to make though is that the calculus approach is in no way less efficient than the other approaches; the differences are mostly conceptual.

Here is an article that discusses linear component distance tests and may demystify things a little. The only real gotcha is detecting and handling the parallel case, for which it can be tricky to choose an appropriate epsilon (I use a relative error test on the squared sine of the difference angle to deal with this). So yeah, the segment-segment test is a bit of a pain to write, but once you have it you'll get both segment-capsule intersection and capsule-capsule intersection essentially for free.

Share this post


Link to post
Share on other sites
RPTD    340
i used now more or less the code provided there. the first part i get easily the second one with the square-edge detection still looks strange to me but the code seems to work (according to tests). so far that's working and capsule-capsule should be no problem. left there is the capsule-aabb test.

about the ray-aabb test with sat... i could no more find that original article about the sat theories hence i googled my way through. according to my math it looks a bit strange that the projection of a vector a onto another vector b (as distance only) reduces to |a dot b|*|a|. somebody can enlighten me why this is valid? as for my math i end up with a slightly different term of |a dot b|*|a| / |b|.

Share this post


Link to post
Share on other sites
d00fus    328
The length of the axis (|b| in your example) is typically simplified away in a SAT test as it appears on both sides of the inequality (this can cause problems with very large or small axes but don't need to go into that here...).

As to your original problem with capsule-AABB intersection tests, if you need a boolean result only a SAT-based test will probably provide the best performance. The axes to test are listed in this message on the GameDevAlgorithms mailing list:

http://sourceforge.net/mailarchive/message.php?msg_id=10449906

An alternative approach that gives the TOI and contact point is given in Christer Ericson's book Real-time Collision Detection (I don't have it here so can't reference it exactly). It is based on expanding the box by the capsule radius and doing a line segment test. You can test all the features naively (8 corner spheres, 12 fat edges and 6 expanded faces) or use the direction of the segment to cull out the features that cannot be hit.

Both of these approach will generally prove faster than the distance method.

Share this post


Link to post
Share on other sites
RPTD    340
already thought about that SAT test myself but got into troubles as the round caps of the capsule seem to be very hairy to find appropriate axes to test with. the fat aabb test looks rather straight forward, although a bit slower than a SAT test based one but in general you should anyways keep difficult shape collisions down, which is why i want to use capsule-aabb only for rough testing. the big time eater will be triangle-triangle detection anyways.

i'll try out that feature solution as all i need is already there ( segment-capsule, sphere-capsule and segment-aabb ), except the segment-aabb, but that should be not too hard to realize as a 6x face-segment intersection test. i guess this should be fast enough compared to a full blown solution, what you think?

Share this post


Link to post
Share on other sites
d00fus    328
Yeah the axes can be a bit harder to figure out for objects like capsules, however I find it helps to think in terms of feature contacts: the possible contact configurations for a capsule hitting an AABB are cap-vert, cap-edge, cap-face, cylinder-vert, cylinder-edge, cylinder-face. It is these configurations that give rise to the axes listed in that post on GDA I referenced.

The simple version of the expanded box method is quite easy as you say, because generally you already have the primitive operations needed. It becomes a matter of finding the first impact from all the features, roughly as follows:


segment = capsule axis
r = capsule radius
for each box face f
find intersection point for segment vs f expanded by r
if point closest so far
record it as closest
for each box vert v
find closest intersection point for segment vs sphere centered at v with radius r
if point closest so far
record it as closest
for each box edge e
find closest intersection point for segment vs edge cylinder with radius r
if point closest so far
record it as closest
return closest intersection



Some of the features can be removed as I indicated earlier, for example you can't hit faces facing away from the segment without hitting another feature first.

Share this post


Link to post
Share on other sites
RPTD    340
i'll go into that feature-collision direction as it looks straight forward and furthermore that kind of collisions are scarce as most are of sphere-aabb or aabb-aabb nature and only in possible collision cases i go down into more refined collision volumes. thx for the help as i completly forgot about the simple things of (coding-)life... that's the downside of university: you start to think too complicated [grin]

Share this post


Link to post
Share on other sites
RPTD    340
have another question. i thought about what would happen if i go thee distance segment-aabb way and in fact take the closest distance from the segment to one of my 6 faces. now what i am not sure about this idea is what the closest distance in terms of definition would be. a closest point from the quad(plane) is perpendicular to the quad(plane). the closest point on a segment is perpendicular to the segment direction. now those two definitions somehow harass each other (unless i get something wrong). now which closest-distance definition is the right one?

Share this post


Link to post
Share on other sites
d00fus    328
I'm not sure what you mean by "the closest point on a segment is perpendicular to the segment direction". The closest point on the segment is simply the point which minimizes the distance to the box. The vector from the the closest point on the segment to the closest point on the box needn't be perpendicular to the segment direction, think for example of this case:


|
|
|
x

-----x-------


The separation vector in this case is parallel to the segment direction.

Share this post


Link to post
Share on other sites
RPTD    340
i guess i see where i made the error in my thinking. in the segment-segment distance check you calculate the two closest points giving the distance, which is what i assume to be the case here to. in that case the closest point on the line is perpendicular to the plane and then clamped to 0 <= lamba <= 1 range in that case.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this