Benchmarks for tf::tree construction and spatial queries. See experimental setup for methodology.

Point Clouds

Tree Construction

Construction time for spatial index structures over mesh vertices. TrueForm builds trees with AABB, OBB, and OBBRSS bounding volumes; nanoflann builds a k-d tree. Each configuration is measured 10 times; the min is reported.

Source: TrueForm, nanoflann

Point Cloud Tree Construction

TF AABB

TF OBB

TF OBBRSS

Point Cloud Tree Construction (Speedup)

vs

TrueForm AABB tree construction is 7× faster than nanoflann's k-d tree at 1M points, while also supporting OBB and OBBRSS bounding volumes.

k-Nearest Neighbor

Query time for k nearest neighbors. Query points are generated by adding uniform random offsets (within 1% of bounding box diagonal) to mesh vertices. For each mesh size, 1000 queries are executed; the mean time per query is reported. Results shown for k=10.

Source: TrueForm, nanoflann

k-Nearest Neighbor Query (k=10)

k-Nearest Neighbor Speedup (k=10)

vs

TrueForm k-NN queries are 3× faster than nanoflann at 500K points.

Polygon Meshes

BVH Construction

Construction time for bounding volume hierarchies over triangle meshes. TrueForm trees use arity 4 and leaf size 4. Each configuration is measured 10 times; the min is reported.

AABB

Tree using axis-aligned bounding boxes. TrueForm is compared against CGAL AABB trees, FCL BVHModel<AABB>, and Coal BVHModel<AABB>.

Source: TrueForm, CGAL, FCL, Coal

BVH Construction (AABB)

FCL

Coal

BVH Construction AABB (Speedup)

vs

vs FCL

vs Coal

TrueForm AABB tree construction is 21× faster than FCL, 15× faster than CGAL, and 14× faster than Coal at 1M polygons.

OBB

Tree using oriented bounding boxes. TrueForm is compared against FCL BVHModel<OBB> and Coal BVHModel<OBB>.

Source: TrueForm, FCL, Coal

BVH Construction (OBB)

FCL

Coal

TrueForm OBB tree construction is 30× faster than FCL and 26× faster than Coal at 1M polygons.

OBBRSS

Tree using a hybrid of oriented bounding boxes and rectangle swept spheres. TrueForm is compared against FCL BVHModel<OBBRSS> and Coal BVHModel<OBBRSS>.

Source: TrueForm, FCL, Coal

BVH Construction (OBBRSS)

FCL

Coal

TrueForm OBBRSS tree construction is 27× faster than FCL and 24× faster than Coal at 1M polygons.

Mesh-to-Mesh Distance

Minimum distance computation between two copies of the same mesh. The second mesh is placed at a random rigid transform sampled uniformly within a sphere of radius equal to twice the bounding box diagonal. For each mesh size, 1000 random configurations are evaluated; the mean query time is reported. TrueForm uses tf::neighbor_search on polygon forms; FCL uses fcl::distance() and Coal uses coal::distance() with the corresponding BVHModel<BV>.

AABB

Using axis-aligned bounding boxes. Coal is excluded from this comparison as its AABB distance queries are slower than FCL (see OBBRSS for Coal results).

Source: TrueForm, FCL

Mesh-to-Mesh Distance (AABB)

FCL

TrueForm mesh-to-mesh distance queries with AABB are 469× faster than FCL at 1M polygons per mesh.

OBBRSS

Using a hybrid of oriented bounding boxes and rectangle swept spheres.

Source: TrueForm, FCL, Coal

Mesh-to-Mesh Distance (OBBRSS)

FCL

Coal

TrueForm mesh-to-mesh distance queries with OBBRSS are 2× faster than FCL and Coal at 1M polygons per mesh. The smaller gap compared to AABB reflects that OBBRSS provides tighter bounds, reducing the number of primitive tests for all libraries.

Incremental Tree Updates

Update time for tf::mod_tree when a contiguous region of primitives changes. Dirty primitives are selected by growing a region from a random seed vertex via BFS, simulating localized edits. The tree prunes affected nodes and rebuilds only the delta.

Source: TrueForm

The efficiency chart below shows the ratio of dirty percentage to update percentage. A value of 1.0 means perfect scaling: updating X% of primitives takes X% of full build time.

Efficiency improves with both mesh size and dirty percentage. At low dirty percentages (1–5%), there is a fixed overhead from tree traversal and delta management, resulting in efficiencies of 0.3–0.6. As the dirty region grows, this overhead is amortized: at 40% dirty, efficiency approaches 0.9–1.0 across all mesh sizes.

Larger meshes benefit more from incremental updates. At 1M polygons, the fixed overhead is only ~1.3%, making incremental updates worthwhile even for small localized changes.