# Welcome to boxtree’s documentation!¶

boxtree is a package that, given some point locations in two or three dimensions, sorts them into an adaptive quad/octree of boxes, efficiently, in parallel, using OpenCL. It also computes geometric lookup tables and generates FMM interaction lists.

Other places on the web to find boxtree stuff:

Now you obviously want to watch the library do something (at least mildly) cool? Well, sit back and watch:

import pyopencl as cl
import numpy as np
from six.moves import range

ctx = cl.create_some_context()
queue = cl.CommandQueue(ctx)

dims = 2
nparticles = 10**4

# -----------------------------------------------------------------------------
# generate some random particle positions
# -----------------------------------------------------------------------------
from pyopencl.clrandom import RanluxGenerator
rng = RanluxGenerator(queue, seed=15)

from pytools.obj_array import make_obj_array
particles = make_obj_array([
rng.normal(queue, nparticles, dtype=np.float64)
for i in range(dims)])

# -----------------------------------------------------------------------------
# build tree and traversals (lists)
# -----------------------------------------------------------------------------
from boxtree import TreeBuilder
tb = TreeBuilder(ctx)
tree, _ = tb(queue, particles, max_particles_in_box=30)

from boxtree.traversal import FMMTraversalBuilder
tg = FMMTraversalBuilder(ctx)
trav, _ = tg(queue, tree)



This file is included in the boxtree distribution as examples/demo.py. With some plotting code (not shown above, but included in the demo file), you can see what’s going on:

More importantly, perhaps, than being able to draw the tree, the boxtree.Tree data structure is now accessible via the tree variable above, and the connectivity information needed for an FMM-like traversal is available in trav as a boxtree.traversal.FMMTraversalInfo.