Sign in to follow this  

Swept Capsule-Capsule intersection (3D)

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by oliii
swept 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Mercenarey
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...


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 this post


Link to post
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).

Share this post


Link to post
Share on other sites
I will look into your code in a few days, since Im going away for the weekend.

Starting by testing against infinite line-cylinder sounds like a good idea. I will test it, then I will report back :)

Share this post


Link to post
Share on other sites
Let we do things relatively to one capsule, so that capsule is not moving.
So we need to find intersection of capsule with "swept capsule" , as topic says.

Let at time t1 we have capsule with sphere centers placed at A,B, and at time t2 we have capsule with sphere centers placed at C,D . Let capsule radius is r.

To find intersection with swept capsule you need to

1: Check for intersection with capsules AB and CD
2: Check for intersections with capsules AC and BD
3: Check for intersection with polygons ABCD displaced by +-r along it's normal.
(that is, polygons [A+N*r,B+N*r,C+N*r,D+N*r] and [A-N*r,B-N*r,C-N*r,D-N*r] where N is normal)
You can do it in other order, do faster checks first...

By "capsule AB" i mean capsule with sphere centers in A,B , obviously.

Share this post


Link to post
Share on other sites
Do swept line line collision, where you simply return when the lines are close enough to each other. A capped cylinder is just the volume around a line extending out in all directions from the line a certain distance.

Share this post


Link to post
Share on other sites
Quote:
Original post by pTymN
Do swept line line collision, where you simply return when the lines are close enough to each other. A capped cylinder is just the volume around a line extending out in all directions from the line a certain distance.

Yes, and that's main reason why capsules is a popular thing for intersections and collisions....

Putting all together, it's intersection of capped cylinder with polygon, can be done by finding closest distance between segment and polygon...

Share this post


Link to post
Share on other sites
I made a simpler solution, and thus I haven't implemented a true capsule collision.

I really only need capsules for upright items (characters in my game world, trees etc.), and therefore I decided to implement that for now, and I will return to the more complex capsule collision when I need it.

There will be a whole other problem with sweep testing capsules if you allow them to turn as well. Each point on the segment will move with different velocities.


So this is what I did:
First I assure that the capsules are upright (axis pointing up in the world). Then I reduce the capsules to 2D circles, and raycast (one circle center is the ray origin, the combined velocity is the delta, the other circle is static and has the combined radius of the circles). I do this to see if we are even in the ballpark of a collision (and if the collision takes place on the x/z plane, the cylinder part, then I already have time t of collision).

If we are in this ballpark, I move the capsules forward to t (in reality I just take a copy of the base point, and move it forward, I know the axis Y-height and the radius, enough to do the Y-test) and do a 1D collision on the Y-axis, to see if the capsules will ever collide on the Y-axis. If not, then I don't have to take further action.
In the Y-axis test, I test if the overlap will occur on the top/bottom parts of the capsule, or it will collide on the middle, cylinder part.
If it will be on the top/bottom parts, I do an ordinary sphere-sphere sweep test between the top/bottom parts of the capsules. If it is on the middle, I already have the information (time t) from the circle-circle test (extracting further information like Point-Of-Intersection and Dividing Plane is easy once you have t).

I tested it realtime, and it seems solid so far.
One word of warning: If you do the 1D Y-axis test, then remember to add the Y-components of the velocities to the overlap test.


I know this is far from what I wanted to discuss originally, but since I don't need more than upright capsules at the moment, this will suffice for now.
The thought of turning capsules with different velocities really turned me off - I will take that fight when its really necessary :).

[Edited by - Mercenarey on December 21, 2004 6:40:21 PM]

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

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