Sign in to follow this  

How do you do swept (translation only) capsule collision?

This topic is 4517 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

Has anyone implemented swept capsule collision before? I'm not so much interested in taking rotation into account, mainly just translation (to match the swept test I have for SAT on boxes). I want to collide capsules with basic primitives (other capsules, spheres, boxes, triangles etc). Oh and by capsule I mean a line with a radius (like a cylinder with hemispheres on each each). cheers -Steve.

Share this post


Link to post
Share on other sites
Hello,

I suggest take a look at OPCODE collision detection library (http://www.codercorner.com/Opcode.htm), I am sure it contains a swept capsule collision query.

Hope that helps you,
Oscar

Share this post


Link to post
Share on other sites
Quote:
Has anyone implemented swept capsule collision before? I'm not so much interested in taking rotation into account, mainly just translation (to match the swept test I have for SAT on boxes). I want to collide capsules with basic primitives (other capsules, spheres, boxes, triangles etc).
Hi Steve,

I doubt I can tell you anything you don't already know, but as this is an area of interest for me, I'm going to chip in.
Quote:
I suggest take a look at OPCODE collision detection library..., I am sure it contains a swept capsule collision query.
I can't say for sure, but I doubt that is the case. I'll also mention that geometrictools.com, a go-to source for intersection tests, doesn't have code for the tests you mentioned (I don't think).

Anyway, from my experience at least, swept capsule-sphere tests are quite doable, but the other primitives you mentioned are more difficult. The capsule-plane test is easy, but once you introduce other features it gets complicated very quickly.

You probably also know that the GJK algorithm can be used to detect swept intersection between most convex objects, including capsules. The problem, however, is that implementing swept GJK robustly is a pain.

I haven't tried this, but perhaps GJK could be special-cased for the tests you mentioned. For example, the CSO of a triangle and a capsule would be, I think, an oblique triangular prism with a radius. Perhaps a custom routine could be devised to raycast against this shape, and from there you could derive a swept capsule-triangle test.

I recently ran across a discussion of this topic - it starts on this page. I don't know that they came to any clear conclusions, though.

Share this post


Link to post
Share on other sites
Thanks for the replies.

After reading the mentioned threads (and complete lack of info on the net), it looks like I'm going to have to bite the bullet and take a crack at GJK.

Anyone recommend any good source demos/starting points for GJK? (I'm not concerned with swept collision for an initial implementation).

thanks
-Steve.

Share this post


Link to post
Share on other sites
For GJK, this book and this book, for starters.

For some swept tests, such as those involving cones, cylinders, or ellipsoids, GJK may be the only practical solution. For capsules, though, I still think one could come up with custom solutions that were easier to implement. After reading your post I was curious, and so took a stab at implementing swept capsule/sphere and capsule/tri tests as described in my first reply. I haven't got contact points for the capsule/tri test yet, but otherwise it all seems to work. Here are a couple of screenshots:





Gray is the old position, white the new position, and violet the positions at the first time of intersection. Anyway, GJK may very well be the way to go, but I thought you might be interested in the above anyway.

Share this post


Link to post
Share on other sites
My reckoning was that if your object is moving fast enough to need a swept test (my code does only an overlap test if the relative motion is smaller than dt * radius), then the exact result isn't so important - the main thing being to prevent objects passing through each other. So, a really simple, and possibly fast(?), solution is to represent the cylinder as a number of overlapping spheres along its length and sweep them, since that's pretty easy. This also gives you a representation of the capsule rotation, so long as the capsule doesn't rotate too much over the sweep time. Not too good if the capsule is long-and-thin, of course.

Share this post


Link to post
Share on other sites
I was thinking you just move your shape by 0.9 * dt * radius at the most until you've used up the total translation.

That way you are guaranteed an overlap if there is a collision, at least for single radius shapes like spheres, lss and rss.

Share this post


Link to post
Share on other sites

This topic is 4517 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