TY - JOUR
T1 - Exact and efficient polyhedral envelope containment check
AU - Wang, Bolun
AU - Schneider, Teseo
AU - Hu, Yixin
AU - Attene, Marco
AU - Panozzo, Daniele
N1 - Publisher Copyright:
© 2020 ACM.
PY - 2020/7/8
Y1 - 2020/7/8
N2 - We introduce a new technique to check containment of a triangle within an envelope built around a given triangle mesh. While existing methods conservatively check containment within a Euclidean envelope, our approach makes use of a non-Euclidean envelope where containment can be checked both exactly and efficiently. Exactness is crucial to address major robustness issues in existing geometry processing algorithms, which we demonstrate by integrating our technique in two surface triangle remeshing algorithms and a volumetric tetrahedral meshing algorithm. We provide a quantitative comparison of our method and alternative algorithms, showing that our solution, in addition to being exact, is also more efficient. Indeed, while containment within large envelopes can be checked in a comparable time, we show that our algorithm outperforms alternative methods when the envelope becomes thin.
AB - We introduce a new technique to check containment of a triangle within an envelope built around a given triangle mesh. While existing methods conservatively check containment within a Euclidean envelope, our approach makes use of a non-Euclidean envelope where containment can be checked both exactly and efficiently. Exactness is crucial to address major robustness issues in existing geometry processing algorithms, which we demonstrate by integrating our technique in two surface triangle remeshing algorithms and a volumetric tetrahedral meshing algorithm. We provide a quantitative comparison of our method and alternative algorithms, showing that our solution, in addition to being exact, is also more efficient. Indeed, while containment within large envelopes can be checked in a comparable time, we show that our algorithm outperforms alternative methods when the envelope becomes thin.
KW - geometric predicates
KW - robust geometric computation
KW - shape proximity
UR - http://www.scopus.com/inward/record.url?scp=85090380243&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090380243&partnerID=8YFLogxK
U2 - 10.1145/3386569.3392426
DO - 10.1145/3386569.3392426
M3 - Article
AN - SCOPUS:85090380243
SN - 0730-0301
VL - 39
JO - ACM Transactions on Graphics
JF - ACM Transactions on Graphics
IS - 4
M1 - 3392426
ER -