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/trimesh.rs | 53 +++++++++++++++++-------------------------------- 1 file changed, 18 insertions(+), 35 deletions(-) (limited to 'src/geometry/trimesh.rs') diff --git a/src/geometry/trimesh.rs b/src/geometry/trimesh.rs index 62731b6..f9e6034 100644 --- a/src/geometry/trimesh.rs +++ b/src/geometry/trimesh.rs @@ -1,4 +1,4 @@ -use crate::geometry::{Triangle, WAABBHierarchy}; +use crate::geometry::{Triangle, WQuadtree}; use crate::math::{Isometry, Point}; use na::Point3; use ncollide::bounding_volume::{HasBoundingVolume, AABB}; @@ -7,7 +7,7 @@ use ncollide::bounding_volume::{HasBoundingVolume, AABB}; #[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] /// A triangle mesh. pub struct Trimesh { - waabb_tree: WAABBHierarchy, + wquadtree: WQuadtree, aabb: AABB, vertices: Vec>, indices: Vec>, @@ -25,41 +25,24 @@ impl Trimesh { "A triangle mesh must contain at least one triangle." ); - // z-sort the indices. - // indices.sort_unstable_by(|idx, jdx| { - // let ti = Triangle::new( - // vertices[idx[0] as usize], - // vertices[idx[1] as usize], - // vertices[idx[2] as usize], - // ); - // let tj = Triangle::new( - // vertices[jdx[0] as usize], - // vertices[jdx[1] as usize], - // vertices[jdx[2] as usize], - // ); - // let center_i = (ti.a.coords + ti.b.coords + ti.c.coords) / 3.0; - // let center_j = (tj.a.coords + tj.b.coords + tj.c.coords) / 3.0; - // crate::geometry::z_cmp_floats(center_i.as_slice(), center_j.as_slice()) - // .unwrap_or(std::cmp::Ordering::Equal) - // }); let aabb = AABB::from_points(&vertices); + let data = indices.iter().enumerate().map(|(i, idx)| { + let aabb = Triangle::new( + vertices[idx[0] as usize], + vertices[idx[1] as usize], + vertices[idx[2] as usize], + ) + .local_bounding_volume(); + (i, aabb) + }); - let aabbs: Vec<_> = indices - .iter() - .map(|idx| { - Triangle::new( - vertices[idx[0] as usize], - vertices[idx[1] as usize], - vertices[idx[2] as usize], - ) - .local_bounding_volume() - }) - .collect(); - - let waabb_tree = WAABBHierarchy::new(&aabbs); + let mut wquadtree = WQuadtree::new(); + // NOTE: we apply no dilation factor because we won't + // update this tree dynamically. + wquadtree.clear_and_rebuild(data, 0.0); Self { - waabb_tree, + wquadtree, aabb, vertices, indices, @@ -71,8 +54,8 @@ impl Trimesh { self.aabb.transform_by(pos) } - pub(crate) fn waabbs(&self) -> &WAABBHierarchy { - &self.waabb_tree + pub(crate) fn waabbs(&self) -> &WQuadtree { + &self.wquadtree } /// The number of triangles forming this mesh. -- cgit From 7c92848383b9f76bde010f00683a44453b2b456a Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Tue, 6 Oct 2020 14:17:18 +0200 Subject: Implement RayCast for the Trimesh. --- src/geometry/trimesh.rs | 52 ++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 51 insertions(+), 1 deletion(-) (limited to 'src/geometry/trimesh.rs') diff --git a/src/geometry/trimesh.rs b/src/geometry/trimesh.rs index f9e6034..dd8cb4b 100644 --- a/src/geometry/trimesh.rs +++ b/src/geometry/trimesh.rs @@ -1,5 +1,6 @@ -use crate::geometry::{Triangle, WQuadtree}; +use crate::geometry::{Ray, RayIntersection, Triangle, WQuadtree}; use crate::math::{Isometry, Point}; +use crate::ncollide::query::RayCast; use na::Point3; use ncollide::bounding_volume::{HasBoundingVolume, AABB}; @@ -103,3 +104,52 @@ impl Trimesh { } } } + +impl RayCast for Trimesh { + fn toi_and_normal_with_ray( + &self, + m: &Isometry, + ray: &Ray, + max_toi: f32, + solid: bool, + ) -> Option { + // FIXME: do a best-first search. + let mut intersections = Vec::new(); + let ls_ray = ray.inverse_transform_by(m); + self.wquadtree + .cast_ray(&ls_ray, max_toi, &mut intersections); + let mut best: Option = None; + + for inter in intersections { + let tri = self.triangle(inter); + if let Some(inter) = tri.toi_and_normal_with_ray(m, ray, max_toi, solid) { + if let Some(curr) = &mut best { + if curr.toi > inter.toi { + *curr = inter; + } + } else { + best = Some(inter); + } + } + } + + best + } + + fn intersects_ray(&self, m: &Isometry, ray: &Ray, max_toi: f32) -> bool { + // FIXME: do a best-first search. + let mut intersections = Vec::new(); + let ls_ray = ray.inverse_transform_by(m); + self.wquadtree + .cast_ray(&ls_ray, max_toi, &mut intersections); + + for inter in intersections { + let tri = self.triangle(inter); + if tri.intersects_ray(m, ray, max_toi) { + return true; + } + } + + false + } +} -- cgit From e87b73a2a20fee1ed333d564ba46dbf1c3ca75e2 Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Tue, 6 Oct 2020 15:49:22 +0200 Subject: Fix compilation in 2D. --- src/geometry/trimesh.rs | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'src/geometry/trimesh.rs') diff --git a/src/geometry/trimesh.rs b/src/geometry/trimesh.rs index dd8cb4b..b6e23e7 100644 --- a/src/geometry/trimesh.rs +++ b/src/geometry/trimesh.rs @@ -1,9 +1,14 @@ -use crate::geometry::{Ray, RayIntersection, Triangle, WQuadtree}; +use crate::geometry::{Triangle, WQuadtree}; use crate::math::{Isometry, Point}; -use crate::ncollide::query::RayCast; use na::Point3; use ncollide::bounding_volume::{HasBoundingVolume, AABB}; +#[cfg(feature = "dim3")] +use { + crate::geometry::{Ray, RayIntersection}, + ncollide::query::RayCast, +}; + #[derive(Clone)] #[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] /// A triangle mesh. @@ -105,6 +110,7 @@ impl Trimesh { } } +#[cfg(feature = "dim3")] impl RayCast for Trimesh { fn toi_and_normal_with_ray( &self, -- cgit