Weiler–Atherton clipping algorithm: Difference between revisions

Revision as of 17:48, 6 August 2015

Revision as of 01:22, 8 December 2015

Line 1:

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

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

Line 5:

== Prelude ==

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

Before applying to any polygon, the algorithm requires several preconditions to be fulfilled. :

-* Candidate polygons need to be oriented clockwise.

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

-* The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes. Then, merging of polygons can be performed by a variant of the algorithm.

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

- The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes. Then, merging of polygons can be performed by a variant of the algorithm.

== The Algorithm ==

Suppose,Given polygon A isas the clipping polygon/region/area, and, polygon B isas the candidate polygon/subject polygon/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.

First,# twoLabel liststhe are created where one list contains thelisted vertices of the clippingsubject polygon AB andas theeither anotherinside listor contains the verticesoutside of theclipping subjectregion polygonA. B.

All# Find all the polygon intersections are then found and areinsert insertedthem into both lists, linking the lists at the intersections.

# 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.

The list entries are labelled as either inside or outside the other polygon.

Then# Follow each intersection in the list is followed clockwise around the linked lists until the start position is found.

All the polygon intersections are then found and are inserted into both lists, linking the lists at the intersections.

Then a list of inbound intersections is generated.

Then each intersection in the list is followed clockwise around the linked lists until the start position is found.

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

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

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