Weiler–Atherton urklippsalgoritm

Weiler - Atherton är en polygonklippningsalgoritm . Det används inom områden som datorgrafik och spelutveckling där klippning av polygoner behövs. Det tillåter klippning av ett ämne eller kandidatpolygon med en godtyckligt formad klipppolygon/område/region .

Det är generellt endast tillämpligt i 2D . Den kan dock användas i 3D genom synlig ytbestämning och med förbättrad effektivitet genom Z-ordning .

Förutsättningar

Underindelning med Weiler-Atherton-algoritmen

Innan den appliceras på en polygon kräver algoritmen flera förutsättningar för att vara uppfyllda:

• Kandidatpolygoner måste vara orienterade medurs.
• Kandidatpolygoner bör inte vara självkorsande (dvs återinträdande).
• Algoritmen kan stödja hål (som moturs polygoner helt inuti sin moderpolygon), men kräver ytterligare algoritmer för att avgöra vilka polygoner som är hål, varefter sammanslagning av polygonerna kan utföras med en variant av algoritmen.

Algoritm

Givet polygon A som urklippsregion och polygon B som ämnespolygon som ska klippas, består algoritmen av följande steg:

1. Lista hörnen för urklippsregionens polygon A och de i ämnespolygonen B.
2. Märk de listade hörnen av ämnespolygon B som antingen inuti eller utanför klippområde A.
3. Hitta alla polygonkorsningar och infoga dem i båda listorna, länka samman listorna vid skärningspunkterna.
4. Skapa en lista med "inkommande" skärningspunkter – skärningspunkterna där vektorn från skärningspunkten till efterföljande hörn av ämnespolygon B börjar inuti klippområdet.
5. Följ varje korsning medurs runt de länkade listorna tills startpositionen hittas.

Om det inte finns några korsningar måste ett av tre villkor vara sant:

1. A är inuti B – returnera A för klippning, B för sammanfogning.
2. B är inuti A – returnera B för klippning, A för sammanfogning.
3. A och B överlappar inte – returnera Ingen för klippning eller A & B för sammanslagning.

Slutsats

En eller flera konkava polygoner kan producera mer än en skärande polygon. Konvexa polygoner kommer bara att ha en skärande polygon.

Samma algoritm kan användas för att slå samman två polygoner genom att börja vid de utgående korsningarna snarare än de inkommande. Detta kan dock ge hål moturs.

Vissa polygonkombinationer kan vara svåra att lösa, speciellt när hål är tillåtna.

Punkter mycket nära kanten på den andra polygonen kan betraktas som både in och ut tills deras status kan bekräftas efter att alla skärningar har hittats och verifierats; detta ökar dock komplexiteten.

Olika strategier kan användas för att förbättra hastigheten på denna märkning och för att undvika att behöva gå vidare. Försiktighet kommer att behövas där polygonerna delar en kant.

Se även

• Sutherland–Hodgman urklippsalgoritm
• Vatti klippningsalgoritm
• Greiner–Hormann urklippsalgoritm

• Weiler, Kevin och Atherton, Peter. "Hidden Surface Removal using Polygon Area Sorting" , Computer Graphics, 11(2):214-222, 1977.