Acelerar la detección de colisiones con SIMD

• Box3D aplicó wide SIMD a pruebas complejas de colisión de envolventes convexas 3D, reduciendo a menos de la mitad el tiempo total de simulación de 5,120 objetos con 32 puntos y 89 aristas
• El teorema del eje separador (SAT) en 3D revisa combinaciones cara-vértice y arista-arista de dos envolventes; en Boulder-Boulder, las combinaciones de aristas llegan a 7,921, por lo que el costo del doble bucle puede dominar la simulación
• Al agrupar 4 aristas de hullB en formato SoA y probarlas simultáneamente contra una arista de hullA, el tiempo de ejecución de 1 hilo y 500 pasos bajó de Scalar 40,706 ms a SSE2 17,337 ms y AVX2-Lite 15,762 ms
• Incluso con 8 hilos registró Scalar 5,292 ms, SSE2 2,410 ms y AVX2-Lite 2,277 ms; estas mediciones corresponden a la simulación completa, incluyendo tanto las pruebas de aristas como el solucionador de contactos
• Las colisiones Box-Box, con solo 12 aristas, casi no se benefician por el costo de preparación, pero resulta útil para envolventes complejas usadas en efectos de destrucción, y a futuro queda margen para probar 8 aristas simultáneamente con AVX2

---

Costo computacional de SAT y forma de aplicar SIMD

• El wide SIMD de Box3D procesa varias unidades de trabajo al mismo tiempo, a diferencia del narrow SIMD, que coloca un vector xyz en un registro SIMD
  • En el solucionador de contactos resuelve 4 puntos de contacto de una sola vez
  • El narrow SIMD también puede ser útil, pero la mejora de rendimiento no es tan clara como con wide SIMD
• El benchmark Convex Pile portado desde PEEL deja caer 5,120 envolventes convexas, cada una con 32 puntos
  • Box está compuesto por 8 vértices, 6 caras y 12 aristas
  • Boulder está compuesto por 32 vértices, 59 caras y 89 aristas
  • Box3D también trata las cajas como envolventes y, en benchmarks centrados en Box, la narrow phase generalmente no era el costo principal
• Para la detección de colisiones se usa el teorema del eje separador (SAT)
  • Con SAT se encuentra la mejor característica para separar los objetos y la distancia de desplazamiento necesaria, y también se calculan la normal de contacto y los puntos de contacto
  • Otros motores de física también combinan GJK con EPA para manejar solapamientos
• SAT no requiere un margen de colisión, por lo que permite ubicar los objetos directamente en contacto entre sí
  • La combinación de GJK y EPA a veces separa un poco los objetos para mantenerse en la región más rápida de GJK, lo que puede crear huecos visuales
  • EPA puede ser numéricamente frágil y, como debe calcular envolventes convexas a partir de entradas planas y delgadas, a veces se necesita una segunda ruta alternativa ante fallas
• SAT 3D revisa, para dos envolventes A y B, las caras de A contra los vértices de B, las caras de B contra los vértices de A y las aristas de A contra las aristas de B, mostrando complejidad cuadrática
  • Box-Box implica 6 combinaciones cara-vértice, 6 vértice-cara y 144 arista-arista
  • Boulder-Boulder implica 59, 59 y 7,921 combinaciones, respectivamente
  • Con Gauss Map se pueden reducir las pruebas de aristas, pero las pruebas arista-arista pueden dominar toda la simulación
  • Se pueden consultar técnicas relacionadas en Improvements to the Separating Axis Test
• Para que SIMD funcione de forma eficiente, los datos deben prepararse como estructura de arreglos (SoA), por lo que en envolventes de 12 aristas el beneficio no es grande frente al costo de preparación
  • Al comparar 89 aristas contra 89, TestCrossProduct se llama 7,921 veces
  • La implementación wide SIMD prueba una arista de hullA simultáneamente contra un EdgeWide que contiene 4 aristas de hullB

Resultados del benchmark y alcance de aplicación

• Se fijó un AMD 7950X a 4.42 GHz y se ejecutaron 500 pasos con 1 a 8 hilos; cada cifra corresponde al mejor resultado de 4 ejecuciones

