Basic 2D Clipping

There are two ways to clip computer images: at the image space level and at the object space level. Image space really means at the pixel level. When the image is being rasterized, there is a clipping filter that determines if a pixel is within the viewport. This is appropriate for plotting single pixels, but not for large objects such as bitmaps, lines, or polygons. For objects like those that have some geometry to them, you might as well take advantage of the extra information.

For example, if you're writing a bitmap clipper, all you have to do is clip one rectangle against another; that is, clip your bitmap's bounding rectangle to the viewport. The intersection of the two is the area that you need to blit.

Although you wouldn't think so, lines are a little more difficult to clip. Take a look at Figure 8.8 to see the general problem of clipping a line to a rectangular viewport.

As you can see, there are four general cases:

• Case 1—The line is completely outside the clipping region. This is the trivial rejection case, which is good!

• Case 2—The line is completely inside the clipping region. In this case, no clipping is needed and the line can be passed to the rasterizer as is.

• Case 3—One end of the line segment is outside the clipping region and must be clipped.

• Case 4—Both ends of the line are outside the clipping region and must be clipped.

There are a number of known algorithms to clip lines, such as Cohen-Sutherland, Cyrus-Beck, and so on. But before you take a look at any full clipping algorithms, let's see if you can figure it out yourself!

Given that you have a line (x0,y0) to (x1,y1) in 2D space, along with a viewport defined by the rectangle (rx0, ry0) to (rx1, ry1), you want to clip all lines to this region. So what you need is a preprocessor—or clipping filter, if you will—that takes the input values (x0,y0), (x1,y1), (rx0,ry0), and (rx1,ry1) and outputs a new line segment, (x0',y0') to (x1',y1'), that represents the new line. This process is shown in Figure 8.9. Looking at this problem, the first thing you should notice is that at some point you're going to have to compute the intersection of two lines. Alas, this is a fundamental problem you need to figure out right off the bat, so you might as well start there.

Basically, the line segment from (x0,y0) to (x1,y1) will intersect either the left, right, top, or bottom edge of the clipping rectangle. This means that at least you don't have to find the intersection of two arbitrarily oriented lines since the line being rasterized will always intersect either a vertical or horizontal line. Knowing this may or may not help, but it's worth noting. To compute the intersection of two lines, there are a number of methods, but they are all based on the mathematical form of the lines.

In general, lines can take these general forms:

Y-Intercept Form:    y=m*x+b
Point Slope:         (y–y0)=m*(x–x0)
Two Point Form:      (y–y0)=(x–x0)*(y1–y0)/(x1–x0)
General Form:        a*x+b*y=c
*Parametric Form:    P=p0+V*t

Computing the Intersection of Two Lines Using the Point Slope Form

Off the top of my head, I like both the Point Slope form and the general form. As a good example of algebra, let's work through the intersection of two lines, p0 and p1, using each type of representation. This should warm you up a little for the really gnarly math that's ahead in later chapters <BG>. Let's do the general Point Slope version first (see Figure 8.10).

Referring to Figure 8.10:

Let the first line segment p0 be (x0,y0) to (x1,y1)
Let the second line segment p1 be (x2,y2) to (x3,y3)

Here, p0 and p1 can have any orientation:

Eq.1 – Point Slope form of p0:
m0 = (y1 – y0)/(x1 – x0)

and,

(x – x0) = m0*(y – y0)
Eq.2 – Point Slope form of p1:

m1 = (y3 – y2)/(x3 – x2)

and,

(x – x2) = m1*(y – y2)

Now you have two equations in two unknowns:

Eq.1: (x – x0) = m0*(y – y0)
Eq.2: (x – x2) = m1*(y – y2)

There are two primary ways to solve for (x,y): substitution or matrix operations. Let's try substitution first. The idea here is to find one variable in terms of the other and then plug it into the other equation. Let's try finding x in terms of y for Equation 1 and then plug it into Equation 2:

Equation 1-x in terms of y:

(x – x0) = m0*(y – y0)

x = m0*(y-y0) + x0

That was easy. Now let's plug it into Equation 2 for x.

Equation 2 is

(x – x2) = m1*(y – y2)

In Equation 1, x = m0*(y-y0) + x0. Let's plug that into x:

(m0*(y-y0) + x0 – x2) = m1*(y – y2)

Simplifying for y:

m0*y – m0*y0 + x0 – x2 = m1*y – m1*y2

Collect terms:

