jdiwnab
commented
9 years ago So, this algorithm is suppose to speed things along by estimating calculations if an object is sufficiently far. But at best this does no harm for 1-3 objects, give or take, seems to be ok, but not great for a bunch (500 objects), but is terrible for a moderate number (~10-12). Making this off by default, and putting it under the engine menu.
The Barnes-Hut algorithm is an optimization to the brute force method of calculating all of the interacting forces by estimating forces for distant subsets based on center of mass of those subsets.
The algorithm puts the particles into a quad or octo tree (for 3d), a node for each quadrant. Theses are then sub divided until only 0 or 1 particles is in a leaf node. Each node keeps track of total mass and center of mass.
When calculating forces, a node is sufficiently far away to use the CoM if s/d < theta, where s is the width of the quadrant, d is the distance from the particle to the CoM, and theta is a threshold, typically 0.5. If theta is 0, his works just like normal.
This gives approximately O(n log n) compared to O(n^2)
See https://github.com/Elucidation/Barnes-Hut-Tree-N-body-Implementation-in-HTML-Js http://arborjs.org/docs/barnes-hut