A Brief Survey of Clipping and Intersection Algorithms with a List of References (including Triangle-Triangle Intersections)

Skala, Vaclav

doi:10.15388/23-INFOR508

Informatica

A Brief Survey of Clipping and Intersection Algorithms with a List of References (including Triangle-Triangle Intersections)^✩

Volume 34, Issue 1 (2023), pp. 169–198

Vaclav Skala

https://doi.org/10.15388/23-INFOR508

Pub. online: 27 January 2023 Type: Research Article

Open Access

^✩ The research was supported by the University of West Bohemia – Institutional research support.

Received
1 June 2022

Accepted
1 January 2023

Published
27 January 2023

Abstract

This contribution presents a brief survey of clipping and intersection algorithms in ${E^{2}}$ and ${E^{3}}$ with a nearly complete list of relevant references. Some algorithms use the projective extension of the Euclidean space and vector-vector operations, which support GPU and SSE use.

This survey is intended to help researchers, students, and practitioners dealing with intersection and clipping algorithms.

References

Agoston, M.K. (2004). Computer Graphics and Geometric Modelling: Implementation & Algorithms. Springer-Verlag, Berlin, Heidelberg. 1852338180.

Agoston, M.K. (2005). Computer Graphics and Geometric Modelling: Mathematics. Springer-Verlag, Berlin, Heidelberg. 1852338172.

Akenine-Moller, T., Haines, E., Hoffman, N. (2008). Real-Time Rendering, 3rd ed. A. K. Peters, Ltd., USA. 1568814240.

Amanatides, J., Choi, K.Y. (1995). Ray Tracing Triangular Meshes. http://www.cs.yorku.ca/~amana/research/mesh.pdf.

Ammeraal, L., Zhang, K. (2017). Computer Graphics for Java Programmers. Springer Cham. 978-3-319-63356-5 https://doi.org/10.1007/978-3-319-63357-2.

Andreev, R., Sofianska, E. (1991). New algorithm for two-dimensional line clipping. Computers and Graphics, 15(4), 519–526. https://doi.org/10.1016/0097-8493(91)90051-I.

Angel, E., Shreiner, D. (2011). Interactive Computer Graphics: A Top-Down Approach with Shader-Based OpenGL, 6th ed. Addison-Wesley Publishing Company, USA. 0132545233.

Arokiasamy, A. (1989). Homogeneous coordinates and the principle of duality in two dimensional clipping. Computers and Graphics, 13(1), 99–100. https://doi.org/10.1016/0097-8493(89)90045-9.

Arvo, J. (1991). Graphics Gems II. Academic Press Professional, Inc., USA. 0120644800.

Bao, H., Peng, Q. (1996). Efficient polygon clipping algorithm. Zidonghua Xuebao/Acta Automatica Sinica, 22(6), 741–744.

Bhuiyan, M.I. (2009). Designing a line-clipping algorithm by categorizing line dynamically and using intersection point method. In: 2009 International Conference on Electronic Computer Technology, Macau, China, pp. 22–25. https://doi.org/10.1109/ICECT.2009.79.

Blinn, J.F. (1977). A homogeneous formulation for lines in 3 space. ACM SIGGRAPH Computer Graphics, 11(2), 237–241. https://doi.org/10.1145/965141.563900.

Blinn, J.F. (1991). A trip down the graphics pipeline: line clipping. IEEE Computer Graphics and Applications, 11(1), 98–105. https://doi.org/10.1109/38.67707.

Blinn, J.F., Newell, M.E. (1978). Clipping using homogeneous coordinates. In: Proceedings of the 5th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1978, pp. 245–251. https://doi.org/10.1145/800248.807398.

Brackenbury, I.F. (1984). Line clipping in interactive computer graphics. IBM Technical Disclosure Bulletin, 27(1B), 549–552.

Bui, D.H. (1999). Algorithms for Line Clipping and Their Complexity (supervisor: V. Skala). PhD thesis, University of West Bohemia, Pilsen. http://graphics.zcu.cz/files/DIS_1999_Bui_Duc_Huy.pdf.

Bui, D.H., Skala, V. (1998). Fast algorithms for clipping lines and line segments in E2. Visual Computer, 14(1), 31–37. https://doi.org/10.1007/s003710050121.

Cai, M., Yuan, C.-F., Song, J.-Q., Cai, S.-J. (2001). A fast line clipping algorithm for circular windows. Journal of Computer-Aided Design and Computer Graphics, 13(12), 1063–1067. https://doi.org/10.5121/ijcga.2018.8201.

Calvet, R.G. (2007). Treatise of Plane Geometry Through Geometric Algebra. Cerdanyola del Valles, Spain. 978-84-611-9149-9. http://www.xtec.cat/~rgonzal1/treatise-sample.pdf.

Chang, J.-W., Kim, M.-S. (2009). Technical section: efficient triangle-triangle intersection test for OBB-based collision detection. Computers & Graphics, 33(3), 235–240. https://doi.org/10.1016/j.cag.2009.03.009.

Chao, C., Zhaoyin, Z., Changsong, S. (2009). A midpoint segmentation clipping algorithm of circular window against line. In: 2009 International Forum on Computer Science-Technology and Applications, Chongqing, China, pp. 15–19. https://doi.org/10.1109/IFCSTA.2009.10.

Cheng, F., Yen, Y.-k. (1989). A parallel line clipping algorithm and its implementation. In: Dew, P.M., Heywood, T.R., Earnshaw, R.A. (Eds.), Parallel Processing for Computer Vision and Display. Addison-Wesley, USA, pp. 338–350. 978-0201416053.

Cohen, D. (1969). Incremental Methods for Computer Graphics. Technical report, Harvard University, Cambridge, Massachusetts, USA. https://apps.dtic.mil/sti/pdfs/AD0694550.pdf.

Comninos, P. (2005). Mathematical and Computer Programming Techniques for Computer Graphics. Springer-Verlag, Berlin, Heidelberg. 1852339020. https://doi.org/10.1007/978-1-84628-292-8.

Comninos, P. (2006). Two-dimensional clipping. In: Mathematical and Computer Programming Techniques for Computer Graphics. Springer, London. https://doi.org/10.1007/978-1-84628-292-8_6.

Coxeter, H.S.M., Beck, G. (1992). The Real Projective Plane. Springer-Verlag, Berlin, Heidelberg. 0387978895.

Cychosz, J.M. (1991). Intersecting a ray with an elliptical torus. In: Graphics Gems II. Morgan Kaufmann, pp. 251–256. 9780080507545. https://doi.org/10.1016/B978-0-08-050754-5.50054-2.

Cyrus, M., Beck, J. (1978). Generalized two- and three-dimensional clipping. Computers and Graphics, 3(1), 23–28. https://doi.org/10.1016/0097-8493(78)90021-3.

