Informatica

The conversion of a point $\mathbf{x}={[x,y:w]^{T}}$ from the homogeneous coordinates to the Euclidean representation $\mathbf{X}=(X,Y)$ is given as: where w is the homogeneous coordinate.1

It means that a point $\mathbf{X}\in {E^{2}}$ is represented by a line in the projective space ${[x,y:w]^{T}}$ without the origin, which represents a point in infinity, see Fig. 1.

The extension to the ${E^{3}}$ case is straightforward (Foley et al., 1990). where $\mathbf{x}={[x,y,z:w]^{T}}$.

The use of the projective extension of the Euclidean space is convenient not only for geometric transformations, as it replaces addition by multiplication in the case of translation operation, but it enables to represent a point in infinity. Also, it enables to express some geometric entities in a more compact form, e.g. a line in the ${E^{2}}$ case as: where $\mathbf{a}={[a,b:c]^{T}}$, and $\mathbf{x}={[x,y:w]^{T}}$.

It is necessary to note that $(a,b)$ represents the normal vector2 of a line, while c is related to the distance of a line from the origin of the Euclidean coordinate system. Similarly, a plane in the ${E^{3}}$ case is defined as: where $\mathbf{a}={[a,b,c:d]^{T}}$ and $\mathbf{x}={[x,y,z:w]^{T}}$. However, it is necessary to distinguish vectors, as “movable” entities, from “frames”, which have the origin as the reference point. It is necessary to note that metric is not defined in the projective space.

In many cases, the principle of duality can be used to derive a solution of a dual problem and have only one programming sequence for both problems, i.e. the primary one and the dual. Figure 1 presents the duality in ${E^{2}}$ – the line p is represented as a point $D(p)$ in the dual space (Stolfi, 1991). Unfortunately, the principle of duality is not usually part of the standard computer science curricula.

The principle of duality is one of essential principles in mathematics. In our case of geometric problems described by linear equations, see Eq. (3) and Eq. (4), the principle of duality states that any theorem remains true when we interchange the words: Once the theorem has been established, the dual theorem is obtained as described (Johnson, 1996).

In other words, the principle of duality in the ${E^{2}}$ case says that in all theorems it is possible to substitute the term “point” by the term “line” and term “line” by the term “point” and the given theorem remains valid. This helps a lot in the solution of some geometrical problems, similarly in the ${E^{3}}$ case. It means that the intersection computation of two lines is dual to the computation of a line given by two points in the ${E^{2}}$ case. It is strange as the usual solution in the first case leads to formulation $\mathbf{Ax}=\mathbf{b}$, while in the second case, the parameters of a line are determined as $\mathbf{Ax}=\mathbf{0}$. However, if the projective representation is used, both cases are solved as $\mathbf{Ax}=\mathbf{0}$ (Skala, 2008b). Similarly, the intersection computation of three planes is dual to the computation of a plane given by three points in the ${E^{3}}$ case.

Generally, a system of linear equations $\mathbf{Ax}=\mathbf{0}$ can be solved as: where ${\mathbf{a}_{i}}$ are rows of the matrix A, ∧ is the outer product, i.e. extended cross product, and $\mathbf{x}={[{x_{1}},\dots ,{x_{n}}:w]^{T}}$ is the solution in the homogeneous coordinates. It means that a line given by two points ${\mathbf{x}_{A}}$, ${\mathbf{x}_{B}}$, resp. an intersection of two lines ${\mathbf{p}_{1}}$, ${\mathbf{p}_{2}}$ is given in ${E^{2}}$ as $\mathbf{p}={\mathbf{x}_{A}}\wedge {\mathbf{x}_{B}}$, resp. $\mathbf{x}={\mathbf{p}_{1}}\wedge {\mathbf{p}_{2}}$, due to the principle of duality.

It should be noted that a line in ${E^{2}}$ can be expressed as: In the case of ${E^{3}}$ a line cannot be expressed in the implicit form, but as an intersection of two planes or in the parametric form as: There is a special parametric form of the line in ${E^{3}}$, which uses the Plücker coordinates. It has a specific property as the point $({X_{A}},{Y_{A}},{Z_{A}})$ is the closest point to the origin of the coordinate system (Blinn, 1977; Mahovsky and Wyvill, 2004; Platis and Theoharis, 2003; Wikipedia, 2020).

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

