Barnes-Hut for N-body force calculations

Seen on Reddit a couple of days ago, a nicely presented article on the Barnes-Hut algorithm.

I wish I could write posts like that. :-)

It’s the same method as I’ve used, and comes from the same assignment description in Princeton’s CS126. I didn’t prosper in introductory physics at university but I think I would have enjoyed programming this in introductory CS.

As I’ve implemented it, the three cases for inserting a body S into the tree are:

1. The node is empty. Just put S directly there as an external node.
2. The node is internal. Find the correct subnode and insert S there, and add S to the internal aggregate body.
3. The node is external with existing body T. Replace it with an internal node and create empty subnodes, and insert S and T into the node.

During testing I encountered another issue. What if two bodies S and T share the same position? Once S is inserted in a node, the algorithm attempts to insert T by transforming the node into an internal node using case 3. But both S and T are inserted into the same subnode in case 2, which in turn has case 3 applied. It recurses endlessly. So I’ve added an additional case.

4. If the node’s space is small enough, add S to the node’s aggregate body, but don’t insert it into a subnode.

During force calculation, if a body is close enough to need calculation against subnodes, it will find no subnodes and the effect is that of all bodies in that node’s space is ignored. I have yet to determine the extents to which this improves the calculation’s speed and/or worsens its accuracy.

Another implementation issue for me is that the memory for all nodes is pre-allocated.  But I need to know the maximum number of nodes that may be required for the tree if there are N bodies!  Assuming we only use a node if we put at least one body into it, the tree that uses the most nodes will be a binary tree.  So the answer is 2N-1.  An earlier implementation made all subnodes when creating an internal node; the binary tree of bodies has additional empty nodes — 6 per internal node.  The maximum number of nodes required is 2N-1 + 6(N-1) = 8N-7.

Another question: the electromagnetic force is proportional to the product of charges just as gravitational force is proportional to product of masses.  But charge can be negative, and the product of it can be negative.  Can the Barnes-Hut tree be used for simulating simple electromagnetic attraction/repulsion?  Perhaps: each aggregate body records the sum of the charges of its constituent bodies.  Force is applied to each body using the tree as normal.  If the product of the charge at a node is positive then a repulsive force results, otherwise it’s an attractive force.  In turn that force is divided by the body’s mass to determine acceleration.  Mass is irrelevant for an aggregate body as it has no inherent role in electromagnetic force — only the accumulated charge does.  (I’ve qualified this conclusion with a perhaps because it’s untested.)

Finally on that topic: why do both these forces follow a inverse-square law?  One intuitive answer is that the force can be conceived as a continuous (modulo quantum discreteness) stream of force-carrying particles emanating from each piece of matter in all directions.  When a particle meets other matter, it provides a constant packet of acceleration to it whose direction depends on the product of the mass/charges of originating and receiving bodies. The simple fact that the size of the target diminishes by the square of the distance from the source accounts for the relation between distance and force.  Another way of looking at it is as an expanding sphere of particles, whose surface area is proportional to the square of its radius.  For a given sized target the density of the part of the sphere that encounters the target will be the inverse of that part’s area.