Danaei, B., Karbasizadeh, N., Tale Masouleh, M. (2017). A general approach on collision-free workspace determination via triangle-to-triangle intersection test. Robotics and Computer-Integrated Manufacturing, 44, 230–241. https://doi.org/10.1016/j.rcim.2016.08.013.

Dawod, A.I. (2011). Hardware implementation of line clipping algorithm by using FPGA. Tikrit Journal of Engineering Science, 18, 89–105.

Day, J.D. (1992a). An algorithm for clipping lines in object and image space. Computers and Graphics, 16(4), 421–426. https://doi.org/10.1016/0097-8493(92)90029-U.

Day, J.D. (1992b). A new two dimensional line clipping algorithm for small windows. Computer Graphics Forum, 11(4), 241–245. https://doi.org/10.1111/1467-8659.1140241.

de Magalhães, S.V.G., Franklin, W.R., Andrade, M.V.A. (2020). An efficient and exact parallel algorithm for intersecting large 3-D triangular meshes using arithmetic filters. Computer-Aided Design, 120, 102801. https://doi.org/10.1016/j.cad.2019.102801. https://www.sciencedirect.com/science/article/pii/S0010448519305330.

Deng, W., Lu, G., Chen, L. (2006). New 3D line clipping algorithm against spherical surface window. In: International Technology and Innovation Conference 2006 (ITIC 2006). IET, USA, pp. 894–898. 0-86341-696-9. https://doi.org/10.1049/cp:20060886.

Dev, D., Saharan, P. (2019). Implementation of efficient line clipping algorithm. International Journal of Innovative Technology and Exploring Engineering, 8(7), 295–298.

Devai, F. (1998). An analysis technique and an algorithm for line clipping. In: Proceedings. 1998 IEEE Conference on Information Visualization. An International Conference on Computer Visualization and Graphics, London, UK, 1998, pp. 157–165. https://doi.org/10.1109/IV.1998.694214.

Devai, F. (2005). Analysis of the Nicholl-Lee-Nicholl algorithm. In: Computational Science and Its Applications– ICCSA 2005, Lecture Notes in Computer Science, Vol. 3480. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11424758_75.

Devai, F. (2006). A speculative approach to clipping line segments. In: Computational Science and Its Applications – ICCSA 2006, Lecture Notes in Computer Science, Vol. 3980. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11751540_15.

Devillers, O., Guigue, P. (2002). Faster Triangle-Triangle Intersection Tests. Technical Report RR-4488, INRIA. https://hal.inria.fr/inria-00072100.

Dimri, S.C. (2015). Article: a simple and efficient algorithm for line and polygon clipping in 2-D computer graphics. International Journal of Computers and Applications, 127(3), 31–34. https://doi.org/10.5120/ijca2015906352.

Dimri, S.C., Tiwari, U.K., Ram, M. (2022). An efficient algorithm to clip a 2D-polygon against a rectangular clip window. Applied Mathematics-A Journal of Chinese Universities, 37, 147–158. https://doi.org/10.1007/s11766-022-4556-0.

Dorst, L., Fontijne, D., Mann, S. (2009). Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 9780080553108. https://doi.org/10.1016/B978-0-12-374942-0.X0000-0.

Duvalenko, V.J., Robbins, W.E., Gyurcsik, R.S. (1990). Improving line segment clipping. Dr Dobb’s Journal, 15(7), 36.

Duvanenko, V.J., Gyurcsik, R.S., Robbins, W.E. (1993). Simple and efficient 2D and 3D span clipping algorithms. Computers and Graphics, 17(1), 39–54. https://doi.org/10.1016/0097-8493(93)90050-J.

Duvanenko, V.J., Robbins, W.E., Gyurcsik, R.S. (1996). Line-segment clipping revisited. Dr Dobb’s Journal, 21(1), 107.

Dörr, M. (1990). A new approach to parametric line clipping. Computer Graphics (Pergamon), 14(3–4), 449–464. https://doi.org/10.1016/0097-8493(90)90067-8.

Eberly, D.H. (2003). Game Physics. Elsevier Science Inc., USA. 1558607404.

Eisemann, M., Magnor, M., Grosch, T., Müller, S. (2007). Fast ray/axis-aligned bounding box overlap tests using ray slopes. Journal of Graphics Tools, 12(4), 35–46. https://doi.org/10.1080/2151237X.2007.10129248.

Elliriki, M., Reddy, C., Anand, K. (2019). An efficient line clipping algorithm in 2D space. International Arab Journal of Information Technology, 16(5), 798–807. https://iajit.org/PDF/September%202019,%20No.%205/11103.pdf.

Elsheikh, A.H., Elsheikh, M. (2014). A reliable triangular mesh intersection algorithm and its application in geological modelling. Engineering with Computers, 30(1), 143–157. https://doi.org/10.1007/s00366-012-0297-3.

Evangeline, D., Anitha, S. (2014). 2D polygon clipping using shear transformation: an extension of shear based 2D line clipping. In: 2014 IEEE IEEE International Conference on Advanced Communications, Control and Computing Technologies, pp. 1379–1383. https://doi.org/10.1109/ICACCCT.2014.7019326.

Ferguson, R.S. (2013). Practical Algorithms for 3D Computer Graphics, 2nd ed. A. K. Peters, Ltd., USA. 1466582529.

Foley, J.D., van Dam, A., Feiner, S., Hughes, J.F. (1990). Computer Graphics – Principles and Practice, 2nd ed. Addison-Wesley, USA. 978-0-201-12110-0.

Foster, E.L., Hormann, K., Popa, R.T. (2019). Clipping simple polygons with degenerate intersections. Computers & Graphics: X, 2, 100007. https://doi.org/10.1016/j.cagx.2019.100007.

Glassner, A.S. (Ed.) (1990). Graphics Gems. Academic Press Professional, Inc., USA. http://inis.jinr.ru/sl/vol1/CMC/Graphics_Gems_1,ed_A.Glassner.pdf. 0122861695.

Govil-Pai, S. (2005). Principles of Computer Graphics: Theory and Practice Using OpenGL and Maya. Springer-Verlag, Berlin, Heidelberg. 0387955046.

Greiner, G., Hormann, K. (1998). Efficient clipping of arbitrary polygons. ACM Transactions on Graphics, 17(2), 71–83. https://doi.org/10.1145/274363.274364.

Guigue, P., Devillers, O. (2003). Fast and robust triangle-triangle overlap test using orientation predicates. Journal of Graphics Tools, 8(1), 25–32. https://doi.org/10.1080/10867651.2003.10487580.

Guo, H. (2014). Modern Mathematics and Applications in Computer Graphics and Vision. World Scientific Publ., Singapore. 978-9814449328. https://doi.org/0.1142/8703.

