Height Field Collision Issue

[Julio Jerez]

The assert should not hit, did you get it hit.?
The working buffer is a trick I use in many places.

What happens is that the low level collision routines, can calculate more that 16 contacts, imagine a shape Colliding with a collision tree and hitting many faces,
If it got say 8 faces, each face can generate upto 8 contacts,
So 16 time 8 is 128, that number can even be bigger.
Other shapes that can generate many intermediate interarion between compounds.

With so many contacts, there is lot of duplications, plus the solver has a limit of 16.
In fact for Newton 4 that limit has being reduced to 8.

So to, reduced the redundancy from the list, there is a contact prune routine that removed non essential points then from the array.
The contact prunner takes an array of points a generates a reduced hull of up to 16 points. And those are the one used for collision. It actually does a lot more, it reduced duplicated points that are in between straight line, points that fall in a plane, point that fall inside a volume.
This is one of the biggest responsible of the better quality of the solver in 4.0, since these points Introduced singular values in the solver matrix.

If you step over the code you can see it.

On the secund issue. You are correct it is a big bug, I had it craching an I fixed, but for some reason when merging I did not copy that fix, ther is a commit that say I fixed but since I did not copy the merge, the bug is there, I will fix it.

[Julio Jerez]

to see the contact prunner you can set a break point in function
ndInt32 ndContactSolver::ConvexContactsDiscrete() line 2371

you can see that is prune to a limit of 16 contacts. but you are right to make some warning checker happing we should check that, that is does not copy more that the limit of the fix size array

if you sync, you will get the correct fix.

[Esharc]

No I did not get the assert, I was just concerned that it might happen later on. Thank you for explaining it to me, it makes sense now. I see now where you prune the contacts in the contact solver.
I will merge now again.

I do like working with Newton 4 more than 3.14. It feels a lot less black box now that I can see and step through the code much easier.

[Julio Jerez]

I do like working with Newton 4 more than 3.14. It feels a lot less black box now that I can see and step through the code much easier.

that's the idea.

now that were there, I looked at Prune2dContacts
in my list of future optimizations was to replace the quick hull in two d, with analytical Monotone chain, Andrew's, they both have O(k * n * log(n)) complexity, but the k for the monotone chain, in order of magnitude smaller.
plus is also has the special case that for 3 contacts do not work. and that is a lot.
this should be a good improvement.

the only part I am dubious is that quick hull is very robust numerically, while Monotonic change rely on sorting point lexicographically and sometime rounding errors, can me it that tow point with the same x, and appear in the wrong order. I had not seen it fail yet, but if it does, we still has the old method.

anyway, I crossed out now.

[Esharc]

I am getting an assert which is strange to me. I cannot figure out why it is happening.

I have a test setup where I have added two bodies with a hinge joint connecting the two bodies. All I do on my side is move the hinge between the maximum and minimum limit. It works fine for most of the time, but occasionally this assert gets triggered.

DebugAssert1.png (27.01 KiB) Viewed 3263 times

DebugAssert2.png (16.59 KiB) Viewed 3263 times

DebugAssert3.png (43.39 KiB) Viewed 3263 times

When I ignore the assert, the test continues as normal. So I am confused as to what I am doing wrong to cause the assert.

*EDIT*
I did notice now that I was setting the sleep state of body0 in the update loop. When I take that out then I do not get the assert anymore. The sleep state and auto sleep state confuses me a bit. If I set auto sleep state to false, will the bodies still go into a sleep state if they are not moving? It seems that that is the case here by me

[Julio Jerez]

That not good, in the body array bodies are enumerated, but their location in the array.

That because later in the solver after forces are calculated, a body need to be located from the body index,
Using a pointer is not good because the solve use hew temporary array, that represent others value,
So and index is more useful.

The fact is not crashing is problematic worse, because what it means is that some value is going to be assigned to a wrong body.

You say you have two bodies connected by a hinge?
And you move the hinge?

I will set the standart joint demo to do that, and see if it can be repro..
Is one of the bodies static?

[Julio Jerez]

Bodies always go to sleep as a result of calculation by the solver.
When a body is at rest, meaning net acceleration and net veloc is below the sleep threshold.
But this condition alone is not enought to put a body to sleep. Because it will put bodies in unstable equlibrium to sleep as well.

There are three type of equilibrium in mechanic.
Stable, unstable and indifferent.

Stable is when a small perturbation of the position causes the body to gain potential energy, for us this means the center of mass will go up. Think of a ball rolling on a valley, any movement will cause the ball go uphill.

Unstable is when a small perturbation causes the body to lose potential energy, ex a ball on the top of a mountain, any movement will make the ball goes down hill

Indifferent when the small perturbation does not affect the potential energy. Like a ball rolling on a flat plane.

