FWD: [ODE] Performance with multiple cars

[Martin C. Martin]

You could iterate through the joints in the opposite order every other
iteration.

- Martin

whitt013 wrote:
> 
> 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
> 
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode