Sutherland–Hodgman algorithm: Difference between revisions

Revision as of 18:04, 18 May 2009

Revision as of 19:54, 18 May 2009

Line 2:

==Description==

Begin with a set of all vertices in the subject polygon. Assuming the clip polygon is a rectangle, start by extending the upper side across the whole of the 2D space we are considering. Next, starting from the first vertex of the subject polygon, follow the path of the polygon to the next vertex in the subject polygon. Create new vertices where the path crosses the extended clip polygon line. Repeat this until we are back at the first subject polygon vertex. Now create a new set of all vertices that are on or beneath the extended clip polygon line, including vertices from the clip polygon that are entirely within the subject polygon.

We then need to repeat this process for each clip polygon side by extending the line and creating new sets of vertices that are on the visible side. Once the process is complete, a set of vertices will define a new single polygon that is entirely visible. However, if the subject polygon was [[concave polygon|concave]] at vertices outside the clipping polygon, the new polygon may have coincident (i.e. overlapping) edges - this is acceptable for rendering, but not for other applications such as computing shadows.