💻 computer science

Temporally Coherent Hierarchical Distance Queries for Deformable Triangle Meshes

This paper presents a temporally coherent hierarchical method for signed-distance queries on deformable triangle meshes that selectively refreshes anisotropic bounds and reuses nearest-triangle seeds from previous frames to achieve up to 2.5x performance improvement while maintaining numerical accuracy.

Original authors: Jong-Hyun Kim

Published 2026-10-29

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jong-Hyun Kim

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital worlds of computer graphics and scientific simulation, objects are often built from vast collections of tiny triangles, forming a mesh that can bend, twist, and stretch to mimic real-world materials like cloth, skin, or water. To make these simulations feel real, computers must constantly answer a simple but demanding question: how far is a specific point in space from the surface of this moving object? This measurement, known as the signed distance, tells a program not only the distance to the surface but also whether that point is inside or outside the object. This information is the backbone of collision detection, ensuring virtual characters do not walk through walls, and of physical simulations, allowing fluids to flow around obstacles. However, as an object deforms, its surface changes shape every fraction of a second. Calculating the distance from scratch for every single point in a scene, frame after frame, is a massive computational burden that can slow down even the most powerful computers to a crawl.

Researchers at Inha University have developed a new method to solve this problem by teaching the computer to remember what it learned in the previous moment, rather than starting over every time. Instead of rebuilding the entire map of the object's shape at every instant, their system tracks how the object moves and stretches, updating only the parts of the map that have changed significantly. They found that by keeping a record of the closest surface feature from the last frame and using it as a starting guess for the current frame, the computer can skip huge amounts of unnecessary work. In their tests, this approach allowed the system to calculate distances roughly two and a half times faster than traditional methods, without sacrificing any accuracy. The result is a way to keep complex, moving 3D worlds running smoothly, making real-time simulations of deformable objects more efficient and responsive.

The core of this innovation lies in how the computer organizes the information about the object's surface. Imagine the space around a 3D object is divided into a grid of boxes, where each box holds a list of the triangles that might be closest to any point inside it. In a static world, this list never changes. But when the object moves, the triangles shift, and the old lists can become wrong or misleading. The traditional solution is to throw away the old lists and rebuild them from scratch for every new frame, a process that is slow and energy-intensive. The researchers realized that in most animations, the change from one moment to the next is small and smooth. Triangles do not teleport; they glide. Therefore, the list of nearby triangles from the previous frame is likely still very close to the truth for the current frame.

To exploit this smoothness, the team created a system that maintains a "temporal bound," a safety zone around each box that expands just enough to catch the triangles as they move. They did not simply make the boxes bigger in all directions, which would create a clumsy, oversized safety net. Instead, they stretched these safety zones only in the specific directions where the object was actually moving. If a part of the object stretched to the right, the safety zone expanded to the right but stayed tight in the up-down and front-back directions. This anisotropic, or directionally specific, expansion kept the safety zones tight and efficient. Furthermore, they added a smart filter: if a part of the object moved only a tiny amount, the system kept the old list of triangles and simply widened the safety zone slightly. It only rebuilt the list if the movement was large enough to break the old safety zone. This selective updating meant that for most of the object, the computer did not have to do the heavy lifting of rebuilding its internal map.

The second major trick involved the actual search for the distance. When the computer needs to know the distance to a point, it usually has to check many triangles to find the closest one. The researchers noticed that if they asked for the distance to a specific spot on the grid, the closest triangle was almost certainly the same one that was closest to that spot in the previous frame. They stored this "seed" triangle ID for small blocks of the grid. When a new query arrived, the system first checked this remembered triangle against the current shape of the object. This provided an immediate, very good estimate of the maximum possible distance. With this tight upper limit in hand, the computer could instantly ignore any other triangles that were clearly too far away, skipping them entirely. This process, combined with a streamlined way of navigating the grid that avoided complex memory stacks, allowed the system to prune away vast amounts of irrelevant data before it even began the detailed calculation.