Gupta, R., Tripathi, V.K., Singh, K., Pathak, N.K., Rastogi, R. (2016). An innovative and easy approach for clipping curves along a circular window. In: 2016 Second International Conference on Computational Intelligence & Communication Technology (CICT), Ghaziabad, India, 2016, pp. 638–643. https://doi.org/10.1109/CICT.2016.132.

Harrington, S. (1987). Computer Graphics: A Programming Approach, 2nd ed. McGraw-Hill, Inc., USA. 0070267537.

Hattab, A.S.A., Yusof, Y. (2014). Line clipping based on parallelism approach and midpoint intersection. AIP Conference Proceedings, 1602, 371–374. 9780735412361. https://doi.org/10.1063/1.4882513.

Havel, J., Herout, A. (2010). Yet faster ray-triangle intersection (using SSE4). IEEE Transactions on Visualization and Computer Graphics, 16(3), 434–438. https://doi.org/10.1109/TVCG.2009.73.

Hearn, D.D., Baker, M.P., Carithers, W. (2010). Computer Graphics with OpenGL, 4th ed. Prentice Hall Press, USA. 0136053580.

Heckbert, P.S. (Ed.) (1994). Graphics Gems IV. Academic Press Professional, Inc., USA. 0123361559.

Held, M. (1998). ERIT: a collection of efficient and reliable intersection tests. Journal of Graphics Tools, 2(4), 25–44. https://doi.org/10.1080/10867651.1997.10487482.

Hildenbrand, D. (2012). Foundations of Geometric Algebra Computing. Springer Publishing Company, Inc., London. 3642317936. https://doi.org/10.1007/978-1-84628-997-2.

Hill, F.S., Kelley, S.M. (2006). Computer Graphics Using OpenGL, 3rd ed. Prentice-Hall, Inc., USA. 0131496700.

Huang, W. (2013). Line clipping algorithm of affine transformation for polygon. In: Intelligent Computing Theories, ICIC 2013, Lecture Notes in Computer Science, Vol. 7995. Springer, Berlin, Heidelberg, pp. 55–60. https://doi.org/10.1007/978-3-642-39479-9_7.

Huang, W., Wangyong (2009). A novel algorithm for line clipping. In: Proceedings – 2009 International Conference on Computational Intelligence and Software Engineering, CiSE 2009, pp. 1–5. https://doi.org/10.1109/CISE.2009.5366550.

Huang, Y.Q., Liu, Y.K. (2002). An algorithm for line clipping against a polygon based on shearing transformation. Computer Graphics Forum, 21(4), 683–688. https://doi.org/10.1111/1467-8659.00626.

Hughes, J.F., van Dam, A., McGuire, M., Sklar, D.F., Foley, J.D., Feiner, S.K., Akeley, K. (2014). Computer Graphics – Principles and Practice, 3rd ed. Addison-Wesley, USA. 978-0-321-39952-6.

Iraji, M.S., Mazandarani, A., Motameni, H. (2011). An efficient line clipping algorithm based on Cohen-Sutherland line clipping algorithm. American Journal of Scientific Research, 14(1), 65–71. https://www.researchgate.net/publication/275964580_An_Efficient_Line_Clipping_Algorithm_based_on_Cohen-Sutherland_Line_Clipping_Algorithm.

Jiang, B., Han, J. (2013). Improvement in the Cohen-Sutherland line segment clipping algorithm. In: 2013 IEEE International Conference on Granular Computing (GrC), Beijing, China, 2013, pp. 157–161. https://doi.org/10.1109/GrC.2013.6740399.

Jianrong, T. (2006). A new algorithm of polygon clipping against rectangular window based on the endpoint and intersection-point encoding. Journal of Engineering Graphics.

Johnson, M. (1996). Proof by duality: or the discovery of “New” theorems. Mathematics Today, December, 138–153.

Jokanovic, S. (2019). Two-dimensional line segment–triangle intersection test: revision and enhancement. Visual Computer, 35(10), 1347–1359. https://doi.org/10.1007/s00371-018-01614-1.

Kaijian, S., Edwards, J.A., Cooper, D.C. (1990). An efficient line clipping algorithm. Computers and Graphics, 14(2), 297–301. https://doi.org/10.1016/0097-8493(90)90041-U.

Kanatani, K. (2015). Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for Computer Vision and Graphics. A. K. Peters, Ltd., USA. 1482259508. https://doi.org/10.1201/b18273.

Kirk, D. (Ed.) (1992). Graphics Gems III. Academic Press Professional, Inc., USA. 0124096719.

Kodituwakku, R., Wijeweera, K.R. (2012). An efficient line clipping algorithm for 3D space. International Journal of Advanced Research in Computer Science and Software Engineering, 2(5).

Kodituwakku, S.R., Wijeweera, K.R., Chamikara, M.A.P. (2013). An efficient algorithm for line clipping in computer graphics programming. Ceylon Journal of Science, 17(1), 1–7. https://www.researchgate.net/publication/261288113_An_Efficient_Algorithm_for_Line_Clipping_in_Computer_Graphics_Programming.

Kolingerová, I. (1994). 3D-line clipping algorithms – a comparative study. The Visual Computer, 11(2), 96–104. https://doi.org/10.1007/BF01889980.

Kolingerová, I. (1997). Convex polyhedron-line intersection detection using dual representation. Visual Computer, 13(1), 42–49. https://doi.org/10.1007/s003710050088.

Konashkova, A.M. (2014). Line – convex polyhedron intersection using vertex connections table. Applied Mathematical Sciences, 8(21–24), 1177–1186. https://doi.org/10.12988/ams.2014.4133.

Konashkova, A.M. (2015). Modified Skala’s plane tested algorithm for line-polyhedron intersection. Applied Mathematical Sciences, 9(61–64), 3097–3103. https://doi.org/10.12988/ams.2015.52169.

Kong, D.H., Yin, B.C. (2001). The improvement on the algorithm of Cohen-Surtherland line clipping. CAD/GRAPHICS 2001, 807–810. 7-5062-5137-X.

Krammer, G. (1992). A line clipping algorithm and its analysis. Computer Graphics Forum, 11(3), 253–266. https://doi.org/10.1111/1467-8659.1130253.

Kui Liu, Y., Qiang Wang, X., Zhe Bao, S., Gomboši, M., Žalik, B. (2007). An algorithm for polygon clipping, and for determining polygon intersections and unions. Computers and Geosciences, 33(5), 589–598. https://doi.org/10.1016/j.cageo.2006.08.008.

Kumar, J., Awasthi, A. (2011). Modified trivial rejection criteria in Cohen-Sutherland line clipping algorithm. In: Advances in Computing, Communication and Control. ICAC3 2011, Communications in Computer and Information Science, Vol. 125. Springer, Berlin, Heidelberg, pp. 1–10. https://doi.org/10.1007/978-3-642-18440-6_1.

