Methods

allocate_tree_if_necessary(tree::Octree)

If nextfreenode getting close to the length of treenodes, append treenodes with TreeAllocSection empty nodes

assign_data_to_tree_leaf(tree::Octree, index::Int, p::AbstractParticle)
assign_data_to_tree_leaf(tree::Octree, index::Int, p::AbstractPoint)

When inserting to an empty node, simply copy data and change IsAssigned to true

assign_new_tree_leaf(tree::Octree, parent::Int)

When trying to insert into a leaf witch already has been assigned with a particle, first generate a new internal node at this point and copy the old data to a new subnode, then continue to insert the new data in the next routine.

build(tree::Octree)

Procedures to build an octree:

1. Allocate tree node memories and initialize
2. Insert local data
3. Insert remote toptree leaves

check_in_box(Pos::PVector, Center::PVector, SideLength::Number)

Chech whether Pos is inside the box, which is centered at Center with sidelength SideLength. Used during tree construction only — for runtime neighbor tests see check_incube (same name, different argument semantics: SideLength versus half_len).

function clear(pids = procs())

Clear distributed memories in PhysicalTrees.registry

count_leaves(tree::Octree)

Count local toptree leaves

create_empty_treenodes(tree::Octree, no::Int64, top::Int64, bits::Int64, x::Int64, y::Int64, z::Int64)

Create an octree with empty nodes in the same structure with toptree

fill_domain_buffer(tree::Octree)

Send particle alongside its peano key to the designated process.

find_subnode(Pos::PVector, Center::PVector)
find_subnode(p::AbstractParticle, Center::AbstractPoint)

From the Center cut the domain into eight regions, and index from 1 to 8. Return the domain index that Pos of p.Pos lies in.

Domain indexing

finish_last(tree::AbstractTree)

Close the last NextNode indexing

init_peano(tree::Octree)

1. Count local number of data
2. Compute domain.mutable.DomainFac
3. Compute peano keys of local data
4. Sort peano keys and store in domain.peano_keys

init_topnode(tree::Octree)

Allocate domain.topnodes, set up the first topnode and count NTopnodes from 1

insert_data(tree::Octree)

Insert all data to the octree one by one.

insert_data_pseudo(tree::Octree)

Insert remote toptree leaves.

next_treeid()

Produces an incrementing ID that will be used for trees.

function ratio(tree::AbstractTree)

Amount of leaves / amount of branches

update(tree::AbstractTree)

Compute total mass and mass center of tree nodes, and communicate results between workers

update_local_data(tree::AbstractTree)

Compute total mass and mass center of local nodes

update_pseudo_data(tree::AbstractTree)

Copy total mass and mass center of remote nodes to local treenodes

update_treenodes_kernel(tree::AbstractTree, no::Int64, sib::Int64, father::Int64)

Recursively compute total mass and mass center of each node

walk_toptree(tree::Octree, no::Int64)

Count toptree leaves and store leaf id

octree(data; units = uAstro, config = OctreeConfig(length(data)), pids = workers())

Build an octree from data over the workers pids.

data may be a Vector{<:PVector} (positions only), a StructArray{<:AbstractParticle} (e.g. Star, Massless), or any iterable compatible with extent. The tree is built in four stages: init_octree → split_domain → build → update.

Keyword arguments

• units::Vector{Unitful.FreeUnits} or nothing — internal unit system. Pass nothing for unitless data; defaults to uAstro.
• config::OctreeConfig — build parameters (BoxSize, Periodic, MaxTopnode, …). Defaults to OctreeConfig(length(data)).
• pids::Vector{Int} — workers the tree should live on. The master is included only if myid() ∈ pids. Defaults to workers().

Examples

julia> using PhysicalTrees, PhysicalParticles, Unitful, UnitfulAstro

julia> pos = [PVector( 1.0,  1.0,  1.0, u"kpc"),
            PVector(-1.0, -1.0, -1.0, u"kpc"),
            PVector( 1.0,  0.0, -1.0, u"kpc"),
            PVector(-1.0,  0.0,  1.0, u"kpc"),
            PVector( 0.0,  0.0, -1.0, u"kpc"),
            PVector(-1.0,  0.0,  0.0, u"kpc")];

julia> tree = octree(pos);

