- 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

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

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
- Solve Simultaneous Equations
- The Cohen-Sutherland Line-Clipping 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.
- 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

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

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 more efficient Cohen-Sutherland Algorithm performs initial tests on a line to determine whether intersection calculations can be avoided.

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:

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

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.

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

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.

Go back to Table of Contents

Back to Computer Graphics Courseware

Contact:

Haowei Hsieh

hhsieh@cc.gatech.edu

http://www.cc.gatech.edu/gvu/people/Masters/Haowei.Hsieh.html

Last Change : Feb 27,1995