11institutetext:  University of West Bohemia, Faculty of Applied Sciences
Dept. of Computer Science and Engineering
Pilsen, CZ 301 00, Czech Republic
11email<EMAIL_ADDRESS>www.VaclavSkala.eu

# Clipping and Intersection Algorithms:
Short Survey and References

Vaclav Skala 11 0000-0001-8886-4281

###### 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 supports GPU and SSE use.

This survey is intended as help to researchers, students, and practitioners
dealing with intersection and clipping algorithms. 111 The PDF drafts of the
Skala’s papers can be found at the papers repository
http://afrodita.zcu.cz/$\sim$skala/publications.htm

###### Keywords:

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

##  1 Introduction

Intersection algorithms are the key algorithms in many areas, e.g. in geometry
intersection algorithms of two lines in $E^{2}$ or three planes in $E^{3}$.
Many of those algorithms are part of standard courses and based on
formulations in the Euclidean geometry, e.g. Schneider-Eberly[149]. However,
there is a problem with results in an infinity or close to an infinity in some
cases. Some cases can be solved using the projective extension of the
Euclidean space extension of duality Skala[168]. The projective extension
enables to represent points in an infinity and using the principle of duality
to solve dual problems by the same algorithm Skala[167].

Also, as this approach leads to formulations using $vector-vector$ operations,
it is convenient for GPU and SSE use.

Algorithms for intersections of different geometric entities in $E^{2}$ and
$E^{3}$ are studied for a long time from different aspects as their robustness
and the precision of numerical computations is severely influenced by the
limited numerical precision available at today’s computer system. It is well
known, that $(1/3)*3\neq 1$ in ”the computer world”. Even a simple summation
$S=\sum_{i=1}^{n}a_{i}$ is not easy Skala[171].

It should be noted that, not only in geometry oriented algorithms, a special
care has to be devoted to the cases where differences between mathematics with
infinite precision and mathematics with a limited precision might cause
problems which could lead to the unexpected and incorrect results, sometimes
also leads to disasters.

Unfortunately, programmers and computer scientists are mostly targeted to ”the
technology of implementation”. They have a limited understanding of numerical
aspects of today’s numerical data representation limited more or less to the
IEEE floating-point representation IEEE-754[218]. Despite of the technological
progress, the binary128 and binary256 precisions IEEE-754[218] are not
supported in hardware.

It appears that there is no possibility to represent rational, irrational and
transcendental numbers used in mathematics, where unlimited precision is
expected, e.g. what is the difference of the value of $\pi^{\pi}$ and
$(\mathbf{longreal}~{}pi)^{(\mathbf{longreal}~{}pi)}$ if the IEEE-754
representation is used?

Line, half-line (ray), line segment and triangle-triangle intersection
algorithms are considered as fundamental algorithms in nearly all algorithms
dealing with geometrical aspects.

In computer graphics, some intersection algorithms are called clipping
algorithms and serve to determine a part of one geometric entity inside of the
second one.

##  2 Relevant books and journals

There are many books published related to intersection algorithms, clipping
and computer graphics, which give more context, deeper understanding (*some
books are available for free download via link.Springer.com), e.g.:

  * •

Salomon,D.: The Computer Graphics Manual[148]*
highly recommended,

  * •

Salomon,D.: Computer Graphics and Geometric Modeling[146],

  * •

Agoston,M.K.: Computer Graphics and Geometric Modelling: Mathematics[2],

  * •

Agoston,M.K.: Computer Graphics and Geometric Modelling: Implementation &
Algorithms[1],

  * •

Lengyel,E.: Mathematics for 3D Game Programming and Computer Graphics[95],

  * •

Vince,J.: Introduction to the Mathematics for Computer Graphics[202]*
basic mathematical description of mathematics for undergraduates,

  * •

Foley,J.D., van Dam,A., Feiner,S., Hughes,J.F.: Computer graphics - principles
and practice[53],

  * •

Hughes,J.F., van Dam, A., McGuire,M., Sklar,D.F., Foley,J.D., Feiner,S.K.,
Akeley, K.: Computer Graphics - Principles and Practice[72],

  * •

Ferguson,R.S.: Practical Algorithms for 3D Computer Graphics[52],

  * •

Shirley,P., Marschner,S.: Fundamentals of Computer Graphics[155]

  * •

Theoharis,T., Platis,N., Papaioannou,G., Patrikalakis,N.: Graphics and
Visualization: Principles & Algorithms[195]

  * •

Comninos,P.: Mathematical and Computer Programming Techniques for Computer
Graphics[24],

  * •

Schneider,P.J., Eberly,D.H.: Geometric Tools for Computer Graphics[149],

  * •

Ammeraal,L., Zhang,K.: Computer graphics for Java programmers[5],

  * •

Vince,J.: Matrix Transforms for Computer Games and Animation[203]

There are also computer graphics books using OpenGL interface, e.g.:

  * •

Hill,F.S., Kelley,S.M.: Computer Graphics Using OpenGL[68],

  * •

Angel,E., Shreiner,D.: Interactive Computer Graphics[7],

  * •

Hearn,D.D., Baker,M.P., Carithers,W.: Computer Graphics with OpenGL[64]

  * •

Govil-Pai,S.: Principles of Computer Graphics: Theory and Practice Using
OpenGL and Maya[56]

More advanced books using Geometric Algebra and Conformal Geometry Algebra
approaches are recommended for a deeper study, e.g.:

  * •

Vince,J.: Geometric Algebra: An Algebraic System for Computer Games and
Animation[201],

  * •

Vince,J.: Geometric Algebra for Computer Graphics[204],

  * •

Dorst,L., Fontijne,D., Mann,S.: Geometric Algebra for Computer Science: An
Object-Oriented Approach to Geometry[42],

  * •

Hildenbrand,D.: Foundations of Geometric Algebra Computing[67],

  * •

Kanatani,K.: Understanding Geometric Algebra: Hamilton, Grassmann, and
Clifford for Computer Vision and Graphics[79],

  * •

Calvet,R.G.: Treatise of Plane Geometry through Geometric Algebra[19]

  * •

Guo,H.: Modern Mathematics and Applications in Computer Graphics and
Vision[59].

A short description of barycentric coordinates using geometry algebra approach
is available at Skala[166].

It is also recommended to study ”the historical” books, e.g.:

  * •

Newman,W.M., Sproull,R.F.: Principles of Interactive Computer Graphics[123],

  * •

Harrington,S.: Computer Graphics: A Programming Approach[61],

  * •

Mortenson,M.E.: Computer Graphics: An Introduction to the Mathematics and
Geometry[121],

  * •

Watt,A.: Fundamentals of Three-Dimensional Computer Graphics[211],

  * •

Salomon,D.: Transformations and Projections in Computer Graphics[147],

  * •

Akenine-Moller,T., Haines,E., Hoffman,N.: Real-Time Rendering[3],

  * •

Eberly,D.H.: Game Physics[47],

  * •

Pharr,M., Jakob,W., Humphreys,G.: Physically Based Rendering: From Theory to
Implementation[131],

  * •

Thomas,A.: Integrated Graphic and Computer Modelling[196],
describes the implementation of algorithms with examples of assembler codes,

  * •

Coxeter,H.S.M.,Beck,G.: The Real Projective Plane [26]

Many algorithms with codes are presented in GEMS books:

  * •

Graphics Gems, Ed.Glassner,A.[55],

  * •

Graphics Gems II, Ed.Arvo,J.[9]

  * •

Graphics Gems III, Ed.Kirk,D.[80],

  * •

Graphics Gems IV, Ed.Heckbert,P.S.[65].

Leading computer graphics journals:

  * •

ACM Transactions on Graphics (TOG),

  * •

Computer Graphics Forum (CGF),

  * •

Computers & Graphics (C&G),

  * •

IEEE Trans. on Visualization and Computer Graphics (TVCG),

  * •

The Visual Computer (TVC),

  * •

Computer Animation and Virtual Worlds (CAVW),

  * •

Journal of Graphics Tools (JGT),

  * •

Graphical Models

present a wide variety of intersection algorithm applications and theories.

In the following a brief classification of intersection algorithms in 2D and
3D will be made with short characteristics as Wiki[217]. The above-mentioned
books present principles of the relevant methods and algorithms. Also, an
overview of algorithms can be found in Skala[183] and the Bui’s PhD[16]. A
deeper analysis, comparisons, classifications etc. can be found in the
relevant papers.

There are so many fundamental algorithms variants that differ in some aspects;
mainly, the timing factor is the primary motivation. However, claimed speed up
mostly depends on the hardware properties (caching etc.), programmer’s skill
and actual language and compiler used.

##  3 Intersection algorithms in 2D

