# capsule (or swept-sphere) - box collision

This topic is 5073 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
Quote:
 Original post by RPTDi 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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 axisr = capsule radiusfor each box face f  find intersection point for segment vs f expanded by r  if point closest so far    record it as closestfor 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 closestfor each box edge e  find closest intersection point for segment vs edge cylinder with radius r  if point closest so far    record it as closestreturn 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 on other sites
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 on other sites
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?

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 15
• 21
• 26
• 11