“Exact and efficient polyhedral envelope containment check” by Wang, Schneider, Hu, Attene and Panozzo
Conference:
Type:
Title:
- Exact and efficient polyhedral envelope containment check
Session/Category Title: Shape Modeling
Presenter(s)/Author(s):
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.
References:
1. Mikhail J. Atallah. 1983. A Linear Time Algorithm for the Hausdorff Distance Between Convex Polygons. Inf. Process. Lett. 17 (1983), 207–209.Google ScholarCross Ref
2. Michael Barton, Iddo Hanniel, Gershon Elber, and Myung-Soo Kim. 2010. Precise Hausdorff distance computation between polygonal meshes. Computer Aided Geometric Design 27, 8 (2010), 580 — 591. Advances in Applied Geometry.Google ScholarDigital Library
3. Gilbert Bernstein and Don Fussell. 2009. Fast, Exact, Linear Booleans. In Proceedings of the Symposium on Geometry Processing (SGP ’09). Eurographics Association, Goslar, DEU, 1269–1278.Google Scholar
4. H. Borouchaki and P. J. Frey. 2005. Simplification of surface mesh using Hausdorff envelope.Google Scholar
5. Hervé Brönnimann, Christoph Burnikel, and Sylvain Pion. 1998. Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry. In Proceedings of the Fourteenth Annual Symposium on Computational Geometry (SCG ’98). ACM, New York, NY, USA, 165–174.Google ScholarDigital Library
6. Marcel Campen and Leif Kobbelt. 2010a. Exact and Robust (Self-)Intersections for Polygonal Meshes. Comput. Graph. Forum 29 (05 2010), 397–406.Google Scholar
7. Marcel Campen and Leif Kobbelt. 2010b. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. Computer Graphics Forum 29, 5 (2010), 1613–1622.Google ScholarCross Ref
8. Xiao-Xiang Cheng, Xiao-Ming Fu, Chi Zhang, and Shuangming Chai. 2019. Practical error-bounded remeshing by adaptive refinement. Computers & Graphics 82 (2019), 163 — 173.Google ScholarDigital Library
9. Paolo Cignoni, Claudio Rocchini, and Roberto Scopigno. 1996. Metro: Measuring Error on Simplified Surfaces. Technical Report. Paris, France, France.Google ScholarDigital Library
10. P. Cignoni, C. Rocchini, and R. Scopigno. 1998. Metro: measuring error on simplified surfaces. Computer Graphics Forum 17, 2 (1998), 167–174.Google Scholar
11. Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick Brooks, and William Wright. 1996. Simplification Envelopes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’96). Association for Computing Machinery, New York, NY, USA, 119–128.Google Scholar
12. Olivier Devillers and Sylvain Pion. 2003. Efficient exact geometric predicates for Delaunay triangulations. In Procs. of 5th Workshop Algorithm Eng. Exper. 37–44.Google Scholar
13. Steven Fortune and Christopher J. Van Wyk. 1996. Static Analysis Yields Efficient Exact Integer Arithmetic for Computational Geometry. ACM Trans. Graph. 15, 3 (July 1996), 223–248.Google ScholarDigital Library
14. Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, and Paul Zimmermann. 2007. MPFR: A Multiple-precision Binary Floating-point Library with Correct Rounding. ACM Trans. Math. Softw. 33, 2, Article 13 (June 2007).Google ScholarDigital Library
15. P. J. Frey and H. Borouchaki. 2003. Surface meshing using a geometric error estimate. Internat. J. Numer. Methods Engrg. 58, 2 (2003), 227–245.Google ScholarCross Ref
16. Xiao-Ming Fu, Yang Liu, John Snyder, and Baining Guo. 2014. Anisotropic Simplicial Meshing Using Local Convex Functions. IEEE Transactions on Visualization and Computer Graphics (June 2014), 95–106.Google Scholar
17. Michael Garland and Paul S. Heckbert. 1997. Surface Simplification Using Quadric Error Metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’97). ACM Press/Addison-Wesley Publishing Co., USA, 209–216.Google Scholar
18. Pijush K. Ghosh. 1993. A unified computational framework for Minkowski operations. Computers & Graphics 17, 4 (1993), 357 — 378.Google ScholarCross Ref
19. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3.Google Scholar
20. Peter Hachenberger. 2009. Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces. Algorithmica 55, 2 (01 Oct 2009), 329–345.Google Scholar
21. Michael Hemmer, Susan Hert, Sylvain Pion, and Stefan Schirra. 2019. Number Types. In CGAL User and Reference Manual (5.0 ed.). CGAL Editorial Board. https://doc.cgal.org/5.0/Manual/packages.html#PkgNumberTypesGoogle Scholar
22. Hugues Hoppe. 1996. Progressive Meshes. Association for Computing Machinery, Inc., 24.Google Scholar
23. K. Hu, D. Yan, D. Bommes, P. Alliez, and B. Benes. 2017. Error-Bounded and Feature Preserving Surface Remeshing with Minimal Angle Improvement. IEEE Transactions on Visualization and Computer Graphics 23, 12 (Dec 2017), 2560–2573.Google ScholarCross Ref
24. Yixin Hu, Teseo Schneider, Xifeng Gao, Qingnan Zhou, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2019. TriWild: Robust Triangulation with Curve Constraints. ACM Trans. Graph. 38, 4, Article 52 (July 2019), 15 pages.Google ScholarDigital Library
25. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast Tetrahedral Meshing in the Wild. ACM Trans. Graph. 39, 4 (July 2020).Google ScholarDigital Library
26. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (July 2018), 14 pages.Google ScholarDigital Library
27. Mioara Joldes, Olivier Marty, Jean-Michel Muller, and Valentina Popescu. 2016. Arithmetic Algorithms for Extended Precision Using Floating-Point Expansions. IEEE TRANSACTIONS ON COMPUTERS 65, 4 (April 2016), 1197–1210.Google ScholarDigital Library
28. Wonhyung Jung, Hayong Shin, and Byoung Kyu Choi. 2003. Self-intersection Removal in Triangular Mesh Offsetting.Google Scholar
29. Anil Kaul and Jarek Rossignac. 1992. Solid-interpolating deformations: Construction and animation of PIPs. Computers & Graphics 16, 1 (1992), 107 — 115.Google ScholarCross Ref
30. Bruno Lévy. 2019. Geogram. http://alice.loria.fr/index.php/software/4-library/75-geogram.html.Google Scholar
31. C. Li, S. Pion, and C.K. Yap. 2005. Recent progress in exact geometric computation. The Journal of Logic and Algebraic Programming 64, 1 (2005), 85 — 111. Practical development of exact real number computation.Google ScholarCross Ref
32. Manish Mandad, David Cohen-Steiner, and Pierre Alliez. 2015. Isotopic Approximation Within a Tolerance Volume. ACM Trans. Graph. 34, 4, Article 64 (July 2015), 12 pages.Google ScholarDigital Library
33. S. Loriot Martin Skrodzki. 2019. https://github.com/martinskrodzki/cgalGoogle Scholar
34. Andreas Meyer and Sylvain Pion. 2008. FPG: A code generator for fast and certified geometric predicates. In Real Numbers and Computers. 47–60.Google Scholar
35. Sylvain Pion and Andreas Fabri. 2011. A generic lazy evaluation scheme for exact geometric computations. Science of Computer Programming 76, 4 (2011), 307 — 323. Special issue on library-centric software design (LCSD 2006).Google ScholarDigital Library
36. Boris Schling. 2011. The Boost C++ Libraries. XML Press.Google ScholarDigital Library
37. Jonathan Richard Shewchuk. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (1997), 305–363.Google ScholarCross Ref
38. Hang Si and Jonathan Richard Shewchuk. 2014. Incrementally constructing and updating constrained Delaunay tetrahedralizations with finite-precision coordinates. Engineering with Computers 30, 2 (2014), 253–269.Google ScholarDigital Library
39. Min Tang, Minkyoung Lee, and Young J. Kim. 2009. Interactive Hausdorf Distance Computation for General Polygonal Models. In ACM SIGGRAPH 2009 Papers (SIGGRAPH ’09). ACM, New York, NY, USA, Article 74, 9 pages.Google Scholar
40. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10, 000 3D-Printing Models. CoRR abs/1605.04797 (2016). arXiv:1605.04797Google Scholar
