Question

Describe Sutherland-Hodgeman algorithm for polygon clipping.

Answer 1

In Sutherland-Hodgeman, a polygon is clipped by processing the polygon boundary as a whole against each window edge. Clipping window must be convex. This could be accomplished by processing all polygon vertices against each clip rectangle boundary in turn beginning with the original set of polygon vertices, first clip the polygon against the left rectangle boundary to produce a new sequence of vertices. The new set of vertices could then be successively passed to a right boundary clipper, a top boundary clipper and a bottom boundary clipper. At each step a new set of polygon vertices us generated and passed to the next window boundary clipper. This is the logic used in Sutherland-Hodgeman algorithm.

Fig. Clipping polygon against successive window boundaries

The output of algorithm is a list of polygon vertices all of which are on the visible side of clipping plane. Such each edge of the polygon is individually compared with the clipping plane. This is achieved by processing two vertices of each edge of the polygonaround the clipping boundary or plane. This results in four possible relationships between the edge and clipping plane.

1. If first vertex of polygon edge is outside and second is inside window boundary, then intersection point of polygon edge with window boundary and second vertex are added to output vertices set as shown in Fig. 6.13.

2. If both vertices of edge are inside window boundary, then add only second vertex to output set as shown in Fig. 6.14.

3. If first vertex of edge is inside and second is outside of window boundary then point of intersection of edge with window boundary is stored in output set as shown in Fig. 6.15.

4. If both vertices of edges are outside of window boundary then those vertices are rejected as shown in Fig. 6.16.

Going through above four cases we can realize that there are two key processes in this algorithm: 1. Determine the visibility of point or vertex (Inside – Outside Test) 2. Determine the intersection of the polygon edge and clipping plane. The second key process in Sutherland-Hodgeman polygon clipping algorithm is to determine the intersection of the polygon edge and clipping plane.

Assume that we're clipping a polygon’s edge with vertices at (x1, y1) and (x2,

y2) against a clip window with vertices at (xmin, ymin) and (xmax, ymax).

1. The location (IX, IY) of the intersection of the edge with the left side of the

window is:

(i) IX = xmin

(ii) IY = slope*(xmin – x1) + y1, where the slope = (y2 – y1)/(x2 – x1).

2. The location of the intersection of the edge with the right side of the

window is:

(i) IX = xmax

(ii) IY = slope*(xmax – x1) + y1, where the slope = (y2 – y1)/(x2 – x1)

3. The intersection of the polygon's edge with the top side of the window is:

(i) IX = x1 + (ymax – y1) / slope

(ii) IY = ymax

4. Finally, the intersection of the edge with the bottom side of the window is:

(i) IX = x1 + (ymin – y1) / slope

(ii) IY = ymin

Algorithm for Sutherland-Hodgeman Polygon Clipping:

Step 1: Read co-ordinates of all vertices of the polygon.

Step 2: Read co-ordinates of the clipping window.

Step 3: Consider the left edge of window.

Step 4: Compare vertices of each of polygon, individually with the clipping plane.

Step 5: Save the resulting intersections and vertices in the new list of vertices

according to four possible relationships between the edge and the

clipping boundary.

Step 6: Repeat the steps 4 and 5 for remaining edges of clipping window. Each

time resultant list of vertices is successively passed to process next

edge of clipping window.

Step 7: Stop.