2D Collision Detection Using Distance Maps

[crashlander]

I'm looking for thoughts people have on implementing the 'Nonconvex Rigid Bodies with Stacking' paper in 2D. I'm considering using the 2D equivalent of both the collision detection and collision response. The collision response seems like it would transfer well to 2D. I"m less sure of how the paper's collision detction algo, which uses a distance function and trimesh (polygon for 2D), will convert to 2D. I can see that it would work, but I'm not sure if it makes sense to use this technique over others that are out there. (SAT, GJK)

I'd mostly be using this engine for games, but I'd like to have a pretty robust collision detection system.

My thoughts so far:

-Handles non-convex shapes
-Memory issues with using distance grid less of a problem in 2D
-Distance grid computation less an issue in 2D. Could hopefully be done a load time or lazily. (no precomputation)
-(very important to me..) It's more intuitive to me than the other algos and I love simplicity...

Any and all thoughts are appreciated.

note: I double posted this to both this forum and the gamedev.net physics forums as I wasn't sure how much overlap there was between here and there.

link to the paper: http://graphics.stanford.edu/~fedkiw/pa ... 003-01.pdf

[Erwin Coumans]

I'm looking for thoughts people have on implementing the 'Nonconvex Rigid Bodies with Stacking' paper in 2D. I'm considering using the 2D equivalent of both the collision detection and collision response. The collision response seems like it would transfer well to 2D. I"m less sure of how the paper's collision detction algo, which uses a distance function and trimesh (polygon for 2D), will convert to 2D. I can see that it would work, but I'm not sure if it makes sense to use this technique over others that are out there. (SAT, GJK)

I'd mostly be using this engine for games, but I'd like to have a pretty robust collision detection system.

My thoughts so far:

-Handles non-convex shapes
-Memory issues with using distance grid less of a problem in 2D
-Distance grid computation less an issue in 2D. Could hopefully be done a load time or lazily. (no precomputation)
-(very important to me..) It's more intuitive to me than the other algos and I love simplicity...

Any and all thoughts are appreciated.

note: I double posted this to both this forum and the gamedev.net physics forums as I wasn't sure how much overlap there was between here and there.

link to the paper: http://graphics.stanford.edu/~fedkiw/pa ... 003-01.pdf

Sounds like a good idea. 2D signed distance maps should give good results. SAT/GJK might be a bit more accurate, but I guess you can increase the detail of the distance maps if you need better quality.

If you like simplicity, there is a good explanation of 2D SAT and response in Erin Catto's 2D physics engine GDC presentation (with code):
http://www.gphysics.com/?page_id=16

Either you decompose your concave into convex parts and use SAT or GJK(+penetration depth solution), or indeed signed distance maps. Should give a very useable solution, especially in 2D.

By the way, I'm considering to add 3D signed distance maps to Bullet as well, after the SAT contribution is added.

Erwin