Tuesday, 21 June 2011

Spatial Binning

Recently, development of the class library has focused on optimizing interactions between large populations of particles. Typically each particle is forced to perform a distance check between itself and all other particles in the system. From there it collects forces which are generally some function of this distance. In this case, computation time is proportional to the square of the particle count making large populations really chug. Enter spatial binning.

When forces are only active within a finite range (ie. boids, packing etc.) checking every particle isn't really necessary. By breaking down the simulation space into 3 dimensional domains or "bins", particles can perform their search by only checking the bins that sit within a local influence. Generally the more local the search, the more effective the optimization, assuming the bin size isn't too small or too large. The video above has 10000 agents interacting at about 15 fps. Prior to binning, just under 1000 agents were running at about the same speed. Excelsior.

Platforms: C#, Grasshopper, Rhino

No comments:

Post a Comment