How can I exploit multithreading in collision resolution?

Question

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

Answer 1

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.