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

box2d_rust/contact/
mod.rs
