Completely remove the WAABBHierarchy structure.

It is now replaced by the WQuadtree.

5 files changed, 39 insertions, 261 deletions

diff --git a/src/geometry/broad_phase.rs b/src/geometry/broad_phase.rs
deleted file mode 100644
index a1333d0..0000000
--- a/src/geometry/broad_phase.rs
+++ /dev/null
@@ -1,255 +0,0 @@
-use crate::geometry::ColliderHandle;
-use ncollide::bounding_volume::AABB;
-#[cfg(feature = "simd-is-enabled")]
-use {
-    crate::geometry::WAABB,
-    crate::math::{Point, SIMD_WIDTH},
-    crate::utils::WVec,
-    simba::simd::SimdBool as _,
-};
-
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
-#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
-pub struct ColliderPair {
-    pub collider1: ColliderHandle,
-    pub collider2: ColliderHandle,
-}
-
-impl ColliderPair {
-    pub fn new(collider1: ColliderHandle, collider2: ColliderHandle) -> Self {
-        ColliderPair {
-            collider1,
-            collider2,
-        }
-    }
-
-    pub fn new_sorted(collider1: ColliderHandle, collider2: ColliderHandle) -> Self {
-        if collider1.into_raw_parts().0 <= collider2.into_raw_parts().0 {
-            Self::new(collider1, collider2)
-        } else {
-            Self::new(collider2, collider1)
-        }
-    }
-
-    pub fn swap(self) -> Self {
-        Self::new(self.collider2, self.collider1)
-    }
-
-    pub fn zero() -> Self {
-        Self {
-            collider1: ColliderHandle::from_raw_parts(0, 0),
-            collider2: ColliderHandle::from_raw_parts(0, 0),
-        }
-    }
-}
-
-pub struct WAABBHierarchyIntersections {
-    curr_level_interferences: Vec<usize>,
-    next_level_interferences: Vec<usize>,
-}
-
-impl WAABBHierarchyIntersections {
-    pub fn new() -> Self {
-        Self {
-            curr_level_interferences: Vec::new(),
-            next_level_interferences: Vec::new(),
-        }
-    }
-
-    pub fn computed_interferences(&self) -> &[usize] {
-        &self.curr_level_interferences[..]
-    }
-
-    pub(crate) fn computed_interferences_mut(&mut self) -> &mut Vec<usize> {
-        &mut self.curr_level_interferences
-    }
-}
-
-#[cfg(feature = "simd-is-enabled")]
-#[derive(Clone)]
-#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
-pub struct WAABBHierarchy {
-    levels: Vec<Vec<WAABB>>,
-}
-
-#[cfg(feature = "simd-is-enabled")]
-impl WAABBHierarchy {
-    pub fn new(aabbs: &[AABB<f32>]) -> Self {
-        let mut waabbs: Vec<_> = aabbs
-            .chunks_exact(SIMD_WIDTH)
-            .map(|aabbs| WAABB::from(array![|ii| aabbs[ii]; SIMD_WIDTH]))
-            .collect();
-
-        if aabbs.len() % SIMD_WIDTH != 0 {
-            let first_i = (aabbs.len() / SIMD_WIDTH) * SIMD_WIDTH;
-            let last_i = aabbs.len() - 1;
-            let last_waabb =
-                WAABB::from(array![|ii| aabbs[(first_i + ii).min(last_i)]; SIMD_WIDTH]);
-            waabbs.push(last_waabb);
-        }
-
-        let mut levels = vec![waabbs];
-
-        loop {
-            let last_level = levels.last().unwrap();
-            let mut next_level = Vec::new();
-
-            for chunk in last_level.chunks_exact(SIMD_WIDTH) {
-                let mins = Point::from(array![|ii| chunk[ii].mins.horizontal_inf(); SIMD_WIDTH]);
-                let maxs = Point::from(array![|ii| chunk[ii].maxs.horizontal_sup(); SIMD_WIDTH]);
-                next_level.push(WAABB::new(mins, maxs));
-            }
-
-            // Deal with the last non-exact chunk.
-            if last_level.len() % SIMD_WIDTH != 0 {
-                let first_id = (last_level.len() / SIMD_WIDTH) * SIMD_WIDTH;
-                let last_id = last_level.len() - 1;
-                let mins = array![|ii| last_level[(first_id + ii).min(last_id)]
-                    .mins
-                    .horizontal_inf(); SIMD_WIDTH];
-                let maxs = array![|ii| last_level[(first_id + ii).min(last_id)]
-                    .maxs
-                    .horizontal_sup(); SIMD_WIDTH];
-
-                let mins = Point::from(mins);
-                let maxs = Point::from(maxs);
-                next_level.push(WAABB::new(mins, maxs));
-            }
-
-            if next_level.len() == 1 {
-                levels.push(next_level);
-                break;
-            }
-
-            levels.push(next_level);
-        }
-
-        Self { levels }
-    }
-
-    pub fn compute_interferences_with(
-        &self,
-        aabb: AABB<f32>,
-        workspace: &mut WAABBHierarchyIntersections,
-    ) {
-        let waabb1 = WAABB::splat(aabb);
-        workspace.next_level_interferences.clear();
-        workspace.curr_level_interferences.clear();
-        workspace.curr_level_interferences.push(0);
-
-        for level in self.levels.iter().rev() {
-            for i in &workspace.curr_level_interferences {
-                // This `if let` handle the case when `*i` is out of bounds because
-                // the initial number of aabbs was not a power of SIMD_WIDTH.
-                if let Some(waabb2) = level.get(*i) {
-                    // NOTE: using `intersect.bitmask()` and performing bit comparisons
-                    // is much more efficient than testing if each intersect.extract(i) is true.
-                    let intersect = waabb1.intersects(waabb2);
-                    let bitmask = intersect.bitmask();
-
-                    for j in 0..SIMD_WIDTH {
-                        if (bitmask & (1 << j)) != 0 {
-                            workspace.next_level_interferences.push(i * SIMD_WIDTH + j)
-                        }
-                    }
-                }
-            }
-
-            std::mem::swap(
-                &mut workspace.curr_level_interferences,
-                &mut workspace.next_level_interferences,
-            );
-            workspace.next_level_interferences.clear();
-        }
-    }
-}
-
-#[cfg(not(feature = "simd-is-enabled"))]
-#[derive(Clone)]
-#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
-pub struct WAABBHierarchy {
-    levels: Vec<Vec<AABB<f32>>>,
-}
-
-#[cfg(not(feature = "simd-is-enabled"))]
-impl WAABBHierarchy {
-    const GROUP_SIZE: usize = 4;
-
-    pub fn new(aabbs: &[AABB<f32>]) -> Self {
-        use ncollide::bounding_volume::BoundingVolume;
-
-        let mut levels = vec![aabbs.to_vec()];
-
-        loop {
-            let last_level = levels.last().unwrap();
-            let mut next_level = Vec::new();
-
-            for chunk in last_level.chunks(Self::GROUP_SIZE) {
-                let mut merged = chunk[0];
-                for aabb in &chunk[1..] {
-                    merged.merge(aabb)
-                }
-
-                next_level.push(merged);
-            }
-
-            if next_level.len() == 1 {
-                levels.push(next_level);
-                break;
-            }
-
-            levels.push(next_level);
-        }
-
-        Self { levels }
-    }
-
-    pub fn compute_interferences_with(
-        &self,
-        aabb1: AABB<f32>,
-        workspace: &mut WAABBHierarchyIntersections,
-    ) {
-        use ncollide::bounding_volume::BoundingVolume;
-
-        workspace.next_level_interferences.clear();
-        workspace.curr_level_interferences.clear();
-        workspace.curr_level_interferences.push(0);
-
-        for level in self.levels[1..].iter().rev() {
-            for i in &workspace.curr_level_interferences {
-                for j in 0..Self::GROUP_SIZE {
-                    if let Some(aabb2) = level.get(*i + j) {
-                        if aabb1.intersects(aabb2) {
-                            workspace
-                                .next_level_interferences
-                                .push((i + j) * Self::GROUP_SIZE)
-                        }
-                    }
-                }
-            }
-
-            std::mem::swap(
-                &mut workspace.curr_level_interferences,
-                &mut workspace.next_level_interferences,
-            );
-            workspace.next_level_interferences.clear();
-        }
-
-        // Last level.
-        for i in &workspace.curr_level_interferences {
-            for j in 0..Self::GROUP_SIZE {
-                if let Some(aabb2) = self.levels[0].get(*i + j) {
-                    if aabb1.intersects(aabb2) {
-                        workspace.next_level_interferences.push(i + j)
-                    }
-                }
-            }
-        }
-
-        std::mem::swap(
-            &mut workspace.curr_level_interferences,
-            &mut workspace.next_level_interferences,
-        );
-        workspace.next_level_interferences.clear();
-    }
-}
diff --git a/src/geometry/broad_phase_multi_sap.rs b/src/geometry/broad_phase_multi_sap.rs
index 5c80e0e..0add089 100644
--- a/src/geometry/broad_phase_multi_sap.rs
+++ b/src/geometry/broad_phase_multi_sap.rs
@@ -1,6 +1,6 @@
 use crate::data::pubsub::PubSubCursor;
 use crate::dynamics::RigidBodySet;
