Sutherland–Hodgman algorithm: Difference between revisions

Revision as of 02:57, 22 August 2019

Latest revision as of 10:26, 5 June 2024

(15 intermediate revisions by 12 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==

Line 10 ⟶ 11:

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

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();

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

Point current_point = inputList[i];

Point prev_point = inputList[(i + inputList.count -− 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);

'''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]].

''ComputeIntersection'' is a function, omitted here for clarity, which returns the intersection of a line segment and an infinite edge. Note that itthe intersecting point is only calledadded ifto suchthe anoutput list when the intersection is known to exist, andtherefore henceboth lines can simplyalways treatbe both linestreated as being infinitely long.

==Implementations==

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

==See also==

Other polygon clipping 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==

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