The researchers tested their method on several complex 3D models, including a dragon, an armadillo, and a group of characters moving together. They compared their new system against a standard method that rebuilt the entire map at every step. The results showed that the new method produced distance values that were identical to the standard method, down to the smallest decimal places, proving that the shortcuts did not introduce errors. However, the speed difference was dramatic. On average, the new method completed the distance calculations in less than half the time, with speedups reaching up to 2.5 times faster in some scenes. The tests revealed that the system saved time primarily by visiting far fewer boxes in its internal map and checking far fewer triangles. In one set of tests, the number of triangles it needed to examine dropped to less than half of what the standard method required.

This efficiency came from a balance between remembering the past and checking the present. The system did not blindly trust the old data; it constantly verified that the remembered triangles were still valid for the current shape. If the object moved too much, the system refreshed its memory for that specific area. This adaptability meant the method worked well even when the object underwent large, complex deformations, such as the twisting of a dragon's body or the articulation of a character's limbs. The researchers also found that the method remained effective even when multiple objects were moving in the same scene, suggesting it could handle crowded, dynamic environments. The only time the method lost its advantage was when the object moved so violently or unpredictably that the previous frame's data became useless, but even then, the system remained accurate, simply falling back to a standard search.

The work demonstrates that in the realm of computer simulation, speed does not always require approximation. By carefully managing how information is reused and updated, it is possible to achieve exact results much faster. The method relies on the assumption that the object's topology, or the way its triangles are connected, remains fixed, which is true for most deformable simulations like cloth or soft bodies, but not for objects that tear or break apart. Within these limits, the approach offers a robust way to handle the continuous, fluid motion of 3D worlds. The researchers conclude that by combining these temporal memory techniques with modern graphics hardware, it is possible to make high-fidelity simulations of deformable objects practical for real-time applications, from video games to engineering analysis, where every millisecond of computation counts.

Technical Summary: Temporally Coherent Hierarchical Distance Queries for Deformable Triangle Meshes

1. Problem Statement

Computing signed distance functions (SDFs) for deformable triangle meshes is a fundamental operation in collision handling, physically based simulation, and geometric processing. While spatial acceleration structures like BVHs and octrees effectively reduce the cost of distance queries for static geometry, they face significant challenges in dynamic environments where vertex positions change continuously.

The core problem is the trade-off between update cost and query efficiency:

Full Reconstruction: Rebuilding the hierarchy or exactly refitting bounding volumes at every frame incurs substantial computational overhead.
Conservative Reuse: Simply reusing the previous frame's structure without updates leads to progressively loosening spatial bounds, increasing unnecessary traversal and query costs.
Existing Limitations: Previous methods like Triangle Influence Supersets (TIS) accelerate exact distance queries for static meshes by maintaining conservative candidate sets but do not inherently address the efficient maintenance of these hierarchies under continuous deformation.

The goal is to reduce the overall cost of hierarchy maintenance and distance queries for deformable meshes while preserving the exactness of the distance computation and the conservative candidate pruning properties of TIS.

2. Methodology

The proposed method extends the TIS framework by integrating temporal coherence into both hierarchy maintenance and query processing. The pipeline consists of five key components:

2.1 Initial Hierarchy Construction

The method begins by constructing a TIS-based octree hierarchy for the initial mesh $M_0$ . Unlike static applications where influence relations are permanent, this method treats the hierarchy topology and triangle ordering as fixed. The initial candidate sets are retained, but the validity of pruning is determined dynamically by effective temporal bounds that contain the current geometry, rather than by the initial influence relations alone.

2.2 Anisotropic Temporal Bounds

To handle deformation without global isotropic expansion, the method computes anisotropic temporal bounds for each hierarchy node.

For a node $R_j$ with a reference bound $B_j$ , the method calculates the axis-wise expansion $\delta^t_{j,a}$ required to contain the current geometry $bB^t_j$ .
The effective bound $eB^t_j$ is defined as $B_j$ expanded by $\delta^t_j$ along each axis independently.
This approach suppresses unnecessary bounding volume growth in axes where deformation is minimal, maintaining tighter bounds compared to global expansion.

2.3 Adaptive Hierarchy Refresh

To balance bound tightness with update cost, the method employs a selective refresh strategy.

