3
\$\begingroup\$

I'm trying to speed up my collision resolution by using multiple threads.

I'v read through Box2D's source code and while it was challenging and educating, it didn't really point me to how I could use multiple threads.

I'm ready to make some sacrifices with accuracy. I am investigating this because I have boatloads of game objects.

My current implementation handles AABB checks for 100000 objects in about 10 ms. I have no idea if this number is good, but for my purposes it seems sufficient.

Next, I'm trying to figure out how to resolve collisions. How could I get power out of multiple threads here?


This is what i'm currently planning to do: (Do you see any issues with it?)

  1. Calculate position for each object in separate threads based on manifold data
  2. Update existing manifolds in separate threads
  3. get New collisions for moved objects in separate threads
  4. Repeat 10 times or until no changes
\$\endgroup\$
  • \$\begingroup\$ You say your current implementation is sufficient for your purposes. Do you mean your implementation of AABB checks only, or the collision resolution more generally? At the moment it sounds like the former, but perhaps you meant the latter. \$\endgroup\$ – Anko Oct 12 '15 at 17:40
  • \$\begingroup\$ My AABB checks are sufficient now, but what I need is collision resolution. How to move objects that are intersecting, what impulses to give and so on. \$\endgroup\$ – 0xbaadf00d Oct 12 '15 at 20:13
2
\$\begingroup\$

I'm not sure what solver strategy you use but most physics engines including box2d solve islands of bodies that share manifolds. Only the interrelated bodies that can have impact on one another are solved together. Each island can be solved on a separate thread. Since island sizes change based on the number of interrelated bodies a job scheme consuming islands as threads are free is a good strategy. Havok works this way. Box2d is a good place to look for insight for building islands even if solving isn't multithreaded.

The other thing you could do is perform batches of narrow phase pair-wise collision in seperate threads since the input data is small and constant until the next step. The outputs are again limited to only the two in the pair.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.