McNett

Overview

Buckytree is an implicit data structure for O(NlogN) spatial sort and O(logN)? spatial search of dimensional objects. Because the data structure is implicit, no spatial index is required. When present, the spatial index can be a simple array without pointers.

The name “buckytree” is a reference to the “buckyball” and “buckytube” carbon allotropes named for R. Buckminster Fuller.

Previous Work

Buckytree is similar to LBVH (Lightweight Bounding Volume Hierarchy,) BIH (Bounding Interval Hierarchy) and k-DOP (discrete oriented polytope,) in that it partitions objects by the planes of a convex polytope. Buckytree, however, does not partition objects by intervals, and requires no spatial index.

In a buckytree, the “min” half of each interval is stored in the spatial index or computed at search time, and the “max” half lives in the search query.

Buckytree is also related to k-d tree, which can be an implicit data structure for dimensionless objects (points,) but not for dimensional objects because it supports no concept of interval.

The Algorithm

The algorithm consists of sort function “buckysort” and search function “buckysearch.” We begin by contemplating a 2D explicit buckytree, for simplicity of explanation. The algorithm extends to 3D and higher dimensions.

The algorithm requires axis vectors, positive linear combinations of which fill space. [ A, B, C ], the vertices of an equilateral triangle, meet this requirement (see below.)

[ X, -X, Y, -Y ] also meet this requirement and are well-known as AABB, but [ A, B, C ] better illustrate the novelty of the algorithm, which sees no special relationship between X and -X.

Buckysort

For each object to be sorted, transform all its vertices from [ X, Y ] axes into [ A, B, C ] axes. This can be done with the following math:

Now, find the [ min(A), min(B), min(C) ] coordinates of one object. Just like how [ min(X), max(X), min(Y), max(Y) ] forms a bounding box, [ min(A), min(B), min(C) ] forms a bounding triangle around the object:

Do this for each object to be searched, and store one set of [ min(A), min(B), min(C) ] values per object into an array:

Now to sort the triangles with buckysort.

Calculate, for the set of all triangles, the maximum and minimum values of min(A), min(B) and min(C). Whichever axis has the largest spread between minimum and maximum values is chosen as the splitting axis.

Once the splitting axis is chosen, search the set of triangles for the triangle which min(axis) value is closest to ( maximum - minimum ) / 2. This is chosen as the splitting triangle.

Partition the triangles such that every triangle to the right of the splitting triangle has a min(axis) value no greater than the splitting triangle, and every triangle to the left has a min(axis) value no lesser. This takes average linear time.

In an auxiliary array, store the splitting axis and splitting triangle index at offset zero.

Consider the splitting triangle to be “done”, and perform the algorithm recursively on the left and right sides of the splitting triangle.

On the left side of the splitting triangle, store the splitting axis & index at auxiliary array offset ( zero * 2 ) + 1. On the right side, store the splitting axis & index at auxiliary array offset ( zero * 2 ) + 2.

Once all triangles are “done,” buckysort is done.

Now that the array is sorted, let’s search for intersections with buckysearch.

Buckysearch

First, take the search object ( a triangle, a box, a mesh, whatever ) and transform its vertices from [ X, Y ] axes into [ A, B, C ] axes.

Find the [ max(A), max(B), max(C) ] coordinates of the vertices. Just like how [ min(X), max(X), min(Y), max(Y) ] forms a bounding box, [ max(A), max(B), max(C) ] forms an upside-down bounding triangle - a mirror image of the [ min(A), min(B), min(C) ] triangles from before:

In the auxiliary array, read the splitting axis and splitting triangle index from index zero. Recurse left of the splitting triangle. Test the [ max(A), max(B), max(C) ] triangle against min(splitting axis) in triangle[splitting index]. If max(axis) < min(axis), stop now. Otherwise, test the entire [ max(A), max(B), max(C) ] triangle against the splitting triangle’s [ min(A), min(B), min(C) ]. If any max(axis) < min(axis), reject the splitting triangle. Recurse right of the splitting triangle.

Any time you recurse left, the new auxiliary array index is ( old index * 2 + 1 ). Recurse right, and the new index is ( old index * 2 + 2 ).

Possible Optimizations

For very large databases, a “buckytree of buckytrees” - a buckytree in which each node bounds another, smaller buckytree - may utilize cache better than a buckytree of triangles, etc.

Because the spatial index represents minimum bounds, its values can be rounded down for quantization without making the algorithm numerically unstable. In practice, object databases in videogames require no more than 8 or 16 bits per scalar value.

For data that is very unevenly distributed in space, it may be wise to choose the best axis at each step, rather than automatically proceed through A, B, C, A, etc.

Source Code

Here’s C++ source code for an implicit buckytree of spheres bounded by AABB. No memory is used for a spatial index, but this results in more branching and less parallelism.

http://www.mcnett.org/sphere.cpp

…and this is an explicit buckytree of spheres bounded by AABB. For each 16-byte sphere, 6 more bytes are spent on a spatial index to hold an AABB. The AABB is a loose fit, but the goal is to efficiently reject a vast majority of faraway objects, not to efficiently reject a tiny minority of nearby objects. This code has been optimized for N-way parallel AABB checks.

http://www.mcnett.org/simd.cpp

Here’s pseudocode of implicit buckytree for a bunch of simple dimensional primitives:

http://www.mcnett.org/sphere.txt

http://www.mcnett.org/polytope.txt

http://www.mcnett.org/triangle.txt

Notes

Buckytree is efficient for ray tracing. The ray must be clipped to a line segment before buckysearch, then follow these steps:

1. Recurse left.

2. If median min(A) > line segment max(A), stop now

3. If the line segment crosses the median min(A) plane, clip it to min(A) and recalculate line segment [ max(A), max(B), max(C) ].

4. If none of median [ min(A), min(B), min(C) ] are greater than line segment [ max(A), max(B), max(C) ], add median to potential intersections

5. Recurse right.