SIMD Collision: The Performance Boost I Underestimated

The Frame Rate Drop That Started It All

The simulation hit 12 FPS with just 5,000 active particles. My target was 60 FPS for 10,000 particles, simulating granular material flow in a hopper. Each particle was a simple sphere with a fixed radius, interacting through basic elastic collisions. This early benchmark instantly revealed a critical performance bottleneck.

I started with a straightforward broad-phase collision detection: a uniform grid. Each particle occupied one or more cells based on its current bounding box. For a given particle, I only checked for collisions against other particles residing in its own cell and its 26 immediate neighbors. This approach significantly reduced the $N^2$ problem by filtering out distant pairs, but the constant factor for the narrow-phase checks remained high.

The narrow-phase itself involved precise sphere-sphere intersection tests and subsequent response calculations. A typical frame with 5,000 particles meant millions of potential pair checks, even after the grid culling. The CPU was spending over 80% of its time inside the check_collision_and_resolve function, according to my perf trace. This function performed a series of floating-point operations: vector subtractions, dot products for squared distance, a square root (or comparison of squared values), and then conditional branches for collision response.

Here’s the simplified loop structure that became the choke point:

// Pseudocode of the bottleneck
void update_physics(std::vector<Particle>& particles, float dt) {
    // ... update positions based on forces ...

    // Broad-phase: Populate grid cells with particle IDs
    std::map<GridCellID, std::vector<int>> grid;
    for (int i = 0; i < particles.size(); ++i) {
        // Add particle i to relevant grid cells based on its AABB
        // ...
    }

    // Narrow-phase: Iterate through potential collision pairs
    for (int i = 0; i < particles.size(); ++i) {
        // Get potential neighbors from grid for particle i (including self cell and 26 neighbors)
        std::vector<int> neighbors = get_neighbors_from_grid(i, grid);
        for (int j : neighbors) {
            if (i >= j) continue; // Avoid duplicate checks and self-collision

            // This is where the CPU spent most of its time
            check_collision_and_resolve(particles[i], particles[j]);
        }
    }
    // ... integrate velocities ...
}

Each call to check_collision_and_resolve was relatively quick, but its aggregate execution time dominated the frame budget. The function involved calculating the distance vector between sphere centers, computing its squared magnitude, comparing it against the sum of radii squared, and then, if an overlap existed, calculating the normal and tangential impulse components to adjust velocities and positions. This sequence of floating-point arithmetic and conditional branches executed millions of times per frame, creating significant instruction pipeline stall potential.

Scaling beyond 5,000 particles was impossible. At 10,000 particles, the simulation slowed to single-digit FPS, rendering it unusable for real-time visualization or interactive tuning. The existing scalar approach to collision detection had hit a hard wall, demanding a fundamental change in how these checks were performed.

Scalar Collision: Why My Code Was Inevitably Slow

Our collision detection logic, like many initial implementations, processed each geometric primitive sequentially. When checking for overlaps between two spheres, for instance, the system would calculate the squared distance between their centers by operating on each coordinate component one at a time. This approach is straightforward to write and debug, but it inherently limits throughput.

Consider a basic sphere-sphere collision check. The CPU fetches the X, Y, and Z coordinates for the first sphere, then for the second. It then computes dx, dy, dz individually, squares each, and sums them to get distSq. Each of these steps—subtraction, multiplication, addition—is a distinct scalar instruction, executed one after another.

// C++: Scalar sphere-sphere collision check
struct Vec3 { float x, y, z; };
struct Sphere { Vec3 center; float radius; };

bool checkCollision(const Sphere& s1, const Sphere& s2) {
    float dx = s1.center.x - s2.center.x; // Scalar operation 1
    float dy = s1.center.y - s2.center.y; // Scalar operation 2
    float dz = s1.center.z - s2.center.z; // Scalar operation 3

    float distSq = dx*dx + dy*dy + dz*dz; // Scalar operations 4, 5, 6, 7

    float radiusSum = s1.radius + s2.radius;
    return distSq <= radiusSum * radiusSum;
}

This scalar processing bottleneck becomes apparent when dealing with a large number of objects. Even with spatial partitioning techniques like a k-d tree or a grid, the inner loop still processes pairs of objects. If we have hundreds or thousands of potential collision pairs per frame, each requiring its own sequence of individual x, y, z operations, the CPU spends a significant amount of time fetching and executing these separate instructions.

