Sutherland–Hodgman algorithm: Difference between revisions

Revision as of 05:32, 11 October 2010

Revision as of 05:32, 11 October 2010

Line 1:

The '''Sutherland–Hodgman algorithm''' is used for [[Clipping (computer graphics)|clipping]] [[polygon]]s. It works by extending each line of the [[convex polygon|convex]] ''clip polygon'' in turn and selecting only vertices from the ''subject polygon'' that are on the visible side.

==Description==

The algorithm begins with an input [[List (computing)|list]] of all vertices in the subject polygon. Next, one side of the clip polygon is extended infinitely in both directions, and the path of the subject polygon is traversed. Vertices from the input list are inserted into an output list if they lie on the visible side of the extended clip polygon line, and new vertices are added to the output list where the subject polygon path crosses the extended clip polygon line.

This process is repeated iteratively for each clip polygon side, using the output list from one stage as the input list for the next. Once all sides of the clip polygon have been processed, the final generated list of vertices defines a new single polygon that is entirely visible. Note that 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.

[[image:Sutherland-Hodgman_clipping_sample.svg|center|frame|All steps of clipping concave polygon 'W' by 5-sided convex polygon]]

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.

==Pseudo code==

Given a list of edges in a clip polygon, and a list of vertices in a subject polygon, the following procedure clips the subject polygon against the clip polygon.

List outputList = subjectPolygon;

for (Edge clipEdge in clipPolygon) do

List inputList = outputList;

outputList.clear();

Point S = inputList.last;

for (Point E in inputList) do

if (E inside clipEdge) then

if (S not inside clipEdge) then

outputList.add(ComputeIntersection(S,E,clipEdge));

end if

outputList.add(E);

else if (S inside clipEdge) then

outputList.add(ComputeIntersection(S,E,clipEdge));

end if

S = E;

done

done

The vertices of the clipped polygon are to be found in ''outputList'' when the algorithm terminates. Note that a point is defined as being ''inside'' an edge if it lies on the same side of the edge as the remainder of the polygon. If the vertices of the clip polygon are consistently listed in a clockwise direction, then this is equivalent to testing whether the point lies to the right of the line, and can be implemented simply by using a [[dot product]].

''ComputeIntersection'' is a trivial function, omitted here for clarity, which returns the intersection of a line segment and an infinite edge. Note that it is only called if such an intersection is known to exist, and hence can simply treat both lines as being infinitely long.

==See also==

*[[Weiler–Atherton clipping algorithm]]

*[[Vatti clipping algorithm]]

*[[Rasterisation#Clipping|Clipping (in rasterisation)]]

==External links==

* [http://www.cs.drexel.edu/~david/Classes/CS430/Lectures/L-05_Polygons.6.pdf Polygon clipping and filling] Describes the algorithm using images that are easy to understand.

[[Category:Clipping (computer graphics)]]

[[Category:Computer graphics stubs]]

{{compu-graphics-stub}}

[[de:Algorithmus von Sutherland-Hodgman]]

[[fr:Algorithme de Sutherland-Hodgman]]

[[pl:Algorytm Sutherlanda-Hodgmana]]