For collision tests of a convex object against concave world geometry composed of triangles; the usual procedure is to query your Bounding Volume Tree for triangle candidates and then dispatch individual triangle-vs-queryObject tests with the candidates. But these local tests can give you incorrect collision normals compared to what would be correct for the compound geometry.
For example; hitting a triangle edge in a tesselated plane when both triangles sharing the edge are coplanar. Your sliding object will hit a bump where none exists.
It's a pretty common issue when using GJK. There are a number of ways to fix it, but it seems tricky to get right for all cases. What do people do about this situation?
filtering collision normals on concave mesh
-
mewert
- Posts: 52
- Joined: Sat Oct 08, 2005 1:16 am
- Location: Itinerant
-
Erin Catto
- Posts: 316
- Joined: Fri Jul 01, 2005 5:29 am
- Location: Irvine
For box-triangle I used SAT and disregarded edge-edge contact points. I also weighted the axis selection to use the triangle normal instead of the box face normals.
For a time I was also ignoring box face normals, but then I had a case where a box is hanging over the edge a cliff. The triangle on the face of the cliff saw the box as being deeply penetrated and shot the box off the cliff. So triangle normals are not enough.
With GJK, perhaps you could ignore the contact point if the closest points are on edges of both objects, and one is a triangle. You could also pre-process the triangle mesh to mark shared edges between coplanar triangles as non-colliding (see GPG4).
For a time I was also ignoring box face normals, but then I had a case where a box is hanging over the edge a cliff. The triangle on the face of the cliff saw the box as being deeply penetrated and shot the box off the cliff. So triangle normals are not enough.
With GJK, perhaps you could ignore the contact point if the closest points are on edges of both objects, and one is a triangle. You could also pre-process the triangle mesh to mark shared edges between coplanar triangles as non-colliding (see GPG4).
-
vicviper
- Posts: 21
- Joined: Thu Jun 01, 2006 9:55 pm
What I did and it's working quite well for now is this:
I do a full SAT of the candidate triangles against the convex hull.
The difference is that I only do the SAT to know if I can reject the candidate triangle, if I find that the triangle is actually in contact with the hull, I get the triangle normal as the valid separation axis.
This solves completely the problem with coplanar triangles, but under other triangle configurations some problems may arise, so a correct solution will be more difficult to find
I do a full SAT of the candidate triangles against the convex hull.
The difference is that I only do the SAT to know if I can reject the candidate triangle, if I find that the triangle is actually in contact with the hull, I get the triangle normal as the valid separation axis.
This solves completely the problem with coplanar triangles, but under other triangle configurations some problems may arise, so a correct solution will be more difficult to find
-
mewert
- Posts: 52
- Joined: Sat Oct 08, 2005 1:16 am
- Location: Itinerant
I'm looking for a solution that works with general concave polyhedra.
The GPG4 triangle preprocessing is nice, but I see a problem with it for a gradually sloping tesselated hill. All those edges are convex, but could still result in bumps. Also I'm not crazy about the extra per-triangle bitfield.
Previously I implemented a solution that filtered the new points using the existing manifolds between the moving object and the concave mesh. There were a number of rules which looked at things like the difference between the angle of the incoming normal and the existing normals, whether or not the new point has a greater penetration depth ( or smaller distance ) etc. I can't recall the details, but I do remember it was a bit of a pain in teh arse and I was never really convinced it was the best solution. In it's defense, it worked and has been used in a number of shipped games.
I see 3 catagories here:
1) Filtering based on looking at neighbouring triangles ( preprocessed or run-time )
2) Filtering based on just the new contact data
3) Filtering based on the existing manifold
The GPG4 triangle preprocessing is nice, but I see a problem with it for a gradually sloping tesselated hill. All those edges are convex, but could still result in bumps. Also I'm not crazy about the extra per-triangle bitfield.
Previously I implemented a solution that filtered the new points using the existing manifolds between the moving object and the concave mesh. There were a number of rules which looked at things like the difference between the angle of the incoming normal and the existing normals, whether or not the new point has a greater penetration depth ( or smaller distance ) etc. I can't recall the details, but I do remember it was a bit of a pain in teh arse and I was never really convinced it was the best solution. In it's defense, it worked and has been used in a number of shipped games.
I see 3 catagories here:
1) Filtering based on looking at neighbouring triangles ( preprocessed or run-time )
2) Filtering based on just the new contact data
3) Filtering based on the existing manifold