Computer Graphics - Clipping

1. Line Clipping

This section treats clipping of lines against rectangles. Although there are specialized algorithms for rectangle and polygon clipping, it is important to note that other graphic primitives can be clipped by repeated application of the line clipper.

1.1 Clipping Individual Points

Before we discuss clipping lines, let's look at the simpler problem of clipping individual points.

If the x coordinate boundaries of the clipping rectangle are Xmin and Xmax, and the y coordinate boundaries are Ymin and Ymax, then the following inequalities must be satisfied for a point at (X,Y) to be inside the clipping rectangle:

Xmin < X < Xmax and Ymin < Y < Ymax

If any of the four inequalities does not hold, the point is outside the clipping rectangle.

1.2 Solve Simultaneous Equations

To clip a line, we need to consider only its endpoints, not its infinitely many interior points. If both endpoints of a line lie inside the clip rectangle, the entire line lies inside the clip rectangle and can be trivially accepted. If one endpoint lies inside and one outside(eg CD), the line intersects the clip rectangle and we must compute the intersection point. If both endpoints are outside the clip rectaangle, the line may or may not intersect with the clip rectangle (EF, GH, and IJ), and we need to perform further calculations to determine whether there are any intersections.

The brute-force approach to clipping a line that cannot be trivially accepted is to intersect that line with each of the four clip-rectangle edges to see whether any intersection points lie on those edges; if so, the line cuts the clip rectangle and is partially inside. For each line and clip-rectangle edge, we therefore take the two mathematically infinite lines that contain them and intersect them. Next, we test whether this intersection point is "interior" -- that is, whether it lies within both the clip rectangle edge and the line; if so, there is an intersection with the clip rectangle. In the first example, intersection points G' and H' are interior, but I' and J' are not.

1.3 The Cohen-Sutherland Line-Clipping Algorithm

The more efficient Cohen-Sutherland Algorithm performs initial tests on a line to determine whether intersection calculations can be avoided.

Steps for Cohen-Sutherland algorithm

End-points pairs are check for trivial acceptance or trivial rejected using the outcode.

If not trivial-accepance or trivial-rejected, divided into two segments at a clip edge.

Iteratively clipped by testing trivial-acceptance or trivial-rejected, and divided into two segments until completely inside or trivial-rejected.

Trivial acceptance/reject test

To perform trivial accept and reject tests, we extend the edges of the clip rectangle to divide the plane of the clip rectangle into nine regions. Each region is assigned a 4-bit code deteermined by where the region lies with respect to the outside halfplanes of the clip-rectangle edges. Each bit in the outcode is set to either 1 (true) or 0 (false); the 4 bits in the code correspond to the following conditions:

• Bit 1 : outside halfplane of top edge, above top edge
  Y > Ymax

• Bit 2 : outside halfplane of bottom edge, below bottom edge
  Y < Ymin

• Bit 3 : outside halfplane of right edge, to the right of right edge
  X > Xmax

• Bit 4 : outside halfplane of left edge, to the left of left edge
  X < Xmin

Conclusion

In summary, the C-S algorithm is efficient when outcode testing can be done cheaply (for example, by doing bitwise operations in assembly language) and trivial acceptance or rejection is applicable to the majority of line segments .(For example, large windows - everything is inside , or small windows - everything is outside).

Pseudo-code of Cohen-Sutherland Algorithm.

2. Polygon Clipping

An algorithm that clips a polygon must deal with many different cases. The case is particularly note worthy in that the concave polygon is clipped into two separate polygons. All in all, the task of clipping seems rather complex. Each edge of the polygon must be tested against each edge of the clip rectangle; new edges must be added, and existing edges must be discarded, retained, or divided. Multiple polygons may result from clipping a single polygon. We need an organized way to deal with all these cases.

The following example illustrate a simple case of polygon clipping:

The following example illustrate a complex case of polygon clipping:

Sutherland and Hodgman's polygon-clipping algorithm uses a divide-and-conquer strategy: It solves a series of simple and identical problems that, when combined, solve the overall problem. The simple problem is to clip a polygon against a single infinite clip edge. Four clip edges, each defining one boundary of the clip rectangle, successively clip a polygon against a clip rectangle.

Note the difference between this strategy for a polygon and the Cohen-Sutherland algorithm for clipping a line: The polygon clipper clips against four edges in succession, whereas the line clipper tests the outcode to see which edge is crossed, and clips only when necessary.

Steps of Sutherland-Hodgman's polygon-clipping algorithm

• Polygons can be clipped against each edge of the window one at a time. Windows/edge intersections, if any, are easy to find since the X or Y coordinates are already known.

• Vertices which are kept after clipping against one window edge are saved for clipping against the remaining edges.

• Note that the number of vertices usually changes and will often increases.

• We are using the Divide and Conquer approach.

Four Cases of polygon clipping against one edge

The clip boundary determines a visible and invisible region. The edges from vertex i to vertex i+1 can be one of four types:

• Case 1 : Wholly inside visible region - save endpoint

