Collision detection for mobile physics engine

[Cesar]

Hi,

I'm working on a real time 2d physics engine for a mobile phone application and I've been having a hard time figuring out how to handle collision detection. I first considered sprite based techniques, but I guess it's not a very good idea.

So I chose to use the geometric description of the obstacles, which brings me to another question that has been discussed before but not in the following setting: computational power and heap are limited, the polygons involved are fairly simple (no more than 6 vertices) and most of the objects do not move at all. Which would be the best algorithm: GJK or SAT?

I would really like to hear your oppinions on the subject.

Thanks,

Cesar

[Cesar]

No one? Please?

[Dirk Gregorius]

Look at the Box2D forum. Some people are porting the engine currently and I remember some people discussing mobile devices there. Maybe the Box2D engine is suitable for you needs and you might test its collision detection (SAT) and see if its performance is good enough for yor needs...


http://www.box2d.org

[Cesar]

Thanks for answering Dirk. I'll check box2d forums.

But I was wondering, from a theoretical point of view, if SAT is not better for simple shapes. But that's just my impression simply from the fact that GJK being an iterative algorithm, it would be more interesting for complex polyhedra, where SAT would have to check a lot of different axis.

Does that make any sense at all? Or it's not that simple?

[Erwin Coumans]

But I was wondering, from a theoretical point of view, if SAT is not better for simple shapes. But that's just my impression simply from the fact that GJK being an iterative algorithm, it would be more interesting for complex polyhedra, where SAT would have to check a lot of different axis.

Does that make any sense at all? Or it's not that simple?

It totally makes sense: when you only deal with small polyhedra, a dedicated SAT test is likely faster then GJK/EPA.

Once shapes get more complex, the answer is less simple: there are a lot of optimizations that can be applied to both SAT and GJK, especially when you deal with polyhedra only, which brings performance closer to eachother. So it really depends on many aspects, when/if GJK is better then SAT.

Just to name a few (not exhaustive):
- caching of the separating axis and distance (benefits both SAT and GJK)
- is penetration more likely, or do you mainly deal with separation? GJK only deals with separation, so it requires a companion penetration method which is usually more computationally expensive
- Mixing GJK and Lin Canny

In the limited memory of Cell SPUs (256kb), I find GJK very useful, because the code size is very small, and it handles a lot of different shapes, including spheres, triangles, boxes, capsules, cylinders, convex polyhedra etc. GJK can be combined with compressed AABB trees and contact management to handle concave triangle meshes and compound objects. For GJK, the convex polyhedral object representation can just be a point cloud, so no connectivity information needs to be stored.

Hope this helps,
Erwin

[Cesar]

It helped a lot . I knew the debate GJK vs. SAT was far from trivial but I was wondering which considerations could be made for mobile phones and very simple geometry.

Thanks,

Cesar

[ewjordan]

Figured I'd chime in here: I'm one of the people working on a port of Box2D to Java. Unfortunately at the moment we're not shooting for mobile Java yet, because a) we're still not sure how well things will run on regular old Java, and b) to use on mobile requires that all the math be converted to fixed point, which is just kind of a pain to do while we're trying to get it running in the first place. Also people tend to like as few classes as possible on mobile, and they like to trim code for size; the combination of all these things turns a simple port into a reasonably difficult project involving tons of refactoring and a large chance of failure, so it's not on the agenda for now.

Once we're done, it may be a good experiment (indeed, I would love to eventually try to do the same with Bullet, though I decided to try a smaller engine first to get my porting chops in shape), but to my knowledge there's no one actively doing it right now. I think today's phones are a little bit underpowered for a feature-complete physics engine, though this becomes less true every phone generation, so eventually such a thing would be very useful. Personally I would be excited to see some real physics on the phone!

You might take a look at the Box2D code for the collision handling if that's all you need, rather than a full engine - Erin Catto has thought this stuff out a lot, so if there's a right way to do it, it's probably already in Box2D. If you look through the SVN browse there (somewhere at http://www.sf.net/projects/box2d, and the Java one we're working on is http://www.sf.net/projects/jbox2d - beware, ours is not finished yet, and collisions have not been tested), the file you want to look at is b2CollidePoly (CollidePoly in the Java version). I don't know how much sense it will make apart from the whole engine, but it may help you a bit.