Struct rapier3d::geometry::BroadPhase [−][src]
pub struct BroadPhase { /* fields omitted */ }
Expand description
A broad-phase combining a Hierarchical Grid and Sweep-and-Prune.
The basic Sweep-and-Prune (SAP) algorithm has one significant flaws: the interactions between far-away objects. This means that objects that are very far away will still have some of their endpoints swapped within the SAP data-structure. This results in poor scaling because this results in lots of swapping between endpoints of AABBs that won’t ever actually interact.
The first optimization to address this problem is to use the Multi-SAP method. This basically combines an SAP with a grid. The grid subdivides the spaces into equally-sized subspaces (grid cells). Each subspace, which we call a “region” contains an SAP instance (i.e. there SAP axes responsible for collecting endpoints and swapping them when they move to detect interaction pairs). Each AABB is inserted in all the regions it intersects. This prevents the far-away problem because two objects that are far away will be located on different regions. So their endpoints will never meed.
However, the Multi-SAP approach has one notable problem: the region size must be chosen wisely. It could be user-defined, but that’s makes it more difficult to use (for the end-user). Or it can be given a fixed value. Using a fixed value may result in large objects intersecting lots of regions, resulting in poor performances and very high memory usage.
So a solution to that large-objects problem is the Multi-SAP approach is to replace the grid by a hierarchical grid. A hierarchical grid is composed of several layers. And each layer have different region sizes. For example all the regions on layer 0 will have the size 1x1x1. All the regions on the layer 1 will have the size 10x10x10, etc. That way, a given AABB will be inserted on the layer that has regions big enough to avoid the large-object problem. For example a 20x20x20 object will be inserted in the layer with region of size 10x10x10, resulting in only 8 regions being intersect by the AABB. (If it was inserted in the layer with regions of size 1x1x1, it would have intersected 8000 regions, which is a problem performancewise.)
We call this new method the Hierarchical-SAP.
Now with the Hierarchical-SAP, we can update each layer independently from one another. However, objects belonging to different layers will never be detected as intersecting that way. So we need a way to do inter-layer interference detection. There is a lot ways of doing this: performing inter-layer Multi-Box-Pruning passes is one example (but this is not what we do). In our implementation, we do the following:
- The AABB bounds of each region of the layer
n
are inserted into the corresponding larger region of the layern + 1
. - When an AABB in the region of the layer
n + 1
intersects the AABB corresponding to one of the regions at the smaller layern
, we add that AABB to that smaller region. So in the end it means that a given AABB will be inserted into all the region it intersects at the layern
. And it will also be inserted into all the regions it intersects at the smaller layers (the layers< n
), but only for the regions that already exist (so we don’t have to discretize our AABB into the layers< n
). This involves a fair amount of bookkeeping unfortunately, but this has the benefit of keep the overall complexity of the algorithm O(1) in the typical specially coherent scenario.
From an implementation point-of-view, our hierarchical SAP is implemented with the following structures:
- There is one
SAPLayer
per layer of the hierarchical grid. - Each
SAPLayer
contains multipleSAPRegion
(each being a region of the grid represented by that layer). - Each
SAPRegion
contains threeSAPAxis
, representing the “classical” SAP algorithm running on this region. - Each
SAPAxis
maintains a sorted list ofSAPEndpoints
representing the endpoints of the AABBs intersecting the bounds on theSAPRegion
containing thisSAPAxis
. - A set of
SAPProxy
are maintained separately. It contains the AABBs of all the colliders managed by this broad-phase, as well as the AABBs of all the regions part of this broad-phase.
Implementations
impl BroadPhase
[src]
impl BroadPhase
[src]pub fn update<Colliders>(
&mut self,
prediction_distance: Real,
colliders: &mut Colliders,
modified_colliders: &[ColliderHandle],
removed_colliders: &[ColliderHandle],
events: &mut Vec<BroadPhasePairEvent>
) where
Colliders: ComponentSetMut<ColliderBroadPhaseData> + ComponentSet<ColliderChanges> + ComponentSet<ColliderPosition> + ComponentSet<ColliderShape>,
[src]
pub fn update<Colliders>(
&mut self,
prediction_distance: Real,
colliders: &mut Colliders,
modified_colliders: &[ColliderHandle],
removed_colliders: &[ColliderHandle],
events: &mut Vec<BroadPhasePairEvent>
) where
Colliders: ComponentSetMut<ColliderBroadPhaseData> + ComponentSet<ColliderChanges> + ComponentSet<ColliderPosition> + ComponentSet<ColliderShape>,
[src]Updates the broad-phase, taking into account the new collider positions.
Trait Implementations
impl Clone for BroadPhase
[src]
impl Clone for BroadPhase
[src]fn clone(&self) -> BroadPhase
[src]
fn clone(&self) -> BroadPhase
[src]Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]Performs copy-assignment from source
. Read more
Auto Trait Implementations
impl RefUnwindSafe for BroadPhase
impl Send for BroadPhase
impl Sync for BroadPhase
impl Unpin for BroadPhase
impl UnwindSafe for BroadPhase
Blanket Implementations
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]pub fn borrow_mut(&mut self) -> &mut T
[src]
pub fn borrow_mut(&mut self) -> &mut T
[src]Mutably borrows from an owned value. Read more
impl<T> Downcast for T where
T: Any,
[src]
impl<T> Downcast for T where
T: Any,
[src]pub fn into_any(self: Box<T, Global>) -> Box<dyn Any + 'static, Global>
[src]
pub fn into_any(self: Box<T, Global>) -> Box<dyn Any + 'static, Global>
[src]Convert Box<dyn Trait>
(where Trait: Downcast
) to Box<dyn Any>
. Box<dyn Any>
can
then be further downcast
into Box<ConcreteType>
where ConcreteType
implements Trait
. Read more
pub fn into_any_rc(self: Rc<T>) -> Rc<dyn Any + 'static>
[src]
pub fn into_any_rc(self: Rc<T>) -> Rc<dyn Any + 'static>
[src]Convert Rc<Trait>
(where Trait: Downcast
) to Rc<Any>
. Rc<Any>
can then be
further downcast
into Rc<ConcreteType>
where ConcreteType
implements Trait
. Read more
pub fn as_any(&self) -> &(dyn Any + 'static)
[src]
pub fn as_any(&self) -> &(dyn Any + 'static)
[src]Convert &Trait
(where Trait: Downcast
) to &Any
. This is needed since Rust cannot
generate &Any
’s vtable from &Trait
’s. Read more
pub fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
[src]
pub fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
[src]Convert &mut Trait
(where Trait: Downcast
) to &Any
. This is needed since Rust cannot
generate &mut Any
’s vtable from &mut Trait
’s. Read more
impl<T> DowncastSync for T where
T: Any + Send + Sync,
[src]
impl<T> DowncastSync for T where
T: Any + Send + Sync,
[src]impl<T> Pointable for T
impl<T> Pointable for T
impl<T> Same<T> for T
impl<T> Same<T> for T
type Output = T
type Output = T
Should always be Self
impl<SS, SP> SupersetOf<SS> for SP where
SS: SubsetOf<SP>,
[src]
impl<SS, SP> SupersetOf<SS> for SP where
SS: SubsetOf<SP>,
[src]pub fn to_subset(&self) -> Option<SS>
[src]
pub fn to_subset(&self) -> Option<SS>
[src]The inverse inclusion map: attempts to construct self
from the equivalent element of its
superset. Read more
pub fn is_in_subset(&self) -> bool
[src]
pub fn is_in_subset(&self) -> bool
[src]Checks if self
is actually part of its subset T
(and can be converted to it).
pub fn to_subset_unchecked(&self) -> SS
[src]
pub fn to_subset_unchecked(&self) -> SS
[src]Use with care! Same as self.to_subset
but without any property checks. Always succeeds.
pub fn from_subset(element: &SS) -> SP
[src]
pub fn from_subset(element: &SS) -> SP
[src]The inclusion map: converts self
to the equivalent element of its superset.
impl<T> ToOwned for T where
T: Clone,
[src]
impl<T> ToOwned for T where
T: Clone,
[src]type Owned = T
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn to_owned(&self) -> T
[src]Creates owned data from borrowed data, usually by cloning. Read more
pub fn clone_into(&self, target: &mut T)
[src]
pub fn clone_into(&self, target: &mut T)
[src]🔬 This is a nightly-only experimental API. (toowned_clone_into
)
recently added
Uses borrowed data to replace owned data, usually by cloning. Read more