Exact and efficient polyhedral envelope containment check

Bolun Wang, Teseo Schneider, Yixin Hu, Marco Attene, Daniele Panozzo

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number3392426
JournalACM Transactions on Graphics
Volume39
Issue number4
DOIs
StatePublished - Jul 8 2020

Keywords

  • geometric predicates
  • robust geometric computation
  • shape proximity

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Exact and efficient polyhedral envelope containment check'. Together they form a unique fingerprint.

Cite this