What we want, is for bodies to go to sleep when they are in stable equilibrium.
But the conditions for stable and unstable equilibrium, are identical if we only consider one instant in time.

The key word is the small perturbation, which translate to time. We need to some how introduce the small perturbation to discriminate between stable and unstable equibrium.

Now adding a small perturbation, is not as eassy as it sounds, this implies solving the system one instance in time with the same inputs. But that is prohibitive.

Imagine a cube on an edge with the center of mass falling exactly on the edge. That's a typical case of unstable equilibrium.
This is possible in nature but very unliketly, but in a simulation, the acceleration and velocity are not tested against zero, they are checked against a threshold, so the likelihood of unstable equibrium is far higher and that has to be avoid it.

So what we want is to discriminate from stable, and unstable equilibrium.

For that, we introduce the concepts of islands.
An Island is a group of connected bodies by joints.

Now with this, we can store time Information in the island,
And we can represent the small perturbation, by simply counting how many frames the same island is in equilibrium.
Only island that are in stable equilibrium will survived for a few frames.

So now the condition for going to sleep are.
Acceleration bellow some threshold
Velocity below some threshold,
And the same condition met for certain number of frames.

If all thre are met, then the Intire island goes to sleep.

And now we can add some heuristic, like big islands relax the condition more than small islands.

You also has an interface to set or rest the flag if individual bodies.
So let us say you have a game play object, and you want the to be active even if it is in equilibrium.

This is why you can see bodies in a large array can go to sleep but the island does not.

Them there is the auto sleep flag, which is very simple.
When the final sleep flag for a body is determined.

It does not just set that flag, it set that flag via an and operator with auto sleep flag.
So what this mean is that the body can only sleep when
Auto sleep is true.

[Julio Jerez]

I look at the assert and it turn out that was legacy from code, I removed it, it should work now.

[Esharc]

You say you have two bodies connected by a hinge?
And you move the hinge?

I will set the standart joint demo to do that, and see if it can be repro..
Is one of the bodies static?

Yes there are only 2 bodies and they are connected with a hinge, one of the bodies are static

Thank you for the explanation of the sleeping functionality it makes much more sense now

[Esharc]

I see in ndJointBilateralConstraint.h the function GetRowsCount() returns m_maxDof. Should it not rather return the actual number of rows for the joint?

[Julio Jerez]

Get row count return the max number of rows a joint can have.

For a six dof that should be 6, but the solver now can handle
Singular values, so is it set to 8,
The number is the capacity not the actual count, the actual count is not known until the funtion Submit constraint is called.
It is similar to when you call reserve on an st vector, it just reserve space, but the number of element is not know union after you add elements.

[Esharc]

Get row count return the max number of rows a joint can have.

For a six dof that should be 6, but the solver now can handle
Singular values, so is it set to 8,
The number is the capacity not the actual count, the actual count is not known until the funtion Submit constraint is called.
It is similar to when you call reserve on an st vector, it just reserve space, but the number of element is not know union after you add elements.

Ah I see thanks.

[Esharc]

In ndJointKinematicController.h, the GetTargetMatrix() functions returns m_localMatrix0, but the SetTargetPosit, SetTargetRotation and SetTargetMatrix all set m_localMatrix1. Shouldn't GetTargetMatrix() return m_localMatrix1?

[Julio Jerez]

Yes, you are probably right if that's the case, is not right, it should be consistent.
I do not remember now, if it is the case I will make it so Ge and set all manipulate a global matrix.
I will check it out.

I never like the proliferation of funtionality that could be recreated eassy by the app side, set and get local can be done by the app if it has the global interface.

[Esharc]

Hi Julio,

I am noticing something strange with the compound shape.

When I set the local matrix of the child shapes, then the shape is not placed at the position of the body.

CompoundShape.png (10.46 KiB) Viewed 3209 times

If I do not set the local matrix of the child shapes, then the shape is place at the correct position with the position of the body.

CompoundShape2.png (7.03 KiB) Viewed 3209 times

I have added a demo to your sandbox demos showing the process that I follow to create the compound shape. Here is the code for the example. You will notice that the compound shape does not collide correctly with the floor, but if you comment out the line in AddToCompoundShape() where I set the local matrix of the child instance, then the shape does collide with the floor correctly.

Code: Select all

#include "ndSandboxStdafx.h"
#include "ndSkyBox.h"
#include "ndTargaToOpenGl.h"
#include "ndDemoMesh.h"
#include "ndDemoCamera.h"
#include "ndPhysicsUtils.h"
#include "ndPhysicsWorld.h"
#include "ndMakeStaticMap.h"
#include "ndDemoEntityManager.h"
#include "ndDemoInstanceEntity.h"

