CS-460/560, Week 9A Spring, 1998 R. Eckert POLYGON CLIPPING: THE SUTHERLAND-HODGMAN POLYGON CLIPPER-- Clip a polygon to a rectangular clip area whose boundaries are parallel to the x-y coordinate system axes. Input: an ordered list of polygon vertices (nin, vin[]) and the clip region boundary coordinates (xmin, ymin, xmax, ymax). Output: an ordered list of clipped polygon vertices (nout, vout[]). Here vin[] and vout[] could be an arrays of POINTs. (In the following, vertex variables that begin with upper case letters represent single vertex points. Lower case vertex variables represent arrays of points.) Approach: clip all edges of the polygon with respect to each clipping boundary. Do four passes. On each pass, traverse the polygon and clip with respect to one of the four boundaries. Assemble the output polygon as you go. The output polygon of the clipping with respect to boundary i will become the input polygon with respect to boundary i+1. In other words: vin[] --> Clip Left --> vtemp1[] --> Clip Right --> vtemp2[] --> Clip Bottom --> vtemp3[] --> Clip Top --> vout[] As we traverse the polygon on any of these four passes, the clipping boundary divides the plane into an "in" side half-plane and an "out" side half-plane. For any given edge (characterized by vertices i and i+1), during the traversal, there are four possibilities: vertex i vertex i+1 Action ------------------------------------------------------------------- in in Add vertex i+1 to output list out out Add no vertex to the output list in out Add intersection pt with edge to output list out in Add intersection pt with edge to ouput list as well as vertext i+1 Here we assume that vertex i was taken care of when the previous edge was processed. We want to implement a function sh_clip() that will clip an input polygon (ni, vi[]) with respect to a given boundary (bndry), generating an output polygon (no, vo[]). We will enumerate the boundaries as LEFT, RIGHT, BOTTOM, and TOP. sh_clip(ni, vi[], no, vo[], xmin, ymin, xmax, ymax, bndry); Here vi[] and vo[] could both be arrays of POINTs, and ni, no are the numbers of points in each array. xmin, ymin, xmax, ymax are the clip region boundary coordinates. In order to clip the input polygon (nin, vin[]), to the clip region (xmin, xmax, ymin, ymax), generating the output polygon (nout, vout[]), we would make four calls to sh_clip(): sh_clip(nin, vin[], ntemp1, vtemp1[], xmin, ymin, xmax, ymax, LEFT); sh_clip(ntemp1, vtemp1[], ntemp2, vtemp2[], xmin, ymin, xmax, ymax, RIGHT); sh_clip(ntemp2, vtemp2[], ntemp3, vtemp3[], xmin, ymin, xmax, ymax, BOTTOM); sh_clip(ntemp3, vtemp3[], nout, vout[], xmin, ymin, xmax, ymax, TOP); To facilitate the development of sh_clip(), assume we have the following three helper functions: BOOL inside(V, xmin, ymin, xmax, ymax, Bndry) -- Returns TRUE if vertex point V is on the "in" side of boundary Bndry. VOID intersect(V1, V2, xmin, ymin, xmax, ymax, Bndry, Vnew) -- Computes the intersection point of the edge whose endpoints are V1 and V2 with boundary Bndry and returns the resulting point in Vnew. VOID output(V, n, vout[]) -- Adds vertex point V to the polygon (n, v[]). Here n will be incremented by 1 and vertex V added to the end of the polygon's vertex list v[]. PSEUDO-CODE FOR sh_clip() -- sh_clip(ni, vi[], no, vo[], bndry) { no = 0 // output list begins empty First_V = vi[0] // current edge's first vertex (i) For (j=0 to ni-1) // traverse the polygon Second_V = v[(j+1) MOD ni] // current edge's second vertex (i+1) If (inside(first_V, bndry) If (inside(Second_V, bndry) // "in-in" case output(Second_V, no, vo) Else // "in-out" case intersect(First_V, Second_V, bndry, Vtemp) output (Vtemp, no, vo) Else If (inside(Second_V, bndry) // "out-in" case intersect(First_V, Second_V, bndry, Vtemp) output(Vtemp, no, vo) output(Second_V, no, vo) // note empty Else ("out-out" case) First_V = Second_V // prepare for next edge } Note that this works fine with convex polygons, but can have problems with some concave polygons. In some cases extraneous edges along the clip boundary may be generated as a part of the output polygon. One way to solve this problem would be to add a postprocessing step in which we check the output vertex list for multiple vertex points along any clip boundary and correctly join pairs of vertices. A better approach is to use a more general clipping algorithm, such as the Weiler-Atherton polygon clipper. THE WEILER-ATHERTON POLYGON CLIPPING ALGORITHM-- Clips a "Subject Polygon" to a "Clip Polygon" giving one or more output polygons that lie entirely inside the clip polygon. Both polygons can be of any shape. 1. Set up the vertex list for the subject and clip polygons. (The ordering should be such that as you move down each list the inside of the polygon is always on the right side.) 2. Compute all intersection points between subject polygon and clip polygon edges; insert them into each polygon's list; mark as intersection points. Mark those intersection points in which the subject polygon edge is moving from outside of the clip polygon to inside. (outside/inside tests on subject polygon edge endpoints.) 3. Do until all intersection points have been visited: Traverse the subject polygon list until you find a non-visited intersection point; output the point to a new output list. Make the subject polygon list be the active list. Do until a vertex is revisited: Get the next vertex from the active list and output. If vertex is an intersection point, make the other list active. End the current output polygon list.