Polygon Clipping

Polygon Clipping (Sutherland-Hodgman):

• Window must be a convex polygon
• Polygon to be clipped can be convex or not

Approach:

• Polygon to be clipped is given as
• Each polygon edge is a pair
  • Don't forget wraparound; is also an edge
• Process all polygon edges in succession against a window edge
  • Polygon in - polygon out
  • 
• Repeat on resulting polygon with next sequential window edge

Contrast with Line Clipping:

• Line Clipping:
  • Use outcodes to check all window edges before any clip
  • Clip only against possibly intersecting window edges
  • Deal with window edges in any order
  • Deal with line segment endpoints in either order
• Polygon Clipping:
  • Each window edge must be used
  • Polygon edges must be handled in sequence
  • Polygon edge endpoints have a given order
  • Stripped-down line-segment/window-edge clip is a subtask

There are four cases to consider

Four Cases:

• is the polygon edge starting vertex
• is the polygon edge ending vertex
• i is a polygon-edge/window-edge intersection point
• is the next polygon vertex to be output

Case 1:

Polygon edge is entirely inside the window edge

• p is next vertex of resulting polygon
• 

\

Case 2:

Polygon edge crosses window edge going out

• Intersection point i is next vertex of resulting polygon
• 

\

Case 3:

Polygon edge is entirely outside the window edge

• No output

\

Case 4:

Polygon edge crosses window edge going in

• Intersection point i and p are next two vertices of resulting polygon
• 

\

Simple Examples:

...

An Example:

With a non-convex polygon...

\

Readings: Hearn and Baker, Section 6-8; Red book, 3.11; White book, 3.14.