Optimize Marc's Character Controller / Batching Convex Casts

[Marc]

I posted a while ago my Character Controller. I'm still working on/with it and so far I'm happy with it.

Now I wanted to use it in a game of mine and with the rising of the number of objects in the scene using the controller, I'm getting an issue I guessed I would hit at some point: ConvexCast takes most of my cpu time. Right now, the controller uses 2 ConvexCast per update per object. With about 70 of such objects, I'm hitting almost 100% cpu of one core.

The wiki has a remark that says that it's not as efficient as the collision system used for the physics because it's not batched. Now, I'm wondering: Is it possible to do something like the ConvexCast that can be batched?

All the casts I do right now are independent, so I don't need to have the result of one cast to know what cast I'll be doing next. I could batch all casts up and execute them all at once and process all the various results afterwards. So from the controller's side, it could be batched. But is it possible to do it with newton's collision system? Maybe with newton 3xx ?

[Marc]

I just thought of maybe I can do something like batching those casts myself:

I could create a body for every cast that has to be done. I attach the collisionshapes and set the start positions. Then I calculate and set the velocities so the target position will be reached within one newtonupdate(). In the contact callback I record the contacts I'm interested in as a result of the convex cast. Before leaving the contact callback, I remove all collisions so these bodies have no effect on the world. Afterwards, I use the recorded contact data.

Would this be faster? I guess it scales better because the casts can make use of the collision system. At the same time though, these new bodies will get simulated while there is no use for the results of that simulation. Then again, because I remove all contacts in the callback, that simulation might be really cheap as no collision responses have to get calculated.

Any ideas/suggestions?

[Julio Jerez]

is your player controller runnd from within in a newton update? if so then by setting teh tread count the will make all callback to be dispceh in pareallel

if you are doin your own thing you can do in all newton collsion fntion are threa safe and can be call in parealler.
The simplest way to do that is to plug a post listener or prelistenr callback in the engine.
then in the callback you can run all you player in parallel using the thread pool like this, teh godo thong aboput using pre or post lister call back is that you can set the execution order bacause thet are call in the sae oreder that they are added.
here is a template for loop that displace all lot of call back in pareallel

Code: Select all

   void SimulationLister(DemoEntityManager* const scene, DemoEntityManager::dListNode* const mynode, dFloat timeStep)
   {
      //any application can use this feature of core 300 to execute in parallel any non physics related logic
      //that can be execute outsize a newton callback, ex AI path finding for many objects, ray casting
      //procedural mesh generation, particles update etc. 
      for (int i = 0; i < m_rayCount; i ++) {
         //NewtonDispachThreadJob(m_world, updatePlayer, &m_player[i]);
      }
      NewtonSyncThreadJobs(m_world);
   }

look at demo MultiRayCasting.cpp

I also suggest usin the posi and parelistenert because when I use openCL they will add a way for teh end usen to displace call to open CL kernel as well.


what kind of shape are you casting?

[Marc]

I'm using a cylinder shape which is standing like a soda can and cast it exactly downwards. Maybe that can be optimized somehow because it's perfectly axis aligned and the sides of the cylinder aren't needed?

I checked out the MultiRayCast demo. It paralellizes the task so the maximum gain you can get from this is a factor of the number of cores your pc has. Maybe I'm wrong but I was thinking there could be an order of magnitude acceleration possible. There is also a remark in the wiki that sounds like this:

from http://newtondynamics.com/wiki/index.ph ... ConvexCast:

Code: Select all

The objectcast function is provided as an utility function, this means that even thought the function is very high performance by function standards, it can not by batched and therefore it can not be an incremental function. For example the cost of calling 1000 object casts is 1000 times the cost of calling one object cast. This is much different than the collision system where the cost of calculating collision for 1000 pairs in much, much less that the 1000 times the cost of one pair. Therefore this function must be used with care, as excessive use of it can degrade performance.


Isn't it possible to do something like this? For example by adding dummy bodies like described in my previous post, I do something like that right? But that way, it's some kind of a hack. :/

[Julio Jerez]

The first thing is that tsoe comment apply to core 200 and 100, for core 300 all collaion funtion are reentrat.
There reason they were no before was that the collision shape store locall data. Teh newton update new when to use Lock/ Unlock to about race condition.

In core 300 all collsion are isntance trhefore teh can contat local data, and i nteh case that many collsion hit teh same shaep teh engien make loca inatce on the stack so there is never race contion.


on the performace you say you are using a cylinder. cylyders are very expensive shapes.
core 300 spacial case conic shapes, the are like you say oen order of manity faster calculation cloosion.

