The Sutherland–Hodgman algorithm is an algorithm used for clippingpolygons. It works by extending each line of the convexclip polygon in turn and selecting only vertices from the subject polygon that are on the visible side.
The algorithm begins with an input 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 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.
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.
Pseudocodeedit
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 − 1) % inputList.count]; Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge) if (current_point inside clipEdge) thenif (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 ifdonedone
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 the intersecting 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 long.
Implementationsedit
A Python implementation of the Sutherland-Hodgman can be found here.
Mel Slater, Anthony Steed, Yiorgos Chrysanthou: Computer Graphics and Virtual Environments: From Realism to Real-Time. Addison Wesley. ISBN0-201-62420-6.
Polygon clipping and filling Describes the algorithm using images that are easy to understand.
Rosetta Code example
April 12, 2024
sutherland, hodgman, algorithm, algorithm, used, clipping, polygons, works, extending, each, line, convex, clip, polygon, turn, selecting, only, vertices, from, subject, polygon, that, visible, side, contents, description, pseudocode, implementations, also, re. The Sutherland Hodgman algorithm is an algorithm used for clipping polygons It works by extending each line of the convex clip polygon in turn and selecting only vertices from the subject polygon that are on the visible side Contents 1 Description 2 Pseudocode 3 Implementations 4 See also 5 References 6 External linksDescription editThe algorithm begins with an input 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 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 nbsp All steps for clipping concave polygon W with a 5 sided convex polygonThe 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 Pseudocode editGiven 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 lt 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 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 the intersecting 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 long Implementations editA Python implementation of the Sutherland Hodgman can be found here See also editOther polygon clipping algorithms Weiler Atherton clipping algorithm Vatti clipping algorithmOn the subject of clipping Clipping computer graphics Clipping in rasterisation Line clipping algorithmsReferences editMel Slater Anthony Steed Yiorgos Chrysanthou Computer Graphics and Virtual Environments From Realism to Real Time Addison Wesley ISBN 0 201 62420 6 Ivan Sutherland Gary W Hodgman Reentrant Polygon Clipping Communications of the ACM vol 17 pp 32 42 1974External links editPolygon clipping and filling Describes the algorithm using images that are easy to understand Rosetta Code example Retrieved from https en wikipedia org w index php title Sutherland Hodgman algorithm amp oldid 1059508774, wikipedia, wiki, book, books, library,
