Simulación Háptica 3D con Detección de Colisiones Octree
Sistema de simulación 3D que recrea interacción háptica con objetos virtuales. Usa particionamiento espacial octree (O(N log N)) y Teorema del Eje Separador para detección de colisiones con modelo de fuerza Kelvin-Voigt resorte-amortiguador.
Contexto de Negocio
El renderizado háptico requiere detección de colisiones a tasas de actualización superiores a 1 kHz — el sentido del tacto humano percibe retardos de solo 1 milisegundo. Para mallas 3D con miles de triángulos, la prueba de colisión de fuerza bruta O(N²) es órdenes de magnitud demasiado lenta. Y la retroalimentación de fuerza debe sentirse natural: no una señal de contacto binaria on/off, sino resistencia continua que aumenta con la profundidad de penetración y provee estabilidad mediante disipación de energía.
Valor Estratégico
Detección de colisiones en dos fases logra tasas hápticas en tiempo real: particionamiento espacial octree para fase amplia O(N log N), Teorema del Eje Separador en 11 ejes para fase estrecha matemáticamente exacta. Las fuerzas de contacto siguen el modelo resorte-amortiguador de Kelvin-Voigt F = -k·(p_sonda - p_contacto) - b·v_sonda, produciendo sensación de tacto físicamente plausible. Originalmente construido en 2008 en Universidad de Concepción con un PHANToM Omni físico proveyendo retroalimentación de fuerza 3-DOF; modernizado como Python/FastAPI + Three.js WebGL con interacción de sonda por teclado que funciona sin hardware físico.
El Desafío
El renderizado háptico en tiempo real requiere detección de colisiones a tasas de actualización >1 kHz. La prueba bruta triángulo-triángulo es O(N²), demasiado lenta para mallas complejas. La retroalimentación de fuerza debe sentirse natural y físicamente plausible.
Nuestro Enfoque
Colisión en dos fases: particionamiento espacial octree para fase amplia O(N log N), SAT (Teorema del Eje Separador) para fase estrecha intersección triángulo-triángulo en 11 ejes. Fuerzas de contacto siguen Kelvin-Voigt resorte-amortiguador: F = -k·(p_sonda - p_contacto) - b·v_sonda. Versión web moderna con renderizado Three.js WebGL.
Indicadores Clave de Rendimiento
| KPI | Línea Base | Resultado | Impacto |
|---|---|---|---|
| Eficiencia de Colisión | O(N²) fuerza bruta | O(N log N) octree + SAT | Tasas hápticas en tiempo real |
| Modelo de Fuerza | Detección de contacto simple | Resorte-amortiguador Kelvin-Voigt | Retroalimentación físicamente plausible |
Arquitectura
haptic sim
The Speed Requirement
The human sense of touch perceives delays of just 1 millisecond. Haptic rendering requires collision detection at >1 kHz update rates. For a mesh with thousands of triangles, brute-force O(N²) testing is orders of magnitude too slow. And the force feedback can’t just detect contact — it must feel natural and physically plausible.
Two-Phase Collision
The broad phase uses octree spatial partitioning — the scene recursively divided into octants, each containing a subset of triangles. A probe query only tests against the traversed octant and its neighbors, reducing complexity to O(N log N).
The narrow phase uses the Separating Axis Theorem (SAT): for each candidate triangle pair, test intersection along 11 potential separating axes — 2 face normals plus 9 edge cross-products. If any axis separates the two triangles, they don’t intersect. Only when all 11 fail is there a collision. Mathematically complete and exact.
Force Feedback
Contact forces follow the Kelvin-Voigt spring-damper model: F = -k·(p_probe - p_contact) - b·v_probe. The spring term resists penetration (stiffness); the damping term absorbs energy (stability). Together they produce forces that feel like touching a real surface — not a binary on/off contact, but a continuous resistance that increases with penetration depth.
Originally built in 2008 at Universidad de Concepción using C++/CLI with a physical PHANToM Omni providing 3-DOF force feedback. The modern version recreates the full simulation as a Python/FastAPI + Three.js WebGL application, with keyboard-driven probe interaction that works without physical hardware.
Stack Tecnológico
Capturas de la Aplicación
Diagramas Técnicos
haptic force model
haptic octree