How CAD Collision Detection Works in Motion Simulation

This article examines how collision detection algorithms operate within Computer-Aided Design (CAD) during motion simulations. In mechanical engineering, ensuring that moving components do not intersect or bind is critical for assembly validation and functional testing. The following sections explain the computational pipeline CAD systems use, focusing on the broad-phase and narrow-phase filtering steps, the distinction between discrete and continuous time-step verification, and the mathematical methods used to calculate exact points of clearance and contact.

The Computational Pipeline

CAD models are geometrically complex, often containing thousands of surfaces defined by boundary representation (B-rep) or fine polygonal meshes. Calculating intersections directly between every face of every moving component at every moment is computationally impossible in real time. To solve this, CAD systems use a hierarchical, two-phase pipeline: the broad phase and the narrow phase.

1. Broad-Phase Detection

The broad phase rapidly eliminates pairs of components that are too far apart to possibly collide. Instead of evaluating complex geometry, the engine wraps each component in a simple, conservative geometric proxy called a Bounding Volume (BV). Common bounding volumes include:

  • Axis-Aligned Bounding Boxes (AABB): Rectangular boxes whose faces are aligned with the coordinate axes. They are cheap to compute and fast to test for overlap.
  • Oriented Bounding Boxes (OBB): Boxes that rotate along with the local orientation of the part. They fit tighter around elongated, angled parts than AABBs, reducing false positives.
  • Bounding Spheres: Rotation-invariant spheres defined simply by a center point and a radius.

To further accelerate this phase, CAD kernels place these volumes into Bounding Volume Hierarchies (BVH) or spatial partitioning structures such as Octrees and k-d trees. The simulation engine only checks for overlap among components occupying the same spatial zones.

2. Narrow-Phase Detection

Once the broad phase identifies candidate pairs whose bounding volumes overlap, the system passes those pairs to the narrow phase. This phase performs exact mathematical checks using the true geometry of the CAD models.

Key algorithms used during the narrow phase include:

  • Gilbert-Johnson-Keerthi (GJK) Algorithm: Evaluates convex shapes by computing the minimum distance between them using Minkowski difference operations. If the Minkowski difference contains the origin, a collision has occurred.
  • Expanding Polytope Algorithm (EPA): Often paired with GJK to determine the penetration depth and the normal vector if an intersection is detected.
  • Surface-to-Surface Intersection for NURBS: When working directly with non-uniform rational B-spline surfaces (the mathematical foundation of B-rep CAD), algorithms subdivide surfaces adaptively into planar patches or solve non-linear algebraic equations directly to find exact intersection curves.

Handling Time: Discrete vs. Continuous Collision Detection

Motion simulation introduces the element of time, requiring algorithms to evaluate positions as components move along kinematic paths.

Discrete Collision Detection (DCD)

DCD samples the simulation at fixed time intervals (\(\Delta t\)). At each step, the engine updates component positions and runs collision checks.

While computationally efficient, DCD suffers from the "tunneling" problem: if an object moves fast enough relative to its thickness, it may pass entirely through another object between two consecutive time steps without an intersection ever registering.

Continuous Collision Detection (CCD)

To prevent tunneling, CAD platforms employ Continuous Collision Detection for critical moving assemblies. CCD evaluates the trajectory of parts across the entire interval from \(t\) to \(t + \Delta t\).

  • Swept Volumes: The system mathematically sweeps the geometry of the moving component along its motion trajectory, creating a temporary volume. If this swept volume intersects a static or moving counterpart, a collision is guaranteed.
  • Time-of-Impact (TOI) Root Finding: The algorithm treats distance between moving bodies as a function of time and employs numerical root-finding methods (such as conservative advancement) to determine the exact fraction of the time step at which the distance drops to zero.

Clearance and Contact Reporting

Collision detection algorithms in CAD do not merely detect collisions; they also quantify clearance. By tracking the shortest distance between features, the system can enforce user-defined safety thresholds.

When a collision or breach of minimum clearance occurs, the algorithm extracts the exact coordinates of contact, surface normals, and penetration depth. This data allows the simulation to either halt to notify the user, highlight colliding faces visually, or pass the contact parameters to kinematic and dynamic solvers to calculate reactive forces.