Constant AABBoverlap calls

[rvangaal]

Hi,

I have performance problems. I have a large racetrack (a Tree collision) and about 200 small cones, using Convex Hull collision geometries.
When running this, I get low fps, seemingly caused by lots of calls to AABB overlap callbacks that compare the tree with the cones. The track is large and it's AABB actually always overlaps with each cone, so I guess Newton is then calculating contact points.
However, the cones are frozen (NewtonBodySetFreezeState), so is it normal that my large Tree collision still calls the AABB overlap callback every time?

Thanks,
Ruud

[Julio Jerez]

If the cones are at rest slepping then there should not be any call to AABB at all.
it should only get the force and torque call aback.

however 200 hundred cones should not slow down the broad phase of the enigne at all, even if the cones are active all time, it should be able to deal with a lot more than that,
it shoud eassilly cope with tree or four time that numbe before it even start to slow at all. Is the tree collision optimized?

can I see wire frame image?

[rvangaal]

It still is generating the AABB callback. I have attached a crude wireframe image.
I tried setting the freezestate of the tree collision directly; each cone now has freezeState 1, but the tree collision still 0. I tried (pseudo-code):

- SetFreezeState(1); printf("Freezestate %d\n",GetFreezeState())

For the tree collision, this does not work. I dived into the Newton source a bit, and found this in dgBody.cpp:

