Height field collisions

[Esharc]

Good afternoon Julio.

This is related to the same bug I reported about the static mesh, with respect to the fact that I am updating our version of Newton to the latest version.

In this test we have a height field with randomly generated heights and 100 cubes falling onto the height field. This tests asserts in

Code: Select all

void ndShapeConvexPolygon::GenerateConvexCap(const ndShapeInstance* const parentMesh)

line 328.

I am not sure why this is happening, but I think it may be related to your comment a line or two above. I am going to try and reproduce this assert in the sandbox.

[Esharc]

Luckily I could reproduce this issue. Here is the code that can be pasted into the demo sandbox

Code: Select all

void BuildHeightField(ndDemoEntityManager* const scene)
{
    int iDim = 64;
    ndFloat32 dSize = 128, dMaxHeight = 0.5;
    std::vector<ndFloat32> aData; aData.resize(iDim * iDim);
   ndFloat32 fHorizontalScale = ndFloat32(128.0 / (iDim - 1));
   ndShapeInstance shape(new ndShapeHeightfield(iDim, iDim, ndShapeHeightfield::m_normalDiagonals, fHorizontalScale, fHorizontalScale));
   ndMatrix mLocal(ndGetIdentityMatrix());
   mLocal.m_posit = ndVector(-(dSize * 0.5), 0.0, -(dSize * 0.5), 1.0);
   shape.SetLocalMatrix(mLocal);
   auto pShapeHeightField = shape.GetShape()->GetAsShapeHeightfield();

   for (int i = 0; i < iDim * iDim; ++i)
      pShapeHeightField->GetElevationMap()[i] = rand() * 2.0 * dMaxHeight / RAND_MAX;

   pShapeHeightField->UpdateElevationMapAabb();
   ndMatrix uvMatrix(ndGetIdentityMatrix());
   uvMatrix[0][0] *= 0.025f;
   uvMatrix[1][1] *= 0.025f;
   uvMatrix[2][2] *= 0.025f;

   ndSharedPtr<ndDemoMeshInterface>geometry(new ndDemoMesh("box", scene->GetShaderCache(), &shape, "marbleCheckBoard.tga", "marbleCheckBoard.tga", "marbleCheckBoard.tga", 1.0f, uvMatrix, false));
   ndMatrix location(ndGetIdentityMatrix());
   ndDemoEntity* const entity = new ndDemoEntity(location, nullptr);
   entity->SetMesh(geometry);

   ndBodyKinematic* const body = new ndBodyDynamic();
   body->SetMatrix(location);
   body->SetCollisionShape(shape);
   ndSharedPtr<ndBody> bodyPtr(body);
   scene->GetWorld()->AddBody(bodyPtr);
   scene->AddEntity(entity);
}

void AddBodies(ndDemoEntityManager* const scene)
{
   const int NUM_BOXES_ROWS = 10;
   const int NUM_BOXES_COLS = 10;
   ndFloat32 dUsableSpace = 128;
   ndFloat32 dSpacing_x = dUsableSpace / (NUM_BOXES_COLS + 1);
   ndFloat32 dSpacing_z = dUsableSpace / (NUM_BOXES_ROWS + 1);
   ndFloat32 dStart = -dUsableSpace * 0.5;
   ndVector vStart(dStart, 10.0, dStart, 1.0);
   ndMatrix location(ndGetIdentityMatrix());
   ndMatrix uvMatrix(ndGetIdentityMatrix());
   uvMatrix[0][0] *= 0.025f;
   uvMatrix[1][1] *= 0.025f;
   uvMatrix[2][2] *= 0.025f;

   for (int i = 0; i < NUM_BOXES_ROWS; ++i)
   {
      for (int j = 0; j < NUM_BOXES_COLS; ++j)
      {
         ndFloat32 dOffset_x = dSpacing_x * (j + 1);
         ndFloat32 dOffset_z = dSpacing_z * (i + 1);
         location.m_posit = vStart + ndVector(dOffset_x, 0.0, dOffset_z, 0.0);
         AddBox(scene, location, 1.0f, 1.0f, 1.0f, 1.0f);
      }
   }
}

void ndHeightFieldTest(ndDemoEntityManager* const scene)
{
    // build the height field
    BuildHeightField(scene);
   AddBodies(scene);

    ndQuaternion rot;
    ndVector origin(0.0f, 5.0f, 0.0f, 1.0f);
    scene->SetCameraMatrix(rot, origin);
}


[Julio Jerez]

ah yes, I knew that function
void ndShapeConvexPolygon::GenerateConvexCap(const ndShapeInstance* const parentMesh)

could be problem, but at the time I did not have a test case, to tune the heuristic,

