A system for maintaining hierarchical bounding boxes. More...

#include <bounding_hierarchy.h>

Public Types
using	xfn = AffineTransform< T, N >

using	vecn = Vec< T, N >

using	rangen = Rect< T, N >

using	rayn = Ray< T, N >

using	IB = IntrinsicBounds< HTag, T, N, BTag >

Public Member Functions
	BoundsSystem (entt::registry &reg, TransformSystem< HTag, T, N, XTag > &transforms)

	BoundsSystem (const BoundsSystem &)=delete

BoundsSystem &	operator= (const BoundsSystem &)=delete

TransformSystem< HTag, T, N, XTag > &	transform_system ()

HierarchySystem< HTag > &	hierarchy ()

std::optional< rangen >	set_intrinsic_bounds (entt::entity eid, rangen bounds)
	Set the intrinsic (local) bounding box for an entity.

std::optional< rangen >	get_intrinsic_bounds (entt::entity eid) const
	Get the intrinsic bounds in local coordinates, or `std::nullopt` if not set.

std::optional< rangen >	remove_intrinsic_bounds (entt::entity eid)
	Remove the intrinsic bounds for an entity. Returns the old bounds if they existed.

std::optional< rangen >	get_computed_bounds (entt::entity eid)
	Get the computed bounds for an entity in local coordinates.

auto	traverse (entt::entity root, SiblingOrder order)
	Create a traversal which yields `BoundedNode<NodeEntry,T,N>`.

template<TransformedTraversal< T, N > Traversal>
auto	augment_with_bounds (Traversal &&t)
	Convert a traversal of `TransformedNode<Node,T,N>` to a traversal of `BoundedNode<Node,T,N>`.

template<BoundedTraversal< T, N > Traversal>
auto	traverse_under_point (Traversal &&t, vecn p)
	Filter a bounded traversal to only visit nodes whose computed bounds contain a point (or which have descendants that might).

Generator< PointSearchNode< NodeEntry, T, N > >	search_under_point (entt::entity root, SiblingOrder sibling_order, DfsOrder recursion_order, vecn p)
	Yield all nodes whose intrinsic bounds contain a point.

template<BoundedTraversal< T, N > Traversal>
auto	traverse_along_ray (Traversal &&t, rayn ray)
	Filter a bounded traversal to only visit nodes whose computed bounds intersect a ray (or which have descendants that might).

Generator< RaySearchNode< NodeEntry, T, N > >	search_along_ray (entt::entity root, SiblingOrder sibling_order, DfsOrder recursion_order, rayn ray)
	Yield all nodes whose computed bounds intersect a ray.

Public Attributes
entt::sigh< void(entt::entity, rangen)>	on_bounds_set
	Emitted when intrinsic bounds are first set on an entity. Args: (entity, new_bounds).

entt::sigh< void(entt::entity, rangen)>	on_bounds_removed
	Emitted when intrinsic bounds are removed from an entity. Args: (entity, old_bounds).

entt::sigh< void(entt::entity, rangen, rangen)>	on_bounds_changed
	Emitted when an existing intrinsic bounds value changes. Args: (entity, old_bounds, new_bounds).

Detailed Description

template<typename HTag, typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>
struct entttree::BoundsSystem< HTag, T, N, BTag, XTag >

A system for maintaining hierarchical bounding boxes.

It produces a computed bound for each entity, which is the union of its intrinsic bound and the computed bounds of its children (transformed into parent space). Dirty tracking defers recomputation until the bounds are actually queried, making bulk hierarchy or transform changes inexpensive.

This system connects to a TransformSystem (and through it, a HierarchySystem) via signals. When parent-child relationships change or transforms are modified, the affected bounds are automatically marked dirty up to the root.

The BoundsSystem does not own the TransformSystem; it holds a reference to it. Multiple BoundsSystem instances may share the same TransformSystem if needed.

Template Parameters

HTag	Hierarchy tag type.
T	Scalar type (e.g. `double`).
N	Spatial dimension (e.g. 2 or 3).
BTag	Optional bounds-layer tag. Defaults to HTag.
XTag	Transform-layer tag to observe. Defaults to HTag.

Definition at line 45 of file bounding_hierarchy.h.

Member Typedef Documentation

◆ IB

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

using entttree::BoundsSystem< HTag, T, N, BTag, XTag >::IB = IntrinsicBounds<HTag,T,N,BTag>

Definition at line 51 of file bounding_hierarchy.h.

◆ rangen

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

using entttree::BoundsSystem< HTag, T, N, BTag, XTag >::rangen = Rect<T,N>

Definition at line 49 of file bounding_hierarchy.h.

◆ rayn

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

using entttree::BoundsSystem< HTag, T, N, BTag, XTag >::rayn = Ray<T,N>

Definition at line 50 of file bounding_hierarchy.h.

◆ vecn

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

