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 mean 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 mean is reported.

AABB

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

Source: TrueForm, CGAL, FCL

BVH Construction (AABB)

FCL

BVH Construction AABB (Speedup)

vs

vs FCL

TrueForm AABB tree construction is 23× faster than FCL and 15× faster than CGAL at 1M polygons.

OBB

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

Source: TrueForm, FCL

BVH Construction (OBB)

FCL

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

OBBRSS

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

Source: TrueForm, FCL

BVH Construction (OBBRSS)

FCL

TrueForm OBBRSS tree construction is 35× faster than FCL 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() with the corresponding BVHModel<BV<double>>.

AABB

Using axis-aligned bounding boxes.

Source: TrueForm, FCL

Mesh-to-Mesh Distance (AABB)

FCL

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

OBBRSS

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

Source: TrueForm, FCL

Mesh-to-Mesh Distance (OBBRSS)

FCL

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