I pasted in the ndSandbox\demos\ndStaticMeshCollision.cpp
in the sandbox for debugging, later I will debug it.

first let us check in that other bug with the contact solver was properly fixed.

[Esharc]

Thanks, I just realized when I synced again that I changed the

Code: Select all

ndBodyKinematic* CreateBody(ndDemoEntityManager* const scene, const ndShapeInstance& shape, const ndMatrix& location, ndFloat32 mass, const char* const textName)

function in ndPhysicsUtils.cpp to get the crash to work in the sandbox.

I commented the

Code: Select all

ndMatrix matrix(FindFloor(*world, location, shape, 200.0f));

and added

Code: Select all

ndMatrix matrix(location);

so that the bodies are not place on the height field when adding the bodies, but rather places them in the air so that they can fall on the height field.

[Julio Jerez]

Ok I took that into account and I set so that it runs the demo.
Please check it out when you have some time.

Tel me something, in this function.
void ndShapeConvexPolygon::GenerateConvexCap(const ndShapeInstance* const parentMesh)
by line 328

Code: Select all

      //TODO:
      //this could be a big problem, the edge shared by two faces should be perpendicular to the two normal
      //and it is not, I need to debug this with a repro, but for now just ignore it.
      //ndAssert(edge.DotProduct(adjacentNormal).GetScalar() < ndFloat32(5.0e-2f));
      ndAssert(edge.DotProduct(adjacentNormal).GetScalar() < ndFloat32(2.0e-1f));


I get the assert, but is not a terminal bug, it is a reminder to myself that they there can be bad contact generated at some edges.

basically, this is the problems.

the mesh patch that collides with a convex object is assumed to be a continue surface (a continue manifold). The exception is if the mesh has an open border, which should never happen in reality, since the physics assume a world where surfaces had thickness, but since this is digital world, the engine consider those cases by flagging the open edges.

Since the collision system process one face at a time. Each time the collision happens at an edge, it will generate a contact, but since we are dealing with a manifold, there will also be another face the shared the same edge and will produced another contact.

Unless those the two faces have the same plane equation, those two contacts will have different normal, and because of numerical error they will also have slightly different positions.

this is the cause of discontinue reaction forces by the solver.

I have tried many different solutions to this problem. most of the previous newton versions where base on generating the contacts, them in a postprocessing pass remove the redundant ones.
This is a very error prompt approach, that is full of numerical errors and tolerance tunning problems.

for Newton 4 the new approach is taking the assumption that the surface is continue, Therefore the contact generation itself should not generate more than one contact at the edge.

to do that, the mesh patch is authored with the edge information about the adjacent face.
then it generates a cap, that will extend the face by some skirt coplanar to the adjacent face.

for this the patch generator, determine if the two faced form a convex or concave edge.
when the edge in concave, the cap is zero length, because the should be not contacts over the edge.

if the two adjacent fasce are coplanar or convex, the face is extended, and it turns out that the contact in one face will be convex but for the other will be concave, therefore only one contact should be produced.

at least that's the general idea, the implementation is more involved, and that's why I put the comment there. I know that if I got there and I get a normal that is not perpendicular to the edge, it means that the other face will also generate a contact with a different normal.

I did not have a reproducible test at the time, so this one is very nice for debugging.

if you build in release or if you comment out the assert, it should run, so please try that, until I debug this,

also related to the second bug where you say the contacts set are reduce to zero after pruning,
that must certainly a different bug, so we check that later.

[Esharc]

I did test it by commenting out the assert, and it does work. I will leave it commented out then in our version until you have debugged the problem.

Thank you

[Julio Jerez]

Yes it looks like there are more than one bug.

It is going to take few days to go over.

I set it so that is reproduce the same bug with just one cube, and I will go over that,

The the same test also reprocess the second bug.
So there is work to do on my side.

It should not stops you from continuing thought.

Thank for the repo case

[Esharc]

Thank you Julio.

Yes fortunately these bugs do not stop me from continuing with the update and testing. And I have a bunch of other work to continue with in the mean time.

Good luck with finding those bugs. I am glad you could reproduce them both

[Julio Jerez]

alright, this bug is fixed now.

this was an important one for heightfield meshes,
The problem was the part that builds the colliding patch
manifold, was wrapping at the end of each row or column, assigning an edge normal from the next row.

It wouldn't crash, but I would generate bad contact when
the last triangle of each row or the last triangle of each column of the patch was part of the collisions.

anyway, glad I had this repro to fix it, because this would be hard to find.
if you sync everything should be working now.

thanks,

[Esharc]

Thank you Julio, I can confirm that this bug has also been fixed.

I will report any other bugs that I may find as I continue with the tests