Perhaps they use Jacobi. Still, even when using Jacobi, the constraints might share rigid bodies, so velocity impulses from different constraint on sharing one rigidbody need to be combined. That sounds like a sequential problem, combining those impulses (or updated velocities).Dirk Gregorius wrote:Erwin,
if the GPU are so fast, couldn't it be that they use a Jacobi like solver which is by its very nature parallel as opposed to Gauss-Seidel.
Steve, the solving method takes contact constraints between two bodies (typically), so usually solving happens on a body-pair basis, not per-body.Steve wrote: OK - that makes a lot of sense. If the GPU can do Jacobi many, many times faster than the CPU could do GS - then maybe you can do enough iterations to make it worthwhile. However, the idea here is to use the GPU to do more objects - if we burned too much performance on Jacobi then it might not provide any benefits.
So GS works sequentially through a chain of interactions or something? Something like "look at object A - fix up it's motion - now look at what that fixing up did to objects B, C & D"? If that's it then some parallelism might still be possible if we ran GS in parallel on a bunch of objects that are so far apart that they can't possibly interact with each other?
The idea being to (say) split the world into a spatial grid then run GS in parallel by picking one object from every alternate cell and running all of those in parallel. Since we'd know for sure that those objects could never directly interact - would that be enough to let us run them in parallel? I could imagine situations where that might not work - maybe a long row of boxes - all touching each other. We push on a box on one end - but the consequences of that traverse multiple cells in my hypothetical grid.
Also, we must deal with large stacks where all objects are touching directly or indirectly, so one connected graph. You can make some clustering where you can solve groups of objects in parallel. Then you write back velocities (merge/average results in some way (or apply impulses), and let the relaxation (iterative converging process) deal with your approximations over time.