Custom collision

[pHySiQuE]

I am working on a new vegetation system. It dynamically positions object instances so that the 4x4 matrices of each object never have to be stored in memory. This allows an infinite number of plants to be used, without using any memory at all.

I am ready to implement the physics part of it. I understand that Newton has a callback system for custom geometry. Can you tell me where to get started with this? I think this will work by dynamically generating the 4x4 matrices of all object instances within a certain bounding box and return that to Newton for physics calculations.

download.jpg (51.56 KiB) Viewed 6921 times

[pHySiQuE]

I almost have it working now with the user mesh collision. Here is my collision callback.

Code: Select all

void VegetationLayer::CollideCallback(NewtonUserMeshCollisionCollideDesc* const collideDescData, const void* const continueCollisionHandle)
{
   collideDescData->m_faceCount = 0;
   collideDescData->m_vertexStrideInBytes = 3 * sizeof(float);

   //Get the vegetation layer object
   VegetationLayer* layer = (VegetationLayer*)collideDescData->m_userData;
   if (layer->instanceshape == NULL) return;
      
   //Calculate an AABB
   AABB aabb = AABB(collideDescData->m_boxP0[0], collideDescData->m_boxP0[1], collideDescData->m_boxP0[2], collideDescData->m_boxP1[0], collideDescData->m_boxP1[1], collideDescData->m_boxP1[2]);
      
   //List to receive all intersecting instance 4x4 matrices
   std::vector<Mat4> instances;

   //Retrieve all intersecting instances
   int count = layer->GetInstancesInAABB(aabb, instances);
   if (count == 0) return;

   //Get current thread ID
   int threadNumber = collideDescData->m_threadNumber;

   //For each intersecting instance, add that info to the collision data
   Surface* collisionsurface = layer->instanceshape->GetSurface(0);
   layer->collisionsurfaceindicecounts[threadNumber].resize(0);
   layer->collisionsurfaceindices[threadNumber].resize(0);
   layer->collisionsurfacevertices[threadNumber].resize(0);
      
   //Temporary integer array for indices
   std::vector<int> indices;
   indices.resize(collisionsurface->CountIndices());
   for (int n = 0; n < collisionsurface->CountIndices(); n++)
   {
      indices[n] = collisionsurface->GetIndiceVertex(n);
   }

   Vec3 pos;
   int sz;
   Mat4 identity;

   //Collate all intersecting instances into vertex / indice arrays
   for (int n = 0; n < count; n++)
   {
      collideDescData->m_faceCount += collisionsurface->CountTriangles();

      //Transform and add vertices
      sz = layer->collisionsurfacevertices[threadNumber].size();
      layer->collisionsurfacevertices[threadNumber].resize(sz + collisionsurface->CountVertices() * 3);
      for (int p = 0; p < collisionsurface->CountVertices(); p++)
      {
         pos = collisionsurface->GetVertexPosition(p);
         pos = Transform::Point(pos,instances[n],identity);
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 0] = pos.x;
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 1] = pos.y;
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 2] = pos.z;
      }

      //Add indices
      sz = layer->collisionsurfaceindices[threadNumber].size();
      layer->collisionsurfaceindices[threadNumber].resize(sz + indices.size());
      memcpy(&layer->collisionsurfaceindices[threadNumber][sz], &indices[0], indices.size() * sizeof(int));
   }

   //Fill face indice counts with '3' (triangles)
   layer->collisionsurfaceindicecounts[threadNumber].resize(collisionsurface->CountTriangles()*count*3);
   std::fill(layer->collisionsurfaceindicecounts[threadNumber].begin(), layer->collisionsurfaceindicecounts[threadNumber].end(), 3);
      
   //Set collisioninfo array pointers
   collideDescData->m_faceIndexCount = &layer->collisionsurfaceindicecounts[threadNumber][0];
   collideDescData->m_faceVertexIndex = &layer->collisionsurfaceindices[threadNumber][0];
   collideDescData->m_vertex = &layer->collisionsurfacevertices[threadNumber][0];
}

The data I give it is:
m_faceCount = 12
m_vertexStrideInBytes = 12
m_faceIndexCount = int[12] (all equal to '3')
m_faceVertexIndex = int[36]
m_vertex = float[72]


However, I get a crash in Newton. I traced the problem to dgCollisionMesh::GetCollidingFaces:

