Weiler-Atherton algorithm
The Weiler-Atherton algorithm is a method from computer graphics for calculating the masking of polygons .
functionality
The first step of the Weiler-Atherton algorithm is to sort all polygons approximately according to their z -coordinates. Polygon A , which is closest according to this rough sorting, is now used to clip all polygons against A and to divide them along its contour. This creates two lists: an "inner list" that contains all the polygon parts that are located within the clipping polygon A after projection ( B in A in the example image on the right ), and an "outer list" with all parts outside ( B out A in the example image ).
All polygons in the inner list that are behind A are deleted because they are not visible. If, on the other hand, one of the polygons of the inner list is closer to the viewer than A , this is because the initial sorting failed here. For each of these polygons, the polygon parts of the inner list are tested to see whether they are closer, and possibly clipped. This is done recursively . At the end of the process, the inside list is updated accordingly. Then the polygons of the outer list are processed.
The initial and not the split polygons are always used for clipping, as this requires less effort due to the usually simpler shape of the original polygons. Therefore, the original polygon must also be specified for each split polygon.
In order to be able to process polygons that overlap one another, the algorithm uses a stack memory . This contains all clipping polygons whose processing was interrupted due to a recursive call. If a polygon is found that is before the current clipping polygon, it is first looked for in the stack. If it has already been entered there, no recursion is necessary because all polygon parts within and behind this polygon have already been removed.
literature
- James D. Foley et al: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6
- David F. Rogers: Procedural Elements for Computer Graphics. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5
- Kevin Weiler, Peter Atherton: Hidden Surface Removal Using Polygon Area Sorting. ACM SIGGRAPH Computer Graphics 11, 2 (Summer 1977): 214-222, ISSN 0097-8930