Tree Collision, Continuous Collision, Winding Order

Report any bugs here and we'll post fixes

Moderators: Sascha Willems, Thomas

Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Fri May 13, 2016 4:57 am

Hi

I have discovered a possible bug in the continuous collision detection. Quite often the boxes you shoot will pass through.

To reproduce replace the following function in ContinueCollision1.cpp in DemosSandbox, and then just rotate the camera around and shoot at different parts of the wall. >50% of the time the boxes pass through the wall.

The wall is just one simple quad.

Code: Select all
static NewtonBody* CreateBackgroundWallsAndCellingBody(NewtonWorld* world)
{
   // ******Added*********
   dFloat wall_tris[6][3] =
   {
      {  100, 0, 0 },
      { -100, 0, 0 },      
      { -100, 100, 0 },

      { -100, 100, 0 },
      {  100, 100, 0 },
      {  100, 0, 0 },
   };
   // ******Added*********
   dFloat wall_quad[4][3] =
   {
      { -100, 0, 0 },
      {  100, 0, 0 },
      {  100, 100, 0 },
      { -100, 100, 0 },
   };

   // crate a collision tree
   NewtonCollision* const collision = NewtonCreateTreeCollision(world, 0);

   // start building the collision mesh
   NewtonTreeCollisionBeginBuild(collision);

   // add the face one at a time
   /*NewtonTreeCollisionAddFace(collision, 4, &floor[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 4, &wall_N[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 4, &wall_W[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 4, &wall_S[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 4, &wall_E[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 4, &celling[0][0], 3 * sizeof (dFloat), 0);*/
   
   // ******Added*********
   NewtonTreeCollisionAddFace(collision, 4, &wall_quad[0][0], 3 * sizeof (dFloat), 0);
   
   /*NewtonTreeCollisionAddFace(collision, 3, &wall_tris[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 3, &wall_tris[3][0], 3 * sizeof (dFloat), 0);*/

   // finish building the collision
   NewtonTreeCollisionEndBuild(collision, 1);

   // create a body with a collision and locate at the identity matrix position
   dMatrix matrix(dGetIdentityMatrix());
   NewtonBody* const body = NewtonCreateDynamicBody(world, collision, &matrix[0][0]);

   // do no forget to destroy the collision after you not longer need it
   NewtonDestroyCollision(collision);
   return body;
}


The effect is the same when I add triangles instead of a quad.

Then I also noticed that no collisions occur at all from the other side of the wall. Is this intended behaviour? i.e. should they only collide on one side?

Thanks

James
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby Julio Jerez » Fri May 13, 2016 7:46 am

are you saying that is you change the box form quad to triangles that CCD fail at a 50% rate?

I just tried the demo as it is and not a single box fail the demos,

then I replace the box with you polygon, and the collision fail, but that's because you only added on plane, at the same location that the camera is, so the chances that you will shoot the positive side or negative side of the plane is 50%. And yes that will fail is you should to the side.
because yes collision with polygons in newton are single side, and there not option to change that

I do not know what this test is suppose to show.
try place the polygon away from the eyepoint, and facing the camera. it should always hit it
Julio Jerez
Moderator
Moderator
 
Posts: 11039
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Fri May 13, 2016 8:04 am

Hi Julio

Thanks for the prompt reply.

jamesm6162 wrote:are you saying that is you change the box form quad to triangles that CCD fail at a 50% rate?

No, both the quad and triangles do the same.

jamesm6162 wrote:but that's because you only added on plane, at the same location that the camera is

Yes I added one plane only, but I moved the camera away before shooting the boxes... So that shouldn't be the problem.
But using this data where they are moved away from the camera has the same problem (Both polygons are facing the camera):

Code: Select all
// ******Added*********
   dFloat wall_tris[6][3] =
   {
      { -100, 0,    -100 },
      {  100, 0,    -100 },            
      { -100, 100, -100 },

      { -100, 100, -100 },      
      {  100, 0,   -100 },
      {  100, 100, -100 },
   };
   // ******Added*********
   dFloat wall_quad[4][3] =
   {
      { -100, 0,   -100 },
      {  100, 0,   -100 },
      {  100, 100, -100 },
      { -100, 100, -100 },
   };


