Certain convex hulls in Q3BSP don't collide

A place to discuss everything related to Newton Dynamics.

Moderators: Sascha Willems, walaber

Certain convex hulls in Q3BSP don't collide

Postby Downsider » Fri Sep 27, 2013 4:59 pm

Hi,

I ported some code from Bullet in an effort to make Q3BSP work well in Newton, because right now the only available examples use the mesh structure instead of the underlying true collision structure in the BSP. The difference between the two is pretty evident where one is simplified and composed of convex brushes while the other one is arranged in a way that is efficient for rendering rather than collision and also may contain structures that the scene does not necessarily want to collide against, with no real way to detect and strip them out.

Quake 3 BSP's describe the convex collision shapes as a series of planes and distances, where the interior of the planes is the collision shape. By taking the intersections of these planes you can generate point data that Newton can take to create a convex hull.

This code works for all the brushes in my scene, with the exception of 3. During my debugging process, I decided to try building only one convex hull, this time for brush #69, which is one of the problem brushes. When I ONLY built that one brush, collision worked against that one brush. However, when I continue to build the rest of the brushes as convex hulls, it fails to detect collisions against that brush.

Any ideas? Is there a problem with Newton's implementation of convex hull collision?

Code: Select all
static bool isPointInsidePlanes(std::vector<glm::vec4> equations, glm::vec3 point, float margin)
{
   int numbrushes = equations.size();
   for (int i=0;i<numbrushes;i++)
   {
      const glm::vec3 n1 = glm::vec3(equations[i]);
      float dist = glm::dot(n1, point) + equations[i].w - margin;
      if (dist > 0.f)
         return false;
   }

   return true;
}

static std::vector<glm::vec3> createPointCloudFromPlaneEquations(std::vector<glm::vec4> equations)
{
   std::vector<glm::vec3> vertOut;
   const int numbrushes = equations.size();

   for (int i=0;i<numbrushes;i++)
   {
      const glm::vec3& n1 = glm::vec3(equations[i]);

      for (int j=i+1;j<numbrushes;j++)
      {
         const glm::vec3& n2 = glm::vec3(equations[j]);
         
         for (int k=j+1;k<numbrushes;k++)
         {
            const glm::vec3& n3 = glm::vec3(equations[k]);

            glm::vec3 n2n3; n2n3 = glm::cross(n2, n3);
            glm::vec3 n3n1; n3n1 = glm::cross(n3, n1);
            glm::vec3 n1n2; n1n2 = glm::cross(n1, n2);

            if ( (n2n3.length() * n2n3.length() > 0.0001) &&
                  (n3n1.length() * n3n1.length() > 0.0001) &&
                  (n1n2.length() * n1n2.length() > 0.0001) )
            {
               float quotient = glm::dot(n1, n2n3);

               if (fabs(quotient) > 0.000001)
               {
                  quotient = -1.f / quotient;
                  n2n3 *= equations[i].w;
                  n3n1 *= equations[j].w;
                  n1n2 *= equations[k].w;

                  glm::vec3 potentialVertex = n2n3;
                  potentialVertex += n3n1;
                  potentialVertex += n1n2;
                  potentialVertex *= quotient;
                  
                  if (isPointInsidePlanes(equations, potentialVertex, 0.01f))
                     vertOut.push_back(potentialVertex);
               }
            }
         }
      }
   }

   return vertOut;
}

void CPhysicsWorld::addBrush(CWorld* world, q3bsp_lump_brushes& brush)
{
   std::vector<glm::vec4> planeEquations;

   bool isValidBrush = false;

   for (int i=0;i<brush.n_brushsides;i++)
   {
      q3bsp_lump_brushsides& brushside = world->brushsides[brush.brushside + i];
      q3bsp_lump_planes& plane = world->planes[brushside.plane];

      glm::vec4 planeEq(plane.normal[0], plane.normal[1], plane.normal[2], -plane.dist);

      planeEquations.push_back(planeEq);

      isValidBrush = true;
   }

   if (isValidBrush)
   {
      std::vector<glm::vec3> pointCloud = createPointCloudFromPlaneEquations(planeEquations);
      
      dMatrix identity = GetIdentityMatrix();

      NewtonCollision* hull = NewtonCreateConvexHull(_physWorld, pointCloud.size(), &pointCloud[0][0], sizeof(float) * 3, 0.0f, NULL, NULL);
      NewtonCreateKinematicBody(_physWorld, hull, &identity[0][0]);
   }
}
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Julio Jerez » Fri Sep 27, 2013 5:57 pm

The problem is tahet you are try to use newton as if ir was a different Physic engine.
In Newton Kinematic bodies do not collide teh way you are epcting

