avian3d/collider_tree/
mod.rs

1//! Tree acceleration structures for spatial queries on [colliders](crate::collision::collider::Collider).
2//!
3//! To speed up [broad phase](crate::collision::broad_phase) collision detection and [spatial queries](crate::spatial_query),
4//! Avian maintains a [`ColliderTree`] structure for all colliders in the physics world. This is implemented as
5//! a [Bounding Volume Hierarchy (BVH)][BVH], which accelerates querying for [AABB](crate::collision::collider::ColliderAabb)
6//! overlaps, ray intersections, and more.
7//!
8//! Colliders of dynamic, kinematic, and static bodies are all stored in a separate [`ColliderTree`]
9//! to allow efficiently querying for specific subsets of colliders and to optimize tree updates based on body type.
10//! Trees for dynamic and kinematic bodies are rebuilt every physics step, while the static tree is incrementally updated
11//! when static colliders are added, removed, or modified. The trees are stored in the [`ColliderTrees`] resource.
12//!
13//! [BVH]: https://en.wikipedia.org/wiki/Bounding_volume_hierarchy
14//!
15//! # Usage
16//!
17//! The collider trees are fairly low-level, and not intended to be used directly.
18//! For spatial queries, consider using the higher-level [`SpatialQuery`] API instead,
19//! and for broad phase collision detection, consider using the [`BvhBroadPhasePlugin`].
20//!
21//! [`SpatialQuery`]: crate::spatial_query::SpatialQuery
22//! [`BvhBroadPhasePlugin`]: crate::collision::broad_phase::BvhBroadPhasePlugin
23
24mod diagnostics;
25mod obvhs_ext;
26mod optimization;
27mod proxy_key;
28mod traverse;
29mod tree;
30mod update;
31
32pub use diagnostics::ColliderTreeDiagnostics;
33pub use obvhs_ext::Bvh2Ext;
34pub(crate) use obvhs_ext::obvhs_ray;
35pub use optimization::{ColliderTreeOptimization, TreeOptimizationMode};
36pub use proxy_key::{ColliderTreeProxyKey, ColliderTreeType, ProxyId};
37pub use tree::{ColliderTree, ColliderTreeProxy, ColliderTreeProxyFlags, ColliderTreeWorkspace};
38pub use update::{MovedProxies, update_moved_collider_aabbs};
39
40use optimization::ColliderTreeOptimizationPlugin;
41use update::ColliderTreeUpdatePlugin;
42
43use core::marker::PhantomData;
44
45use crate::prelude::*;
46use bevy::prelude::*;
47
48/// A plugin that manages [collider trees](crate::collider_tree) for a collider type `C`.
49pub struct ColliderTreePlugin<C: AnyCollider>(PhantomData<C>);
50
51impl<C: AnyCollider> Default for ColliderTreePlugin<C> {
52    fn default() -> Self {
53        Self(PhantomData)
54    }
55}
56
57impl<C: AnyCollider> Plugin for ColliderTreePlugin<C> {
58    fn build(&self, app: &mut App) {
59        // Register required components.
60        let _ = app.try_register_required_components_with::<C, ColliderTreeProxyKey>(|| {
61            // Use a default proxy key. This will be overwritten when the proxy is actually created.
62            ColliderTreeProxyKey::PLACEHOLDER
63        });
64
65        // Add plugin for updating trees as colliders move.
66        app.add_plugins(ColliderTreeUpdatePlugin::<C>::default());
67
68        // Add plugin for optimizing trees tp maintain good query performance.
69        if !app.is_plugin_added::<ColliderTreeOptimizationPlugin>() {
70            app.add_plugins(ColliderTreeOptimizationPlugin);
71        }
72
73        // Initialize resources.
74        app.init_resource::<ColliderTrees>()
75            .init_resource::<MovedProxies>();
76
77        // Configure system sets.
78        app.configure_sets(
79            PhysicsSchedule,
80            ColliderTreeSystems::UpdateAabbs
81                .in_set(PhysicsStepSystems::BroadPhase)
82                .after(BroadPhaseSystems::First)
83                .before(BroadPhaseSystems::CollectCollisions),
84        );
85        app.configure_sets(
86            PhysicsSchedule,
87            ColliderTreeSystems::BeginOptimize.in_set(BroadPhaseSystems::Last),
88        );
89        app.configure_sets(
90            PhysicsSchedule,
91            ColliderTreeSystems::EndOptimize.in_set(PhysicsStepSystems::Finalize),
92        );
93    }
94
95    fn finish(&self, app: &mut App) {
96        // Register timer diagnostics for collider trees.
97        app.register_physics_diagnostics::<ColliderTreeDiagnostics>();
98    }
99}
100
101/// System sets for managing [`ColliderTrees`].
102#[derive(SystemSet, Clone, Copy, Debug, PartialEq, Eq, Hash)]
103pub enum ColliderTreeSystems {
104    /// Updates the AABBs of colliders.
105    UpdateAabbs,
106    /// Begins optimizing acceleration structures to keep their query performance good.
107    ///
108    /// This runs concurrently with the simulation step as an async task.
109    BeginOptimize,
110    /// Completes the optimization of acceleration structures started in [`ColliderTreeSystems::BeginOptimize`].
111    ///
112    /// This runs at the end of the simulation step.
113    EndOptimize,
114}
115
116/// Trees for accelerating queries on a set of colliders.
117///
118/// See the [`collider_tree`](crate::collider_tree) module for more information.
119#[derive(Resource, Default)]
120pub struct ColliderTrees {
121    /// A tree for the colliders of dynamic bodies.
122    pub dynamic_tree: ColliderTree,
123    /// A tree for the colliders of kinematic bodies.
124    pub kinematic_tree: ColliderTree,
125    /// A tree for the colliders of static bodies.
126    pub static_tree: ColliderTree,
127    /// A tree for standalone colliders with no associated rigid body.
128    pub standalone_tree: ColliderTree,
129}
130
131impl ColliderTrees {
132    /// Returns the tree for the given [`ColliderTreeType`].
133    #[inline]
134    pub const fn tree_for_type(&self, tree_type: ColliderTreeType) -> &ColliderTree {
135        match tree_type {
136            ColliderTreeType::Dynamic => &self.dynamic_tree,
137            ColliderTreeType::Kinematic => &self.kinematic_tree,
138            ColliderTreeType::Static => &self.static_tree,
139            ColliderTreeType::Standalone => &self.standalone_tree,
140        }
141    }
142
143    /// Returns a mutable reference to the tree for the given [`ColliderTreeType`].
144    #[inline]
145    pub const fn tree_for_type_mut(&mut self, tree_type: ColliderTreeType) -> &mut ColliderTree {
146        match tree_type {
147            ColliderTreeType::Dynamic => &mut self.dynamic_tree,
148            ColliderTreeType::Kinematic => &mut self.kinematic_tree,
149            ColliderTreeType::Static => &mut self.static_tree,
150            ColliderTreeType::Standalone => &mut self.standalone_tree,
151        }
152    }
153
154    /// Returns an iterator over all collider trees.
155    #[inline]
156    pub fn iter_trees(&self) -> impl Iterator<Item = &ColliderTree> {
157        [
158            &self.dynamic_tree,
159            &self.kinematic_tree,
160            &self.static_tree,
161            &self.standalone_tree,
162        ]
163        .into_iter()
164    }
165
166    /// Returns a mutable iterator over all collider trees.
167    #[inline]
168    pub fn iter_trees_mut(&mut self) -> impl Iterator<Item = &mut ColliderTree> {
169        [
170            &mut self.dynamic_tree,
171            &mut self.kinematic_tree,
172            &mut self.static_tree,
173            &mut self.standalone_tree,
174        ]
175        .into_iter()
176    }
177
178    /// Returns the proxy with the given [`ColliderTreeProxyKey`], if it exists.
179    #[inline]
180    pub fn get_proxy(&self, key: ColliderTreeProxyKey) -> Option<&ColliderTreeProxy> {
181        self.tree_for_type(key.tree_type())
182            .proxies
183            .get(key.id().index())
184    }
185
186    /// Returns a mutable reference to the proxy with the given [`ColliderTreeProxyKey`], if it exists.
187    #[inline]
188    pub fn get_proxy_mut(&mut self, key: ColliderTreeProxyKey) -> Option<&mut ColliderTreeProxy> {
189        self.tree_for_type_mut(key.tree_type())
190            .proxies
191            .get_mut(key.id().index())
192    }
193}
avian3d/collider_tree/mod.rs

avian3d/collider_tree/
mod.rs
