Skip to content
Projects

tree_d_3d.kernels.quadtree_build.quadtree_build_pyccel

The Pyccel version (CPU) of the quadtree_build kernel of the tree build.

quadtree_build_numpy.py next to this file is the version for machines without Pyccel, with the same arguments; the folder’s __init__.py declares the kernel (see tree_d_3d.kernels). The flat quadtree is described in tree_d_3d.flat_tree.

Functions

NameDescription
quadtree_buildBuild the tree of the n particles at sorted_pos[:, :n] (n = perm.shape[0]).

quadtree_buildfunction#

def quadtree_build(sorted_pos: float[:, :], leaf_capacity: int, max_depth: int, node_center: float[:, :], node_half: float[:], node_start: int64[:], node_end: int64[:], node_child: int64[:], node_depth: int64[:], perm: int64[:], levels: int64[:], slot_node: int64[:], quadrant: int64[:], cursor: int64[:], new_sorted_pos: float[:, :], new_perm: int64[:], new_slot_node: int64[:], sizes: int64[:]) -> None

Build the tree of the n particles at sorted_pos[:, :n] (n = perm.shape[0]).

On entry node 0 holds the root (node_center[0], node_half[0]) and sorted_pos the positions in input order. A node holding more than leaf_capacity particles above max_depth splits into four children (0..3: upper left, upper right, lower left, lower right), numbered breadth first in the order of their parents; a particle on a dividing line goes left or up, and the particles of a child keep their order. On exit perm lists the particles in tree order, sorted_pos holds their positions in that order (new_sorted_pos, new_perm, new_slot_node, slot_node, quadrant and cursor are scratch), levels[:n_levels + 1] bounds the nodes of each depth, sizes[0] is the node count and sizes[1] the number of levels. If the node arrays (length cursor.shape[0]) are too small, sizes[2] becomes 1 and the tree is unfinished.