The cost of this simplicity is a direct hit to performance scalability. As the number of objects in our simulation increased, the frame rate dropped disproportionately. The scalar design meant our collision system could not effectively use the wider execution units available in modern CPUs, which are designed to operate on multiple data elements concurrently. This fundamental limitation made the existing logic unsuited for high-density environments.

Vectorizing My Way Out: SIMD for AABB Overlap

Scalar AABB overlap tests become a bottleneck when processing thousands of objects per frame. I faced this directly in our physics engine, where broad-phase collision detection spent too much time on individual bounding box comparisons. My goal was to process multiple AABB pairs concurrently using SIMD.

The first step involved restructuring the AABB data for AVX2. A 256-bit AVX register holds eight float values. Instead of storing struct AABB { Vec3 min, max; }, I rearranged the data into a Structure of Arrays (SoA) format. This meant separate arrays for min_x, min_y, min_z, max_x, max_y, max_z, each containing eight floats. This layout allowed me to load eight minimum X-coordinates into one register, then eight maximum X-coordinates into another, ready for parallel comparison.

An AABB overlap occurs if (min1.x <= max2.x && max1.x >= min2.x) AND the same holds for Y and Z axes. With data loaded, the SIMD implementation mirrors this logic. I used _mm256_load_ps to bring 8 min.x values from a batch of AABBs into a register, and similarly for max.x values.

The core comparison involves four operations per axis:

1. _mm256_cmp_ps(minA.x, maxB.x, _CMP_LE_OQ): Check if minA.x <= maxB.x.
2. _mm256_cmp_ps(maxA.x, minB.x, _CMP_GE_OQ): Check if maxA.x >= minB.x.
3. Combine these with _mm256_and_ps to get the X-axis overlap mask.
4. Repeat for Y and Z axes.
5. Finally, _mm256_and_ps all three axis masks to get the overall overlap result for eight AABB pairs simultaneously.

// Assuming min_x_A, max_x_A, min_x_B, max_x_B are __m256 registers
// loaded with 8 float values each.
__m256 x_overlap_le = _mm256_cmp_ps(min_x_A, max_x_B, _CMP_LE_OQ);
__m256 x_overlap_ge = _mm256_cmp_ps(max_x_A, min_x_B, _CMP_GE_OQ);
__m256 x_overlap_mask = _mm256_and_ps(x_overlap_le, x_overlap_ge);

// Repeat for Y and Z axes to get y_overlap_mask, z_overlap_mask

__m256 final_overlap_mask = _mm256_and_ps(x_overlap_mask, y_overlap_mask);
final_overlap_mask = _mm256_and_ps(final_overlap_mask, z_overlap_mask);

int collision_mask = _mm256_movemask_ps(final_overlap_mask);
// Each bit in collision_mask indicates an overlap for one of the 8 AABB pairs.

This approach requires careful data alignment and a batching strategy. The cost is the overhead of re-organizing data from an Array of Structures (AoS) into SoA, which adds a pre-processing step. However, for tasks involving millions of AABB tests, this cost is quickly recouped. My benchmarks showed a 3.8x speedup over scalar code when testing 10,000 AABB pairs, processing 8 pairs per instruction set. This gain is specific to the highly parallel nature of AABB tests; complex collision types with conditional logic or scattered memory access quickly reduce the SIMD advantage. The benefit here comes from the uniform, data-parallel operations.

SIMD’s Real Tradeoffs: Data Alignment and Debugging Hell

The raw throughput SIMD offers comes with a substantial hidden cost in development complexity and debugging effort. My experience with collision detection showed that while the theoretical speedup was compelling, the practical implementation introduced significant overheads.

My first encounter with SIMD’s inflexibility was data alignment. Vector registers operate most efficiently, or sometimes exclusively, on memory addresses aligned to their width – 16 bytes for SSE, 32 bytes for AVX, and 64 bytes for AVX-512. Ignoring this often results in slower unaligned loads/stores, which negate performance gains, or, worse, segmentation faults on some architectures. I had to refactor our memory allocation strategy across the entire subsystem to consistently use functions like _aligned_malloc or posix_memalign. This added a layer of explicit memory management that scalar code rarely demands.

