FW: [ODE] Performance with multiple cars

[Sergio Valverde]

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