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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} to end vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} takes one of 4 cases when taken with respect to an edge:

• outside-to-outside → no output
• inside-to-inside → Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e}
• inside-to-outside → new intersection point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
• outside-to-inside → new intersection point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e}

Simplified rules:

• If endpoints are on different sides of the boundary, output the intersection point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} .
• If the ending point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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