Wednesday, March 21, 2007

ODE Determinism

A while ago I had a play with two free physics systems, ODE and Newton. I started by using ODE, and in this post will summarize my experiences with it.

After a while of flipping objects around I tried making a simulation. I specifically wanted the simulation to be deterministic, meaning that if I set the same simulation up twice and said ‘go’, the same sequence of events would happen. (E.g. A precariously balanced tower would always fall down one direction, let’s say left.)

I found that ODE wasn’t deterministic (E.g. the tower would unpredictably fall left or right each time). I dug through the forums and eventually found something quite interesting. When ODE collides two objects together, it generates multiple contact points. For efficiency and stability, it chooses the contact points it’s going to use randomly, and over time this statistically averages out to represent the full contact surface. At this point you might be scoffing, and saying that you wouldn’t do it that way. I say once you’ve written your own physics system and think it’s easy, then you can scoff :)

So I tried a hack. I tried calling “srand(0)” before the start of each simulation run. This should mean that for the same objects, and the same sized time step, the same sequence of events should happen, and when collisions happen, the same order of random numbers should be generated, meaning the simulation shouldn’t diverge. I tried this, and almost to my surprise it worked! The simulation would run the same way time after time.

However I then realized another facet of the determinism which I hadn’t foreseen. My simulation was deterministic, but if I added another physics object which was off in the distance, and not directly colliding with the main focus of the simulation then I would get a different deterministic result (E.g. the tower would always fall left, until you add a brick somewhere in the distance, and now the tower would fall right). The cause is that the new physics object is causing an extra collision, and therefore throwing off the sequence of random numbers.

The next hack I could do would be to change the Rand function which ODE uses to return a fixed number. This should cause all collisions to resolve the same way.

Unfortunately it was a while ago that I worked with ODE, and I can’t quite remember whether I tried the second hack. By this point the determinism problem and also problems getting objects to fully come to rest were frustrating me and so I decided to try out Newton.

Before I close I’d just like to say that though it may look like I’m giving ODE a hard time, there are lots of users of it, that many applications don’t need determinism, and that I’m delighted that the clever people who wrote it went to the trouble of doing so. Having played with bits of physics code I can appreciate the difficulty in building a physics library, and am grateful that I don’t have to write my own.

No comments: