Triangle Influence Supersets for Fast Distance Computation
No Thumbnail Available
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
© 2023 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd.
Abstract
We present an acceleration structure to efficiently query the Signed Distance Field (SDF) of volumes represented by triangle meshes. The method is based on a discretization of space. In each node, we store the triangles defining the SDF behaviour in that region. Consequently, we reduce the cost of the nearest triangle search, prioritizing query performance, while avoiding approximations of the field. We propose a method to conservatively compute the set of triangles influencing each node. Given a node, each triangle defines a region of space such that all points inside it are closer to a point in the node than the triangle is. This property is used to build the SDF acceleration structure. We do not need to explicitly compute these regions, which is crucial to the performance of our approach. We prove the correctness of the proposed method and compare it to similar approaches, confirming that our method produces faster query times than other exact methods.
Description
@article{10.1111:cgf.14861,
journal = {Computer Graphics Forum},
title = {{Triangle Influence Supersets for Fast Distance Computation}},
author = {Pujol, Eduard and Chica, Antonio},
year = {2023},
publisher = {© 2023 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.14861}
}