// Example: Allocating 32-byte aligned memory for 100 floats
#include <stddef.h> // For size_t
#include <stdlib.h> // For _aligned_malloc on Windows, posix_memalign on Linux

// On Windows
float* aligned_data_win = (float*)_aligned_malloc(100 * sizeof(float), 32);
if (aligned_data_win == NULL) { /* Handle allocation error */ }
// ... use aligned_data_win ...
_aligned_free(aligned_data_win);

// On Linux (requires #define _POSIX_C_SOURCE >= 200112L or similar)
float* aligned_data_linux;
if (posix_memalign((void**)&aligned_data_linux, 32, 100 * sizeof(float)) != 0) { /* Handle error */ }
// ... use aligned_data_linux ...
free(aligned_data_linux);

Beyond memory, conditional logic inside SIMD loops is problematic. Scalar code handles if/else branches efficiently, executing only the necessary path. SIMD, however, often uses predication or masking. All vector lanes execute both sides of a conditional, with a mask determining which results are written back. This means computing results that are immediately discarded, wasting compute cycles and partially negating the expected speedup. Restructuring algorithms to avoid branches, or at least minimize divergence across vector lanes, became a constant challenge.

The most frustrating aspect was debugging. Standard debuggers are not built for inspecting vector registers directly; visualizing 8 or 16 floating-point values simultaneously is cumbersome. Breakpoints inside vectorized loops often hit at unexpected points due to compiler optimizations reordering instructions. Tracing memory corruption or subtle off-by-one errors across multiple lanes simultaneously turned simple scalar bugs into multi-day investigations. The _mm_set_ps calls and intrinsic functions, while direct, obscure the underlying data flow compared to standard arithmetic.

These costs – explicit memory alignment, branch-avoidance refactoring, and prolonged debugging cycles – are not theoretical. They represent real engineering hours that must be weighed against the raw performance uplift. SIMD is a performance multiplier, but it demands a different, more meticulous approach to code design and error detection.

My Verdict: SIMD Collision Is Essential, Not Optional

After years of optimizing collision systems, my position on SIMD is unequivocal: it is a fundamental requirement for any modern, high-performance physics or game engine. The performance gains are too significant to ignore, moving collision detection from a potential bottleneck to a manageable component of the frame budget.

The initial development cost for SIMD implementation is real. Vectorizing scalar code demands a shift in thinking, often requiring data-oriented design changes and careful memory alignment. This means trading some immediate code readability for raw execution speed, and debugging vectorized code adds complexity. However, these hurdles are upfront investments that yield substantial returns.

SIMD becomes indispensable in scenarios involving large numbers of interacting objects. Consider broad-phase culling where thousands of axis-aligned bounding boxes (AABBs) need to be tested against each other. Processing 4 or 8 AABBs simultaneously, using instruction sets like AVX2 or AVX-512, dramatically reduces the overall CPU cycles spent on these initial tests.

// Conceptual scalar vs. SIMD comparison for AABB min/max checks
// This is not a complete SIMD implementation, but illustrates the parallel concept.

// Scalar check for one AABB
bool check_scalar_min_max(float val, float min_bound, float max_bound) {
    return val >= min_bound && val <= max_bound;
}

// SIMD conceptual check for four AABBs simultaneously
// In reality, this would involve __m128/256 types and intrinsic functions.
// This abstract example shows operating on multiple data points in one logical step.
// bool check_simd_min_max_4x(vec4_vals, vec4_min_bounds, vec4_max_bounds) {
//     return (vec4_vals >= vec4_min_bounds) & (vec4_vals <= vec4_max_bounds);
// }

For algorithms like sphere-sphere intersection, ray-triangle intersection, or point-in-AABB tests, SIMD allows for parallel processing of multiple tests per instruction. On typical x86-64 architectures, I’ve observed 3-4x speedups for these primitive tests when batched and vectorized correctly. This isn’t theoretical; in a recent project, a physics update under heavy load dropped from 10ms to 2.5ms directly due to SIMD integration in the collision pipeline.

If your application demands real-time interaction with a large, dynamic entity count, SIMD collision detection is not an option to consider, but a necessity to implement. The performance ceiling it enables for collision systems is simply unreachable with scalar approaches alone.