Broadphase determinism

A place to discuss everything related to Newton Dynamics.

Moderators: Sascha Willems, walaber

Broadphase determinism

Postby Cannos » Thu Aug 24, 2017 10:31 pm

I'm looking into a determinism/replay issue. Specifically I setup and run a simulation, then I "rewind" to the initial state, invalidate cache, and run again. I have a rare case I'm looking into where the 2nd run doesn't give the same results as the first run.

The first difference I see when running is that one of the contacts I'm getting has the 2 contacting bodies in a different order, and the contact normal very slightly different (in addition to being the opposite direction since the bodies are swapped). So...

Question 1) If 2 bodies are in a different order when calculating contacts, is it possible that the contacts can be different (aside from the normal being in the opposite direction).

It appears that the bodies are in a different order because the broadphase tree is different. I can see that the dgBroadPhase::CalculateEntropy() and dgBroadPhase::ImproveNodeFitness() calls are giving different results.

Question 2) If I add some bodies, and then remove them, should the broadphase be the same as when I started? And does it matter if it isn't?

Question 3) If the broadphase organization needs to be the same and deterministic, is there a way to fully recalculate it at the same time I'm calling InvalidateCache?

NOTE - I'm running on an older version of Newton from September 2016 in case there have been changes to broadphase I should be aware of.
Cannos
 
Posts: 129
Joined: Thu Mar 04, 2010 5:41 pm

Re: Broadphase determinism

Postby Julio Jerez » Thu Aug 24, 2017 11:06 pm

yes the order of the body is a major cause of lost of determinism.
the function invalidate cache has not been updated in a long time and there are few places when the data have to be reset. Calculate entropy and fitness is one those cases.
Maybe one thing to do is to delete the broadphase and recreated again, that will delete the caches.
Another thing the newton 3,14 not longer uses OBB and ABB test, instead is uses a distance based approache that make more pairs but if far more robust and extend to discrete and continue collision naturally. That cache have to be destroyed too.

There is a functionality for that, I see if I bring Invalidate cache up to date tonight.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Broadphase determinism

Postby Cannos » Fri Aug 25, 2017 2:40 pm

Yes, I confirmed that destroying and recreating the broadphase fixed the determinism problem I was seeing.

FYI, I locally added the following to reset the broadphase (based on dgWorld::SetBroadPhaseType):

Newton.h
Code: Select all
NEWTON_API void NewtonResetBroadphase(const NewtonWorld* const newtonWorld);


Newton.cpp
Code: Select all
NEWTON_API void NewtonResetBroadphase(const NewtonWorld* const newtonWorld)
{
   TRACE_FUNCTION(__FUNCTION__);
   Newton* const world = (Newton *) newtonWorld;
   return world->ResetBroadPhase();
}


dgWorld.h
Code: Select all
void ResetBroadPhase();


dgWorld.cpp
Code: Select all
void dgWorld::ResetBroadPhase()
{
   dgBroadPhase* newBroadPhase = NULL;

   switch (GetBroadPhaseType())
   {
      case m_persistentBroadphase:
         newBroadPhase = new (m_allocator) dgBroadPhasePersistent(this);
         break;

      case m_defaultBroadphase:
      default:
         newBroadPhase = new (m_allocator) dgBroadPhaseDefault(this);
         break;
   }

   m_broadPhase->MoveNodes(newBroadPhase);
   delete m_broadPhase;
   m_broadPhase = newBroadPhase;
}
Cannos
 
Posts: 129
Joined: Thu Mar 04, 2010 5:41 pm

Re: Broadphase determinism

Postby Julio Jerez » Fri Aug 25, 2017 2:46 pm

Oh cool glad you figure it out, that very much what I was going to do.
excellent, can you make a pull request?
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Broadphase determinism

Postby Cannos » Fri Aug 25, 2017 3:00 pm

Yeah, I'll make a pull request later today.

Edit: Done
Cannos
 
Posts: 129
Joined: Thu Mar 04, 2010 5:41 pm

Re: Broadphase determinism

Postby Cannos » Thu Aug 31, 2017 2:27 pm

Looks like I'm still having a small issue with this, it looks like an order-of-operations issue.

Order the bodies are added to broadphase
  • When bodies are created, they're added to the broadphase in increasing order by their uniqueID.
  • In dgBroadPhase::MoveNodes() (called by the new dgWorld::ResetBroadphase()), they are added to the newly created broadphase in the order that they exist in the dgWorld master list, and this can be different.

Master list order
  • Before dgWorld::SortMasterList() is called, the master list is in roughly decreasing order of body uniqueID.
  • After dgWorld::SortMasterList(), it is in order by category (static/kinematic/dynamic), then by uniqueID. Both of these orders are different than the initial order.

So there are 3 total orders that bodies could be added to the broadphase depending on when/if ResetBroadphase is called:
  1. Initial order - increasing body uniqueID
  2. Pre SortMasterList order - roughly decreasing body uniqueID order <-- we likely never want this one. Only happens if ResetBroadphase() called before SortMasterList()
  3. Post SortMasterList order - by category, then by increasing body uniqueID

