02: Clipping lines

So far, we are able to draw any line that we want... with a caveat. What happens, if we specify a point of the line outside of the image? In the current version, the script will just crash, since you will try to write values outside of the allowed range. This section will solve that issue.

Clipping refers to the process of restricting our drawing operations to a certain region only and to "clip" away anything not in that region.

As screens or windows are generally rectangular and rectangles have nice geometric properties, it makes sense, that an efficient algorithm exists to clip lines with the screen.

A well-known algorithm for this is called the Cohen–Sutherland algorithm ^[1], which we will implement.

We will split up the procedure into two parts:

Determine where a point lies with respect to a rectangle/the screen
Use the previous information to clip the line

You can find the full rasterization code here: Rasterizer 02

Region codes

In the first step for implementing the Cohen-Sutherland we will assign codes to points based on where they lie with respect to a rectangle. This information can then be used to check, if a line needs to be clipped.

There are 4 lines making up a rectangle and we use those for classification. We identify four regions around a rectangle, two mutually exclusive pairs:

Top and bottom
Left and right

These can of course be mixed, so a point could be above and to the left of a rectangle, but it can't be above and below at the same time.

We encode those four regions the following way: We use 4 bits $b_3 b_2 b_1 b_0$ . A bit is set to $1$ , if a point is in the corresponding region, and $0$ otherwise, where we arbitrarily use the following order:

Top
Bottom
Right
Left

A point to the bottom right would then be $0110$ .

What code do we get, when a point is inside the rectangle?

[[0000]]

This bit representation is useful, in that we can combine it with fast bit operations. The bottom right point is just the logical or operation between Bottom ( $0010$ ) and Right ( $0100$ ), which is usually written with the $|$ -operator:

code = BOTTOM | RIGHT

We can check, if any of those bits is set ( $=1$ ), by performing a logical and operation with a number containing $1$ at the bit positions we are interested in and checking the result, usually written with the & operator.

This whole technique is called a bitmask or bitflags.

The operation to check, if all of the bits set in a variable FLAGS are set, you can use the following:

if((code & FLAGS) === FLAGS) {...}

FLAGS could for example just be BOTTOM or any combination of the four regions.

If we just interpret the bits as digits in a binary number, we can write them down in the decimal system as:

Top $= 0001 = 1_{10}$
Bottom $= 0010 = 2_{10}$
Right $= 0100 = 4_{10}$
Left $= 1000 = 8_{10}$

The actual values don't really matter though, the bits they use up just need to be disjoint.

NOTE: In JavaScript, all numbers are floating point numbers. The bitwise operations |,& still work. Internally, the variables are converted to 32-bit integers and the operations are applied. This will introduce some additional overhead, but shouldn't really be noticeable in the grand scheme of things.

One way to specify a rectangle is to specify the lower left point and the top right one. We can use that to very easily find the codes as follows:

code = 0;
if(point is smaller than x_min) {
    code = code | LEFT;
}
if(point is greater than x_max) {
    code = code | RIGHT;
}
if(point is smaller than y_min) {
    code = code | BOTTOM;
}
if(point is greater than y_max) {
    code = code | TOP;
}

We will implement this functionality below!

We specify a rectangle in the middle of the frame and color each of the 8 (including the overlaps) with a different color.

Exercise:

Implement the region code determination from above in the regionCode.js file
defines.js contains the values for TOP/... at the top SCREEN_CODE_LEFT/SCREEN_CODE_RIGHT/SCREEN_CODE_TOP/SCREEN_CODE_BOTTOM

Solution:

See the solution

Next we will do the actual clipping by using our region code.

Clipping the lines at the screen

Now that we can efficiently check, where a point lies in relation to a rectangle (for example our screen), we can use that for clipping.

The basic idea is to use the codes of the line endpoints to quickly check if we need to clip the line.

There are three cases to consider, with the third having sub-cases:

The line is fully inside -> No clipping needed
The line is fully outside -> Line doesn't need to be drawn
Line crosses one of the four lines going through the rectangle sides

The first case happens when both points are inside the rectangle. In this case, the region code of both points is $0000$ . So we can quickly compute the or operation of the codes of both endpoints. This effectively "gathers" all $1$ s that appear in the codes. If the result of that or is still $0$ , the line is inside and we can return both points.

For the second case, we think about when we can be absolutely sure, that a line will be outside the rectangle. Two objects do not intersect, if we can find a line that separates them (this is a case of the so called Separating Axis Theorem, SAT). We have information about four lines, the rectangle sides! If a line is completely on the left, right, bottom or top, then it can't intersect the rectangle. When you look at how the codes are constructed, we can very easily check for that! If the line lines completely on one side, then both point codes will share a $1$ at the same location! So we check for that case by combining both codes with and and then checking if the result is not zero. If it is, the line is fully clipped and does not need to be drawn.

The third case is slightly more involved. At least one point of the line will be outside the rectangle and the line must cross at least one line. To make things easier, we just consider one of the points. As $0$ corresponds to a point inside, we choose the larger code of the two, thus ensuring we have the point outside. Then we get four cases again:

