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.

Inhaltsverzeichnis

Grundversion

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.

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

Pseudo-Code

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

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

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

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sutherland Hodgman — Der Algorithmus von Sutherland Hodgman ist ein Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 2 Erweiterte Version 3 Literatur 4 Weblinks …   Deutsch Wikipedia

  • Sutherland-Hodgeman — Der Algorithmus von Sutherland Hodgman ist ein Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 2 Erweiterte Version 3 Literatur 4 Weblinks …   Deutsch Wikipedia

  • Clipping (Computergrafik) — Als Clipping oder Abschneiden (englisch to clip = „abschneiden“, „kappen“) bezeichnet man in der Computergrafik das Abschneiden von Grundobjekten am Rand eines gewünschten Bildschirmausschnittes oder Fensters. Ein Fenster kann dabei ein… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”