FWD: [ODE] Performance with multiple cars

[whitt013]

Ok, I'll bite.  I've begun working on a high level implementation of the 
iterative algorithm.  My approach right now is to replace the functionality of 
dProcessIslands with a function that simply iterates through all the joints 
and calls a slightly modified dInternalStep on the joint and each body it's 
connected to.  The modifications needed were to add cforce back to the facc 
and tacc vectors and not actually move any bodies until all the iterations 
were complete.  The plan is to just perform one small step and let the end 
user lower their stepsize and do the collision and call dWorldStep multiple 
times per frame.  So far, it looks quite good for all the test_* programs with 
as little as 5 iterations (timestep = .01) per frame.  But it gets really 
sloppy (looks like the CFM is too high, even if CFM is 0, even with 100 
iterations) with more articulated systems (I've got a train of 50 spheres with 
wheel spheres on either side of every other body sphere to make a really long 
"car" with 25 pairs of wheels).

I'll play with it some more over the weekend, maybe even get up enough courage 
to dive into dInternalStep, but feel free to shoot holes in this method if you 
know why it isn't working as well as expected.

David

>===== Original Message From Sergio Valverde <svalverde@barcelona.ubisoft.es> 
=====
>Yes, I've implemented an iterated physics solver. I'm sorry I haven't
>enough free spare time to adapt the algorithm to the current ODE
>version (the original is coded into our own propietary physics system).
>In past e-mails on this list you can find references and pseudo-code
>for the iterative algorithm. So if you don't mind to get your hands
>dirty...
>In any case, I'm going to release a version of the algorithm but it
>is  difficult to me to predict the exact release date.
>I have enough with my job deadlines!
>Regards,
>Sergi Valverde
>Software Engineer/ UbiSoft
>http://complex.upf.es/~sergi
>
>-----Original Message-----
>From: whitt013 [mailto:whitt013@bama.ua.edu]
>Sent: jueves, 13 de marzo de 2003 1:43
>To: ode@q12.org
>Subject: RE: [ODE] Performance with multiple cars
>
>
>Last one....
>=========================
>ODE does have a few problems with scalability at this point.  The big
>problem
>is that it scales with the cube of the number of degrees of freedom removed
>from each island of bodies.  With your example, each car is an island,
>removing 24 DOF's (5 per hinge, 1 for each contact with the ground).  So 8
>non-colliding cars would cost you 24^3 * 8 ~ 110k processing units
>(fictitious
>term, but should be proportional to the amount of time it takes to step the
>world).  However, when they all collide, not only does it add a new contact
>at
>every collision point, removing more DOF's from the system, but they also
>become one island.  That means you've got 25 (24+1 for the new contact
>joint)
>DOF's per car, but 8 cars.... so 200 DOF's removed from one island.  200^3 =
>8000k.  Conclusion: it takes roughly 80 times as long to simulate 8
>colliding
>cars as it does 8 non-colliding cars.
>
>So what can you do about it?  I'm afraid not much.....  There was a guy by
>the
>name of.... Sergi I think.... working on an iterated solution for ODE, but I
>haven't heard anything in the past few weeks.....  The iterated solution is
>O(kN) for a small k, i.e. it scales linearly with the total number of
>constraints in the system.  Say it takes k=10 iterations to resolve the
>system, that means the algorithm may take 2k "processing units" for purposes
>of comparison..... So we're definitely looking at an amazing speed-up for
>ODE
>if that ever gets implemented.
>
>DISCLAIMER:  I know the above method of comparison is unorthodox, and that
>there are several factors outside of those calculations that affect the
>total
>speed of the simulation.  You should take nothing more from the above
>numbers
>other than the fact that 8 touching systems are an order of magnitude slower
>than 8 non-touching systems, and that whole system is an order of magnitude
>slower than it would be if it were implemented with the iterated algorithm.
>
>Now, there is one thing you might be able to do about it..... When one car
>collides with another one, destroy it's joints and wheels, increase the size
>of the box to make up for it and just turn it into a big sliding box.  You
>don't necessarily have to draw on the screen exactly what is happening in
>the
>physics simulation....  You could draw a car based on the location and
>rotation of your box only, and no one would ever notice the difference when
>it
>crashed and came to a screeching halt...  Of course, if the cars just barely
>touch, they would still require more processing power, but you couldn't
>simplify them and still make their motions look believable, so you'll have
>to
>test if it's a crash level collision, maybe based on the penetration depth.
>
>David
>
>>===== Original Message From "Jeroen Schmitz" <ode@engine-software.nl> =====
>>I have a simulation with a car, much in the same way most ode car
>>simulations are built: a box for the carbody, 4 spheres for the wheels
>>that are connected to the body with hinge-2 joints. The car is driving
>>on a surface that is made using the tri-collider and the sides of the
>>road are also defined using the tri collider (you could see that as
>>walls).
>>Now this works quite well if I only have one car driving around and it
>>also works fairly good if I add a second car to the simulation (if you
>>hit the second car with the first one, everything acts like you would
>>expect).
>>However, I have also tried my simulation with 8 cars in total. This also
>>works, until you make the cars collide altoghether. For instance, I have
>>set the 8 cars in a straight line behind each other and then I use the
>>last car to hit into the back of the car in front of them, sorta like a
>>train effect. The simulation becomes very slow then, probably because
>>all cars are colliding with each other, and eventually the program
>>crashes if you try to hit the cars for a while in this way.
>>
>>Is this behaviour to be expected in such a case or should the
>>performance of ODE still be usable in this case and am I doing something
>>wrong here? Note that the simulation works quite well with the 8 cars,
>>as long as not too many cars collide with each other!
>>
>>Jeroen
>>
>>_______________________________________________
>>ODE mailing list
>>ODE@q12.org
>>http://q12.org/mailman/listinfo/ode
>
>
>_______________________________________________
>ODE mailing list
>ODE@q12.org
>http://q12.org/mailman/listinfo/ode
>_______________________________________________
>ODE mailing list
>ODE@q12.org
>http://q12.org/mailman/listinfo/ode