Hilos	Scalar	SSE2	AVX2-Lite
1	40,706 ms	17,337 ms	15,762 ms
2	20,799 ms	8,857 ms	8,131 ms
3	13,789 ms	5,946 ms	5,471 ms
4	10,324 ms	4,509 ms	4,084 ms
5	8,359 ms	3,675 ms	3,361 ms
6	6,958 ms	3,106 ms	2,843 ms
7	6,006 ms	2,697 ms	2,477 ms
8	5,292 ms	2,410 ms	2,277 ms

• SSE2 es más de 2 veces más rápido que Scalar, y las mediciones incluyen no solo las pruebas arista-arista, sino toda la simulación
  • En la columna Scalar, el solucionador de contactos también se ejecuta en modo Scalar
• Aunque Box3D solo implementa directamente funciones intrínsecas SIMD para SSE2, con solo activar la arquitectura AVX2 obtiene la mejora adicional de rendimiento de AVX2-Lite
  • Box2D también tiene intrínsecos AVX2, pero había más usuarios de lo esperado usando CPU sin soporte para AVX2
  • En el futuro, una implementación AVX2 real podría probar 8 aristas simultáneamente
• Box3D limita las aristas por envolvente a un máximo de 128 para mantener bajo el espacio de almacenamiento
  • Es una limitación derivada del esquema de almacenamiento con índices de 8 bits y dos half-edges por arista
  • Convertir envolventes complejas en mallas puede resolver el problema del crecimiento cuadrático, pero las vuelve menos adecuadas para objetos dinámicos
• En colisiones Box-Box, las pruebas SIMD de aristas casi no tienen efecto
  • En escenarios de destrucción que usan envolventes complejas, sí ofrecen una mejora de rendimiento suficiente

[GN⁺]

Comentarios en Lobste.rs

• SIMD parece difícil por proyectos complejos como simdutf o simdjson, pero el patrón básico de procesar N bytes a la vez en un bucle común es sorprendentemente simple
  Basta con replicar constantes en cada lane, inicializar un acumulador vectorial, recorrer la entrada con el ancho del vector haciendo comparaciones y operaciones, reducir o guardar el resultado, y luego procesar los elementos restantes con el bucle escalar de siempre
  En un proyecto real, cambiaron a este enfoque un bucle con salida temprana que buscaba valores menores o iguales a 0xF y obtuvieron una mejora de rendimiento de 2 a 16 veces según el hardware
  El compilador puede vectorizar automáticamente bucles aritméticos simples y regulares, pero no logra detectar de forma confiable transformaciones que combinan salida temprana, máscaras de comparación, reducción y búsqueda del primer lane con fallo. Más detalles en https://llvm.org/docs/Vectorizers.html
  Aunque la vectorización automática se ha investigado durante décadas, los compiladores reales todavía pierden oportunidades con frecuencia: https://arxiv.org/abs/2406.04693
  Una vez que uno se familiariza con el patrón básico, puede escribirlo tan naturalmente como un bucle escalar, así que más desarrolladores deberían aprenderlo y los lenguajes deberían ofrecer herramientas para ello. La versión ampliada está en https://mitchellh.com/writing/everyone-should-know-simd
  • Me pregunto si para aprovechar bien SIMD hace falta usar arreglo de estructuras (SoA) en vez de arreglo de structs (AoS). Con AoS, parece que la ventaja se perdería por las copias adicionales y el enmascaramiento, y también queda la duda de cómo diseñar una interfaz SIMD única cuando cada CPU soporta instrucciones distintas
    Quisiera saber si el runtime debe incluir implementaciones para cada conjunto de instrucciones de la arquitectura objetivo, además de una implementación alternativa para CPUs sin SIMD, o si normalmente se apunta solo a un conjunto de instrucciones específico
  • Me gusta especialmente el proyecto de investigación relacionado Halide, y ojalá se use en más proyectos
  • Me pregunto cuánto de la investigación reciente sobre vectorización automática se ha incorporado realmente a compiladores de uso real
    Recuerdo que antes muchas veces se quedaba en pruebas de concepto académicas o llegaba solo a algunos compiladores de Fortran, sin implementarse en compiladores principales