3 ms·

Very cool, I was just reading about constraint solvers and position-, velocity- / impulse-, forced-based dynamics etc the last few days and wondered how hard it

Very cool, I was just reading about constraint solvers and position-, velocity- / impulse-, forced-based dynamics etc the last few days and wondered how hard it would be to do a physics engine from scratch. As far as I can tell, this is single threaded CPU only, right? I wonder if it wouldn't be more appealing to do it parallel on the GPU instead when starting a new physics engine today, especially given how hard it is to change that later on.

zelphirkalt 6y ago
There was an article on HN not too long ago, where the title was something like: "When in parallel pull, not push". It was about calculating sand pile fractals and how pulling strategy removes the need of locking. I guess for a physics engine the same principle applies. Instead of telling objects, that they are being pushed, let objects themselves ask whether they are pushed, pulling the information readonly from their environment. You would need really light weight processes for situations with many bodies though.
- Diggsey 6y ago
  It would be tricky: constraint solving is a single-threaded algorithm, so the best option might be to run the broad-phase, and then break the scene down into islands of disconnected bodies for parallel constraint solving. The problems are that: 1) There may not be enough islands to make full use of the available threads. 2) For many frames there might be a single island which is particularly expensive to solve, so the benefit from parallelisation is reduced. The broad-phase itself might benefit significantly from parallelisation though.
  - rossnordby 6y ago
    While island based parallelism is doable and works reasonably well for many workloads, it's possible to dynamically batch constraints based on their involved bodies such that no constraints in a given batch share the same bodies. All constraints within each batch can be solved in parallel. Of course, pathological cases can generate a ton of batches. Usually such implementations will use a final 'catchall' batch of some kind after N normal batches. That final batch can be handled sequentially or with a fully parallel jacobi-ish solver (which typically has worse convergence than PGS/SI, but it's usually not a problem in context).
_bxg1 6y ago
> wondered how hard it would be to do a physics engine from scratch It's extremely easy to get started with the basics, and then there's a long ramp of increasingly difficult features you can implement. So if you're doing it for fun/learning, it's a great project. One of my first programming projects when I started learning Java in high school was a 2D physics system. Just took the equations from my physics class and implemented them in code and bam, you have particle physics. And then I figured out how to make those particles into circles with collision and added infinite lines for them to bounce off of, without really knowing what I was doing. Then in an early CS class in college my team for a project did a similar engine but with arbitrary equilateral polygons for colliders. We had someone who already knew the math for doing those intersection checks, so it wasn't too hard. But yeah: things obviously get hard at a certain point, but it's not one of those projects where you don't see any satisfying results until you've mastered it.
rossnordby 6y ago
Having both written physics engines and worked with GPUs extensively (including GPU physics simulation), I would be really hesitant to go GPU-first unless there was a very specific use case in mind. There's no doubt that GPUs have the flops/bandwidth advantage, and even all the overheads of adapting a physics engine to a GPU won't completely eliminate those advantages. If a company needed an absolute-maximum-performance backend simulation on computers they built to spec, it could definitely make sense. But when you move into the realm of game client simulation, it's harder to justify the use of GPUs. Very, very few gamers have multiple GPUs, and the one GPU they do have is often already quite busy. Ignoring all the nightmarish issues around driver bugs and vendor compatibility, it comes down a question of comparative advantage. GPUs are extremely good at graphics. They can also do a pretty darn good job at physics. Or sound path tracing. Or machine learning inference. Or any number of other high throughput workloads. There's a limited budget, and there's no reason to leave a beefy CPU idle. What task allocation gives you the most bang for the buck? Would your average gamer be okay with worse graphics, just because the GPU is needed to perform physics simulation in order to play the game? The answer will sometimes be yes, but it's something to be careful about. Plus, especially with the latest surge in CPU performance and competition courtesy of AMD, CPUs can do a pretty darn good job of running physics simulations per dollar.

zelphirkalt 6y ago

There was an article on HN not too long ago, where the title was something like: "When in parallel pull, not push". It was about calculating sand pile fractals and how pulling strategy removes the need of locking. I guess for a physics engine the same principle applies. Instead of telling objects, that they are being pushed, let objects themselves ask whether they are pushed, pulling the information readonly from their environment. You would need really light weight processes for situations with many bodies though.

Diggsey 6y ago
It would be tricky: constraint solving is a single-threaded algorithm, so the best option might be to run the broad-phase, and then break the scene down into islands of disconnected bodies for parallel constraint solving. The problems are that: 1) There may not be enough islands to make full use of the available threads. 2) For many frames there might be a single island which is particularly expensive to solve, so the benefit from parallelisation is reduced. The broad-phase itself might benefit significantly from parallelisation though.
- rossnordby 6y ago
  While island based parallelism is doable and works reasonably well for many workloads, it's possible to dynamically batch constraints based on their involved bodies such that no constraints in a given batch share the same bodies. All constraints within each batch can be solved in parallel. Of course, pathological cases can generate a ton of batches. Usually such implementations will use a final 'catchall' batch of some kind after N normal batches. That final batch can be handled sequentially or with a fully parallel jacobi-ish solver (which typically has worse convergence than PGS/SI, but it's usually not a problem in context).

_bxg1 6y ago

> wondered how hard it would be to do a physics engine from scratch It's extremely easy to get started with the basics, and then there's a long ramp of increasingly difficult features you can implement. So if you're doing it for fun/learning, it's a great project. One of my first programming projects when I started learning Java in high school was a 2D physics system. Just took the equations from my physics class and implemented them in code and bam, you have particle physics. And then I figured out how to make those particles into circles with collision and added infinite lines for them to bounce off of, without really knowing what I was doing. Then in an early CS class in college my team for a project did a similar engine but with arbitrary equilateral polygons for colliders. We had someone who already knew the math for doing those intersection checks, so it wasn't too hard. But yeah: things obviously get hard at a certain point, but it's not one of those projects where you don't see any satisfying results until you've mastered it.

rossnordby 6y ago

Having both written physics engines and worked with GPUs extensively (including GPU physics simulation), I would be really hesitant to go GPU-first unless there was a very specific use case in mind. There's no doubt that GPUs have the flops/bandwidth advantage, and even all the overheads of adapting a physics engine to a GPU won't completely eliminate those advantages. If a company needed an absolute-maximum-performance backend simulation on computers they built to spec, it could definitely make sense. But when you move into the realm of game client simulation, it's harder to justify the use of GPUs. Very, very few gamers have multiple GPUs, and the one GPU they do have is often already quite busy. Ignoring all the nightmarish issues around driver bugs and vendor compatibility, it comes down a question of comparative advantage. GPUs are extremely good at graphics. They can also do a pretty darn good job at physics. Or sound path tracing. Or machine learning inference. Or any number of other high throughput workloads. There's a limited budget, and there's no reason to leave a beefy CPU idle. What task allocation gives you the most bang for the buck? Would your average gamer be okay with worse graphics, just because the GPU is needed to perform physics simulation in order to play the game? The answer will sometimes be yes, but it's something to be careful about. Plus, especially with the latest surge in CPU performance and competition courtesy of AMD, CPUs can do a pretty darn good job of running physics simulations per dollar.