In the following, a brief classification of intersection algorithms in 2D and 3D will be presented with short characteristics; a short overview can be found in Wikipedia (2021a).

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

Intersection algorithms with a rectangular area (window) are well known as the line clipping or as the line segment clipping algorithms. The first algorithm was developed and used for the flight simulator project led by Cohen (1969) in 1967. Efficient coding of the line segment position coding leading to significant computational reduction was introduced in Sproull and Sutherland (1968) and patented in 1972 (Sutherland, 1972). The Cohen-Sutherland algorithm is described in Newman and Sproull (1979), Comninos (2006), Matthes and Drakopoulos (2019a, 2019b), etc. The Cohen-Sutherland algorithm generates a bit-code LRTB, i.e. [Left, Right, Top, Bottom], for each end-point of the line segment, see Fig. 2. The coding is redundant. However, it enables simple identification of the cases, when the line segment is totally inside or outside as follows: where land, resp. or mean bit-wise and, resp. or operations.

The ultimately deep classification of all the possible cases using arithmetic operation with the codes was described in Skala (2021b), see Table 1 and Fig. 3. The ${C_{AB}}$ value is the index to the array of functions representing each case.

Distinguishing all the cases leads to more efficient coding and efficient implementation (Skala, 2021b); specific cases are presented in Table 2.

The Cohen-Sutherland algorithm can also be extended to the 3D case, i.e. intersection of a line segment with a cube or right-angled parallelepiped.

The Cohen-Sutherland algorithm was improved by Nicholl et al. (1987). It uses the window corners position classification in relation to the line segment position, see Fig. 4. The Nicholl-Lee-Nicholl algorithm was improved by Bui and Skala (1998) using some additional classification of possible cases and extended to the ${E^{3}}$ case in Skala and Bui (2001).

The algorithms (Liang and Barsky, 1983) and (Dörr, 1990) are based on the direct intersection computation of a line with the polygon edges in the parametric form. Analysis of the Nicholl-Lee-Nicholl and Liang-Barsky algorithms was given in Devai (2005). Simple and robust line and line segment clipping algorithms in ${E^{2}}$ was described in Skala (2004, 2005, 2012, 2020). They are based on the projective representation and homogeneous coordinates using a separation of the convex polygon vertices by the given line, see Fig. 5. The sign of the function values $F(\mathbf{x})$, which represents the given line, for each window corner gives a 4-bit code identifying the edges intersected by the given line. The algorithm can be extended for the convex polygon case.

Let us consider an implicit function $F(\mathbf{x})={\mathbf{a}^{T}}\mathbf{x}$, where $\mathbf{a}={[a,b:c]^{T}}$ are coefficients of the given line p, $\mathbf{x}={[x,y:w]^{T}}$ means a point on this line. Then the equation $F(\mathbf{x})=0$ represents the given line p in ${E^{2}}$ using the projective extension of the Euclidean space.

The clipping operation should determine the intersection points ${\mathbf{x}_{i}}={[{x_{i}},{y_{i}}:{w_{i}}]^{T}}$, $i=1,2$ of the given line with the window, if any. The line splits the plane into two parts, see Fig. 5. The corners of the window are split into two groups according to the sign of the function $F(\mathbf{x})$ value. This results into Smart-Line-Clip (S-L-Clip) algorithm, see Algorithm 1. It means that each corner can be classified by a bit value ${c_{i}}$ as: where $\mathbf{a}={[a,b:c]^{T}}$ are coefficients of the given line p, $\mathbf{x}={[x,y:w]^{T}}$ means a point on this line. Table 3 shows the codes for all situations (some of those are not possible). The $\mathbf{TAB}\mathbf{1}$ and $\mathbf{TAB}\mathbf{2}$ contain indices of edges of the window intersected by the given line (values in the $\mathbf{MASK}$ is used in the line segment algorithm).

It can be seen, that the S-L-Clip Algorithm 1 is quite simple and easily extensible for the convex polygon clipping case as well. Table 3 can be generated synthetically. It is significantly more straightforward than the algorithm (Liang and Barsky, 1984). It also supports SSE4 and GPU use directly and leads to simple implementations, as the cross-product and dot-product operations, are supported in hardware. It should be noted, that the algorithm is designed for a very general case, as the window corners and the points defining the line, are generally in the projective representation, i.e. $w\ne 0$. Therefore, the S-L-Clip algorithm has further potential for optimization, especially for the case when the corner points of the window are given in the Euclidean coordinates, i.e. $w=1$, and clipping is made in the Normalized Device Coordinate (NDC) system (Skala, 2020).

