Algorithmus von Sutherland-Hodgman

Der Algorithmus von Sutherland-Hodgman ist ein nach Ivan Sutherland und Gary W. Hodgman benannter Algorithmus der Computergrafik zum Clipping von Polygonen.

Grundversion[Bearbeiten | Quelltext bearbeiten]

Mit dem Sutherland-Hodgman-Algorithmus kann man mit jedem konvexen Polygon jedes andere Polygon (konvex oder konkav) clippen. Für jede Fensterkante wird die Begrenzungsstrecke zu einer Gerade erweitert, an der sämtliche (relevanten) Polygonkanten gekürzt werden.

Pseudo-Code[Bearbeiten | Quelltext bearbeiten]

Der folgende Pseudo-Code clippt ein Polygon nach 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

• 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[Bearbeiten | Quelltext bearbeiten]

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