deterministic physics using a fixed-point conversion buffer

[CCJ]

Hi all,

I've been doing some reading on deterministic physics lately and I've found that there really aren't any truly deterministic (that is to say deterministic across platforms/architectures/compilers) 3D physics engines out there. To accomplish this, I suppose one would need to rely on fixed-point math and that would throw a great deal of hardware accelerated calculation potential out the window. I've seen countless discussions going back and forth about the potential virtues and vices of fixed point math instead of floating point for physics calculations, but I don't believe I've ever seen someone propose the following ideas:

First, provided one's physics engine and rendering engine are completely modular and disparate, one could write a 'floating point to fixed point conversion buffer' class which would be inserted between the physics and rendering engines. The physics engine would be free to perform its calculations with hardware-accelerated floating point values which would then be passed to the conversion buffer class, and then the conversion buffer class would convert all floating point values to fixed values according to a set of rules composed in such a way that scenarios falling within a certain range of similarity always end up as the same fixed point value. This fixed point value would then be passed to the rendering engine so that the result the user sees is based on fixed point values and can be completely deterministic.

Second, one could even apply a bit of 'machine learning' to the situation by having the rule set described above for the conversion buffer class be determined dynamically based on results returned via floating point values the first time a certain range of similar scenarios occurs-- the resultant physics values and/or even the rendered result could be stored in a pseudo-database and associated with the causal scenario range such that when a sufficiently similar scenario occurs again the program doesn't perform new physics calculations, it merely draws on the results it came up with the first time for the given scenario range. Using this technique, the conversion class could be bypassed altogether in favor of a 'learned physics' model that makes minimal calls to the physics engine and instead relies on previously calculated results to decide what it should render for a given scenario. This would also allow the rendering engine to use floating point values, in case it benefits from them in terms of performance. The obvious drawback to this approach is that the 'physics' wouldn't be deterministic across playthroughs unless one were to construct a giant database of physics results in beta testing and then nix the physics engine entirely for the release. To be practical, this method would also cut down on the versatility of the physics scenarios.

I especially like the first idea proposed above; using a floating to fixed point conversion class (with a pre-determined conversion rule set) seems like it would be a relatively simple way to achieve versatile deterministic physics in 3D applications without sacrificing calculation speed for the physics engine. Anyway, my question is why hasn't anybody tried something like this yet? Does rendering benefit much from floating point as opposed to fixed point values? If so, is it really such a dramatic difference that fixed point values for 3D rendering would significantly negatively impact performance?

Any comments/insight would be much appreciated!
Thanks,
CCJ

[bone]

there really aren't any truly deterministic (that is to say deterministic across platforms/architectures/compilers) 3D physics engines out there

... due to floating point calculations, right?

The physics engine would be free to perform its calculations with hardware-accelerated floating point values

So ... you're still going to have the exact same problem.

I think you're misunderstanding something. Nothing you do on the rendering side (or in between rendering and physics) is going to make the physics deterministic. It's not even going to make the rendering deterministic, since the input, the physics, is still non-deterministic.

As for your second idea, I think you're underestimating the complexity of most physics engines. You can't do a table lookup or anything similar to find the results of a complex calculation. The number of dimensions is very large, and therefore the number of possible scenarios is essentially infinite for all intents and purposes. Perhaps it would work for a single ball bouncing on a flat surface, but that doesn't seem very interesting or worthwhile to build a complex machine learning algorithm for.

Or were we talking about quantum computers???

[CCJ]

Quote:
there really aren't any truly deterministic (that is to say deterministic across platforms/architectures/compilers) 3D physics engines out there


... due to floating point calculations, right?

yes

Quote:
The physics engine would be free to perform its calculations with hardware-accelerated floating point values


So ... you're still going to have the exact same problem.

I think you're misunderstanding something. Nothing you do on the rendering side (or in between rendering and physics) is going to make the physics deterministic. It's not even going to make the rendering deterministic, since the input, the physics, is still non-deterministic.

The physics output would remain non-deterministic, but the point of the conversion buffer class in between the physics calculations and rendering would be to change the non-deterministic floating point values from the physics engine to fixed point values according to a pre-determined rule set (ex. one such rule could apply to the floating point values 53.012345679013455670012 and 53.012345679013455679936, changing the values to fit a Q3.8 fixed point specification such that each value resolves to 53.01234568. A more complicated example might be the values 53.012345679 and 53.012345671 which a more complex custom rounding function would specify should both resolve to 53.01234567 simply for the sake of determinism in Q3.8 fixed point).

That way, even though the physics calculations themselves aren't deterministic the results the user sees in the rendering should be deterministic. Essentially the trade-off is that you would need to give up on some of that sweet physics engine calculation integrity in some cases, but you could (in theory) ensure that what the user sees is deterministic. Also the rendering would be working with fixed point so its performance might not be as good as it could be with floating point on certain architectures, but the calculations the rendering engine needs to perform are generally fairly basic linear algebra (fairly basic at least compared to what the physics engine has to contend with) so I wouldn't expect much trouble from that.

Does that make more sense now?

The second idea I had last night while playing Braid Just thought I'd throw it out there; I realize it would be impractical for most situations. Still, in conjunction with other strategies it could potentially be of use...

EDIT: naturally, the level of non-determinism of the given physics engine cross-platform/architecture/compiler is important... if the integer portion of a calculated value from the physics engine changes for the exact same scenario across two different platforms then it becomes a whole new ball game. If however the integer portion remains the same and only the fractional bits differ you would only need to impose rounding function rules, which should be do-able. Even in the former case it might be possible to make the buffer class work, but it would require some very clever implementation. How far off do results from Bullet tend to be across different platforms (ex. i7 PC to ARM Android, both with FPU)? Does anybody have a numeric cross-comparison of Bullet's calculated results (not just performance) driving some core physics behaviors [collision, effects of gravity etc.] on different platforms?

[bone]

I understood where you were going with that, but the problem is the "butterfly effect". A small difference early that may be easily filtered out by the conversion can still lead to a big difference later that cannot.

EDIT: and I might note that most accelerated floating-point calculations are sadly only available in single-precision which makes this problem many many orders of magnitude worse.

[CCJ]

Hmm, interesting. Well, it was just a thought... are there any special tricks used to try to squeeze pseudo-determinism out of 3D physics engines? For most purposes cross-platform determinism wouldn't be too important I suppose, but for engineering simulation apps and heavily physics-based games it could be rather necessary.

[bone]

That's a good question. I'm not sure about all compilers and platforms, but at least the MS compilers on PCs have a 'strict' floating point mode which gives up a little performance to ensure IEEE standards. And I don't actually know if this makes it deterministic or not.

At some point I came across a software library that performed strict floating point operations in code, which could be used to verify the hardware implementations. If you're really curious you could search for something like that and see if there's more information there.

You're exactly right, though, a proper engineering simulation would ideally provide determinism on all supported platforms, at least for debugging.

[Story]

Even strict fp is not perfectly deterministic, though it is good enough for all practical purposes.