The modification of the S-L-Clip algorithm for a line segment clipping is simple and described in Skala (2004). The advantage of it is that the end-points and the window corners might be given generally in the projective space, i.e. $w\ne 0$. The cross-product is used for the intersection computation using SSE4 or GPU acceleration.

Other proposed modifications of algorithms can be found in Bui (1999), Andreev and Sofianska (1991), Bao and Peng (1996), Devai (2005, 2006, 1998), Duvalenko et al. (1990, 1993, 1996), Cai et al. (2001), Day (1992a, 1992b), Evangeline and Anitha (2014), Kaijian et al. (1990), Kodituwakku et al. (2013), Kong and Yin (2001), Maillot (1992), Wei et al. (2013), Slater and Barsky (1994), Ray (2012a, 2012b, 2014, 2015), Li (2016), Singh and Lumar (2016), Dev and Saharan (2019).

Some additional modifications of algorithms were published in Brackenbury (1984), Chao et al. (2009), Cheng and Yen (1989), Dimri (2015), Dimri et al. (2022), Elliriki et al. (2019), Hattab and Yusof (2014), Iraji et al. (2011), Jiang and Han (2013), Jianrong (2006), Kumar and Awasthi (2011), Kuzmin (1995), Li et al. (2014), Li and Lei (2012), Meriaux (1984), Molla et al. (2003), Nisha (2017b, 2017a), Sobkow et al. (1987), Sharma and Manohar (1993), Wang et al. (1998a, 1998b, 2012, 2001), Yang (1988), Pandey and Jain (2013), Bhuiyan (2009). The hardware FPGA implementation was proposed in Dawod (2011).

Analysis and comparisons of some clipping algorithms were published recently in Krammer (1992), Skala and Huy (2000), Skala et al. (1995), Nisha (2017a, 2017b), Matthes and Drakopoulos (2022), Ray (2012b).

Generic solutions for polygon clipping were developed by Weiler and Atherton (1977), Rappoport (1991), Vatti (1992), Wu et al. (2004), Xie et al. (2010), Zhang and Sabharwal (2002), Zhang et al. (2022). Boolean operations with polygons were introduced by Rivero and Feito (2000), Martinez et al. (2009).

Algorithms for a line clipping ${E^{2}}$ 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 enables to decrease complexity from $O(N)$ to $O(\lg N)$ (Skala, 1994). It should be noted that a similar complexity decrease is not possible in the ${E^{3}}$ case as there is no ordering.

In the non-convex polygon cases, when the polygon can be self-intersecting, etc., problems with robustness of computation can be expected. Also, in some cases a three-value logic is to be used in order to solve specific cases properly, e.g. a line passes a vertex, a line touches a vertex, a line lies on an edge, etc. (Mccoid and Gander, 2022; Skala, 1989, 1990a).

The Cyrus-Beck’s algorithm (Cyrus and Beck, 1978) is probably the famous algorithm for line-convex polygon clipping. It is based on a computation of the parameter t of the given line in the parametric form with edges of the given convex polygon, Fig. 6. The algorithm is of $O(N)$ computational complexity and can be extended for the ${E^{3}}$ case.

The Cyrus-Beck’s algorithm is based on direct intersection computation of the given line p in the parametric form and a line on which the polygon edge ${e_{i}}$ lies, see Fig. 6, in the implicit form, i.e. on a solution of two linear equations (vector notation is used): where ${\mathbf{x}_{A}}={[{x_{A}},{y_{A}}]^{T}}$, $\mathbf{s}={[{s_{x}},{s_{y}}]^{T}}$ is the directional vector of the line p, ${\mathbf{n}_{i}}={[{n_{x}},{n_{y}}]^{T}}$ is the normal vector of the edge ${e_{i}}$.

Solving those equations, the parameter t for the intersection point is obtained as: Then ${t_{i}}$ is the parameter t value for the intersection of the line p and the line on which the edge ${e_{i}}$ lies, see Fig. 6. It can be seen that the algorithm is not robust as if the line p is parallel or nearly parallel to the edge ${e_{i}}$, the expression ${\mathbf{n}_{i}^{T}}\mathbf{s}\to 0$ and ${t_{i}}\to \pm \infty $. The fraction computation might cause an overflow or high imprecision of the computed parameter t value, see Fig. 6.

