Sutherland-Hodgman clipping algorithm

From Wikipedia, the free encyclopedia

The Sutherland-Hodgman algorithm is used for clipping polygons. It works by extending each line of the clip polygon in turn and selecting only vertices from the subject polygon that are on the visible side.

1 Description
2 Pseudo Code
3 See also
4 External links

[edit] 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 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.

The Weiler-Atherton algorithm overcomes this by returning a set of divided polygons, but is more complex and computationally more expensive, so Sutherland-Hodgman is used for many rendering applications. Sutherland-Hodgman can also be extended into 3D space by clipping the polygon paths based on the boundaries of planes defined by the viewing space.

[edit] Pseudo Code

Given a specific clip plane and an array containing the vertices of a single polygon, the following procedure clips the polygon against the plane.

  arrayLength = array.size
  vertex S = array[ arrayLength - 1 ]
  for( j = 0, j < arrayLength, j = j+1 )
  {
     vertex P = array[ j ]
     if( P is inside clip_plane )
     {
        if( S is inside clip_plane )
        {
           Output( P )
        }
        else
        {
           Output( ComputeIntersection( S, P, clip_plane ) )
           Output( P )
        }
     }
     else if( S is inside clip_plane )
     {
        Output( ComputeIntersection( P, S, clip_plane ) )
     }
     S = P
  }

Output and ComputeIntersection are functions that have not been implemented here for ease of readability (and they are not very complex).

Output is generally some function or code that adds a vertex to an array.

ComputeIntersection finds the intersection point of a line segment and a clip plane and returns that value (a vertex).