Robust Line-Convex Polygon Intersection Computation in E2 using Projective Space Representation

• Autorzy: Skala Vaclav

Identyfikatory

DOI

10.22630/MGV.2023.32.3.1

• Języki publikacji: EN

Abstrakty

EN

This paper describes modified robust algorithms for a line clipping by a convex polygon in, E2 and a convex polyhedron in E3. The proposed algorithm is based on the Cyrus-Beck algorithm and uses homogeneous coordinates to increase the robustness of computation. The algorithm enables computation fully in the projective space using the homogeneous coordinates and the line can be given in the projective space, in general. If the result can remain in projective space, no division operation is needed. It supports the use of vector-vector operations, SSE/AVX instructions, and GPU.

Słowa kluczowe

EN

computer graphics; line convex polygon intersection; line convex polygon clipping; Cyrus-Beck algorithm; homogeneous coordinates; projective space; duality principle; vector-vector operations; GPU computing

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2023
• Tom: Vol. 32, No. 3/4
• Strony: 3--16
• Opis fizyczny: Bibliogr. 35 poz., rys.

Twórcy

autor

Skala Vaclav

• Dept. of Computer Science and Engineering, Faculty of Applied Sciences University of West Bohemia, Pilsen, Czech Republic

• https://orcid.org/0000-0001-8886-4281

Bibliografia

