3D coordinates of intersection point in clipping for a rasterizer

When doing clipping in homogeneous coordinates, we need to find the coordinates of the intersection of the viewing frustum with the line to be clipped. This can be done easily if we want those coordinates to be in screen space(simply divide by the fourth coordinate). But how can we find those coordinates in 3D space? And do we need to do so in the first place?

• Dividing by the 4th coordinate would lead to conversion from homogeneous projective coordinates to Carthesian coordinates in Euclidean space. The clipping test then computes intersection with a plane in Euclidean space, with that plane just happening to be axis-aligned. If you need to do the same thing in world-space, the only difference is that the plane is no longer axis-aligned, but ends up being the (not-axis-aligned) planes bounding your viewing frustum. – Martin Prazak Apr 14 at 9:20

I think it depends on what your goal is and what kind of initial data you are provided with. I don't think that dividing by the forth coordinate solves a clipping task. What it does is switching of the coordinates of your objects from 3D projective (four components) to 3D Euclidean (three components).

I would say, the basic component you need is a procedure of calculating the intersection point in projective coordinates of a line and a plane.

An arbitrary point in projective three space is written as a four-vector column: $$X = \begin{bmatrix}X_1\\X_2\\X_3\\x_4\end{bmatrix}$$ and a plane in projective three space can be expressed as $$N^T X = 0$$ where $$N^T X = \begin{bmatrix}N_1 \,\, N_2 \,\, N_3\,\, N_4\end{bmatrix} \begin{bmatrix}X_1\\X_2\\X_3\\x_4\end{bmatrix} = N_1X_1 + N_2X_2 + N_3X_3 + N_4X_4$$ A line in projective three space is traditionally given by a pair of points $$A = \begin{bmatrix}A_1\\A_2\\A_3\\A_4\end{bmatrix} \,\, \text{ and }\,\, B = \begin{bmatrix}B_1\\B_2\\B_3\\B_4\end{bmatrix}$$ and any point $$X$$ on the line is expressed as $$X = t_1 A + t_2 B$$ for two real numbers $$t_1, \, t_2$$ not equal to zero simultaneously. Tho find the intersection point of the line $$X = t_1 A + t_2 B$$ with the plane $$N^TX = 0$$ we simply plug $$0 = N^TX = N^T \big(t_1 A + t_2 B \big) = t_1(N^TA) + t_2 (N^TB)$$ and since $$t_1, \, t_2$$ are determined uniquely up to a common factor, a solution to the equation $$t_1(N^TA) + t_2 (N^TB) = 0$$ is $$t_1 = -\, (N^TB)$$ and $$t_2 = (N^TA)$$.

Therefore, given a plane $$N^TX = 0$$ and a line determined by a pair of points $$A$$ and $$B$$, the unique intersection point of the line with the plane is calculated as $$P = - (N^TB)\, A + (N^TA)\, B$$ We us projective coordinates, because it may happen that one of the points on the line, say $$B$$ is "at infinity" with respect to our perferred choice of Cartesian coordinates. That means that $$B = \begin{bmatrix}B_1\\B_2\\B_3\\0\end{bmatrix}$$. In this case, the line is interpreted in Cartesian coordinates as the line passing through the 3D Cartesian point $$A = \begin{bmatrix}\frac{A_1}{A_4}\\\frac{A_2}{A_4}\\\frac{A_3}{A_4}\end{bmatrix}$$ and aligned with the 3D vector $$\vec{V}_B = \begin{bmatrix}B_1\\B_2\\B_3\end{bmatrix}$$.

In order to clip a line, you can go about it in two different ways, both of which can use the formula for the intersection between a line and a plane. You can find the (projective) equations of the planes of the frustum, intersect the 3d line with them and then project the points onto the screen, which is again intersection of a plane with lines passing through the origin. Alternatively, you can project the two points that determine the line onto the screen (again you can use the formula for the intersection of the line connecing the origin with any of the two points with the plane of the screen), which allows you to know the projection of the 3D line on the screen, and then find the intersection points of the projected line with the borders of the screen. Maybe the second scenario is simpler?

