trueform

Modules | C++

Spatial

Trees, forms, search, neighbor queries, and ray casting.

The Spatial module extends primitive-range queries with spatial structures and transforms via tf::tree and tf::form.

Include the module with:

#include <trueform/spatial.hpp>

Spatial Structures

Spatial structures accelerate queries by organizing primitives into hierarchies.

tf::tree

tf::tree<Index, BV> is a high-performance spatial hierarchy designed for real-time geometry queries, introduced in:

Žiga Sajovic, Dejan Knez, and Robert Korez. tf::tree: A General-Purpose Spatial Hierarchy for Real-Time Geometry Queries.Institute of Electrical and Electronics Engineers (IEEE), June 2025. https://doi.org/10.36227/techrxiv.174952959.92977743/v1

The tree is parameterized by an index type and a bounding volume (BV) type. Convenience aliases are provided for common bounding volumes:

Alias	Equivalent
`tf::aabb_tree<Index, RealType, Dims>`	`tf::tree<Index, tf::aabb<RealType, Dims>>`
`tf::obb_tree<Index, RealType, Dims>`	`tf::tree<Index, tf::obb<RealType, Dims>>`
`tf::obbrss_tree<Index, RealType, Dims>`	`tf::tree<Index, tf::obbrss<RealType, Dims>>`

While aabb_tree supports arbitrary dimensions, obb_tree and obbrss_tree are restricted to 2D and 3D.

Choosing a Bounding Volume

BV Type	Build Speed	Best For
`aabb`	Fastest	General-purpose queries, ray casting, self-intersection, collision detection
`obb`	Moderate	Proximity queries between meshes
`obbrss`	Slowest	Proximity queries between meshes

For most applications, aabb_tree provides the best overall performance—including collision detection between meshes. Use obb_tree or obbrss_tree for nearest-neighbor and proximity searches between two meshes, where tighter bounding volumes significantly improve query culling.

Building the Tree

To construct a tree, provide a primitive range and a configuration specifying the arity (number of children per node) and the maximum number of primitives in a leaf.

build_tree.cpp

tf::aabb_tree<int, float, 3> tree(primitive_range, tf::config_tree(4, 4));
// or
tree.build(primitive_range, tf::config_tree(4, 4));

Empirically, the configuration (4, 4) offers the best performance across workloads.

Partitioning Policies

Tree construction uses a partitioning strategy analogous to std::nth_element. We support several selection-based algorithms:

tf::spatial::floyd_rivest_t
tf::spatial::pdq_t
tf::spatial::median_of_medians_t
tf::spatial::median_of_ninthers_t
tf::spatial::median_of_3_random_t
tf::spatial::heap_select_t
tf::spatial::nth_element_t (default)

partitioning.cpp

tree.build<tf::spatial::nth_element>(primitive_range, tf::config_tree(4, 4));

Forms

A tf::form is a composite of a primitive range, a spatial structure and a frame (the frame may be omitted). It is used for spatial queries.

forms.cpp

std::vector<float> raw_pts;
auto pts = tf::make_points<3>(raw_pts)
           | tf::tag_id("point cloud");
tf::aabb_tree<int, float, 3> tree(pts, tf::config_tree(4, 4));
tf::frame<float, 3> frame = tf::random_transformation<float, 3>();
auto form = tf::make_form(frame, tree, pts);

// A form behaves like the primitive range it wraps
auto pt0 = form[0];

Spatial Queries

Queries on primitives extend to forms via tree-accelerated search. All queries support both form vs primitive and form vs form.

Distance and Intersection

Query	Returns
`distance2`	Squared distance
`distance`	Distance
`intersects`	`bool`

Supported primitives: point, segment, line, ray, polygon, plane (intersects only)

distance_intersection.cpp

// Form vs primitive
auto d2 = tf::distance2(form, point);
auto d = tf::distance(form, segment);
bool hit = tf::intersects(form, polygon);

// Form vs form
auto d2_ff = tf::distance2(form0, form1);
bool collide = tf::intersects(form0, form1);

Neighbor Search

Generalizes closest_metric_point from Core with tree acceleration, optional search radius, and kNN support.

Form vs primitive returns tf::nearest_neighbor<Index, RealT, Dims>:

.element - primitive id
.info - tf::metric_point (metric + point)
Convertible to bool (false when nothing found within radius)

Form vs form returns tf::nearest_neighbor_pair<Index, RealT, Dims>:

.element - pair of primitive ids
.info - tf::metric_point_pair (metric + point pair)
Convertible to bool (false when nothing found within radius)

Supported primitives: point, segment, line, ray, polygon

neighbor_search.cpp

// Nearest neighbor (always finds one)
auto nearest = tf::neighbor_search(form, point);
auto [primitive_id, metric_point] = nearest;
auto [metric, closest_pt] = metric_point;

// Nearest within radius (may not find any)
auto nearest_r = tf::neighbor_search(form, point, radius);
if (nearest_r) {
    auto [id, mp] = nearest_r;
}

// Form vs form
auto nearest_pair = tf::neighbor_search(form0, form1);
auto [ids, metric_point_pair] = nearest_pair;
auto [id0, id1] = ids;
auto [metric, pt0, pt1] = metric_point_pair;

