×

Fast floating-point filters for robust predicates. (English) Zbl 1514.65056

Summary: Geometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geographic information systems and computer-aided design. With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail. This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations. The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this. We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions. We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed. We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations. Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations.

MSC:

65G50 Roundoff error
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

References:

[1] Alliez, P., Jamin, C., Rineau, L., Tayeb, S., Tournois, J., Yvinec, M.: 3D mesh generation. In: CGAL User and Reference Manual, 5.4 edn. CGAL Editorial Board (2022). https://doc.cgal.org/5.4/Manual/packages.html#PkgMesh3
[2] Attene, M., Indirect predicates for geometric constructions, Comput. Aided Des., 126 (2020) · doi:10.1016/j.cad.2020.102856
[3] Bartels, T., Fisikopoulos, V.: Fast robust arithmetics for geometric algorithms and applications to GIS. Int. Arch. Photogram. Remote Sens. Spatial Inf. Sci. XLVI-4/W2-2021, 1-8 (2021). doi:10.5194/isprs-archives-XLVI-4-W2-2021-1-2021
[4] Bartels, T., Fisikopoulos, V., Weiser, M.: Fast floating-point filters for robust predicates (2023). doi:10.5281/zenodo.7539355
[5] Berg, MD; Cheong, O.; Kreveld, MV; Overmars, M., Computational Geometry: Algorithms and Applications (2008), Santa Clara: Springer-Verlag TELOS, Santa Clara · Zbl 1140.68069 · doi:10.1007/978-3-540-77974-2
[6] Brönnimann, H., Burnikel, C., Pion, S.: Interval arithmetic yields efficient dynamic filters for computational geometry. In: Proc. of the 14th Annual Symposium on Computational Geometry, pp. 165-174. ACM, USA (1998). doi:10.1145/276884.276903 · Zbl 0967.68157
[7] Brönnimann, H., Fabri, A., Giezeman, G.J., Hert, S., Hoffmann, M., Kettner, L., Pion, S., Schirra, S.: 2D and 3D linear geometry kernel. In: CGAL User and Reference Manual, 5.2.1 edn. CGAL Editorial Board (2021). https://doc.cgal.org/5.2.1/Manual/packages.html#PkgKernel23
[8] Burnikel, C., Funke, S., Seel, M.: Exact geometric computation using cascading. Int. J. Comput. Geom. Appl. 11(03), 245-266 (2001). doi:10.1142/S0218195901000493 · Zbl 1074.65509
[9] de Matos Menezes, M., Magalhães, S.V.G., de Oliveira, M.A., Franklin, W.R., de Oliveira Bauer Chichorro, R.E.: Fast parallel evaluation of exact geometric predicates on GPUs (2021). Submitted
[10] Devillers, O., Fronville, A., Mourrain, B., Teillaud, M.: Algebraic methods and arithmetic filtering for exact predicates on circle arcs. In: Proc. of the 16th Annual Symposium on Computational Geometry, pp. 139-147. ACM, USA (2000). doi:10.1145/336154.336194 · Zbl 1374.68658
[11] Devillers, O., Pion, S.: Efficient exact geometric predicates for Delaunay triangulations. In: R.E. Ladner (ed.) Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, Baltimore, MD, USA, January 11, 2003, pp. 37-44. SIAM (2003)
[12] Dimov, P.: Boost C++ libraries: Mp11, version 1.76 (2021). https://boost.org/libs/mp11
[13] Fisikopoulos, V.; Peñaranda, L., Faster geometric algorithms via dynamic determinant computation, Comput. Geom., 54, 1-16 (2016) · Zbl 1338.65118 · doi:10.1016/j.comgeo.2015.12.001
[14] Gehrels, B., Lalande, B., Loskot, M., Wulkiewicz, A., Karavelas, M., Fisikopoulos, V.: Boost C++ libraries: Geometry, version 1.76 (2021). https://boost.org/libs/geometry
[15] Granlund, T.: The GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library, 5.0.5 edn. (2012). http://gmplib.org/
[16] Hauser, J.R.: Handling floating-point exceptions in numeric programs. ACM Trans. Program. Lang. Syst. 18(2), 139-174 (1996). doi:10.1145/227699.227701
[17] Hemmer, M., Hert, S., Pion, S., Schirra, S.: Number types. In: CGAL User and Reference Manual, 5.4 edn. CGAL Editorial Board (2022). https://doc.cgal.org/5.4/Manual/packages.html#PkgNumberTypes
[18] 754-2008 - IEEE standard for floating-point arithmetic. IEEE (2008). doi:10.1109/IEEESTD.2008.4610935
[19] Jamin, C., Alliez, P., Yvinec, M., Boissonnat, J.D.: Cgalmesh: a generic framework for Delaunay mesh generation. ACM Trans. Math. Softw. (2015). doi:10.1145/2699463 · Zbl 1347.65047
[20] Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., Yap, C.: Classroom examples of robustness problems in geometric computations. In: Algorithms - ESA 2004, pp. 702-713. Springer, Berlin (2004). doi:10.1007/978-3-540-30140-0_62 · Zbl 1111.68725
[21] Li, Z., Zhu, C., Gold, C.: Digital Terrain Modeling: Principles and Methodology. CRC Press (2005). doi:10.1201/9780203357132
[22] Loriot, S., Rouxel-Labbé, M., Tournois, J., Yaz, I.O.: Polygon mesh processing. In: CGAL User and Reference Manual, 5.4 edn. CGAL Editorial Board (2022). https://doc.cgal.org/5.4/Manual/packages.html#PkgPolygonMeshProcessing
[23] Maddock, J., Kormanyos, C.: Boost C++ libraries: Geometry, version 1.76 (2021). https://boost.org/libs/multiprecision
[24] Meyer, A., Pion, S.: FPG: a code generator for fast and certified geometric predicates. In: Real Numbers and Computers, pp. 47-60. Santiago de Compostela, Spain (2008). https://hal.inria.fr/inria-00344297
[25] Nanevski, A.; Blelloch, G.; Harper, R., Automatic generation of staged geometric predicates, Higher-Order Symb. Comput. LISP Symb. Comput., 16, 4, 379-400 (2003) · Zbl 1059.68147 · doi:10.1023/a:1025876920522
[26] Ozaki, K.; Bünger, F.; Ogita, T.; Oishi, S.; Rump, SM, Simple floating-point filters for the two-dimensional orientation problem, BIT Numer. Math., 56, 2, 729-749 (2016) · Zbl 1347.65050 · doi:10.1007/s10543-015-0574-9
[27] Qi, M.; Yan, K.; Zheng, Y., Gpredicates: Gpu implementation of robust and adaptive floating-point predicates for computational geometry, IEEE Access, 7, 60868-60876 (2019) · doi:10.1109/ACCESS.2019.2911641
[28] Rump, SM, Error estimation of floating-point summation and dot product, BIT Numer. Math., 52, 1, 201-220 (2011) · Zbl 1243.65047 · doi:10.1007/s10543-011-0342-4
[29] Shewchuk, J.: Routines for arbitrary precision floating-point arithmetic and fast robust geometric predicates (1996). https://cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c
[30] Shewchuk, J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput. Geometry 18(3), 305-363 (1997). doi:10.1007/pl00009321 · Zbl 0892.68098
[31] Shewchuk, J.R.: Tetrahedral mesh generation by Delaunay refinement. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, SCG’98, pp. 86-95. Association for Computing Machinery, New York (1998). doi:10.1145/276884.276894
[32] Sunday, D.: Practical Geometry Algorithms: with C++ Code. Amazon Digital Services LLC (2021). ISBN: 9798749449730
[33] Vassilev, V., Canal, P., Naumann, A., Moneta, L., Russo, P.: Cling—The New Interactive Interpreter for ROOT 6. p. 052071. IOP Publishing (2012). doi:10.1088/1742-6596/396/5/052071
[34] Veldhuizen, T., Expression templates, C++ Rep., 7, 5, 26-31 (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.