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

A Wooly Example

I've been getting some requests for wooly paths source code for the past few months so I decided to clean up an early version of it in VB.net and hand it over to the internet. Grab it here.

I've simplified it a bit in an effort to keep the code clear. Unfortunately, in doing so, it takes a bit of a speed hit since some optimizations regarding large particle populations were left out. Feel free to use it / tinker with the source code however you like. All I ask for in return is street cred.

Platforms: C#, VB.net, Grasshopper, Rhino