rhusics_core/collide/
mod.rs

1//! Generic data structures and algorithms for collision detection
2
3pub use collision::prelude::Primitive;
4pub use collision::{CollisionStrategy, ComputeBound, Contact};
5
6pub mod broad;
7pub mod narrow;
8
9use std::collections::HashSet;
10use std::fmt::Debug;
11use std::hash::Hash;
12
13use cgmath::prelude::*;
14use collision::dbvt::{DynamicBoundingVolumeTree, TreeValue, TreeValueWrapped};
15use collision::prelude::*;
16
17use self::broad::{broad_collide, BroadPhase};
18use self::narrow::{narrow_collide, NarrowPhase};
19
20/// Used to check if two shapes should be checked for collisions
21pub trait Collider {
22    /// Should shapes generate contact events
23    fn should_generate_contacts(&self, other: &Self) -> bool;
24}
25
26impl<'a> Collider for () {
27    fn should_generate_contacts(&self, _: &Self) -> bool {
28        true
29    }
30}
31
32/// Control continuous mode for shapes
33#[derive(Debug, Clone, PartialOrd, PartialEq)]
34#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
35pub enum CollisionMode {
36    /// Discrete collision mode
37    Discrete,
38
39    /// Continuous collision mode
40    Continuous,
41}
42
43/// Contains all contact information for a single contact, together with IDs of the colliding bodies
44///
45/// # Type parameters
46///
47/// - `ID`: The ID type of the body. This is supplied by the user of the library. In the ECS case,
48///         this will be [`Entity`](https://docs.rs/specs/0.9.5/specs/struct.Entity.html).
49/// - `V`: cgmath vector type
50#[derive(Debug, Clone)]
51pub struct ContactEvent<ID, P>
52where
53    P: EuclideanSpace,
54    P::Diff: Debug,
55{
56    /// The ids of the two colliding bodies
57    pub bodies: (ID, ID),
58
59    /// The contact between the colliding bodies
60    pub contact: Contact<P>,
61}
62
63impl<ID, P> ContactEvent<ID, P>
64where
65    ID: Clone + Debug,
66    P: EuclideanSpace,
67    P::Diff: VectorSpace + Zero + Debug,
68{
69    /// Create a new contact event
70    pub fn new(bodies: (ID, ID), contact: Contact<P>) -> Self {
71        Self { bodies, contact }
72    }
73
74    /// Convenience function to create a contact set with a simple [`Contact`](struct.Contact.html).
75    pub fn new_simple(strategy: CollisionStrategy, bodies: (ID, ID)) -> Self {
76        Self::new(bodies, Contact::new(strategy))
77    }
78}
79
80/// Collision shape describing a complete collision object in the collision world.
81///
82/// Can handle both convex shapes, and concave shapes, by subdividing the concave shapes into
83/// multiple convex shapes. This task is up to the user of the library to perform, no subdivision is
84/// done automatically in the library.
85///
86/// Contains cached information about the base bounding box containing all primitives,
87/// in model space coordinates. Also contains a cached version of the transformed bounding box,
88/// in world space coordinates.
89///
90/// Also have details about what collision strategy/mode to use for contact resolution with this
91/// shape.
92///
93/// ### Type parameters:
94///
95/// - `P`: Primitive type
96/// - `T`: Transform type
97/// - `B`: Bounding volume type
98/// - `Y`: Shape type (see `Collider`)
99#[derive(Debug, Clone)]
100#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
101pub struct CollisionShape<P, T, B, Y = ()>
102where
103    P: Primitive,
104{
105    /// Enable/Disable collision detection for this shape
106    pub enabled: bool,
107    base_bound: B,
108    transformed_bound: B,
109    primitives: Vec<(P, T)>,
110    strategy: CollisionStrategy,
111    mode: CollisionMode,
112    ty: Y,
113}
114
115impl<P, T, B, Y> CollisionShape<P, T, B, Y>
116where
117    P: Primitive + ComputeBound<B>,
118    B: Bound<Point = P::Point> + Union<B, Output = B> + Clone,
119    T: Transform<P::Point>,
120    Y: Default,
121{
122    /// Create a new collision shape, with multiple collision primitives.
123    ///
124    /// Will compute and cache the base bounding box that contains all the given primitives,
125    /// in model space coordinates.
126    ///
127    /// # Parameters
128    ///
129    /// - `strategy`: The collision strategy to use for this shape.
130    /// - `primitives`: List of all primitives that make up this shape.
131    /// - `ty`: The shape type, use () if not needed
132    pub fn new_complex(
133        strategy: CollisionStrategy,
134        mode: CollisionMode,
135        primitives: Vec<(P, T)>,
136        ty: Y,
137    ) -> Self {
138        let bound: B = get_bound(&primitives);
139        Self {
140            base_bound: bound.clone(),
141            primitives,
142            enabled: true,
143            transformed_bound: bound,
144            strategy,
145            mode,
146            ty,
147        }
148    }
149
150    /// Convenience function to create a simple collision shape with only a single given primitive,
151    /// with no local-to-model transform.
152    ///
153    /// # Parameters
154    ///
155    /// - `strategy`: The collision strategy to use for this shape.
156    /// - `primitive`: The collision primitive.
157    pub fn new_simple(strategy: CollisionStrategy, mode: CollisionMode, primitive: P) -> Self {
158        Self::new_complex(
159            strategy,
160            mode,
161            vec![(primitive, T::one())],
162            Default::default(),
163        )
164    }
165
166    /// Convenience function to create a simple collision shape with only a single given primitive,
167    /// and a shape type, with no local-to-model transform.
168    ///
169    /// # Parameters
170    ///
171    /// - `strategy`: The collision strategy to use for this shape.
172    /// - `primitive`: The collision primitive.
173    pub fn new_simple_with_type(
174        strategy: CollisionStrategy,
175        mode: CollisionMode,
176        primitive: P,
177        ty: Y,
178    ) -> Self {
179        Self::new_complex(strategy, mode, vec![(primitive, T::one())], ty)
180    }
181
182    /// Convenience function to create a simple collision shape with only a single given primitive,
183    /// with a given local-to-model transform.
184    ///
185    /// # Parameters
186    ///
187    /// - `strategy`: The collision strategy to use for this shape.
188    /// - `primitive`: The collision primitive.
189    /// - `transform`: Local-to-model transform of the primitive.
190    pub fn new_simple_offset(
191        strategy: CollisionStrategy,
192        mode: CollisionMode,
193        primitive: P,
194        transform: T,
195    ) -> Self {
196        Self::new_complex(
197            strategy,
198            mode,
199            vec![(primitive, transform)],
200            Default::default(),
201        )
202    }
203
204    /// Update the cached transformed bounding box in world space coordinates.
205    ///
206    /// If the end transform is given, that will always be used. If the collision mode of the shape
207    /// is `Continuous`, both the start and end transforms will be added to the transformed bounding
208    /// box. This will make broad phase detect collisions for the whole transformation path.
209    ///
210    /// ## Parameters
211    ///
212    /// - `start`: Current model-to-world transform of the shape at the start of the frame.
213    /// - `end`: Optional model-to-world transform of the shaped at the end of the frame.
214    pub fn update(&mut self, start: &T, end: Option<&T>) {
215        self.transformed_bound = match end {
216            None => self.base_bound.transform_volume(start),
217            Some(end_t) => {
218                let base = self.base_bound.transform_volume(end_t);
219                if self.mode == CollisionMode::Continuous {
220                    base.union(&self.base_bound.transform_volume(start))
221                } else {
222                    base
223                }
224            }
225        };
226    }
227
228    /// Return the current transformed bound for the shape
229    ///
230    pub fn bound(&self) -> &B {
231        &self.transformed_bound
232    }
233
234    /// Borrow the primitives of the shape
235    pub fn primitives(&self) -> &Vec<(P, T)> {
236        &self.primitives
237    }
238}
239
240impl<P, T, B, Y> HasBound for CollisionShape<P, T, B, Y>
241where
242    P: Primitive + ComputeBound<B>,
243    B: Bound<Point = P::Point> + Union<B, Output = B> + Clone,
244    T: Transform<P::Point>,
245    Y: Default,
246{
247    type Bound = B;
248
249    fn bound(&self) -> &Self::Bound {
250        &self.transformed_bound
251    }
252}
253
254fn get_bound<P, T, B>(primitives: &[(P, T)]) -> B
255where
256    P: Primitive + ComputeBound<B>,
257    B: Bound<Point = P::Point> + Union<B, Output = B>,
258    T: Transform<P::Point>,
259{
260    primitives
261        .iter()
262        .map(|&(ref p, ref t)| p.compute_bound().transform_volume(t))
263        .fold(B::empty(), |bound, b| bound.union(&b))
264}
265
266/// Collision data used for performing a full broad + narrow phase
267pub trait CollisionData<I, P, T, B, Y, D>
268where
269    P: Primitive,
270{
271    /// Get the list of data to perform broad phase on
272    fn get_broad_data(&self) -> Vec<D>;
273    /// Get shape
274    fn get_shape(&self, id: I) -> Option<&CollisionShape<P, T, B, Y>>;
275    /// Get pose
276    fn get_pose(&self, id: I) -> Option<&T>;
277    /// Get the dirty poses, used by tree broad phase
278    fn get_dirty_poses(&self) -> Vec<I> {
279        Vec::default()
280    }
281    /// Get the next pose if possible
282    fn get_next_pose(&self, id: I) -> Option<&T>;
283}
284
285/// Trait used to extract the lookup id used by `CollisionData`, given the output from a broad phase
286pub trait GetId<I> {
287    /// Get the id
288    fn id(&self) -> I;
289}
290
291impl<I, B> GetId<I> for TreeValueWrapped<I, B>
292where
293    B: Bound,
294    I: Copy + Debug + Hash + Eq,
295    <B::Point as EuclideanSpace>::Diff: Debug,
296{
297    fn id(&self) -> I {
298        self.value
299    }
300}
301
302/// Do basic collision detection (not using a DBVT)
303///
304/// ### Type parameters:
305///
306/// - `C`: Collision data
307/// - `I`: Id, returned by `GetId` on `D`, primary id for a collider
308/// - `P`: Primitive
309/// - `T`: Transform
310/// - `B`: Bounding volume
311/// - `Y`: Collider, see `Collider` for more information
312/// - `D`: Broad phase data
313pub fn basic_collide<C, I, P, T, B, Y, D>(
314    data: &C,
315    broad: &mut Box<BroadPhase<D>>,
316    narrow: &Option<Box<NarrowPhase<P, T, B, Y>>>,
317) -> Vec<ContactEvent<I, P::Point>>
318where
319    C: CollisionData<I, P, T, B, Y, D>,
320    P: Primitive,
321    <P::Point as EuclideanSpace>::Diff: Debug,
322    I: Copy + Debug,
323    D: HasBound<Bound = B> + GetId<I>,
324    B: Bound<Point = P::Point>,
325{
326    let potentials = broad_collide(data, broad);
327    if potentials.is_empty() {
328        return Vec::default();
329    }
330    match *narrow {
331        Some(ref narrow) => narrow_collide(data, narrow, &potentials),
332        None => potentials
333            .iter()
334            .map(|&(left, right)| {
335                ContactEvent::new_simple(CollisionStrategy::CollisionOnly, (left, right))
336            }).collect::<Vec<_>>(),
337    }
338}
339
340/// Do collision detection using a DBVT
341///
342/// ### Type parameters:
343///
344/// - `C`: Collision data
345/// - `I`: Id, returned by `GetId` on `D`, primary id for a collider
346/// - `P`: Primitive
347/// - `T`: Transform
348/// - `B`: Bounding volume
349/// - `Y`: Collider, see `Collider` for more information
350/// - `D`: `TreeValue` in DBVT
351pub fn tree_collide<C, I, P, T, B, Y, D>(
352    data: &C,
353    tree: &mut DynamicBoundingVolumeTree<D>,
354    broad: &mut Option<Box<BroadPhase<(usize, D)>>>,
355    narrow: &Option<Box<NarrowPhase<P, T, B, Y>>>,
356) -> Vec<ContactEvent<I, P::Point>>
357where
358    C: CollisionData<I, P, T, B, Y, D>,
359    P: Primitive,
360    <P::Point as EuclideanSpace>::Diff: Debug,
361    I: Copy + Debug + Hash + Eq,
362    D: HasBound<Bound = B> + GetId<I> + TreeValue<Bound = B>,
363    B: Bound<Point = P::Point>
364        + Clone
365        + SurfaceArea<Scalar = <P::Point as EuclideanSpace>::Scalar>
366        + Contains<B>
367        + Union<B, Output = B>
368        + Discrete<B>,
369{
370    use collision::algorithm::broad_phase::DbvtBroadPhase;
371    let potentials = match *broad {
372        Some(ref mut broad) => {
373            let p = broad.find_potentials(tree.values_mut());
374            tree.reindex_values();
375            p
376        }
377        None => {
378            let dirty_entities = data.get_dirty_poses().into_iter().collect::<HashSet<I>>();
379            let dirty = tree
380                .values()
381                .iter()
382                .map(|&(_, ref v)| dirty_entities.contains(&v.id()))
383                .collect::<Vec<_>>();
384            DbvtBroadPhase.find_collider_pairs(tree, &dirty[..])
385        }
386    };
387    let potentials = potentials
388        .iter()
389        .map(|&(ref l, ref r)| (tree.values()[*l].1.id(), tree.values()[*r].1.id()))
390        .collect::<Vec<_>>();
391    match *narrow {
392        Some(ref narrow) => narrow_collide(data, narrow, &potentials),
393        None => potentials
394            .iter()
395            .map(|&(left, right)| {
396                ContactEvent::new_simple(CollisionStrategy::CollisionOnly, (left, right))
397            }).collect::<Vec<_>>(),
398    }
399}
rhusics_core/collide/mod.rs

rhusics_core/collide/
mod.rs
