Broadphase pair ordering hurts determinism

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Create a world with at least two dynamic rigid bodies
2. Cause the bodies to collide
3. Inspect collision response
4. Reset positions and repeat

What is the expected output? What do you see instead?
Ideally the collision response should be deterministic, ie. identical each time 
the initial conditions are the same.  In actuality contact points are 
calculated slightly differently depending on the order of the btBroadphaseProxy 
pointers (m_pProxy0 and m_pProxy1) in btBroadphasePair.  The order is depends 
on the values of the proxies' m_uniqueId members, which is nondeterministic.  
The proxies are sometimes swapped in order to make generating a hash for the 
pair independant of their order.

What version of the product are you using? On what operating system?
Bullet 2.77 (svn r2220) on Windows, Xbox 360 and ps3.

Please provide any additional information below.

The attached patch prevents reordering the pairs and solves the problem of 
creating a hash by only checking the order when generating the hash, that is to 
say calling getHash().  Based on the points in btHashedOverlappingPairCache at 
which the pairs were previously reordered versus getHash() invocations, the 
only performance penalty should be some negligible additional checks/swaps when 
growTables() runs.

Original issue reported on code.google.com by neph...@gmail.com on 18 Feb 2011 at 10:57

Attachments:

• bullet-svn-broadphase-determinism.patch

[GoogleCodeExporter]

"The order is depends on the values of the proxies' m_uniqueId members, which 
is nondeterministic"

How is the value of m_uniqueId nondeterministic?

As long as you add the objects to the world in the same order, it should be 
deterministic, right?

Do you have some reproduction case to show this problem?
Thanks a lot,
Erwin

Original comment by erwin.coumans on 19 Feb 2011 at 7:19

[GoogleCodeExporter]

I don't know about other broadphases, but in the case of btAxisSweep the 
m_uniqueId field is an index into the m_pHandles array.  Handles in the array 
are allocated from a last-in-first-out linked list of free array indices 
(m_firstFreeHandle/Handle::SetNextFree()/Handle::GetNextFree()).  Therefore, to 
get repeatable values of m_uniqueId from one simulation run to the next, it's 
necessary to either destroy and recreate the broadphase or ensure that objects 
are removed from the collision world in the reverse order of their being added 
to it.

So, I'm not sure if it was entirely fair of me to call that behaviour 
'non-deterministic', but it does seem like an unnecessary trap for people who 
are interested in a determistic simulation.

Are you still interested in a test case?  If so, I can provide one.

Original comment by neph...@gmail.com on 23 Feb 2011 at 3:57

[GoogleCodeExporter]

It is indeed necessary to destroy and re-create the broadphase. We are not 
making the change for Bullet 2.x anymore.

We are now focussing on Bullet 3.x at http://github.com/erwincoumans/bullet3 
and make sure it will be deterministic/reproducing same results.

Original comment by erwin.coumans on 12 Sep 2013 at 10:36

• Changed state: WontFix