The screen is parallel to the $$x,\,y$$ plane of the 3D Cartesian frame, while the $$z$$ axis is perpendicular to the screen and the screen is at a distance $$l$$ from the origin of the coordinate system. Therefore, the Cartesian equation of the plane of the screen is $$z = l$$. In projective coordinates, $$z = \frac{X_3}{X_4}$$, which means that $$\frac{X_3}{X_4} = l$$ so the projective equation is $$X_3 = l\, X_4$$ and can be also expressed as $$0 = X_3 - l\, X_4 = S^TX = \begin{bmatrix} 0 \,\,\, 0 \,\,\, 1 \,\, - l\end{bmatrix} \begin{bmatrix}X_1\\X_2\\X_3\\x_4\end{bmatrix}$$ where $$S = \begin{bmatrix}0 \\ 0 \\ 1 \\ -l\end{bmatrix}$$ so if the 3D line is determined by the pair of points $$A = \begin{bmatrix}A_1\\A_2\\A_3\\A_4\end{bmatrix}$$ and $$B = \begin{bmatrix}B_1\\B_2\\B_3\\B_4\end{bmatrix}$$ Hence, with $$O = \begin{bmatrix}0\\0\\0\\1\end{bmatrix}$$, the projection of $$A$$ on the screen is $$\hat{A} = - (S^TO)\, A + (S^TA)\, O = l\, A + (A_3-l\, A_4)\, O = \begin{bmatrix}l\,A_1\\l\,A_2\\l\,A_3\\l\,A_4\end{bmatrix} + \begin{bmatrix}0\\0\\0\\A_3-l\, A_4\end{bmatrix} = \begin{bmatrix}l\,A_1\\l\,A_2\\l\,A_3\\A_3\end{bmatrix}$$ and the projection of $$B$$ on the screen is $$\hat{B}= \begin{bmatrix}l\,B_1\\l\,B_2\\l\,B_3\\B_3\end{bmatrix}$$ So one can write this projection in matrix form as follows:

$$P_{scr} = - (S^TO)\, \text{Id} + O\,S^T$$ because $$P_{scr}A = \Big(- (S^TO)\, \text{Id} + O\,S^T\Big)\,A = - (S^TO)\,A + O\,(S^TA) = - (S^TO)\,A + (S^TA)\,O = \hat{A}$$

\begin{align} P_{scr} &= - (S^TO)\, \text{Id} + O\,S^T\\ &\\ &= - (-l)\begin{bmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix} + \begin{bmatrix}0\\0\\0\\1\end{bmatrix} \begin{bmatrix}0\,\,\, 0\,\,\, 1 \,\,\, - l\end{bmatrix}\\ &\\ &= \begin{bmatrix}l & 0 & 0 & 0 \\0 & l & 0 & 0\\0 & 0 & l & 0\\0 & 0 & 0 & l\end{bmatrix} + \begin{bmatrix}0 & 0 & 0 & 0 \\0 & 0 & 0 & 0\\0 & 0 & 0 & 0\\0 & 0 & 1 & -l \end{bmatrix}\\ &\\ & = \begin{bmatrix}l & 0 & 0 & 0\\0 & l & 0 & 0\\0 & 0 & l & 0\\0 & 0 & 1 & 0\end{bmatrix} \end{align} And thus $$\hat{A} = P_{scr}\, A \,\, \text{ and } \,\, \hat{B} = P_{scr}\, B$$ When you have your points projected on the screen plane, you would like to get rid of the $$z-$$coordiante, so you need to remove the third (out of our) component of your projected points, i.e.: $$\hat{A} = \begin{bmatrix}l\,A_1\\l\,A_2\\l\,A_3\\A_3\end{bmatrix} \mapsto \begin{bmatrix}l\,A_1\\l\,A_2\\A_3\end{bmatrix}$$ so if you take the projection from four vectors to three vectors $$P_0 = \begin{bmatrix} 1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ and muptiply it by $$P_{scr}$$ from the right as $$P_0P_{scr}$$, we can take the projective map from the projective three space to the projective plane of the screen $$P = P_0P_{scr} = \begin{bmatrix} l & 0 & 0 & 0\\0 & l & 0 & 0\\0 & 0 & 1 & 0\end{bmatrix}$$ So, to recap, given a line in projective three space, passing through the pair of points $$A$$ and $$B$$, their screen images, in projective coordinates of the screen, are $$\hat{A} = P\, A$$ and $$\hat{B} =P \, B$$. The formula for the intersection of a line with a plane in projective three space translates verbatim to the intersection of a line given by a pair of points $$\hat{A}$$ and $$\hat{B}$$ with another line given as an equation $$N^T\hat{X} = 0$$ in the projective plane, where $$N = \begin{bmatrix} n_1\\n_2\\n_3\end{bmatrix}$$, $$\hat{X}_N = (- N^T\hat{B})\hat{A} + (N^T\hat{A})\hat{B}$$ so alltogether $$\hat{X}_N = (- N^TP{B})\,P{A} + (N^TP{A})\,P{B}$$ So this is the formula for the projected points of intersection of the three dimensional line with the frustum's boundary. For example, the right vertical boundary of the screen is given by an $$N_{right\, vert} = \begin{bmatrix} w\\0\\0\end{bmatrix}$$ and the bottom horizontal boundary of the screen is given by an $$N_{bottom\, hor} = \begin{bmatrix} 0\\- h\\0\end{bmatrix}$$