Collision Detection

A tree data structure used to organize objects in space to accelerate collision queries. Instead of checking every object pair (an O(n²) operation), the BVH groups objects into nested bounding volumes (like boxes or spheres). The tree is traversed, and only volumes that overlap are tested further.

• Types: Common bounding volumes include Axis-Aligned Bounding Boxes (AABB), Oriented Bounding Boxes (OBB), and Spheres.
• Construction: Can be built top-down (divide space) or bottom-up (cluster objects).
• Use Case: Essential for real-time applications like physics simulation and rendering, where thousands of objects exist.

A fundamental theorem for detecting intersection between convex polygons or polyhedra. It states: Two convex shapes are disjoint if and only if there exists an axis onto which their projections do not overlap.

• Process: The algorithm tests a set of candidate axes derived from the shapes' edges or face normals.
• Efficiency: Highly efficient for pairs of convex shapes like boxes and polygons.
• Limitation: Only guaranteed for convex shapes; non-convex shapes must first be decomposed into convex parts.

An iterative algorithm for computing the distance between two convex sets and detecting collision. It is renowned for its speed and simplicity in implementation.

• Core Concept: Uses Minkowski Difference to transform the collision problem into determining if the origin is inside the resulting shape.
• Support Function: The algorithm relies on a function that returns the farthest point in a given direction for each shape.
• Output: Returns a boolean for collision and, with the Expanding Polytope Algorithm (EPA), can provide the penetration depth and vector.

A broad-phase algorithm that quickly identifies pairs of objects that are potentially colliding by sorting their projections onto coordinate axes. It exploits temporal coherence—the idea that objects move little between time steps.

• Mechanism: Maintains sorted lists of object start and end points along the X, Y, and Z axes. Overlapping intervals on all axes indicate a potential collision pair.
• Complexity: Reduces pair checks from O(n²) to O(n log n + k), where k is the number of overlapping pairs.
• Application: Almost universally used as the first step in physics engines and motion planners to cull obviously separate objects.

Also known as dynamic or time-continuous collision detection. Unlike discrete methods that check at fixed time steps (risking tunneling), CCD checks for collisions along the entire path an object travels between frames.

• Tunneling Problem: Fast-moving small objects can pass through thin obstacles between discrete checks.
• Methods: Often uses conservative advancement or computes the time of impact (TOI) by solving equations of motion.
• Critical For: High-speed robotics, bullet physics, and any simulation where discrete checks are insufficient for safety.

Spatial partitioning techniques that divide the workspace into a uniform grid (voxels) or use a hash function to map object coordinates to grid cells.

• Voxel Grid: The environment is discretized into a 3D grid. Each object is associated with the voxels it occupies. Collision checks only occur between objects sharing voxels.
• Spatial Hashing: A more memory-efficient method where a hash function converts object bounding box coordinates into a hash table key. Objects in the same hash bucket are tested.
• Advantage: Extremely fast for large numbers of small, uniformly sized objects in a bounded space.

Collision detection is the core safety check within sampling-based planners like RRT (Rapidly-exploring Random Tree) and PRM (Probabilistic Roadmap). These algorithms generate candidate robot configurations and must verify each one is in free space (collision-free) before adding it to a path. Efficient collision checking often consumes over 90% of a motion planner's computation time, making optimized geometric algorithms essential for real-time performance.

For dynamic environments with moving obstacles or humans (Human-Robot Interaction), collision detection shifts from pre-planning to a continuous, high-frequency loop. This involves:

• Proximity queries to compute minimum distances between the robot and obstacles.
• Velocity obstacles or model predictive control (MPC) to predict and evade potential future collisions.
• Integration with force/torque sensors for contact detection upon unexpected touch. Latency targets are often < 1 ms for critical control loops.

Physics engines like NVIDIA PhysX, Bullet, and MuJoCo rely on collision detection to simulate realistic physical interactions for Sim-to-Real Transfer Learning. This is used for:

• Training reinforcement learning policies safely in virtual environments.
• Testing thousands of robotic manipulation scenarios before hardware deployment.
• Validating plans via kinodynamic simulation to ensure they are dynamically feasible and collision-free.

Grasp planning requires precise collision detection between a robot's gripper, the target object, and surrounding clutter. This involves:

• Computing antipodal contact points that yield force-closure grasps.
• Verifying the gripper's closing trajectory does not collide with the object or environment.
• In dexterous manipulation, continuous collision checking is needed for finger-object and object-object contacts during in-hand manipulation sequences.

A fundamental technique is to transform the problem by mapping the robot's physical geometry into an abstract Configuration Space (C-Space). In this space:

• The robot is represented as a single point.
• Obstacles are expanded into forbidden regions called C-obstacles.
• Collision detection becomes a point-in-region test, which is often simpler and faster. This transformation is central to many classic motion planning algorithms.

For computational efficiency, collision detection is typically a two-stage pipeline:

• Broad Phase: Quickly identifies pairs of objects that are potentially colliding using fast approximate volumes like Axis-Aligned Bounding Boxes (AABBs) or spatial partitioning structures (BVH trees, grids). This eliminates most object pairs from costly detailed checks.
• Narrow Phase: Performs exact geometric intersection tests on the candidate pairs from the broad phase using algorithms like Gilbert–Johnson–Keerthi (GJK) for convex shapes or Minkowski sums.