Optimize Marc's Character Controller / Batching Convex Casts

[Julio Jerez]

It is not going to cast anything at all yet, I just check in the closest point code.
now I am going over convex cast, this is how the version looks like

Code: Select all

dgInt32 dgCollisionConvex::CalculateConvexCastContacts(dgCollisionParamProxy& proxy) const
{
   _ASSERTE (0);
/*
   dgVector sum;
   dgVector diff;
   dgVector dir (matrixIn.m_posit);

   dgFloat32 mag2 = dir % dir;
   if (mag2 > dgFloat32 (0.0f)) {
      dir = dir.Scale (dgRsqrt (mag2));
   } else {
      dir =  dgVector(dgFloat32 (1.0f), dgFloat32 (0.0f), dgFloat32 (0.0f), dgFloat32 (0.0f));
   }

   dgFloat32 tacc = dgFloat32 (0.0f);
   dgMatrix matrix (matrixIn);
   for (dgInt32 iter = 0; iter < DG_SEPARATION_PLANES_ITERATIONS; iter ++ ) {
      if (!SeparatingPlane (matrix, dir, convexShape)) {
         return -1;
      }

      dgFloat32 den = dir % veloc;
      if (den <= dgFloat32 (0.0f)) {
         return 0;
      }

      dgVector p (SupportVertex(dir));
      dgVector dir1 (matrix.UnrotateVector (dir.Scale (dgFloat32 (-1.0f))));
      dir1 = dir1.Scale (dgRsqrt (dir1 % dir1));
      _ASSERTE (dgAbsf(dir1 % dir1 - dgFloat32 (1.0f)) < dgFloat32 (1.0e-2f));
      dgVector q (matrix.TransformVector (convexShape->SupportVertex (dir1)));

      dgFloat32 num = dir % (q - p);
      if (num <= dgFloat32 (0.0f)) {
         dgVector step (veloc.Scale (tacc));
         matrix.m_posit = matrixIn.m_posit - step;

         dgMatrix invMatrix (invMatrixIn);
         invMatrix.m_posit = invMatrixIn.TransformVector(step);

         p = ConvexConicSupporVertex(dir);
         q = p + dir.Scale ((q - p) % dir);
         dgInt32 count = CalculateConvexConicContacts (p, q, contact, matrix, invMatrix, convexShape);
//         _ASSERTE (count);

         for (dgInt32 i = 0; i < count; i ++) {
            contact[i].m_point += step;
         }
if (iter > 1)
dgTrace (("%d\n", iter));
         timeStep = tacc;
         return count;
      }

      tacc += ((num + DG_ROBUST_PLANE_CLIP)/ den);
      _ASSERTE (tacc >= dgFloat32 (0.0f));
      if (tacc >= timeStep) {
         return 0;
      }

      matrix.m_posit = matrixIn.m_posit - veloc.Scale (tacc);
   }
*/
   return 0;
}

I am going try to check in some time today.

[Marc]

Ok. I'm looking forward to it.

[Julio Jerez]

Now I check in the complete path for convex cast.

I also refactored teh convex cast demo so that It is eassyoes to followe, and I will make so that it cast around 250 bodies on a regular mesh.
similar to the ray cast demo.

I dis that so that peoel can see hwop for exampel a Playe controller can be implemnetd on a post listener and execute all players in parallel.
however I expect the code to handle aropun 1000 general convex cast under 2 to 3 milisecunds using a single core in x87 mode.
This is a conservative estimate In reality I expect under 500 mocrosecudn or less is the cast distance is relativally small, around (2000 cast per milisecudn per cores is my target)

of cores this is after I fix the existing bugs.
The code I check in exposr a cast glich, at soem orientation, afte I fix that I will mak eteh demo to do waht I said above.

[Marc]

Ok, it doesn't look bad on my flat ground. Jumping and moving seems to work like before. Thx. Slopes and slopes aren't there so I haven't tested that.

There are some other strange things happening though. For example, from time to time I spawn physical particles that fall towards the floor and bounce a bit and roll around until they stand still and get faded away. They behave wired. When they hit the ground box, sometimes they behave correct, but 50% of the time they jump back higher then they were falling down from. some do this 3 times in a row and skyrocket away. They are ellipsoids. I replaced them with spheres scaled by the 2xx ellipsoid axis radiuses.

Another thing is when I collide with another character controller - theoretically, those are only cylinders colliding - It gets very shaky in the up down position. No idea why yet. This might be related to the new way contact filterung has to be done through the collision user data instead of shapeids. I have to check that.

To test things further, having the user collision work would really help for me.

[Julio Jerez]

Yes I thionk tshi si happening too, I beleiv I found why, I al;ready fis part of the problem and check in those functions.
but the main funtion I still need to fix sokethon else I will check int sometime tonight or tomorrow.

Bascially the newer closest distance had some few edge cases that need to be taken care, plus and I also has a but on my closest vonoi distance to a triangle function.
I already fixed that, but I need to make sure all places that the function is used, the prblem is also fixed.

