Thinking about the Octree

The k-d tree is a related idea. A very quick web search: There are many papers out there about using octrees to do gravity stuff. I suppose distant cubies can be replaced by their point mass equivalent. Intermediate distances by dipole, quadripole etc approximations—N-body stuff.

Data Structures

Abstract BNF

A node is either:

Concrete BNF 1

A <node> is either: This is efficient to scan if we need to visit the entire tree. It is inefficient to scan in order to find a node with given coordinates. It is inefficient to mutate.

This is a dense form.

Concrete BNF 2

Linked list: “<node>” is address or index into array of nodes. Presumably no nodes occur twice. Except now the empty state merely points eight times to ‘the’ empty cube ⅛ of the current size. Ditto the full cube. Indeed the full cube can point to itself, and an empty cube to itself.

This is a mutable and navigable form.

The most frequent instance of this form is the bottom which points only to 8 empty or full descendants. It is dumb to use 256 bits to convey 8 bits of information. We could afford and allocate 256 elements in item space for these common patterns and share them. Then the code might be more uniform.

In this scheme the abstract states E and F are absent. The trees loop and are thus infinite. Code stops at a depth of its choosing.

Some cursor formats

I think we need a cursor which denotes node. Either of both of:

Octal number
Sequence of chars from “01234567”, as long as depth. Works for both tree forms.
List
Linked list pointing towards root, of node pointers (Like the stack of a recursive visitor). Fields: See Same Fringe problem. Works for BNF 2.

An Organizing Idea

We want to call our messy function u (here) only for corners, where the ‘corner sum’ is not 0. The augends of such a sum may come from places in the octree that are distant from each other. It may not be important to avoid such calls but deciding when it is too distant makes a hard problem even harder.

The simpler plan is to virtually pass over lexically the fine mesh of points with integer coordinates, carrying four tree cursors (see above). Then all eight cubies are at hand to make any contributions to a corner sum. There are a lot of lattice points but when we are not near the surface our reports from the tree (via the cursor) will dictate large steps. As we proceed along some coordinate for some fixed x and y, we step z according to the minimum size reported by the 4 adjacent tree cursors. Notes on code to do this

This may be critical to octree logic!