box2d_rust/contact/
mod.rs

1// Port of contact.h (data model) and contact.c (contact lifecycle + narrow
2// phase update). Split: lifecycle.rs holds the register table and contact
3// creation/destruction; update.rs holds the narrow-phase manifold update.
4//
5// Contacts and determinism
6// A deterministic simulation requires contacts to exist in the same order in
7// b2Island no matter the thread count. The order must reproduce from run to
8// run. This is necessary because the Gauss-Seidel constraint solver is order
9// dependent.
10//
11// Creation:
12// - Contacts are created using results from b2UpdateBroadPhasePairs
13// - These results are ordered according to the order of the broad-phase move
14//   array
15// - The move array is ordered according to the shape creation order using a
16//   bitset.
17// - The island/shape/body order is determined by creation order
18// - Logically contacts are only created for awake bodies, so they are
19//   immediately added to the awake contact array (serially)
20//
21// Island linking:
22// - The awake contact array is built from the body-contact graph for all awake
23//   bodies in awake islands.
24// - Awake contacts are solved in parallel and they generate contact state
25//   changes.
26// - These state changes may link islands together using union find.
27// - The state changes are ordered using a bit array that encompasses all
28//   contacts
29// - As long as contacts are created in deterministic order, island link order
30//   is deterministic.
31// - This keeps the order of contacts in islands deterministic
32//
33// SPDX-FileCopyrightText: 2023 Erin Catto
34// SPDX-License-Identifier: MIT
35
36use crate::collision::Manifold;
37use crate::core::NULL_INDEX;
38use crate::distance::SimplexCache;
39use crate::math_functions::{Rot, Transform, ROT_IDENTITY, TRANSFORM_IDENTITY};
40
41mod api;
42mod lifecycle;
43mod update;
44
45pub use api::*;
46pub use lifecycle::*;
47pub use update::*;
48
49// enum b2ContactFlags
50pub mod contact_flags {
51    /// Set when the solid shapes are touching.
52    pub const TOUCHING: u32 = 0x00000001;
53    /// Contact has a hit event
54    pub const HIT_EVENT: u32 = 0x00000002;
55    /// This contact wants contact events
56    pub const ENABLE_CONTACT_EVENTS: u32 = 0x00000004;
57    pub const RECYCLE: u32 = 0x00000008;
58
59    /// Set when the shapes are touching (sim flag)
60    pub const SIM_TOUCHING: u32 = 0x00010000;
61    /// This contact no longer has overlapping AABBs
62    pub const SIM_DISJOINT: u32 = 0x00020000;
63    /// This contact started touching
64    pub const SIM_STARTED_TOUCHING: u32 = 0x00040000;
65    /// This contact stopped touching
66    pub const SIM_STOPPED_TOUCHING: u32 = 0x00080000;
67    /// This contact has a hit event
68    pub const SIM_ENABLE_HIT_EVENT: u32 = 0x00100000;
69    /// This contact wants pre-solve events
70    pub const SIM_ENABLE_PRE_SOLVE_EVENTS: u32 = 0x00200000;
71    /// This contact has a cached relative transform
72    pub const SIM_RELATIVE_TRANSFORM_VALID: u32 = 0x00400000;
73}
74
75/// A contact edge is used to connect bodies and contacts together in a contact
76/// graph where each body is a node and each contact is an edge. A contact edge
77/// belongs to a doubly linked list maintained in each attached body. Each
78/// contact has two contact edges, one for each attached body. (b2ContactEdge)
79#[derive(Debug, Clone, Copy, PartialEq, Eq)]
80pub struct ContactEdge {
81    pub body_id: i32,
82    pub prev_key: i32,
83    pub next_key: i32,
84}
85
86impl Default for ContactEdge {
87    fn default() -> Self {
88        ContactEdge {
89            body_id: NULL_INDEX,
90            prev_key: NULL_INDEX,
91            next_key: NULL_INDEX,
92        }
93    }
94}
95
96/// Cold contact data. Used as a persistent handle and for persistent island
97/// connectivity. (b2Contact)
98#[derive(Debug, Clone, Copy, PartialEq, Eq)]
99pub struct Contact {
100    pub edges: [ContactEdge; 2],
101
102    /// A contact only belongs to an island if touching, otherwise NULL_INDEX.
103    pub island_id: i32,
104
105    /// Index into the island's contacts array for O(1) swap-removal.
106    /// NULL_INDEX when not in an island.
107    pub island_index: i32,
108
109    /// index of simulation set stored in World. NULL_INDEX when slot is free.
110    pub set_index: i32,
111
112    /// index into the constraint graph color array. NULL_INDEX for
113    /// non-touching or sleeping contacts, and when the slot is free.
114    pub color_index: i32,
115
116    /// contact index within set or graph color. NULL_INDEX when slot is free.
117    pub local_index: i32,
118
119    pub shape_id_a: i32,
120    pub shape_id_b: i32,
121    pub contact_id: i32,
122
123    /// contact_flags bits
124    pub flags: u32,
125
126    /// Monotonically advanced when a contact is allocated in this slot.
127    /// Used to check for invalid ContactId.
128    pub generation: u32,
129}
130
131impl Default for Contact {
132    fn default() -> Self {
133        Contact {
134            edges: [ContactEdge::default(); 2],
135            island_id: NULL_INDEX,
136            island_index: NULL_INDEX,
137            set_index: NULL_INDEX,
138            color_index: NULL_INDEX,
139            local_index: NULL_INDEX,
140            shape_id_a: NULL_INDEX,
141            shape_id_b: NULL_INDEX,
142            contact_id: NULL_INDEX,
143            flags: 0,
144            generation: 0,
145        }
146    }
147}
148
149/// Manages contact between two shapes. A contact exists for each overlapping
150/// AABB in the broad-phase (except if filtered), so a contact object may exist
151/// that has no contact points. (b2ContactSim)
152///
153/// The C `#if B2_ENABLE_VALIDATION` bodyIdA/bodyIdB fields are always present
154/// here; they only feed validation.
155#[derive(Debug, Clone, Copy, PartialEq)]
156pub struct ContactSim {
157    pub contact_id: i32,
158
159    /// Cache for contact recycling.
160    pub cached_rotation_a: Rot,
161    pub cached_rotation_b: Rot,
162    pub cached_relative_pose: Transform,
163
164    pub body_id_a: i32,
165    pub body_id_b: i32,
166
167    /// Transient body indices
168    pub body_sim_index_a: i32,
169    pub body_sim_index_b: i32,
170
171    pub shape_id_a: i32,
172    pub shape_id_b: i32,
173
174    pub inv_mass_a: f32,
175    pub inv_i_a: f32,
176
177    pub inv_mass_b: f32,
178    pub inv_i_b: f32,
179
180    pub manifold: Manifold,
181
182    /// Mixed friction and restitution
183    pub friction: f32,
184    pub restitution: f32,
185    pub rolling_resistance: f32,
186    pub tangent_speed: f32,
187
188    /// contact_flags bits (sim flags)
189    pub sim_flags: u32,
190
191    pub cache: SimplexCache,
192}
193
194impl Default for ContactSim {
195    fn default() -> Self {
196        ContactSim {
197            contact_id: NULL_INDEX,
198            cached_rotation_a: ROT_IDENTITY,
199            cached_rotation_b: ROT_IDENTITY,
200            cached_relative_pose: TRANSFORM_IDENTITY,
201            body_id_a: NULL_INDEX,
202            body_id_b: NULL_INDEX,
203            body_sim_index_a: NULL_INDEX,
204            body_sim_index_b: NULL_INDEX,
205            shape_id_a: NULL_INDEX,
206            shape_id_b: NULL_INDEX,
207            inv_mass_a: 0.0,
208            inv_i_a: 0.0,
209            inv_mass_b: 0.0,
210            inv_i_b: 0.0,
211            manifold: Manifold::default(),
212            friction: 0.0,
213            restitution: 0.0,
214            rolling_resistance: 0.0,
215            tangent_speed: 0.0,
216            sim_flags: 0,
217            cache: SimplexCache::default(),
218        }
219    }
220}
221
222#[cfg(test)]
223mod tests {
224    use super::*;
225    use crate::body::{create_body, get_body_full_id, get_body_transform};
226    use crate::broad_phase::update_broad_phase_pairs;
227    use crate::collision::ShapeType;
228    use crate::geometry::make_box;
229    use crate::math_functions::VEC2_ZERO;
230    use crate::shape::create_polygon_shape;
231    use crate::solver_set::AWAKE_SET;
232    use crate::table::shape_pair_key;
233    use crate::types::{default_body_def, default_shape_def, default_world_def, BodyType};
234    use crate::world::World;
235
236    #[test]
237    fn contact_register_pairs() {
238        use ShapeType::*;
239        // All 12 registered pairs collide, in either order.
240        for (a, b) in [
241            (Circle, Circle),
242            (Capsule, Circle),
243            (Capsule, Capsule),
244            (Polygon, Circle),
245            (Polygon, Capsule),
246            (Polygon, Polygon),
247            (Segment, Circle),
248            (Segment, Capsule),
249            (Segment, Polygon),
250            (ChainSegment, Circle),
251            (ChainSegment, Capsule),
252            (ChainSegment, Polygon),
253        ] {
254            assert!(can_collide(a, b), "{a:?} vs {b:?}");
255            assert!(can_collide(b, a), "{b:?} vs {a:?}");
256        }
257
258        // No segment vs segment style collisions.
259        assert!(!can_collide(Segment, Segment));
260        assert!(!can_collide(Segment, ChainSegment));
261        assert!(!can_collide(ChainSegment, ChainSegment));
262    }
263
264    // Slice-4 acceptance test: two dynamic bodies with overlapping box shapes.
265    // update_broad_phase_pairs must create exactly one contact (dedup: both
266    // proxies are in the move array) and update_contact must report touching
267    // with a two point manifold.
268    #[test]
269    fn overlapping_boxes_create_touching_contact() {
270        let mut world = World::new(&default_world_def());
271
272        let mut body_def = default_body_def();
273        body_def.type_ = BodyType::Dynamic;
274        let body_a = create_body(&mut world, &body_def);
275        let body_b = create_body(&mut world, &body_def);
276        let body_index_a = get_body_full_id(&world, body_a);
277        let body_index_b = get_body_full_id(&world, body_b);
278
279        // Identical overlapping boxes at the origin.
280        let box_poly = make_box(0.5, 0.5);
281        let shape_def = default_shape_def();
282        let sa = create_polygon_shape(&mut world, body_a, &shape_def, &box_poly);
283        let sb = create_polygon_shape(&mut world, body_b, &shape_def, &box_poly);
284        let shape_index_a = sa.index1 - 1;
285        let shape_index_b = sb.index1 - 1;
286
287        assert_eq!(world.broad_phase.move_array.len(), 2);
288
289        // Broad-phase pair update creates exactly one non-touching contact in
290        // the awake set and consumes the move buffer.
291        update_broad_phase_pairs(&mut world);
292        assert_eq!(world.contact_id_pool.id_count(), 1);
293        assert_eq!(world.solver_sets[AWAKE_SET as usize].contact_sims.len(), 1);
294        assert!(world.broad_phase.move_array.is_empty());
295        assert!(world
296            .broad_phase
297            .pair_set
298            .contains_key(shape_pair_key(shape_index_a, shape_index_b)));
299
300        let contact_id = world.solver_sets[AWAKE_SET as usize].contact_sims[0].contact_id;
301        {
302            let contact = &world.contacts[contact_id as usize];
303            assert_eq!(contact.set_index, AWAKE_SET);
304            assert_eq!(contact.color_index, NULL_INDEX);
305            assert_eq!(contact.flags & contact_flags::TOUCHING, 0);
306            assert_eq!(contact.edges[0].body_id, body_index_a);
307            assert_eq!(contact.edges[1].body_id, body_index_b);
308        }
309        // Contact edges are linked into both bodies.
310        assert_eq!(world.bodies[body_index_a as usize].contact_count, 1);
311        assert_eq!(world.bodies[body_index_b as usize].contact_count, 1);
312        assert_eq!(
313            world.bodies[body_index_a as usize].head_contact_key,
314            contact_id << 1
315        );
316        assert_eq!(
317            world.bodies[body_index_b as usize].head_contact_key,
318            (contact_id << 1) | 1
319        );
320
321        // A second pair update is a no-op (move buffer empty, pair exists).
322        update_broad_phase_pairs(&mut world);
323        assert_eq!(world.contact_id_pool.id_count(), 1);
324
325        // Narrow phase: the manifold has two points and the contact touches.
326        let (shape_id_a, shape_id_b) = {
327            let contact = &world.contacts[contact_id as usize];
328            (contact.shape_id_a, contact.shape_id_b)
329        };
330        let ctx = ContactUpdateContext::new(&world);
331        let transform_a = get_body_transform(&world, body_index_a);
332        let transform_b = get_body_transform(&world, body_index_b);
333        let shape_a = world.shapes[shape_id_a as usize].clone();
334        let shape_b = world.shapes[shape_id_b as usize].clone();
335
336        let mut contact_sim = world.solver_sets[AWAKE_SET as usize].contact_sims[0];
337        let touching = update_contact(
338            &ctx,
339            &mut contact_sim,
340            &shape_a,
341            transform_a,
342            VEC2_ZERO,
343            &shape_b,
344            transform_b,
345            VEC2_ZERO,
346        );
347        assert!(touching);
348        assert_eq!(contact_sim.manifold.point_count, 2);
349        assert!(contact_sim.sim_flags & contact_flags::SIM_TOUCHING != 0);
350        world.solver_sets[AWAKE_SET as usize].contact_sims[0] = contact_sim;
351
352        // Destroying the contact unlinks the bodies and frees the pair.
353        destroy_contact(&mut world, contact_id, false);
354        assert_eq!(world.contact_id_pool.id_count(), 0);
355        assert!(world.solver_sets[AWAKE_SET as usize]
356            .contact_sims
357            .is_empty());
358        assert!(!world
359            .broad_phase
360            .pair_set
361            .contains_key(shape_pair_key(shape_index_a, shape_index_b)));
362        assert_eq!(world.bodies[body_index_a as usize].contact_count, 0);
363        assert_eq!(world.bodies[body_index_b as usize].contact_count, 0);
364        assert_eq!(
365            world.bodies[body_index_a as usize].head_contact_key,
366            NULL_INDEX
367        );
368
369        world.validate_solver_sets();
370    }
371}
box2d_rust/contact/mod.rs

box2d_rust/contact/
mod.rs