void dgBody::Freeze ()
{
if (m_invMass.m_w > dgFloat32 (0.0f)) {
if (!m_freeze) {
m_freeze = true;

Obviously my track is static in the world, so has a mass of 0. Probably this means that it fails to freeze. This effectively means the tree has freezeState=0, and the cone freezeState=1. Might this trigger AABB overlap calls anyway (one of the objects being not frozen)?

Thanks,
Ruud

[Julio Jerez]

Tha image show teh cone colliong with oen maybe to faces and teh fsp is 5 fps, you must have something that keep the object active or some that is going terrible wrong.
the bottom line is that 200 hundred objects should not slow down the engine not even a few microsecond even if they all are active at all time regardless of how complex the object are.
even if the terrain have few tens of millions faces.
I assume you are using core 200, is this is so you can check file c:..\source\physics\dgBroadPhaseCollision.cpp

look an this function and set a break point there.

Code: Select all

void dgBroadPhaseCollision::UpdatePairs (dgBody* const body0, dgSortArray::dgListNode* const srcnode, dgInt32 axisX, dgInt32 threadIndex) const
{
//   dgFloat32 val;
//   dgBody* body1;

   if (!body0->m_collision->IsType (dgCollision::dgCollisionNull_RTTI)) {
      dgFloat32 val = body0->m_maxAABB[axisX];
      dgCollidingPairCollector& contactPair = *((dgWorld*)this);
      for (dgSortArray::dgListNode* node = srcnode; node && (node->GetInfo().m_key < val); node = node->GetNext() ) {
         dgBody* const body1 = node->GetInfo().m_body;
         if (!body1->m_collision->IsType (dgCollision::dgCollisionNull_RTTI)) {
            _ASSERTE (body0 != body1);
            if (OverlapTest(body0, body1)) {
               contactPair.AddPair(body0, body1, threadIndex);
            }
         }
      }
   }
}


void dgBroadPhaseCellPairsWorkerThread::ThreadExecute()
{
   dgInt32 step = m_step;
   dgInt32 count = m_count;
   dgBroadPhaseCollision& broadPhase =  *m_world;
   for (dgInt32 i = 0; i < count; i += step) {
      if(m_pairs[i].m_cell_B) {
         broadPhase.UpdatePairs (*m_pairs[i].m_cell_A, *m_pairs[i].m_cell_B, m_threadIndex);
      } else {
         m_pairs[i].m_cell_A->UpdateAutoPair(m_world, m_threadIndex);
      }
   }
}


That is the function that is call to determine if a pair of bodies is close enough to send then to the narrow phase contact calculation.
if you have 200 cone on a terrain, if they are no touching each other they yu will have few calls

void dgBroadPhaseCollision::UpdatePairs (dgBody* const body0, dgSortArray::dgListNode* const srcnode, dgInt32 axisX, dgInt32 threadIndex) const

each with bodo0 being the terrain, and srcnode a list of few cones,
since the terrain is larger and if the cones are active then there will be 200 calls to
if (OverlapTest(body0, body1)) {

if the test pass then that pair will be send to the pair list for contact calculation
contactPair.AddPair(body0, body1, threadIndex);

there are few points here.
1) even if the cone are all active the maximum number of call is 200, not enough to slow down that function,
you can call it maybe 200,000 time before you see the impact in eh Game.

2) if the code are at rest that function should not even be called at all. so there must be something that is keeping the cone active.

this mean there are more than one reason for this.

the first thing to do is to make a simple test that can be step trough.

I suggest make a test demo with the same mesh track, but only with say 5 representative cones. do no apply anything let the cone has default values.
this test is to see if the cone fail to go to rest.

then run the demo until they are settle on the terrain,
then set a break point on function void dgBroadPhaseCellPairsWorkerThread::ThreadExecute()
that function should not be called is the cone are all resting on the floor.

that will be test 1,
can you do that before we do the next test which is making all cones actives and see if it is the search for the triangle that the cone is colliding with that is producing the slow down.

if you can produce that test and the first part fail, can you send it to me for testing?

[rvangaal]

Forgive my ignorance on this part, but how would I most easily debug this? I tried adding the physics/core/newton .vcproj files to my own, but I get a mixup of the configurations (debugDLL, releaseDLL and my own Debug and Release).

Previously I could send you an exe and you could set breakpoint in your newton.dll to check things separately from my project; how did you do that exactly? How do you set a breakpoint in a DLL that you're not opening yourself?

I'll see if I can get it working, but I'm wandering in too many directions currently...

[rvangaal]

Ok, I got it working by creating a .lib and using that in my project (I'm using core200 indeed).

The results: first, I got an assert when optimizing my tree:

- dgPolygonSoupBuilder.cpp line 938: _ASSERTE (leftOver.GetCount() == 0);

I skipped optimizing my tree to get beyond this one.

Next, I have a car ofcourse and cones. The car is always active since it's moving.
After some time to let the cones rest, I set the breakpoint and it stops at:

void dgBroadPhaseCollision::UpdatePairs (dgBody* const body0, dgSortArray::dgListNode* const srcnode, dgInt32 axisX, dgInt32 threadIndex) const

Some Overlap tests do succeed and perform AddPair(). With 1 car and 1 cone I get both in my AABB overlap callbacks.
Also, dgBroadPhaseCellPairsWorkerThread::ThreadExecute() is run, but this might be because of my car being non-frozen. I might need to turn it off; the car is probably getting in the way of debugging this.

Can it be that adding gravity force to the cone each step will make it active? Should I skip that if the cone is frozen?

EDIT: More information: when trying to turn off gravity force adding when the cone is frozen, I get no change.
However, when I hit the cone with the car, it is thrown away. Then, after it comes to rest then, the AABB calls for the cone stop!

So it seems like the cone is slightly pushed into the track polygons perhaps at the beginning (and forced frozen). However, I then applied a small offset (of 0.5m) to lift the cone up and make sure it doesn't touch the track.

In detail:
- at the start, the cone is frozen, the car is not. The cone floats 0.5m above the surface. I get AABB overlap calls for car-tree and cone-tree.
- I hit the cone and it flies away. After a while, I get AABB calls now only for car-tree. The car is not frozen.
- I move the car close to the cone; AABB calls car-cone appear. Both car and cone now have freezeState=0. I would expect the cone to be frozen now (autosleep=1).

All this time, NewtonBodyGetAutoSleep returns 1 for both car and cone...

[Julio Jerez]

if you add teh car it will be mode complicated because it si an active object.

basically the car will be tested agaisnt the map, and all the coned that happen to be in the same sector that the car is at.
I am gussing that for 200 cones if they are no all closted together you will be getting aroidn a docen calls.

It is better to debug with out any active object.

I asume that in teh cone force callback you are always applity the gravity. do not try to secund guess what the engine wants to do to the cones.
simple apply the same gravity force in every call to thier force and torque callback.
the cone will be at rest and considered sleeping if the gravity, plus the resting forces add to zero, and it velocity is also zero, and it is not force active.
if you move it, activate it, skip applying gravity, apply a variable gravity, give it a velocity, or an impulse, any of those things will change the
physic equlibrium of the cone and they will be considered for contact calculation by adding it the the pair list.

you should simple place the cones in the map, and in the callback apply the gravity, just like any object in real life.

In a map polulated by cones, after a few ticks all cones should go to rest, and you should get zero calls to dgBroadPhaseCollision::AddPair

also remember after that test if all the cones go to rest, mesaure the time taken by the physics step,
then force all cones active and measure the time taken by the physcis step again, the difference should by not more than a milisencund,
and even that estimate is very high for 200 objects.

Remember do not do anything to the cones other than just apply the gravity force in the force callback.
the function for the force callback of the cone should look like this

Code: Select all

DEMO_GRAVITY = -9.8
// add force and torque to rigid body
void  PhysicsApplyGravityForce (const NewtonBody* body, dFloat timestep, int threadIndex)
{
   dFloat Ixx;
   dFloat Iyy;
   dFloat Izz;
   dFloat mass;
   NewtonBodyGetMassMatrix (body, &mass, &Ixx, &Iyy, &Izz);
   dVector force (0.0f, mass * DEMO_GRAVITY, 0.0f);
   NewtonBodySetForce (body, &force.m_x);
}

[rvangaal]

I think I found it! I didn't realize the difference between freezing and sleeping.
My initial state for all cones was frozen; this to try to avoid unnecessary calculations for the first few frames.
A frozen object though seem to NEVER go to sleep! This is why the AABB keeps getting called.

I have modified things so that all cones initially are NOT frozen; it now comes to rest after a few steps indeed, and all cones are going to sleep.

A point though; in the documentation (Wiki) for NewtonBodySetFreezeState, it states:

"If some other body collide or is connected to a frozen body,
the entire island become dynamic again, but only while they are connected to an non-frozen body.
When they lose the contact they become frozen again."

It seems when I hit my frozen cone, it is unfrozen, but never frozen again after it comes to rest. Is that right?

Questions that remain then:
- is it by design that a frozen body never goes to sleep? (if so, why?)
- when would you need to freeze a body? (it gets unfrozen when hit, so I don't see the difference between freeze=1 and sleeping=1)
- can I set an initial body sleep state? My cones are all well-placed, so normally don't need to be awake at startup. I see a NewtonBodySetSleepState() call is missing; for the 300 cones or so, you'd think it be good to be able to force the initial sleep.

Thanks for the help sofar!

[Julio Jerez]

A frozen object though seem to NEVER go to sleep! This is why the AABB keeps getting called.

that may be a bug in newtn then, a frozen body would be frce sleeped.
fowever freezen a body is a special case feature, foe xampel if you wa to put a body floating in the air bu you do no want the body to fall.

A point though; in the documentation (Wiki) for NewtonBodySetFreezeState, it states:
"If some other body collide or is connected to a frozen body,
the entire island become dynamic again, but only while they are connected to an non-frozen body.
When they lose the contact they become frozen again."

That shoud be the correct behavior, It may had broken in 2.0 but is is how it should be I will verify.

- is it by design that a frozen body never goes to sleep? (if so, why?)

No a frozen body should always be forced sleep, and only be dynamic if it come in contact with another active body.
the moment the frozen body loses its conection to any active body, the frozen body stops being simulated.

Like I say this is a special feature that may not be what you want.
for example say a cone in lifted on the air, because it is frozzen it will not move and wil stay float there locking bad,

This behavior of Newton in SDK 1.53 was used by some of the self appointed Crackpot experts from Umaea University in some physics forum
and some graphics forum to show that Newton was just as Bad as some other engines,
In newton 2.00 I change the sleep/freeze algorithm an I migh had broken that Freeze flag funtionality. I will verify.

One way to us eteh frezze flag is a One time freeze
say you have lot of cones, whe you satt teh lever theyw will all be active and teh engien will try to bring then to reast before puting then to sleep.
because of that teh code may be slow at the start.

if you make the frozzen (after I fix the Bug of course), then the will be simple there,
ther you make a material and in the material callback you check if the body was frozzen.
if it is frozzen you make it unfrozzen.

then from that point on, that body will be active and will go normally to sleep when it reach equilibrium.
since the bodies tend to be separated, not all will be active, therefore the performance should be acceptable and the physic behaviur will be realistic as well.


So is the preformanace acceptable now?

[Julio Jerez]

There is also a Feature of the engine used by very few people. this is

void NewtonSetIslandUpdateEvent (const NewtonWorld* const newtonWorld, NewtonIslandUpdate islandUpdate);

this is a call back that you set in the newton world, the function callback prototype is this

int IslandCallBack(const NewtonWorld* const newtonWorld, const void* islandHandle, int bodyCount);

this function is called with the set of bodies that will be submited to the solver for calculation. in the function you can use this other two functions, to get infomation abpout what is going to be simulated
NewtonBody* NewtonIslandGetBody (const void* const island, int bodyIndex);
void NewtonIslandGetBodyAABB (const void* const island, int bodyIndex, dFloat* const p0, dFloat* const p1);

you can qicklly get the AABB of the entire island and check against the view frutrum to see if the body is in view.
if the AABB inteset the frustrum to return 1 an dteh isaln will be update normally, if you return zero then teh island will be suspended and no caculation will be done until the function return 1.

the callback can be somethog like this

Code: Select all

int IslandCallBack(const NewtonWorld* const newtonWorld, const void* islandHandle, int bodyCount)
{
   dVector minP(1.0e10f, 1.0e10f, 1.0e10f, 0.0f);
   dVector maxP(-1.0e10f, -1.0e10f, -1.0e10f, 0.0f);
   for (int i = 0; i < bodyCount; i ++) {}
      NewtonBody* const body = NewtonIslandGetBody (island, i);
      //check if this body si of special interst, for example teh bod is a car
      if (IsSpecialBody(body)) {
         return 1;
      }
      dVector p0;
      dVector p1;
      NewtonIslandGetBodyAABB (island, i, &p0.m_x, &p1.m_x);
      for (int j = 0; j < 3; j ++) {
         minP[j] = GetMin (minP[j], p0[j]);
         maxP[j] = GetMax (minP[j], p1[j]);
      }
   }

   return CameraFrustrumCheck (minP, maxP);
}

Now by sun thsi featire you can place many cone in eh world, all normally an dteh all will be there.
only the one in view will be active simulated and the will go to sleep, by as all other will be skipped.
then as the come into view they will resume simulation again.
this is anoe feature you can consider too for perfomace consideration with large worlds withe many bodies.

[rvangaal]

No a frozeen body sodul aloway be forced sleep, and only be dynamica if it is in contact with anoeth active body.
teh momen eteh frozzen body loas it conetion to any active body it will that body and all oteh frozen body it is in contact with will stop being simulatete.

Like I say this is a special feature that may no be what you want.
for example say a cone in lifted on the air, because it si frozzen it will not move,
say you hit it, then teh collison life teh cone even higher, by nwi the cone is not torchig anthing so it will be supended in th air.

So is the preformanace acceptable now?

Performance is good now, thanks. (except for the first few frames, but I'll do that initial-freeze trick and unfreeze on the first hit)

In any case, the freeze flag seems buggy indeed; if I freeze the cone in mid-air, then hit it, it will fall down to the ground, never going back to freeze mode and lying still on the ground (not floating higher up).
I'll await your fix!

[Julio Jerez]

I think I found the reason why Freeze body behavior changed in 2.00

if you look at file ..\source\physics\dgBodyMasterList.cpp
in 1.53 the function AttachConstraint and RemovedConstraint were controlling the equlibrium fstate of a body by themself,
then in 2.00 I changed that to make a call to Unfrezze body, but this was a mistake because then it changes the freeze state of the body for ever redering the functio SetFreeze useless

here one of then

Code: Select all

void dgBodyMasterList::AttachConstraint(dgConstraint* const constraint,   dgBody* const body0, dgBody* const srcbody1)
{
   _ASSERTE (body0);
   dgBody* body1 = srcbody1;
   if (!body1) {
      body1 = body0->GetWorld()->GetSentinelBody();
      constraint->m_isUnilateral = true;
   }
   _ASSERTE (body1);

   constraint->m_body0 = body0;
   constraint->m_body1 = body1;
   constraint->m_link0 = body0->m_masterNode->GetInfo().AddJoint (constraint, body1);
   constraint->m_link1 = body1->m_masterNode->GetInfo().AddJoint (constraint, body0);

// note this is in observation (to prevent bodies from not going to sleep  inside triggers      
//   body0->m_equilibrium = body0->m_invMass.m_w ? false : true;
//   body1->m_equilibrium = body1->m_invMass.m_w ? false : true;
   body0->Unfreeze();
   body1->Unfreeze();

   m_constraintCount = m_constraintCount + 1;
}

I will have to go and see why I did that and make sure the freeze flag is repected.
I think it has to do wit the trigger feature that appeedr first in core 200 but I do not remember.

basically what happened was that you were calling frezze body and the engine was calculation contacts,
that set unfreeze automatilly but you kept calling Freezze again and the body was in a perpetual first time collison state, throwing away the contact cache
and doing the contact calculation the most expensive possible way.

It was no the AABB, or teh collision trree being big that was slow, it was the was what came next, narrow phase contact for teh cones.
Narrow phase contact calculation is expnesive for first time collision, but after that the cache make very fast.

I will fix it so that freeze works as it should.

[Julio Jerez]

Ok I believe that commenting out the two calls to
// body0->Unfreeze();
// body1->Unfreeze();

in those tow funtion soudl solve the problem
by doing that the cache is valid and only the first time contact are calculated of after the body move.
you can see a break point in function to break point, if that function returns zero, it means the cache will be throw out because the body lost it equilibrium, but Unfreeze does exactly that it tell teh body its equlibrium is invalid and it does it again.
dgInt32 dgWorld::ValidateContactCache (dgBody* const convexBody, dgBody* const otherBody, dgContact* const contact) const

Are you getting teh code from SVN?
I can sync to it and get the fix and you can test it, see if it works the way you want.

remember tshi si oly to fix the freeze flag behavior, it i sbetter not to rely on a feature to get the desire behavuior,
it is when the body is at rest that they are most efficient. A frozen body still need to check AABB, and is added to the contact pair, and resting body it is not.
frozen bodies save contact calculation is they are not moving and solve resolution

[rvangaal]

I don't see much change with the Unfreeze() calls commented out (in both AttachConstraint() and RemoveConstraint() ).
What I get if I freeze the objects (just one time, when the cones are loaded) is that AABB overlaps are being called for each cone, with the state of each cone being:

freezeState 1, autoSleep 1, sleeping 0

So even though they not unfreeze when being hit, they never go to sleep in the first place. Hm. The question is then how to get the objects to sleep still at the start, only to wake them up when being hit (to avoid narrow phase contact calculations taking place for all cones for the first few frames, which is highly noticable).

I'm using SVN indeed.

[Julio Jerez]

In newton 200 objects only go to sleep went they are in equilibrium. Freeze only supend the solver resoltion and the contact calculation if teh body is not moving.
But they get the broadphase calls.

This is different form 1.5 where freeze bodies were also sleeping.

The easiest way to get the body sleeping in the first frame is to save the scene with all bodies at rest instate that simply place then close enought to thisr location and let teh real time do the job.

I know this is a a pain because it requires to save the scene from some kind of editor which nee ot run the update before saving,
but is saves a great deal of logic in the engine. In the past many people where very confused with sleep bodies not getting callback.

if in your editor you add a command that simple update the newton world until the object are sleeping then after you load the scene they entire scene will go to rest after the first frame.
This is problem the nature of all physics base games.

I hope you undetand it.
the bottom line is that freezing a body when it is not in equilbrium violates many laws of newtonian mechanics, so keepping track of a freeze body that is not in equilibrium makes the logic very complicated.

Bascially in newton 1.5 this was possible simply because sleeping bodies and frezze bodies were in a secund list, so only bodies in the active list were updated.
however in newtn 200, the double list tecnique does no work well with mutitreading algotim, many bodies keep going to sleep dunring simulation and it end up doing too many critical sections.


I will check what are the implications of skipping broaphase update on bodies who has the freeze flag on,
It seems that soudl not be a problem, it is not I will make it so.
Out of teh bat, I know that they braphase sdul eb call at least once. because if they are it cause desatrisu result.

say for example you put a freeze body in the level, then another body hit it.
if the body does not have a braophase pair, then it will has not contacts wit teh level, but it will go to the solver because it is in contact with an active body,
but at that time it is too late to calculate contacts so it will most likly penetate the ground.

So frozen bodies needs a more sophiticate function to detect if it is OK to skip broaphase update on then. I will invetigate, I do no see why it cannot be possible.