Sutherland-Hodgman-algoritm

Sutherland –Hodgman-algoritmen är en algoritm som används för att klippa polygoner . Det fungerar genom att förlänga varje rad i den konvexa klipppolygonen i tur och ordning och endast välja hörn från ämnespolygonen som är på den synliga sidan.

Beskrivning

Algoritmen börjar med en inmatningslista över alla hörn i ämnespolygonen. Därefter förlängs en sida av klipppolygonen oändligt i båda riktningarna och banan för den aktuella polygonen korsas. Vertices från inmatningslistan infogas i en utdatalista om de ligger på den synliga sidan av den utökade klipppolygonlinjen, och nya hörn läggs till i utdatalistan där ämnespolygonbanan korsar den utökade klipppolygonlinjen.

Denna process upprepas iterativt för varje klipppolygonsida, med utdatalistan från ett steg som inmatningslista för nästa. När alla sidor av klipppolygonen har bearbetats, definierar den slutgiltiga genererade listan med hörn en ny enkel polygon som är helt synlig. Observera att om ämnespolygonen var konkav vid hörn utanför klipppolygonen, kan den nya polygonen ha sammanfallande (dvs överlappande) kanter – detta är acceptabelt för rendering, men inte för andra applikationer som beräkningsskuggor.

Alla steg för att klippa konkav polygon 'W' med en 5-sidig konvex polygon

Weiler -Atherton- algoritmen övervinner detta genom att returnera en uppsättning delade polygoner, men är mer komplex och beräkningsmässigt dyrare, så Sutherland-Hodgman används för många renderingstillämpningar. Sutherland–Hodgman kan också utökas till 3D-rymden genom att klippa polygonbanorna baserat på gränserna för plan som definieras av visningsutrymmet.

Pseudokod

Med en lista över kanter i en klipppolygon och en lista över hörn i en ämnespolygon, klipper följande procedur ämnespolygonen mot klipppolygonen.

            

    
 List outputList = subjectPolygon;  för  (Edge clipEdge i clipPolygon)  gör  List inputList = outputList; outputList.clear();   för  (int i = 0; i < inputList.count; i += 1)  gör  Point current_point = inputList[i]; Point prev_point = inputList[(i − 1) % inputList.count];  Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)   if  (current_point inside clipEdge)  then  if  (prev_point not inside clipEdge)  then  outputList.add(Skärningspunkt);  end if  outputList.add(current_point);  annars if  (prev_point inuti clipEdge)  sedan  outputList.add(Skärningspunkt);  slut om  gjort  gjort 

Topparna för den klippta polygonen återfinns i outputList när algoritmen avslutas. Observera att en punkt definieras som inuti en kant om den ligger på samma sida av kanten som resten av polygonen. Om hörn av klipppolygonen är konsekvent listade i en moturs riktning, så motsvarar detta att testa om punkten ligger till vänster om linjen (vänster betyder inuti medan höger betyder utanför ), och kan implementeras helt enkelt genom att använder en korsprodukt .

ComputeIntersection är en funktion, utelämnad här för tydlighetens skull, som returnerar skärningen av ett linjesegment och en oändlig kant. Observera att skärningspunkten endast läggs till i utdatalistan när man vet att skärningspunkten finns, därför kan båda linjerna alltid behandlas som oändligt långa.

Genomföranden

En Python-implementering av Sutherland-Hodgman kan hittas här .

Se även

Andra polygonklippningsalgoritmer:

• Weiler–Atherton urklippsalgoritm
• Vatti klippningsalgoritm

Om ämnet klippning:

• Klippning (datorgrafik)
• Klippning (i rasterisering)
• Algoritmer för linjeklipp

•   Mel Slater, Anthony Steed, Yiorgos Chrysanthou: Datorgrafik och virtuella miljöer: från realism till realtid. Addison Wesley. ISBN 0-201-62420-6 .
• Ivan Sutherland , Gary W. Hodgman: Reentrant Polygon Clipping. Communications of the ACM , vol. 17, s. 32–42, 1974

externa länkar

• Polygonklippning och fyllning Beskriver algoritmen med bilder som är lätta att förstå.
• Rosetta Code exempel