I think that tomorrow I will ahve then all covered.

[Marc]

Great. I'll try it then

[Julio Jerez]

Ok I just check in teh fix, can you please try again.
there are soem lose cases still but I beleive this should show much improvement

edit: oh there is one more funtion I have to restore, if has this pathway coimmnet oput for poygom nesh'

Code: Select all

dgInt32 dgWorld::CalculateConvexToNonConvexContacts (dgCollisionParamProxy& proxy) const
{
...
...
      if (doContinueCollision) {
         _ASSERTE (0);

so casting meshes will still fail, I am fixing it now.

[Julio Jerez]

I check in teh closet distance demo where it shows 1000 convex to convex closest distance on all in one core.
The complete physics frames takes 4.1 milisecunds in my machine, try to update and see how long it takes in yours
please see how that works, later I will make the demo mutiothread, that should scale linear wit the core count.

Also notice that newton can run concurrent wit the application, select the check box "Concurrent physics updates" in the menu see how your frame rate almost double.
this is a very good trick because more systems are at least dual cores, and in a dual core there a lots dead CPU time that go to waste on thread Sleep. Running conrurrent the system can commint thread tim to oteh cores without affectin the main thread at all.
In fact this is so good that with tow thread for example the perforamce can more than double, because concurrent thread has chrider microthread those can also use spare time that is waste in mean thread.
This is because with main GPU some time teh system has to wait until a render call or a buffer floash is completed, and tha time can be use but some mocrithread.
threfore running concurrent is good even on single cores.

check it out and see if you can do in your game, it essencially give you the physics time for free on any system with more than one core.


edit:
Ok I made the demo parallel, and yes it scale linearlly with the core count.
in my system on average a closest distance calculation between any two simple shapes is 4 micro secunds

[Marc]

Oh yes, in my rough test, all the convex cast together are about 4 times faster than before with newton2xx. Well done

[Julio Jerez]

Ok I just check in a new version with an important bug fix.
the important part is that, it is faster by a significan percent and more robust.

The is on edge case I had not cover yet, an dthat is cycling on hill climing when the loser point is a platoo.
But I have a solution for that, and it will make the algorth to coverge even faster.
Bescially righ now I trap cyclin by counting repetition by that is no a good method.

I still nee to solve teh casewhen eth shape penetrate whis still use the old contact solver of core 200,
I expect anothe 30 to 40% gain in perforcmce there, an dtshi si because teh new fution will resue teh valuse o fthe closet point calculation as fist guess rathe than build a simple from scrtch as is does now. This translate to very sustancial saving.
for now you convex cast should be working.

I will do more testing to cover all of the numercial degenerated conditions that produces positive false answers.

[Marc]

I just updated from svn and tried it. At first it didn't compile. I removed the comments from dgTypes.h line 32-40 to have _WIN_32_VER defined to make it compile.

The result was rather surprising. It's working like the first time I tried the convex cast in newton and you showed me that the implementation at that point did nothing. I'm not sure what happened there, but somehow it got worse compared to my last trial.

Boxes colliding with boxes seem to behave fine now though. No strange bouncing.

[Julio Jerez]

what you mean it got worse? it is slower or it is malfuntioning

[Marc]

Malfunctioning. Before the newest update, my character controller worked like it should. I used the convex cast to get the distance to the ground and apply forces to hover above the ground. But now, that doesn't work. It starts bouncing. There are two things I can imagine that happen:

0. It gets the contacts, but too late. Then I would apply forces to hover back over the ground and from there, the collisioncast will return no contacts anymore so it sinks down again.
-or-
1. The convex cast doesn't return any contact and the cylinder body bounces like everything did a while ago when colliding with the ground because hovering doesn't occur if the convex cast returns 0 results.

The hovering with the convex cast worked before the svn update I did today.

[Julio Jerez]

yu are right there is still a bug
I just run a test castion 225 objects

when castion a spaher I get 2.5 misecund spend on teh update
when casting a 24 point convex hull it spend 9.05 milisecund, this is because I have not optimize that part of the code and it is still using the old code.
all the other shapes from sphere to convex hull take some where in between, withe the close form shapes take less than teh poygonal shapes.
it also scale linar wit eth core count.

however trghet are still some falilure the only shape that seem to pass 100 o fteh time is teh speher, all oteh fail with highet probability depend of teh complexity of the shape.
I am fixxing these bug before moving to optimizing the rest.

do no test yet until I get this bug fixed, teh conevx cast should be fast, and 100% acurate in 100% of teh cases. on failure and it is is considred wrong.

[Marc]

I experimented a bit with it and found out that the normals of the result of the convex cast are flipped (and I need the normals). If I do

Code: Select all

         for (i = 0; i < contacts; ++i)
         {
            info[i].m_normal[0] = -info[i].m_normal[0];
            info[i].m_normal[1] = -info[i].m_normal[1];
            info[i].m_normal[2] = -info[i].m_normal[2];
         }


the hovering works again. Is this flip intentional? Is it so from now on? Or is this a bug?