Kumar, P., Patel, F., Kanna, R. (2018). An efficient line clipping algorithm for circular windows using vector calculus and parallelization. International Journal of Computational Geometry and Applications, 8(1/2), 01–08. https://doi.org/10.5121/IJCGA.2018.8201.

Kuzmin, Y.P. (1995). Bresenham’s line generation algorithm with built-in clipping. Computer Graphics Forum, 14(5), 275–280. https://doi.org/10.1111/1467-8659.1450275.

Lagae, A., Dutré, P. (2005). An efficient ray-quadrilateral intersection test. Journal of Graphics Tools, 10(4), 23–32. https://doi.org/10.1080/2151237X.2005.10129208.

Landier, S. (2017). Boolean operations on arbitrary polygonal and polyhedral meshes. CAD Computer Aided Design, 85, 138–153. https://doi.org/10.1016/j.cad.2016.07.013.

Lengyel, E. (2011). Mathematics for 3D Game Programming and Computer Graphics, 3rd ed. Course Technology Press, Boston, MA, USA. 1435458869.

Li, H. (2016). Analysis and Implementation of Cohen_Sutherland Line Clipping Algorithm. In: Proceedings of the 2016 International Conference on Sensor Network and Computer Engineering. Atlantis Press, China, pp. 482–485. 978-94-6252-217-6. https://doi.org/10.2991/icsnce-16.2016.94.

Li, W. (2005). Bisearch-based line clipping algorithm against a convex polygonal window. Journal of Computer-Aided Design and Computer Graphics, 17(5), 962–965.

Li, Z., Lei, G. (2012). Modified Sutherland-Cohen line clipping algorithm (in Chinese). Computer Engineering and Applications, 48(34), 175. https://caod.oriprobe.com/articles/31582699/Modified_Sutherland_Cohen_line_clipping_algorithm.htm.

Li, Z.-Q., He, Y., Tian, Z.-J. (2012). Overlapping area computation between irregular polygons for its evolutionary layout based on convex decomposition. Journal of Software, 7(2), 485–492. https://doi.org/10.4304/jsw.7.2.485-492.

Li, Z., He, D., Wang, J., Wang, M. (2014). An improved algorithm of Cohen-Sutherland line clipping. WIT Transactions on Information and Communication Technologies, 49, 575–582. 9781845648558.

Liang, Y.-D., Barsky, B.A. (1983). An analysis and algorithm for polygon clipping. Communications of the ACM, 26(11), 868–877. https://doi.org/10.1145/182.358439.

Liang, Y.D., Barsky, B.A. (1984). A new concept and method for line clipping. ACM Transactions on Graphics (TOG), 3(1), 1–22. https://doi.org/10.1145/357332.357333.

Llanas, B., Sainz, F.J. (2012). A local search algorithm for ray-convex polyhedron intersection. Computational Optimization and Applications, 51(2), 533–550. https://doi.org/10.1007/s10589-010-9354-2.

Lo, S., Wang, W. (2004). A fast robust algorithm for the intersection of triangulated surfaces. Engineering with Computers, 20, 11–21. https://doi.org/10.1007/s00366-004-0277-3.

Lu, G., Wu, X. (2002). Midpoint-subdivision line clipping algorithm based on filtering technique. Journal of Computer-Aided Design and Computer Graphics, 14(6), 513–517.

Lu, G., Wu, X., Peng, Q. (2002a). An efficient line clipping algorithm based on adaptive line rejection. Computers and Graphics (Pergamon), 26(3), 409–415. https://doi.org/10.1016/S0097-8493(02)00084-5.

Lu, G., Xing, J., Tan, J. (2002b). New clipping algorithm of line against circular window with multi-encoding approach. Journal of Computer-Aided Design and Computer Graphics, 14(12), 1133–1137.

Mahovsky, J., Wyvill, B. (2004). Fast ray-axis aligned bounding box overlap tests with plucker coordinates. Journal of Graphics Tools, 9(1), 35–46. https://doi.org/10.1080/10867651.2004.10487597.

Maillot, P.-G. (1991). Three-dimensional homogeneous clipping of triangle strips. In: Graphics Gems II. Elsevier Inc., USA, pp. 219–231. 9780080507545. https://doi.org/10.1016/B978-0-08-050754-5.50050-5.

Maillot, P.-G. (1992). A new, fast method for 2D polygon clipping: analysis and software implementation. ACM Transactions on Graphics (TOG), 11(3), 276–290. https://doi.org/10.1145/130881.130894.

Maonica, B., Das, P., Ramteke, P.B., Koolagudi, S.G. (2017). Selective cropper for geometrical objects in OpenFlipper. In: Satapathy, S.C., Bhateja, V., Joshi, A. (Eds.), Proceedings of the International Conference on Data Engineering and Communication Technology. Springer, Singapore, pp. 391–399. 978-981-10-1675-2. https://doi.org/10.1007/978-981-10-1675-2_39.

Marschner, S., Shirley, P. (2016). Fundamentals of Computer Graphics, 4th ed. A. K. Peters, Ltd., USA. 1482229390.

Martinez, F., Rueda, A.J., Feito, F.R. (2009). A new algorithm for computing Boolean operations on polygons. Computers and Geosciences, 35(6), 1177–1185. https://doi.org/10.1016/j.cageo.2008.08.009.

Matthes, D., Drakopoulos, V. (2019a). Another simple but faster method for 2D line clipping. International Journal of Computer Graphics & Animation (IJCGA), 9(1–3). https://doi.org/10.5121/ijcga.2019.9301. https://aircconline.com/ijcga/V9N3/9319ijcga01.pdf.

Matthes, D., Drakopoulos, V. (2019b). A simple and fast line-clipping method as a scratch extension for computer graphics education. Computer Science and Information Technology, 7, 40–47. https://doi.org/10.13189/csit.2019.070202.

Matthes, D., Drakopoulos, V. (2022). Line clipping in 2D: overview, techniques and algorithms. Journal of Imaging, 8(10). https://doi.org/10.3390/jimaging8100286. https://www.mdpi.com/2313-433X/8/10/286.

Mccoid, C., Gander, M.J. (2022). A provably robust algorithm for triangle-triangle intersections in floating-point arithmetic. ACM Transactions on Mathematical Software, 48(2). https://doi.org/10.1145/3513264.

McLaurin, D., Marcum, D., Remotigue, M., Blades, E. (2013). Repairing unstructured triangular mesh intersections. International Journal for Numerical Methods in Engineering, 93(3), 266–275. https://doi.org/10.1002/nme.4385.

Melero, F.J., Aguilera, A., Feito, F.R. (2019). Fast collision detection between high resolution polygonal models. Computers and Graphics (Pergamon), 83, 97–106. https://doi.org/10.1016/j.cag.2019.07.006.