m0*y - m1*y = – m1*y2 – (– m0*y0 + x0 – x2)

Pull out y and multiply all signs:

y*(m0 – m1) = m0*y0 – m1*y2 + x2 – x0

And finally, divide both sides by (m0 – m1):

y = (m0*y0 – m1*y2 + x2 – x0)/(m0 – m1)

At this point you could plug this back into Equation 1 and solve for x, or you could rewrite Equation 2 in terms of x and plug that into y of Equation 1. The results will be the same and are shown here.

Equation 3:

x = (-m0/(m1 – m0))*x2 + m0*(y2 – y0) + x0

Equation 4:

y = (m0*y0 – m1*y2 + x2 – x0)/(m0 – m1)

Now, there are some things here that you must consider. First, are there any situations where the previous equations will have problems? Yes! In advanced mathematics, infinity isn't a problem to work with, but in computer graphics, it is! In Equations 3 and 4, the term (m1 – m0) and (m0 – m1) could be 0.0 if the slope of the two lines is the same—in other words, when the lines are parallel.

In this case, they can't possibly intersect and you get a 0.0 in the denominators, driving the quotients of both Equation 3 and 4 to infinity. Of course, this means that at infinity the lines touch, but because you're only working with screens that have a resolution of 1024x768 or so, it's not something you need to consider <BG>.

The bottom line is that this tells you that the intersection equations only work for lines that intersect! If they can't possibly intersect, the math will fail. This is easy to test. Simply check m0 and m1 before doing the math. If m0 == m1, there isn't an intersection. Anyway, let's move on…

If you take a look at Equations 3 and 4 and count up the operations, you're doing about four divides, four multiplies, and eight additions (subtractions count as additions). If you count computing the slopes m0 and m1, that adds four more additions and two divisions. Not too bad.

Computing the Intersection of Two Lines Using the General Form

The general form of any linear equation is

a*x + b*y = c

Or, if you like the canonical form:

a*x + b*y + c = 0

In reality, both the Point Slope form and Y-Intercept form can be put into the general form. For example, if you look at the Y-Intercept form:

y = m*x+b

m*x – 1*y = b

Or a = m, b = -1, and c = b (the intercept). But what if you don't have the intercept? How can you find the values of (a,b,c) if you only have the coordinates (x0,y1) and (x2,y2)? Well, let's see if the Point Slope form can help out…

(y – y0) = m*(x – x0)

Multiplying by m:

y – y0 = m*x – m*x0

Collecting x and y on the LHS (left-hand side):

-m*x + y = y0 + m*x0

Multiplying by –1:

m*x + (-1)*y = (-m)*x0 + (-1)*y0

Computing the Intersection of Two Lines Using the Matrix Form

So it looks like a = m, b = -1, and c = (-m*x0 – y0). Now that you know how to transform the Point Slope form into the general form, you can move on to yet another method of solutions based on matrices. Let's take a look.

Given two general linear equations in this form:

a1*x + b1*y = c1
a2*x + b2*y = c2

You want to find (x,y) such that both equations are simultaneously solved. In the previous example, you used substitution, but there's another method based on matrices. I'm not going to go into the theory too much because I'm going to give you a crash course in vector/matrix math when you get to 3D. For now, I'm just going to show you the results and tell you how to find (x,y) using matrix operations. Take a look.

Let the matrix A equal

|a1    b1|
|a2    b2|

and X (the unknowns) equal

|x|
|y|

and finally, Y (the constants) equals

|c1|
|c2|

Therefore, you can write the matrix equation:

A*X = Y

Multiplying both sides by the inverse of A, or A^-1, you get

A-1*A*X = A-1*Y

Simplifying:

X = A-1*Y

That's it! Of course, you have to know how to find the inverse of a matrix and then perform the matrix multiplication to extract (x,y), but I'll give you some help here and show the final results:

x = Det(A1)/Det
y = Det(A2)/Det

where A1 equals

|c1 b1|
|c2 b2|

and A2 equals

|a1 c1|
|a2 c2|

In essence, you have replaced the first and second column of A with Y to create A1 and A2, respectively. Det(M) means the determinate of M and is computed as follows (in general).

Given a general 2x2 matrix M:

M = |a b|
    |c d|

Det(M) =  (a*d – c*b)

With all that in mind, here's a real example:

A*X       = Y

5*x – 2*y = -1
2*x + 3*y = 3

A = |5 –2|
    |2  3|
