3D Haptic Simulation with Octree Collision Detection
A 3D simulation system recreating haptic interaction with virtual objects. Uses octree spatial partitioning (O(N log N)) and Separating Axis Theorem for collision detection with spring-damper Kelvin-Voigt force model.
Business Context
Haptic rendering requires collision detection at update rates exceeding 1 kHz — the human sense of touch perceives delays of just 1 millisecond. For 3D meshes with thousands of triangles, brute-force O(N²) collision testing is orders of magnitude too slow. And the force feedback must feel natural: not a binary on/off contact signal, but continuous resistance that increases with penetration depth and provides stability through energy dissipation.
Strategic Value
Two-phase collision detection achieves real-time haptic rates: octree spatial partitioning for O(N log N) broad phase, Separating Axis Theorem across 11 axes for mathematically exact narrow phase. Contact forces follow the Kelvin-Voigt spring-damper model F = -k·(p_probe - p_contact) - b·v_probe, producing physically plausible touch sensation. Originally built in 2008 at Universidad de Concepción with a physical PHANToM Omni providing 3-DOF force feedback; modernized as Python/FastAPI + Three.js WebGL with keyboard-driven probe interaction that works without physical hardware.
The Challenge
Real-time haptic rendering requires collision detection at >1 kHz update rates. Brute-force triangle-triangle testing is O(N²), far too slow for complex meshes. The force feedback must feel natural and physically plausible.
Our Approach
Two-phase collision: octree spatial partitioning for broad-phase O(N log N), SAT (Separating Axis Theorem) for narrow-phase triangle-triangle intersection across 11 axes. Contact forces follow Kelvin-Voigt spring-damper: F = -k·(p_probe - p_contact) - b·v_probe. Modern web version with Three.js WebGL rendering.
Key Performance Indicators
| KPI | Baseline | Result | Impact |
|---|---|---|---|
| Collision Efficiency | O(N²) brute force | O(N log N) octree + SAT | Real-time haptic rates |
| Force Model | Simple contact detection | Kelvin-Voigt spring-damper | Physically plausible feedback |
Architecture
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.
Technology Stack
Application Screenshots
Technical Diagrams
haptic force model
haptic octree