Meriaux, M. (1984). A two-dimensional clipping divider. In: Eurographics Conference Proceedings. https://doi.org/10.2312/eg.19841031.

Molla, R., Jorquera, P., Vivo, R. (2003). Fixed-point arithmetic line clipping. In: WSCG ’2003 Proceedings, pp. 93–96.

Mortenson, M.E. (1988). Computer Graphics: An Introduction to the Mathematics and Geometry. Industrial Press, Inc., USA. 0831111828.

Möller, T. (1997). A fast triangle-triangle intersection test. Journal of Graphics Tools, 2(2), 25–30. https://doi.org/10.1080/10867651.1997.10487472.

Möller, T., Trumbore, B. (1997). Fast, minimum storage ray-triangle intersection. Journal of Graphics Tools, 2(1), 21–28. https://doi.org/10.1080/10867651.1997.10487468.

Newman, W.M., Sproull, R.F. (1979). Principles of Interactive Computer Graphics, 2nd ed. McGraw-Hill, Inc., USA. 0070463387.

Nicholl, T.M., Lee, D.T., Nicholl, R.A. (1987). An efficient new algorithm for 2-D line clipping: its development and analysis. In: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987, pp. 253–262. https://doi.org/10.1145/37401.37432.

Nielsen, H.P. (1995). Line clipping using semi-homogeneous coordinates. Computer Graphics Forum, 14(1), 3–16. https://doi.org/10.1111/1467-8659.1410003.

Nisha, A. (2017a). Comparison of various line clipping algorithms: review. International Journal of Advanced Research in Computer Science and Software Engineering, 7(1). https://doi.org/10.23956/ijarcsse/V7I1/0149.

Nisha, A. (2017b). A review: comparison of line clipping algorithms in 3D space. International Journal of Advanced Research (IJAR), 5(1). https://doi.org/10.21474/IJAR01/3022.

Nishita, T., Johan, H. (1999). A scan line algorithm for rendering curved tubular objects. In: Proceedings. Seventh Pacific Conference on Computer Graphics and Applications, Seoul, Korea (South), pp. 92–101. https://doi.org/10.1109/PCCGA.1999.803352.

Pandey, A., Jain, S. (2013). Comparison of various line clipping algorithm for improvement. International Journal of Modern Engineering Research, 3(1), 69–74.

Petrie, F., Mills, S. (2020). Real time ray tracing of analytic and implicit surfaces. In: 2020 35th International Conference on Image and Vision Computing New Zealand (IVCNZ), Wellington, New Zealand, pp. 1–6. https://doi.org/10.1109/IVCNZ51579.2020.9290653.

Pharr, M., Jakob, W., Humphreys, G. (2016). Physically Based Rendering: From Theory to Implementation, 3rd ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 0128006455.

Platis, N., Theoharis, T. (2003). Fast ray-tetrahedron intersection using plucker coordinates. Journal of Graphics Tools, 8(4), 37–48. https://doi.org/10.1080/10867651.2003.10487593.

Raja, S.P. (2019). Line and polygon clipping techniques on natural images – a mathematical solution and performance evaluation. International Journal of Image and Graphics, 19(2). https://doi.org/10.1142/S0219467819500128.

Rajan, K., Hashemi, S., Karpuzcu, U., Doggett, M., Reda, S. (2020). Dual-precision fixed-point arithmetic for low-power ray-triangle intersections. Computers and Graphics (Pergamon), 87, 72–79. https://doi.org/10.1016/j.cag.2020.01.006.

Rappoport, A. (1991). An efficient algorithm for line and polygon clipping. The Visual Computer, 7(1), 19–28. https://doi.org/10.1007/BF01994114.

Ray, B.K. (2012a). An alternative algorithm for line clipping. Journal of Graphics Tools, 16(1), 12–24. https://doi.org/10.1080/2151237X.2012.641824.

Ray, B.K. (2012b). A line segment clipping algorithm in 2D. International Journal of Computer Graphics, 3(2), 51–76.

Ray, B.K. (2014). A procedure to clip line segment. International Journal of Computer Graphics, 5(1), 9–19. https://doi.org/10.14257/ijcg.2014.5.1.02.

Ray, B.K. (2015). Line clipping against arbitrary polygonal window. International Journal of Computer Graphics, 6(1), 12–24. https://doi.org/10.14257/ijcg.2015.6.1.01.

Reshetov, A. (2017). Exploiting Budan-Fourier and Vincent’s theorems for ray tracing 3D Bézier curves. In: Proceedings of High Performance Graphics, HPG ’17. Association for Computing Machinery, New York, NY, USA. 9781450351010. https://doi.org/10.1145/3105762.3105783.

Reshetov, A. (2019). Cool patches: a geometric approach to ray/bilinear patch intersections. In: Ray Tracing Gems: High-Quality and Real-Time Rendering with DXR and Other APIs, pp. 95–109. 978-1-4842-4427-2. https://doi.org/10.1007/978-1-4842-4427-2_8.

Reshetov, A. (2022). Ray/ribbon intersections. Proceedings of the ACM on Computer Graphics and Interactive Techniques, 5(3). https://doi.org/10.1145/3543862.

Rivero, M., Feito, F.R. (2000). Boolean operations on general planar polygons. Computers and Graphics (Pergamon), 24(6), 881–896. https://doi.org/10.1016/S0097-8493(00)00090-X.

Rogers, D.F., Rybak, L.M. (1985). On an efficient general line-clipping algorithm. IEEE Computer Graphics and Applications, 5(1), 82–86. https://doi.org/10.1109/MCG.1985.276298.

Rogers, D.F., Adams, J.A. (1989). Mathematical Elements for Computer Graphics, 2nd ed. McGraw-Hill, Inc., USA. 0070535299.

Roy, U., Dasari, V.R. (1998). Implementation of a polygonal algorithm for surface–surface intersections. Computers & Industrial Engineering, 34(2), 399–412. https://doi.org/10.1016/S0360-8352(97)00276-3.

Sabharwal, C., Leopold, J., McGeehan, D. (2013). Triangle-triangle intersection determination and classification to support qualitative spatial reasoning. Polibits, 48, 13–22. https://doi.org/10.17562/PB-48-2.

Sabharwal, C.L., Leopold, J.L. (2015). A triangle-triangle intersection algorithm. Computers and Graphics, 5(11), 27–35. https://doi.org/10.5121/csit.2015.51003.

Sabharwal, C.L., Leopold, J.L. (2016). A generic design for implementing intersection between triangles in computer vision and spatial reasoning. In: Pal, R. (Ed.), Innovative Research in Attention Modeling and Computer Vision Applications. IGI Global, USA, p. 41. https://doi.org/10.4018/978-1-4666-8723-3.ch008.