Point is at the top -> The clipped $y$ -coordinate is the maximum $y$ -coordinate. Calculate $x$ .
Point is at the bottom -> The clipped $y$ -coordinate is the minimum $y$ -coordinate. Calculate $x$ .
Point is to the right -> The clipped $x$ -coordinate is the maximum $x$ -coordinate. Calculate $y$ .
Point is at the left -> The clipped $x$ -coordinate is the minimum $x$ -coordinate. Calculate $y$ .

After we have resolved one of these cases, we replace the point corresponding to the greater code with the newly clipped coordinates. Then we update that points region code and redo the loop.

When everything is clipped, the line will be fully inside and thus the loop terminates.

The last missing piece is how to compete the missing coordinate in these four cases.

We will show how to get the equation for the first case. We have a line defined by the two endpoints $\mathbf{A}$ and $\mathbf{B}$ .

We can write the line as

\begin{align*} \mathbf{p}(t) &= \mathbf{A} + t(\mathbf{B} - \mathbf{A}) \\ &= \begin{pmatrix}A_x \\ A_y \end{pmatrix} + t \begin{pmatrix}B_x - A_x \\ B_y - A_y\end{pmatrix} \end{align*}

$t$ describes where we are on the line and for $t\in [0,1]$ , we have the segment between the two points (check by plugging $0$ and $1$ in). From the equation, we see that the $x$ and $y$ coordinate moves with the same $t$ parameter, so if we have the one that gets us the $y_{\text{max}}$ , the same one will give us the corresponding $x$ -coordinate. So let's find $t$ :

\begin{align*} y_{\text{max}} &= A_y + t (B_y - A_y) \\ y_{\text{max}} - A_y &= t(B_y - A_y) \\ \frac{y_{\text{max}} - A_y}{B_y - A_y} &= t \end{align*}

With that found, we can plug it back in to get the missing $x$ -coordinate.

\begin{align*} p_x &= A_x + t (B_x - A_x) \\ &= A_x + \frac{y_{\text{max}} - A_y}{B_y - A_y} (B_x - A_x) \\ &= \frac{A_x(B_y - A_y) + (y_{\text{max}} - A_y)(B_x - A_x)}{B_y - A_y} \\ &= \frac{A_x B_y - A_x A_y - A_y(B_x - A_x) + y_{\text{max}}(B_x - A_x)}{B_y - A_y} \\ &= \frac{A_x B_y - A_x A_y - A_y B_x + A_x A_y + y_{\text{max}}(B_x - A_x)}{B_y - A_y} \\ &= \frac{A_x B_y - A_y B_x + y_{\text{max}}(B_x - A_x)}{B_y - A_y} \\ \end{align*}

In the solution, the second line is chosen for the implementation, as it is a bit more understandable. Bonus: If you know the formula for the normal of a 2D vector and the implicit equation defining a 2D line, you might express this in terms of $\mathbf{n}$ and $d$ .

As the other cases work the same, just with minimum and maximum or $x$ and $y$ switched, we will only list the results for the 4 cases here:

Point is at the top -> $y = y_{\text{max}}, x = A_x + \frac{y_{\text{max}} - A_y}{B_y - A_y} (B_x - A_x)$
Point is at the bottom -> $y = y_{\text{min}}, x = A_x + \frac{y_{\text{min}} - A_y}{B_y - A_y} (B_x - A_x)$
Point is to the right -> $x = x_{\text{max}}, y = A_y + \frac{x_{\text{max}} - A_x}{B_x - A_x} (B_y - A_y)$
Point is at the left -> $x = x_{\text{min}}, y = A_y + \frac{x_{\text{min}} - A_x}{B_x - A_x} (B_y - A_y)$

Now, you can implement the full procedure below! The code includes previously written code, with small alterations to call the clipping in the actual rasterization of the line.

We added a bit more information to the Pipeline, to specify the drawing region. It is called a viewport and is a rectangular region with a bottom left origin and a width and height.

class Pipeline {
    constructor({
        viewport = {
            x: 0,
            y: 0,
            w: 0,
            h: 0
        },
        framebuffer = Framebuffer.new(),
    } = {}) {
        this.viewport = viewport;
        this.framebuffer = framebuffer;
    }
}

The solution can once again be seen hidden after that.

Exercise:

Create a while(true) loop for the clipping and implement the cases in the rasterizer.js file
- If the bitwise or (|) of both codes is 0, both points are inside and we can return the points
- If the bitwise and (&) of both codes is greater than 0, both points are outside on the same side, so we can return an empty array []
- Choose the code, that is greater than the other:
  - Clip the point with the equations above, depending on which bit is set (we choose one at a time)
  - Replace the point corresponding to the code with the clipped point and recompute the code

Solution:

You can run it to check your result.

See the solution

Robert F. Sproull and Ivan E. Sutherland. 1968. A clipping divider. In Proceedings of the December 9-11, 1968, fall joint computer conference, part I (AFIPS '68 (Fall, part I)). Association for Computing Machinery, New York, NY, USA, 765–775. https://doi.org/10.1145/1476589.1476687 ↩︎