using entttree::BoundsSystem< HTag, T, N, BTag, XTag >::vecn = Vec<T,N>

Definition at line 48 of file bounding_hierarchy.h.

◆ xfn

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

using entttree::BoundsSystem< HTag, T, N, BTag, XTag >::xfn = AffineTransform<T,N>

Definition at line 47 of file bounding_hierarchy.h.

Constructor & Destructor Documentation

◆ BoundsSystem()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

entttree::BoundsSystem< HTag, T, N, BTag, XTag >::BoundsSystem	(	entt::registry &	reg,
		TransformSystem< HTag, T, N, XTag > &	transforms
	)

inline

Definition at line 68 of file bounding_hierarchy.h.

Member Function Documentation

◆ augment_with_bounds()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

template<TransformedTraversal< T, N > Traversal>

auto entttree::BoundsSystem< HTag, T, N, BTag, XTag >::augment_with_bounds ( Traversal && t )

inline

Convert a traversal of TransformedNode<Node,T,N> to a traversal of BoundedNode<Node,T,N>.

Each node is augmented with its intrinsic and computed bounds. Dirty bounds are recomputed on the fly.

Definition at line 192 of file bounding_hierarchy.h.

Referenced by entttree::BoundsSystem< HTag, T, N, BTag, XTag >::traverse().

◆ get_computed_bounds()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

std::optional< rangen > entttree::BoundsSystem< HTag, T, N, BTag, XTag >::get_computed_bounds ( entt::entity eid )

inline

Get the computed bounds for an entity in local coordinates.

Computed bounds are the union of the entity's intrinsic bounds and the computed bounds of all its children (transformed into parent space). If the bounds are dirty, they are lazily recomputed before returning.

Returns: The computed bounds, or std::nullopt if the entity has no intrinsic bounds and no children with bounds.

Definition at line 162 of file bounding_hierarchy.h.

◆ get_intrinsic_bounds()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

std::optional< rangen > entttree::BoundsSystem< HTag, T, N, BTag, XTag >::get_intrinsic_bounds ( entt::entity eid ) const

inline

Get the intrinsic bounds in local coordinates, or std::nullopt if not set.

Definition at line 125 of file bounding_hierarchy.h.

◆ hierarchy()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

HierarchySystem< HTag > & entttree::BoundsSystem< HTag, T, N, BTag, XTag >::hierarchy ( )

inline

Definition at line 95 of file bounding_hierarchy.h.

◆ remove_intrinsic_bounds()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

std::optional< rangen > entttree::BoundsSystem< HTag, T, N, BTag, XTag >::remove_intrinsic_bounds ( entt::entity eid )

inline

Remove the intrinsic bounds for an entity. Returns the old bounds if they existed.

Definition at line 133 of file bounding_hierarchy.h.

References entttree::and, entttree::HierarchySystem< HTag >::child_count(), entttree::BoundsSystem< HTag, T, N, BTag, XTag >::on_bounds_removed, and entttree::HierarchySystem< HTag >::parent_of().

◆ search_along_ray()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

Generator< RaySearchNode< NodeEntry, T, N > > entttree::BoundsSystem< HTag, T, N, BTag, XTag >::search_along_ray	(	entt::entity	root,
		SiblingOrder	sibling_order,
		DfsOrder	recursion_order,
		rayn	ray
	)

inline

Yield all nodes whose computed bounds intersect a ray.

This performs a depth-first traversal, pruning subtrees whose computed bounds do not intersect the ray.

Parameters

root	Root of the subtree to search.
sibling_order	Order in which siblings are visited.
recursion_order	Pre-order or post-order visitation.
ray	The query ray in root-space coordinates.

Definition at line 316 of file bounding_hierarchy.h.

◆ search_under_point()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

Generator< PointSearchNode< NodeEntry, T, N > > entttree::BoundsSystem< HTag, T, N, BTag, XTag >::search_under_point	(	entt::entity	root,
		SiblingOrder	sibling_order,
		DfsOrder	recursion_order,
		vecn	p
	)

inline

Yield all nodes whose intrinsic bounds contain a point.

This performs a depth-first traversal, pruning subtrees whose computed bounds do not contain the point, and then post-filters to only yield nodes whose intrinsic bounds contain the local point.

Parameters

root	Root of the subtree to search.
sibling_order	Order in which siblings are visited.
recursion_order	Pre-order or post-order visitation.
p	The query point in root-space coordinates.

Definition at line 254 of file bounding_hierarchy.h.

References entttree::and, entttree::BoundsSystem< HTag, T, N, BTag, XTag >::traverse(), and entttree::BoundsSystem< HTag, T, N, BTag, XTag >::traverse_under_point().

◆ set_intrinsic_bounds()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

std::optional< rangen > entttree::BoundsSystem< HTag, T, N, BTag, XTag >::set_intrinsic_bounds	(	entt::entity	eid,
		rangen	bounds
	)