• [1] M. K. Agoston. Computer Graphics and Geometric Modelling: Implementation & Algorithms. Springer-Verlag, Berlin, Heidelberg, 2004. doi:10.1007/b138805.
• [2] M. K. Agoston. Computer Graphics and Geometric Modelling: Mathematics. Springer-Verlag, Berlin, Heidelberg, 2005. doi:10.1007/b138899.
• [3] A. Arokiasamy. Homogeneous coordinates and the principle of duality in two dimensional clipping. Computers and Graphics, 13(1):99-100, 1989. doi:10.1016/0097-8493(89)90045-9.
• [4] P. Comninos. Mathematical and Computer Programming Techniques for Computer Graphics. Springer-Verlag, Berlin, Heidelberg, 2005. doi:10.1007/978-1-84628-292-8.
• [5] M. Cyrus and J. Beck. Generalized two- and three-dimensional clipping. Computers and Graphics,3(1):23-28, 1978. doi:10.1016/0097-8493(78)90021-3.
• [6] R. S. Ferguson. Practical Algorithms for 3D Computer Graphics. A. K. Peters, Ltd., USA, 2nd edn., 2013. doi:10.1201/b16333.
• [7] J. D. Foley, A. van Dam, S. Feiner, and J. F. Hughes. Computer Graphics - Principles and Practice. Addison-Wesley, 2nd edn., 1990.
• [8] J. F. Hughes, A. van Dam, M. McGuire, D. F. Sklar, J. D. Foley, et al. Computer Graphics - Principles and Practice. Addison-Wesley, 3rd edn., 2014.
• [9] M. Johnson. Proof by duality: or the discovery of “new” theorems. Mathematics Today, December:138-153, 1996.
• [10] E. Lengyel. Mathematics for 3D Game Programming and Computer Graphics. Course Technology Press, Boston, MA, USA, 3rd edn., 2011.
• [11] N. Platis and T. Theoharis. Fast ray-tetrahedron intersection using Plücker coordinates. Journal of Graphics Tools, 8(4):37-48, 2003. doi:10.1080/10867651.2003.10487593.
• [12] D. Salomon. Computer Graphics and Geometric Modeling. Springer-Verlag, Berlin, Heidelberg, 1st edn., 1999.
• [13] D. Salomon. The Computer Graphics Manual. Springer, 2011. doi:10.1007/978-0-85729-886-7.
• [14] P. J. Schneider and D. H. Eberly. Geometric Tools for Computer Graphics. The Morgan Kaufmann Series in Computer Graphics. Morgan Kaufmann, San Francisco, 2003. doi:10.1016/B978-1-55860-594-7.50025-4.
• [15] P. Shirley and S. Marschner. Fundamentals of Computer Graphics. A. K. Peters, Ltd., USA, 3rd edn., 2009. doi:10.1201/9781439865521.
• [16] V. Skala. An efficient algorithm for line clipping by convex polygon. Computers and Graphics, 17(4):417-421, 1993. doi:10.1016/0097-8493(93)90030-D.
• [17] V. Skala. O(lg N) line clipping algorithm in E2. Computers and Graphics, 18(4):517-524, 1994. doi:10.1016/0097-8493(94)90064-7.
• [18] V. Skala. An efficient algorithm for line clipping by convex and non-convex polyhedra in E3. Computer Graphics Forum, 15(1):61-68, 1996. doi:10.1111/1467-8659.1510061.
• [19] V. Skala. A fast algorithm for line clipping by convex polyhedron in E3. Computers and Graphics (Pergamon), 21(2):209-214, 1997. doi:10.1016/s0097-8493(96)00084-2.
• [20] V. Skala. A new approach to line and line segment clipping in homogeneous coordinates. Visual Computer, 21(11):905-914, 2005. doi:10.1007/s00371-005-0305-3.
• [21] V. Skala. Duality and intersection computation in projective space with GPU support. In: Latest Trends on Applied Mathematics, Simulation, Modelling - Proc. 4th International Conference on Applied Mathematics, Simulation, Modelling (ASM’10), pp. 66-71. Corfu, Greece, 2010. http://hdl.handle.net/11025/11797.
• [22] V. Skala. Duality, barycentric coordinates and intersection computation in projective space with GPU support. WSEAS Transactions on Mathematics, 9(6):407-416, 2010. http://afrodita.zcu.cz/~skala/PUBL/PUBL_2010/2010_NAUN-journal.pdf.
• [23] V. Skala. Geometry, duality and robust computation in engineering. WSEAS Transactions on Computers, 11(9):275-293, 2012.
• [24] V. Skala. S-clip E2: A new concept of clipping algorithms. SIGGRAPH Asia Posters, SA, pp. 1-2, 2012. doi:10.1145/2407156.2407200.
• [25] V. Skala. Algorithms for line and plane intersection with a convex polyhedron with O(sqrt(N)) expected complexity in E3. In: SIGGRAPH Asia 2014 Posters, SA ’14. Association for Computing Machinery, New York, NY, USA, 2014. doi:10.1145/2668975.2668976.
• [26] V. Skala. Geometric transformations and duality for virtual reality and haptic systems. Communications in Computer and Information Science, 434 PART I:642-647, 2014. doi:10.1007/978-3-319-07857-1113.
• [27] V. Skala. Projective geometry, duality and plücker coordinates for geometric computations with determinants on GPUs. ICNAAM 2017, 1863, 2017. doi:10.1063/1.4992684.
• [28] V. Skala. Optimized line and line segment clipping in E2 and geometric algebra. Ann. Math. Inf., 52:199-215, 2020. doi:10.33039/ami.2020.05.001.
• [29] V. Skala. A new coding scheme for line segment clipping in E2. Lecture Notes in Computer Science, LNCS-accepted for publication ICCSA 2021:16-29, 2021. doi:10.1007/978-3-030-86976-2 2.
• [30] V. Skala. A novel line convex polygon clipping algorithm in E2 with parallel processing modification. Lecture Notes in Computer Science, LNCS 12953 ICCSA 2021:3-15, 2021. doi:10.1007/978-3-030-86976-21.
• [31] V. Skala. A brief survey of clipping and intersection algorithms with a list of references (including triangle-triangle intersections). Informatica (Lithuania), 34(1):169-198, 2023. doi:10.15388/23-INFOR508.
• [32] V. Skala, S. A. A. Karim, and E. A. Kadir. Scientific computing and computer graphics with GPU: Application of projective geometry and principle of duality. International Journal of Mathematics and Computer Science, 15(3):769-777, 2020. http://ijmcs.future-in-tech.net/15.3/R-Skala-AbdulKarim.pdf.
• [33] V. Skala and M. Kuchǎr. The hash function and the principle of duality. In: Proc. Computer Graphics International Conference (CGI’01), pp. 167-174. Hong Kong, China, 2001. doi:10.1109/CGI.2001.934671.
• [34] V. Skala and M. Smolik. A new formulation of Plücker coordinates using projective representation. In: Proc. 2018 5th International Conference on Mathematics and Computers in Sciences and Industry (MCSI 2018), pp. 52-56. Corfu, Greece, 2018. doi:10.1109/MCSI.2018.00020.
• [35] T. Theoharis, N. Platis, G. Papaioannou, and N. Patrikalakis. Graphics and Visualization: Principles & Algorithms (1st ed.). A K Peters/CRC Press, 2008. doi:10.1201/b10676.