a conic shape is thar shape teh can be define but a paramerametri equation oc a conic, or the struction or lacing of a parmetric equation of a conic.
Colynder and cones do no fall on that cathegory because the have hard edges.
I am think on soem specia optimization for cylidner bu tha will be afte I fix the hug ebnergy collision bug with

As a test can you try a capsule, ot a and elipsoid? just to see the result.
It should be about 10 time or more faster.

[Julio Jerez]

On a secund thought, It may be possible to make the collidenr cast an order of magnitud faster on average.

Let me experiment with that tonight.

[Marc]

All this sounds great. I'm looking forward to your results

I'll try replacing the cylinder with a capsule tomorrow. I can't use a sphere for everything because having two players pushing against each other, with a sphere, one will probably push himself on top of the other if there are even small differences in their vertical position. I might use a capsule for the body and a capsule or sphere for the casts, though. I'll try that tomorrow.

What makes me wonder is that you haven't said anything to my initial idea, or well the idea I had when I started this thread. Maybe I haven't explained it good enough or maybe it's total *. So I try to explain it more in detail:

Right now, assuming you have N objects in your scene. I assume newton has some sort of spatial tree structure where it puts the objects in. So from a theoretical point, doing an AABB Query in the scene is O(log N) I guess. I also guess that convex cast basically does an AABB Query first and then does something linearly with the resulting objects, so its complexity is O(log N) as well. Now, if I have a Convex Cast in every logic code of every object, that makes N Convex casts, which results in a complexity of O(N log N) for all convex casts.
Now, what I was thinking, but maybe it's wrong, is the following: Assuming I know all N Convex Casts upfront, I could somehow batch them all together and just query this against the newtonworld. I'm not exactly sure how, but I'm thinking that this way, one could achieve O(N) as a complexity for N Convex casts.

Is this wrong?

[Julio Jerez]

if you are refering to this:

All the casts I do right now are independent, so I don't need to have the result of one cast to know what cast I'll be doing next. I could batch all casts up and execute them all at once and process all the various results afterwards. So from the controller's side, it could be batched. But is it possible to do it with newton's collision system? Maybe with newton 3xx ?

To me batching is the prosses of doi a buch of similar operation in on function call. teh way teh engien does that is by usin teh thread pool.

if you refert to the idea of putting a bunch of calles in thread and letting it run asycronous.
There are some engines that do work like that and they use a double buffers internally to go around syncronization logic.
when I made newton 1.00 mutithreaed teh first time, I tried that, but after a while I found it too complicated for both the client application and the intenal engine logic.
The way Netwon works is that id does task in pareallet and syncronize at a exit pointm teh do a noteh buck of tasck and syncronize again, and so on.
if you fo example place a bunck convex cast on a thread to work a asycronnous, then the Bradphase will have to have a lock/unlock mechannish
each time is going to update the location of a cell inetranlly of exrenally,
this will bring the engine back to the original point when collisions were objects, not intances.
by this I mean the Broadphase in the engine is not reentrant to support that funtionality eassilly.

On this

Right now, assuming you have N objects in your scene. I assume newton has some sort of spatial tree structure where it puts the objects in. So from a theoretical point, doing an AABB Query in the scene is O(log N) I guess. I also guess that convex cast basically does an AABB Query first and then does something linearly with the resulting objects, so its complexity is O(log N) as well. Now, if I have a Convex Cast in every logic code of every object, that makes N Convex casts, which results in a complexity of O(N log N) for all convex casts.
Now, what I was thinking, but maybe it's wrong, is the following: Assuming I know all N Convex Casts upfront, I could somehow batch them all together and just query this against the newtonworld. I'm not exactly sure how, but I'm thinking that this way, one could achieve O(N) as a complexity for N Convex casts.
Is this wrong?

yes this is all correct, however you are making a common mistake of applig teh time complxiti of an algorithm to an applictaion.
Ye is is true that teh braod phase is and O(lonN) query.
but a phsocs engien, just loekl a graphics engien is mand of many diffrent algorithm,

for exemple the broadp phase is an O(log n), by say you have a lareg mehs trryy in teh braod phase, oarehap more than one
you shape may toufh few of those, and a collison

a collsion tress also have a o(m *logn) when m is teh numbe of face tah hit the oobb.
a terrai high field isn conatct time by report more faces,
a convex cast has a comples time complxity. and so on.

so bascially you are tlaking of bacthing the outer layer of the engine (the braad phase)
but I am positive that of the total time that is the part that is most insignificant.
can you tell my about how your scene is made off?

[Marc]

