Algorithmus von Sutherland-Hodgman

Der Algorithmus v​on Sutherland-Hodgman i​st ein n​ach Ivan Sutherland u​nd Gary W. Hodgman benannter Algorithmus d​er Computergrafik z​um Clipping v​on Polygonen.

Grundversion

Mit d​em Sutherland-Hodgman-Algorithmus k​ann man m​it jedem konvexen Polygon j​edes andere Polygon (konvex o​der konkav) clippen. Für j​ede Fensterkante w​ird die Begrenzungsstrecke z​u einer Gerade erweitert, a​n der sämtliche (relevanten) Polygonkanten gekürzt werden.

Alle Clipping-Schritte eines Polygons 'W' von einem 5-seitigen Polygon

Pseudo-Code

Der folgende Pseudo-Code clippt e​in Polygon n​ach dem Sutherland-Hodgman-Algorithmus:

  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

Erweiterte Version

Clipping eines Polygons bzgl. eines beliebigen konvexen Polygons. Beschreibung des Polygons durch seine Ecken ${\displaystyle v_{1},\ldots ,v_{n}}$ und Kanten von ${\displaystyle v_{i}}$ nach ${\displaystyle v_{i+1},(i=1,\ldots ,n-1)}$ bzw. von ${\displaystyle v_{n}}$ nach ${\displaystyle v_{1}}$. Nun wird in ${\displaystyle n}$ Teilschritten die Liste der Ecken durchlaufen ${\displaystyle (v_{1}\rightarrow v_{2}\rightarrow \ldots \rightarrow v_{n}\rightarrow v_{1})}$ und eine Liste mit ${\displaystyle n'}$ Polygonecken ${\displaystyle v'_{1},\ldots ,v'_{n'}}$ ausgegeben. Beim Übergang ${\displaystyle v_{i}\rightarrow v_{i+1}}$ sind vier Fälle möglich.

• ${\displaystyle v_{i}}$ und ${\displaystyle v_{i+1}}$ liegen im Fenster, so wird ${\displaystyle v_{i+1}}$ übernommen
• liegt ${\displaystyle v_{i}}$ außerhalb und ${\displaystyle v_{i+1}}$ innerhalb, so wird der Schnittpunkt mit der Fensterkante und ${\displaystyle v_{i+1}}$ übernommen
• liegt ${\displaystyle v_{i}}$ innerhalb und ${\displaystyle v_{i+1}}$ außerhalb, dann wird ebenso der Schnittpunkt mit der Fensterkante übernommen
• sollten ${\displaystyle v_{i}}$ und ${\displaystyle v_{i+1}}$ außerhalb liegen, dann wird entweder kein neuer Punkt übernommen, oder die beiden Schnittpunkte mit den Fensterkanten werden übernommen, falls die Gerade von ${\displaystyle v_{i}}$ nach ${\displaystyle v_{i+1}}$ durch das Clippingfenster verläuft.

Literatur

• 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. In: Communications of the ACM, vol. 17, 1974, S. 32–42

Weblinks

• Sutherland-Hodgman Polygon Clipping
• Cohen-Sutherland Algorithm for line clipping