Clipping

detailed topics

• a simple example for line clipping.
• quiz about line clipping.
• outcode.
• pseudo-code of cohen-sutherland algorithm.
• step-by-step example of polygon clipping.
• pseudo-code of sutherland and hodgman's polygon-clipping algorithm.
• four cases in edge-by-edge clipping

1. concept

it is desirable to restrict the effect of graphics primitives to a subregion of the canvas, to protect other portions of the canvas. all primitives are clipped to the boundaries of this clipping rectangle; that is, primitives lying outside the clip rectangle are not drawn.

the default clipping rectangle is the full canvas ( the screen ), and it is obvious that we cannot see any graphics primitives outside the screen.

a simple example of line clipping can illustrate this idea.

go back to table of contents

2. 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.

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.

see if you can answer these questions

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 (eg ab, refer to the first example ), 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.

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

1. end-points pairs are check for trivial acceptance or trivial rejected using the outcode.
2. if not trivial-accepance or trivial-rejected, divided into two segments at a clip edge.
3. iteratively clipped by testing trivial-acceptance or trivial-rejected, and divided into two segments until completely inside or trivial-rejected.

pseudo-code of cohen-sutherland algorithm.

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).

go back to table of contents

1.3 clipping polygons

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.

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.

here is a step-by-step example of polygon clipping.

pseudo-code of sutherland and hodgman's polygon-clipping algorithm.

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
• case 2 : exit visible region - save the intersection
• case 3 : wholly outside visible region - save nothing
• case 4 : enter visible region - save intersection and endpoint

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.