My scene is made of a user collision and multiple of my character controllers which consist of a cylinder. Mainly, the cylinder collides in xy direction with things while it hovers above the ground. I make it hover by using the result of the convex casts to calculate forces to make it hover above the ground at a defined distance. The convex casts are cylinders as well which get cast downwards.

Ah I see. When I mentioned the batching, I also meant using some more efficient algorithm that was made possible through batching, not just running things in parallel. But ok, it seems like the log N is not worth it since other parts of the convex cast take more time anyways.

I just tried replacing the cylinder body with a capsule. With 100 character controllers in the scene the newton update takes 4ms with the cylinder shape and only 3.5ms with the capsule. So it's a bit more efficient. I haven't tested the ellipsoid because of the problems I would get with using it. I was wondering: Might it be possible to adjust the spherical parts of the capsule to be ellipsoid like?

Now the surprising part: I tried replacing the collisions I cast downwards with a capsule and with a ellipsoid. For 100 character controllers, all the casts together take 10ms with the cylinder shape. Changing it to a capsule makes it take 12ms. And the most surprising part: Changing it to an ellipsoid makes it take 20ms!

I don't know the internal details but casting down a cylinder essentially is like casting down a disk. Casting down a capsule or an ellipsoid is more like casting down a half sphere which sound more complicated than the disk. Maybe that's the reason for these results?

All this is done still using newton 2xx.

[Julio Jerez]

I was talking about 3.00 not 2.00

In 2.00 all conevex cast are done using a generic function, very few are single out for optimization,
this is not the case for 3.00 where almost all close form shapes use a special function that is much faster, because it works by using the features of the shape not the surface.
casting a sphere and a capsule is much faster than a cylinder in core 300.
and I will mad eteh cylinde use that funtion too, so in many case it will also be faters than using the generaic funtion.

Bascially a convex cast in core 300, has teh same cost at the collsion test for all shapes. it only add a marginal overhead afte the conta point is found.
If I can place few hundred object the I sopudl eb able to cats few hundre shape in eh same amount or time or faster.

[Julio Jerez]

Ok I check in a bunck of optimizations, for close form collsions, it does no cover cylinder yet, I had to make sure all was working first.

Now I will write the fast cylindewr close diatnce function.
Basicially it will no be a 100 fast it will be fast for almost all cases. and the corrent whne teh fast fail. so in essnces it will make collisions with cyloider slower in wors case and fast inb most cases.
hwoever the balance is amost 95% in favor of the fast path. for the other conic shapes is over 99.9% in favor if the fast path

[Julio Jerez]

I believe I am going to have contines collision for all convex shapes in fact one order of magnitud faster

the explanation is as follows, when to convex shapes are not colliding, the test for determining the intersection point is an order of magnitude faster than the test for calculating the contact point of tow collision shape.
what this means is that continue continues of an island of fast moving bodies is faster to calculate, however in the same frame the island is advanced
to the first intersection point and an the another continue or discrete collision is executed depend on the relative speed of the colling bodies after the first contact is resolved

I continue collision simulation e equal to a discrete collsion plus one or more step of continues collision.

for user continues collsion this is is the case, because teh use is interestin on colision part only.
Basically teh CC will be slow wn the tow shape are in deep peneteration at teh orignal localtion in wich case reolev fo teh statnd contact calcuation.

try moving to core 300, so that you can test this. by my statomation you soidl be able to run aorund 1000 convex cast cast for the same time that the old metod takes.
this will be usin a singel core not simd. with mutipel core thsi will scale linerarlly.

so you should be able to have between 700 to 1000 players under 4 milisecond of simulations with one core, thsi my staiomation base of teh Ray cast, simce teh new convex cast will be arund the same speed of a ray cast.

[Marc]

I'm trying to make my code work with Newton3xx. I have some questions which I put in a seperate thread. Afterwards, I'll come back here

[Julio Jerez]

Ok I check in teh first pass of the convex cast,
I need to debug it first but preliminatry result are very satifying.
for a spheres and a capsule agaisnt any othe sphe it work in constant time, whn eteh shape are originaly not intesecting, It is unvelibable how fast it is.

I do not have the figures for other shapes yet, but I need to prefect the casting because it fail with shape liek cone and chamfered cylinders. (chapener cylioder are very important for me befacuse they are use for wheel shapes)

[Marc]

I'm not sure if you mean sphere or shape with sphe:

any othe sphe it work in constant time

Assuming it means shape, I tried it with replacing my cylinders shapes with sphere shapes for casting. There is only a large box below as a ground, so the only thing these casts will hit are this box. Sadly, the results are bogus - or at least completely different to the results I got from newton 2xx.