Exact and Efficient Polyhedral Envelope Containment Check

We introduce a new technique to check containment of a triangle within anenvelope built around a given triangle mesh. While existing methods conservativelycheck containment within a Euclidean envelope, our approachmakes use of a non-Euclidean envelope where containment can be checkedboth exactly and efficiently. Exactness is crucial to address major robustnessissues in existing geometry processing algorithms, which we demonstrateby integrating our technique in two surface triangle remeshing algorithmsand a volumetric tetrahedral meshing algorithm. We provide a quantitativecomparison of our method and alternative algorithms, showing that oursolution, in addition to being exact, is also more efficient. Indeed, whilecontainment within large envelopes can be checked in a comparable time,we show that our algorithm outperforms alternative methods when theenvelope becomes thin.