Clipping

Why we need clipping?

Let’s start with a question. What is clipping? Clipping is a process in graphics where the GPU rules out every vertex out of camera view. There are many reasons for this process’ existence, first thing comes to mind is efficiency where eleminating vertices out of view would save us a lot of time further down the gpu pipe-line. Second thing is i’ve talked about camera transformations and projection matrices on my previous post, where every frame camera, gets first translated to origin, rotated so that viewing direction coincides with z-axis and the up vector coincides with y-axis(which is actually achieved by a single matrix as i’ve talked about few posts ago), then every vertex gets hit by projection matrix so that they can carried on to image-space and then to screen space. All this sounds nice and dandy but what about the vertices we don’t see? Remember our projection matrix:

$$\begin{bmatrix} \cot\frac{\alpha}{2} & 0 & 0 & 0 \\ 0 & \cot\frac{\alpha}{2} & 0 & 0 \\ 0 & 0 & \frac{f+n}{f-n} & \frac{2fn}{f-n} \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

Take a look at the bottom row, 3rd column. Before multiplying with projection matrix, all our points look like this

\begin{bmatrix}x \\ y \\ z \\ 1\end{bmatrix}

but after multiplication because of the last row,3rd column part that i pointed out before, our matrix will look like this

\begin{bmatrix}x \\ y \\ z \\ w\end{bmatrix}

where the \(w\) value is defined my that portion, which is actually the \(z\) of our matrix. The idea here is that, greater the z value, further the object therefore smaller. So when we convert our point from 3d space to image-space, we divide all our \(x\),\(y\) and \(z\) coodinates by \(w\) and voila! the greater the \(w\) the smaller our object is(which is actually a really cool hack found by a cool dude named Mobius, and is the reason why we are using homogenous coordinates, to facilitate projection basically). So what is waiting for a vertex behind the camera then? Well lets take it step by step. When the camera gets translated to origin with all the rotation and what not, the vertex gets translated with it therefore ending up with a negative \(z\) value, which will cause a negative \(w\) after projection, so when we are porting to image space, dividing every coordinate with a negative \(w\) will leave us with negative coordinates, which will end up as an upside down image. So clipping is a serious business.

How it is done?

Image our viewing frustum, you can imagine it as a funky box with confined by six planes and what we need to find out is if a vertex is inside this box or outside? Actually the process here is pretty simple and straightforward. Every plane here has a normal vector on it and a point. We shall call this \(\vec{N}\) and \(P\) respectively. Say we have a point \(Q\) and we want to know where it lies, well what we do is to substract \(P\) from \(Q\) which will give us a vector, if \(Q\) actually is on the plane, this means that our vector \((Q-P)\) is perpendicular to \(N\) so their dot product should be 0.

$$\vec{N} \cdot (Q-P) = 0$$

If \(Q\) is inside the box, this means they are not perpendicular anymore, lets call the angle between them \(\theta\),

$$\vec{N} \cdot (Q-P) = \lVert\vec{N}\rVert \lVert Q-P\rVert \cos\theta$$

It is not hard to see that the product will be a positive number, where if the vertex is outside the box, \(\theta\) will be more then 90 degrees which will produce a negative number. To summarize:

• \(\vec{N} \cdot (Q-P) = 0\) vertex on the plane
• \(\vec{N} \cdot (Q-P) > 0\) vertex inside frustum
• \(\vec{N} \cdot (Q-P) < 0\) vertex outside frustum

Doing this with a single vertex is pretty simple but lets be honest a vertex is never alone right?

Lets think about two points on is in the inside and one is outside. These points are bound with a line between them and guess what? We need to split this line i a way that we exclude the point on the outside but keep the line intact in our frustum, basically we need a point that is on the plane and also on the line. Lets start by taking two points \(Q_1\) and \(Q_2\). We’ll call our point on the plane \(I\). Now we can define any point on vector \((Q_2 - Q_1)\) by \(Q_1 + t(Q_2 - Q1)\) which includes our point \(I\) also. So:

$$I=Q_1 + t(Q_2-Q_1)$$

But what is \(t\) then? Brace yourselves. I will define two variables \(d_1\) and \(d_2\) where

$$d_1 = \vec{N} \cdot (Q_1 - P)$$

And:

$$d_2 = \vec{N} \cdot (Q_2 - P)$$

Now, by subtracting \(P\) from both sides on our equation \(I=Q_1 + t(Q_2-Q_1)\) and then dotting both sides with \(\vec{N}\) i get an equation like this:

$$\vec{N} \cdot (I-P) = \vec{N} \cdot (Q_1-P) + t(\vec{N} \cdot (Q_2-P)-\vec{N} \cdot (Q_1-P))$$

Which is actually:

$$0 = d_1 + t(d_2-d_1)$$

Aaaand voila! here is our t:

$$t =\frac{d_1}{d_1- d_2}$$

Well i guess i covered the basics of clipping for now. There are many more to it i just scratched the surface but maybe i will continue on this topic later. Cheers for your time!