It is hard to detect and solve such cases reliably and programmers usually use a sequence like which is an incorrect solution as the value $\textit{eps}$ is the programmer’s choice and the value of ${\mathbf{n}_{i}^{T}}\mathbf{s}$ might also be close to the value of ${\mathbf{n}_{i}^{T}}{\mathbf{x}_{A}}+{c_{i}}$, see Eq. (12).

However, textbooks do not point out such dangerous construction as far as robustness and computational stability are concerned.

The modification of the Cyrus-Beck’s algorithm using the cross product for more reliable detection of the “close to singular” cases was described by Skala (1993). Probably the most reliable modification of the Cyrus-Beck’s algorithm is to use:

The Cyrus-Beck’s algorithm for a line clipping is described by Algorithm 2. It can be easily modified for the line segment clipping just restricting the range of the parameter t to $\langle 0,1\rangle $, i.e. It can be seen that the algorithm complexity is $O(N)$ and the division operation, which is the most consuming time operation in the floating-point representation, is used N times.3

However, only 2 values (${t_{\min }}$, ${t_{\max }}$) of the parameter t are valid, i.e. $N-2$ computations of the parameter t are lost. Also, reliable detection of the “singular or close to singular” cases is difficult and time-consuming, especially in the ${E^{3}}$ case.

Some improvements and modifications were described by Skala (1993). As the edges of the convex polygon are ordered, the algorithm with the $O(\lg N)$ complexity was derived by Skala (1994). An algorithm based on space subdivision was described in Slater and Barsky (1994).

Another approach based on the implicit form of the given line and convex polygon vertices classification, the S-Clip algorithm, was developed in Skala (2021c) and modified by Konashkova (2014, 2015). Another algorithm based on the S-Clip algorithm was described in Skala (2021c). An algorithm for a line segment clipping based on the line segment end-points evaluation with the $O(N)$ complexity was described by Matthes and Drakopoulos (2022).

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

The algorithm with the run-time $O(1)$ complexity using pre-computation was developed by Skala (1996b, 1996d). 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 and Lederbuch (1996), Skala et al. (1996).

Other related algorithms or modifications of existing ones were published by: Li (2005), Nishita and Johan (1999), Raja (2019), Sun et al. (2006), Vatti (1992), Wang et al. (2005), Wijeweera et al. (2019), Sharma and Kaur (2016), Sharma and Manohar (1992) use the affine transformation.

Probably, the first algorithm dealing with the non-convex polygon clipping was published in the Reentrant polygon clipping algorithm paper (Sutherland and Hodgman, 1974), followed by the Weiler-Atherton algorithm for polygon-polygon clipping (Weiler, 1980; Weiler and Atherton, 1977; Rappoport, 1991).

Intersections with arbitrary non-convex polygons were described in Greiner and Hormann (1998) and solutions of “the singular” (degenerated) cases were described in Foster et al. (2019). The algorithm (Skala, 1989) uses a three-value logic.

A robust solution of triangle-triangle intersection in ${E^{2}}$ is described in Mccoid and Gander (2022). Other algorithms or modifications are described in Dimri (2015), Evangeline and Anitha (2014), Lu and Wu (2002), Lu et al. (2002a), Tang and He (2009). The affine transformations are used in Huang (2013), Huang and Wangyong (2009), Huang and Liu (2002).

Algorithms that also handle arcs and use a three-value logic to handle singular cases properly, including self-intersecting non-convex polygons, were described in Skala (2015, 1989, 1990a), Wang and Chong (2016), Tran (1986).

Homogeneous coordinates are used in computer graphics not only for geometric transformations. Sproull and Sutherland (1968) used the homogeneous coordinates in the Clipping divider in 1968. Arokiasamy (1989) used them with duality in 1989, Blinn (1991), Blinn and Newell (1978) described the clipping pipeline using the projective extension of the Euclidean space and Nielsen (1995) described the use of semi-homogeneous coordinates for clipping. New approach to 2D clipping based on the separation of the convex polygon vertices by the given line was presented in Kolingerová (1994, 1997) and Skala (2004, 2005, 2012, 2020).

In the following, algorithms related to the intersection in 3D will be briefly mentioned in a short introductory overview.

Special attention was recently given to a line clipping by a pyramid in 3D due to the perspective pyramid clipping. The problem was analysed recently by Cohen (1969), Sproull and Sutherland (1968), Blinn (1991), Blinn and Newell (1978), Skala and Bui (2000, 2001).