static ndBodyDynamic* AddRigidBody(ndDemoEntityManager* const scene,
   const ndMatrix& matrix, const ndShapeInstance& shape,
   ndDemoInstanceEntity* const rootEntity, ndFloat32 mass)
{
   ndBodyDynamic* const body = new ndBodyDynamic();
   ndDemoEntity* const entity = new ndDemoEntity(matrix, rootEntity);

   body->SetNotifyCallback(new ndDemoEntityNotify(scene, entity));
   body->SetMatrix(matrix);
   body->SetCollisionShape(shape);
   body->SetMassMatrix(mass, shape);

   ndWorld* const world = scene->GetWorld();
   world->AddBody(body);
   return body;
}

static void AddToCompoundShape(const ndMatrix& mLocalMatrix, ndShapeInstance& parentShape, ndShapeInstance& childInstance)
{
   auto pCompoundShape = parentShape.GetShape()->GetAsShapeCompound();
   pCompoundShape->BeginAddRemove();
   childInstance.SetLocalMatrix(mLocalMatrix);
   pCompoundShape->AddCollision(&childInstance);
   pCompoundShape->EndAddRemove();
}

void CreateBoxCompoundShape(ndShapeInstance& parentInstance)
{
   ndShapeInstance wall1(new ndShapeBox(2.0, 2.0, 0.1));
   ndShapeInstance wall2(new ndShapeBox(0.1, 2.0, 2.0));
   ndShapeInstance wall3(new ndShapeBox(2.0, 2.0, 0.1));
   ndShapeInstance wall4(new ndShapeBox(0.1, 2.0, 2.0));
   ndShapeInstance floor(new ndShapeBox(2.0, 0.1, 2.0));
   ndMatrix mWall1Local = dGetIdentityMatrix();
   mWall1Local.m_posit = ndVector(0.0f, 0.0f, -1.0f, 0.0f);
   ndMatrix mWall2Local = dGetIdentityMatrix();
   mWall2Local.m_posit = ndVector(1.0f, 0.0f, 0.0f, 0.0f);
   ndMatrix mWall3Local = dGetIdentityMatrix();
   mWall3Local.m_posit = ndVector(0.0f, 0.0f, 1.0f, 0.0f);
   ndMatrix mWall4Local = dGetIdentityMatrix();
   mWall4Local.m_posit = ndVector(-1.0f, 0.0f, 0.0f, 0.0f);
   ndMatrix mFloorLocal = dGetIdentityMatrix();
   mFloorLocal.m_posit = ndVector(0.0f, -1.0f, 0.0f, 0.0f);
   AddToCompoundShape(mWall1Local, parentInstance, wall1);
   AddToCompoundShape(mWall2Local, parentInstance, wall2);
   AddToCompoundShape(mWall3Local, parentInstance, wall3);
   AddToCompoundShape(mWall4Local, parentInstance, wall4);
   AddToCompoundShape(mFloorLocal, parentInstance, floor);
}

void ndBasicCompoundShapeDemo(ndDemoEntityManager* const scene)
{
   // build a floor
   BuildFlatPlane(scene, true);
   ndShapeInstance compoundShapeInstance(new ndShapeCompound());
   CreateBoxCompoundShape(compoundShapeInstance);
   ndDemoMeshIntance* const compGeometry = new ndDemoMeshIntance("compoundShape", scene->GetShaderCache(), &compoundShapeInstance, "earthmap.tga", "earthmap.tga", "earthmap.tga");
   ndDemoInstanceEntity* const compEntity = new ndDemoInstanceEntity(compGeometry);
   scene->AddEntity(compEntity);
   ndMatrix mBodyMatrix = dGetIdentityMatrix();
   mBodyMatrix.m_posit = ndVector(-2.0f, 5.0f, -5.0f, 0.0f);
   AddRigidBody(scene, mBodyMatrix, compoundShapeInstance, compEntity, 10.0);
   ndShapeInstance originShape(new ndShapeSphere(0.5));
   ndDemoMeshIntance* const origGeometry = new ndDemoMeshIntance("origShape", scene->GetShaderCache(), &originShape, "earthmap.tga", "earthmap.tga", "earthmap.tga");
   ndDemoInstanceEntity* const origEntity = new ndDemoInstanceEntity(origGeometry);
   scene->AddEntity(origEntity);
   ndMatrix mOrigMatrix = dGetIdentityMatrix();
   AddRigidBody(scene, mOrigMatrix, originShape, origEntity, 0.0);
   
   ndVector origin(ndVector::m_zero);
   ndQuaternion rot(dYawMatrix (45.0f * ndDegreeToRad));
   origin.m_x -= 3.0f;
   origin.m_y += 5.0f;

   origin.m_x -= 15.0f;
   origin.m_z += 15.0f;

   scene->SetCameraMatrix(rot, origin);
}