From 754a48b7ff6d8c58b1ee08651e60112900b60455 Mon Sep 17 00:00:00 2001 From: Sébastien Crozet Date: Tue, 25 Aug 2020 22:10:25 +0200 Subject: First public release of Rapier. --- src/counters/ccd_counters.rs | 49 + src/counters/collision_detection_counters.rs | 32 + src/counters/mod.rs | 225 ++++ src/counters/solver_counters.rs | 67 + src/counters/stages_counters.rs | 48 + src/counters/timer.rs | 53 + src/data/arena.rs | 1159 +++++++++++++++++ src/data/graph.rs | 830 ++++++++++++ src/data/mod.rs | 4 + src/dynamics/integration_parameters.rs | 207 +++ src/dynamics/joint/ball_joint.rs | 34 + src/dynamics/joint/fixed_joint.rs | 33 + src/dynamics/joint/joint.rs | 112 ++ src/dynamics/joint/joint_set.rs | 218 ++++ src/dynamics/joint/mod.rs | 16 + src/dynamics/joint/prismatic_joint.rs | 193 +++ src/dynamics/joint/revolute_joint.rs | 46 + src/dynamics/mass_properties.rs | 206 +++ src/dynamics/mass_properties_ball.rs | 30 + src/dynamics/mass_properties_capsule.rs | 60 + src/dynamics/mass_properties_cuboid.rs | 33 + src/dynamics/mass_properties_polygon.rs | 144 +++ src/dynamics/mod.rs | 30 + src/dynamics/rigid_body.rs | 441 +++++++ src/dynamics/rigid_body_set.rs | 518 ++++++++ src/dynamics/solver/categorization.rs | 70 + src/dynamics/solver/delta_vel.rs | 18 + src/dynamics/solver/interaction_groups.rs | 434 +++++++ src/dynamics/solver/island_solver.rs | 73 ++ .../joint_constraint/ball_position_constraint.rs | 165 +++ .../ball_position_constraint_wide.rs | 199 +++ .../joint_constraint/ball_velocity_constraint.rs | 238 ++++ .../ball_velocity_constraint_wide.rs | 329 +++++ .../joint_constraint/fixed_position_constraint.rs | 139 ++ .../joint_constraint/fixed_velocity_constraint.rs | 370 ++++++ .../fixed_velocity_constraint_wide.rs | 472 +++++++ .../solver/joint_constraint/joint_constraint.rs | 340 +++++ .../joint_constraint/joint_position_constraint.rs | 169 +++ src/dynamics/solver/joint_constraint/mod.rs | 65 + .../prismatic_position_constraint.rs | 170 +++ .../prismatic_velocity_constraint.rs | 558 ++++++++ .../prismatic_velocity_constraint_wide.rs | 687 ++++++++++ .../revolute_position_constraint.rs | 142 +++ .../revolute_velocity_constraint.rs | 294 +++++ .../revolute_velocity_constraint_wide.rs | 397 ++++++ src/dynamics/solver/mod.rs | 56 + src/dynamics/solver/parallel_island_solver.rs | 259 ++++ src/dynamics/solver/parallel_position_solver.rs | 582 +++++++++ src/dynamics/solver/parallel_velocity_solver.rs | 485 +++++++ src/dynamics/solver/position_constraint.rs | 246 ++++ src/dynamics/solver/position_constraint_wide.rs | 217 ++++ src/dynamics/solver/position_ground_constraint.rs | 189 +++ .../solver/position_ground_constraint_wide.rs | 199 +++ src/dynamics/solver/position_solver.rs | 451 +++++++ src/dynamics/solver/velocity_constraint.rs | 401 ++++++ src/dynamics/solver/velocity_constraint_wide.rs | 344 +++++ src/dynamics/solver/velocity_ground_constraint.rs | 300 +++++ .../solver/velocity_ground_constraint_wide.rs | 300 +++++ src/dynamics/solver/velocity_solver.rs | 405 ++++++ src/geometry/ball.rs | 16 + src/geometry/broad_phase.rs | 255 ++++ src/geometry/broad_phase_multi_sap.rs | 645 ++++++++++ src/geometry/capsule.rs | 168 +++ src/geometry/collider.rs | 373 ++++++ src/geometry/collider_set.rs | 139 ++ src/geometry/contact.rs | 485 +++++++ .../ball_ball_contact_generator.rs | 98 ++ .../ball_convex_contact_generator.rs | 85 ++ .../ball_polygon_contact_generator.rs | 0 .../capsule_capsule_contact_generator.rs | 200 +++ .../contact_generator/contact_dispatcher.rs | 127 ++ .../contact_generator/contact_generator.rs | 222 ++++ .../cuboid_capsule_contact_generator.rs | 188 +++ .../cuboid_cuboid_contact_generator.rs | 155 +++ .../cuboid_polygon_contact_generator.rs | 0 .../cuboid_triangle_contact_generator.rs | 171 +++ .../heightfield_shape_contact_generator.rs | 189 +++ src/geometry/contact_generator/mod.rs | 71 ++ .../polygon_polygon_contact_generator.rs | 298 +++++ .../trimesh_shape_contact_generator.rs | 194 +++ .../voxels_shape_contact_generator.rs | 0 src/geometry/cuboid.rs | 234 ++++ src/geometry/cuboid_feature2d.rs | 128 ++ src/geometry/cuboid_feature3d.rs | 516 ++++++++ src/geometry/interaction_graph.rs | 259 ++++ src/geometry/mod.rs | 80 ++ src/geometry/narrow_phase.rs | 483 +++++++ src/geometry/polygon.rs | 76 ++ src/geometry/polygon_intersection.rs | 263 ++++ src/geometry/polyhedron_feature3d.rs | 284 +++++ src/geometry/proximity.rs | 31 + .../ball_ball_proximity_detector.rs | 68 + .../ball_convex_proximity_detector.rs | 53 + .../ball_polygon_proximity_detector.rs | 0 .../cuboid_cuboid_proximity_detector.rs | 79 ++ .../cuboid_polygon_proximity_detector.rs | 0 .../cuboid_triangle_proximity_detector.rs | 88 ++ src/geometry/proximity_detector/mod.rs | 30 + .../polygon_polygon_proximity_detector.rs | 54 + .../proximity_detector/proximity_detector.rs | 212 ++++ .../proximity_detector/proximity_dispatcher.rs | 136 ++ .../trimesh_shape_proximity_detector.rs | 133 ++ .../voxels_shape_proximity_detector.rs | 0 src/geometry/sat.rs | 294 +++++ src/geometry/triangle.rs | 9 + src/geometry/trimesh.rs | 122 ++ src/geometry/waabb.rs | 116 ++ src/geometry/z_order.rs | 70 + src/lib.rs | 255 ++++ src/pipeline/collision_pipeline.rs | 111 ++ src/pipeline/event_handler.rs | 51 + src/pipeline/mod.rs | 9 + src/pipeline/physics_pipeline.rs | 332 +++++ src/utils.rs | 1333 ++++++++++++++++++++ 114 files changed, 24539 insertions(+) create mode 100644 src/counters/ccd_counters.rs create mode 100644 src/counters/collision_detection_counters.rs create mode 100644 src/counters/mod.rs create mode 100644 src/counters/solver_counters.rs create mode 100644 src/counters/stages_counters.rs create mode 100644 src/counters/timer.rs create mode 100644 src/data/arena.rs create mode 100644 src/data/graph.rs create mode 100644 src/data/mod.rs create mode 100644 src/dynamics/integration_parameters.rs create mode 100644 src/dynamics/joint/ball_joint.rs create mode 100644 src/dynamics/joint/fixed_joint.rs create mode 100644 src/dynamics/joint/joint.rs create mode 100644 src/dynamics/joint/joint_set.rs create mode 100644 src/dynamics/joint/mod.rs create mode 100644 src/dynamics/joint/prismatic_joint.rs create mode 100644 src/dynamics/joint/revolute_joint.rs create mode 100644 src/dynamics/mass_properties.rs create mode 100644 src/dynamics/mass_properties_ball.rs create mode 100644 src/dynamics/mass_properties_capsule.rs create mode 100644 src/dynamics/mass_properties_cuboid.rs create mode 100644 src/dynamics/mass_properties_polygon.rs create mode 100644 src/dynamics/mod.rs create mode 100644 src/dynamics/rigid_body.rs create mode 100644 src/dynamics/rigid_body_set.rs create mode 100644 src/dynamics/solver/categorization.rs create mode 100644 src/dynamics/solver/delta_vel.rs create mode 100644 src/dynamics/solver/interaction_groups.rs create mode 100644 src/dynamics/solver/island_solver.rs create mode 100644 src/dynamics/solver/joint_constraint/ball_position_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/ball_position_constraint_wide.rs create mode 100644 src/dynamics/solver/joint_constraint/ball_velocity_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/ball_velocity_constraint_wide.rs create mode 100644 src/dynamics/solver/joint_constraint/fixed_position_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/fixed_velocity_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/fixed_velocity_constraint_wide.rs create mode 100644 src/dynamics/solver/joint_constraint/joint_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/joint_position_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/mod.rs create mode 100644 src/dynamics/solver/joint_constraint/prismatic_position_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/prismatic_velocity_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/prismatic_velocity_constraint_wide.rs create mode 100644 src/dynamics/solver/joint_constraint/revolute_position_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/revolute_velocity_constraint.rs create mode 100644 src/dynamics/solver/joint_constraint/revolute_velocity_constraint_wide.rs create mode 100644 src/dynamics/solver/mod.rs create mode 100644 src/dynamics/solver/parallel_island_solver.rs create mode 100644 src/dynamics/solver/parallel_position_solver.rs create mode 100644 src/dynamics/solver/parallel_velocity_solver.rs create mode 100644 src/dynamics/solver/position_constraint.rs create mode 100644 src/dynamics/solver/position_constraint_wide.rs create mode 100644 src/dynamics/solver/position_ground_constraint.rs create mode 100644 src/dynamics/solver/position_ground_constraint_wide.rs create mode 100644 src/dynamics/solver/position_solver.rs create mode 100644 src/dynamics/solver/velocity_constraint.rs create mode 100644 src/dynamics/solver/velocity_constraint_wide.rs create mode 100644 src/dynamics/solver/velocity_ground_constraint.rs create mode 100644 src/dynamics/solver/velocity_ground_constraint_wide.rs create mode 100644 src/dynamics/solver/velocity_solver.rs create mode 100644 src/geometry/ball.rs create mode 100644 src/geometry/broad_phase.rs create mode 100644 src/geometry/broad_phase_multi_sap.rs create mode 100644 src/geometry/capsule.rs create mode 100644 src/geometry/collider.rs create mode 100644 src/geometry/collider_set.rs create mode 100644 src/geometry/contact.rs create mode 100644 src/geometry/contact_generator/ball_ball_contact_generator.rs create mode 100644 src/geometry/contact_generator/ball_convex_contact_generator.rs create mode 100644 src/geometry/contact_generator/ball_polygon_contact_generator.rs create mode 100644 src/geometry/contact_generator/capsule_capsule_contact_generator.rs create mode 100644 src/geometry/contact_generator/contact_dispatcher.rs create mode 100644 src/geometry/contact_generator/contact_generator.rs create mode 100644 src/geometry/contact_generator/cuboid_capsule_contact_generator.rs create mode 100644 src/geometry/contact_generator/cuboid_cuboid_contact_generator.rs create mode 100644 src/geometry/contact_generator/cuboid_polygon_contact_generator.rs create mode 100644 src/geometry/contact_generator/cuboid_triangle_contact_generator.rs create mode 100644 src/geometry/contact_generator/heightfield_shape_contact_generator.rs create mode 100644 src/geometry/contact_generator/mod.rs create mode 100644 src/geometry/contact_generator/polygon_polygon_contact_generator.rs create mode 100644 src/geometry/contact_generator/trimesh_shape_contact_generator.rs create mode 100644 src/geometry/contact_generator/voxels_shape_contact_generator.rs create mode 100644 src/geometry/cuboid.rs create mode 100644 src/geometry/cuboid_feature2d.rs create mode 100644 src/geometry/cuboid_feature3d.rs create mode 100644 src/geometry/interaction_graph.rs create mode 100644 src/geometry/mod.rs create mode 100644 src/geometry/narrow_phase.rs create mode 100644 src/geometry/polygon.rs create mode 100644 src/geometry/polygon_intersection.rs create mode 100644 src/geometry/polyhedron_feature3d.rs create mode 100644 src/geometry/proximity.rs create mode 100644 src/geometry/proximity_detector/ball_ball_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/ball_convex_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/ball_polygon_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/cuboid_cuboid_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/cuboid_polygon_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/cuboid_triangle_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/mod.rs create mode 100644 src/geometry/proximity_detector/polygon_polygon_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/proximity_detector.rs create mode 100644 src/geometry/proximity_detector/proximity_dispatcher.rs create mode 100644 src/geometry/proximity_detector/trimesh_shape_proximity_detector.rs create mode 100644 src/geometry/proximity_detector/voxels_shape_proximity_detector.rs create mode 100644 src/geometry/sat.rs create mode 100644 src/geometry/triangle.rs create mode 100644 src/geometry/trimesh.rs create mode 100644 src/geometry/waabb.rs create mode 100644 src/geometry/z_order.rs create mode 100644 src/lib.rs create mode 100644 src/pipeline/collision_pipeline.rs create mode 100644 src/pipeline/event_handler.rs create mode 100644 src/pipeline/mod.rs create mode 100644 src/pipeline/physics_pipeline.rs create mode 100644 src/utils.rs (limited to 'src') diff --git a/src/counters/ccd_counters.rs b/src/counters/ccd_counters.rs new file mode 100644 index 0000000..682adfc --- /dev/null +++ b/src/counters/ccd_counters.rs @@ -0,0 +1,49 @@ +use crate::counters::Timer; +use std::fmt::{Display, Formatter, Result}; + +/// Performance counters related to continuous collision detection (CCD). +#[derive(Default, Clone, Copy)] +pub struct CCDCounters { + /// The number of substeps actually performed by the CCD resolution. + pub num_substeps: usize, + /// The total time spent for TOI computation in the CCD resolution. + pub toi_computation_time: Timer, + /// The total time spent for force computation and integration in the CCD resolution. + pub solver_time: Timer, + /// The total time spent by the broad-phase in the CCD resolution. + pub broad_phase_time: Timer, + /// The total time spent by the narrow-phase in the CCD resolution. + pub narrow_phase_time: Timer, +} + +impl CCDCounters { + /// Creates a new counter initialized to zero. + pub fn new() -> Self { + CCDCounters { + num_substeps: 0, + toi_computation_time: Timer::new(), + solver_time: Timer::new(), + broad_phase_time: Timer::new(), + narrow_phase_time: Timer::new(), + } + } + + /// Resets this counter to 0. + pub fn reset(&mut self) { + self.num_substeps = 0; + self.toi_computation_time.reset(); + self.solver_time.reset(); + self.broad_phase_time.reset(); + self.narrow_phase_time.reset(); + } +} + +impl Display for CCDCounters { + fn fmt(&self, f: &mut Formatter) -> Result { + writeln!(f, "Number of substeps: {}", self.num_substeps)?; + writeln!(f, "TOI computation time: {}", self.toi_computation_time)?; + writeln!(f, "Constraints solver time: {}", self.solver_time)?; + writeln!(f, "Broad-phase time: {}", self.broad_phase_time)?; + writeln!(f, "Narrow-phase time: {}", self.narrow_phase_time) + } +} diff --git a/src/counters/collision_detection_counters.rs b/src/counters/collision_detection_counters.rs new file mode 100644 index 0000000..d164452 --- /dev/null +++ b/src/counters/collision_detection_counters.rs @@ -0,0 +1,32 @@ +use crate::counters::Timer; +use std::fmt::{Display, Formatter, Result}; + +/// Performance counters related to collision detection. +#[derive(Default, Clone, Copy)] +pub struct CollisionDetectionCounters { + /// Number of contact pairs detected. + pub ncontact_pairs: usize, + /// Time spent for the broad-phase of the collision detection. + pub broad_phase_time: Timer, + /// Time spent for the narrow-phase of the collision detection. + pub narrow_phase_time: Timer, +} + +impl CollisionDetectionCounters { + /// Creates a new counter initialized to zero. + pub fn new() -> Self { + CollisionDetectionCounters { + ncontact_pairs: 0, + broad_phase_time: Timer::new(), + narrow_phase_time: Timer::new(), + } + } +} + +impl Display for CollisionDetectionCounters { + fn fmt(&self, f: &mut Formatter) -> Result { + writeln!(f, "Number of contact pairs: {}", self.ncontact_pairs)?; + writeln!(f, "Broad-phase time: {}", self.broad_phase_time)?; + writeln!(f, "Narrow-phase time: {}", self.narrow_phase_time) + } +} diff --git a/src/counters/mod.rs b/src/counters/mod.rs new file mode 100644 index 0000000..c172350 --- /dev/null +++ b/src/counters/mod.rs @@ -0,0 +1,225 @@ +//! Counters for benchmarking various parts of the physics engine. + +use std::fmt::{Display, Formatter, Result}; + +pub use self::ccd_counters::CCDCounters; +pub use self::collision_detection_counters::CollisionDetectionCounters; +pub use self::solver_counters::SolverCounters; +pub use self::stages_counters::StagesCounters; +pub use self::timer::Timer; + +mod ccd_counters; +mod collision_detection_counters; +mod solver_counters; +mod stages_counters; +mod timer; + +/// Aggregation of all the performances counters tracked by nphysics. +#[derive(Clone, Copy)] +pub struct Counters { + /// Whether thi counter is enabled or not. + pub enabled: bool, + /// Timer for a whole timestep. + pub step_time: Timer, + /// Timer used for debugging. + pub custom: Timer, + /// Counters of every satge of one time step. + pub stages: StagesCounters, + /// Counters of the collision-detection stage. + pub cd: CollisionDetectionCounters, + /// Counters of the constraints resolution and force computation stage. + pub solver: SolverCounters, + /// Counters for the CCD resolution stage. + pub ccd: CCDCounters, +} + +impl Counters { + /// Create a new set of counters initialized to wero. + pub fn new(enabled: bool) -> Self { + Counters { + enabled, + step_time: Timer::new(), + custom: Timer::new(), + stages: StagesCounters::new(), + cd: CollisionDetectionCounters::new(), + solver: SolverCounters::new(), + ccd: CCDCounters::new(), + } + } + + /// Enable all the counters. + pub fn enable(&mut self) { + self.enabled = true; + } + + /// Return `true` if the counters are enabled. + pub fn enabled(&self) -> bool { + self.enabled + } + + /// Disable all the counters. + pub fn disable(&mut self) { + self.enabled = false; + } + + /// Notify that the time-step has started. + pub fn step_started(&mut self) { + if self.enabled { + self.step_time.start(); + } + } + + /// Notfy that the time-step has finished. + pub fn step_completed(&mut self) { + if self.enabled { + self.step_time.pause(); + } + } + + /// Total time spent for one of the physics engine. + pub fn step_time(&self) -> f64 { + self.step_time.time() + } + + /// Notify that the custom operation has started. + pub fn custom_started(&mut self) { + if self.enabled { + self.custom.start(); + } + } + + /// Notfy that the custom operation has finished. + pub fn custom_completed(&mut self) { + if self.enabled { + self.custom.pause(); + } + } + + /// Total time of a custom event. + pub fn custom_time(&self) -> f64 { + self.custom.time() + } + + /// Set the number of constraints generated. + pub fn set_nconstraints(&mut self, n: usize) { + self.solver.nconstraints = n; + } + + /// Set the number of contacts generated. + pub fn set_ncontacts(&mut self, n: usize) { + self.solver.ncontacts = n; + } + + /// Set the number of contact pairs generated. + pub fn set_ncontact_pairs(&mut self, n: usize) { + self.cd.ncontact_pairs = n; + } +} + +macro_rules! measure_method { + ($started:ident, $stopped:ident, $time:ident, $info:ident. $timer:ident) => { + impl Counters { + /// Start this timer. + pub fn $started(&mut self) { + if self.enabled { + self.$info.$timer.start() + } + } + + /// Stop this timer. + pub fn $stopped(&mut self) { + if self.enabled { + self.$info.$timer.pause() + } + } + + /// Gets the time elapsed for this timer. + pub fn $time(&self) -> f64 { + if self.enabled { + self.$info.$timer.time() + } else { + 0.0 + } + } + } + }; +} + +measure_method!( + update_started, + update_completed, + update_time, + stages.update_time +); +measure_method!( + collision_detection_started, + collision_detection_completed, + collision_detection_time, + stages.collision_detection_time +); +measure_method!( + island_construction_started, + island_construction_completed, + island_construction_time, + stages.island_construction_time +); +measure_method!( + solver_started, + solver_completed, + solver_time, + stages.solver_time +); +measure_method!(ccd_started, ccd_completed, ccd_time, stages.ccd_time); + +measure_method!( + assembly_started, + assembly_completed, + assembly_time, + solver.velocity_assembly_time +); +measure_method!( + velocity_resolution_started, + velocity_resolution_completed, + velocity_resolution_time, + solver.velocity_resolution_time +); +measure_method!( + velocity_update_started, + velocity_update_completed, + velocity_update_time, + solver.velocity_update_time +); +measure_method!( + position_resolution_started, + position_resolution_completed, + position_resolution_time, + solver.position_resolution_time +); +measure_method!( + broad_phase_started, + broad_phase_completed, + broad_phase_time, + cd.broad_phase_time +); +measure_method!( + narrow_phase_started, + narrow_phase_completed, + narrow_phase_time, + cd.narrow_phase_time +); + +impl Display for Counters { + fn fmt(&self, f: &mut Formatter) -> Result { + writeln!(f, "Total timestep time: {}", self.step_time)?; + self.stages.fmt(f)?; + self.cd.fmt(f)?; + self.solver.fmt(f)?; + writeln!(f, "Custom timer: {}", self.custom) + } +} + +impl Default for Counters { + fn default() -> Self { + Self::new(false) + } +} diff --git a/src/counters/solver_counters.rs b/src/counters/solver_counters.rs new file mode 100644 index 0000000..babcf41 --- /dev/null +++ b/src/counters/solver_counters.rs @@ -0,0 +1,67 @@ +use crate::counters::Timer; +use std::fmt::{Display, Formatter, Result}; + +/// Performance counters related to constraints resolution. +#[derive(Default, Clone, Copy)] +pub struct SolverCounters { + /// Number of constraints generated. + pub nconstraints: usize, + /// Number of contacts found. + pub ncontacts: usize, + /// Time spent for the resolution of the constraints (force computation). + pub velocity_resolution_time: Timer, + /// Time spent for the assembly of all the velocity constraints. + pub velocity_assembly_time: Timer, + /// Time spent for the update of the velocity of the bodies. + pub velocity_update_time: Timer, + /// Time spent for the assembly of all the position constraints. + pub position_assembly_time: Timer, + /// Time spent for the update of the position of the bodies. + pub position_resolution_time: Timer, +} + +impl SolverCounters { + /// Creates a new counter initialized to zero. + pub fn new() -> Self { + SolverCounters { + nconstraints: 0, + ncontacts: 0, + velocity_assembly_time: Timer::new(), + velocity_resolution_time: Timer::new(), + velocity_update_time: Timer::new(), + position_assembly_time: Timer::new(), + position_resolution_time: Timer::new(), + } + } + + /// Reset all the counters to zero. + pub fn reset(&mut self) { + self.nconstraints = 0; + self.ncontacts = 0; + self.velocity_resolution_time.reset(); + self.velocity_assembly_time.reset(); + self.velocity_update_time.reset(); + self.position_assembly_time.reset(); + self.position_resolution_time.reset(); + } +} + +impl Display for SolverCounters { + fn fmt(&self, f: &mut Formatter) -> Result { + writeln!(f, "Number of contacts: {}", self.ncontacts)?; + writeln!(f, "Number of constraints: {}", self.nconstraints)?; + writeln!(f, "Velocity assembly time: {}", self.velocity_assembly_time)?; + writeln!( + f, + "Velocity resolution time: {}", + self.velocity_resolution_time + )?; + writeln!(f, "Velocity update time: {}", self.velocity_update_time)?; + writeln!(f, "Position assembly time: {}", self.position_assembly_time)?; + writeln!( + f, + "Position resolution time: {}", + self.position_resolution_time + ) + } +} diff --git a/src/counters/stages_counters.rs b/src/counters/stages_counters.rs new file mode 100644 index 0000000..856b759 --- /dev/null +++ b/src/counters/stages_counters.rs @@ -0,0 +1,48 @@ +use crate::counters::Timer; +use std::fmt::{Display, Formatter, Result}; + +/// Performance counters related to each stage of the time step. +#[derive(Default, Clone, Copy)] +pub struct StagesCounters { + /// Time spent for updating the kinematic and dynamics of every body. + pub update_time: Timer, + /// Total time spent for the collision detection (including both broad- and narrow- phases). + pub collision_detection_time: Timer, + /// Time spent for the computation of collision island and body activation/deactivation (sleeping). + pub island_construction_time: Timer, + /// Total time spent for the constraints resolution and position update.t + pub solver_time: Timer, + /// Total time spent for CCD and CCD resolution. + pub ccd_time: Timer, +} + +impl StagesCounters { + /// Create a new counter intialized to zero. + pub fn new() -> Self { + StagesCounters { + update_time: Timer::new(), + collision_detection_time: Timer::new(), + island_construction_time: Timer::new(), + solver_time: Timer::new(), + ccd_time: Timer::new(), + } + } +} + +impl Display for StagesCounters { + fn fmt(&self, f: &mut Formatter) -> Result { + writeln!(f, "Update time: {}", self.update_time)?; + writeln!( + f, + "Collision detection time: {}", + self.collision_detection_time + )?; + writeln!( + f, + "Island construction time: {}", + self.island_construction_time + )?; + writeln!(f, "Solver time: {}", self.solver_time)?; + writeln!(f, "CCD time: {}", self.ccd_time) + } +} diff --git a/src/counters/timer.rs b/src/counters/timer.rs new file mode 100644 index 0000000..fd25063 --- /dev/null +++ b/src/counters/timer.rs @@ -0,0 +1,53 @@ +use std::fmt::{Display, Error, Formatter}; + +/// A timer. +#[derive(Copy, Clone, Debug, Default)] +pub struct Timer { + time: f64, + start: Option, +} + +impl Timer { + /// Creates a new timer initialized to zero and not started. + pub fn new() -> Self { + Timer { + time: 0.0, + start: None, + } + } + + /// Resets the timer to 0. + pub fn reset(&mut self) { + self.time = 0.0 + } + + /// Start the timer. + pub fn start(&mut self) { + self.time = 0.0; + self.start = Some(instant::now()); + } + + /// Pause the timer. + pub fn pause(&mut self) { + if let Some(start) = self.start { + self.time += instant::now() - start; + } + self.start = None; + } + + /// Resume the timer. + pub fn resume(&mut self) { + self.start = Some(instant::now()); + } + + /// The measured time between the last `.start()` and `.pause()` calls. + pub fn time(&self) -> f64 { + self.time + } +} + +impl Display for Timer { + fn fmt(&self, f: &mut Formatter) -> Result<(), Error> { + write!(f, "{}s", self.time) + } +} diff --git a/src/data/arena.rs b/src/data/arena.rs new file mode 100644 index 0000000..fcec017 --- /dev/null +++ b/src/data/arena.rs @@ -0,0 +1,1159 @@ +//! Arena adapted from the generational-arena crate. +//! +//! See https://github.com/fitzgen/generational-arena/blob/master/src/lib.rs. +//! This has been modified to have a fully deterministic deserialization (including for the order of +//! Index attribution after a deserialization of the arena. +use std::cmp; +use std::iter::{self, Extend, FromIterator, FusedIterator}; +use std::mem; +use std::ops; +use std::slice; +use std::vec; + +/// The `Arena` allows inserting and removing elements that are referred to by +/// `Index`. +/// +/// [See the module-level documentation for example usage and motivation.](./index.html) +#[derive(Clone, Debug)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct Arena { + items: Vec>, + generation: u64, + free_list_head: Option, + len: usize, +} + +#[derive(Clone, Debug)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +enum Entry { + Free { next_free: Option }, + Occupied { generation: u64, value: T }, +} + +/// An index (and generation) into an `Arena`. +/// +/// To get an `Index`, insert an element into an `Arena`, and the `Index` for +/// that element will be returned. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// let idx = arena.insert(123); +/// assert_eq!(arena[idx], 123); +/// ``` +#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct Index { + index: usize, + generation: u64, +} + +impl Index { + /// Create a new `Index` from its raw parts. + /// + /// The parts must have been returned from an earlier call to + /// `into_raw_parts`. + /// + /// Providing arbitrary values will lead to malformed indices and ultimately + /// panics. + pub fn from_raw_parts(a: usize, b: u64) -> Index { + Index { + index: a, + generation: b, + } + } + + /// Convert this `Index` into its raw parts. + /// + /// This niche method is useful for converting an `Index` into another + /// identifier type. Usually, you should prefer a newtype wrapper around + /// `Index` like `pub struct MyIdentifier(Index);`. However, for external + /// types whose definition you can't customize, but which you can construct + /// instances of, this method can be useful. + pub fn into_raw_parts(self) -> (usize, u64) { + (self.index, self.generation) + } +} + +const DEFAULT_CAPACITY: usize = 4; + +impl Default for Arena { + fn default() -> Arena { + Arena::new() + } +} + +impl Arena { + /// Constructs a new, empty `Arena`. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::::new(); + /// # let _ = arena; + /// ``` + pub fn new() -> Arena { + Arena::with_capacity(DEFAULT_CAPACITY) + } + + /// Constructs a new, empty `Arena` with the specified capacity. + /// + /// The `Arena` will be able to hold `n` elements without further allocation. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(10); + /// + /// // These insertions will not require further allocation. + /// for i in 0..10 { + /// assert!(arena.try_insert(i).is_ok()); + /// } + /// + /// // But now we are at capacity, and there is no more room. + /// assert!(arena.try_insert(99).is_err()); + /// ``` + pub fn with_capacity(n: usize) -> Arena { + let n = cmp::max(n, 1); + let mut arena = Arena { + items: Vec::new(), + generation: 0, + free_list_head: None, + len: 0, + }; + arena.reserve(n); + arena + } + + /// Clear all the items inside the arena, but keep its allocation. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(1); + /// arena.insert(42); + /// arena.insert(43); + /// + /// arena.clear(); + /// + /// assert_eq!(arena.capacity(), 2); + /// ``` + pub fn clear(&mut self) { + self.items.clear(); + + let end = self.items.capacity(); + self.items.extend((0..end).map(|i| { + if i == end - 1 { + Entry::Free { next_free: None } + } else { + Entry::Free { + next_free: Some(i + 1), + } + } + })); + self.free_list_head = Some(0); + self.len = 0; + } + + /// Attempts to insert `value` into the arena using existing capacity. + /// + /// This method will never allocate new capacity in the arena. + /// + /// If insertion succeeds, then the `value`'s index is returned. If + /// insertion fails, then `Err(value)` is returned to give ownership of + /// `value` back to the caller. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// + /// match arena.try_insert(42) { + /// Ok(idx) => { + /// // Insertion succeeded. + /// assert_eq!(arena[idx], 42); + /// } + /// Err(x) => { + /// // Insertion failed. + /// assert_eq!(x, 42); + /// } + /// }; + /// ``` + #[inline] + pub fn try_insert(&mut self, value: T) -> Result { + match self.try_alloc_next_index() { + None => Err(value), + Some(index) => { + self.items[index.index] = Entry::Occupied { + generation: self.generation, + value, + }; + Ok(index) + } + } + } + + /// Attempts to insert the value returned by `create` into the arena using existing capacity. + /// `create` is called with the new value's associated index, allowing values that know their own index. + /// + /// This method will never allocate new capacity in the arena. + /// + /// If insertion succeeds, then the new index is returned. If + /// insertion fails, then `Err(create)` is returned to give ownership of + /// `create` back to the caller. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::{Arena, Index}; + /// + /// let mut arena = Arena::new(); + /// + /// match arena.try_insert_with(|idx| (42, idx)) { + /// Ok(idx) => { + /// // Insertion succeeded. + /// assert_eq!(arena[idx].0, 42); + /// assert_eq!(arena[idx].1, idx); + /// } + /// Err(x) => { + /// // Insertion failed. + /// } + /// }; + /// ``` + #[inline] + pub fn try_insert_with T>(&mut self, create: F) -> Result { + match self.try_alloc_next_index() { + None => Err(create), + Some(index) => { + self.items[index.index] = Entry::Occupied { + generation: self.generation, + value: create(index), + }; + Ok(index) + } + } + } + + #[inline] + fn try_alloc_next_index(&mut self) -> Option { + match self.free_list_head { + None => None, + Some(i) => match self.items[i] { + Entry::Occupied { .. } => panic!("corrupt free list"), + Entry::Free { next_free } => { + self.free_list_head = next_free; + self.len += 1; + Some(Index { + index: i, + generation: self.generation, + }) + } + }, + } + } + + /// Insert `value` into the arena, allocating more capacity if necessary. + /// + /// The `value`'s associated index in the arena is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// + /// let idx = arena.insert(42); + /// assert_eq!(arena[idx], 42); + /// ``` + #[inline] + pub fn insert(&mut self, value: T) -> Index { + match self.try_insert(value) { + Ok(i) => i, + Err(value) => self.insert_slow_path(value), + } + } + + /// Insert the value returned by `create` into the arena, allocating more capacity if necessary. + /// `create` is called with the new value's associated index, allowing values that know their own index. + /// + /// The new value's associated index in the arena is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::{Arena, Index}; + /// + /// let mut arena = Arena::new(); + /// + /// let idx = arena.insert_with(|idx| (42, idx)); + /// assert_eq!(arena[idx].0, 42); + /// assert_eq!(arena[idx].1, idx); + /// ``` + #[inline] + pub fn insert_with(&mut self, create: impl FnOnce(Index) -> T) -> Index { + match self.try_insert_with(create) { + Ok(i) => i, + Err(create) => self.insert_with_slow_path(create), + } + } + + #[inline(never)] + fn insert_slow_path(&mut self, value: T) -> Index { + let len = self.items.len(); + self.reserve(len); + self.try_insert(value) + .map_err(|_| ()) + .expect("inserting will always succeed after reserving additional space") + } + + #[inline(never)] + fn insert_with_slow_path(&mut self, create: impl FnOnce(Index) -> T) -> Index { + let len = self.items.len(); + self.reserve(len); + self.try_insert_with(create) + .map_err(|_| ()) + .expect("inserting will always succeed after reserving additional space") + } + + /// Remove the element at index `i` from the arena. + /// + /// If the element at index `i` is still in the arena, then it is + /// returned. If it is not in the arena, then `None` is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// assert_eq!(arena.remove(idx), Some(42)); + /// assert_eq!(arena.remove(idx), None); + /// ``` + pub fn remove(&mut self, i: Index) -> Option { + if i.index >= self.items.len() { + return None; + } + + match self.items[i.index] { + Entry::Occupied { generation, .. } if i.generation == generation => { + let entry = mem::replace( + &mut self.items[i.index], + Entry::Free { + next_free: self.free_list_head, + }, + ); + self.generation += 1; + self.free_list_head = Some(i.index); + self.len -= 1; + + match entry { + Entry::Occupied { + generation: _, + value, + } => Some(value), + _ => unreachable!(), + } + } + _ => None, + } + } + + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all indices such that `predicate(index, &value)` returns `false`. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut crew = Arena::new(); + /// crew.extend(&["Jim Hawkins", "John Silver", "Alexander Smollett", "Israel Hands"]); + /// let pirates = ["John Silver", "Israel Hands"]; // too dangerous to keep them around + /// crew.retain(|_index, member| !pirates.contains(member)); + /// let mut crew_members = crew.iter().map(|(_, member)| **member); + /// assert_eq!(crew_members.next(), Some("Jim Hawkins")); + /// assert_eq!(crew_members.next(), Some("Alexander Smollett")); + /// assert!(crew_members.next().is_none()); + /// ``` + pub fn retain(&mut self, mut predicate: impl FnMut(Index, &mut T) -> bool) { + for i in 0..self.capacity() { + let remove = match &mut self.items[i] { + Entry::Occupied { generation, value } => { + let index = Index { + index: i, + generation: *generation, + }; + if predicate(index, value) { + None + } else { + Some(index) + } + } + + _ => None, + }; + if let Some(index) = remove { + self.remove(index); + } + } + } + + /// Is the element at index `i` in the arena? + /// + /// Returns `true` if the element at `i` is in the arena, `false` otherwise. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// assert!(arena.contains(idx)); + /// arena.remove(idx); + /// assert!(!arena.contains(idx)); + /// ``` + pub fn contains(&self, i: Index) -> bool { + self.get(i).is_some() + } + + /// Get a shared reference to the element at index `i` if it is in the + /// arena. + /// + /// If the element at index `i` is not in the arena, then `None` is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// assert_eq!(arena.get(idx), Some(&42)); + /// arena.remove(idx); + /// assert!(arena.get(idx).is_none()); + /// ``` + pub fn get(&self, i: Index) -> Option<&T> { + match self.items.get(i.index) { + Some(Entry::Occupied { generation, value }) if *generation == i.generation => { + Some(value) + } + _ => None, + } + } + + /// Get an exclusive reference to the element at index `i` if it is in the + /// arena. + /// + /// If the element at index `i` is not in the arena, then `None` is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// *arena.get_mut(idx).unwrap() += 1; + /// assert_eq!(arena.remove(idx), Some(43)); + /// assert!(arena.get_mut(idx).is_none()); + /// ``` + pub fn get_mut(&mut self, i: Index) -> Option<&mut T> { + match self.items.get_mut(i.index) { + Some(Entry::Occupied { generation, value }) if *generation == i.generation => { + Some(value) + } + _ => None, + } + } + + /// Get a pair of exclusive references to the elements at index `i1` and `i2` if it is in the + /// arena. + /// + /// If the element at index `i1` or `i2` is not in the arena, then `None` is returned for this + /// element. + /// + /// # Panics + /// + /// Panics if `i1` and `i2` are pointing to the same item of the arena. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx1 = arena.insert(0); + /// let idx2 = arena.insert(1); + /// + /// { + /// let (item1, item2) = arena.get2_mut(idx1, idx2); + /// + /// *item1.unwrap() = 3; + /// *item2.unwrap() = 4; + /// } + /// + /// assert_eq!(arena[idx1], 3); + /// assert_eq!(arena[idx2], 4); + /// ``` + pub fn get2_mut(&mut self, i1: Index, i2: Index) -> (Option<&mut T>, Option<&mut T>) { + let len = self.items.len(); + + if i1.index == i2.index { + assert!(i1.generation != i2.generation); + + if i1.generation > i2.generation { + return (self.get_mut(i1), None); + } + return (None, self.get_mut(i2)); + } + + if i1.index >= len { + return (None, self.get_mut(i2)); + } else if i2.index >= len { + return (self.get_mut(i1), None); + } + + let (raw_item1, raw_item2) = { + let (xs, ys) = self.items.split_at_mut(cmp::max(i1.index, i2.index)); + if i1.index < i2.index { + (&mut xs[i1.index], &mut ys[0]) + } else { + (&mut ys[0], &mut xs[i2.index]) + } + }; + + let item1 = match raw_item1 { + Entry::Occupied { generation, value } if *generation == i1.generation => Some(value), + _ => None, + }; + + let item2 = match raw_item2 { + Entry::Occupied { generation, value } if *generation == i2.generation => Some(value), + _ => None, + }; + + (item1, item2) + } + + /// Get the length of this arena. + /// + /// The length is the number of elements the arena holds. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// assert_eq!(arena.len(), 0); + /// + /// let idx = arena.insert(42); + /// assert_eq!(arena.len(), 1); + /// + /// let _ = arena.insert(0); + /// assert_eq!(arena.len(), 2); + /// + /// assert_eq!(arena.remove(idx), Some(42)); + /// assert_eq!(arena.len(), 1); + /// ``` + pub fn len(&self) -> usize { + self.len + } + + /// Returns true if the arena contains no elements + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// assert!(arena.is_empty()); + /// + /// let idx = arena.insert(42); + /// assert!(!arena.is_empty()); + /// + /// assert_eq!(arena.remove(idx), Some(42)); + /// assert!(arena.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self.len == 0 + } + + /// Get the capacity of this arena. + /// + /// The capacity is the maximum number of elements the arena can hold + /// without further allocation, including however many it currently + /// contains. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(10); + /// assert_eq!(arena.capacity(), 10); + /// + /// // `try_insert` does not allocate new capacity. + /// for i in 0..10 { + /// assert!(arena.try_insert(1).is_ok()); + /// assert_eq!(arena.capacity(), 10); + /// } + /// + /// // But `insert` will if the arena is already at capacity. + /// arena.insert(0); + /// assert!(arena.capacity() > 10); + /// ``` + pub fn capacity(&self) -> usize { + self.items.len() + } + + /// Allocate space for `additional_capacity` more elements in the arena. + /// + /// # Panics + /// + /// Panics if this causes the capacity to overflow. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(10); + /// arena.reserve(5); + /// assert_eq!(arena.capacity(), 15); + /// # let _: Arena = arena; + /// ``` + pub fn reserve(&mut self, additional_capacity: usize) { + let start = self.items.len(); + let end = self.items.len() + additional_capacity; + let old_head = self.free_list_head; + self.items.reserve_exact(additional_capacity); + self.items.extend((start..end).map(|i| { + if i == end - 1 { + Entry::Free { + next_free: old_head, + } + } else { + Entry::Free { + next_free: Some(i + 1), + } + } + })); + self.free_list_head = Some(start); + } + + /// Iterate over shared references to the elements in this arena. + /// + /// Yields pairs of `(Index, &T)` items. + /// + /// Order of iteration is not defined. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// for i in 0..10 { + /// arena.insert(i * i); + /// } + /// + /// for (idx, value) in arena.iter() { + /// println!("{} is at index {:?}", value, idx); + /// } + /// ``` + pub fn iter(&self) -> Iter { + Iter { + len: self.len, + inner: self.items.iter().enumerate(), + } + } + + /// Iterate over exclusive references to the elements in this arena. + /// + /// Yields pairs of `(Index, &mut T)` items. + /// + /// Order of iteration is not defined. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// for i in 0..10 { + /// arena.insert(i * i); + /// } + /// + /// for (_idx, value) in arena.iter_mut() { + /// *value += 5; + /// } + /// ``` + pub fn iter_mut(&mut self) -> IterMut { + IterMut { + len: self.len, + inner: self.items.iter_mut().enumerate(), + } + } + + /// Iterate over elements of the arena and remove them. + /// + /// Yields pairs of `(Index, T)` items. + /// + /// Order of iteration is not defined. + /// + /// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx_1 = arena.insert("hello"); + /// let idx_2 = arena.insert("world"); + /// + /// assert!(arena.get(idx_1).is_some()); + /// assert!(arena.get(idx_2).is_some()); + /// for (idx, value) in arena.drain() { + /// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world")); + /// } + /// assert!(arena.get(idx_1).is_none()); + /// assert!(arena.get(idx_2).is_none()); + /// ``` + pub fn drain(&mut self) -> Drain { + Drain { + inner: self.items.drain(..).enumerate(), + } + } + + /// Given an i of `usize` without a generation, get a shared reference + /// to the element and the matching `Index` of the entry behind `i`. + /// + /// This method is useful when you know there might be an element at the + /// position i, but don't know its generation or precise Index. + /// + /// Use cases include using indexing such as Hierarchical BitMap Indexing or + /// other kinds of bit-efficient indexing. + /// + /// You should use the `get` method instead most of the time. + pub fn get_unknown_gen(&self, i: usize) -> Option<(&T, Index)> { + match self.items.get(i) { + Some(Entry::Occupied { generation, value }) => Some(( + value, + Index { + generation: *generation, + index: i, + }, + )), + _ => None, + } + } + + /// Given an i of `usize` without a generation, get an exclusive reference + /// to the element and the matching `Index` of the entry behind `i`. + /// + /// This method is useful when you know there might be an element at the + /// position i, but don't know its generation or precise Index. + /// + /// Use cases include using indexing such as Hierarchical BitMap Indexing or + /// other kinds of bit-efficient indexing. + /// + /// You should use the `get_mut` method instead most of the time. + pub fn get_unknown_gen_mut(&mut self, i: usize) -> Option<(&mut T, Index)> { + match self.items.get_mut(i) { + Some(Entry::Occupied { generation, value }) => Some(( + value, + Index { + generation: *generation, + index: i, + }, + )), + _ => None, + } + } +} + +impl IntoIterator for Arena { + type Item = T; + type IntoIter = IntoIter; + fn into_iter(self) -> Self::IntoIter { + IntoIter { + len: self.len, + inner: self.items.into_iter(), + } + } +} + +/// An iterator over the elements in an arena. +/// +/// Yields `T` items. +/// +/// Order of iteration is not defined. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// for i in 0..10 { +/// arena.insert(i * i); +/// } +/// +/// for value in arena { +/// assert!(value < 100); +/// } +/// ``` +#[derive(Clone, Debug)] +pub struct IntoIter { + len: usize, + inner: vec::IntoIter>, +} + +impl Iterator for IntoIter { + type Item = T; + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some(Entry::Free { .. }) => continue, + Some(Entry::Occupied { value, .. }) => { + self.len -= 1; + return Some(value); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (self.len, Some(self.len)) + } +} + +impl DoubleEndedIterator for IntoIter { + fn next_back(&mut self) -> Option { + loop { + match self.inner.next_back() { + Some(Entry::Free { .. }) => continue, + Some(Entry::Occupied { value, .. }) => { + self.len -= 1; + return Some(value); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } +} + +impl ExactSizeIterator for IntoIter { + fn len(&self) -> usize { + self.len + } +} + +impl FusedIterator for IntoIter {} + +impl<'a, T> IntoIterator for &'a Arena { + type Item = (Index, &'a T); + type IntoIter = Iter<'a, T>; + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +/// An iterator over shared references to the elements in an arena. +/// +/// Yields pairs of `(Index, &T)` items. +/// +/// Order of iteration is not defined. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// for i in 0..10 { +/// arena.insert(i * i); +/// } +/// +/// for (idx, value) in &arena { +/// println!("{} is at index {:?}", value, idx); +/// } +/// ``` +#[derive(Clone, Debug)] +pub struct Iter<'a, T: 'a> { + len: usize, + inner: iter::Enumerate>>, +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = (Index, &'a T); + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some((_, &Entry::Free { .. })) => continue, + Some(( + index, + &Entry::Occupied { + generation, + ref value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (self.len, Some(self.len)) + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + fn next_back(&mut self) -> Option { + loop { + match self.inner.next_back() { + Some((_, &Entry::Free { .. })) => continue, + Some(( + index, + &Entry::Occupied { + generation, + ref value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } +} + +impl<'a, T> ExactSizeIterator for Iter<'a, T> { + fn len(&self) -> usize { + self.len + } +} + +impl<'a, T> FusedIterator for Iter<'a, T> {} + +impl<'a, T> IntoIterator for &'a mut Arena { + type Item = (Index, &'a mut T); + type IntoIter = IterMut<'a, T>; + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +/// An iterator over exclusive references to elements in this arena. +/// +/// Yields pairs of `(Index, &mut T)` items. +/// +/// Order of iteration is not defined. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// for i in 0..10 { +/// arena.insert(i * i); +/// } +/// +/// for (_idx, value) in &mut arena { +/// *value += 5; +/// } +/// ``` +#[derive(Debug)] +pub struct IterMut<'a, T: 'a> { + len: usize, + inner: iter::Enumerate>>, +} + +impl<'a, T> Iterator for IterMut<'a, T> { + type Item = (Index, &'a mut T); + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some((_, &mut Entry::Free { .. })) => continue, + Some(( + index, + &mut Entry::Occupied { + generation, + ref mut value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (self.len, Some(self.len)) + } +} + +impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { + fn next_back(&mut self) -> Option { + loop { + match self.inner.next_back() { + Some((_, &mut Entry::Free { .. })) => continue, + Some(( + index, + &mut Entry::Occupied { + generation, + ref mut value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } +} + +impl<'a, T> ExactSizeIterator for IterMut<'a, T> { + fn len(&self) -> usize { + self.len + } +} + +impl<'a, T> FusedIterator for IterMut<'a, T> {} + +/// An iterator that removes elements from the arena. +/// +/// Yields pairs of `(Index, T)` items. +/// +/// Order of iteration is not defined. +/// +/// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// let idx_1 = arena.insert("hello"); +/// let idx_2 = arena.insert("world"); +/// +/// assert!(arena.get(idx_1).is_some()); +/// assert!(arena.get(idx_2).is_some()); +/// for (idx, value) in arena.drain() { +/// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world")); +/// } +/// assert!(arena.get(idx_1).is_none()); +/// assert!(arena.get(idx_2).is_none()); +/// ``` +#[derive(Debug)] +pub struct Drain<'a, T: 'a> { + inner: iter::Enumerate>>, +} + +impl<'a, T> Iterator for Drain<'a, T> { + type Item = (Index, T); + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some((_, Entry::Free { .. })) => continue, + Some((index, Entry::Occupied { generation, value })) => { + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => return None, + } + } + } +} + +impl Extend for Arena { + fn extend>(&mut self, iter: I) { + for t in iter { + self.insert(t); + } + } +} + +impl FromIterator for Arena { + fn from_iter>(iter: I) -> Self { + let iter = iter.into_iter(); + let (lower, upper) = iter.size_hint(); + let cap = upper.unwrap_or(lower); + let cap = cmp::max(cap, 1); + let mut arena = Arena::with_capacity(cap); + arena.extend(iter); + arena + } +} + +impl ops::Index for Arena { + type Output = T; + + fn index(&self, index: Index) -> &Self::Output { + self.get(index).expect("No element at index") + } +} + +impl ops::IndexMut for Arena { + fn index_mut(&mut self, index: Index) -> &mut Self::Output { + self.get_mut(index).expect("No element at index") + } +} diff --git a/src/data/graph.rs b/src/data/graph.rs new file mode 100644 index 0000000..ea27e03 --- /dev/null +++ b/src/data/graph.rs @@ -0,0 +1,830 @@ +// This is basically a stripped down version of petgraph's UnGraph. +// - It is not generic wrt. the index type (we always use u32). +// - It preserves associated edge iteration order after Serialization/Deserialization. +// - It is always undirected. +//! A stripped-down version of petgraph's UnGraph. + +use std::cmp::max; +use std::ops::{Index, IndexMut}; + +/// Node identifier. +#[derive(Copy, Clone, Default, PartialEq, PartialOrd, Eq, Ord, Hash, Debug)] +#[cfg_attr(feature = "serde