-use crate::geometry::{Collider, ColliderHandle, ColliderPair, ColliderSet, RemovedCollider};
+use crate::geometry::{Collider, ColliderHandle, ColliderSet, RemovedCollider};
 use crate::math::{Point, Vector, DIM};
 #[cfg(feature = "enhanced-determinism")]
 use crate::utils::FxHashMap32 as HashMap;
@@ -16,6 +16,41 @@ const NEXT_FREE_SENTINEL: u32 = u32::MAX;
 const SENTINEL_VALUE: f32 = f32::MAX;
 const CELL_WIDTH: f32 = 20.0;
 
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
+pub struct ColliderPair {
+    pub collider1: ColliderHandle,
+    pub collider2: ColliderHandle,
+}
+
+impl ColliderPair {
+    pub fn new(collider1: ColliderHandle, collider2: ColliderHandle) -> Self {
+        ColliderPair {
+            collider1,
+            collider2,
+        }
+    }
+
+    pub fn new_sorted(collider1: ColliderHandle, collider2: ColliderHandle) -> Self {
+        if collider1.into_raw_parts().0 <= collider2.into_raw_parts().0 {
+            Self::new(collider1, collider2)
+        } else {
+            Self::new(collider2, collider1)
+        }
+    }
+
+    pub fn swap(self) -> Self {
+        Self::new(self.collider2, self.collider1)
+    }
+
+    pub fn zero() -> Self {
+        Self {
+            collider1: ColliderHandle::from_raw_parts(0, 0),
+            collider2: ColliderHandle::from_raw_parts(0, 0),
+        }
+    }
+}
+
 pub enum BroadPhasePairEvent {
     AddPair(ColliderPair),
     DeletePair(ColliderPair),
diff --git a/src/geometry/contact_generator/trimesh_shape_contact_generator.rs b/src/geometry/contact_generator/trimesh_shape_contact_generator.rs
index 7dc0054..52ba9b7 100644
--- a/src/geometry/contact_generator/trimesh_shape_contact_generator.rs
+++ b/src/geometry/contact_generator/trimesh_shape_contact_generator.rs
@@ -1,7 +1,7 @@
 use crate::geometry::contact_generator::{
     ContactGenerationContext, PrimitiveContactGenerationContext,
 };
-use crate::geometry::{Collider, ContactManifold, Shape, Trimesh, WAABBHierarchyIntersections};
+use crate::geometry::{Collider, ContactManifold, Shape, Trimesh};
 use crate::ncollide::bounding_volume::{BoundingVolume, AABB};
 
 pub struct TrimeshShapeContactGeneratorWorkspace {
diff --git a/src/geometry/mod.rs b/src/geometry/mod.rs
index 4456961..562f962 100644
--- a/src/geometry/mod.rs
+++ b/src/geometry/mod.rs
@@ -43,8 +43,7 @@ pub type RayIntersection = ncollide::query::RayIntersection<f32>;
 
 #[cfg(feature = "simd-is-enabled")]
 pub(crate) use self::ball::WBall;
-pub(crate) use self::broad_phase::{ColliderPair, WAABBHierarchy, WAABBHierarchyIntersections};
-pub(crate) use self::broad_phase_multi_sap::BroadPhasePairEvent;
+pub(crate) use self::broad_phase_multi_sap::{BroadPhasePairEvent, ColliderPair};
 pub(crate) use self::collider_set::RemovedCollider;
 #[cfg(feature = "simd-is-enabled")]
 pub(crate) use self::contact::WContact;
@@ -58,7 +57,6 @@ pub(crate) use self::wquadtree::WQuadtree;
 //pub(crate) use self::z_order::z_cmp_floats;
 
 mod ball;
-mod broad_phase;
 mod broad_phase_multi_sap;
 mod capsule;
 mod collider;
diff --git a/src/geometry/proximity_detector/trimesh_shape_proximity_detector.rs b/src/geometry/proximity_detector/trimesh_shape_proximity_detector.rs
index 1fc5e1e..edf3085 100644
--- a/src/geometry/proximity_detector/trimesh_shape_proximity_detector.rs
+++ b/src/geometry/proximity_detector/trimesh_shape_proximity_detector.rs
@@ -1,7 +1,7 @@
 use crate::geometry::proximity_detector::{
     PrimitiveProximityDetectionContext, ProximityDetectionContext,
 };
-use crate::geometry::{Collider, Proximity, Shape, Trimesh, WAABBHierarchyIntersections};
+use crate::geometry::{Collider, Proximity, Shape, Trimesh};
 use crate::ncollide::bounding_volume::{BoundingVolume, AABB};
 
 pub struct TrimeshShapeProximityDetectorWorkspace {