Sutherland-Hodgmans algoritme

Sutherland–Hodgmans algoritme brukes for å klippe polygoner. Den virker ved å utvide hver av kantene i det konvekse klippepolygonet etter tur, og så velge kun de knutepunktene fra polygonet som befinner seg i det synlige området.

Beskrivelse

Algoritmen starter med en liste over alle knutepunktene i polygonet. Deretter velges en kant i klippepolygonet som utvides uendelig i begge retninger, før polygonet løpes gjennom. Knutepunktene fra polygonet settes direkte inn i en ny liste hvis de befinner seg på den synlige siden av den uendelig lange kanten. Hvis et knutepunkt befinner seg på utsiden, settes det inn et nytt punkt i krysningspunktet mellom den uendelige linjen og dette punktets linje. Dette nye punktet legges så inn i listen.

Denne prosessen blir utført for hver kant i klippepolygonet, og hver gang brukes den listen som ble laget ved forrige iterasjon. Når alle sidene i klippepolygonet har blitt prosessert, får man den endelige listen med knutepunkter, som nå definerer et polygon helt innenfor det synlige området. Merk at hvis polygonet er konkavt i området utenfor klippepolygonet, kan det hende det nye polygonet får en eller flere overlappende kanter. Dette er akseptabelt til rendering, men ikke i tilfeller hvor polygonet skal brukes til å generere skygger.

Alle stegene som utføres ved klipping av det konkave polygonet W med et femsidet konvekst klippepolygon

Weiler–Athertons algoritme unngår dette ved å returnere et sett med oppdelte polygoner, men er mer komplisert, og krever mer prosesseringskraft. Derfor foretrekkes Sutherland–Hodgman i mange renderingsapplikasjoner. Sutherland–Hodgman kan også utvides til 3D ved å bruke plan istedenfor kanter.

Pseudokode

Gitt en liste med kanter i et klippepolygon, og en liste med kanter i et polygon vi ønsker å klippe, kjøres følgende prosedyre mot klippepolygonet.

  List outputList = subjectPolygon;
  for (Edge clipEdge in clipPolygon) do
     List inputList = outputList;
     outputList.clear();
     Point S = inputList.last;
     for (Point E in inputList) do
        if (E inside clipEdge) then
           if (S not inside clipEdge) then
              outputList.add(ComputeIntersection(S,E,clipEdge));
           end if
           outputList.add(E);
        else if (S inside clipEdge) then
           outputList.add(ComputeIntersection(S,E,clipEdge));
        end if
        S = E;
     done
  done

Knutepunktene i det klippede polygonet finnes i outputList. Merk at et punkt defineres som på innsiden av en kant hvis det ligger på samme side av kanten som resten av polygonet. Hvis knutepunktene i klippepolygonet er angitt i retning med klokken, vil dette bli det samme som å sjekke om punktet ligger til venstre for linjen (venstre betyr innenfor, høyre betyr utenfor), og kan regnes ut enkelt ved å bruke kryssproduktet.

ComputeIntersection er en enkel funksjon som returnerer krysningspunktet mellom en linje og en uendelig lang kant. Den er ikke tatt med her for ryddighetens skyld. Merk at funksjonen kun kjøres hvis et krysningspunkt finnes, og vi kan derfor se på begge linjene som uendelig lange.

Litteratur

• Mel Slater, Anthony Steed, Yiorgos Chrysanthou: Computer Graphics and Virtual Environments: From Realism to Real-Time. Addison Wesley. ISBN 0-201-62420-6
• Ivan Sutherland, Gary W. Hodgman: Reentrant Polygon Clipping. Communications of the ACM, vol. 17, ss. 32–42, 1974

Eksterne lenker

• Polygonklipping og fylling Beskriver algoritmen ved bruk av bilder som er enkle å forstå.