Weiler–Atherton clipping algorithm: Difference between revisions

Revision as of 05:20, 25 May 2012

Latest revision as of 05:51, 4 July 2023

(32 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Polygon clipping algorithm}}

The '''Weiler–Atherton [[Clipping (computer graphics)|clipping]] algorithm''' is used in [[computer graphics]].

The '''Weiler–Atherton''' is a polygon-[[Clipping (computer graphics)|clipping]] [[algorithm]]. It is used in areas like [[computer graphics]] and games development where clipping of polygons is needed. It allows clipping of a ''subject or candidate polygon'' by an arbitrarily shaped ''clipping polygon/area/region''.

It allows clipping of a ''subject polygon'' by an arbitrarily shaped ''clip polygon'' window. It is generally applicable only in [[2D computer graphics|2D]]. However, it can be used in [[3D computer graphics|3D]] through visible surface determination and with improved efficiency through [[Z-order| Z-ordering]]. <ref> Foley, James, Andries van Dam, Steven Feiner, and John Hughes. "Computer Graphics: Principle and Practice". Addison-Wesley Publishing Company. Reading, Massachusetts: 1987. pages 689-693</ref>

It allows clipping of a ''subject polygon'' by an arbitrarily shaped ''clip polygon'' window. It is generally applicable only in [[2D computer graphics|2D]]. However, it can be used in [[3D computer graphics|3D]] through visible surface determination and with improved efficiency through [[Z-order| Z-ordering]]ing. <ref> Foley, James, Andries van Dam, Steven Feiner, and John Hughes. "Computer Graphics: Principle and Practice". Addison-Wesley Publishing Company. Reading, Massachusetts: 1987. pages 689-693</ref>

== Description ==

== Preconditions ==

[[image:Weiler-Atherton subdivision.svg|thumb|upright=1.2|Subdivision with the Weiler-Atherton algorithm]]

Before being applied to a polygon, the algorithm requires several preconditions to be fulfilled:

The algorithm requires polygons to be clockwise and not reentrant (self intersecting). The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes. Merging of polygons can also be performed by a variant of the algorithm.

* Candidate polygons need to be oriented clockwise.

Two lists are created from the coordinates of each polygons A and B, where A is the clip region and B is the polygon to be clipped.

* Candidate polygons should not be self-intersecting (i.e., re-entrant).

The algorithm requires polygons to be clockwise and not reentrant (self intersecting).* The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes., after Mergingwhich merging of the polygons can also be performed byusing a variant of the algorithm.

== Algorithm ==

The list entries are labelled as either inside or outside the other polygon. Various strategies can be used to improve the speed of this labelling, and to avoid needing to proceed further.

Given polygon A as the clipping region and polygon B as the subject polygon to be clipped, the algorithm consists of the following steps:

# List the vertices of the clipping-region polygon A and those of the subject polygon B.

# Label the listed vertices of subject polygon B as either inside or outside of clipping region A.

All# Find all the polygon intersections are then found and areinsert insertedthem into both lists, linking the lists at the intersections. Care will be needed where the polygons share an edge.

# Generate a list of "inbound" intersections – the intersections where the vector from the intersection to the subsequent vertex of subject polygon B begins inside the clipping region.

# Follow each intersection clockwise around the linked lists until the start position is found.

If there are no intersections then one of three situationsconditions existmust be true:

All the polygon intersections are then found and are inserted into both lists, linking the lists at the intersections. Care will be needed where the polygons share an edge.

# A is inside B -– return A for clipping, B for merging.

# B is inside A -– return B for clipping, A for merging.

# A and B do not overlap -– return None for clipping or A & B for merging.

== Conclusion ==

If there are no intersections then one of three situations exist:

A list of inbound intersections is then generated. Each intersection in the list is then followed clockwise around the linked lists until the start position is found. One or more concave polygons may produce more than one intersecting polygon. Convex polygons will only have one intersecting polygon.

# A is inside B - return A for clipping, B for merging.

# B is inside A - return B for clipping, A for merging.

# A and B do not overlap - return None for clipping or A & B for merging.

A list of inbound intersections is then generated. Each intersection in the list is then followed clockwise around the linked lists until the start position is found. One or more concave polygons may produce more than one intersecting polygon. Convex polygons will only have one intersecting polygon.

The same algorithm can be used for merging two polygons by starting at the outbound intersections rather than the inbound ones. However this can produce counter-clockwise holes.

Line 23 ⟶ 32:

Some polygon combinations may be difficult to resolve, especially when holes are allowed.

Points very close to the edge of the other polygon may be considered as both in and out until their status can be confirmed after all the intersections have been found and verified,; however, this increases the complexity.

The list entries are labelled as either inside or outside the other polygon. Various strategies can be used to improve the speed of this labellinglabeling, and to avoid needing to proceed further. Care will be needed where the polygons share an edge.

==See also==

* [[Sutherland–Hodgman algorithm|Sutherland–Hodgman clipping algorithm]]

* [[Vatti clipping algorithm]]

* [[Greiner–Hormann clipping algorithm]]

== References ==

Line 33 ⟶ 45:

* Weiler, Kevin and Atherton, Peter. [http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf "Hidden Surface Removal using Polygon Area Sorting"], Computer Graphics, 11(2):214-222, 1977.

{{DEFAULTSORT:Weiler-Atherton clipping algorithm}}

[[Category:Clipping (computer graphics)]]

[[Category:Polygon clipping algorithms]]

{{compu-graphics-stub}}

[[de:Weiler-Atherton-Algorithmus]]

[[ru:Алгоритм Уайлера — Атертона]]