Salles Viana Gomes Magalhães
ABSTRACT
This paper presents a proposal for the development of 3D-EPUG-Overlay, an efficient algorithm for exactly computing the intersection of 3D triangulations. 3D-EPUG-Overlay will be innovative because of two reasons. First, it will use arbitrary-precision rational numbers to represent and process spatial data, thereby completely avoiding round-off errors caused by floating-point numbers, what could create topological impossibilities. The use of rationals goes beyond merely using existing packages, which are inefficient when used in parallel on large problems. Second, for efficiency, 3D-EPUG-Overlay will use high performance computing and a uniform grid to index the data.
In order to validate these ideas, we developed and implemented EPUG-Overlay, a version of 3D-EPUG-Overlay for overlaying polygonal maps. EPUG-Overlay uses a two-level uniform grid for indexing the edges in the maps and high performance computing to accelerate the computations. Preliminary experiments showed that EPUG-Overlay was faster than GRASS GIS, even though GRASS uses inexact arithmetic. This suggests that the 3D version will also be efficient.
- E. S. Agency. Ariane 501 inquiry board report. http://ravel.esrin.esa.it/docs/esa-x-1819eng.pdf (accessed on Jun-2015).Google Scholar
- J.-D. Boissonnat and F. P. Preparata. Robust plane sweep for intersecting segments. SIAM J. Comput., 29(5):1401--1421, 2000. Google ScholarDigital Library
- L. Cucu, M. Dragan, V. Negru, and D. Mangu. Three dimensional Delaunay triangulation using an uniform grid. In 11th European Workshop Comput. Geom., pages 21--23. Universität Linz, 1995.Google Scholar
- H. Edelsbrunner and E. P. Mücke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM TOG, 9(1):66--104, 1990. Google ScholarDigital Library
- F. Feito, C. Ogayar, R. Segura, and M. Rivero. Fast and accurate evaluation of regularized boolean operations on triangulated solids. Computer-Aided Design, 45(3):705--716, 2013. Google ScholarDigital Library
- W. R. Franklin, N. Chandrasekhar, M. Kankanhalli, M. Seshan, and V. Akman. Efficiency of uniform grids for intersection detection on serial and parallel machines. In N. Magnenat-Thalmann and D. Thalmann, editors, Proc. Computer Graphics International'88, pages 288--297. Springer-Verlag, 1988.Google Scholar
- W. R. Franklin, V. Sivaswami, D. Sun, M. Kankanhalli, and C. Narayanaswami. Calculating the area of overlaid polygons without constructing the overlay. Cartography and Geographic Information Systems, 21(2):81--89, 1994.Google ScholarCross Ref
- W. R. Franklin, D. Sun, M.-C. Zhou, and P. Y. Wu. Uniform grids: A technique for intersection detection on serial and parallel machines. In Proc. of Auto Carto 9, pages 100--109, Baltimore, Maryland, April 1989.Google Scholar
- T. Granlund and the GMP development team. GNU MP: The GNU Multiple Precision Arithmetic Library, 6.0.0 edition, 2014. http://gmplib.org/ (accessed on Jun-2015).Google Scholar
- J. D. Hobby. Practical segment intersection with finite precision output. Comput. Geom., 13(4):199--214, 1999. Google ScholarDigital Library
- C. M. Hoffman. The problems of accuracy and robustness in geometric computation. Computer, 22(3):31--40, 1989. Google ScholarDigital Library
- L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, and C. Yap. Classroom examples of robustness problems in geometric computations. Comput. Geom. Theory Appl., 40(1):61--78, May 2008. Google ScholarDigital Library
- C. Li. Exact geometric computation: theory and applications,. PhD thesis, Department of Computer Science, Courant Institute - New York University, January 2001. Google ScholarDigital Library
- G. Mei and J. C. Tipper. Simple and robust boolean operations for triangulated surfaces. CoRR, abs/1308.4434, 2013.Google Scholar
- T. Möller. A fast triangle-triangle intersection test. Journal of graphics tools, 2(2):25--30, 1997. Google ScholarDigital Library
- J. Nievergelt and F. P. Preparata. Plane-sweep algorithms for intersecting geometric figures. Commun. ACM, 25(10):739--747, Oct. 1982. Google ScholarDigital Library
- R. Skeel. Roundoff error and the patriot missile. SIAM News, 25. Jul. 1992.Google Scholar
- J. Yongbin, W. Liguan, B. Lin, and C. Jianhong. Boolean operations on polygonal meshes using obb trees. In ESIAT 2009, volume 1, pages 619--622. IEEE, 2009. Google ScholarDigital Library
- S. Zlatanova, A. A. Rahman, and M. Pilouk. Trends in 3d gis development. Journal of Geospatial Engineering, 4(2):71--80, 2002.Google Scholar
Index Terms
- An efficient algorithm for computing the exact overlay of triangulations
Recommendations
Fast exact parallel map overlay using a two-level uniform grid
BigSpatial '15: Proceedings of the 4th International ACM SIGSPATIAL Workshop on Analytics for Big Geospatial DataWe present EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an algorithm to overlay two maps that is fast and parallel, has no roundoff errors, and is freely available. EPUG-Overlay combines several novel aspects. It represents coordinates with ...
Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD
We present an algorithm to compute the topology and geometry of an arbitrary number of polygon sets in the plane, also known as the map overlay. This algorithm can perform polygon clipping and related operations of interest in VLSI CAD. The algorithm ...
Comments