Algorithms for intersections of different 2D geometric entities are studied
for a long time from various aspects, primarily due to computation speed,
robustness and limited numerical precision of the floating-point
representation. The majority of 2D algorithms deals with an intersection of a
line or a half-line (ray) or a line segment with 2D geometric entity, e.g. a
rectangle, convex polygon, non-convex polygon, quadric and cubic curves,
parametric curves and areas with quadratic arcs Skala[172][181][182], etc.

###  3.1 Intersection with a rectangular area

Intersection algorithms with a rectangular area (window) are well known as
line clipping or as line segment clipping algorithms were developed and used
for a flight simulator project led by Cohen[23] in 1967. An efficient coding
of a line segment position coding leading to significant computational
reduction was introduced in Sproull&Sutherland[189] and patented by
Sutherland[192] in 1972. The Cohen&Sutherland algorithm is described in
Newman[123], Comninos[25], Matthes[113], Matthes[114], etc.

The Cohen-Sutherland algorithm can be extended to the 3D case, i.e.
intersection of a line with a cube or right parallelepiped. The Cohen-
Sutherland algorithm was improved by Nicholl–Lee–Nicholl[124] and Bui[17] by
classification of some possible cases. Ultimate cases classification was made
by Skala[175] in 2021. The algorithms Liang-Barsky[102] and Doerr[46] are
based on direct intersection computation of a line with polygon edges in the
parametric form. Simple and robust 3D Clipping algorithms based on projective
representation and homogeneous coordinates using a separation of the convex
polygon vertices by the given line was presented in Skala[164][165][169][173].

Other known proposed algorithms can be found in references Bui[16],
Andreev[6], Bao[10], Devai[36][37][38], Duvalenko[43][44][45], Cai[18],
Day[31][32], Evangeline[51], Kaijian[78], Kodituwakku[82], Kong[87],
Maillot[110], Wei[213], Slater[187], Ray[136][137][138][139], Li[96],
Singh[156], Dev[35], Tran[197], Wang[205].

Some additional modifications of algorithms were published in Brackenbury[15],
Chen[21][22], Brackenbury[15], Dimri2015[40][41], Ellriki[49], Hattab[62],
Iraji[73], Jiang[74], Jianrong[75], Kumar[90], Kuzmin[92], Li[98][100],
Meriaux[119], Molla[120], Nisha[127], Nisha[126], Sobkow[188], Sharma[153],
Skala[184], Wang[206][207][209][210], Yang[225], Pandey[129] and Bhuiyan[11].
Algorithms for clipping Bezier and Hermit parametric curve by a rectangular
area was published in Skala[174]. Dawod[30] presented FPGA solution for a line
clipping.

Analysis and comparisons of some clipping algorithms were published in
Krammer[88], Skala[179][180], Nisha[126][127] and Ray[137]. Algorithms for
triangle-triangle intersections were presented by Sabharwal[143][144][145].

###  3.2 Intersection with polygons

Generic solutions for polygon clipping was developed by Weiler&Atherton[215],
Rappaport[135], Vatti[200], Wu[222], Xie[224], Zhang[227]. Boolean operations
with polygons were introduced by Rivero[140] and Martinez[112].

Algorithms for line clipping by a polygon depend on the polygon property, i.e.
if the polygon is convex or non-convex. In the case of convex polygons, the
convexity property and ordering of vertices enable to decrease complexity to
$O(lgN)$. However, in the non-convex polygon cases, when the polygon can be
self-intersecting, etc., problems with a robustness of computation can be
expected, in some cases a three-value logic is to be used, e.g.
Skala[181][182].

####  3.2.1 Convex polygons

The Cyrus-Beck’s[28] algorithm is the famous algorithm for line-convex polygon
clipping. It is based on computation of a parameter $t$ of a line in the
parametric form and edges of the given convex polygon. The algorithm is of
$O(N)$ computational complexity. The algorithm can be extended for the $E^{3}$
case. Some improvements and modifications were described by Skala[157]. As the
edges of the convex polygon are ordered, algorithm with the $O(lgN)$ was
derived by Skala[158]. An algorithm based on space subdivision was described
in Slater[187].

Another approach based on the implicit form of the given line and convex
polygon vertices classification was developed in Skala[176] and modified by
Konashkova[85][86]. Another algorithm based S-Clip was described in
Skala[176]. Another algorithm for a line segment clipping based on the line
segment end-points evaluation with $O(N)$ complexity was described by
Matthes&Drakopoulos[115].

The Liang-Barsky algorithm[101][102] is based on direct intersection
computation of a line with the convex polygon edges in the parametric form and
has $O(N)$ computational complexity, too.

The algorithm with a run-time $O(1)$ complexity using pre-computation was
developed by Skala[160][162]. The algorithm was motivated by the scan-line
raster conversion used recently for solving visibility in rendering. The
memory requirements depend on the geometrical properties of the given convex
polygon. A comparison of the $O(1)$ algorithm with the Cyrus-Beck algorithm is
presented in Skala[185][186].

Other related algorithms or modification of existing ones were published in:
Sun[191], Vatti[200], Wang[208], Li[97], Nishita[128], Gupta[60],
Wijeweera[216], Raja[133] and Sharma[151][152] uses the affine transformation,
Zheng[228] uses a linear programming method for ray-polyhedron intersection.

####  3.2.2 Non-convex polygons

Probably, the first algorithm dealing with non-convex polygon clipping was
published by Sutherland&Hodgman in the Reentrant polygon clipping algorithm
paper[193] in 1974, followed by Weiler&Atherton algorithm for polygon-polygon
clipping [214][215], Rappaport[135],

Intersections with arbitrary non-convex non-convex polygons were described in
Greiner[57] and solutions of ”the singular” (degenerated) cases were described
in Skala[181] and Foster[54].
A robust solution of triangle-triangle intersection in $E^{2}$ is described in
McCoid[116]. Other algorithms or modifications are described in Dimri[40],
Evangeline[51], Tang[194], Lu[105][106] and the affine transformations are
used in Huang[69][70][71].

An algorithm that handles also arcs and uses a three-value logic to handle
singular cases properly, including self-intersecting non-convex triangles, was
described in Skala[172][181][182]. Algorithm for circular arc was described in
Van Wyk[199], for overlapping areas by Li[99] and for circular window in
Lu[107], Kumar[91]. Wu[221] presented algorithm for intersection of parabola
segments against circular windows. The paper Kui Liu[89] and Landier[94]
present algorithms for union and intersection operations with polygons.

###  3.3 Clipping using homogeneous coordinates

Homogeneous coordinates are used in computer graphics not only for geometric
transformations. Sproull[189] use them in the Clipping divider in 1968.
Arokiasamy[8] use them with duality in 1989, Blinn[13][14] described the
clipping pipeline using the projective extension of the Euclidean space.
Nielsen[125] described use of semi-homogeneous coordinates for clipping, more
general view was published by Stolfi[190].

New approach to 2D clipping based on separation of the convex polygon vertices
by the given line was presented in Skala[164][165][169][173], Kolingerova[83].
The principle of duality Johnson[76] presents duality between line clipping
and pint-in-polygon problem.

##  4 Intersection algorithms in 3D

Intersection algorithms in 3D are widely used in many applications. An
overview of the clipping algorithms is given in the Bui’s PhD [16].
Intersection of a line segment with a polygon in 3D was studied in
Segura[150], the intersection of polygonal models was analyzed by Melero[118].

Algorithms for 3D clipping were over-viewed in Skala[183] and Bui’s PhD[16]. A
comparative study of selected algorithms was presented by Kolingerova[84].
Reliable intersection tests with geometrical objects were published by
Held[66].

###  4.1 Line-viewing pyramid

Special attention was given recently to a line clipping by a pyramid in 3D due
to the perspective pyramid clipping. The problem was analyzed very recently
Cohen[23], Sproull[189], Blinn[13][14][12], Skala[177][178].

####  4.1.1 Convex polyhedron case

The Cyrus-Beck’s[28] algorithm is probably the famous algorithm for line-
convex polyhedron clipping in $E^{3}$. It is based on computation of a
parameter $t$ of a line in the parametric form and plane of the given face of
the convex polyhedron. The algorithm is of $O(N)$ computational complexity.
Rogers[141] published a general clipping algorithm in 3D in 1995.

The algorithm with $O_{exp}(\sqrt{N})$ complexity was described in Skala[163].
The algorithm is based on two planes representing the given line in $E^{3}$
and the search of the neighbours in the triangular mesh of the given polygon.
The algorithm was modified by Konashkova[86]. An interesting approach using
the vertex connection table was published in Konashkova[85].

