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

Include the module with:

#include <trueform/spatial.hpp>

Spatial Structures

Spatial structures accelerate queries by organizing primitives into hierarchies. The module provides two tree types:

Both are fully interchangeable. Every query, search, and operation in this module works identically with either tree type. Choose based on your update pattern:

• Use tree for static geometry or infrequent changes
• Use mod_tree for interactive applications with frequent local changes

Bounding Volumes

Both tree types are parameterized by a bounding volume (BV) type:

For most applications, aabb provides the best overall performance. Use obb or obbrss for nearest-neighbor and proximity searches between two meshes, where tighter bounding volumes improve query culling.

tf::tree

tf::tree<Index, BV> is a high-performance spatial hierarchy introduced in:

Convenience aliases:

Building

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

The configuration specifies arity (children per node) and maximum primitives per leaf.

Partitioning Policies

Tree construction uses a partitioning strategy. Several selection-based algorithms are available:

• tf::spatial::nth_element_t (default)
• 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

tree.build<tf::spatial::floyd_rivest_t>(primitives, tf::config_tree(4, 4));

tf::mod_tree

tf::mod_tree<Index, BV> is a modifiable tree that extends tree with efficient incremental updates. It maintains two internal trees:

• Main tree: Bulk of primitives (pruned on updates)
• Delta tree: Recently added or modified primitives (rebuilt on updates)

This enables O(delta) updates rather than O(n) rebuilds.

Convenience aliases:

Building

Construction is identical to tf::tree:

tf::aabb_mod_tree<int, float, 3> tree;
tree.build(primitives, tf::config_tree(4, 4));

// With explicit partitioner
tree.build<tf::spatial::nth_element_t>(primitives, tf::config_tree(4, 4));

Incremental Updates

Updates work by pruning elements from the main tree and adding dirty elements to the delta tree. Two methods are provided:

• Simple Update — When only geometry changes (vertices moved, same primitive count)
• Update with Remapping — When also topology changes (primitives added, removed, or reindexed)

tree_index_map

Encapsulates remapping information for tree updates:

• f() — Forward map: old_id → new_id (sentinel f().size() if removed)
• dirty_ids() — IDs of new or modified elements to add to delta tree

// View type (wraps existing ranges)
auto map = tf::make_tree_index_map(forward_range, dirty_ids_range);

// Owning buffer type
tf::tree_index_map_buffer<int> map;

Simple Update

Since no IDs are remapped, tree_index_map is not needed. The keep_if predicate controls which elements stay in the main tree—return false for dirty IDs to move them to the delta tree.

tf::buffer<int> dirty_ids = {5, 12, 47};  // IDs of modified primitives
std::set<int> dirty_set(dirty_ids.begin(), dirty_ids.end());

// keep_if returns false for dirty IDs → they move to delta tree
tree.update(primitives, dirty_ids,
    [&](int id) { return !dirty_set.contains(id); },
    tf::config_tree(4, 4));

Update with Remapping

Uses tree_index_map to encapsulate the remapping.

auto tree_map = tf::make_tree_index_map(
    tf::make_range(remap),      // old_id → new_id (sentinel if removed)
    tf::make_range(dirty_ids)); // new/modified element IDs

tree.update(new_primitives, tree_map, tf::config_tree(4, 4));

Accessing Internal Structure

const auto& main = tree.main_tree();      // tree_like view
const auto& delta = tree.delta_tree();    // tree_like view
const auto& delta_ids = tree.delta_ids(); // IDs in delta tree

Trees and Policies

Trees integrate with the policy system. Attach a tree to its primitive range:

auto form = primitives | tf::tag(tree);      // works with tf::tree
auto form = primitives | tf::tag(mod_tree);  // works with tf::mod_tree

Because both policies and ranges compose, you can build separate trees for different levels:

tf::aabb_tree<int, float, 3> pt_tree(polygons.points(), tf::config_tree(4, 4));
tf::aabb_tree<int, float, 3> poly_tree(polygons, tf::config_tree(4, 4));

auto polygons_with_trees = tf::make_polygons(
    polygons.faces(),
    polygons.points() | tf::tag(pt_tree)
) | tf::tag(poly_tree);

// Access trees at each level
const auto& pt_tr = polygons_with_trees.points().tree();
const auto& poly_tr = polygons_with_trees.tree();

Spatial Queries

Spatial queries operate on forms with tagged trees: form | tf::tag(tree). All queries support both form vs primitive and form vs form.

Distance and Intersection

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

// 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<Index0, Index1, 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 and plane.

// 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.

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.

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 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 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:

// 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));

Manual Search

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

Searching a Form

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:

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:

// 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

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

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

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

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));

This pattern is how tf::gather_ids(form0, form1, ...) is implemented internally.

Searching a Form Against Itself

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

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

auto within_epsilon = [=](const auto &a, const auto &b) {
    return tf::distance2(a, b) <= epsilon2;
};

tf::local_vector<std::pair<int, int>> local;
tf::search_self(
    form,
    within_epsilon,
    [&](const auto &p0, const auto &p1) {
        if (within_epsilon(p0, p1))
            local.push_back({p0.id(), p1.id()});
    });

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

This pattern is how tf::gather_self_ids(form, ...) is implemented internally.