Salomon, D. (1999). Computer Graphics and Geometric Modeling, 1st ed. Springer-Verlag, Berlin, Heidelberg. 0387986820.

Salomon, D. (2006). Transformations and Projections in Computer Graphics. Springer-Verlag, Berlin, Heidelberg. 1846283922.

Salomon, D. (2011). The Computer Graphics Manual. Springer, USA, pp. 1–1496. 978-0-85729-885-0. https://doi.org/10.1007/978-0-85729-886-7.

Schneider, P.J., Eberly, D.H. (2003). Geometric Tools for Computer Graphics, The Morgan Kaufmann Series in Computer Graphics. Morgan Kaufmann, San Francisco, pp. 1–1009. 978-1-55860-594-7. https://doi.org/10.1016/B978-1-55860-594-7.50025-4.

Segura, R.J., Feito, F.R. (1998). An algorithm for determining intersection segment-polygon in 3D. Computers and Graphics (Pergamon), 22(5), 587–592. https://doi.org/10.1016/s0097-8493(98)00064-8.

Sharma, M., Kaur, J. (2016). An improved polygon clipping algorithm based on affine transformation. Advances in Intelligent Systems and Computing, 379(1), 783–792. https://doi.org/10.1007/978-81-322-2517-1_75.

Sharma, N.C., Manohar, S. (1992). Line clipping revisited: two efficient algorithms based on simple geometric observations. Computers and Graphics, 16(1), 51–54. https://doi.org/10.1016/0097-8493(92)90071-3.