Points=[B]

• Case 2 : Exit visible region - save the intersection

Points=[B, B']

• Case 3 : Wholly outside visible region - save nothing

Points=[B, B']

• Case 4 : Enter visible region - save intersection and endpoint

Points=[B, B', C', A]

Because clipping against one edge is independent of all others, it is possible to arrange the clipping stages in a pipeline. The input polygon is clipped against one edge and any points that are kept are passed on as input to the next stage of the pipeline. This way four polygons can be at different stages of the clipping process simultaneously. This is often implemented in hardware.

Sutherland-Hodgman uses a divide-and-conquer strategy to attack the problem. First, it clips the polygon against the right clipping boundary. The resulting, partly clipped polygon is then clipped against the top boundary, and then the process is repeated for the two remaining boundaries. (Of course, it also works in another order.) In a way, it is the most natural thing to do. If you had to clip a paper polygon with a pair of scissors, you would probably proceed the same way.

Sutherland-Hodgman's divide-and-conquer strategy. To clip a polygon against a rectangular boundary window, successively clip against each boundary.

To clip against one boundary, the algorithm loops through all polygon vertices. At each step, it considers two of them, called 'previous' and 'current.' First, it determines whether these vertices are inside or outside the clipping boundary. This, of course, is simply a matter of comparing the horizontal or vertical position to the boundary's position.

Then, it applies the following simple rules:

	If 'previous' and 'current' are both inside: Output 'current.'
	If 'previous' is inside, and 'current' is outside: Output the intersection point of the corresponding edge and the clipping boundary.
	If 'previous' and 'current' are both outside: Do nothing.
	If 'previous' is outside, and 'current' is inside: Output the intersection point, and then output 'current.'

This way, you get a new polygon, clipped against one boundary, and ready to be clipped against the next boundary. The method works, but has one disadvantage: To clip against all four boundaries, you have to store the intermediate, partly clipped polygons. It's evident that this is a costly operation.

Luckily, there are ways to avoid the intermediate storage. Instead of storing an output point, you can send it to the next stage immediately, where it can be clipped against the next boundary.

The classical way to do this is to make one general boundary-clipping function, which calls itself recursively to put a vertex to the next stage. An extra parameter tells the function which boundary to use for clipping. Inside the function, a few switch statements account for the differences.

A somewhat faster option is to create separate functions for the four boundaries, thus eliminating the nasty switch statements. However, this means developing and debugging four very similar functions, which is an open invitation for all kinds of trouble.

Pseudo-Code of Sutherland and Hodgman's polygon-clipping Algorithm.

type
    vertex = point;    /*point hold real x,y*/
    edge = array[1..2] of vertex;
    vertexArray = array[1..MAX] of vertex; /*MAX is a declared constant*/

procedure SutherlandHodgmanPolygoClip (
    inVertexArray : vertexArray;          /*Input vertex array*/
    var outVertexArray : vertexArray;  /*Output vertex array*/
    inLength : integer;                   /*Number of entries in inVertexArray*/
    var outLength : integer;           /*Number of entries in outVertexArray*/
    clipBoundary : edge);              /*Edge of clip polygon*/
var
    s,p,                            /*Start, end point of current polygon edge*/
    i : vertex;                   /*Intersection point with a clip boundary*/
    j : integer;                  /*Vertex loop counter*/

    procedure Output(
              newVertex : vertex; var outLength : integer; var outVertexArray : vertexArray);
    /*Adds newVertex to outVertexArray and then updates outLength */
    begin
    ...
    end;

    function Inside(testVertex : vertex; clipBoundary : edge):boolean;
    /*Checks whether the vertex lies inside the clip edge or not*/
    begin
    ...
    end;

    procedure Intersect(first,second:vertex; clipBoundary:edge; var intersectPt:vertex);
    /*Clips polygon edge (first,second) against clipBoundary, outputs the new point*/
    begin
    ...
    end;

begin
    outLength := 0;
    s := inVertexArray[inLength];
    /*Start with the last vertex in inVertexArray*/
    for j := 1 to inLength do
      begin
        p := inVertexArray[j]; /*Now s and p correspond to the vertices in Fig. 3.48*/
        if Inside(p,clipBoundary) then       /*Cases 1 and 4*/
          if Inside(s, clipBoundary) then
            Output(p, outLength, outVertexArray)    /*Case 1*/
          else
            begin
              Intersect(s, p, clipBoundary, i);
              Output(i, outLength, outVertexArray);
              Output(p, outLength, outVertexArray)
            end
        else                                        /*Cases 2 and 3*/
          if Inside(s, clipBoundary) then           /*Cases 2*/
            begin
              Intersect(s, p, clipBoundary, i);
              Output(i, outLength, outVertexArray)
            end;                           /*No action for case 3*/
        s := p                             /*Advance to next pair of vertices*/
      end /*for*/
end; /*SutherlandHodgmanPolygonClip*/

Authors: Huiling Yang, Haowei Hsieh and Sjaak Priester