Weiler–Atherton clipping algorithm: Difference between revisions

Revision as of 03:01, 28 September 2018

Latest revision as of 05:51, 4 July 2023

(4 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Polygon clipping algorithm}}

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

== PreludePreconditions ==

[[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:

Line 9 ⟶ 10:

* Candidate polygons need to be oriented clockwise.

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

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

== The Algorithm ==

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.