I have no idea why the default demo works, but my plane does not.
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Fri May 13, 2016 8:13 am

In fact if you use the original demo, and remove all the walls except the one (e.g. south wall) the same issue occurs:

Code: Select all
    // add the face one at a time
   //NewtonTreeCollisionAddFace(collision, 4, &floor[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &wall_N[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &wall_W[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 4, &wall_S[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &wall_E[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &celling[0][0], 3 * sizeof (dFloat), 0);
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby Julio Jerez » Fri May 13, 2016 8:28 am

Ok I change the face position in you test, and the the polygon is away from the camera
the quad winding was face away, so I reordered.
Code: Select all
   // ******Added*********
   dFloat wall_tris[6][3] =
   {
      {  100, 0, 100 },
      { -100, 0, 100 },     
      { -100, 100, 100 },

      { -100, 100, 100 },
     {  100, 100, 100 },
      {  100, 0, 100 },
    
   };
   // ******Added*********
   dFloat wall_quad[4][3] =
   {
      { -100, 0, 100 },
     { -100, 100, 100 },
      {  100, 100, 100 },
      {  100, 0, 100 },
   };


yes there was a bug is the CCD test trivial rejection, is fix now
please sync and try again
Julio Jerez
Moderator
Moderator
 
Posts: 11039
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Fri May 13, 2016 9:27 am

Thanks Julio

It is much better now.

I do however still get about 1/1000 chance miss, but I'm not sure why as it's difficult to reproduce. It mainly happens closer to the sides of the plane.
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby Julio Jerez » Fri May 13, 2016 9:34 am

It should work 100% of the time.

try to add a dTrace line to log the position and velocity each time you fire. and when the bug happens, the get the data from the output window, and replace the initialization of the projectile to that data, and it should reproduce the bug each time.
I use that trick to debug hard to find bugs.

also, see if you can do with the quad first, but to increase the change of misses
use the triangles and do no optimize the mesh, this will add more edges.
Julio Jerez
Moderator
Moderator
 
Posts: 11039
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Mon May 16, 2016 3:47 am

Hi Julio

I tried the trace and got a failure case that consistently misses.

Use the following setup:

Code: Select all
NewtonTreeCollisionBeginBuild(collision);

   // add the face one at a time
   //NewtonTreeCollisionAddFace(collision, 4, &floor[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &wall_N[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &wall_W[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 4, &wall_S[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &wall_E[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 4, &celling[0][0], 3 * sizeof (dFloat), 0);

   //NewtonTreeCollisionAddFace(collision, 3, &wall_tris[0][0], 3 * sizeof (dFloat), 0);
   //NewtonTreeCollisionAddFace(collision, 3, &wall_tris[3][0], 3 * sizeof (dFloat), 0);
   // finish building the collision
   NewtonTreeCollisionEndBuild(collision, 1);


And this position and velocity to fire the box:

Code: Select all
dVector Pos(9.010377,52.781680,-22.977158);
dVector Vel(628.279440,-59.964005,-775.673426);


This is in debug_double configuration BTW

Thanks
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby Julio Jerez » Mon May 16, 2016 8:47 am

indeed it reproduces the bug.

I now see what it is the problem. I is a numerical precision with 32 bit floats,
the velocity of the body is over 1000 unit per second, to put it is perspective this over three times the speed of sound.

the speed uses a 4 out of the 7 digits of the dynamic strange of a float, leaving only three digits for calculation that project relative velocities over normal vectors and numerical errors creeps in a lot.

The bug happen when the body move by almost the same distance than the time step,
at that point the CCD step says than it can take the step.
The next frame say this objet is too close to the wall, but in reality is very close but not touching it, so contact report no contacts letting the body take a small step, but at 1000 mps, a small step is bigger than the small box size and the box passes thought the wall.

