Exact and Efficient Polyhedral Envelope Containment Check

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.