We need a consistent order in the broadphase, so I see a couple solutions:
  1. Use Initial Order - In dgBroadPhase::MoveNodes(), re-sort the list of bodies in order by increasing uniqueID, before adding to the new broadphase. This way they'll always be added in the order they were initially created, before any calls to InvalidateCache and ResetBroadphase.
  2. Use Post SortMasterList Order - Make sure to call SortMasterList() before ResetBroadphase(). And do this at least once before you expect determinism to start. This won't match the initially created order, but will be deterministic after the first SortMasterList().

    Also related, dgWorld::FlushCache() does this:
    Code: Select all
       m_broadPhase->InvalidateCache ();
       SortMasterList();


    But I think I need to make sure SortMasterList is called first, then the broadphase can be reset and invalidated, like this:
    Code: Select all
       SortMasterList();
       ResetBroadphase();
       m_broadPhase->InvalidateCache ();

Does this make sense? Solution (1) is more consistent with initial creation and doesn't require explicit ordering of SortMasterList() and ResetBroadphase(). But solution (2) doesn't require a separate sort just for the broadphase.
Cannos
 
Posts: 129
Joined: Thu Mar 04, 2010 5:41 pm

Re: Broadphase determinism

Postby Julio Jerez » Thu Aug 31, 2017 4:49 pm

this will definitely yeild the wrong result at some point.
When bodies are created, they're added to the broadphase in increasing order by their uniqueID.
In dgBroadPhase::MoveNodes() (called by the new dgWorld::ResetBroadphase()), they are added to the newly created broadphase in the order that they exist in the dgWorld master list, and this can be different.


I believe the should be added by the body unique id.
then after the broaphase is formed, it should call master sort and that should generate the correct order in the mater list because the sort in the maters list is stabled, meaning the order will be preserve.

for example ya you have two bodies, the will have different unique id by definition.
the may have the same category.

so the may be in order A, B is matter list.
I believe that if we sort them the order in the mater list after the sort should still be A, B

If this does not work, then the solution is to either to figure out why not, or remove the bodies for the mater list and re add then by the unique id order. the sort, this will guarantee the proper order.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Broadphase determinism

Postby Cannos » Thu Aug 31, 2017 5:31 pm

If A and B are in the same category, yes they will stay A and B in the master list after sorting.

But if they are different categories, they can be swapped so that B comes before A, even though B's uniqueID is greater than A's. This is because of the dgBodyMasterList::MakeSortMask() which adds the category flags to the sorting key. I.e. After sorting, all static objects will come before all dynamic objects regardless of creation (uniqueID) order.

So if the master list needs to be sorted to keep bodies in order by unique ID, then the category bits should be removed from the MakeSortMask and it should just use uniqueID. I'm not sure if there are other issues that require the master list to use category-based sorting though.

So which of these might be better? Just depends on if the categorization in master list is important for other reasons:
1) Always add bodies to broadphase by uniqueID, regardless of master list sort.
2) Make master list sort use uniqueID only. This will make broadphase order also match uniqueID order.
Cannos
 
Posts: 129
Joined: Thu Mar 04, 2010 5:41 pm

Re: Broadphase determinism

Postby Julio Jerez » Thu Aug 31, 2017 6:48 pm

But if they are different categories, they can be swapped so that B comes before A, even though B's uniqueID is greater than A's. This is because of the dgBodyMasterList::MakeSortMask() which adds the category flags to the sorting key. I.e. After sorting, all static objects will come before all dynamic objects regardless of creation (uniqueID) order.


the should be fine,
so what sink of static/dynamics being the highest significant digit of the sort key

so what we get is a key for the from
cathegory * largeConst + unique id.

so all static should be in order by unique id, and all dynamics should be in order by unique id.
this tell me that calling sort on the master list fix the problem because we know that the unique ids are different for each body so that makes it so that each sort key is unique.
In fact now I start to think the problem is not there. unless somehow there is a but in the master list and some objects are out of order.

my guess is that the broad phase is still the problem
1) Always add bodies to broadphase by uniqueID, regardless of master list sort.

one think you should take into account is that is you are going to use determinist, then the function you should periodically call invalidate cache.

here is the reason.

say you star the game with 100 bodies. and the game stat to run.
the and some point you want to restart the game, the only valid check point is the beginning of the game. no other point will guaranteed determinism because no other point will record of the amount of entropy that was reduced, the entropy nay have ben adjusted 4 or ten times.

so what you nee to do is that ever some frame you call invalidate cache and invalidate cache se the entropy to the max every where so the is force to be recalculate from the state of the bodies.
Julio Jerez
Moderator
Moderator
 
Posts: 12249
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Broadphase determinism

Postby Cannos » Thu Aug 31, 2017 8:02 pm

Yes, I already have InvalidateCache (and ResetBroadphase) calls at every checkpoint from which I need determinism. I've had this working for a long time and determinism has been good for me 99% of the time. These broadphase issues are the only problems I'm aware of at the moment.

The problem is the order in which bodies are added to the broadphase initially vs. when they are added in master list order.

Here's an example:

Bodies A (dynamic), B (dynamic), C (static), D (static) created:
  • Order added to broadphase initially: ABCD
  • MasterList initial order: ADCB (master list inserts new items after the first item)
  • MasterList sort: CDAB (sorted by category, then by uniqueID)

So the question is, when ResetBroadphase is called, should it always put bodies back into the broadphase in created order (ABCD), or in MasterList sorted order (CDAB)?

If the latter (CDAB), then we also need to make sure that SortMasterList() is called before ResetBroadphase(). And do an InvalidateCache/Sort/Reset before the initial simulation. For these reasons, I'm thinking that always adding to the broadphase in created order (ABCD) might be simpler and more robust since MasterList order wouldn't matter to it.
Cannos
 
Posts: 129
Joined: Thu Mar 04, 2010 5:41 pm


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 16 guests

cron