Concave Penetration

[raigan2]

hi,
I'm trying to find a well-behaved method for resolving penetrations between two concave polygons in 2D. Probably this is similar to trimesh-vs-trimesh in 3D.

By "resolving penetrations" I really just mean "generating nice penetration info", the solver can handle the actual constraint/simulation part.

Currently we have a "slightly-inflated shapes + distance tests" system working, however this breaks if there is fast movement. I would rather not resort to sweep tests: my solver is position-based, so things will be pushed into penetration at each solver iteration.. I'm not going to sweep-test with each iteration! I'd like to just clean things up at the start of the next frame.


For convex-vs-convex this is more or less solved: penetration can be resolved by explicitly forming the convex hull of the shapes' minkowski difference, and finding the point on the hull's surface closest to the origin.

Obviously this isn't the fastest solution, but my point is that it's a known correct solution, which can then be reached/approximated in more optimal ways (via SAT/EPA/sampled-minksum/etc).


Does anyone know of anything comparable for concave shapes?

Generating well-behaved penetration information for concave shapes is a topic that must be quite common in practice, yet it seems to be perpetually glossed over in the literature. There are several threads on these forums that touch on the subject, but it seems like no one has presented a solution that works much of the time. Yet most games seem to have at least convex-vs-concave working well..


Obviously, if the penetration is very deep the "correct" penetration information is ambiguous (without resorting to heuristics such as looking at previous state or current velocity). I'll settle for something that only works with "reasonable" penetration amounts.


I'm aware of the following proposed solutions, but none of them seem to be very good:

1) back up time until the shapes aren't penetrating, find the closest features in the past, and use these to calculate the current penetration.

problem: "back up time" is a bit vague

To avoid problems with rotating objects, or cases where the objects were penetrating last frame, you wouldn't really want to look backwards in time -- you'd want to simply translate the shapes until they're separated. But.. how do you know how to translate them? This is the problem we're trying to solve!


2) Decompose the concave shapes into convex pieces, apply known convex-vs-convex solutions.

problem: just doesn't work

This is a very frequently presented solution, but it simply doesn't work in practice: if you represent your concave shape as a union of convex shapes, and then try to generate penetration information using convex-vs-convex tests, you end up with objects being trapped between convex shapes. This approach works well for minimum-distance and boolean/intersection queries, but not for penetration as far as I've seen.


3) Distance maps: represent your shapes implicitly, as a grid of signed distance samples, use point queries to determine the closest point on the surface of the shape.

problem: slow? memory-hog? Unlike the above "solutions", I haven't yet tried this; has anyone used this sort of approach in a game?


I'm sorry for this overlong post, I've just spent the past three days trying to hack something together with invented "heuristics", and frustratingly nothing is working well.

If you extend the thinking behind "slightly-inflated shapes + distance tests", you end up with a system where you calculate the "skeleton"/medial axis (http://compgeom.cs.uiuc.edu/~jeffe/open/skeleton.html) of each polygon, with corresponding inflation amounts so that each segment of the skeleton/medial axis becomes a capsule. This will still break, it will just take a larger penetration amount, and things will be horribly rounded. It seems like a geometry-based version of signed-distance-maps.


Has anyone had any luck with concave collision? I thought Novodex has mesh-vs-mesh working, but I can't find anything online about it.

thanks,
raigan

[Erwin Coumans]

2) Decompose the concave shapes into convex pieces, apply known convex-vs-convex solutions.

problem: just doesn't work

This might be a bug in your implementation. Composite/compound objects are the most popular concave representation that has been used in many games. Havok, Bullet, PhysX/Novodex and others are using this.

Can you make a testcase using Bullet btCompoundShape that shows the failure?

Thanks,
Erwin

PhysX/Novodex used to have PMAPS but they are obsolete due to excessive memory usage. OpenTissue has an open source signed distance map implementation, in case you are interested. You might also want to search in deformable concave collision detection for concave-versus-concave solutions based on tetrahedral meshes.
OPCODE/ODE uses concave trimesh-trimesh using AABB trees and heuristic for penetration depth. GIMPACT also performs concave trimesh, but convex decomposition gives better quality and performs faster in my experience. Although you didn't like to us CCD, it is an option to use CCD on concave meshes, see the FAST paper/implementation.

[kotsoft]

hi, i'm kind of new to this forum, and wasn't here when this post was created, so maybe your problems were already solved.

hey, a few months ago i was reading the n ninja forums and i saw a similar problem with the ninja landing between two boxes or something and being stopped. i think this is similar to decomposing a concave polygon.

the problem is, when you decompose, you are probably including that newly created invisible edge in your collision resolution. and because of that, objects might get trapped.

so basically, you can use the invisible edge during the SAT that determines whether there is a collision or not, but do not use it when resolving the penetration.

and then, i think just add all the resolutions to a list or something and solve them like a little system.

i haven't tried this but i think it might work. hope this solves your problems.