See also rebuild, unregister, OctreeConfig.

rebuild(tree::Octree)

Re-run the full build pipeline against the existing tree.data, without re-shipping the particles across workers. Use this when the data has changed substantially but the worker set is unchanged (e.g. after a load-balancing step).

The pipeline is the same as octree: global_extent → split_domain → build → update.

Example

tree = octree(particles, pids = workers());
# … move particles in `tree.data` …
rebuild(tree);

unregister(tree::AbstractTree)

Remove tree.id from every worker's PhysicalTrees.registry and from the master. After this call the tree's id is no longer valid; the per-worker memory will be reclaimed by Julia's GC.

If you want to wipe every tree (e.g. before constructing a fresh one with a recycled id), use PhysicalTrees.clear(workers()).

Example

tree = octree(particles, pids = workers());
# … use the tree …
unregister(tree);

update_node_len(tree::AbstractTree)

Walk the local tree and enlarge every node whose SideLength is too small to contain its descendants.

update_node_len is meant to be called after particles have moved within the tree (for example after a few SPH time steps) but before the next search / SPH pass. It performs the equivalent of Gadget2's force_update_node_len_local:

1. For each assigned leaf, recompute SideLength so the actual particle position (tree.data[ParticleID].Pos) lies inside the cube (SideLength >= 2 * max(|Pos - Center|)).
2. Walk up to the root, expanding each ancestor so it can enclose all of its children (`SideLength >= 2 * (|Centerchild - Centerparent|
   • SideLength_child / 2)`).

The function is broadcast across workers so each rank updates its local copy of the tree.

global_extent(tree::AbstractTree)

Compute global extent of all particles and broadcast the result.

procs(tree::AbstractTree) -> Vector{Int}

Return the worker pids the tree is distributed over.

send_buffer(tree::AbstractTree)

Block until every peer task has shipped its sendbuffer into this task's recvbuffer. The traversal is ordered (the local pid is moved last) so the buffer exchange happens with reduced contention.

This is the helper used during split_domain / the periodic domain exchange. Most users should not need to call it directly.

peanokey(x, y, [z]; bits) -> Int128
peanokey(p::AbstractPoint, Corner::AbstractPoint, DomainFac, bits) -> Int128
peanokey(data, Corner, DomainFac, bits) -> Vector{Pair{Int128, Ref}}

Compute a Peano-Hilbert key for one or many points. The 2D / 3D integer overloads are the low-level routines (adapted from GeometricalPredicates.jl / Gadget-2); the AbstractPoint overloads quantize a position against Corner / DomainFac and then dispatch to them; the array overload maps the per-particle function over data and returns the peano_keys array used by split_domain to sort the local particles.

bits controls the Peano bit length per axis. The default (peano_2D_bits = 31 / peano_3D_bits = 21) is what Gadget-2 uses and gives a 63- / 63-bit key — large enough that neighbouring cells have keys that differ by a small multiple of the cell index.

check_incube(Pos, Center, half_len)

Return true if Pos lies inside the axis-aligned cube centered at Center with half side length half_len. Works for both unitful and unitless AbstractPoint types.

check_incube_periodic(Pos, Center, half_len, boxHalf, boxSize)

Periodic-aware variant of check_incube. A particle is considered inside the cube if its nearest periodic image lies inside the cube centered at Center with half side length half_len. This is the correct test for Periodic trees, where a particle can wrap around the box and still be a neighbor.

The original ngb_treefind_* family only applied min-image to the secondary sphere test, so a particle whose raw position was outside the cube but whose periodic image was inside was silently dropped.

check_insphere(Pos, Center, radius)

Squared-distance sphere test. Pos and Center should share the same unit (or both be dimensionless). Returns true iff |Pos - Center| ≤ radius.

ngb_periodic_diff(dx, boxHalf, boxSize)

Map a raw coordinate difference dx to the nearest periodic image, i.e. into the range (-boxHalf, boxHalf]. Works for both unitful and unitless Numbers. Inputs must be commensurate (callers that mix Quantity and bare Float64 should ustrip first).

ngb_treefind_variable(center, hsml, tree; startnode=1) -> Vector{Int}

Return indices of every local particle within a cube (and, for Periodic trees, a sphere) of side 2 * hsml around center.