Sharma, N.C., Manohar, S. (1993). Three dimensional line-clipping by systematic enumeration. (IFIP Transactions B: Computer Applications in Technology, 1(9), 225–232. 0444815643.

Shen, H., Heng, P.A., Tang, Z. (2003). A fast triangle-triangle overlap test using signed distances. Journal of Graphics Tools, 8(1), 17–23. https://doi.org/10.1080/10867651.2003.10487579.

Shirley, P., Marschner, S. (2009). Fundamentals of Computer Graphics, 3rd ed. A. K. Peters, Ltd., USA. 1568814690.

Singh, R., Lumar, A. (2016). RJ-ASHI algorithm: a new polygon/line clipping algorithm for 2D space. International Journal of Advanced Research in Computer Science and Software Engineering, 6, 215–219.

Skala, V. (1989). Algorithms for 2D line clipping. In: Hansmann, W., Hopgood, F.R.A., Straßer, W. (Eds.), EG 1989 Proceedings. Eurographics Association, The Netherlands. https://doi.org/10.2312/egtp.19891026.

Skala, V. (1990a). Algorithms for clipping quadratic arcs. In: Chua, T.S., Kunii, T.L. (Eds.), CGI Proceedings. Springer, Tokyo, pp. 255–268. https://doi.org/10.1007/978-4-431-68123-6_16.

Skala, V. (1990b). Clipping Algorithm. Habilitation thesis. University of West Bohemia, Pilsen (partially in Czech). http://afrodita.zcu.cz/~skala/EDU-PUB/Habilitace-komplet.pdf.

Skala, V. (1993). An efficient algorithm for line clipping by convex polygon. Computers and Graphics, 17(4), 417–421. https://doi.org/10.1016/0097-8493(93)90030-D.

Skala, V. (1994). O(lg N) line clipping algorithm in E². Computers and Graphics, 18(4), 517–524. https://doi.org/10.1016/0097-8493(94)90064-7.

Skala, V. (1996a). An efficient algorithm for line clipping by convex and non-convex polyhedra in E³. Computer Graphics Forum, 15(1), 61–68. https://doi.org/10.1111/1467-8659.1510061.

Skala, V. (1996b). Line clipping in E² with O(1) processing complexity. Computer Graphics (Pergamon), 20(4), 523–530. https://doi.org/10.1016/0097-8493(96)00024-6.

Skala, V. (1996c). Line clipping in E³ with expected complexity O(1). Machine Graphics and Vision, 5(4), 551–562. https://doi.org/10.48550/arXiv.2201.00592.

Skala, V. (1996d). Trading time for space: an O(1) average time algorithm for point-in-polygon location problem: theoretical fiction or practical usage? Machine Graphics and Vision, 5(3), 483–494.

Skala, V. (1997). A fast algorithm for line clipping by convex polyhedron in E³. Computers and Graphics (Pergamon), 21(2), 209–214. https://doi.org/10.1016/s0097-8493(96)00084-2.

Skala, V. (2004). A new line clipping algorithm with hardware acceleration. In: Proceedings of Computer Graphics International Conference, CGI, pp. 270–273. https://doi.org/10.1109/CGI.2004.1309220.

Skala, V. (2005). A new approach to line and line segment clipping in homogeneous coordinates. Visual Computer, 21(11), 905–914. https://doi.org/10.1007/s00371-005-0305-3.

Skala, V. (2008a). Barycentric coordinates computation in homogeneous coordinates. Computers and Graphics (Pergamon), 32(1), 120–127. https://doi.org/10.1016/j.cag.2007.09.007.

Skala, V. (2008b). Intersection computation in projective space using homogeneous coordinates. International Journal of Image and Graphics, 8(4), 615–628. https://doi.org/10.1142/S021946780800326X.

Skala, V. (2010). Duality, barycentric coordinates and intersection computation in projective space with GPU support. WSEAS Transactions on Mathematics, 9(6), 407–416. http://afrodita.zcu.cz/~skala/PUBL/PUBL_2010/2010_NAUN-journal.pdf.

Skala, V. (2012). S-clip E²: a new concept of clipping algorithms. In: SIGGRAPH Asia Posters, SA ’12, pp. 1–2. https://doi.org/10.1145/2407156.2407200.

Skala, V. (2013a). Line-torus intersection for ray tracing: alternative formulations. WSEAS Transactions on Computers, 12(7), 288–297. https://doi.org/10.48550/ARXIV.2301.03191.

Skala, V. (2013b). Summation problem revisited – more robust computation. In: 17th International Conference on Computers – Recent Advances in Computer Science CSCC ’13, pp. 56–64. 978-960-474-311-7. https://doi.org/10.48550/arXiv.2211.04402.

Skala, V. (2014). 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. https://doi.org/10.1145/2668975.2668976.

Skala, V. (2015). A new approach to line – sphere and line – quadrics intersection detection and computation. AIP Conference Proceedings, 1648, 1–4. 9780735412873. https://doi.org/10.1063/1.4913058.

Skala, V. (2020). Optimized line and line segment clipping in E2 and geometric algebra. Annales Mathematicae et Informaticae, 52, 199–215. https://doi.org/10.33039/ami.2020.05.001.

Skala, V. (2021a). Efficient intersection computation of the Bezier and Hermite curves with axis aligned bounding box. WSEAS Transactions on Systems, 20, 320–323. https://doi.org/10.37394/23202.2021.20.36.

Skala, V. (2021b). A new coding scheme for line segment clipping in E². In: Computational Science and Its Applications – ICCSA 2021, Lecture Notes in Computer Science, Vol. 12953, pp. 16–29. https://doi.org/10.1007/978-3-030-86976-2_2.

Skala, V. (2021c). A novel line convex polygon clipping algorithm in E² with parallel processing modification. In: Computational Science and Its Applications – ICCSA 2021, Lecture Notes in Computer Science, Vol. 12953. pp. 3–15. https://doi.org/10.1007/978-3-030-86976-2_1.

Skala, V. (2022). Clipping and Intersection Algorithms: Short Survey and References. arXiv: https://doi.org/10.48550/ARXIV.2206.13216. https://arxiv.org/abs/2206.13216.

Skala, V., Bui, D.H. (2000). Faster algorithm for line clipping against a pyramid in E3. Machine Graphics and Vision, 9(4), 841–850. https://doi.org/10.48550/arXiv.2201.00587.

Skala, V., Bui, D.H. (2001). Extension of the Nicholls-Lee-Nichols algorithm to three dimensions. Visual Computer, 17(4), 236–242. https://doi.org/10.1007/s003710000094.

Skala, V., Huy, B.D. (2000). Two new algorithms for line clipping in E2 and their comparison. Machine Graphics and Vision, 9(1/2), 297–306. https://doi.org/10.48550/arXiv.2201.00590.

Skala, V., Lederbuch, P. (1996). A comparison of a new O(1) and the cyrus-beck line clipping algorithms in E2. In: Compugraphics’96: Fifth International Conference on Computational Graphics and Visualization Techniques. ACM, Portugal, pp. 281–287. 972-8342-01-2. https://dspace5.zcu.cz/handle/11025/11808.

Skala, V., Kolingerova, I., Blaha, P. (1995). A comparison of 2D line clipping algorithms. Machine Graphics and Vision, 3(4), 625–633.

Skala, V., Lederbuch, P., Sup, B. (1996). A comparison of O(1) and Cyrus-Beck line clipping algorithm in E2 and E3. In: SCCG96 Conference Proceedings. Comenius University, Slovakia, pp. 17–44. https://doi.org/10.48550/arXiv.2111.07987. https://dspace5.zcu.cz/handle/11025/11806.

Slater, M., Barsky, B.A. (1994). 2D line and polygon clipping based on space subdivision. The Visual Computer, 10(7), 407–422. https://doi.org/10.1007/BF01900665.

Sobkow, M.S., Pospisil, P., Yang, Y.-H. (1987). A fast two-dimensional line clipping algorithm via line encoding. Computers and Graphics, 11(4), 459–467. https://doi.org/10.1016/0097-8493(87)90061-6.

Sproull, R.F., Sutherland, I.E. (1968). A clipping divider. In: Fall Joint Computer Conference Proceedings, of the December 9–11, 1968, AFIPS ’68 (Fall, part I). Association for Computing Machinery, New York, NY, USA, pp. 765–775. 9781450378994. https://doi.org/10.1145/1476589.1476687.

Stolfi, J. (1991). Oriented Projective Geometry. Academic Press Professional, Inc., USA. 0126720258.

Sun, C., Wang, W., Li, J., Wu, E. (2006). Line clipping against a polygon through convex segments. Journal of Computer-Aided Design and Computer Graphics, 18(12), 1799–1805.

Sutherland, I.E. (1972). Display windowing by clipping. Google Patents. https://patents.google.com/patent/US3639736A/en.

Sutherland, I.E., Hodgman, G.W. (1974). Reentrant polygon clipping. Communications of the ACM, 17(1), 32–42. https://doi.org/10.1145/360767.360802.

Tang, L.-L., He, Y.-J. (2009). A linear time algorithm for the line clipping against concave polygon. In: Proceedings – 2009 International Conference on Information Engineering and Computer Science, ICIECS 2009, pp. 1–4. https://doi.org/10.1109/ICIECS.2009.5364626.

Theoharis, T., Platis, N., Papaioannou, G., Patrikalakis, N.M. (2008). Graphics and Visualization: Principles & Algorithms, 1st ed. A. K. Peters/CRC Press, New York. https://doi.org/10.1201/b10676.

Thomas, A. (2008). Integrated Graphics and Computer Modelling, 1st ed. Springer, London. 1848001789.

Tran, C.-H. (1986). Fast Clipping Algorithms for Computer Graphics. PhD thesis, University of British Columbia. https://doi.org/10.14288/1.0096928. https://open.library.ubc.ca/collections/ubctheses/831/items/1.0096928.

Tropp, O., Tal, A., Shimshoni, I. (2006). A fast triangle to triangle intersection test for collision detection. Computer Animation and Virtual Worlds, 17(5), 527–535. https://doi.org/10.1002/cav.115.

Van Wyk, C.J. (1984). Clipping to the boundary of a circular-arc polygon. Computer Vision, Graphics, and Image Processing, 25(3), 383–392. https://doi.org/10.1016/0734-189X(84)90202-0.

Vatti, B.R. (1992). A generic solution to polygon clipping. Communications of the ACM, 35(7), 56–63. https://doi.org/10.1145/129902.129906.

Vince, J. (2009). Geometric Algebra: An Algebraic System for Computer Games and Animation, 1st ed. Springer, London. 1848823789.

Vince, J. (2010). Introduction to the Mathematics for Computer Graphics, 3rd ed. Springer-Verlag, Berlin, Heidelberg. 1849960224. https://link.springer.com/book/10.1007/978-1-4471-6290-2#toc.

Vince, J. (2012). Matrix Transforms for Computer Games and Animation. Springer, London. 1447143205.

Vince, J.A. (2008). Geometric Algebra for Computer Graphics, 1st ed. Springer-Verlag TELOS, Santa Clara, CA, USA. 1846289963. https://doi.org/10.1007/978-1-84628-997-2.

Wang, H., Chong, S. (2016). A high efficient polygon clipping algorithm for dealing with intersection degradation. Dongnan Daxue Xuebao (Ziran Kexue Ban)/Journal of Southeast University (Natural Science Edition), 46(4), 702–707. https://doi.org/10.3969/j.issn.1001-0505.2016.04.005.

Wang, H., Wu, R., Cai, S. (1998a). A new algorithm for two-dimensional line clipping via geometric transformation. Journal of Computer Science and Technology, 13(5), 410–416. https://doi.org/10.1007/bf02948499.

Wang, H., Wu, R., Cai, S. (1998b). New efficient line clipping algorithm based on geometric transformation. Ruan Jian Xue Bao/Journal of Software, 9(10), 728–733.

Wang, J., Lu, G.-D., Peng, Q.-S., Wu, X.-H. (2005). Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting. Journal of Zhejiang University: Science, 6(Suppl 1), 100–107. https://doi.org/10.1631/jzus.2005.AS0100.

Wang, J., Cui, C., Gao, J. (2012). An efficient algorithm for clipping operation based on trapezoidal meshes and sweep-line technique. Advances in Engineering Software, 47(1), 72–79. https://doi.org/10.1016/j.advengsoft.2011.12.003.

Wang, X., Xue, Y., Fang, F., Chen, G. (2001). From probability model to a fast line clipping algorithm. In: CAD/GRAPHICS 2001, pp. 802–806.

Watt, A. (1993). 3d Computer Graphics, 2nd ed. Addison-Wesley Longman Publishing Co., Inc., USA. 0201631865.

Wei, L.-Y. (2014). A faster triangle-to-triangle intersection test algorithm. Computer Animation and Virtual Worlds, 25(5–6), 553–559. https://doi.org/10.1002/cav.1558.

Wei, W., Ma, P., Lin, W. (2013). An improved Cohen-Sutherland region encoding algorithm. Applied Mechanics and Materials, 239–240, 1313–1317. 9783037855454. https://doi.org/10.4028/www.scientific.net/AMM.239-240.1313.

Weiler, K. (1980). Polygon comparison using a graph representation. In: Proceedings of the 7th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’80, pp. 10–18. https://doi.org/10.1145/800250.807462.

Weiler, K., Atherton, P. (1977). Hidden surface removal using polygon area sorting. In: Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’77, pp. 214–222. https://doi.org/10.1145/563858.563896.

Wijeweera, K.R., Kodituwakku, S.R., Pathum Chamikara, M.A. (2019). A novel and efficient approach for line segment clipping against a convex polygon. Ruhuna Journal of Science, 10(2), 161–173. https://doi.org/10.4038/rjs.v10i2.81.

Wikipedia (2020). Plücker Matrix – Wikipedia, The Free Encyclopedia. [Online; accessed 12-May-2022]. https://en.wikipedia.org/wiki/Plucker_matrix.

Wikipedia (2021a). Clipping (Computer Graphics) – Wikipedia, The Free Encyclopedia. [Online; accessed 28-July-2021]. https://en.wikipedia.org/wiki/Clipping_(computer_graphics).

Wikipedia (2021b). IEEE 754 – Wikipedia, The Free Encyclopedia. [Online; accessed 11-July-2021]. https://en.wikipedia.org/wiki/IEEE_754.

Wikipedia (2021c). Ray Tracing (Graphics) – Wikipedia, The Free Encyclopedia. [Online; accessed 3-August-2021]. https://en.wikipedia.org/wiki/Ray_tracing_(graphics).

Williams, A., Barrus, S., Morley, R.K., Shirley, P. (2005). An efficient and robust ray-box intersection algorithm. In: ACM SIGGRAPH 2005 Courses. ACM, New York, NY, USA, p. 9. https://doi.org/10.1145/1198555.1198748.

Wu, Q., Huang, X., Han, Y. (2006). A clipping algorithm for parabola segments against circular windows. Computers & Graphics, 30(4), 540–560. https://doi.org/10.1016/j.cag.2006.03.001. https://www.sciencedirect.com/science/article/pii/S0097849306000732.

Wu, Y., Li, X. (2022). Curve intersection based on cubic hybrid clipping. Visual Computing for Industry, Biomedicine, and Art, 5(1). https://doi.org/10.1186/s42492-022-00114-3.

Wu, Z., Gou, C., Yang, D., Luo, Z. (2004). Line clipping algorithm against arbitrary polygons. Journal of Computer-Aided Design and Computer Graphics, 16(2), 228–233.

Xiao, L., Mei, G., Cuomo, S., Xu, N. (2020). Comparative investigation of GPU-accelerated triangle-triangle intersection algorithms for collision detection. Multimedia Tools and Applications, 81, 3165–3180. https://doi.org/10.1007/s11042-020-09066-3.

Xie, L., Li, P., Zhou, M., Wang, X. (2010). An clipping general polygons in regular girds algorithm base on successive encoding. In: 2010 International Conference on Computer Application and System Modeling, ICCASM 2010, Taiyuan, 2010, pp. 4709–4713. https://doi.org/10.1109/ICCASM.2010.5619427.

Yang, W. (1988). New approach to line clipping in computer graphics display. Zhongnan Kuangye Xueyuan Xuebao, 18(1), 73–78.

Ye, X., Huang, L., Wang, L., Xing, H. (2015). An improved algorithm for triangle to triangle intersection test. In: ICIA 2015 Proceedings, pp. 2689–2694. https://doi.org/10.1109/ICInfA.2015.7279740.

Zhang, M., Sabharwal, C.L. (2002). An efficient implementation of parametric line and polygon clipping algorithm. In: Proceedings of the ACM Symposium on Applied Computing, pp. 796–800. https://doi.org/10.1145/508791.508945.

Zhang, Z., Fan, J., Xu, S., Chen, Z. (2022). VCS optimization method of Vatti algorithm for polygon overlay and parallelization using GPU. Journal of Geo-Information Science, 24(3), 437–447 (in Chinese). https://doi.org/10.12082/dqxxkx.2022.210409.

Zheng, J.L., Millham, C.B. (1991). A linear programming method for ray-convex polyhedron intersection. Computers and Graphics, 15(2), 195–204. https://doi.org/10.1016/0097-8493(91)90073-Q.

Biographies

Skala Vaclav

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

skala@kiv.zcu.cz

V. Skala is a full professor of computer science at the University of West Bohemia, Pilsen, Czech Republic. He received his Ing. (equivalent of MSc) degree in 1975 from the Institute of Technology in Pilsen, CSc. (equivalent of PhD) degree from the Czech Technical University in Prague, in 1981. In 1996, he became a full professor in computer science. He is a Fellow of the Eurographics Association, member of several editorial boards of international research journals and the editor-in-chief of the Journal of WSCG and Computer Science Research Notes. He is the organizer of the WSCG conferences on computer graphics, visualization and computer vision (www.wscg.eu) held annually since 1992.

His current research interests are computer graphics and visualization, applied mathematics, especially geometrical algebra, algorithms, and data structures.

Full article

Open access article under the CC BY license.

Keywords

intersection algorithms line clipping line segment clipping polygon clipping triangle-triangle intersection homogeneous coordinates projective space duality computer graphics geometry convex polygon convex polyhedron

Metrics (since January 2020)

62 Article info views	38 Full article views
102 PDF downloads	19 XML downloads

RSS

Authors

Abstract

References

Biographies

Export citation

Copy and paste formatted citation

Download citation in file