Hello,
I’m looking for guidance how to best implement collision detection of large object sets that would benefit from temporal coherence (https://en.wikipedia.org/wiki/Collision_detection#Exploiting_temporal_coherence).
Problem setup:
- Need to know which things overlap actors at any time and track that state
- There are 10s of players and 100,000s of actors in the 3D world that mostly resembles a plane
- Players overlap at most 1000s of actors at any time
- Players move “slowly” so on each move there’s at most 10s-100s of actors that changed if they overlap or not anymore
- This is where “temporal coherence” comes into play that I’d like to use as an collision search optimization vector
How do you suggest approaching this in Unreal Engine (we are at 5.4 now)?
Starting Ideas:
- Use UE collision system. Would be neat to use default system but I don’t know if there’s a way to benefit from temporal coherence with it. If we do a fresh collision query after each player move is too costly due to the linear nature of the result set - we will always be returning 1000s of results. If collision system supported temporal coherence then it would only return the changed set which is magnitude or 2 smaller 10s-100s.
- Use World Partitioning. Seems like it could solve the problem as it already has temporal coherence built in - activates and deactivates cells only when close to you. Unsure if flexible enough to support multiple grid partitions, arbitrary activation rules (distance, shape, …) or 3D grid.
Thank you!
Hi Ivan and thank you for your question.
There are certainly ways we can look to tune the scenario you describe above. The first thing I’d be looking to do is to mock this up in as simple a way as possible and profile it using insights. That will give you a good idea of where the load within the physics tick is coming from. (What I mean here is that it is no good optimizing the broadphase, only to find you are transferring the load to the narrowphase section, which would still need running to check if the collision still exists). Once we have that we can take a stab at methods to reduce the time spend on the tick.
In a more generic answer - there were some earlier physics algorithms which worked well with temporal coherence - Sweep and Prune exploited this pretty well. However as worlds have become more dynamic the update cost tended to dominate the saving of temporal coherency.
All the best
Geoff
Hi Ivan,
No, we use AABB trees since that fits most scenarios pretty well and allows us to focus our performance efforts into one implementation.
I’d still ensure that this is the weak link before rewriting an entire broadphase though - this is a major component of the physics engine, and this still could end up less performant that the AABB at the end of it.
Obviously if you do though, we’d love to hear about the results!
Best
Geoff
Hi Ivan,
Mulling this over a bit more - are these SceneQueries primarily you are looking to recycle over time? If so - would a cache be a potentially less expensive change to make? Happy to hop on a call as well if that helps
Geoff
Made a 2D diagram to show what I’m thinking.
I can mostly reduce the problem to players becoming AABB’s moving around and rest of actors being points in 3D space
The question is to understand which actors are overlapped assuming players move slowly.
Naively, I can search the entire AABB space at the new position and process all of those actors but knowing that moves are “slow” I can use that to search a much smaller space - just the difference.
On the implementation side:
- I can construct these delta AABB search spaces myself and run those queries
- Or Unreal already support this somehow out of the box
- Or I manually implement a sorted position list approach where I do logN binary search in X,Y,Z space on the delta X,Y,Z
- which is similar to what AABB trees must be exploiting but I need to sit down and read the theory to speak confidently about this
[Image Removed]
Hi Ivan,
A couple of extra bit of info from the dev side.
We do expand the AABB bounds by around 10% for shapes - that way we don’t have to change the tree for small movements which helps speed things up.
SAP can struggle with performance for SceneQueries - essentially they aren’t generally inserted into a broadphase since they can’t be collided with, only collide with other things. This means a lot of searching and probable cache thrashing while searching.
SAP can also get into issues when there are a lot of overlaps on one axis even when the objects are really far apart, so you pay a cost for a large result set initially which then gets filtered out.
Specifically on your diagram, for a SAP structure - that square won’t be the search domain - it will have *all* the search space between the points along each axis - so more of a cross shape which then gets compared to filter out collisions. For updates then you would search for the X axis difference (for all Y), and Y axis difference (for all X), then filter out the X, Y and finally the overlap for X and Y.
Hope this all helps. Let us know if you need any specific advice when you are ready.
Geoff
Thanks for the answer!
Algorithmically, sweep and prune seems to fit what I need here. Forgot to mention that actors in our world rarely or never move so there wouldn’t be a lot of cost in resorting the sorted list.
Does sweep and prune implementation exist in Unreal in some form? I can also do it myself given it’s simplicity.
Thanks!