From d7ff0826d2b1f0243aa1b54589796c66775f4f0c Mon Sep 17 00:00:00 2001 From: Robert Hrusecky Date: Mon, 5 Oct 2020 18:43:35 -0500 Subject: Simple fix: Always remove empty SAPRegions --- src/geometry/broad_phase_multi_sap.rs | 39 +++++++++++++++++++++-------------- 1 file changed, 23 insertions(+), 16 deletions(-) (limited to 'src') diff --git a/src/geometry/broad_phase_multi_sap.rs b/src/geometry/broad_phase_multi_sap.rs index 054fccf..db588cf 100644 --- a/src/geometry/broad_phase_multi_sap.rs +++ b/src/geometry/broad_phase_multi_sap.rs @@ -204,13 +204,13 @@ impl SAPAxis { } } - fn delete_out_of_bounds_proxies(&self, existing_proxies: &mut BitVec) -> bool { - let mut deleted_any = false; + fn delete_out_of_bounds_proxies(&self, existing_proxies: &mut BitVec) -> usize { + let mut deleted = 0; for endpoint in &self.endpoints { if endpoint.value < self.min_bound { if endpoint.is_end() { existing_proxies.set(endpoint.proxy() as usize, false); - deleted_any = true; + deleted += 1; } } else { break; @@ -221,14 +221,14 @@ impl SAPAxis { if endpoint.value > self.max_bound { if endpoint.is_start() { existing_proxies.set(endpoint.proxy() as usize, false); - deleted_any = true; + deleted += 1; } } else { break; } } - deleted_any + deleted } fn delete_out_of_bounds_endpoints(&mut self, existing_proxies: &BitVec) { @@ -304,6 +304,7 @@ struct SAPRegion { #[cfg_attr(feature = "serde-serialize", serde(skip))] to_insert: Vec, // Workspace need_update: bool, + proxy_count: usize, } impl SAPRegion { @@ -319,6 +320,7 @@ impl SAPRegion { existing_proxies: BitVec::new(), to_insert: Vec::new(), need_update: false, + proxy_count: 0, } } @@ -338,6 +340,7 @@ impl SAPRegion { if !self.existing_proxies[proxy_id] { self.to_insert.push(proxy_id); self.existing_proxies.set(proxy_id, true); + self.proxy_count += 1; false } else { self.need_update = true; @@ -348,15 +351,14 @@ impl SAPRegion { pub fn update(&mut self, proxies: &Proxies, reporting: &mut HashMap<(u32, u32), bool>) { if self.need_update { // Update endpoints. - let mut deleted_any = false; + let mut deleted = 0; for dim in 0..DIM { self.axii[dim].update_endpoints(dim, proxies, reporting); - deleted_any = self.axii[dim] - .delete_out_of_bounds_proxies(&mut self.existing_proxies) - || deleted_any; + deleted += self.axii[dim].delete_out_of_bounds_proxies(&mut self.existing_proxies); } - if deleted_any { + if deleted > 0 { + self.proxy_count -= deleted; for dim in 0..DIM { self.axii[dim].delete_out_of_bounds_endpoints(&self.existing_proxies); } @@ -588,11 +590,18 @@ impl BroadPhase { } } + fn update_regions(&mut self) { + for (_, region) in &mut self.regions { + region.update(&self.proxies, &mut self.reporting); + } + + // Remove all the empty regions + self.regions.retain(|_, region| region.proxy_count > 0); + } + pub(crate) fn complete_removals(&mut self) { if self.deleted_any { - for (_, region) in &mut self.regions { - region.update(&self.proxies, &mut self.reporting); - } + self.update_regions(); // NOTE: we don't care about reporting pairs. self.reporting.clear(); @@ -604,9 +613,7 @@ impl BroadPhase { // println!("num regions: {}", self.regions.len()); self.reporting.clear(); - for (_, region) in &mut self.regions { - region.update(&self.proxies, &mut self.reporting) - } + self.update_regions(); // Convert reports to broad phase events. // let t = instant::now(); -- cgit From c25c5c5192d843d96d300aa3c4d711a43f709c54 Mon Sep 17 00:00:00 2001 From: Robert Hrusecky Date: Mon, 5 Oct 2020 23:20:03 -0500 Subject: Bug fix: newly empty regions not updating SAPRegions which became empty in the last frame need to be updated one more time in order to remove the last proxy. --- src/geometry/broad_phase_multi_sap.rs | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/geometry/broad_phase_multi_sap.rs b/src/geometry/broad_phase_multi_sap.rs index db588cf..84e05d9 100644 --- a/src/geometry/broad_phase_multi_sap.rs +++ b/src/geometry/broad_phase_multi_sap.rs @@ -303,7 +303,7 @@ struct SAPRegion { existing_proxies: BitVec, #[cfg_attr(feature = "serde-serialize", serde(skip))] to_insert: Vec, // Workspace - need_update: bool, + update_count: usize, proxy_count: usize, } @@ -319,7 +319,7 @@ impl SAPRegion { axii, existing_proxies: BitVec::new(), to_insert: Vec::new(), - need_update: false, + update_count: 0, proxy_count: 0, } } @@ -328,7 +328,7 @@ impl SAPRegion { // We keep the proxy_id as argument for uniformity with the "preupdate" // method. However we don't actually need it because the deletion will be // handled transparently during the next update. - self.need_update = true; + self.update_count = 1; } pub fn preupdate_proxy(&mut self, proxy_id: usize) -> bool { @@ -343,13 +343,16 @@ impl SAPRegion { self.proxy_count += 1; false } else { - self.need_update = true; + // Here we need a second update if all proxies exit this region. In this case, we need + // to delete the final proxy, but the region may not have AABBs overlapping it, so it + // wouldn't get an update otherwise. + self.update_count = 2; true } } pub fn update(&mut self, proxies: &Proxies, reporting: &mut HashMap<(u32, u32), bool>) { - if self.need_update { + if self.update_count > 0 { // Update endpoints. let mut deleted = 0; for dim in 0..DIM { @@ -364,7 +367,7 @@ impl SAPRegion { } } - self.need_update = false; + self.update_count -= 1; } if !self.to_insert.is_empty() { -- cgit From b614b3de5ed388ae0d848f00cc026b1c222584a3 Mon Sep 17 00:00:00 2001 From: Robert Hrusecky Date: Tue, 6 Oct 2020 02:14:18 -0500 Subject: Fix edge case --- src/geometry/broad_phase_multi_sap.rs | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'src') diff --git a/src/geometry/broad_phase_multi_sap.rs b/src/geometry/broad_phase_multi_sap.rs index 84e05d9..bb30e14 100644 --- a/src/geometry/broad_phase_multi_sap.rs +++ b/src/geometry/broad_phase_multi_sap.rs @@ -377,6 +377,10 @@ impl SAPRegion { } self.axii[0].batch_insert(0, &self.to_insert, proxies, Some(reporting)); self.to_insert.clear(); + + // In the rare event that all proxies leave this region in the next step, we need an + // update to remove them. + self.update_count = 1; } } } -- cgit From 0c1b210109e6d4816dc54f2a6dc93e8d6beb5089 Mon Sep 17 00:00:00 2001 From: Robert Hrusecky Date: Tue, 6 Oct 2020 14:01:48 -0500 Subject: Fix corner case: exit on multiple axes --- src/geometry/broad_phase_multi_sap.rs | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/geometry/broad_phase_multi_sap.rs b/src/geometry/broad_phase_multi_sap.rs index bb30e14..10c0c8b 100644 --- a/src/geometry/broad_phase_multi_sap.rs +++ b/src/geometry/broad_phase_multi_sap.rs @@ -208,8 +208,9 @@ impl SAPAxis { let mut deleted = 0; for endpoint in &self.endpoints { if endpoint.value < self.min_bound { - if endpoint.is_end() { - existing_proxies.set(endpoint.proxy() as usize, false); + let proxy_idx = endpoint.proxy() as usize; + if endpoint.is_end() && existing_proxies[proxy_idx] { + existing_proxies.set(proxy_idx, false); deleted += 1; } } else { @@ -219,7 +220,8 @@ impl SAPAxis { for endpoint in self.endpoints.iter().rev() { if endpoint.value > self.max_bound { - if endpoint.is_start() { + let proxy_idx = endpoint.proxy() as usize; + if endpoint.is_start() && existing_proxies[proxy_idx] { existing_proxies.set(endpoint.proxy() as usize, false); deleted += 1; } -- cgit From 1097c630062129cc0a5137ac18e5bfbecf48f85a Mon Sep 17 00:00:00 2001 From: Robert Hrusecky Date: Sat, 31 Oct 2020 20:55:17 -0500 Subject: Add a cache of empty regions avoiding reallocation --- src/geometry/broad_phase_multi_sap.rs | 60 +++++++++++++++++++++++++++++------ 1 file changed, 51 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/geometry/broad_phase_multi_sap.rs b/src/geometry/broad_phase_multi_sap.rs index d76f026..10f20be 100644 --- a/src/geometry/broad_phase_multi_sap.rs +++ b/src/geometry/broad_phase_multi_sap.rs @@ -359,6 +359,36 @@ impl SAPRegion { } } + pub fn recycle(bounds: AABB, mut old: Self) -> Self { + // Correct the bounds + for (axis, &bound) in old.axes.iter_mut().zip(bounds.mins.iter()) { + axis.min_bound = bound; + } + for (axis, &bound) in old.axes.iter_mut().zip(bounds.maxs.iter()) { + axis.max_bound = bound; + } + + old.update_count = 0; + + // The rest of the fields should be "empty" + assert_eq!(old.proxy_count, 0); + assert!(old.to_insert.is_empty()); + debug_assert!(!old.existing_proxies.any()); + for axis in old.axes.iter() { + assert!(axis.endpoints.len() == 2); // Account for sentinels + } + + old + } + + pub fn recycle_or_new(bounds: AABB, pool: &mut Vec) -> Self { + if let Some(old) = pool.pop() { + Self::recycle(bounds, old) + } else { + Self::new(bounds) + } + } + pub fn predelete_proxy(&mut self, _proxy_id: usize) { // We keep the proxy_id as argument for uniformity with the "preupdate" // method. However we don't actually need it because the deletion will be @@ -427,6 +457,8 @@ pub struct BroadPhase { regions: HashMap, SAPRegion>, removed_colliders: Option>, deleted_any: bool, + region_pool: Vec, + points_to_remove: Vec>, // Workspace // We could think serializing this workspace is useless. // It turns out is is important to serialize at least its capacity // and restore this capacity when deserializing the hashmap. @@ -517,6 +549,8 @@ impl BroadPhase { removed_colliders: None, proxies: Proxies::new(), regions: HashMap::default(), + region_pool: Vec::new(), + points_to_remove: Vec::new(), reporting: HashMap::default(), deleted_any: false, } @@ -617,15 +651,16 @@ impl BroadPhase { let start = point_key(aabb.mins); let end = point_key(aabb.maxs); + let regions = &mut self.regions; + let pool = &mut self.region_pool; #[cfg(feature = "dim2")] for i in start.x..=end.x { for j in start.y..=end.y { let region_key = Point::new(i, j); let region_bounds = region_aabb(region_key); - let region = self - .regions + let region = regions .entry(region_key) - .or_insert_with(|| SAPRegion::new(region_bounds)); + .or_insert_with(|| SAPRegion::recycle_or_new(region_bounds, pool)); let _ = region.preupdate_proxy(proxy_id); } } @@ -636,10 +671,9 @@ impl BroadPhase { for k in start.z..=end.z { let region_key = Point::new(i, j, k); let region_bounds = region_aabb(region_key); - let region = self - .regions + let region = regions .entry(region_key) - .or_insert_with(|| SAPRegion::new(region_bounds)); + .or_insert_with(|| SAPRegion::recycle_or_new(region_bounds, pool)); let _ = region.preupdate_proxy(proxy_id); } } @@ -649,12 +683,20 @@ impl BroadPhase { } fn update_regions(&mut self) { - for (_, region) in &mut self.regions { + for (point, region) in &mut self.regions { region.update(&self.proxies, &mut self.reporting); + if region.proxy_count == 0 { + self.points_to_remove.push(*point); + } } - // Remove all the empty regions - self.regions.retain(|_, region| region.proxy_count > 0); + // Remove all the empty regions and store them in the region pool + let regions = &mut self.regions; + self.region_pool.extend( + self.points_to_remove + .drain(..) + .map(|p| regions.remove(&p).unwrap()), + ); } pub(crate) fn complete_removals(&mut self) { -- cgit