Octree

This page documents the internal data structure and the init_octree → split_domain → build → update pipeline that octree drives.

Data layout

A built tree is an instance of Octree. Its fields are:

OctreeNode is an immutable struct:

The non-MVector fields are scalars; because OctreeNode is immutable, mutation is done through Setfield.jl (used internally) and BangBang.jl's setproperties!! / setproperty!!.

The build pipeline

┌──────────────┐    ┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ init_octree  │ →  │ split_domain │ →  │     build    │ →  │    update    │
└──────────────┘    └──────────────┘    └──────────────┘    └──────────────┘
   on every pid       Peano-decompose       Recurse, place      Mass / Center /
   (config + e +      the work into        particles into      NextNode / Sibling
   units)             NTopLeaves             leaves             + fill pseudo
                                                                  leaves

Step 1 — init_octree

init_octree(data, units, config::OctreeConfig, pids::Array{Int64,1})

Computes the global extent, expands it by config.ExtentMargin, computes the per-worker DomainFac, and registers an empty Octree in the local PhysicalTrees.registry. All workers are reached via Distributed.remotecall_eval so the master never directly owns the master's tree when the master is not in pids.

Step 2 — split_domain

Each worker:

1. Sorts its local data by peanokey.
2. Builds a top tree of TopNodes describing the local per-leaf particle counts.
3. Walks the top tree downward (split_topnode_local_kernel) until every leaf has Count <= NumTotal / (TopnodeFactor * NWorkers²).
4. Walks the global top tree to assign each leaf a worker (find_split).
5. Ships the particles / peano keys to the assigned worker (fill_domain_buffer, send_buffer, clear_domain_buffer).

After this stage every worker owns exactly the particles that the top-tree DomainTask assigned to it, in Peano-sorted order.

Step 3 — build

1. init_treenodes — allocates the root treenode and recursively carves the empty top tree into the local treenode array (create_empty_treenodes).
2. insert_data — walks each particle down the local top tree and writes it into the deepest unoccupied leaf (assign_data_to_tree_leaf). When two particles end up in the same leaf, assign_new_tree_leaf is invoked to split it.
3. insert_data_pseudo — attaches a pseudo leaf to each remote top-node leaf. The pseudo leaf stores the aggregated mass and mass center of the remote subtree, so the local tree can resolve gravity / SPH contributions from remote particles.

Step 4 — update

1. update_local_data walks the local tree depth-first to compute Mass, MassCenter, MaxSoft, NextNode and Sibling for every node.
2. fill_pseudo_buffer serializes the local top-tree leaf moments.
3. update_pseudo_data merges the pseudo-leaf moments into the local top tree, re-aggregating Mass / MassCenter / MaxSoft from root to leaves.
4. flag_local_treenodes marks the top-level / local-partition subtrees with bit flags so search routines can short-circuit leaves that contain no relevant data.

Periodic boundary conditions

When config.Periodic == true the search routines apply a minimum-image convention via ngb_periodic_diff. The relevant differences are:

• check_incube_periodic replaces check_incube inside ngb_treefind_variable / ngb_treefind_pairs so a particle whose periodic image falls inside the search cube is included.
• ngb_periodic_diff maps a raw coordinate difference into the half-open range (-boxHalf, boxHalf].
• BoxSize must match the underlying physical box — the tree's mutable.extent.SideLength is set by config.ExtentMargin and can be much larger than the physical box.

Side-length maintenance

After particle positions drift (SPH integration, gravity kicks, …), the tree's SideLength may no longer enclose its assigned particle or its children. Call update_node_len:

This is the Julia equivalent of Gadget-2's force_update_node_len_local. It performs two sweeps:

1. Leaf pass — for every treenode with a non-zero ParticleID, ensure SideLength >= 2 * max(|Pos - Center|).
2. Internal-node pass (high → low index) — for every non-leaf, ensure SideLength >= 2 * (max over children of |Center_child - Center_parent| + SideLength_child / 2).

For a full rebuild (e.g. after re-gridding), use rebuild:

rebuild runs global_extent → split_domain → build → update against the existing tree.data. Use it when the data geometry has changed substantially (e.g. after a load-balancing step or a redistribute); use update_node_len for the common case of small per-step drift.

Distributing and unregistering

unregister(tree) removes tree.id from each worker's PhysicalTrees.registry and from the master. After unregister, accessing the old id raises a KeyError.

To wipe all trees at once (e.g. when tearing down a long-lived session), use clear(workers()) (the lowercase clear is PhysicalTrees.clear; it's not exported to avoid clashing with Base.clear).

Tree serialization and debugging

summary returns a human-readable string of every top-level field:

io = IOBuffer()
show(io, tree)
String(take!(io))

Base.show(::IO, ::OctreeNode) prints a single line per node (id, parent, daughters, mass, mass-center, …). These are used heavily by the test suite as well as by AstroPlot.plot_tree.

Field-level invariants

After a successful octree(...) call, the following must hold:

• length(treenodes) == config.TreeAllocSection or the array has been grown to accommodate the tree depth.
• For every non-leaf node n, n.SideLength divides into n.DaughterID's children's SideLength * 2 (geometric halving).
• For every assigned leaf n, data[n.ParticleID].Pos lies inside the cube [n.Center ± n.SideLength/2]³.
• tree.mutable.NumTotal == length(data); tree.mutable.NumLocal is the number of particles on this worker.

Violations of these invariants mean update_node_len (or rebuild) should be called before the next search.