aabb_tree.hpp File Reference

AABB tree over leaf boxes, with visitor-based traversal and dual-tree collision queries. More...

#include <algorithm>
#include <stdexcept>
#include <numeric>
#include <utility>
#include <vector>
#include <Eigen/Dense>
#include "ellipsoid_tree/geometry.hpp"

Classes
class	ellipsoid_tree::AABBTree
	Axis-aligned bounding box (AABB) tree over a set of leaf boxes. More...

Namespaces
namespace	ellipsoid_tree

Functions
template<class PairPredicate , class LeafPairCallback >
bool	ellipsoid_tree::visit_pairs (const AABBTree &A, const AABBTree &B, PairPredicate &&overlaps_pair, LeafPairCallback &&on_leaf_pair)
	Dual-tree simultaneous descent over two trees: overlaps_pair(loA, hiA, loB, hiB) prunes node pairs; on_leaf_pair(ext_a, ext_b) is called for surviving leaf pairs and stops everything by returning false.
template<class PairPredicate , class LeafPairCallback >
bool	ellipsoid_tree::visit_self_pairs (const AABBTree &T, PairPredicate &&overlaps_pair, LeafPairCallback &&on_leaf_pair)
	Self-collision variant: visits each unordered pair of distinct leaves at most once.

Detailed Description

AABB tree over leaf boxes, with visitor-based traversal and dual-tree collision queries.

AABB tree over a set of leaf boxes, stored in an implicit complete-binary- heap layout: node b has children 2b+1 and 2b+2, and a tree with n leaves has exactly 2n-1 nodes. The build splits each node's leaf range so that every level is full except the last, which is filled left to right — this is what makes the heap indexing valid.

Traversal is visitor-based: visit() takes a node predicate ("does the query overlap this node box?") and a leaf callback (return false to stop early). Concrete query types are two-line predicates on top of it; the convenience point/box/ball queries below are exactly that. visit_pairs() and visit_self_pairs() implement dual-tree simultaneous descent for tree-vs-tree collision queries.

Node boxes and structure are publicly inspectable (node_lo/node_hi/...), both for the dual traversal and for visualization tooling.