`octree.h`#

#include <sif/structures/octree.h>

SIF_STRUCTURES_OCTREE_H#

Adaptive octree over a particle field, for neighbour queries on clustered data.

Where the chain mesh divides space uniformly, this subdivides only where particles are, so a query cost tracks the local density instead of the box volume. That is what makes it the right structure for a field with voids and filaments and the wrong one for a nearly uniform field, where the mesh is cheaper and simpler.

Nodes carry a contiguous particle range rather than a list of members, which is possible only because the field is Morton-sorted: Morton order is depth-first octree order, so every subtree occupies one slice of the arrays. The tree is therefore an index into the field, and both must be passed to every query.

struct sif_octree_node_t#

One node: either a leaf, or an internal node with eight children.

The eight children of a node are consecutive, so one index locates all of them and the whole tree is a flat array rather than a web of pointers.

uint32_t first_child#: Index of the first of eight consecutive children, or UINT32_MAX for a leaf.

uint32_t p_start#: First particle of this node’s range, indexing the Morton-sorted field.

uint32_t p_counting#: Particles in the range.

uint32_t padding#: Unused; keeps the node at 16 bytes so four fit in a cache line.

struct sif_octree_t#

An octree over one field.

sif_octree_node_t *nodes#: Flat node array; the root is nodes[0].

uint32_t capacity#: Nodes allocated.

uint32_t count#: Nodes in use.

sif_real root_center[3]#: Centre of the root cube, from the field.

sif_real root_half_span#: Half-side of the root cube.

sif_octree_t *sif_octree_alloc(sif_field_t *field, uint32_t max_per_leaf)#

Build an octree over a field.

Subdivides until every leaf holds at most max_per_leaf particles, or until the Morton resolution runs out – coincident particles cannot be separated and stop the recursion early, so a leaf may exceed the threshold.

Parameters:

field – Field to index. Modified: the tree requires Morton order and valid bounds, so both are established on the field if they are not already present, which physically reorders its arrays.
max_per_leaf – Particles a leaf may hold before it splits. Larger values make a shallower tree that scans more particles per leaf; the useful range is tens.

Returns:

The tree, owned by the caller and released with sif_octree_free(). NULL on invalid input or allocation failure.

Warning

The tree indexes the field by position and stays valid only as long as the field is not reordered or resized under it. Anything that re-sorts or re-assigns the field invalidates the tree.

void sif_octree_free(sif_octree_t *tree)#

Release an octree.

Parameters:

tree – Tree to free. NULL is accepted and ignored. Does not free the field.

uint64_t sif_octree_find_nearest(const sif_octree_t *tree, const sif_field_t *field, sif_real px, sif_real py, sif_real pz)#

Index of the particle nearest a point.

Descends to the point’s own leaf first, then unwinds, skipping any subtree whose cube is farther than the best candidate so far.

Parameters:

tree – The tree.
field – The field it was built over.
px – Query point, x axis.
py – Query point, y axis.
pz – Query point, z axis.

Returns:

Index into the Morton-sorted field. Use sif_field_t::original_indices to map it back to the caller’s input order.

Note

Open boundaries: separations are taken directly, not through periodic images. Use sif_chain_mesh_find_nearest_pbc() where the box wraps.

uint64_t sif_octree_search_radius(const sif_octree_t *tree, const sif_field_t *field, sif_real px, sif_real py, sif_real pz, sif_real radius, uint64_t *out_indices, uint64_t max_capacity)#

Every particle within a radius of a point.

Parameters:

tree – The tree.
field – The field it was built over.
px – Centre, x axis.
py – Centre, y axis.
pz – Centre, z axis.
radius – Search radius.
out_indices – Written with the indices found, into the Morton-sorted field.
max_capacity – Entries out_indices can hold.

Returns:

The number of particles found, which may exceed max_capacity when the output was truncated – compare the two to detect it, and note that only the first max_capacity indices were written.

uint64_t sif_octree_search_box(const sif_octree_t *tree, const sif_field_t *field, sif_real min_x, sif_real min_y, sif_real min_z, sif_real max_x, sif_real max_y, sif_real max_z, uint64_t *out_indices, uint64_t max_capacity)#

Every particle inside an axis-aligned box.

Parameters:

tree – The tree.
field – The field it was built over.
min_x – Lower bound, x axis.
min_y – Lower bound, y axis.
min_z – Lower bound, z axis.
max_x – Upper bound, x axis.
max_y – Upper bound, y axis.
max_z – Upper bound, z axis.
out_indices – Written with the indices found, into the Morton-sorted field.
max_capacity – Entries out_indices can hold.

Returns:

The number of particles found; see sif_octree_search_radius() on truncation.

octree.h#

`octree.h`#