The local expansion magnitude $\rho^t_j = \|\delta^t_j\|_\infty$ is compared against a threshold $\tau_r$ .
If $\rho^t_j \le \tau_r$ , the node retains its reference bound $B_j$ and applies only the temporal pad $\delta^t_j$ .
If $\rho^t_j > \tau_r$ , the reference bound is refreshed to the current exact bound $bB^t_j$ , and the pad is reset to zero.
This ensures that only nodes with significant local deformation undergo expensive bound updates, while others rely on the temporal padding.

2.4 Persistent Triangle Seeds

Temporal coherence is exploited during the query phase using persistent triangle seeds.

The SDF query grid is partitioned into $2 \times 2 \times 2$ voxel blocks.
For each block, the ID of the nearest triangle found in the previous frame is stored.
At the start of a new query, this seed triangle is re-evaluated against the current geometry to provide a tight initial upper bound ( $d^2_{best}$ ).
This allows the branch-and-bound traversal to prune large portions of the hierarchy early, even if the seed is no longer the exact nearest triangle.

2.5 Exact Stackless Traversal

The method performs stackless hierarchical traversal on the GPU.

Using precomputed "escape links" (which point to the next node to visit if a subtree is pruned), the algorithm avoids per-thread stack allocation.
Traversal proceeds in a conservative preorder, discarding subtrees where the lower bound distance exceeds the current best distance.
The final signed distance is computed using the exact current geometry and feature-consistent pseudonormals (angle-weighted for vertices, combined for edges) to ensure correct inside/outside classification.

3. Key Contributions

The paper identifies four primary contributions:

Anisotropic Temporal Bounds: A mechanism to track node deformation independently along each axis, reducing unnecessary hierarchy overlap caused by global isotropic expansion.
Selective Refresh Strategy: A method to preserve hierarchy tightness by updating reference bounds only when local deformation exceeds a prescribed threshold, preventing global bound inflation.
Persistent Triangle Seeds: A compact storage of nearest-triangle IDs from the previous frame, re-evaluated on current geometry to initialize queries with tight upper bounds.
Integrated Framework: The combination of these components with stackless traversal to perform exact signed-distance queries on deformable meshes efficiently on the GPU.

4. Experimental Results

The method was evaluated on various deformable models (Stanford Bunny, Dragon, Armadillo, Happy Buddha) and multi-object scenes using an NVIDIA GeForce GTX 1080 Ti.

Performance: The proposed method achieved a 2.43× average speedup in query performance compared to a full-refit baseline (ranging from 2.28× to 2.51× across scenes).
Workload Reduction: The average number of visited hierarchy nodes was reduced to 51% of the baseline, and exact point-triangle evaluations dropped to 43%.
Accuracy: The signed distance values agreed with the baseline exact query within numerical precision (mean errors around $10^{-7}$ ), confirming that temporal reuse does not compromise correctness.
Ablation Study: Removing any single component (anisotropic bounds, adaptive refresh, or persistent seeds) degraded performance, with the removal of persistent seeds causing the largest increase in query time (27.46 ms vs. 17.99 ms for the full method).
Refresh Ratio: On average, only 19.8% of nodes required reference bound updates per frame, demonstrating the effectiveness of the selective refresh strategy.

5. Significance and Claims

The paper claims that the proposed method effectively reduces the cost of repeated distance queries on dynamic geometry without sacrificing accuracy. Its significance lies in:

Preserving Exactness: Unlike neural implicit methods or approximate SDFs, this approach guarantees exact nearest-triangle queries and correct signed distances by relying on the current geometry for all final calculations.
Efficient Maintenance: It avoids the high cost of full hierarchy reconstruction or global bound inflation by leveraging temporal coherence through anisotropic bounds and selective updates.
GPU Suitability: The stackless traversal and contiguous memory layout are specifically optimized for GPU execution, reducing local-memory pressure and irregular memory access.
Applicability: The method is suitable for real-time graphics and simulation applications requiring repeated distance computations on deformable geometry with fixed topology.

The author notes that the method assumes fixed topology and temporally coherent query distributions. In scenarios with abrupt topology changes (fracture) or highly discontinuous motion, the performance benefits may diminish, though correctness is preserved. Future work is suggested to address topology changes via incremental reconstruction and to optimize maintenance costs via dirty-region updates.