An hp-Adaptive Discretization Algorithm for Signed Distance Field Generation.

Area of Science:

• Computer Graphics
• Computational Geometry
• Numerical Analysis

Background:

• Signed Distance Fields (SDFs) are crucial for representing geometry in computer graphics and simulation.
• Existing methods for generating SDFs often face challenges with accuracy, memory efficiency, and handling complex geometries.

Purpose of the Study:

• To develop an hp-adaptive algorithm for generating discrete higher-order polynomial SDFs on hexahedral grids.
• To improve the accuracy and reduce the memory footprint of SDFs compared to prior techniques.
• To enable robust collision detection for complex solid objects in physically-based simulations.

Main Methods:

• Utilizing an orthonormal polynomial basis to fit SDFs on each grid cell.
• Implementing an error-driven, globally adaptive algorithm that combines spatial subdivision (h-refinement) and polynomial degree adaptation (p-refinement).
• Introducing a novel error-estimator to guide the choice between h- and p-refinement.
• Applying an optimization-based post-processing step to enforce weak continuity over cell interfaces.

Main Results:

• The hp-adaptive algorithm successfully generates accurate polynomial SDFs from manifold polygonal meshes.
• The method achieves significantly lower memory consumption compared to existing approaches.
• The generated SDFs demonstrate practical relevance when applied as collision detectors in physically-based simulations of complex objects.

Conclusions:

• The proposed hp-adaptive algorithm offers a superior approach for constructing high-accuracy, memory-efficient SDFs.
• The integration of h- and p-refinement, guided by an error-estimator, provides effective adaptive control.
• The method's successful application in collision detection highlights its potential for advanced geometric modeling and simulation.