I made a change to fix that, however if the velocity is increased even more, that the is not way It can be solved with 32 floats , there is just not enough precision.

Please sync and see if it is better.

if it still happens, I can make so that base if the magnitude of the speed it choses, the double version path.
Julio Jerez
Moderator
Moderator
 
Posts: 11039
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Mon May 16, 2016 9:47 am

Thanks it seems 100% now.

I won't be needing that much velocity anyway.

Just for interest sake, the precision will be better in double precision mode, right? So theoretically you can have higher velocities there?
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby Julio Jerez » Mon May 16, 2016 10:25 am

jamesm6162 wrote:Just for interest sake, the precision will be better in double precision mode, right? So theoretically you can have higher velocities there?


the answer is complicated. it is yes and it is no.

yes because all the collision calculation will have 17 digits of dynamic range precision,
no because the dynamics part still use a second order integrator, so as the velocity is faster and faster that are still integration error that the only way to reduce them is by taking a shorter step.
This is specially true for objects with high inertia aspect ration, like a thin rod.

all in all is by far much better in double yes
Julio Jerez
Moderator
Moderator
 
Posts: 11039
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Tue May 17, 2016 8:06 am

Hi Julio

Ok. I've run into another precision issue with the CCD, but I think this one is totally fixable.
As I tested in my own application I kept getting misses. Long story short, eventually I found that my box collision is specified with 0.2, 0.2, 0.2, and in DemoSandbox it was 0.2f, 0.2f, 0.2f. And that made the difference...

To reproduce:

1.) Set MAX_PHYSICS_FPS to 60 in DemoEntityManager
Code: Select all
//#define MAX_PHYSICS_FPS            120.0f
#define MAX_PHYSICS_FPS         60.0f


2.) Change the size and speed of the box collision fired in ContinueCollision1.cpp.
NB: Use doubles to define the size, not floats (0.2 vs 0.2f)
Code: Select all
static void FireNewtonCcdBox(NewtonWorld* world, const dVector & postion, const dVector & velocity)
{
   //NewtonCollision* collision = NewtonCreateBox(world, 1.0f, 1.0f, 1.0f, 0, NULL);
   NewtonCollision* collision = NewtonCreateBox(world, 0.2, 0.2, 0.2, 0, NULL);

...
   dFloat ammo_vel = 200.0f;
   dVector vel(dir.m_x*ammo_vel, dir.m_y*ammo_vel, dir.m_z*ammo_vel);


   // These will definitely miss, but almost any shot misses
   pos = dVector(4.00094,11.7184,-23.0402);
   vel = dVector(63.7135,1.95944,189.57);
   FireNewtonCcdBox(m_scene->GetNewton(), pos, vel);


3.) Use the following plane:
Code: Select all
   dFloat tris[6][3] = {
      {20,0,20}, {-20,0,20}, {-20,20,20},
      {20,0,20}, {-20,20,20}, {20,20,20}
   };
   NewtonTreeCollisionAddFace(collision, 3, &tris[0][0], 3 * sizeof (dFloat), 0);
   NewtonTreeCollisionAddFace(collision, 3, &tris[3][0], 3 * sizeof (dFloat), 0);

   // finish building the collision
   NewtonTreeCollisionEndBuild(collision, 0);


4.) Move the camera down so you can see better:
Code: Select all
   dVector pos(0.0f);

   pos.m_x = 0.0f;
   pos.m_y = 10.0f;
   pos.m_z = 0.0f;

   //dQuaternion rot(dVector(1.f,0.f,0.f),(dFloat)M_PI/4.0f);
   dQuaternion rot;//(dVector(0.f,0.f,0.f),(dFloat)M_PI/4.0f);
   scene->SetCameraMatrix(rot, pos);


5.) Compile debug_double configuration.

So now pressing R will fire the preset box, that should pass through the wall. You can even use any shooting direction at only 200 velocity and most will miss.

