Sutherland–Hodgman algorithm: Difference between revisions

Revision as of 01:38, 22 December 2007

Latest revision as of 10:26, 5 June 2024

(109 intermediate revisions by 76 users not shown)

Line 1:

{{Short description|Algorithm for clipping polygons}}

The '''Sutherland-–Hodgman algorithm''' is an [[algorithm]] 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==

BeginThe algorithm begins with aan input [[List set(computing)|list]] of all vertices in the subject polygon. Assuming the clip polygon is a rectangleNext, start by extending the upperone side acrossof the wholeclip ofpolygon theis 2Dextended spaceinfinitely wein areboth considering. Nextdirections, starting fromand the first vertexpath of the subject polygon, followis thetraversed. pathVertices offrom the polygoninput tolist theare nextinserted vertexinto inan theoutput subjectlist polygon.if Createthey newlie vertices whereon the pathvisible crossesside of the extended clip polygon line., Repeatand thisnew until wevertices are backadded atto the firstoutput subjectlist polygonwhere vertex.the Nowsubject createpolygon apath new set of all vertices that are on or beneathcrosses the extended clip polygon line, including vertices from the clip polygon that are entirely within the subject polygon.

WeThis thenprocess needis torepeated repeat this processiteratively for each clip polygon side, by extendingusing the lineoutput andlist creatingfrom newone setsstage ofas verticesthe thatinput arelist onfor the visible sidenext. Once all sides of the processclip ispolygon completehave been processed, athe setfinal generated list of vertices will definedefines a new single polygon that is entirely visible. However,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 for clipping concave polygon 'W' with a 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.

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==

==Pseudocode==

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

Given a specificlist of edges in a clip planepolygon, and ana arraylist containing theof vertices ofin a singlesubject polygon, the following procedure clips the subject polygon against the planeclip polygon.

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

}

List outputList = subjectPolygon;

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

'''for''' (Edge clipEdge in clipPolygon) '''do'''

List inputList = outputList;

outputList.clear();

'''for''' (int i = 0; i < inputList.count; i += 1) '''do'''

Point current_point = inputList[i];

Point prev_point = inputList[(i − 1) % inputList.count];

Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)

'''if''' (current_point inside clipEdge) '''then'''

'''if''' (prev_point not inside clipEdge) '''then'''

outputList.add(Intersecting_point);

Output( P'''end )if'''

outputList.add(current_point);

'''else if''' (prev_point inside clipEdge) '''then'''

outputList.add(Intersecting_point);

{'''end if'''

'''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 counter-clockwise direction, then this is equivalent to testing whether the point lies to the left of the line (left means ''inside'', while right means ''outside''), and can be implemented simply by using a [[cross product]].

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

'''ComputeIntersection''' findsis a function, omitted here for clarity, which returns the intersection point of a line segment and aan clipinfinite planeedge. and returnsNote that valuethe (aintersecting point is only added to the output list when the intersection is known to exist, therefore both lines can always be treated as being infinitely vertex)long.

==Implementations==

A Python implementation of the Sutherland-Hodgman can be found [https://github.com/mdabdk/sutherland-hodgman here].

==See also==

*[[Weiler-AthertonOther polygon clipping algorithm]]algorithms:

*[[Weiler&ndash;Atherton clipping algorithm]]

*[[Vatti clipping algorithm]]

On the subject of clipping:

*[[Clipping (computer graphics)]]

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

*[[Line clipping|Line clipping algorithms]]

== References==

* Mel Slater, Anthony Steed, Yiorgos Chrysanthou: ''Computer Graphics and Virtual Environments: From Realism to Real-Time.'' Addison Wesley, 2002. {{ISBN|0-201-62420-6}}.

* [[Ivan Sutherland]], Gary W. Hodgman: ''Reentrant Polygon Clipping.'' [[Communications of the ACM]], vol. 17, pp.&nbsp;32–42, 1974

==External links==

{{compu-graphics-stub}}

* [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.

* [https://rosettacode.org/wiki/Sutherland-Hodgman_polygon_clipping Rosetta Code example]

{{DEFAULTSORT:Sutherland-Hodgman algorithm}}

[[Category:Computer graphics stubs]]

[[Category:Polygon clipping algorithms]]