Sutherland Hodgman

Der Algorithmus von Sutherland-Hodgman ist ein Algorithmus der Computergrafik zum Clipping von Polygonen.

Grundversion

In der Grundversion des Algorithmus erfolgt das Clipping für konvexe Polygone. Für jede Fensterkante wird die Begrenzungsstrecke zu einer Gerade erweitert, an der sämtliche (relevanten) Polygonkanten gekürzt werden.

Erweiterte Version

Clipping eines Polygons bzgl. eines beliebigen konvexen Polygons. Beschreibung des Polygons durch seine Ecken $v_1, \ldots, v_n$ und Kanten von v_i nach $v_{i+1}, (i=1,\ldots,n-1)$ bzw. von v_n nach v₁. 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 4 Fälle möglich.

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

Literatur

• Mel Slater, Anthony Steed, Yiorgos Chrysanthou. Computer Graphics and Virtual Environments: From Realism to Real-Time. Addison Wesley ISBN 0-201-62420-6
• I. E. Sutherland and G. W. Hodgman. Reentrant Polygon Clipping. CACM, vol. 17, pp. 32-42, 1974

Weblinks

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