CSCE 441 Lecture 7

« previous | Wednesday, January 29, 2014 | next »

Polygon Clipping (cont'd)

Sutherland-Hodgman Clipping

Consider each edge of view window and clip polygon against that edge's equation

Works for convex polygons, but concave shapes may not work correctly.

Easy to pipeline for parallel processing → substantial performance gains

Algorithm

Input: ordered list of polygon vertices Output: ordered list of clipped polygon vertices

Idea: Edge from start vertex $s$ to end vertex $e$ takes one of 4 cases when taken with respect to an edge:

• outside-to-outside → no output
• inside-to-inside → $e$
• inside-to-outside → new intersection point $i$
• outside-to-inside → new intersection point $i$ and $e$

Simplified rules:

• If endpoints are on different sides of the boundary, output the intersection point $i$.
• If the ending point $e$ is inside, also output it.

def clip_to_edge(edge, points):
    first_point = points[0]

    n = len(points)

    output = []
    for i in xrange(0, n):
        a = points[i]
        b = points[i+1] if i+1 == n

Weiler-Atherton Algorithm

General polygon vs. polygon clipping Even handles non-convex shapes

Relatively poor efficiency compared to Sutherland-Hodgman.

Idea:

1. Process edges of polygon in CCW order until an inside-outside pair of vertices is encountered.
2. Follow window boundaries in CCW direction from exit-intersection point to another intersection point with the polygon.
3. Repeat until at a previously processed vertex.
4. ...
5. output polygon
6. If points remain, Go back to point where polygon exited the boundary
7. Follow edges until an outside-inside pair is encountered