I sugestion is that you make a compound. then add all of the brushes to that compound as child shapes.
The make a dynamic bodie with zeor mass, and pass the compound collision as the collision shape. It should work perfect and very efficiently.

you could also make a scene collision instead of a compound, Scene collision are static compound,
therefore they can take not just convex hulls as children, but also all other shapes, terrain, collision tree, or othe compounds.

on this line
NewtonCollision* hull = NewtonCreateConvexHull(_physWorld, pointCloud.size(), &pointCloud[0][0], sizeof(float) * 3, 0.0f, NULL, NULL);

if a point cloud is degenerated then hull will be NULL, the rarelly happens, but I know that some quake files do allow for quasy convex shapes.
the do lot of fudging floats to fake convexity, while in Netwon convexes are exact, Newton uses extended presitinn integer arithmetic to create perfect hulls.
check if a that funtion ever return NULL. if ti is the it means that point cloud is degenerated, probably a flat plane or a line, threfore not collidable. you can simple skip it.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Fri Sep 27, 2013 6:46 pm

That function has never returned NULL in my test map.

Can you think of any reason why the problem brush I'm talking about would fail to work, but works when it's the only convex hull I add to the scene?

I'm also not putting any other dynamic bodies in the scene, I'm only raytesting right now, so kinematic bodies should still generate a ray hit. I don't expect the kinematic body to behave properly with dynamic bodies. I've read the docs, kinematic bodies is what I want, but they're not responding to the ray test properly,

EDIT:
I now push them into a compound shape and submit them as a single collision object, but it still doesn't work.
Last edited by Downsider on Fri Sep 27, 2013 7:10 pm, edited 1 time in total.
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Julio Jerez » Fri Sep 27, 2013 7:05 pm

It shoul never fail. what version of newton are you using?
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Fri Sep 27, 2013 7:10 pm

Julio Jerez wrote:It shoul never fail. what version of newton are you using?


SVN version from no less than a week ago, built for Android.
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Fri Sep 27, 2013 7:35 pm

I hacked the CRC calculation and caching mechanism disabled to see if that would fix it:

Code: Select all
dgCollisionInstance* dgWorld::CreateConvexHull (dgInt32 count, const dgFloat32* const vertexArray, dgInt32 strideInBytes, dgFloat32 tolerance, dgInt32 shapeID, const dgMatrix& offsetMatrix)
{
   dgUnsigned32 crc = rand();//dgCollisionConvexHull::CalculateSignature (count, vertexArray, strideInBytes);
   dgBodyCollisionList::dgTreeNode* node = 0; //= dgBodyCollisionList::Find (crc);
   if (!node) {
      // shape not found crate 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 (collision, crc);
      } else {
         // MOST LIKELLY TEH POINT CLOUD IS A STRIGH LINE OF A SINGLE POINT
         //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(), shapeID, offsetMatrix);
}


When I "disabled" the caching mechanism through that hack, the problem disappeared. Is this only broken because of something platform specific to Android or is the caching mechanism not completely implemented yet in the SVN version of Newton? Or has nobody seriously encountered this before?
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Julio Jerez » Fri Sep 27, 2013 7:58 pm

with the expection of the dgMatha class, whi I only impemnetd simd for intel CPUs The is not platform specific code in entiree engine.
I can not imagine why the cach will generate an error like that,

basically by using dgUnsigned32 crc = rand() is invalidating the cache
you are making a full instance for each convex.
but since these convexes that you are passing are unique to begidn with, the cache was not doing anything anyway.
my guess is that maybe there is a broken dgMath function that work fine on x87 simd and busted in scalar float.
and the cache is finding duplacte for diffrents entries.

can you check if dgCollisionConvexHull::CalculateSignature (count, vertexArray, strideInBytes); returns zero or the same value every time
if this is the case then I think I know what could be.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Certain convex hulls in Q3BSP don't collide

Postby Julio Jerez » Fri Sep 27, 2013 8:15 pm

There is one secund posibility, that is that CRC code is not 100% safe.

CRC may negerates collision, That probability of that is very very low, and you will be the one preson that came across that bug.

about 12 years ago I had a simular bug with using CRC to cache texture names for a game called Battlezone.
The Game was working fine every time, but when it was about to submit a candidate release, an artist changed a texture name of an asset, and
that texture started show on the Terrain. I took me a whole weekend with no sleep to figure out what was wrong.
when I found it I could not believe it, but is was true, so I wrote a test program to generate 5 leters words for the entire alphebet and saving the CRC code on a map,
and I could not believe how frequent the CRC was generating the same code for different names. I had about one collision every 10000 words

This is why I made the CRC 64, but I never ported to the lower lever core engine, maybe this is a good time for that.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Fri Sep 27, 2013 8:22 pm

When I get a chance later tonight I'll make an array that stores both of all the generated CRC's and their respective vertices. Then I'll iterate over and see if there's any duplicate CRC's that don't have the same verts.

I appreciate all your help and insight :wink: I really want to use Newton.

EDIT:
As a second thought, even if there is a CRC collision, shouldn't it then start iterating over a linked list or array of those objects with the same CRC to determine if it's legitimately the same object or not?
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Fri Sep 27, 2013 11:41 pm

Yep. It's a CRC collision that isn't a true match.

Image
Image

crcTests and vertexTests are parallel arrays that hold the CRC and vertices for each mesh. There are a LOT of collisions. Very many. About 14 in a simple test scene with 105 total convex meshes.

Am I seriously the first person to have this problem? Seems pretty major. I guess nobody uses convex shapes? Maybe at the risk of finding more fundamental issues I should switch to trimeshes or to Bullet :P which I don't want to do, by the way.

I think the best solution is to iterate over all the bodies with the same CRC, comparing vertices, and see if there's a true collision or if it's fake. It'll add some time complexity because you don't have the nice CRC but it will be for very few meshes.
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Julio Jerez » Sat Sep 28, 2013 12:13 am

No, the CRC collision is a one in probable 10 to 100 million time. You are the first person in the 10 years that the engine had being around that came a cross that problem.
I understand if you fell that the bug does not inspired you confidence, and you wan to try a different library.

Downsider wrote:crcTests and vertexTests are parallel arrays that hold the CRC and vertices for each mesh. There are a LOT of collisions. Very many. About 14 in a simple test scene with 105 total convex meshes.

not that no very many at all, There are users of newton that make SceneCollision with 100 of thousands of convex shapes, and the but has never happens.
I also use it for the voronoi convex fracture and for convex decomposition for complex shapes and generate 100 of millions of convex and that has never happened.

This is a problem that you always get when using CRC to generate Hash values. The only way to solve it is by saving the key with CRC values, but the key value for a convex hull is too large, and convex build should be very fast.
an easy solution is by calculation the way the Key is calculated. A better one is to use the CRC64 as the hash table, a CRC64 will reduce the probability of a collision by (1/2^32)

I will change the CRC to CRC64 tomorrow, meant time if you still want to use the engine, you can use the hack that disable the cache. that will make always unique convexes.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Certain convex hulls in Q3BSP don't collide

Postby Julio Jerez » Sat Sep 28, 2013 1:01 am

Ok if you synk to svn, now the code use a CRC64. The bug should not happens now.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Sat Sep 28, 2013 1:09 am

Are you saying it's not an incorrect CRC collision, or that I'm extremely unlucky? I have multiple incorrect CRC collisions with just 100 convex objects that I've verified with that piece of code..

The verts don't match, but the CRC's match, for 14 of them. Am I wrong in assuming this is the root of my problem? I counted how many times that breakpoint was hit, it's 14 times.

What I'm saying the best solution would be, because it would mean 0 incorrect collisions and very little extra CPU time (The linear search would only happen if there was a CRC collision, which is apparently a 1 in 10 million chance that I managed to hit 10% of the time..) is to have a linked list of convex hulls mapped to each CRC rather than a single convex hull. Then you can do a linear search along that linked list to see if it's a true collision or not.

That linear search would only happen when a collision occurs, and it would only occur over a linked list of elements that has the same CRC. So it should happen extremely infrequently and it will be fast because it's a small list.

Isn't that a better solution since it doesn't add much time complexity and 100% guarantees that there is 0 possibility for an incorrect collision? I believe Python uses this internally for its hashmap implementation.

Not only that, but adding things to the scene needs to be fast, but isn't extremely time-critical, it's more important that they actually work, and not leave it up to some random chance that the whole thing can blow up, no matter how small.. And apparently it's not that small for my scene..
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Sat Sep 28, 2013 1:26 am

Julio Jerez wrote:Ok if you synk to svn, now the code use a CRC64. The bug should not happens now.


Thanks. I still want to use Newton after seeing it being a robust and well put together solution in Amnesia, but not with any random chance to have the caching mechanism fail. If you're not going to implement a solution that will work all the time I'll probably just do it myself.

Thanks for all your help :)
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Re: Certain convex hulls in Q3BSP don't collide

Postby Downsider » Sat Sep 28, 2013 1:50 am

http://www.cplusplus.com/reference/map/multimap/

That's what I'm talking about. Insert with a hash, and then when two values with the same hash are inserted, it will resolve them efficiently.
Downsider
 
Posts: 9
Joined: Fri Sep 27, 2013 4:52 pm

Next

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 3 guests