Certain convex hulls in Q3BSP don't collide

[Julio Jerez]

There are things that are not worth pursuing because see the solution can be unpractical, the case that you had is the first that I know in all of people how had used the library,
by making the CRC a 64 value the chance of that bug happen again is reduced by a factor of 4 billion.

The reason I had that 64 bit CRC code, was precisely that I used it for my file format and there I did had those collisions, by since the change to 64 bit I had not had that event occurring again.
for me spending so much time and effort on an event with such low probability is a waste of time, and even if is was fixed, the problem may not even ever happen again on my life time or yours.

one way to solve solved it problem in a simple way that saving tow CRC or the same key, generate by some permutation of the same input data.

for example: say the key is the word: ABCDEF and the CRC is 1234, you save the CRC and also a CRC of some permutation of the KEY say ACEBDF
the another Key will have to have but key matching the second key, and I believe that the will reduce the change even more that the switching to a CRC64


you are welcome to implement your own solution if you want, but like I say that say a futile effort that generates no real benefit.

[Julio Jerez]

ok I am adding the pat that store a key signature in the cache the code now will look like this

Code: Select all

dgCollisionInstance* dgWorld::CreateConvexHull (dgInt32 count, const dgFloat32* const vertexArray, dgInt32 strideInBytes, dgFloat32 tolerance, dgInt32 shapeID, const dgMatrix& offsetMatrix)
{
   dgUnsigned32 signature = dgCollisionConvexHull::CalculateSecundSignature (count, vertexArray, strideInBytes);

   dgUnsigned32 crc = dgCollisionConvexHull::CalculateSignature (count, vertexArray, strideInBytes);
   dgBodyCollisionList::dgTreeNode* node = dgBodyCollisionList::Find (crc);
   if (!node) {
      // shape not found create a new one and add to the cache
      dgCollisionConvexHull* const collision = new (m_allocator) dgCollisionConvexHull (m_allocator, crc, count, strideInBytes, tolerance, vertexArray);
      if (collision->GetConvexVertexCount()) {
         node = dgBodyCollisionList::Insert (CollisionKeyPair(collision, signature), crc);
      } else {
         //most likely the point cloud is a plane or a line
         //could not make the shape destroy the shell and return NULL
         //note this is the only newton shape that can return NULL;
         collision->Release();
         return NULL;
      }
   }

   if (node->GetInfo().m_validateKey != signature) {
      // shape was found but it i sa CRC collision simple single out this shape as a unique entry in the cache
      dgTrace (("we have a CRC collision simple single out this shape as a unique entry in the cache\n"));
      dgCollisionConvexHull* const collision = new (m_allocator) dgCollisionConvexHull (m_allocator, signature, count, strideInBytes, tolerance, vertexArray);
      if (collision->GetConvexVertexCount()) {
         node = dgBodyCollisionList::Insert (CollisionKeyPair(collision, signature), signature);
      } else {
         //most likely the point cloud is a plane or a line
         //could not make the shape destroy the shell and return NULL
         //note this is the only newton shape that can return NULL;
         collision->Release();
         return NULL;
      }
   }

   // add reference to the shape and return the collision pointer
   return CreateInstance (node->GetInfo().m_collision, shapeID, offsetMatrix);
}

and the cache is modified like this

Code: Select all

class CollisionKeyPair
{
   public:
   CollisionKeyPair(const dgCollision* collision, dgUnsigned32 pinNumber)
      :m_collision(collision)
      ,m_pinNumber(pinNumber)
   {
   }
   const dgCollision* m_collision;
   dgUnsigned32 m_pinNumber;
};

class dgBodyCollisionList: public dgTree<CollisionKeyPair, dgUnsigned32>
{
   public:
   dgBodyCollisionList (dgMemoryAllocator* const allocator)
      :dgTree<CollisionKeyPair, dgUnsigned32>(allocator)
   {
   }
};

this is similar to the pin system that is used by banks, where each card customer has a card number, by the customer also has a pin number
to get a valid hit the card number and the pin number must match.

the pin is generated by a permutation of the data use to produce the CRC, so fo the purist, It is possible that the CRC and the pin number generate the value for different sequence of numbers,
by I will imagine the change of that happen in is of the order of product of the probability of each CRC with is around the order is (1/2^ 32 ) * (1/2^ 32 )

put is another way, for a bank it is possible that a person who still a credit card or a back can guess the pin number, but the change of that is so low that back do use that system all around the world.
I will check this in in a moment instead of the CRC64.

[Julio Jerez]

ok if you sync to svn now the code usen a CRC and a pin number, this soul be very\, very robust now.

I hope this work for you.