Precise Hausdorff distance computation for freeform surfaces based on computations with osculating toroidal patches


Journal article


Sanghyun Son, Myung-Soo Kim, Gershon Elber
Computer Aided Geometric Design, 2021

Github
Cite

Cite

APA   Click to copy
Son, S., Kim, M.-S., & Elber, G. (2021). Precise Hausdorff distance computation for freeform surfaces based on computations with osculating toroidal patches. Computer Aided Geometric Design.


Chicago/Turabian   Click to copy
Son, Sanghyun, Myung-Soo Kim, and Gershon Elber. “Precise Hausdorff Distance Computation for Freeform Surfaces Based on Computations with Osculating Toroidal Patches.” Computer Aided Geometric Design (2021).


MLA   Click to copy
Son, Sanghyun, et al. “Precise Hausdorff Distance Computation for Freeform Surfaces Based on Computations with Osculating Toroidal Patches.” Computer Aided Geometric Design, 2021.


BibTeX   Click to copy

@article{son2021a,
  title = {Precise Hausdorff distance computation for freeform surfaces based on computations with osculating toroidal patches},
  year = {2021},
  journal = {Computer Aided Geometric Design},
  author = {Son, Sanghyun and Kim, Myung-Soo and Elber, Gershon}
}

Abstract

We present an efficient algorithm for computing the precise Hausdorff Distance (HD) between two freeform surfaces. The algorithm is based on a hybrid Bounding Volume Hierarchy (BVH), where osculating toroidal patches (stored in the leaf nodes) provide geometric properties essential for the HD computation in high precision. Intrinsic features from the osculating geometry resolve computational issues in handling the cross-boundary problem for composite surfaces, which leads to the acceleration of HD algorithm with a solution (within machine precision) to the exact HD. The HD computation for general freeform surfaces is discussed, where we focus on the computational issues in handling the local geometry across surface boundaries or around surface corners that appear as the result of gluing multiple patches together in the modeling of generic composite surfaces. We also discuss how to switch from an approximation stage to the final step of computing the precise HD using numerical improvements and confirming the correctness of the HD computation result. The main advantage of our algorithm is in the high precision of HD computation result. As the best cases of the proposed torus-based approach, we also consider the acceleration of HD computation for freeform surfaces of revolution and linear extrusion, where we can support real-time computation even for deformable surfaces. The acceleration is mainly due to a fast biarc approximation to the planar profile curves of the simple surfaces, each generated by rotating or translating a planar curve. We demonstrate the effectiveness of the proposed approach using experimental results.