Strategies for dealing with non-incremental broadphase

[sphet]

Hey Folks,

So a lot of the refactoring work in our physics engine is complete, and we have it in our game. Our previous system lacked a sophisticated broadphase, instead performing linear comparisons against bodies during detection and ray casts. Our new system uses a DBVT to great effect. One of the side effects of this system is that we are now 'one frame behind' on specific tests. Here's an example:

1. Take player input and generate velocities; set velocities in body.
2. Update broadphase, perform collision detection, update bodies, etc.
3. Take new velocities from simulation, determine correct animations to play, update player skeleton
4. Move player hit boxes in physics work to match new animation.
5. Cast rays against hit boxes - oops broadphase has not been updated.

This problem is also demonstrated with AABB phantoms are moved and expected to immediately reflect the new overlap list.

I can see solving this in a few ways:

1. making the DBVT operate incrementally, which would cause the tree to be refreshed and events fired all over the frame, which isn't cache friendly at all.
2. ask the client to invoke 'update broadphase' at key points in the frame to get the broadphase in a valid state.

How do other people solve this problem?

S

[Dirk Gregorius]

I update the proxy in the broadphase immediately to avoid the problems you described, but I don't compute contacts directly.

For hitboxes I don't add them into the physics broadphase at all. Especially on a server/client structure you don't want to rewind those. And even in general it makes sense to avoid the hitbox traffic on the broadphase in this case. Hitboxes can be implemented very efficiently using brute force methods utilizing SIMD. I am now even leaning forwards to take triggers out the physics broadphase and have them in a separate system.

Cheers,
-Dirk

[sphet]

I update the proxy in the broadphase immediately to avoid the problems you described, but I don't compute contacts directly.
...

Dirk,

As always, thank you for the reply. This is my suspicion - that allowing the broadphase to be updated incrementally is the desired behaviour. I support OnContactBegin( Pair& ) and OnContactEnd( Pair& ), not to mention the allocation and deallocation of pair-wise collision agents. When I originally had a sweep and prune broadphase I incrementally updated the broadphase, but then these callbacks were fired at many points in the frame, causing all kinds of problems.

When you update the proxies, and either new pairs are created, or previous pairs destroyed, how do you deal with the propagation of this data? If all of these events fire at any point in the frame a lot of problems can occur. Do you queue up this data somehow and only push it out once a frame?

Any insight would be appreciated.

S

[Dirk Gregorius]

I don't create pairs at that point. The proxy movement is cached and when you step the physics world the first thing you do is to create new contacts by iterating over the cached proxies that have moved. The general concept with a dynamic tree broadphase is different from a SAP. The SAP has begin/end overlap kind of built in. In the dynamic tree the idea is that a contact has is to confirm itself when you iterate to update the manifold.

I don't fire immediately, but queue events. Alternatively people can even iterate over the notifications and pull it.

Again this is all pretty well implemented in Box2D. In b2WorldCallbacks you need to implement OnContactBegin() / OnContactEnd(), PreSolve() and PostSolve(). This should give a good idea. It is pretty straight forward to adapt this to any behavior you need. This callbacks are a pain in butt. The game code often likes to destroy bodies on contact begin and invalidates pointers. This can lead to all kind of subtle bugs. We postpone any deletion until the end of the frame therefore not exposing pointers directly, but using handles.

[sphet]

I don't create pairs at that point. The proxy movement is cached and when you step the physics world the first thing you do is to create new contacts by iterating over the cached proxies that have moved. The general concept with a dynamic tree broadphase is different from a SAP. The SAP has begin/end overlap kind of built in. In the dynamic tree the idea is that a contact has is to confirm itself when you iterate to update the manifold.

I don't fire immediately, but queue events. Alternatively people can even iterate over the notifications and pull it.

Again this is all pretty well implemented in Box2D. In b2WorldCallbacks you need to implement OnContactBegin() / OnContactEnd(), PreSolve() and PostSolve(). This should give a good idea. It is pretty straight forward to adapt this to any behavior you need. This callbacks are a pain in butt. The game code often likes to destroy bodies on contact begin and invalidates pointers. This can lead to all kind of subtle bugs. We postpone any deletion until the end of the frame therefore not exposing pointers directly, but using handles.

Dirk,

The callback system is all set up and working - OnBeginContact()/OnEndContact() based on manifold contacts going from 0->N and N->0, respectively. PreSolve and PostSolve are also done.

The question of queueing is more interesting as it does not seem like Box2D is incremental update, nor queued events. Do you store a little datastructure for the events? It is the case of contacts ending and objects deleting themselves as a result that I am trying to localize to a specific point in the frame.

I'm going to take another look - I think it shouldn't be too difficult to resolve.

EDIT: Indeed it was straight forward - the contact begin/end is handled correctly in the collision step; the only complication is the AddPair/RemovePair callbacks that need to be dispatched to my Sensor/Ghost/Phantom API immediately which can be handled by the client code correctly.

So other than some data/instruction cache downside to this change, I think it's a fix, thanks.

Thanks again.