From 3c85a6ac41397cf95199933c6a93909bc070a844 Mon Sep 17 00:00:00 2001 From: Sébastien Crozet Date: Tue, 8 Sep 2020 21:18:17 +0200 Subject: Start implementing ray-casting. This adds a QueryPipeline structure responsible for scene queries. Currently this structure is able to perform a brute-force ray-cast. This commit also includes the beginning of implementation of a SIMD-based acceleration structure which will be used for these scene queries in the future. --- src/geometry/waabb.rs | 93 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 91 insertions(+), 2 deletions(-) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index c3853bc..702b5aa 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -1,15 +1,27 @@ #[cfg(feature = "serde-serialize")] use crate::math::DIM; -use crate::math::{Point, SimdBool, SimdFloat, SIMD_WIDTH}; +use crate::math::{Point, SIMD_WIDTH}; use ncollide::bounding_volume::AABB; -use simba::simd::{SimdPartialOrd, SimdValue}; +#[cfg(feature = "simd-is-enabled")] +use { + crate::math::{SimdBool, SimdFloat}, + simba::simd::{SimdPartialOrd, SimdValue}, +}; #[derive(Debug, Copy, Clone)] +#[cfg(feature = "simd-is-enabled")] pub(crate) struct WAABB { pub mins: Point, pub maxs: Point, } +#[derive(Debug, Copy, Clone)] +#[cfg(not(feature = "simd-is-enabled"))] +pub(crate) struct WAABB { + pub mins: [Point; SIMD_WIDTH], + pub maxs: [Point; SIMD_WIDTH], +} + #[cfg(feature = "serde-serialize")] impl serde::Serialize for WAABB { fn serialize(&self, serializer: S) -> Result @@ -18,16 +30,24 @@ impl serde::Serialize for WAABB { { use serde::ser::SerializeStruct; + #[cfg(feature = "simd-is-enabled")] let mins: Point<[f32; SIMD_WIDTH]> = Point::from( self.mins .coords .map(|e| array![|ii| e.extract(ii); SIMD_WIDTH]), ); + #[cfg(feature = "simd-is-enabled")] let maxs: Point<[f32; SIMD_WIDTH]> = Point::from( self.maxs .coords .map(|e| array![|ii| e.extract(ii); SIMD_WIDTH]), ); + + #[cfg(not(feature = "simd-is-enabled"))] + let mins = self.mins; + #[cfg(not(feature = "simd-is-enabled"))] + let maxs = self.maxs; + let mut waabb = serializer.serialize_struct("WAABB", 2)?; waabb.serialize_field("mins", &mins)?; waabb.serialize_field("maxs", &maxs)?; @@ -52,6 +72,7 @@ impl<'de> serde::Deserialize<'de> for WAABB { ) } + #[cfg(feature = "simd-is-enabled")] fn visit_seq(self, mut seq: A) -> Result where A: serde::de::SeqAccess<'de>, @@ -66,17 +87,36 @@ impl<'de> serde::Deserialize<'de> for WAABB { let maxs = Point::from(maxs.coords.map(|e| SimdFloat::from(e))); Ok(WAABB { mins, maxs }) } + + #[cfg(not(feature = "simd-is-enabled"))] + fn visit_seq(self, mut seq: A) -> Result + where + A: serde::de::SeqAccess<'de>, + { + let mins = seq + .next_element()? + .ok_or_else(|| serde::de::Error::invalid_length(0, &self))?; + let maxs = seq + .next_element()? + .ok_or_else(|| serde::de::Error::invalid_length(1, &self))?; + Ok(WAABB { mins, maxs }) + } } deserializer.deserialize_struct("WAABB", &["mins", "maxs"], Visitor {}) } } +#[cfg(feature = "simd-is-enabled")] impl WAABB { pub fn new(mins: Point, maxs: Point) -> Self { Self { mins, maxs } } + pub fn new_invalid() -> Self { + Self::splat(AABB::new_invalid()) + } + pub fn splat(aabb: AABB) -> Self { Self { mins: Point::splat(aabb.mins), @@ -103,6 +143,7 @@ impl WAABB { } } +#[cfg(feature = "simd-is-enabled")] impl From<[AABB; SIMD_WIDTH]> for WAABB { fn from(aabbs: [AABB; SIMD_WIDTH]) -> Self { let mins = array![|ii| aabbs[ii].mins; SIMD_WIDTH]; @@ -114,3 +155,51 @@ impl From<[AABB; SIMD_WIDTH]> for WAABB { } } } + +#[cfg(not(feature = "simd-is-enabled"))] +impl WAABB { + pub fn new_invalid() -> Self { + Self::splat(AABB::new_invalid()) + } + + pub fn splat(aabb: AABB) -> Self { + Self { + mins: [aabb.mins; SIMD_WIDTH], + maxs: [aabb.maxs; SIMD_WIDTH], + } + } + + #[cfg(feature = "dim2")] + pub fn intersects_lanewise(&self, other: &WAABB) -> [bool; SIMD_WIDTH] { + array![|ii| + self.mins[ii].x <= other.maxs[ii].x + && other.mins[ii].x <= self.maxs[ii].x + && self.mins[ii].y <= other.maxs[ii].y + && other.mins[ii].y <= self.maxs[ii].y + ; SIMD_WIDTH + ] + } + + #[cfg(feature = "dim3")] + pub fn intersects_lanewise(&self, other: &WAABB) -> [bool; SIMD_WIDTH] { + array![|ii| + self.mins[ii].x <= other.maxs[ii].x + && other.mins[ii].x <= self.maxs[ii].x + && self.mins[ii].y <= other.maxs[ii].y + && other.mins[ii].y <= self.maxs[ii].y + && self.mins[ii].z <= other.maxs[ii].z + && other.mins[ii].z <= self.maxs[ii].z + ; SIMD_WIDTH + ] + } +} + +#[cfg(not(feature = "simd-is-enabled"))] +impl From<[AABB; SIMD_WIDTH]> for WAABB { + fn from(aabbs: [AABB; SIMD_WIDTH]) -> Self { + let mins = array![|ii| aabbs[ii].mins; SIMD_WIDTH]; + let maxs = array![|ii| aabbs[ii].maxs; SIMD_WIDTH]; + + WAABB { mins, maxs } + } +} -- cgit From 2dda0e5ce48ed0d93b4b0fa3098ba08f59a50a0a Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Mon, 21 Sep 2020 17:26:57 +0200 Subject: Complete the WQuadtree construction and ray-cast. --- src/geometry/waabb.rs | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 63 insertions(+), 1 deletion(-) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index 702b5aa..0664a50 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -1,13 +1,39 @@ +use crate::geometry::Ray; #[cfg(feature = "serde-serialize")] use crate::math::DIM; -use crate::math::{Point, SIMD_WIDTH}; +use crate::math::{Point, Vector, SIMD_WIDTH}; +use crate::utils; use ncollide::bounding_volume::AABB; +use num::{One, Zero}; #[cfg(feature = "simd-is-enabled")] use { crate::math::{SimdBool, SimdFloat}, simba::simd::{SimdPartialOrd, SimdValue}, }; +#[derive(Debug, Copy, Clone)] +#[cfg(feature = "simd-is-enabled")] +pub(crate) struct WRay { + pub origin: Point, + pub dir: Vector, +} + +impl WRay { + pub fn splat(ray: Ray) -> Self { + Self { + origin: Point::splat(ray.origin), + dir: Vector::splat(ray.dir), + } + } +} + +#[derive(Debug, Copy, Clone)] +#[cfg(not(feature = "simd-is-enabled"))] +pub(crate) struct WRay { + pub origin: [Point; SIMD_WIDTH], + pub dir: [Vector; SIMD_WIDTH], +} + #[derive(Debug, Copy, Clone)] #[cfg(feature = "simd-is-enabled")] pub(crate) struct WAABB { @@ -124,6 +150,42 @@ impl WAABB { } } + pub fn intersects_ray(&self, ray: &WRay, max_toi: SimdFloat) -> SimdBool { + let _0 = SimdFloat::zero(); + let _1 = SimdFloat::one(); + let _infinity = SimdFloat::splat(f32::MAX); + + let mut hit = SimdBool::splat(true); + let mut tmin = SimdFloat::zero(); + let mut tmax = max_toi; + + // TODO: could this be optimized more considering we really just need a boolean answer? + for i in 0usize..DIM { + let is_not_zero = ray.dir[i].simd_ne(_0); + let is_zero_test = + (ray.origin[i].simd_ge(self.mins[i]) & ray.origin[i].simd_le(self.maxs[i])); + let is_not_zero_test = { + let denom = _1 / ray.dir[i]; + let mut inter_with_near_plane = + ((self.mins[i] - ray.origin[i]) * denom).select(is_not_zero, -_infinity); + let mut inter_with_far_plane = + ((self.maxs[i] - ray.origin[i]) * denom).select(is_not_zero, _infinity); + + let gt = inter_with_near_plane.simd_gt(inter_with_far_plane); + utils::simd_swap(gt, &mut inter_with_near_plane, &mut inter_with_far_plane); + + tmin = tmin.simd_max(inter_with_near_plane); + tmax = tmax.simd_min(inter_with_far_plane); + + tmin.simd_le(tmax) + }; + + hit = hit & is_not_zero_test.select(is_not_zero, is_zero_test); + } + + hit + } + #[cfg(feature = "dim2")] pub fn intersects_lanewise(&self, other: &WAABB) -> SimdBool { self.mins.x.simd_le(other.maxs.x) -- cgit From 56f6051b047aded906b8a89cbc66672c6f1e698e Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Mon, 21 Sep 2020 18:29:32 +0200 Subject: Start adding incremental topology update for the WQuadtree. --- src/geometry/waabb.rs | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index 0664a50..c04514a 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -150,6 +150,11 @@ impl WAABB { } } + pub fn replace(&mut self, i: usize, aabb: AABB) { + self.mins.replace(i, aabb.mins); + self.maxs.replace(i, aabb.maxs); + } + pub fn intersects_ray(&self, ray: &WRay, max_toi: SimdFloat) -> SimdBool { let _0 = SimdFloat::zero(); let _1 = SimdFloat::one(); -- cgit From a7d77a01447d2b77694b2a957d000790af60b383 Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Tue, 22 Sep 2020 15:29:29 +0200 Subject: Add non-topological WQuadtree update. --- src/geometry/waabb.rs | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index c04514a..0a90801 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -150,6 +150,12 @@ impl WAABB { } } + pub fn dilate_by_factor(&mut self, factor: SimdFloat) { + let dilation = (self.maxs - self.mins) * factor; + self.mins -= dilation; + self.maxs += dilation; + } + pub fn replace(&mut self, i: usize, aabb: AABB) { self.mins.replace(i, aabb.mins); self.maxs.replace(i, aabb.maxs); @@ -191,6 +197,24 @@ impl WAABB { hit } + #[cfg(feature = "dim2")] + pub fn contains_lanewise(&self, other: &WAABB) -> SimdBool { + self.mins.x.simd_le(other.mins.x) + & self.mins.y.simd_le(other.mins.y) + & self.maxs.x.simd_ge(other.maxs.x) + & self.maxs.y.simd_ge(other.maxs.y) + } + + #[cfg(feature = "dim3")] + pub fn contains_lanewise(&self, other: &WAABB) -> SimdBool { + self.mins.x.simd_le(other.mins.x) + & self.mins.y.simd_le(other.mins.y) + & self.mins.z.simd_le(other.mins.z) + & self.maxs.x.simd_ge(other.maxs.x) + & self.maxs.y.simd_ge(other.maxs.y) + & self.maxs.z.simd_ge(other.maxs.z) + } + #[cfg(feature = "dim2")] pub fn intersects_lanewise(&self, other: &WAABB) -> SimdBool { self.mins.x.simd_le(other.maxs.x) @@ -208,6 +232,13 @@ impl WAABB { & self.mins.z.simd_le(other.maxs.z) & other.mins.z.simd_le(self.maxs.z) } + + pub fn to_merged_aabb(&self) -> AABB { + AABB::new( + self.mins.coords.map(|e| e.simd_horizontal_min()).into(), + self.maxs.coords.map(|e| e.simd_horizontal_max()).into(), + ) + } } #[cfg(feature = "simd-is-enabled")] -- cgit From 84bd60e4a5b88c9aa824797c8a444945b46e96b2 Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Tue, 22 Sep 2020 17:57:29 +0200 Subject: Fix compilation when SIMD is not enabled. --- src/geometry/waabb.rs | 89 --------------------------------------------------- 1 file changed, 89 deletions(-) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index 0a90801..4981373 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -5,14 +5,12 @@ use crate::math::{Point, Vector, SIMD_WIDTH}; use crate::utils; use ncollide::bounding_volume::AABB; use num::{One, Zero}; -#[cfg(feature = "simd-is-enabled")] use { crate::math::{SimdBool, SimdFloat}, simba::simd::{SimdPartialOrd, SimdValue}, }; #[derive(Debug, Copy, Clone)] -#[cfg(feature = "simd-is-enabled")] pub(crate) struct WRay { pub origin: Point, pub dir: Vector, @@ -28,26 +26,11 @@ impl WRay { } #[derive(Debug, Copy, Clone)] -#[cfg(not(feature = "simd-is-enabled"))] -pub(crate) struct WRay { - pub origin: [Point; SIMD_WIDTH], - pub dir: [Vector; SIMD_WIDTH], -} - -#[derive(Debug, Copy, Clone)] -#[cfg(feature = "simd-is-enabled")] pub(crate) struct WAABB { pub mins: Point, pub maxs: Point, } -#[derive(Debug, Copy, Clone)] -#[cfg(not(feature = "simd-is-enabled"))] -pub(crate) struct WAABB { - pub mins: [Point; SIMD_WIDTH], - pub maxs: [Point; SIMD_WIDTH], -} - #[cfg(feature = "serde-serialize")] impl serde::Serialize for WAABB { fn serialize(&self, serializer: S) -> Result @@ -56,24 +39,17 @@ impl serde::Serialize for WAABB { { use serde::ser::SerializeStruct; - #[cfg(feature = "simd-is-enabled")] let mins: Point<[f32; SIMD_WIDTH]> = Point::from( self.mins .coords .map(|e| array![|ii| e.extract(ii); SIMD_WIDTH]), ); - #[cfg(feature = "simd-is-enabled")] let maxs: Point<[f32; SIMD_WIDTH]> = Point::from( self.maxs .coords .map(|e| array![|ii| e.extract(ii); SIMD_WIDTH]), ); - #[cfg(not(feature = "simd-is-enabled"))] - let mins = self.mins; - #[cfg(not(feature = "simd-is-enabled"))] - let maxs = self.maxs; - let mut waabb = serializer.serialize_struct("WAABB", 2)?; waabb.serialize_field("mins", &mins)?; waabb.serialize_field("maxs", &maxs)?; @@ -98,7 +74,6 @@ impl<'de> serde::Deserialize<'de> for WAABB { ) } - #[cfg(feature = "simd-is-enabled")] fn visit_seq(self, mut seq: A) -> Result where A: serde::de::SeqAccess<'de>, @@ -113,27 +88,12 @@ impl<'de> serde::Deserialize<'de> for WAABB { let maxs = Point::from(maxs.coords.map(|e| SimdFloat::from(e))); Ok(WAABB { mins, maxs }) } - - #[cfg(not(feature = "simd-is-enabled"))] - fn visit_seq(self, mut seq: A) -> Result - where - A: serde::de::SeqAccess<'de>, - { - let mins = seq - .next_element()? - .ok_or_else(|| serde::de::Error::invalid_length(0, &self))?; - let maxs = seq - .next_element()? - .ok_or_else(|| serde::de::Error::invalid_length(1, &self))?; - Ok(WAABB { mins, maxs }) - } } deserializer.deserialize_struct("WAABB", &["mins", "maxs"], Visitor {}) } } -#[cfg(feature = "simd-is-enabled")] impl WAABB { pub fn new(mins: Point, maxs: Point) -> Self { Self { mins, maxs } @@ -241,7 +201,6 @@ impl WAABB { } } -#[cfg(feature = "simd-is-enabled")] impl From<[AABB; SIMD_WIDTH]> for WAABB { fn from(aabbs: [AABB; SIMD_WIDTH]) -> Self { let mins = array![|ii| aabbs[ii].mins; SIMD_WIDTH]; @@ -253,51 +212,3 @@ impl From<[AABB; SIMD_WIDTH]> for WAABB { } } } - -#[cfg(not(feature = "simd-is-enabled"))] -impl WAABB { - pub fn new_invalid() -> Self { - Self::splat(AABB::new_invalid()) - } - - pub fn splat(aabb: AABB) -> Self { - Self { - mins: [aabb.mins; SIMD_WIDTH], - maxs: [aabb.maxs; SIMD_WIDTH], - } - } - - #[cfg(feature = "dim2")] - pub fn intersects_lanewise(&self, other: &WAABB) -> [bool; SIMD_WIDTH] { - array![|ii| - self.mins[ii].x <= other.maxs[ii].x - && other.mins[ii].x <= self.maxs[ii].x - && self.mins[ii].y <= other.maxs[ii].y - && other.mins[ii].y <= self.maxs[ii].y - ; SIMD_WIDTH - ] - } - - #[cfg(feature = "dim3")] - pub fn intersects_lanewise(&self, other: &WAABB) -> [bool; SIMD_WIDTH] { - array![|ii| - self.mins[ii].x <= other.maxs[ii].x - && other.mins[ii].x <= self.maxs[ii].x - && self.mins[ii].y <= other.maxs[ii].y - && other.mins[ii].y <= self.maxs[ii].y - && self.mins[ii].z <= other.maxs[ii].z - && other.mins[ii].z <= self.maxs[ii].z - ; SIMD_WIDTH - ] - } -} - -#[cfg(not(feature = "simd-is-enabled"))] -impl From<[AABB; SIMD_WIDTH]> for WAABB { - fn from(aabbs: [AABB; SIMD_WIDTH]) -> Self { - let mins = array![|ii| aabbs[ii].mins; SIMD_WIDTH]; - let maxs = array![|ii| aabbs[ii].maxs; SIMD_WIDTH]; - - WAABB { mins, maxs } - } -} -- cgit From c031f96ac548645932c5605bfc17869618e9212b Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Mon, 28 Sep 2020 10:04:56 +0200 Subject: Fix compilation when parallelism is not enabled. --- src/geometry/waabb.rs | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index 4981373..1706370 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -1,7 +1,5 @@ use crate::geometry::Ray; -#[cfg(feature = "serde-serialize")] -use crate::math::DIM; -use crate::math::{Point, Vector, SIMD_WIDTH}; +use crate::math::{Point, Vector, DIM, SIMD_WIDTH}; use crate::utils; use ncollide::bounding_volume::AABB; use num::{One, Zero}; -- cgit From 8e432b298bd71df7d1b776b77c15713d9bea280e Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Tue, 6 Oct 2020 10:46:59 +0200 Subject: Make the WQuadTree more generic and use it as the trimesh acceleration structure. --- src/geometry/waabb.rs | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index 1706370..cc420d9 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -156,7 +156,7 @@ impl WAABB { } #[cfg(feature = "dim2")] - pub fn contains_lanewise(&self, other: &WAABB) -> SimdBool { + pub fn contains(&self, other: &WAABB) -> SimdBool { self.mins.x.simd_le(other.mins.x) & self.mins.y.simd_le(other.mins.y) & self.maxs.x.simd_ge(other.maxs.x) @@ -164,7 +164,7 @@ impl WAABB { } #[cfg(feature = "dim3")] - pub fn contains_lanewise(&self, other: &WAABB) -> SimdBool { + pub fn contains(&self, other: &WAABB) -> SimdBool { self.mins.x.simd_le(other.mins.x) & self.mins.y.simd_le(other.mins.y) & self.mins.z.simd_le(other.mins.z) @@ -174,7 +174,7 @@ impl WAABB { } #[cfg(feature = "dim2")] - pub fn intersects_lanewise(&self, other: &WAABB) -> SimdBool { + pub fn intersects(&self, other: &WAABB) -> SimdBool { self.mins.x.simd_le(other.maxs.x) & other.mins.x.simd_le(self.maxs.x) & self.mins.y.simd_le(other.maxs.y) @@ -182,7 +182,7 @@ impl WAABB { } #[cfg(feature = "dim3")] - pub fn intersects_lanewise(&self, other: &WAABB) -> SimdBool { + pub fn intersects(&self, other: &WAABB) -> SimdBool { self.mins.x.simd_le(other.maxs.x) & other.mins.x.simd_le(self.maxs.x) & self.mins.y.simd_le(other.maxs.y) -- cgit From 682ff61f94931ef205a9f81e7d00417ac88537c1 Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Tue, 6 Oct 2020 15:23:48 +0200 Subject: Don't let the PubSub internal offsets overflow + fix some warnings. --- src/geometry/waabb.rs | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) (limited to 'src/geometry/waabb.rs') diff --git a/src/geometry/waabb.rs b/src/geometry/waabb.rs index cc420d9..645ac04 100644 --- a/src/geometry/waabb.rs +++ b/src/geometry/waabb.rs @@ -93,10 +93,6 @@ impl<'de> serde::Deserialize<'de> for WAABB { } impl WAABB { - pub fn new(mins: Point, maxs: Point) -> Self { - Self { mins, maxs } - } - pub fn new_invalid() -> Self { Self::splat(AABB::new_invalid()) } @@ -132,7 +128,7 @@ impl WAABB { for i in 0usize..DIM { let is_not_zero = ray.dir[i].simd_ne(_0); let is_zero_test = - (ray.origin[i].simd_ge(self.mins[i]) & ray.origin[i].simd_le(self.maxs[i])); + ray.origin[i].simd_ge(self.mins[i]) & ray.origin[i].simd_le(self.maxs[i]); let is_not_zero_test = { let denom = _1 / ray.dir[i]; let mut inter_with_near_plane = -- cgit