Free JavaScript Editor Ajax Editor

↑

Main Page

## Basic 2D ClippingThere 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. ## Figure 8.8. The general line clipping problem.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. ## Figure 8.9. The clipping process diagrammed.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 TIP If you're uneasy with the parametric form, don't worry. I'll explain parametric equations shortly. In addition, note that the Point Slope form and the Two Point form are really the same because in both cases m = (y1 – y0)/(x1 – x0). ## Computing the Intersection of Two Lines Using the Point Slope FormOff 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). ## Figure 8.10. Computing the intersection of two lines.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 FormThe 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 MATH The (-1) and the associated multiplies aren't necessary. They just make the extraction of (a,b,c) easier to see. ## Computing the Intersection of Two Lines Using the Matrix FormSo 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 A Simplifying: X = A 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 LineAs 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. ## Figure 8.11. Clipping against a rectangle is much easier than t he general case.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 AlgorithmIn 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 ## Figure 8.12. Using clipping codes for efficient line endpoint determination.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 The demo, |

↓

Ajax Editor JavaScript Editor