// Form vs form within radius
auto nearest_pair_r = tf::neighbor_search(form0, form1, radius);
if (nearest_pair_r) {
    auto [ids, mpp] = nearest_pair_r;
}

kNN Queries

For k nearest neighbors, use tf::nearest_neighbors which maintains a sorted buffer of results.

knn.cpp

std::array<tf::nearest_neighbor<int, float, 3>, 10> buffer;
auto knn = tf::make_nearest_neighbors(buffer.begin(), k);
tf::neighbor_search(form, point, knn);

// Iterate over found neighbors (sorted by distance)
for (auto [primitive_id, metric_point] : knn) {
    // process neighbor
}

// With radius limit (may find fewer than k)
auto knn_r = tf::make_nearest_neighbors(buffer.begin(), k, radius);
tf::neighbor_search(form, point, knn_r);

Ray Casting

Extends ray casting on primitives to forms. See Core Ray Casting for return types and status values.

ray_casting.cpp

auto config = tf::make_ray_config(min_t, max_t);

auto result = tf::ray_cast(ray, form, config);
if (result) {
    auto [primitive_id, r_cast] = result;
    // r_cast.status, r_cast.t
}

auto hit = tf::ray_hit(ray, form, config);
if (hit) {
    auto [primitive_id, r_hit] = hit;
    // r_hit.status, r_hit.t, r_hit.point
}

Custom Spatial Queries

Building blocks for queries beyond the built-in functions.

Gathering Primitive IDs

tf::gather_ids collects primitive IDs matching a predicate. It handles thread-safety internally.

gather_ids.cpp

// Gather IDs of primitives intersecting an AABB
std::vector<int> ids;
auto query_aabb = tf::make_aabb(min_pt, max_pt);
tf::gather_ids(form, tf::intersects_f(query_aabb), std::back_inserter(ids));

// With separate BV and primitive predicates (for efficiency)
tf::gather_ids(form,
    [&](const auto &bv) { return tf::intersects(bv, query_aabb); },
    [&](const auto &prim) { return tf::intersects(prim, query_aabb); },
    std::back_inserter(ids));

For pairs of forms, gather_ids returns pairs of primitive IDs:

gather_ids_pair.cpp

// Gather intersecting primitive pairs between two forms
std::vector<std::pair<int, int>> pairs;
tf::gather_ids(form0, form1, tf::intersects_f, std::back_inserter(pairs));

For self-queries within a single form, use tf::gather_self_ids:

gather_self_ids.cpp

// Find self-intersecting primitives
std::vector<std::pair<int, int>> self_pairs;
tf::gather_self_ids(form, tf::intersects_f, std::back_inserter(self_pairs));

// Find pairs of points within a tolerance (for cleaning duplicate points)
auto tolerance2 = tolerance * tolerance;
tf::buffer<std::array<int, 2>> close_pairs;
tf::gather_self_ids(
    point_cloud_form,
    [=](const auto &a, const auto &b) { return tf::distance2(a, b) <= tolerance2; },
    std::back_inserter(close_pairs));

If the primitive does not have an id policy, it is tagged with its index in the primitive range.

Manual Search

For full control over traversal, use tf::search directly. The built-in spatial queries are implemented using these primitives.

Searching a Form

search_form.cpp

tf::search(form, check_bv_f, apply_to_primitive_f);

Where check_bv_f: bounding_volume -> bool filters tree nodes, and apply_to_primitive_f: primitive -> void | bool processes primitives. If it returns a boolean, the search stops on the first true.

For example, tf::intersects(form, segment) could be implemented as:

intersects_impl.cpp

auto intersects(const auto &form, const auto &segment) -> bool {
    return tf::search(
        form,
        [&](const auto &bv) { return tf::intersects(bv, segment); },
        [&](const auto &prim) { return tf::intersects(prim, segment); });
}

When the primitive callback returns void, search visits all matching primitives:

search_accumulate.cpp

// Accumulate area of primitives intersecting an AABB
float total_area = 0;
tf::search(
    form,
    [&](const auto &bv) { return tf::intersects(bv, query_aabb); },
    [&](const auto &polygon) {
        if (tf::intersects(polygon, query_aabb))
            total_area += tf::area(polygon);
    });

Searching a Pair of Forms

search_pair.cpp

tf::search(form0, form1, check_bv_f, apply_to_primitives_f);

For example, tf::intersects(form0, form1) could be implemented as:

intersects_pair_impl.cpp

auto intersects(const auto &form0, const auto &form1) -> bool {
    return tf::search(form0, form1, tf::intersects_f, tf::intersects_f);
}

Pair search runs in parallel. Ensure thread-safety using tf::local_value or tf::local_vector when aggregating values.

search_pair_example.cpp

tf::local_vector<std::pair<int, int>> local;
tf::search(
    form0, form1,
    tf::intersects_f,
    [&](const auto &p0, const auto &p1) {
        if (tf::intersects(p0, p1))
            local.push_back({p0.id(), p1.id()});
    });

std::vector<std::pair<int, int>> result;
local.to_iterator(std::back_inserter(result));

Searching a Form Against Itself

search_self.cpp

tf::search_self(form, check_bv_f, apply_to_primitives_f);

Useful for finding self-intersections or epsilon-duplicates within a single form.

Core

Primitives, ranges, transformations, queries, buffers, policies, and algorithms.

Topology

Connectivity structures, planar embeddings, and mesh analysis.