• 12
• 27
• 9
• 9
• 20

# Swept Capsule-Capsule intersection (3D)

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

## Recommended Posts

I have been looking around for a solution to this problem. However, it is not easy to find anything. I figure, that I have to somehow make a segment-segment test with the axes of the capsules. But then again, that won't give me the time t when it will actually hit the surface of the capsule (when the radii collide). *sigh*, I am really lost on this problem. Can anyone help me? PS: I did google this problem, I even downloaded 4 different free engines to see if they had implemented this, but without luck.

##### Share on other sites
Did you download Magic Software's capsule/capsule code, available at the link below?

Magic Software Intersection code

You might also check out Miguel Gomez's article at gamasutra:

Simple Intersection Tests For Games

He discusses the swept-sphere intersection test. Registration to gamasutra is free, and there are many, many very handle articles there. (Its the free online archive site for Game Developer Magazine.

##### Share on other sites
swept capsules? You mean swept spheres, forming capsules.

##### Share on other sites
Quote:
 Original post by oliiiswept capsules? You mean swept spheres, forming capsules.linky

how do you know?

if youre really talking about swept capsules: well, they can rotate, so sweeping them isnt going to be solved analiticly. it should be very possible to derive a numerical method to sweep capsules tho.

however, i dont see what the big fuss with capsules is. i think they are quite impractical. why not use a more inituative element for your collision detection?

##### Share on other sites
the most simple way in my opinion (meaning i could implement it) is using a bisection method. just split your timestep in 2 and check for overlap. for a better description google it. If you really need the swept volume, i haven;t come across a good description either.

here's a demo: http://home.planet.nl/~woute890/debug.zip

##### Share on other sites
You could consider having a "dual" representation for the capsules. If they're moving slowly, use standard overlap tests. If they're moving fast, represent one of them with a set of spheres distributed (overlapping), and do a series of swept sphere-capsule tests (transform into the frame of the "other" capsule). This will give you an approximate collision time - if you need it more accurate then follow it up with a capsule-capsule overlap test at this collision time and adjust your result.

However, it's not clear from your original post if you mean swept capsules or swept spheres (thread title says one thing, your proposed solution suggests another...)

##### Share on other sites
Overlap tests is out of the question. I hate the idea, and none of my other other collision tests run on it. Too imprecise IMO.

-----------------------------

Olii:
Yes, I mean Capsule, not ellipsoid. A capsule consisting of a cylinder capped by two half-spheres.

-----------------------------

grhodes_at_work:
This is the code from Magic Studio:

template <class Real>bool Wml::TestIntersection (const Capsule3<Real>& rkC0,    const Capsule3<Real>& rkC1){    Real fSqrDist = SqrDistance<Real>(rkC0.Segment(),rkC1.Segment());    Real fRSum = rkC0.Radius() + rkC1.Radius();    Real fRSumSqr = fRSum*fRSum;    return fSqrDist <= fRSumSqr;}

As you can see it is a static test, while what I need is dynamic (swept).

-----------------------------

Both Olii and grhodes_at_work link to some sphere sweep tests. I already have successfully implemented that into my collision system. It is not the sphere parts of the capsule that is my problem, it is the cylinder part:

How do I know which points on the moving cylinders' axes will be the closest to each other upon collision? If I knew that, I could do a raycasting from one point to the other cylinder side's combined radius, to see if and when it will intersect.
That is how I solved the sphere vs. capsule intersection. But here I knew what point to raycast from (the sphere center), while I do not know what point on the cylinder axis that will be the closest.

And I have been on all your links :(
I find it strange, that there is not more material on this, considering how often capsules are debated as bounding volumes...

##### Share on other sites
Actually, I misread what you were asking. When you wrote swept capsule, and especially when you mentioned the segment-segment tests in your original post, I read, in my head, "swept spheres." Thought you were trying to find the intersection of spherical bounding volumes moving over a time step.

Hmm. Why not take a look a Magic-Software's Lozenge-Lozenge intersection. This may be closer to what you want (a lozenge being the set of points equidistant from a rectangle). Its not completely general, since swept capsules don't necessarily sweep perpendicular to their center axis and since if the centerline sweeps out of a plane the swept capsule will not be made of points equidistant from the resulting swept center surface. But, at least its something, :).

Keep in mind, as Eelco said, in the most general case you are not at all likely to find a closed-form solution. Why not just go with an iterative method rather than continue digging for a solution that may not be readily available or may not even exist. Alternately solve the math yourself. In the process you may discover why there isn't a solution out there.

Same link as before for Magic's lozenge stuff.

##### Share on other sites
Quote:
 Original post by MercenareyOverlap tests is out of the question. I hate the idea, and none of my other other collision tests run on it. Too imprecise IMO.-----------------------------Olii:Yes, I mean Capsule, not ellipsoid. A capsule consisting of a cylinder capped by two half-spheres.-----------------------------grhodes_at_work:This is the code from Magic Studio:template bool Wml::TestIntersection (const Capsule3& rkC0, const Capsule3& rkC1){ Real fSqrDist = SqrDistance(rkC0.Segment(),rkC1.Segment()); Real fRSum = rkC0.Radius() + rkC1.Radius(); Real fRSumSqr = fRSum*fRSum; return fSqrDist <= fRSumSqr;}As you can see it is a static test, while what I need is dynamic (swept).-----------------------------Both Olii and grhodes_at_work link to some sphere sweep tests. I already have successfully implemented that into my collision system. It is not the sphere parts of the capsule that is my problem, it is the cylinder part:How do I know which points on the moving cylinders' axes will be the closest to each other upon collision? If I knew that, I could do a raycasting from one point to the other cylinder side's combined radius, to see if and when it will intersect.That is how I solved the sphere vs. capsule intersection. But here I knew what point to raycast from (the sphere center), while I do not know what point on the cylinder axis that will be the closest.And I have been on all your links :(I find it strange, that there is not more material on this, considering how often capsules are debated as bounding volumes...

OK, if you need the closest point between the segments (the capsule core and the other segment), it's quite easy. First, the direction between the two closest points on both segments will be

Axis = Segment1.Dir x Segment2.Dir

from there, a geometrical solution would be to generate a plane containing Segment1 and aligned with the vector Axis, and test the intersection of segment2 with that plane.

that will give you the point on P2 Segment 2 the closest to segment 1. The point on segment1 is the closest point to P2 on Segment1.

in code....

Vector AB = B - A;Vector CD = D - C;Vector H = AB.Cross(CD);Vector N = AB.Cross(H);float  t1 = (C - A).Dot(N) / CD.Dot(N);t1 = (t1 < 0.0f)? 0.0f : (t1 > 1.0f)? 1.0f : t1;Vector I1 = C + t1 * CD;float  t0 = (I1 - A).Dot(AB) / (AB.Dot(AB));t0 = (t0 < 0.0f)? 0.0f : (t0 > 1.0f)? 1.0f : t0;Vector I0 = A + t0 * AB;

I0, I1 are the closest point on both segments. these are the closest points you are looking for. But it does not give you the time of collision. It merely tells you if two capsule intersected.

There is an analytical method that comes to the same result, so I won;t bother.

and the code of doing a sphere-sphere time of collisoin calculation can be easily extended for a cylinder. YOu just have to use the cylinder equation

[(P - C) x D]2 = r2

instead fo the sphere equation

(P - C)2 = r2

where in eq1, C is a point in the centre of the cylinder, D is the direction of the cylinder, r is obviously its radius.

##### Share on other sites
the solution from Magic Software is just the same as mine.

in dynamic, for a capsule test, you can have 3 types of collisions. vertex against vertex, vertex against edge, edge against edge.

ok, to simplify, I'm working in one of the edge's space. meaning, one edge is static, while the other will move towards it with added velocity. One edge will have a radius of 0 (it's then a line), while the other will have the radius eqaul to the sum of both radii (a thicker cylinder).

I'd start with the edge edge one. I'll first extent it to a infinite line translating to hit an infinite cylinder.

to find the time a line hits a cylinder is equivalent to finding the time when one of the vertex of the line hit a plane on the surface of the cylinder with normal Cylinder.Dir x Line.Dir

so,

AB = B - A; // direction of sweeping line with velocity V, passing through A, B
CD = D - C; // direction of cylinder passing through C, D
N = AB x CD;
d = N.Dot(C);
tcoll = (d - A.Dot(N)) / (V.Dot(N)); // time when the line hits the cylinder.

then you move the line at time tcoll. From then on, you use the static test to decide if you need to do an extra vertex-cylinder test, or an extra vertex-vertex test, or if you have a sgment hitting a capsule on the side and then tcoll is indeed the time of collision.

watch out for the algo above, it's imcomplete (you need to determine which 'side' of the cylinder to test, so check out the sign of d, and if the segment is moving towards the cylinder or moving away from it). Like the segment distance calculation is incomplete (if the segments are aligned for example, and CD.Dot(N) == 0.0f).