Using pre-computation, the algorithm in $E^{3}$ with a run-time $O(1)$
complexity was developed by Skala[161]; a comparison was presented in
Skala[186].

####  4.1.2 Ray-convex polyhedron

Extensive list of relevant publications can be found via Wiki[219].

Intersection of a line or a ray with a triangle can be also found in an
algorithms presented by Havel[63] using the SSE4 instructions, Xiao[223] using
GPUs and Skala[168] using the barycentric coordinates computation in the
homogeneous coordinates, Rajan[134] uses dual-precision fixed-point arithmetic
for low-power ray-triangle intersections. Platis&Theoharis[132] published
algorithm for ray-tetrahedron intersection using the Plucker coordinates. The
intersection with the AABBox is described in Eisemann[48], Kodituwakku[81],
Maonica[111] and Mahovsky[108]. Other algorithms are available in Sharma[153],
Skala[159], Williams[220], Llanas[103], Lagae[93] and Amanatides[4].

####  4.1.3 Intersection with complex objects

Intersection computation with implicitly defined objects were published by
Petrie[130] (Real Time Ray Tracing of Analytic and Implicit Surfaces),
intersection with a torus was published by Cychosz[27] and alternative
formulations were given in Skala[170]. Intersection with general quadrics
using the homogeneous coordinates was described in Skala[172] and clipping by
a spherical window was published by Deng[34].

However, as polygonal models are mostly formed by triangular surfaces a
special attention is also targeted to $triangle-triangle$ intersections.

### Triangle-Triangle intersection in 3D

Computation of intersection of triangles is probably the most important as
nearly all Computer Aided Design (CAD) systems depend on efficient, robust and
reliable computation. In the CAD systems two different data sets are usually
used:

  * •

set of triangles - there is no connection between triangles; typical example
is the STL format for 3D print

  * •

triangular mesh - there is information on the neighbors of the given triangles
and triangles sharing the given vertex; a typical example is the winged edge
or the half-edge data structures

An efficient triangle-triangle intersection algorithm was developed by
Moeller-Trumbore[122]. Other methods or approaches were described by
Chang[20], Danaei[29], Devillers[39], Elsheikh[50], Guigue-Devillers[58],
Jokanovi[77], McLaurin[117], Roy[142], Lo[104], Shen&Ann[154], Tropp&Tal[198],
Wei[212], Ye[226]. Clipping triangular strips using homogeneous coordinates
was described by Maillot[109] in GEM II[9]. Parallel exact algorithm for the
intersection of large 3D triangular meshes was described in de Magalhães[33].
Comparison of triangle-triangle tests on GPU was described in Xiao[223].

##  5 Conclusion

This contribution briefly summarizes known clipping algorithms with some
extents to the intersection and ray-tracing algorithms. The list of published
papers related to clipping algorithms should be complete to the author’s
knowledge and extensive search via Web of Science, Scopus, Research Gate and
WEB search with the related topics. The relevant DOIs were included, if found.
If other source was found, the relevant URL was included. Unfortunately, some
papers are not publicly available.

There is a hope, that this summary will help researchers, students and
software developers to find the relevant papers easily.

However, users are urged to consider a limited precision of the floating-point
representation[218] and numerical robustness issues to proper handling near
$singular$ cases in the actual implementations.

Surprisingly, during the study and this summary preparation, there are still
some problems to be explored more deeply, like a robust and efficient
intersection of triangular meshes; application of triangle-triangle
intersection algorithms leads to inconsistencies, inefficiency, and
unreliability in general Those topics will be explored more in future work.

## Acknowledgments

The author would like to thank colleagues and students at the University of
West Bohemia in Plzen, VSB-Technical University and Ostrava University in
Ostrava for their comments and recommendations.

Thanks also belong to several authors of recently published relevant papers
for sharing their views and hints provided.