The returned indices are the local particle ids in the current task (1..NumLocal). Use search_inbox_local when you also need to know which remote tasks own additional candidates.

Keyword arguments

• startnode: tree-node id at which to start the walk. Defaults to the root (1); callers may resume from a previously saved nextfreenode for SPH buffer-oversize recovery.

Unit handling

When tree.units is nothing, all center/hsml arguments are dimensionless. Otherwise, hsml should carry the same length unit used to build the tree.

ngb_treefind_pairs(center, hsml, tree; startnode=1) -> Vector{Int}

Asymmetric neighbor search (a.k.a. "pairs") used by SPH, where the search radius is enlarged by max(0, h_j - hsml) for every node containing particles of varying smoothing length.

Particles are returned if |Pos_j - center| ≤ hsml + max(0, h_j - hsml).

For particles without a per-particle smoothing field this collapses to ngb_treefind_variable.

ngb_treefind_all(tree, hsml) -> Vector{Vector{Int}}

Walk the tree once and produce the neighbor list of every local particle. The result is a length-NumLocal vector of Vector{Int}, where the i-th entry contains the indices (1..NumLocal) of all particles within hsml of particle i.

This is the O(N log N) routine that SPH solvers (see PhysicalSPH.SPHFluidSolver) can use to replace the naive O(N²) double loop. When hsml differs per particle, use ngb_treefind_pairs_all.

hsml may be either a scalar (constant smoothing length) or a vector of length NumLocal (per-particle smoothing length).

ngb_treefind_pairs_all(tree, hsml) -> Vector{Vector{Int}}

Asymmetric variant of ngb_treefind_all (the SPH "pairs" search). Both scalar and per-particle hsml are supported; the search radius for particle i is enlarged to hsml_i + max(0, hsml_j - hsml_i) to match Gadget2's ngb_treefind_pairs semantics.

search_inbox_local(center, halflen, tree; startnode=1) -> (ngblist, ExportFlag)

Locally compute the neighbor list of center inside the cube of half side length halflen and record which remote tasks own additional candidates (ExportFlag[pid] = true).

If tree.config.Periodic is true, the cube is also clipped to the periodic box (using minimum-image convention) so a particle exactly on the boundary is still matched.

The returned ngblist contains local particle indices (1..NumLocal). The caller is responsible for merging in remote candidates — see search_all_parallel for a higher-level wrapper that does this automatically.

search_inradius_local(center, radius, tree; startnode=1) -> (ngblist, ExportFlag)

Like search_inbox_local but prunes tree nodes with a true cube-sphere test and only retains particles strictly inside the sphere of radius radius around center. Periodic minimum-image is honored when tree.config.Periodic is true.

search_all_parallel(center, hsml, tree; use_pairs=false) -> Vector{Int}

Run a parallel neighbor search around center and return the combined list of local + remote candidate particle indices (local numbering preserved on each side; remote indices are still 1-based on the owning worker — see split_data for the mapping).

Internally calls search_inbox_local, exports the request to every flagged task via ParallelOperations.sendto, and merges the results.

Keyword arguments

• use_pairs::Bool: if true, dispatch to ngb_treefind_pairs on each worker; if false (default), use ngb_treefind_variable.

On a single-pid tree this is equivalent to ngb_treefind_variable / ngb_treefind_pairs.

ngb_clear_buf(center, hsml, ngblist, tree) -> Vector{Int}

Truncate ngblist to only contain particles inside the sphere of radius hsml around center. Periodic minimum-image convention is honored when tree.config.Periodic is true.

This is the cheap post-filter used by the SPH density pass: a ngb_treefind_variable (or ngb_treefind_pairs) gives a cube over-estimate, and ngb_clear_buf cuts it down to a sphere without a second tree walk.

density_evaluate(target_idx, center, hsml, tree; mode=0) -> Vector{Int}

Convenience wrapper used by SPH density loops.

Keyword arguments

• mode::Int:
  • 0 (default): return every cube-neighbor. The caller is responsible for applying the sphere cut (or any kernel cutoff).
  • 1: also apply the sphere cut via ngb_clear_buf.

The first positional argument target_idx is currently unused but kept for API symmetry with downstream consumers (e.g. SPHFluidSolver) that want to know which local particle is the SPH "center".