Code: Select all

      } else {
         for (dgInt32 i = 0; (i < data->m_faceCount) && (faceIndexCount0 < (DG_MAX_COLLIDING_INDICES - 32)); i ++) {
            dgInt32 indexCount = faceIndexCountArray[i];
            const dgInt32* const indexArray = &srcIndices[faceIndexCount1];

            dgInt32 normalIndex = data->GetNormalIndex (indexArray, indexCount);
            dgVector faceNormal (&vertex[normalIndex * stride]);
            dgFloat32 dist = data->PolygonBoxDistance (faceNormal, indexCount, indexArray, stride, vertex);

            const dgInt32 faceIndexCount = data->GetFaceIndexCount(indexCount);
            if (dist > dgFloat32 (0.0f)) {
               hitDistance[faceCount0] = dist;
               address[faceCount0] = faceIndexCount0;
               faceIndexCountArray[faceCount0] = indexCount;
               memcpy (&dstIndices[faceIndexCount0], indexArray, faceIndexCount * sizeof (dgInt32));
               faceCount0 ++;
               faceIndexCount0 += faceIndexCount;
            }
            faceIndexCount1 += faceIndexCount;
         }
      }

The faceIndexCount1 value is being incremented in a strange way. I would expect it to advanced by 3 each time, i.e. 0, 3, 6, 9, 12...

Instead it is going 0, 8, 18, 27, and then it exceeds the bounds of my vertex array and crashes.

This is how I got it to stop crashing (still no collision), but I do not know if this is correct:

Code: Select all

      } else {
         for (dgInt32 i = 0; (i < data->m_faceCount) && (faceIndexCount0 < (DG_MAX_COLLIDING_INDICES - 32)); i ++) {
            dgInt32 indexCount = faceIndexCountArray[i];
            const dgInt32* const indexArray = &srcIndices[faceIndexCount1];

            dgInt32 normalIndex = indexCount;// data->GetNormalIndex(indexArray, indexCount);
            dgVector faceNormal (&vertex[normalIndex * stride]);
            dgFloat32 dist = data->PolygonBoxDistance (faceNormal, indexCount, indexArray, stride, vertex);

            const dgInt32 faceIndexCount = indexCount;// data->GetFaceIndexCount(indexCount);
            if (dist > dgFloat32 (0.0f)) {
               hitDistance[faceCount0] = dist;
               address[faceCount0] = faceIndexCount0;
               faceIndexCountArray[faceCount0] = indexCount;
               memcpy (&dstIndices[faceIndexCount0], indexArray, faceIndexCount * sizeof (dgInt32));
               faceCount0 ++;
               faceIndexCount0 += faceIndexCount;
            }
            faceIndexCount1 += faceIndexCount;
         }

[Julio Jerez]

the correct sequence for a triangle going 0, 9, 18, 27, ... and then it exceeds the bounds of my vertex array and crashes.

the face continent two type of information, the vertex index and the normal index.
do the format for a triangle

v0, v1, v2, // triangle vertex index
A, // triangle used id
N, // triangle face normal
n0, n1, n2, // triangle normal of the adjacent triangle
L // length of the shortest edge

the formal to know the edge count is
triangleIndexCount = (c + 1) * 2 + 1

if you have N traingle the space you nee to allocate is

totalSize = N * triangleIndexCount;

c = the vertex count;

[pHySiQuE]

Okay, I am looking at the UserPlaneCollision.cpp example and trying to figure this out. It looks like the vertex positions and normals are both stored in the same vertex array:

Code: Select all

// index count
m_faceIndices[i][0] = 3;

// face indices
m_indexArray[i][0] = 0;
m_indexArray[i][1] = 1;
m_indexArray[i][2] = 2;

// face attribute
m_indexArray[i][3] = 0;

// face normal
m_indexArray[i][4] = 4;

// face adjacent index (infinite plane does not have shared edge with other faces)
m_indexArray[i][5] = 4;
m_indexArray[i][6] = 4;
m_indexArray[i][7] = 4;

// face area (the plane is clipped around the box, the face size is always optimal)
m_indexArray[i][8] = 0;

Where are face attributes stored? I assume this value is a pointer, so storing an offset in a dvector array doesn't make sense to me.

What is the face adjacent index? I don't understand how to calculate this.

How is the face area stored? Is this a float value stored in the vertex array? Why does your example just use an indice of 0? I don't see the triangle area being calculated anywhere.

I don't see anywhere in the code where vertex info is being set in the m_collisionVertex array?

[Julio Jerez]

Where are face attributes stored? I assume this value is a pointer, so storing an offset in a dvector array doesn't make sense to me.
who said is a an offset to a dVector? it is a face attribute specified by the user.

What is the face adjacent index? I don't understand how to calculate this.
a triangle has three edges, each edge is part of another triangle, the adjacent normal is the index into the face normal of the adjacent triangle. if the triangle does not share an edge with another triangle, you can set the corresponding index to its own normal.

How is the face area stored? Is this a float value stored in the vertex array? Why does your example just use an indice of 0? I don't see the triangle area being calculated anywhere.
I use zero for simplicity. that's not an area, it is length of the shortest edge of the face rounded to the nearest integer. this is used to decide if the collision may produce degenerated results.
you can just measure the size of your faces and determine a representative value to use for everything in the call. do not use zero because using zero is telling the engine that the triangle is very small and will use the more expensive routines.
for example if you know that your faces are on average 1.5 meter x 1.5 meter you can save 2 or 1
either value is a good stimate. saving zero make that all relative pair comparison are much large that zero and result on expensive contact calculation.

I don't see anywhere in the code where vertex info is being set in the m_collisionVertex array?
no, the vertex are suppose to be stored in pointer m_vertex, this is a pointer that you pass in, but you keep the data in your own array, look at struct NewtonUserMeshCollisionCollideDesc

[pHySiQuE]

Awesome, I have it sort of working now. I still have a lot of optimization work to do.

In the future, an instance cloud collision type might be a good idea. This would work by providing an AABB to the callback, which would return an array of 4x4 matrices and scales for all intersecting instances. This would avoid the rather expensive step of dynamically building a mesh out of multiple instances.

Here is my callback. It works by getting all instances in the area and building a mesh from them:

Code: Select all

void VegetationLayer::CollideCallback(NewtonUserMeshCollisionCollideDesc* const collideDescData, const void* const continueCollisionHandle)
{
   collideDescData->m_faceCount = 0;
   collideDescData->m_vertexStrideInBytes = 3 * sizeof(float);

   //Get the vegetation layer object
   VegetationLayer* layer = (VegetationLayer*)collideDescData->m_userData;
   if (layer->instanceshape == NULL) return;
      
   //Calculate an AABB
   AABB aabb = AABB(collideDescData->m_boxP0[0], collideDescData->m_boxP0[1], collideDescData->m_boxP0[2], collideDescData->m_boxP1[0], collideDescData->m_boxP1[1], collideDescData->m_boxP1[2]);
      
   //List to receive all intersecting instance 4x4 matrices
   std::vector<Mat4> instances;

   //Retrieve all intersecting instances
   int count = layer->GetInstancesInAABB(aabb, instances);
   if (count == 0) return;

   //Get current thread ID
   int threadNumber = collideDescData->m_threadNumber;

   //For each intersecting instance, add that info to the collision data
   Surface* collisionsurface = layer->instanceshape->GetSurface(0);
   layer->collisionsurfaceindicecounts[threadNumber].resize(0);
   layer->collisionsurfaceindices[threadNumber].resize(0);
   layer->collisionsurfacevertices[threadNumber].resize(0);
   
   //Temporary integer array for indices
   std::vector<int> indices;
   indices.resize(collisionsurface->CountTriangles() * 9);
   for (int n = 0; n < collisionsurface->CountTriangles(); n++)
   {
      //Triangle vertex
      indices[n * 9 + 0] = collisionsurface->GetTriangleVertex(n, 0);
      indices[n * 9 + 1] = collisionsurface->GetTriangleVertex(n, 1);
      indices[n * 9 + 2] = collisionsurface->GetTriangleVertex(n, 2);

      //Face attribute
      indices[n * 9 + 3] = 0;

      //Face normal
      indices[n * 9 + 4] = collisionsurface->CountVertices() + n;

      // face adjacent index (infinite plane does not have shared edge with other faces)
      indices[n * 9 + 5] = indices[n * 9 + 4];
      indices[n * 9 + 6] = indices[n * 9 + 4];
      indices[n * 9 + 7] = indices[n * 9 + 4];

      // face area (the plane is clipped around the box, the face size is always optimal)
      indices[n * 9 + 8] = 1;
   }

   Vec3 pos;
   int sz;
   Mat4 identity;
   int indice_offset;

   //Collate all intersecting instances into vertex / indice arrays
   for (int n = 0; n < count; n++)
   {
      collideDescData->m_faceCount += collisionsurface->CountTriangles();
      
      //Transform and add vertices
      sz = layer->collisionsurfacevertices[threadNumber].size();
      layer->collisionsurfacevertices[threadNumber].resize(sz + collisionsurface->CountVertices() * 3);
      for (int p = 0; p < collisionsurface->CountVertices(); p++)
      {
         pos = collisionsurface->GetVertexPosition(p);
         pos = Transform::Point(pos,instances[n],identity);
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 0] = pos.x;
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 1] = pos.y;
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 2] = pos.z;
      }

      //Transform and add normals
      sz = layer->collisionsurfacevertices[threadNumber].size();
      layer->collisionsurfacevertices[threadNumber].resize(sz + collisionsurface->CountTriangles() * 3);
      for (int p = 0; p < collisionsurface->CountTriangles(); p++)
      {
         pos = collisionsurface->GetTriangleNormal(p);
         pos = Transform::Normal(pos, instances[n], identity);
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 0] = pos.x;
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 1] = pos.y;
         layer->collisionsurfacevertices[threadNumber][sz + p * 3 + 2] = pos.z;
      }
      
      //Add indices
      sz = layer->collisionsurfaceindices[threadNumber].size();
      layer->collisionsurfaceindices[threadNumber].resize(sz + indices.size());
      memcpy(&layer->collisionsurfaceindices[threadNumber][sz], &indices[0], indices.size() * sizeof(int));

      //Add indice offset
      indice_offset = n * (collisionsurface->CountVertices() + collisionsurface->CountTriangles());
      for (int p = 0; p < collisionsurface->CountTriangles(); p++)
      {
         layer->collisionsurfaceindices[threadNumber][sz + p * 9 + 0] += indice_offset;
         layer->collisionsurfaceindices[threadNumber][sz + p * 9 + 1] += indice_offset;
         layer->collisionsurfaceindices[threadNumber][sz + p * 9 + 2] += indice_offset;
         layer->collisionsurfaceindices[threadNumber][sz + p * 9 + 4] += indice_offset;
         layer->collisionsurfaceindices[threadNumber][sz + p * 9 + 5] += indice_offset;
         layer->collisionsurfaceindices[threadNumber][sz + p * 9 + 6] += indice_offset;
         layer->collisionsurfaceindices[threadNumber][sz + p * 9 + 7] += indice_offset;
      }
   }

   //Fill face indice counts with '3' (triangles)
   layer->collisionsurfaceindicecounts[threadNumber].resize(collisionsurface->CountTriangles()*count);
   std::fill(layer->collisionsurfaceindicecounts[threadNumber].begin(), layer->collisionsurfaceindicecounts[threadNumber].end(), 3);
   
   Debug::Assert(layer->collisionsurfaceindicecounts[threadNumber].size() == collisionsurface->CountTriangles()*count);
   Debug::Assert(layer->collisionsurfaceindices[threadNumber].size() == collisionsurface->CountTriangles()*count*9);
   Debug::Assert(layer->collisionsurfacevertices[threadNumber].size() == (collisionsurface->CountVertices() + collisionsurface->CountTriangles()) * 3 * count);

   //Set collisioninfo array pointers
   collideDescData->m_faceIndexCount = &layer->collisionsurfaceindicecounts[threadNumber][0];
   collideDescData->m_faceVertexIndex = &layer->collisionsurfaceindices[threadNumber][0];
   collideDescData->m_vertex = &layer->collisionsurfacevertices[threadNumber][0];
}

[pHySiQuE]

I've got it working perfectly now, and with my optimizations it's pretty fast. Thank you for your assistance!
http://www.leadwerks.com/werkspace/blog ... n-physics/

Now that I understand how this works, I can also use it for custom terrain collisions.

[pHySiQuE]

Here is a demo you can try that shows it working:
http://www.leadwerks.com/werkspace/blog ... tion-demo/

[pHySiQuE]

[Julio Jerez]

Very cool, can you try making the big borders breakable? that will give your users a high end gimmick, and it is very easy and I believe fix well with the procedural placement theme.

I can see the appeal of not using memory, but here is a question. why are you so concerned with it when memory is the cheapest resource on a computer today?
doesn't the procedural placement make to that the final map become too repetitive?

[pHySiQuE]

The data can get quite big, and it doesn't scale well for my future plans of 64-bit landscapes.

[pHySiQuE]

Working very nicely now. A 1024x1024 terrain only requires 6 mb of memory.
2 bytes: height
4 bytes: 16 vegetation layers + 16 texture layers.

It's crazy that none of the vegetation objects are actually persistent in memory. I'd like to make the terrain use a similar design so it can just exist everywhere, at any given point in space.