inline

Set the intrinsic (local) bounding box for an entity.

Returns: The previous intrinsic bounds, or std::nullopt if the entity had none.

Definition at line 105 of file bounding_hierarchy.h.

References entttree::BoundsSystem< HTag, T, N, BTag, XTag >::on_bounds_changed, and entttree::BoundsSystem< HTag, T, N, BTag, XTag >::on_bounds_set.

◆ transform_system()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

TransformSystem< HTag, T, N, XTag > & entttree::BoundsSystem< HTag, T, N, BTag, XTag >::transform_system ( )

inline

Definition at line 94 of file bounding_hierarchy.h.

◆ traverse()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

auto entttree::BoundsSystem< HTag, T, N, BTag, XTag >::traverse	(	entt::entity	root,
		SiblingOrder	order
	)

inline

Create a traversal which yields BoundedNode<NodeEntry,T,N>.

Definition at line 177 of file bounding_hierarchy.h.

References entttree::BoundsSystem< HTag, T, N, BTag, XTag >::augment_with_bounds(), and entttree::HierarchySystem< HTag >::traverse().

Referenced by entttree::BoundsSystem< HTag, T, N, BTag, XTag >::search_under_point().

◆ traverse_along_ray()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

template<BoundedTraversal< T, N > Traversal>

auto entttree::BoundsSystem< HTag, T, N, BTag, XTag >::traverse_along_ray	(	Traversal &&	t,
		rayn	ray
	)

inline

Filter a bounded traversal to only visit nodes whose computed bounds intersect a ray (or which have descendants that might).

Transforms the traversal from BoundedNode<Node,T,N> to RaySearchNode<Node,T,N>, which includes the local ray and the parameter interval of the intersection. Nodes without computed bounds are traversed unconditionally.

Definition at line 283 of file bounding_hierarchy.h.

◆ traverse_under_point()

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

template<BoundedTraversal< T, N > Traversal>

auto entttree::BoundsSystem< HTag, T, N, BTag, XTag >::traverse_under_point	(	Traversal &&	t,
		vecn	p
	)

inline

Filter a bounded traversal to only visit nodes whose computed bounds contain a point (or which have descendants that might).

Transforms the traversal from BoundedNode<Node,T,N> to PointSearchNode<Node,T,N>, which includes the query point in each node's local coordinates for convenience. Nodes without computed bounds are traversed unconditionally.

Definition at line 225 of file bounding_hierarchy.h.

Referenced by entttree::BoundsSystem< HTag, T, N, BTag, XTag >::search_under_point().

Member Data Documentation

◆ on_bounds_changed

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

entt::sigh<void(entt::entity, rangen, rangen)> entttree::BoundsSystem< HTag, T, N, BTag, XTag >::on_bounds_changed

Emitted when an existing intrinsic bounds value changes. Args: (entity, old_bounds, new_bounds).

Definition at line 62 of file bounding_hierarchy.h.

Referenced by entttree::BoundsSystem< HTag, T, N, BTag, XTag >::set_intrinsic_bounds().

◆ on_bounds_removed

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

entt::sigh<void(entt::entity, rangen)> entttree::BoundsSystem< HTag, T, N, BTag, XTag >::on_bounds_removed

Emitted when intrinsic bounds are removed from an entity. Args: (entity, old_bounds).

Definition at line 60 of file bounding_hierarchy.h.

Referenced by entttree::BoundsSystem< HTag, T, N, BTag, XTag >::remove_intrinsic_bounds().

◆ on_bounds_set

template<typename HTag , typename T = double, size_t N = 2, typename BTag = HTag, typename XTag = HTag>

entt::sigh<void(entt::entity, rangen)> entttree::BoundsSystem< HTag, T, N, BTag, XTag >::on_bounds_set

Emitted when intrinsic bounds are first set on an entity. Args: (entity, new_bounds).

Definition at line 58 of file bounding_hierarchy.h.

Referenced by entttree::BoundsSystem< HTag, T, N, BTag, XTag >::set_intrinsic_bounds().

The documentation for this struct was generated from the following file:

include/entttree/bounding_hierarchy.h

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ IB

◆ rangen

◆ rayn

◆ vecn

◆ xfn

Constructor & Destructor Documentation

◆ BoundsSystem()

Member Function Documentation

◆ augment_with_bounds()

◆ get_computed_bounds()

◆ get_intrinsic_bounds()

◆ hierarchy()

◆ remove_intrinsic_bounds()

◆ search_along_ray()

◆ search_under_point()

◆ set_intrinsic_bounds()

◆ transform_system()

◆ traverse()

◆ traverse_along_ray()

◆ traverse_under_point()

Member Data Documentation

◆ on_bounds_changed

◆ on_bounds_removed

◆ on_bounds_set