The problem line that I found was in dgCollisionConvexPolygon.cpp:554:
Code: Select all
   dgFloat32 penetration = (m_localPoly[0] - p0) % m_normal + proxy.m_skinThickness;
   if (penetration < dgFloat32(0.0f)) {
      return 0;
   }


The penetration value is very small -1.xxxe-14, which is pretty much zero but not quite and is less than 0, so the function returns no hit. This happens because of a very small precision difference between m_localPoly[0] and p0.

When you specify the size of the CCD box as 0.2f then penetration is exactly 0.f, but when you specify it as double '0.2' then you get the issue where some precision error creeps in.

Not sure why, my math isn't the best.

Regards

James
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby Julio Jerez » Tue May 17, 2016 10:25 am

wow,
Code: Select all
this collide
NewtonCollision* collision = NewtonCreateBox(world, 0.2f, 0.2f, 0.2f, 0, NULL); collide

this fail:
NewtonCollision* collision = NewtonCreateBox(world, 0.2f, 0.2f, 0.2f, 0, NULL); collide

how's that for a dramatic demonstration of numerical rounding errors in action.

The thing is that this happen even with double, this mean that I need to add some tolerance on that check, but is not that simple because the function is used for both CCD and discrete collision.

It is time to fix that by using some small tolerance, instead of an absolute zero.
I think is fixed now.

Please try again.
Julio Jerez
Moderator
Moderator
 
Posts: 11039
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Tree Collision, Continuous Collision, Winding Order

Postby jamesm6162 » Wed May 18, 2016 4:11 am

That's exactly what I thought. It took my half a day to find that that was the problem.

Anyway.

I tested again and there is still one case where the box goes through:

If you use triangles and not a quad, as in my test case I gave you above, and you fire the box exactly on the edge between the two triangles then the box still goes through.

To reproduce, use the same setup as I gave you, but use this pos and vel:

Code: Select all
vel = dVector(-41.502968015776617, -7.9978666586559308, 195.48283242983715);
pos = dVector(-0.081704197890863042, 12.346892172724450, 3.9671033511450151);


Again, still in debug_double config.

Thanks for all the help, and apologies for being a pain

James
jamesm6162
 
Posts: 49
Joined: Wed Aug 12, 2015 8:50 am

Re: Tree Collision, Continuous Collision, Winding Order

Postby Julio Jerez » Wed May 18, 2016 8:26 am

oh not problem, the made the code more robust.
In fact the kind of test is what make physics engine reliable and robust.
This is in fact t the dirty little secret of engine like PhysX and Havoc, the get better not better the people how write it, the people who write are no more qualifies that any one else.
we all more less have the same more or less academic qualification.
what make those engine better is the a staff of programmers fixing thousand box reported by customer support.

QA is one of the more powerful tool to polish the engine. In the case of Newton I am eh only person
how work on it, and this is why I give priority to these bugs because do not have QA.

Anyway, yes that was another case.
it is here, file: ..\coreLibrary_300\source\physics\dgContactSolver.cpp, line 2012

if (penetration < dgFloat32(0.0)) {

it should have a tolerance, so that is calculate contact when the object are touching by not interpenetrating
if (penetration <= dgFloat32(1.0e-5f)) {

if the object travel exactly the time step. then the distance between the two is zero.
so the do no collide and there should be able to more freely, however at 200 mps, then small step is really large. In the case the penetration is again
penetration 1.4155343563970746e-015 double

a small step advance the body by more than 0.2 units.

I change the test, But I am no sure is this is the correct solution. because declare contact will now declare collision for bodies that are touching but no colliding.
Maybe the best solution is the make the small step a function of the relative velocity, but that a more complex solution that the simple tolerance test.

please sync an test it again. I will check that is does no break static collision.
Julio Jerez
Moderator
Moderator
 
Posts: 11039
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Next

Return to Bugs and Fixes

Who is online

Users browsing this forum: No registered users and 1 guest

cron