Real-Time Physics Simulation Forum

convex hull vs polygon soup collision detection

2006-10-16T22:11:34+00:00

I fixed a typo there.

What I meant to say is that you should only consider the triangle normal _and_ the hull face normals when creating contact points. You should only use the edge-edge cross product axes to rule out collision.

Statistics: Posted by Erin Catto — Mon Oct 16, 2006 10:11 pm

convex hull vs polygon soup collision detection

2006-10-16T22:04:12+00:00

I dealt with this problem quite a bit.

I found a good heuristic is to consider the triangle normal and the box face normals axes contact normals. This avoids the edge-edge case, and helps with the cliff problem.

What do you mean by axes contact normals? could you develop this a bit?

Right now I'm doing this:

First I test the triangle normal as separation axis test.

Then, I test the cross products of the triangle normal vs the triangle edges, but I only take the result into consideration if the resulting dot product between the triangle normal and the adyacent triangles are within some limit angle. This seems to solve the edge-edge case too, but I need to do further tests.

The case which I haven't solved yet is the hull plane vs triangle corner, that is, when I test the hull axes alone.

Statistics: Posted by vicviper — Mon Oct 16, 2006 10:04 pm

convex hull vs polygon soup collision detection

2006-10-16T22:07:45+00:00

I dealt with this problem quite a bit.

As Erwin mentioned, if you only use triangle normals, then a box sitting on the edge of a cliff will be pushed off the edge. With many physics algorithms, there is a little bit of penetration. The triangles on the face of the cliff will see the box as being deeply embedded into the face. This is obviously bad behavior.

When you have penetration, there are some odd cases. Another example is a thin box sticking vertically into the floor along the edge between two triangles. In this case, an edge-edge axis will likely have the minimum penetration. But the edge-edge axis is parallel to the floor so the box will fall right through the floor.

I found a good heuristic is to consider the triangle normal and the box face normals as contact normals. This avoids the edge-edge case, and helps with the cliff problem.

Statistics: Posted by Erin Catto — Thu Oct 12, 2006 6:11 pm

Re: convex hull vs polygon soup collision detection

2006-10-08T23:25:24+00:00

With triangles, I test all possible axes, but In case there's a collision, I always get the triangle normal as separation axis, regardless an axis with shorter depth has been found. This is good because it solves very well the conflicts when a convex hull collides very close to the edges of two triangles in a mesh, actually, always choosing the triangle normal as separation axis is correct 95% of the time.

The problem is the other 5%, where the correct separation axis is one other than the triangle normal (usually a cross product between a triangle and hull normals)

The question is: how to know when these 5% axes are the correct ones?

Thanks in advance

Handling concave triangle meshes by performing a batch of separate convex versus triangle tests is very common, and either SAT or GJK can be used. I assume you use a culling stage (midphase) like kdop tree or aabb tree to cull triangles that can't contribute to the final results.

SAT has the drawback that it is penetration based, so the effect of hitting 'internal edges' is larger then when you use GJK, because GJK allows contact generation based on distance (using some margin). Still, both approaches can benefit from some heuristics, and using the triangle normal is one of them, using continuous collision detection another (this is used for character controllers, like the typical quake FPS) or using rounded collision shapes(when using GJK you can easily round all shapes by increasing a collision margin).

One improvement is to distinguish between 'convex' edges and 'concave' edges. You can safely ignore 'concave' edges, as no collision will happen with them. You could add some threshold based on the angle of the two triangles that share the edge, and below certain values (although the edge is convex) still threat it as concave, so use the triangle normal.
You have to be careful which penetration depth and normal to use, otherwise you can push objects in the wrong direction: imagine an objects on the edge of a cliff, it will be pushes off-the-cliff.

Another more complicated improvement is doing some convex decomposition (either precomputed or online/at runtime) to solve this: group all triangle that share convex-edges into a convex hull, and do a convex-hull versus convex-hull test.

Erwin

Statistics: Posted by Erwin Coumans — Sun Oct 08, 2006 11:25 pm

convex hull vs polygon soup collision detection

2006-10-08T20:53:34+00:00

I'm doing some research about how to detect collisions between a convex hull and triangle soups with arbitrarily arranged triangles.

What I'm trying to do is to treat every triangle in the soup as a convex hull, using SAT, and so far, I can detect collisions very well.

The problem comes when I want to find the correct separation axis between the convex hull and a triangle.

Typically when two convex hulls collide, the correct separation axis is the one with the shorterst depth penetration.

With triangles, I test all possible axes, but In case there's a collision, I always get the triangle normal as separation axis, regardless an axis with shorter depth has been found. This is good because it solves very well the conflicts when a convex hull collides very close to the edges of two triangles in a mesh, actually, always choosing the triangle normal as separation axis is correct 95% of the time.

The problem is the other 5%, where the correct separation axis is one other than the triangle normal (usually a cross product between a triangle and hull normals)

The question is: how to know when these 5% axes are the correct ones?

Thanks in advance

Statistics: Posted by vicviper — Sun Oct 08, 2006 8:53 pm