Quadtrees and octrees are themselves quite deep research areas. If the acceleration data structures interest you, I highly recommend Hanan Samet's book "Foundations of Multidimensional and Metric Data Structures". It's from 2006, but is basically the bible for the field.
Note that even without an acceleration structure ("direct summation" in N-body research terminology), a CUDA program or GLSL shader program can exceed 60 fps with 10,000 to 20,000 particles. And a parallel, C/C++/fortran vectorized CPU code can do the same with over 5 thousand.
FPS is a poor metric anyway, things like this should be measured in frame time instead - but either are meaningless numbers without knowing the hardware it runs on.
Sure, I usually measure performance of methods like these in terms of FLOP/s; getting 50-65% of theoretical peak FLOP/s for any given CPU or GPU hardware is close to ideal.
The general algorithm used here (of computing attraction and repulsion forces between pairs of particles) is very similar to that used in simulations of many interesting phenomena in physics. Start with Smoothed Particle Hydrodynamics (https://en.wikipedia.org/wiki/Smoothed-particle_hydrodynamic...) and then check out Lagrangian Vortex Particle Methods and other N-Body problems (https://en.wikipedia.org/wiki/N-body_problem).
And the algorithms to solve these quickly is another deep area of research.
Thank you - I was just about to point out some of that.
The reason that the flocks are tight is because the separation "force" is normally computed as a repulsion between a target boid and all other nearby boids individually, not vs. the center of mass of all nearby boids.
Let's be a little more clear: these are not "laws" as much as they are scaling relationships, this is not "new math" (see Ziph and others), and central planning has always had an impact on city development. Nevertheless, I appreciate this line of inquiry.
Something doesn't add up here. The listed peak fp64 performance assumes one fp64 operation per clock per thread, yet there's very little description of how each PE performs 8 flops per cycle, only "threads are paired up such that one can take over processing when another one stalls...", classic latency-hiding. So the performance figures must assume that each PE has either an 8-wide SIMD unit (and 16-wide for fp32) or 8 separately schedulable execution units, neither of which seem likely given the supposed simplicity of the core (or 4 FMA EUs). Am I missing something?
Exactly this. Whenever I talk about how I got started in computer art over 40 years ago, I always mention the fact that a screen back then was a one-way device: TV network to you. Basic home computers HAD to plug into the TV, and to a kid, this was magic and freedom.
Yes, this appears to use Stam's Stable Fluids algorithm. Look for the phrases "semi-Lagrangian advection" and "pressure correction" to see the important functions. The 3d version seems to use trilinear interpolation, which is pretty diffusive.
This is a fine collection of links - much to learn! - but the connection between flow and gravitation is (in my understanding) limited to both being Green's function solutions of a Poisson problem. https://en.wikipedia.org/wiki/Green%27s_function
There are n-body methods for both (gravitation and Lagrangian vortex particle methods), and I find the similarities and differences of those algorithms quite interesting.
But the Fedi paper misses that key connection: they're simply describing a source/sink in potential flow, not some newly discovered link.
Supercomputers will simulate trillions of masses. The HACC code, commonly used to verify the performance of these machines, uses a uniform grid (interpolation and a 3D FFT) and local corrections to compute the motion of ~8 trillion bodies.