The Cyrus-Beck’s algorithm (Cyrus and Beck, 1978) is probably the famous algorithm for the line-convex polyhedron clipping in ${E^{3}}$. It computes a parameter t of a line in the parametric form and plane of the given face of the convex polyhedron. The algorithm is of the $O(N)$ computational complexity given by the fact that in the ${E^{3}}$ space there is “no order” of the polyhedron facets defined. Rogers and Rybak (1985) published a more general clipping algorithm in 3D in 1995.

The algorithm with the ${O_{\exp }}(\sqrt{N}\hspace{0.1667em})$ complexity was described in Skala (1997, 2014). It assumes a triangular mesh, i.e. there is info on the neighbour triangles available. The algorithm is based on two planes representing the given line in ${E^{3}}$ and testing of the neighbours in the triangular mesh of the given polyhedron. The algorithm was modified by Konashkova (2015). An interesting approach using the vertex connection table was published in Konashkova (2014).

Using pre-computation, the algorithm in ${E^{3}}$ with a run-time $O(1)$ complexity was developed by Skala (1996c). Comparison was presented in Skala et al. (1996).

The Moeller-Trumbore algorithm for a ray-triangle intersection was published in Möller and Trumbore (1997). Since then many modifications and approaches have been published, e.g. Xiao et al. (2020) using GPUs, Skala (2010, 2008a) uses the computation of the barycentric coordinates in the homogeneous coordinates, Rajan et al. (2020) uses dual-precision fixed-point arithmetic for low-power ray-triangle intersections. Platis and Theoharis (2003) published an algorithm for a ray-tetrahedron intersection using the Plücker coordinates. The intersection with the AABBox is described in Eisemann et al. (2007), Kodituwakku and Wijeweera (2012), Maonica et al. (2017) and Mahovsky and Wyvill (2004). Other algorithms are available in Sharma and Manohar (1993), Skala (1996a), Williams et al. (2005), Llanas and Sainz (2012). The 3D line segment-triangle intersection algorithm is described in Jokanovic (2019), Amanatides and Choi (1995), Lagae and Dutré (2005) (in 2D only) and a ray/convex polyhedron intersection was described in Zheng and Millham (1991). Intersection of a line or a ray with a triangle using the SSE4 instructions was developed and described in Havel and Herout (2010). An extensive list of relevant publications can be found via Wikipedia (2021c).

The intersection computation with implicitly defined objects was published by Petrie and Mills (2020), intersection with a torus was published by Cychosz (1991) and alternative formulations were given in Skala (2013a). Reshetov (2022) published an efficient algorithm for a ray/ribbon intersections computation, ray tracing of 3D Bézier curves given by Reshetov (2017) and a ray/bilinear patch intersection (Reshetov, 2019). The intersection with general quadrics using the homogeneous coordinates was described in Skala (2015) and clipping by a spherical window was published by Deng et al. (2006).

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

The computation of the intersection of triangles is probably the most important, as nearly all Computer Aided Design (CAD) systems depend on efficient, robust and reliable computation. Figures 8 and 9 present the non-trivial cases, when triangles are split into a set of triangles, which potentially leads to an explosion of small triangles and numerical and robustness problems.

In the CAD systems, two different data sets are usually used: An efficient triangle-triangle intersection algorithm was developed by Möller (1997). It is based on the mutual triangle intersection with the plane of the other. Other methods or approaches were described by Chang and Kim (2009), Danaei et al. (2017), Devillers and Guigue (2002), Elsheikh and Elsheikh (2014), Guigue and Devillers (2003), Held (1998), Sabharwal and Leopold (2016), Sabharwal et al. (2013), Sabharwal and Leopold (2015), Shen et al. (2003), Tropp et al. (2006), Roy and Dasari (1998), Wei (2014), Ye et al. (2015). A deep analysis of possible situations is given in Lo and Wang (2004). Robust and reliable solution of the triangle-triangle intersection was developed by Mccoid and Gander (2022).

Clipping triangular strips using homogeneous coordinates was described by Maillot (1991) in GEM II (Arvo, 1991). Parallel exact algorithm for the intersection of large 3D triangular meshes was described in de Magalhães et al. (2020) and a comparison of triangle-triangle tests on GPU was described in Xiao et al. (2020). Triangular mesh repair was described by McLaurin et al. (2013).