Hi there,

i have implemented a particle engine with one-way collisions against box2d chain shapes (chained line segments).

Its working fine and my contact solver solves the penetration successfully, but...

...i am using a O(N^2) approach to detect any possible combination for every frame which obviously is very slow.

Thats n * (body + n * line segments) * n * particle... too much to test against it. Even with 1200~ particles against 15 chain shapes (up to 30 edges) reduces the framerate to 2.x.

Therefore i really need a broadphase technique which drastically reduces the body <> line segment checks. Testing just the fixture of the chain shape by AABB does not help me at all, because my line segment geometry is all over the place. Mostly covering half of the map, cause the chain shapes are built using the traced outlines of a tilemap. It may start at the top left corner and ends at the bottom right cornor in worst case scenarios.

What broadphase techniques would work for that problem?

Thanks in advance,

Final