Sign in to follow this  
Kest

Correcting a capsule intersection

Recommended Posts

I came up with my own pretty generic physics system a while back which used several spheres to represent major points on a dynamic object. The spheres basically free-fall and are then pulled back together and put back into shape. Once put back together, the sphere positions are used to calculate the object's state matrix. It's a really cheap way to simulate some crazy dynamics. Everything worked great until I tested with convex surfaces. I was pretty narrow minded to not realize this was coming. All I want to do is push the shape out of trouble. I don't want to do anything fancy. Just move the entire object until it's not colliding. I can detect when the trouble is present, but I don't know what to do about it. This all comes down to a really simple problem. I have a capsule which I know is intersecting polygons, and I want to move it so that it's not. I want a stable solution, but I don't care at all about accuracy. As long as the object doesn't jump around (like gravity pushing it down, and a lump in the ground pushing it up). Here are the situations I'll need to fix. I think these are the only type of intersections I'll find trouble with. All convex. Keep in mind that the capsule could be oriented at any angle on these types of surfaces, and also that this is happening in 3 dimensions: Image Hosted by ImageShack.us Any help on this? I'm happy to listen to even the most generic solution.

Share this post


Link to post
Share on other sites
Hi Kest,

The category of objects under consideration here is medial-structure or swept-sphere objects. I mention the general term because the solutions to the static intersection problem are similar for all such objects.

Consider sphere-sphere intersection. We all know that boolean intersection is determined by comparing the (squared) distance between the centers to the (squared) sum of the radii. Furthermore, the normalized vector between the centers, along with the difference between the length of this vector and the summed radii, can be used to construct a vector with which you can resolve the intersection, if there is one.

Spheres are trivial enough that we usually don't think of them this way, but they are in fact medial structure objects. The medial structure is a point; the sphere itself is the Minkowski sum of a sphere and a point, or, a sphere 'swept' over the point (although in this case the 'swept' obviously doesn't amount to anything). The generalization is useful in that it lays the groundwork for other tests, including the ones you're inquiring about.

The general procedure for static intersection tests between two medial-structure objects is:

1. Find the squared distance and the (or a) closest pair of points between them.

2. If the squared distance is greater than the squared sum of the radii, no intersection.

3. Else the intersection normal is the normalized vector between the closest points, and...

4. The penetration distance is the difference between the length of this vector and the sum of the radii.

5. You now have a normal-distance pair that you can use to push the objects apart.

It may be (such as in your examples) that one of the objects is not a swept-sphere object, in which case you can simply ignore its radius in the above steps.

This all sounds pretty straightforward, but alas, the devil is in the details. Most of the effort of this algorithm, both in performance and implementation, falls on finding the distance and closest points between the medial structures. In your case, it looks like you need to find the distance between a line segment (the capsule medial structure) and a box or triangle. This post is long enough as is, but I can provide some more info/references/links regarding these distance tests if you'd like.

[Edit: You mentioned that you already know the objects are intersecting, so maybe you already have the distance function and just need to apply it as described above.]

Share this post


Link to post
Share on other sites
I use a pretty simple method to detect the collision. Just buff out the polygons using the capsule radius and turn the capsule into a ray. This gives me a point of contact, but not at all the closest point on the capsule (line segment) to the polygons.

I forgot to mention before that the spheres on either side of the capsule will always be outside of polygon intersection. So the center is always the problem area.

As long as the capsule doesn't jerk from one position to another between frames, I'll be happy with the result. I know I need two bits of information to do this. A direction and distance to move. I was considering taking the polygon normals on each side of the capsule (like intersect the pushed out polygons from both sides of the capsule to the opposite sides), adding those together, and normalize. That would most usually make a nice direction to move. Well, other than in rare situations like the bottom right example. But I could also subtract a bit of the capsule's last movement direction before normalizing. Anyway, I also cannot come up with the distance to move. So it doesn't look like it will work anyway.

It looks like my free falling sphere dynamics are being shot down. I might just have to invest time into some dynamic rigid body collision studying instead. I've had my head out of math for too long. Not sure I'm up to the challenge.

I really appreciate your help.

Share this post


Link to post
Share on other sites
For what it's worth the 'closest points' method, if you were to pursue it, would give you the collision resolution vector that you're looking for. Also it wouldn't impose the limitation that the end spheres not intersect the polygon (which may not be important for you).
Quote:
I use a pretty simple method to detect the collision. Just buff out the polygons using the capsule radius and turn the capsule into a ray. This gives me a point of contact, but not at all the closest point on the capsule (line segment) to the polygons.
I'm curious: if you don't mind sharing, how are you approaching the problem of intersecting a ray with a polygon expanded by a radius? My own code for raytracing sphere-swept objects is pretty complicated and I've been looking for a way to simplify it. I might be missing something obvious, so I'd be interested to know what you're doing.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
I'm curious: if you don't mind sharing, how are you approaching the problem of intersecting a ray with a polygon expanded by a radius? My own code for raytracing sphere-swept objects is pretty complicated and I've been looking for a way to simplify it. I might be missing something obvious, so I'd be interested to know what you're doing.

I push the plane of the triangle outward, turn the edges into cylinders, and the vertices into spheres. The radius of all of these set to the capsule's (which is being turned into a ray) radius. Basically just intersect these primitives with the ray. Or at least that's how I learned the method (from here a good while back). I wrote a pretty nice routine to quickly detect capsule - ray intersections, so ended up ditching the vertex spheres and turning the edges into capsules. Most of the tests are rejected on the plane, though.

If you were wrong, and your method is more simplified, please share [smile]

Share this post


Link to post
Share on other sites
Quote:
If you were wrong, and your method is more simplified, please share
It might be a little more efficient, but probably not any simpler - your method probably works just fine. I'm currently working on code for intersection of linear components and a variety of sphere-swept objects, including capsules, lozenges, and 'rounded' boxes and triangles. These tests can function as-is for raytracing, but also as support functions for swept intersection between spheres and both the sphere-swept objects and the medial structures themselves. For example, a swept sphere vs. box or rounded box test can be expressed as raytracing a rounded box with the appropriate radius.

Capsules and even triangles aren't that big a deal, but with a rounded box there are 8 spheres and 12 cylinders - too many quadratic primitives to find the intersections by brute force. The planes of the medial box partition the rounded box into regions, each associated with a sphere (corner), cylinder (edge) or quad (side). Currently I'm using 3DDDA to step through the regions, keeping track of intersections along the way, but I'm not yet happy with my implementation. Basically, the goal is to minimize the number of quadratics to solve.

All these problems can be approached uniformly through GJK, but I'm interested in pursuing the above method as well. Anyway, that's probably more than you wanted to know, but that's why I asked about your ray vs. triangle+radius function :)

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
It might be a little more efficient, but probably not any simpler - your method probably works just fine.

I didn't realize it could get much more efficient. Oh well, thanks for.. the thought.

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