X = |x|
    |y|

Y = |-1|
    | 3|

Therefore:

A1 = |-1 –2|
     |3   3|

A2 = |5  -1|
     |2   3|

Solving for x,y:

    Det |-1 –2|
        | 3  3|     (-1*3 – 3*(-2))
x =    ---------- = ---------------- = 3/19
    Det |5  -2|     (5*3 – 2*(-2))
        |2   3|

    Det |5  –1|
        |2   3|     (5*3 – 2*(-1))
y =    ---------- = ---------------- = 17/19
    Det |5  -2|     (5*3 – 2*(-2))
        |2   3|

Wow! Seems like a lot of drama, huh? Well, that's what game programming is all about—math! Especially these days. Luckily, once you write the math code, you don't have to worry about it. But it's good to understand it, which is why I have given you a brief refresher on it.

Now that you've taken a little mathematical detour, let's get back to the reason for all this—clipping.

Clipping the Line

As you can see, the concept of clipping is trivial, but the actual implementation can be a bit complex because linear algebra comes into play. At the very least, you have to understand how to deal with linear equations and compute their intersection. However, as I mentioned before, you can always take advantage of a priori knowledge about the geometry of the problem to help simplify the math, and this is one of those times.

Ultimately, you still have a long way to go to clip a line against a general rectangle, but we'll get to that. Right now, let's take a look at the problem and see if it can help to know that you're always going to clip a general line against either a vertical line or horizontal line. Take a look at Figure 8.11.

You see in Figure 8.11 that you only need to consider one variable at a time here, either the x or the y. This greatly simplifies the math. Basically, instead of doing all the hard math (which you need to know once you get to 3D), you can use the Point Slope form of the line itself to find the intersection point by plugging in the known value for either a line of the form X = constant or Y = constant. For example, let's say that your clipping region is (x1,y1) to (x2,y2). If you want to find where your line intersects the left edge, you know that at the point of intersection the x-coordinate must be x1! Thus, all you have to do is find the y coordinate and you're done.

Conversely, if you want to find the point of intersection on a horizontal line such as the bottom of the clipping rectangle, y2 in this case, you know that the y-coordinate is y2 and you just have to find the x—get it? Here's the math for computing the (x,y) intersections of a line, (x0,y0) to (x1,y1), with a horizontal line with value Y = Yh, and for a vertical line X = Xv.

Horizontal Line Intersection—(x,Yh):

We want x...

Start with Point-Slope, m =(y1 – y0)/(x1 – x0)

(y – y0)            = m*(x – x0)

(y – y0)            = m*x – m*x0
(y – y0)  + m*x0    = m*x
((y – y0) + m*x0)/m = x

x = ((y – y0) + m*x0)/m

or

x = 1/m * (y – y0) + x0

Vertical Line Intersection—(Xv, y):

We want y...

Start with Point-Slope, m =(y – y0)/(x – x0)

(y – y0)            = m*(x – x0)

y                   = m*(x – x0) + y0

And that's how that goes. So now you can compute the intersection of a line with an arbitrary line and with a purely vertical or horizontal line (the important one in the case of rectangular clipping). At this point, we can talk about the rest of the clipping problem.

The Cohen-Sutherland Algorithm

In general, you need to figure out if a line is totally visible, partially visible, partially clipped (one end), or totally clipped (both ends). This turns out to be quite an undertaking, and a number of algorithms have been invented to deal with all the cases. However, one algorithm is the most widely used: Cohen-Sutherland. It's reasonably fast, not too bad to implement, and well published.

Basically, it's a brute-force algorithm. But instead of using millions of if statements to figure out where the line is, the algorithm breaks the clipping region into a number of sectors and then assigns a bit code to each of the endpoints of the line segment being clipped. Then, using only a few if statements or a case statement, it figures out what the situation is. Figure 8.12 shows the plan of attack graphically.

The following function is a version of the Cohen-Sutherland I wrote that works on the same premise:

int Clip_Line(int &x1,int &y1,int &x2, int &y2)
{
// this function clips the sent line using the globally defined clipping
// region

// internal clipping codes
#define CLIP_CODE_C  0x0000
#define CLIP_CODE_N  0x0008
#define CLIP_CODE_S  0x0004
#define CLIP_CODE_E  0x0002
#define CLIP_CODE_W  0x0001

#define CLIP_CODE_NE 0x000a
#define CLIP_CODE_SE 0x0006
#define CLIP_CODE_NW 0x0009
#define CLIP_CODE_SW 0x0005

int xc1=x1,
    yc1=y1,
    xc2=x2,
    yc2=y2;

int p1_code=0,
    p2_code=0;

// determine codes for p1 and p2
if (y1 < min_clip_y)
    p1_code|=CLIP_CODE_N;
else
if (y1 > max_clip_y)
    p1_code|=CLIP_CODE_S;

if (x1 < min_clip_x)
    p1_code|=CLIP_CODE_W;
else
if (x1 > max_clip_x)
    p1_code|=CLIP_CODE_E;

if (y2 < min_clip_y)
    p2_code|=CLIP_CODE_N;
else
if (y2 > max_clip_y)
    p2_code|=CLIP_CODE_S;

if (x2 < min_clip_x)
    p2_code|=CLIP_CODE_W;
else
if (x2 > max_clip_x)
    p2_code|=CLIP_CODE_E;
// try and trivially reject
if ((p1_code & p2_code))
    return(0);

// test for totally visible, if so leave points untouched
if (p1_code==0 && p2_code==0)
    return(1);

// determine end clip point for p1
switch(p1_code)
      {
      case CLIP_CODE_C: break;

      case CLIP_CODE_N:
           {
           yc1 = min_clip_y;
           xc1 = x1 + 0.5+(min_clip_y-y1)*(x2-x1)/(y2-y1);
           } break;
      case CLIP_CODE_S:
           {
           yc1 = max_clip_y;
           xc1 = x1 + 0.5+(max_clip_y-y1)*(x2-x1)/(y2-y1);
           } break;

      case CLIP_CODE_W:
           {
           xc1 = min_clip_x;
           yc1 = y1 + 0.5+(min_clip_x-x1)*(y2-y1)/(x2-x1);
           } break;

      case CLIP_CODE_E:
           {
           xc1 = max_clip_x;
           yc1 = y1 + 0.5+(max_clip_x-x1)*(y2-y1)/(x2-x1);
           } break;

    // these cases are more complex, must compute 2 intersections
      case CLIP_CODE_NE:
           {
           // north hline intersection
           yc1 = min_clip_y;
           xc1 = x1 + 0.5+(min_clip_y-y1)*(x2-x1)/(y2-y1);

           // test if intersection is valid,
           // if so then done, else compute next
            if (xc1 < min_clip_x || xc1 > max_clip_x)
                {
                // east vline intersection
                xc1 = max_clip_x;
                yc1 = y1 + 0.5+(max_clip_x-x1)*(y2-y1)/(x2-x1);
                } // end if

           } break;

      case CLIP_CODE_SE:
             {
           // south hline intersection
           yc1 = max_clip_y;
           xc1 = x1 + 0.5+(max_clip_y-y1)*(x2-x1)/(y2-y1);

           // test if intersection is valid,
           // if so then done, else compute next
           if (xc1 < min_clip_x || xc1 > max_clip_x)
              {
              // east vline intersection
              xc1 = max_clip_x;
              yc1 = y1 + 0.5+(max_clip_x-x1)*(y2-y1)/(x2-x1);
              } // end if

           } break;

      case CLIP_CODE_NW:
             {
           // north hline intersection
           yc1 = min_clip_y;
           xc1 = x1 + 0.5+(min_clip_y-y1)*(x2-x1)/(y2-y1);
           
	     // test if intersection is valid,
           // if so then done, else compute next
           if (xc1 < min_clip_x || xc1 > max_clip_x)
              {
              xc1 = min_clip_x;
              yc1 = y1 + 0.5+(min_clip_x-x1)*(y2-y1)/(x2-x1);
              } // end if

           } break;

      case CLIP_CODE_SW:
           {
           // south hline intersection
           yc1 = max_clip_y;
           xc1 = x1 + 0.5+(max_clip_y-y1)*(x2-x1)/(y2-y1);

           // test if intersection is valid,
           // if so then done, else compute next
           if (xc1 < min_clip_x || xc1 > max_clip_x)
              {
              xc1 = min_clip_x;
              yc1 = y1 + 0.5+(min_clip_x-x1)*(y2-y1)/(x2-x1);
              } // end if

           } break;

      default:break;

      } // end switch
// determine clip point for p2
switch(p2_code)
      {
      case CLIP_CODE_C: break;

      case CLIP_CODE_N:
           {
           yc2 = min_clip_y;
           xc2 = x2 + (min_clip_y-y2)*(x1-x2)/(y1-y2);
           } break;

      case CLIP_CODE_S:
           {
           yc2 = max_clip_y;
           xc2 = x2 + (max_clip_y-y2)*(x1-x2)/(y1-y2);
           } break;

      case CLIP_CODE_W:
           {
           xc2 = min_clip_x;
           yc2 = y2 + (min_clip_x-x2)*(y1-y2)/(x1-x2);
           } break;

      case CLIP_CODE_E:
           {
           xc2 = max_clip_x;
           yc2 = y2 + (max_clip_x-x2)*(y1-y2)/(x1-x2);
           } break;

        // these cases are more complex, must compute 2 intersections
      case CLIP_CODE_NE:
           {
           // north hline intersection
           yc2 = min_clip_y;
           xc2 = x2 + 0.5+(min_clip_y-y2)*(x1-x2)/(y1-y2);

           // test if intersection is valid,
           // if so then done, else compute next
            if (xc2 < min_clip_x || xc2 > max_clip_x)
                {
                // east vline intersection
                xc2 = max_clip_x;
                yc2 = y2 + 0.5+(max_clip_x-x2)*(y1-y2)/(x1-x2);
                } // end if

           } break;

      case CLIP_CODE_SE:
             {
           // south hline intersection
           yc2 = max_clip_y;
           xc2 = x2 + 0.5+(max_clip_y-y2)*(x1-x2)/(y1-y2);
           // test if intersection is valid,
           // if so then done, else compute next
           if (xc2 < min_clip_x || xc2 > max_clip_x)
              {
              // east vline intersection
              xc2 = max_clip_x;
              yc2 = y2 + 0.5+(max_clip_x-x2)*(y1-y2)/(x1-x2);
              } // end if

           } break;

      case CLIP_CODE_NW:
             {
           // north hline intersection
           yc2 = min_clip_y;
           xc2 = x2 + 0.5+(min_clip_y-y2)*(x1-x2)/(y1-y2);

           // test if intersection is valid,
           // if so then done, else compute next
           if (xc2 < min_clip_x || xc2 > max_clip_x)
              {
              xc2 = min_clip_x;
              yc2 = y2 + 0.5+(min_clip_x-x2)*(y1-y2)/(x1-x2);
              } // end if

           } break;

      case CLIP_CODE_SW:
           {
           // south hline intersection
           yc2 = max_clip_y;
           xc2 = x2 + 0.5+(max_clip_y-y2)*(x1-x2)/(y1-y2);

           // test if intersection is valid,
           // if so then done, else compute next
           if (xc2 < min_clip_x || xc2 > max_clip_x)
              {
              xc2 = min_clip_x;
              yc2 = y2 + 0.5+(min_clip_x-x2)*(y1-y2)/(x1-x2);
              } // end if

           } break;

      default:break;

      } // end switch

// do bounds check
if ((xc1 < min_clip_x) || (xc1 > max_clip_x) ||
    (yc1 < min_clip_y) || (yc1 > max_clip_y) ||
    (xc2 < min_clip_x) || (xc2 > max_clip_x) ||
    (yc2 < min_clip_y) || (yc2 > max_clip_y) )
    {
    return(0);
    } // end if

// store vars back
x1 = xc1;
y1 = yc1;
x2 = xc2;
y2 = yc2;

return(1);

} // end Clip_Line

All you do is send the function the endpoints of the line, and it clips them to the clipping rectangle defined by the globals:

int min_clip_x = 0,      // clipping rectangle
    max_clip_x = SCREEN_WIDTH-1,
    min_clip_y = 0,
    max_clip_y = SCREEN_HEIGHT-1;

I usually set these globals to the size of the screen. The only detail about the function is that it takes the parameters as a call by the reference, so the variables can be modified. Make copies if you don't want the variables to be changed. Here's an example of the function in use:

// clip the line (x1,y1) to (x2,y2)

// make copies
int clipped_x1 = x1,
    clipped_y1 = y1,
    clipped_x2 = x2,
    clipped_y2 = y2;

// clip the line
Clip_Line(clipped_x1, clipped_y1,
          clipped_x2, clipped_y2);

When the function returns the clipped_* variables, they will have new clipped values based on the clipping rectangle stored in the globals.

The demo, DEMO8_2.CPP|EXE, creates a 200x200 clipping region that is centered on the screen and then draws random lines within it. Notice how they're clipped <BG>.