## References

  * [1] Agoston, M.K.: Computer Graphics and Geometric Modelling: Implementation & Algorithms. Springer-Verlag, Berlin, Heidelberg (2004)
  * [2] Agoston, M.K.: Computer Graphics and Geometric Modelling: Mathematics. Springer-Verlag, Berlin, Heidelberg (2005)
  * [3] Akenine-Moller, T., Haines, E., Hoffman, N.: Real-Time Rendering. A. K. Peters, Ltd., USA, 3rd edn. (2008)
  * [4] Amanatides, J., Choi, K.Y.: Ray tracing triangular meshes. Western Computer Graphics Symposium p. 43–52 (1997)
  * [5] Ammeraal, L., Zhang, K.: Computer graphics for java programmers. Computer Graphics for Java Programmers pp. 1–387 (2017). https://doi.org/10.1007/978-3-319-63357-2
  * [6] Andreev, R., Sofianska, E.: New algorithm for two-dimensional line clipping. Computers and Graphics 15(4), 519–526 (1991). https://doi.org/10.1016/0097-8493(91)90051-I
  * [7] Angel, E., Shreiner, D.: Interactive Computer Graphics: A Top-Down Approach with Shader-Based OpenGL. Addison-Wesley Publishing Company, USA, 6th edn. (2011)
  * [8] Arokiasamy, A.: Homogeneous coordinates and the principle of duality in two dimensional clipping. Computers and Graphics 13(1), 99–100 (1989). https://doi.org/10.1016/0097-8493(89)90045-9
  * [9] Arvo, J.: Graphics Gems II. Academic Press Professional, Inc., USA (1991)
  * [10] Bao, H., Peng, Q.: Efficient polygon clipping algorithm. Zidonghua Xuebao/Acta Automatica Sinica 22(6), 741–744 (1996)
  * [11] Bhuiyan, M.: Designing a line-clipping algorithm by categorizing line dynamically and using intersection point method. Proc. - Int. Conf. Electron. Comput. Technol., ICECT pp. 22–25 (2009). https://doi.org/10.1109/ICECT.2009.79
  * [12] Blinn, J.F.: A homogeneous formulation for lines in 3 space. SIGGRAPH Comput. Graph. 11(2), 237–241 (jul 1977). https://doi.org/10.1145/965141.563900, https://doi.org/10.1145/965141.563900
  * [13] Blinn, J.: A trip down the graphics pipeline: Line clipping. IEEE Comput Graphics Appl 11(1), 98–105 (1991). https://doi.org/10.1109/38.67707
  * [14] Blinn, J., Newell, M.: Clipping using homogeneous coordinates. Proceedings of the 5th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1978 pp. 245–251 (1978). https://doi.org/10.1145/800248.807398
  * [15] Brackenbury, I.: Line clipping in interactive computer graphics. IBM technical disclosure bulletin 27(1 B), 549–552 (1984)
  * [16] Buc, D.H.: Algorithms for Line Clipping and Their Complexity. Ph.D. thesis, University of West Bohemia, University of West Bohemia, Pilsen (1999), http://graphics.zcu.cz/files/DIS_1999_Bui_Duc_Huy.pdf
  * [17] Bui, D., Skala, V.: Fast algorithms for clipping lines and line segments in E2. Visual Computer 14(1), 31–37 (1998). https://doi.org/10.1007/s003710050121
  * [18] Cai, M., Yuan, C.F., Song, J.Q., Cai, S.J.: A fast line clipping algorithm for circular windows. Journal of Computer-Aided Design and Computer Graphics 13(12), 1063–1067 (2001). https://doi.org/10.5121/ijcga.2018.8201
  * [19] Calvet, R.G.: Treatise of Plane Geometry through Geometric Algebra. Cerdanyola del Valles (2007), http://www.xtec.cat/$∼$rgonzal1/treatise-sample.pdf
  * [20] Chang, J.W., Kim, M.S.: Technical section: Efficient triangle-triangle intersection test for OBB-based collision detection. Comput. Graph. 33(3), 235–240 (Jun 2009). https://doi.org/10.1016/j.cag.2009.03.009
  * [21] Chen, C., Zhang, Z., Sun, C.: A midpoint segmentation clipping algorithm of circular window against line. IFCSTA-International Forum on Computer Science-Technology and Applications 1, 15–19 (2009). https://doi.org/10.1109/IFCSTA.2009.10
  * [22] Cheng, F., kwo Yen, Y.: A parallel line clipping algorithm and its implementation. In: Dew, P., Heywood, T., Earnshaw, R. (eds.) Parallel Processing for Computer Vision and Display. pp. 338–350. Addison-Wesley (1989)
  * [23] Cohen, D.: Incremental methods for computer graphics. Tech. rep., Harvard University, Cambridge, Massachusetts, USA (April 1969), https://apps.dtic.mil/sti/pdfs/AD0694550.pdf
  * [24] Comninos, P.: Mathematical and Computer Programming Techniques for Computer Graphics. Springer-Verlag, Berlin, Heidelberg (2005). https://doi.org/10.1007/978-1-84628-292-8
  * [25] Comninos, P.: Two-Dimensional Clipping, pp. 193–223. Springer London, London (2006). https://doi.org/10.1007/978-1-84628-292-8_6
  * [26] Coxeter, H.S.M., Beck, G.: The Real Projective Plane. Springer-Verlag, Berlin, Heidelberg (1992)
  * [27] Cychosz, J.M.: Intersecting a ray with an elliptical torus. Graphics Gems II (1991)
  * [28] Cyrus, M., Beck, J.: Generalized two- and three-dimensional clipping. Computers and Graphics 3(1), 23–28 (1978). https://doi.org/10.1016/0097-8493(78)90021-3
  * [29] Danaei, B., Karbasizadeh, N., Tale Masouleh, M.: A general approach on collision-free workspace determination via triangle-to-triangle intersection test. Robotics and Computer-Integrated Manufacturing 44, 230–241 (2017). https://doi.org/10.1016/j.rcim.2016.08.013
  * [30] Dawod, A.I.: Hardware implementation of line clipping algorithm by using fpga. Tikrit Journal of Engineering Science 18, 89–105 (2011)
  * [31] Day, J.: An algorithm for clipping lines in object and image space. Computers and Graphics 16(4), 421–426 (1992). https://doi.org/10.1016/0097-8493(92)90029-U
  * [32] Day, J.: A new two dimensional line clipping algorithm for small windows. Computer Graphics Forum 11(4), 241–245 (1992). https://doi.org/10.1111/1467-8659.1140241
  * [33] de Magalhães, S.V.G., Franklin, W.R., Andrade, M.V.A.: An efficient and exact parallel algorithm for intersecting large 3-d triangular meshes using arithmetic filters. Computer-Aided Design 120, 102801 (2020). https://doi.org/10.1016/j.cad.2019.102801, https://www.sciencedirect.com/science/article/pii/S0010448519305330
  * [34] Deng, W., Lu, G., Chen, L.: New 3D line clipping algorithm against spherical surface window. In: International Technology and Innovation Conference 2006 (ITIC 2006). pp. 894–898. IET (2006). https://doi.org/10.1049/cp:20060886
  * [35] Dev, D., Saharan, P.: Implementation of efficient line clipping algorithm. Int. J. of Innovative Technology and Exploring Engineering 8(7), 295–298 (2019)
  * [36] Devai, F.: Analysis of the Nicholl-Lee-Nicholl algorithm. Lecture Notes in Computer Science 3480(I), 726–736 (2005). https://doi.org/10.1007/11424758_75
  * [37] Devai, F.: A speculative approach to clipping line segments. Lecture Notes in Computer Science LNCS 3980, 131–140 (2006). https://doi.org/10.1007/11751540_15
  * [38] Devai, F.: Analysis technique and an algorithm for line clipping. Proceedings of the IEEE Symposium on Information Visualization pp. 157–165 (1998). https://doi.org/10.1109/IV.1998.694214
  * [39] Devillers, O., Guigue, P.: Faster Triangle-Triangle Intersection Tests. Tech. Rep. RR-4488, INRIA (June 2002), https://hal.inria.fr/inria-00072100
  * [40] Dimri, S.C.: Article: A simple and efficient algorithm for line and polygon clipping in 2-d computer graphics. Int. Journal of Computer Applications 127(3), 31–34 (October 2015). https://doi.org/10.5120/ijca2015906352
  * [41] Dimri, S.C., Tiwari, U.K., Ram, M.: An efficient algorithm to clip a 2d-polygon against a rectangular clip window. Applied Mathematics-A Journal of Chinese Universities 37, 147–158 (2022). https://doi.org/10.1007/s11766-022-4556-0
  * [42] Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2009). https://doi.org/10.1016/B978-0-12-374942-0.X0000-0
  * [43] Duvalenko, V.J., Robbins, W.E., Gyurcsik, R.S.: Improving line segment clipping. Dr Dobbs Journal 15(7), 36–& (July 1990)
  * [44] Duvanenko, V.J., Gyurcsik, R.S., Robbins, W.: Simple and efficient 2D and 3D span clipping algorithms. Computers and Graphics 17(1), 39–54 (1993). https://doi.org/10.1016/0097-8493(93)90050-J
  * [45] Duvanenko, V.J., Robbins, W.E., Gyurcsik, R.S.: Line-segment clipping revisited. DR DOBBS JOURNAL 21(1), 107–& (JAN 1996)
  * [46] Dörr, M.: A new approach to parametric line clipping. Comput Graphics (Pergamon) 14(3-4), 449–464 (1990). https://doi.org/10.1016/0097-8493(90)90067-8
  * [47] Eberly, D.H.: Game Physics. Elsevier Science Inc., USA (2003)
  * [48] Eisemann, M., Magnor, M., Grosch, T., Müller, S.: Fast ray/axis-aligned bounding box overlap tests using ray slopes. Journal of Graphics Tools 12(4), 35–46 (2007). https://doi.org/10.1080/2151237X.2007.10129248
  * [49] Elliriki, M., Reddy, C., Anand, K.: An efficient line clipping algorithm in 2D space. Int. Arab J. of Info. Tech. 16(5), 798–807 (2019), https://iajit.org/PDF/September%202019,%20No.%205/11103.pdf
  * [50] Elsheikh, A., Elsheikh, M.: A reliable triangular mesh intersection algorithm and its application in geological modelling. Engineering with Computers 30(1), 143–157 (2014). https://doi.org/10.1007/s00366-012-0297-3
  * [51] Evangeline, D., Anitha, S.: 2D polygon clipping using shear transformation: An extension of shear based 2D line clipping. 2014 IEEE Int.Conf.on Advanced Communications, Control and Computing Technologies pp. 1379–1383 (2014). https://doi.org/10.1109/ICACCCT.2014.7019326
  * [52] Ferguson, R.S.: Practical Algorithms for 3D Computer Graphics. A. K. Peters, Ltd., USA, 2nd edn. (2013)
  * [53] Foley, J.D., van Dam, A., Feiner, S., Hughes, J.F.: Computer graphics - principles and practice, 2nd Edition. Addison-Wesley (1990)
  * [54] Foster, E.L., Hormann, K., Popa, R.T.: Clipping simple polygons with degenerate intersections. Computers & Graphics: X 2, Article 100007, 10 pages (Dec 2019). https://doi.org/10.1016/j.cagx.2019.100007
  * [55] Glassner, A.S. (ed.): Graphics Gems. Academic Press Professional, Inc., USA (1990)
  * [56] Govil-Pai, S.: Principles of Computer Graphics: Theory and Practice Using OpenGL and Maya. Springer-Verlag, Berlin, Heidelberg (2005)
  * [57] Greiner, G., Hormann, K.: Efficient clipping of arbitrary polygons. ACM Trans. Graph. 17(2), 71–83 (April 1998). https://doi.org/10.1145/274363.274364
  * [58] Guigue, P., Devillers, O.: Fast and robust triangle-triangle overlap test using orientation predicates. Journal of Graphics Tools 8(1), 25–32 (2003). https://doi.org/10.1080/10867651.2003.10487580
  * [59] Guo, H.: Modern Mathematics and Applications in Computer Graphics and Vision. World Scientific Publ., Singapore (2014). https://doi.org/0.1142/8703, 10.1142/8703
  * [60] Gupta, R., Tripathi, V., Singh, K., Pathak, N., Rastogi, R.: An innovative and easy approach for clipping curves along a circular window. Proceedings - 2016 2nd International Conference on Computational Intelligence and Communication Technology, CICT 2016 pp. 638–643 (2016). https://doi.org/10.1109/CICT.2016.132
  * [61] Harrington, S.: Computer Graphics: A Programming Approach, 2nd Ed. McGraw-Hill, Inc., USA (1987)
  * [62] Hattab, A., Yusof, Y.: Line clipping based on parallelism approach and midpoint intersection. AIP Conference Proceedings 1602, 371–374 (2014). https://doi.org/10.1063/1.4882513
  * [63] Havel, J., Herout, A.: Yet faster ray-triangle intersection (using SSE4). IEEE Transactions on Visualization and Computer Graphics 16(3), 434–438 (2010). https://doi.org/10.1109/TVCG.2009.73
  * [64] Hearn, D.D., Baker, M.P., Carithers, W.: Computer Graphics with OpenGL. Prentice Hall Press, USA, 4th edn. (2010)
  * [65] Heckbert, P.S. (ed.): Graphics Gems IV. Academic Press Professional, Inc., USA (1994)
  * [66] Held, M.: Erit: A collection of efficient and reliable intersection tests. J. Graph. Tools 2(4), 25–44 (Jan 1998). https://doi.org/10.1080/10867651.1997.10487482
  * [67] Hildenbrand, D.: Foundations of Geometric Algebra Computing. Springer Publishing Company, Incorporated (2012). https://doi.org/10.1007/978-1-84628-997-2
  * [68] Hill, F.S., Kelley, S.M.: Computer Graphics Using OpenGL (3rd Edition). Prentice-Hall, Inc., USA (2006)
  * [69] Huang, W.: Line clipping algorithm of affine transformation for polygon. Lecture Notes in Computer Science 7995 LNCS, 55–60 (2013). https://doi.org/10.1007/978-3-642-39479-9_7
  * [70] Huang, W., Wangyong: A novel algorithm for line clipping. Proceedings - 2009 International Conference on Computational Intelligence and Software Engineering, CiSE 2009 pp. 1–5 (2009). https://doi.org/10.1109/CISE.2009.5366550
  * [71] Huang, Y., Liu, Y.: An algorithm for line clipping against a polygon based on shearing transformation. Computer Graphics Forum 21(4), 683–688 (2002). https://doi.org/10.1111/1467-8659.00626
  * [72] Hughes, J.F., van Dam, A., McGuire, M., Sklar, D.F., Foley, J.D., Feiner, S.K., Akeley, K.: Computer Graphics - Principles and Practice, 3rd Edition. Addison-Wesley (2014)
  * [73] Iraji, M.S., Mazandarani, A., Motameni, H.: An efficient line clipping algorithm based on Cohen-Sutherland line clipping algorithm. American Journal of Scientific Research 14(1), 65–71 (2011), https://www.researchgate.net/publication/275964580_An_Efficient_Line_Clipping _Algorithm_based_on_Cohen-Sutherland_Line_Clipping_Algorithm
  * [74] Jiang, B., Han, J.: Improvement in the Cohen-Sutherland line segment clipping algorithm. IEEE Int. Conf. on Granular Computing, GrC 2013 pp. 157–161 (2013). https://doi.org/10.1109/GrC.2013.6740399
  * [75] Jianrong, T.: A new algorithm of polygon clipping against rectangular window based on the endpoint and intersection-point encoding. Journal of Engineering Graphics (2006)
  * [76] Johnson, M.: Proof by duality: or the discovery of “new” theorems. Mathematics Today December, 138–153 (1996)
  * [77] Jokanovic, S.: Two-dimensional line segment–triangle intersection test: revision and enhancement. Visual Computer 35(10), 1347–1359 (2019). https://doi.org/10.1007/s00371-018-01614-1
  * [78] Kaijian, S., Edwards, J., Cooper, D.: An efficient line clipping algorithm. Computers and Graphics 14(2), 297–301 (1990). https://doi.org/10.1016/0097-8493(90)90041-U
  * [79] Kanatani, K.: Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for Computer Vision and Graphics. A. K. Peters, Ltd., USA (2015). https://doi.org/10.1201/b18273
  * [80] Kirk, D. (ed.): Graphics Gems III. Academic Press Professional, Inc., USA (1992)
  * [81] Kodituwakku, R., Wijeweera, K.R.: An efficient line clipping algorithm for 3D space. Int. journal of Advanced Research in Computer Science and Software Engineering 2(5) (2012)
  * [82] Kodituwakku, S.R., Wijeweera, K.R., Chamikara, M.A.P.: An efficient algorithm for line clipping in computer graphics programming. Ceylon Journal of Science 17(1), 1–7 (2013), https://www.researchgate.net/publication/261288113_An_Efficient_Algorithm _for_Line_Clipping_in_Computer_Graphics_Programming
  * [83] Kolingerova, I.: Convex polyhedron-line intersection detection using dual representation. Visual Computer 13(1), 42–49 (1997). https://doi.org/10.1007/s003710050088
  * [84] Kolingerová, I.: 3d-line clipping algorithms - a comparative study. The Visual Computer 11(2), 96–104 (1994). https://doi.org/10.1007/BF01889980
  * [85] Konashkova, A.: Line - convex polyhedron intersection using vertex connections table. Applied Mathematical Sciences 8(21-24), 1177–1186 (2014). https://doi.org/10.12988/ams.2014.4133
  * [86] Konashkova, A.: Modified Skala’s plane tested algorithm for line-polyhedron intersection. Applied Mathematical Sciences 9(61-64), 3097–3103 (2015). https://doi.org/10.12988/ams.2015.52169
  * [87] Kong, D.H., Yin, B.C.: The improvement on the algorithm of Cohen-Surtherland line clipping. CAD/GRAPHICS 2001 pp. 807–810 (2001)
  * [88] Krammer, G.: A line clipping algorithm and its analysis. Computer Graphics Forum 11(3), 253–266 (1992). https://doi.org/10.1111/1467-8659.1130253
  * [89] Kui Liu, Y., Qiang Wang, X., Zhe Bao, S., Gomboši, M., Žalik, B.: An algorithm for polygon clipping, and for determining polygon intersections and unions. Computers and Geosciences 33(5), 589–598 (2007). https://doi.org/10.1016/j.cageo.2006.08.008
  * [90] Kumar, J., Awasthi, A.: Modified trivial rejection criteria in Cohen-Sutherland line clipping algorithm. Commun. Comput. Info. Sci. 125 CCIS, 1–10 (2011). https://doi.org/10.1007/978-3-642-18440-6_1
  * [91] Kumar, P., Patel, F., Kanna, R.: An efficient line clipping algorithm for circular windows using vector calculus and parallelization. International Journal of Computational Geometry and Applications 8, 01–08 (2018). https://doi.org/10.5121/IJCGA.2018.8201
  * [92] Kuzmin, Y.: Bresenham’s line generation algorithm with built‐in clipping. Computer Graphics Forum 14(5), 275–280 (1995). https://doi.org/10.1111/1467-8659.1450275
  * [93] Lagae, A., Dutré, P.: An efficient ray-quadrilateral intersection test. Journal of Graphics Tools 10(4), 23–32 (2005). https://doi.org/10.1080/2151237X.2005.10129208
  * [94] Landier, S.: Boolean operations on arbitrary polygonal and polyhedral meshes. CAD Computer Aided Design 85, 138–153 (2017). https://doi.org/10.1016/j.cad.2016.07.013
  * [95] Lengyel, E.: Mathematics for 3D Game Programming and Computer Graphics, Third Edition. Course Technology Press, Boston, MA, USA, 3rd edn. (2011)
  * [96] Li, H.: Analysis and implementation of Cohen_Sutherland line clipping algorithm. In: Proc. of the 2016 Int. Conf. on Sensor Network and Computer Engineering. pp. 482–485. Atlantis Press (2016/07). https://doi.org/https://doi.org/10.2991/icsnce-16.2016.94
  * [97] Li, W.: Bisearch-based line clipping algorithm against a convex polygonal window. Journal of Computer-Aided Design and Computer Graphics 17(5), 962–965 (2005)
  * [98] Li, Z., He, D., Wang, J., Wang, M.: An improved algorithm of Cohen-Sutherland line clipping. WIT Transactions on Information and Communication Technologies 49, 575–582 (2014)
  * [99] Li, Z.Q., He, Y., Tian, Z.J.: Overlapping area computation between irregular polygons for its evolutionary layout based on convex decomposition. Journal of Software 7(2), 485–492 (2012). https://doi.org/10.4304/jsw.7.2.485-492
  * [100] Li, Z., Lei, G.: Modified Sutherland-Cohen line clipping algorithm (in Chinese). Computer Engineering and Applications 48(34), 175 (2012), https://caod.oriprobe.com/articles/31582699/Modified_Sutherland_Cohen _line_clipping_algorithm.htm
  * [101] Liang, Y.D., Barsky, B.A.: A new concept and method for line clipping. ACM Transactions on Graphics (TOG) 3(1), 1–22 (1984). https://doi.org/10.1145/357332.357333
  * [102] Liang, Y.D., Barsky, B.A.: An analysis and algorithm for polygon clipping. Commun. ACM 26(11), 868–877 (November 1983). https://doi.org/10.1145/182.358439
  * [103] Llanas, B., Sainz, F.: A local search algorithm for ray-convex polyhedron intersection. Computational Optimization and Applications 51(2), 533–550 (2012). https://doi.org/10.1007/s10589-010-9354-2
  * [104] Lo, S., Wang, W.: A fast robust algorithm for the intersection of triangulated surfaces. Engineering with Computers 20, 11–21 (2004). https://doi.org/10.1007/s00366-004-0277-3
  * [105] Lu, G., Wu, X.: Midpoint-subdivision line clipping algorithm based on filtering technique. Journal of Computer-Aided Design and Computer Graphics 14(6), 513–517 (2002)
  * [106] Lu, G., Wu, X., Peng, Q.: An efficient line clipping algorithm based on adaptive line rejection. Computers and Graphics (Pergamon) 26(3), 409–415 (2002). https://doi.org/10.1016/S0097-8493(02)00084-5
  * [107] Lu, G., Xing, J., Tan, J.: New clipping algorithm of line against circular window with multi-encoding approach. Journal of Computer-Aided Design and Computer Graphics 14(12), 1133–1137 (2002)
  * [108] Mahovsky, J., Wyvill, B.: Fast ray-axis aligned bounding box overlap tests with plucker coordinates. Journal of Graphics Tools 9(1), 35–46 (2004). https://doi.org/10.1080/10867651.2004.10487597
  * [109] Maillot, P.G.: Three-dimensional homogeneous clipping of triangle strips. Elsevier Inc. (1991). https://doi.org/10.1016/B978-0-08-050754-5.50050-5
  * [110] Maillot, P.G.: A new, fast method for 2D polygon clipping: Analysis and software implementation. ACM Transactions on Graphics (TOG) 11(3), 276–290 (1992). https://doi.org/10.1145/130881.130894
  * [111] Maonica, B., Das, P., Ramteke, P.B., Koolagudi, S.G.: 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. pp. 391–399. Springer Singapore, Singapore (2017). https://doi.org/10.1007/978-981-10-1675-2_39
  * [112] Martinez, F., Rueda, A., Feito, F.: A new algorithm for computing boolean operations on polygons. Computers and Geosciences 35(6), 1177–1185 (2009). https://doi.org/10.1016/j.cageo.2008.08.009
  * [113] Matthes, D., Drakopoulos, V.: Another simple but faster method for 2D line clipping. International Journal of Computer Graphics & Animation (IJCGA) 9(1/2/3) (July 2019). https://doi.org/10.5121/ijcga.2019.9301, https://aircconline.com/ijcga/V9N3/9319ijcga01.pdf
  * [114] Matthes, D., Drakopoulos, V.: A simple and fast line-clipping method as a scratch extension for computer graphics education. Computer Science and Information Technology 7, 40–47 (2019). https://doi.org/10.13189/csit.2019.070202
  * [115] Matthes, D., Drakopoulos, V.: A very simple algorithm for line segment clipping against a convex polygon, private communication
  * [116] Mccoid, C., Gander, M.J.: A provably robust algorithm for triangle-triangle intersections in floating-point arithmetic. ACM Trans. Math. Softw. 48(2) (may 2022). https://doi.org/10.1145/3513264, https://doi.org/10.1145/3513264
  * [117] McLaurin, D., Marcum, D., Remotigue, M., Blades, E.: Repairing unstructured triangular mesh intersections. International Journal for Numerical Methods in Engineering 93(3), 266–275 (2013). https://doi.org/10.1002/nme.4385
  * [118] Melero, F., Aguilera, A., Feito, F.: Fast collision detection between high resolution polygonal models. Computers and Graphics (Pergamon) 83, 97–106 (2019). https://doi.org/10.1016/j.cag.2019.07.006
  * [119] Meriaux, M.: A two-dimensional clipping divider. Eurographics Conference Proceedings (1984). https://doi.org/10.2312/eg.19841031
  * [120] Molla, R., Jorquera, P., Vivo, R.: Fixed-point arithmetic line clipping. WSCG’2003 Proc. pp. 93–96 (2003)
  * [121] Mortenson, M.E.: Computer Graphics: An Introduction to the Mathematics and Geometry. Industrial Press, Inc., USA (1988)
  * [122] Möller, T., Trumbore, B.: Fast, minimum storage ray-triangle intersection. Journal of Graphics Tools 2(1), 21–28 (1997). https://doi.org/10.1080/10867651.1997.10487468
  * [123] Newman, W.M., Sproull, R.F.: Principles of Interactive Computer Graphics (2nd Ed.). McGraw-Hill, Inc., USA (1979)
  * [124] Nicholl, T., Lee, D., Nicholl, R.: An efficient new algorithm for 2-d line clipping: Its development and analysis. Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987 pp. 253–262 (1987). https://doi.org/10.1145/37401.37432
  * [125] Nielsen, H.: Line clipping using semi‐homogeneous coordinates. Computer Graphics Forum 14(1), 3–16 (1995). https://doi.org/10.1111/1467-8659.1410003
  * [126] Nisha, A.: Comparison of various line clipping algorithms: Review. International Journal of Advanced Research in Computer Science and Software Engineering 7(1) (2017). https://doi.org/10.23956/ijarcsse/V7I1/0149
  * [127] Nisha, A.: A review: Comparison of line clipping algorithms in 3D space. International Journal of Advanced Research (IJAR) 5(1) (2017). https://doi.org/10.21474/IJAR01/3022
  * [128] Nishita, T., Johan, H.: A scan line algorithm for rendering curved tubular objects. Proc. - Pac. Conf. Comput. Graph. Appl., Pac. Graphics pp. 104–105 (1999). https://doi.org/10.1109/PCCGA.1999.803352
  * [129] Pandey, A., Jain, S.: Article: Comparison of various line clipping algorithm for improvement. International Journal of Modern Engineering Research 3(1), 69–74 (January-February 2013)
  * [130] Petrie, F., Mills, S.: Real time ray tracing of analytic and implicit surfaces. International Conference Image and Vision Computing New Zealand 2020-November (2020). https://doi.org/10.1109/IVCNZ51579.2020.9290653
  * [131] Pharr, M., Jakob, W., Humphreys, G.: Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 3rd edn. (2016)
  * [132] Platis, N., Theoharis, T.: Fast ray-tetrahedron intersection using plucker coordinates. Journal of Graphics Tools 8(4), 37–48 (2003). https://doi.org/10.1080/10867651.2003.10487593
  * [133] Raja, S.: Line and polygon clipping techniques on natural images - a mathematical solution and performance evaluation. Int. Journal of Image and Graphics 19(2) (2019). https://doi.org/10.1142/S0219467819500128
  * [134] Rajan, K., Hashemi, S., Karpuzcu, U., Doggett, M., Reda, S.: Dual-precision fixed-point arithmetic for low-power ray-triangle intersections. Computers and Graphics (Pergamon) 87, 72–79 (2020). https://doi.org/10.1016/j.cag.2020.01.006
  * [135] Rappoport, A.: An efficient algorithm for line and polygon clipping. The Visual Computer 7(1), 19–28 (1991). https://doi.org/10.1007/BF01994114
  * [136] Ray, B.K.: An alternative algorithm for line clipping. Journal of Graphics Tools 16(1), 12–24 (2012). https://doi.org/10.1080/2151237X.2012.641824
  * [137] Ray, B.K.: A line segment clipping algorithm in 2D. Int.J.of Computer Graphics 3(2), 51–76 (2012)
  * [138] Ray, B.K.: A procedure to clip line segment. Int.J.of Computer Graphics 5(1), 9–19 (2014). https://doi.org/10.14257/ijcg.2014.5.1.02
  * [139] Ray, B.K.: Line clipping against arbitrary polygonal window. Int.J.of Computer Graphics 6(1), 12–24 (2015). https://doi.org/10.14257/ijcg.2015.6.1.01
  * [140] Rivero, M., Feito, F.: Boolean operations on general planar polygons. Computers and Graphics (Pergamon) 24(6), 881–896 (2000). https://doi.org/10.1016/S0097-8493(00)00090-X
  * [141] Rogers, D., Rybak, L.: On an efficient general line-clipping algorithm. IEEE Comput Graphics Appl 5(1), 82–86 (1985). https://doi.org/10.1109/MCG.1985.276298
  * [142] Roy, U., Dasari, V.: Implementation of a polygonal algorithm for surface–surface intersections. Computers & Industrial Engineering 34(2), 399–412 (1998). https://doi.org/10.1016/S0360-8352(97)00276-3
  * [143] Sabharwal, C., Leopold, J., McGeehan, D.: Triangle-triangle intersection determination and classification to support qualitative spatial reasoning. Polibits 48, 13–22 (12 2013). https://doi.org/10.17562/PB-48-2
  * [144] Sabharwal, C.L., Leopold, J.L.: A triangle-triangle intersection algorithm. Computers and Graphics –(May), 27–35 (2015). https://doi.org/10.5121/csit.2015.51003
  * [145] Sabharwal, C.L., Leopold, J.L.: 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, p. 41. IGI Global (2016). https://doi.org/10.4018/978-1-4666-8723-3.ch008
  * [146] Salomon, D.: Computer Graphics and Geometric Modeling. Springer-Verlag, Berlin, Heidelberg, 1st edn. (1999)
  * [147] Salomon, D.: Transformations and Projections in Computer Graphics. Springer-Verlag, Berlin, Heidelberg (2006)
  * [148] Salomon, D.: The Computer Graphics Manual. Springer (2011). https://doi.org/10.1007/978-0-85729-886-7
  * [149] Schneider, P.J., Eberly, D.H.: Geometric Tools for Computer Graphics. The Morgan Kaufmann Series in Computer Graphics, Morgan Kaufmann, San Francisco (2003). https://doi.org/10.1016/B978-1-55860-594-7.50025-4
  * [150] Segura, R., Feito, F.: An algorithm for determining intersection segment-polygon in 3D. Computers and Graphics (Pergamon) 22(5), 587–592 (1998). https://doi.org/10.1016/s0097-8493(98)00064-8
  * [151] Sharma, M., Kaur, J.: An improved polygon clipping algorithm based on affine transformation. Advances in Intelligent Systems and Computing 379(1), 783–792 (2016). https://doi.org/10.1007/978-81-322-2517-1_75
  * [152] Sharma, N., Manohar, S.: Line clipping revisited: Two efficient algorithms based on simple geometric observations. Computers and Graphics 16(1), 51–54 (1992). https://doi.org/10.1016/0097-8493(92)90071-3
  * [153] Sharma, N., Manohar, S.: Three dimensional line-clipping by systematic enumeration. IFIP Trans B Comput Appl Technol 1(9), 225–232 (1993)
  * [154] Shen, H., Heng, P.A., Tang, Z.: A fast triangle-triangle overlap test using signed distances. Journal of Graphics Tools 8(1), 17–23 (2003). https://doi.org/10.1080/10867651.2003.10487579
  * [155] Shirley, P., Marschner, S.: Fundamentals of Computer Graphics. A. K. Peters, Ltd., USA, 3rd edn. (2009)
  * [156] Singh, R., Lumar, A.: RJ-ASHI algorithm: A new polygon/line clipping algorithm for 2D space. Int. journal of Advanced Research in Computer Science and Software Engineering 6, 215–219 (11 2016)
  * [157] Skala, V.: An efficient algorithm for line clipping by convex polygon. Computers and Graphics 17(4), 417–421 (1993). https://doi.org/10.1016/0097-8493(93)90030-D
  * [158] Skala, V.: O(lg N) line clipping algorithm in E2. Computers and Graphics 18(4), 517–524 (1994). https://doi.org/10.1016/0097-8493(94)90064-7
  * [159] Skala, V.: An efficient algorithm for line clipping by convex and non-convex polyhedra in E3. Computer Graphics Forum 15(1), 61–68 (1996). https://doi.org/10.1111/1467-8659.1510061
  * [160] Skala, V.: Line clipping in E2 with O(1) processing complexity. Comput Graphics (Pergamon) 20(4), 523–530 (1996). https://doi.org/10.1016/0097-8493(96)00024-6
  * [161] Skala, V.: Line clipping in E3 with expected complexity O(1). Machine Graphics and Vision 5(4), 551–562 (1996)
  * [162] Skala, V.: 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 (1996)
  * [163] Skala, V.: A fast algorithm for line clipping by convex polyhedron in E3. Computers and Graphics (Pergamon) 21(2), 209–214 (1997). https://doi.org/10.1016/s0097-8493(96)00084-2
  * [164] Skala, V.: A new line clipping algorithm with hardware acceleration. Proceedings of Computer Graphics International Conference, CGI pp. 270–273 (2004). https://doi.org/10.1109/CGI.2004.1309220
  * [165] Skala, V.: A new approach to line and line segment clipping in homogeneous coordinates. Visual Computer 21(11), 905–914 (2005). https://doi.org/10.1007/s00371-005-0305-3
  * [166] Skala, V.: Barycentric coordinates computation in homogeneous coordinates. Computers and Graphics (Pergamon) 32(1), 120–127 (2008). https://doi.org/10.1016/j.cag.2007.09.007
  * [167] Skala, V.: Intersection computation in projective space using homogeneous coordinates. Intl. J. Image Graphics 8(4), 615–628 (2008). https://doi.org/10.1142/S021946780800326X
  * [168] Skala, V.: 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
  * [169] Skala, V.: S-clip E2: A new concept of clipping algorithms. SIGGRAPH Asia Posters, SA pp. 1–2 (2012). https://doi.org/10.1145/2407156.2407200
  * [170] Skala, V.: Line-torus intersection for ray tracing: Alternative formulations. WSEAS Trans. Comput. 12(7), 288–297 (2013)
  * [171] Skala, V.: Summation problem revisited - more robust computation. In: Recent Advances in Computer Science. pp. 56–64 (2013)
  * [172] Skala, V.: A new approach to line - sphere and line - quadrics intersection detection and computation. AIP Conference Proceedings 1648, 1–4 (2015). https://doi.org/10.1063/1.4913058
  * [173] Skala, V.: Optimized line and line segment clipping in E2 and geometric algebra. Ann. Math. Inf. 52, 199–215 (2020). https://doi.org/10.33039/ami.2020.05.001
  * [174] Skala, V.: Efficient intersection computation of the Bezier and Hermite curves with axis aligned bounding box. WSEAS Transactions on Systems 20, 320–323 (2021). https://doi.org/10.37394/23202.2021.20.36
  * [175] Skala, V.: A new coding scheme for line segment clipping in E2. Lecture Notes in Computer Science LNCS 12953, 16–29 (2021). https://doi.org/10.1007/978-3-030-86976-2_2
  * [176] Skala, V.: A novel line convex polygon clipping algorithm in E2 with parallel processing modification. Lecture Notes in Computer Science LNCS Vol.12953, 3–15 (2021). https://doi.org/10.1007/978-3-030-86976-2_1
  * [177] Skala, V., Bui, D.: Faster algorithm for line clipping against a pyramid in E3. Machine Graphics and Vision 9(4), 841–850 (2000)
  * [178] Skala, V., Bui, D.: Extension of the Nicholls-Lee-Nichols algorithm to three dimensions. Visual Comput 17(4), 236–242 (2001). https://doi.org/10.1007/s003710000094
  * [179] Skala, V., Huy, B.: Two new algorithms for line clipping in E2 and their comparison. Machine Graphics and Vision 9(1/2), 297–306 (2000)
  * [180] Skala, V., Kolingerova, I., Blaha, P.: A comparison of 2D line clipping algorithms. Machine Graphics and Vision 3(4), 625–633 (1995)
  * [181] Skala, V.: Algorithms for 2D Line Clipping. In: Hansmann, W., Hopgood, F.R.A., Straßer, W. (eds.) EG 1989 proceedings. Eurographics Association (1989). https://doi.org/10.2312/egtp.19891026
  * [182] Skala, V.: Algorithms for Clipping Quadratic Arcs. In: Chua, T., Kunii, T. (eds.) CGI proceedings. pp. 255–268. Springer (1990). https://doi.org/10.1007/978-4-431-68123-6_16
  * [183] Skala, V.: Clipping Algorithm - Habilitation thesis. University of West Bohemia (1990), http://afrodita.zcu.cz/$∼$skala/EDU-PUB/Habilitace-komplet.pdf, (partially in Czech)
  * [184] Skala, V.: 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). https://doi.org/10.1145/2668975.2668976
  * [185] Skala, V., Lederbuch, P.: 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. pp. 281–287. Comenius University. Slovakia (1996), https://dspace5.zcu.cz/handle/11025/11808
  * [186] Skala, V., Lederbuch, P., Sup, B.: A Comparison of O(1) and Cyrus-Beck Line Clipping Algorithm in E2 and E3. In: SCCG96 Conference proceedings. pp. 17–44. Comenius University. Slovakia (1996), https://dspace5.zcu.cz/handle/11025/11806
  * [187] Slater, M., Barsky, B.: 2D line and polygon clipping based on space subdivision. The Visual Computer 10(7), 407–422 (1994). https://doi.org/10.1007/BF01900665
  * [188] Sobkow, M., Pospisil, P., Yang, Y.H.: A fast two-dimensional line clipping algorithm via line encoding. Computers and Graphics 11(4), 459–467 (1987). https://doi.org/10.1016/0097-8493(87)90061-6
  * [189] Sproull, R.F., Sutherland, I.E.: A clipping divider. In: Fall Joint Computer Conference Proc., Dec. 9-11, 1968, Part I. p. 765–775. AFIPS’68 (Fall, part I), Association for Computing Machinery, New York, NY, USA (1968). https://doi.org/10.1145/1476589.1476687
  * [190] Stolfi, J.: Oriented Projective Geometry. Academic Press Professional, Inc., USA (1991)
  * [191] Sun, C., Wang, W., Li, J., Wu, E.: Line clipping against a polygon through convex segments. Journal of Computer-Aided Design and Computer Graphics 18(12), 1799–1805 (2006)
  * [192] Sutherland, I.E.: Display windowing by clipping (May 2 1972), https://patents.google.com/patent/US3639736A/en
  * [193] Sutherland, I.E., Hodgman, G.W.: Reentrant polygon clipping. Commun. ACM 17(1), 32–42 (Jan 1974). https://doi.org/10.1145/360767.360802
  * [194] Tang, L.L., He, Y.J.: A linear time algorithm for the line clipping against concave polygon. Proceedings - 2009 International Conference on Information Engineering and Computer Science, ICIECS 2009 pp. 1–4 (2009). https://doi.org/10.1109/ICIECS.2009.5364626
  * [195] Theoharis, T., Platis, N., Papaioannou, G., Patrikalakis, N.: Graphics and Visualization: Principles & Algorithms (1st ed.). A K Peters/CRC Press (2008). https://doi.org/10.1201/b10676
  * [196] Thomas, A.: Integrated Graphic and Computer Modelling. Springer Publishing Company, Incorporated, 1 edn. (2008)
  * [197] Tran, C.H.: Fast clipping algorithms for computer graphics. Ph.D. thesis, University of British Columbia (1986). https://doi.org/http://dx.doi.org/10.14288/1.0096928, https://open.library.ubc.ca/collections/ubctheses/831/items/1.0096928
  * [198] Tropp, O., Tal, A., Shimshoni, I.: A fast triangle to triangle intersection test for collision detection. Computer Animation and Virtual Worlds 17(5), 527–535 (2006). https://doi.org/10.1002/cav.115
  * [199] Van Wyk, C.J.: Clipping to the boundary of a circular-arc polygon. Computer Vision, Graphics, and Image Processing 25(3), 383–392 (1984). https://doi.org/10.1016/0734-189X(84)90202-0
  * [200] Vatti, B.R.: A generic solution to polygon clipping. Commun. ACM 35(7), 56–63 (Jul 1992). https://doi.org/10.1145/129902.129906
  * [201] Vince, J.: Geometric Algebra: An Algebraic System for Computer Games and Animation. Springer Publishing Company, Incorporated, 1st edn. (2009)
  * [202] Vince, J.: Introduction to the Mathematics for Computer Graphics. Springer-Verlag, Berlin, Heidelberg, 3rd edn. (2010), https://link.springer.com/book/10.1007/978-1-4471-6290-2#toc
  * [203] Vince, J.: Matrix Transforms for Computer Games and Animation. Springer Publishing Company, Incorporated (2012)
  * [204] Vince, J.A.: Geometric Algebra for Computer Graphics. Springer-Verlag TELOS, Santa Clara, CA, USA, 1 edn. (2008). https://doi.org/10.1007/978-1-84628-997-2
  * [205] Wang, H., Chong, S.: 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 (2016). https://doi.org/10.3969/j.issn.1001-0505.2016.04.005
  * [206] Wang, H., Wu, R., Cai, S.: A new algorithm for two-dimensional line clipping via geometric transformation. Journal of Computer Science and Technology 13(5), 410–416 (1998). https://doi.org/10.1007/bf02948499
  * [207] Wang, H., Wu, R., Cai, S.: New efficient line clipping algorithm based on geometric transformation. Ruan Jian Xue Bao/Journal of Software 9(10), 728–733 (1998)
  * [208] Wang, J., Lu, G.D., Peng, Q.S., Wu, X.H.: Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting. Journal of Zhejiang University: Science 6 A(SUPPL.), 100–107 (2005). https://doi.org/10.1631/jzus.2005.AS0100
  * [209] Wang, J., Cui, C., Gao, J.: An efficient algorithm for clipping operation based on trapezoidal meshes and sweep-line technique. Advances in Engineering Software 47(1), 72–79 (2012). https://doi.org/10.1016/j.advengsoft.2011.12.003
  * [210] Wang, X., Xue, Y., Fang, F., Chen, G.: From probability model to a fast line clipping algorithm. CAD/GRAPHICS 2001 pp. 802–806 (2001)
  * [211] Watt, A.: Fundamentals of Three-Dimensional Computer Graphics. Addison-Wesley Longman Publishing Co., Inc., USA (1990)
  * [212] Wei, L.Y.: A faster triangle-to-triangle intersection test algorithm. Computer Animation and Virtual Worlds 25(5-6), 553–559 (2014). https://doi.org/10.1002/cav.1558
  * [213] Wei, W., Ma, P., Lin, W.: An improved Cohen-Sutherland region encoding algorithm. Applied Mechanics and Materials 239-240, 1313–1317 (2013). https://doi.org/10.4028/www.scientific.net/AMM.239-240.1313
  * [214] Weiler, K.: Polygon comparison using a graph representation. Proc. Annu. Conf. Comput. Graph. Interact. Tech., SIGGRAPH pp. 10–18 (1980). https://doi.org/10.1145/800250.807462
  * [215] Weiler, K., Atherton, P.: Hidden surface removal using polygon area sorting. Proc. Annu. Conf. Comput. Graph. Interact. Tech., SIGGRAPH pp. 214–222 (1977). https://doi.org/10.1145/563858.563896
  * [216] Wijeweera, K., Kodituwakku, S.R., Pathum Chamikara, M.A.: A novel and efficient approach for line segment clipping against a convex polygon. Ruhuna Journal of Science 10(2), 161–173 (2019). https://doi.org/10.4038/rjs.v10i2.81, https://rjs.sljol.info/articles/abstract/10.4038/rjs.v10i2.81/
  * [217] Wikipedia: Clipping (computer graphics) - Wikipedia, the free encyclopedia (2021), https://en.wikipedia.org/wiki/Clipping_(computer_graphics), [Online; accessed 28-July-2021]
  * [218] Wikipedia: IEEE 754 - Wikipedia, the free encyclopedia (2021), https://en.wikipedia.org/wiki/IEEE_754, [Online; accessed 11-July-2021]
  * [219] Wikipedia: Ray tracing (graphics) - Wikipedia, the free encyclopedia (2021), https://en.wikipedia.org/wiki/Ray_tracing_(graphics), [Online; accessed 3-August-2021]
  * [220] Williams, A., Barrus, S., Morley, R.K., Shirley, P.: An efficient and robust ray-box intersection algorithm. In: ACM SIGGRAPH 2005 Courses. p. 9–es. ACM, New York, NY, USA (2005). https://doi.org/10.1145/1198555.1198748
  * [221] Wu, Q., Huang, X., Han, Y.: A clipping algorithm for parabola segments against circular windows. Computers & Graphics 30(4), 540–560 (2006). https://doi.org/https://doi.org/10.1016/j.cag.2006.03.001, https://www.sciencedirect.com/science/article/pii/S0097849306000732
  * [222] Wu, Z., Gou, C., Yang, D., Luo, Z.: Line clipping algorithm against arbitrary polygons. Journal of Computer-Aided Design and Computer Graphics 16(2), 228–233 (2004)
  * [223] Xiao, L., Mei, G., Cuomo, S., Xu, N.: Comparative investigation of GPU-accelerated triangle-triangle intersection algorithms for collision detection. Multimedia Tools and Applications (2020). https://doi.org/10.1007/s11042-020-09066-3
  * [224] Xie, L., Li, P., Zhou, M., Wang, X.: An clipping general polygons in regular girds algorithm base on successive encoding. ICCASM - Int. Conf. Comput. Appl. Syst. Model., Proc. 4, V4709–V4713 (2010). https://doi.org/10.1109/ICCASM.2010.5619427
  * [225] Yang, W.: New approach to line clipping in computer graphics display. Zhongnan Kuangye Xueyuan Xuebao 18(1), 73–78 (1988)
  * [226] Ye, X., Huang, L., Wang, L., Xing, H.: An improved algorithm for triangle to triangle intersection test. ICIA 2015 proceedings pp. 2689–2694 (2015). https://doi.org/10.1109/ICInfA.2015.7279740
  * [227] Zhang, M., Sabharwal, C.: An efficient implementation of parametric line and polygon clipping algorithm. Proceedings of the ACM Symposium on Applied Computing pp. 796–800 (2002). https://doi.org/10.1145/508791.508945
  * [228] Zheng, J., Millham, C.: A linear programming method for ray-convex polyhedron intersection. Computers and Graphics 15(2), 195–204 (1991). https://doi.org/10.1016/0097-8493(91)90073-Q