Microcosm (appositelabs.com/microcosm) is a Granular Synthesis sound toy for iOS. This video is a demonstration of one of the algorithms being used in the development of the app's next update: Octree Spatial Partitioning.
To enhance Microcosm's visual engine, we are adding interactions between individual particles. Because CPU and memory are limited, we need a way to limit the number of necessary calculations. So, rather than comparing every particle to every other particle, we need only compare particles that are close to each other. In order to accomplish this, we divide the space using an Octree algorithm.
Octrees are recursive tree data structures in which a cube is subdivided into 8 child-nodes. Each child-node can be further subdivided into 8 pieces, and so on. In our case, a node is subdivided when it contains more than a certain number of particles. Ultimately, when we perform particle to particle interactions, particles will only be compared to other particles in the same node.
The algorithm seen in this video is not optimized; the Octree is destroyed and rebuilt every frame (at roughly 60 frames per second). The production version in development is further optimized by merging and destroying nodes dynamically as the particles move through space.
For more information on Octrees, see: en.wikipedia.org/wiki/Octree
Audio source material for Granular Synthesis from: freesound.org/people/timdrussell/sounds/51837/