薩瑟蘭-霍奇曼算法
薩瑟蘭-霍奇曼算法（英語：Sutherland–Hodgman algorithm）是裁剪多邊形的算法。它通過輪流延長每個凸多邊形的邊，並且只選擇在可見一側的頂點來完成任務。
描述[編輯]
該算法從目標多邊形中所有頂點的輸入列表開始。接下來，剪裁多邊形的一條邊在兩個方向上無限延伸，同時遍歷目標多邊形的邊。如果輸入列表中的頂點位於擴展的剪裁多邊形線的可見側，則它們會插入到輸出列表中，並且目標多邊形與剪裁多邊形的延長後的邊相交的頂點會添加到輸出列表。
使用一個階段的輸出列表作為下一個階段的輸入列表，對每個剪輯多邊形側重複進行此過程。剪裁多邊形的所有邊都經過處理後，最終生成的頂點列表將定義一個完全可見的新單個多邊形。請注意，如果目標多邊形在剪裁多邊形外部的頂點處凹入，則新多邊形可能具有重疊的邊緣——這對於渲染是可接受的，但不適用於其他應用程式，例如計算陰影。
偽代碼[編輯]
給定一個剪裁多邊形的一組邊，和一個目標多邊形的頂點列表，下面的過程將目標多邊形根據剪裁多邊形進行剪裁。
List outputList = subjectPolygon;
for (Edge clipEdge in clipPolygon) do
List inputList = outputList;
outputList.clear();
for(int i = 0 ; i < inputList.count ; i += 1) do
Point current_point = inputList[i];
Point prev_point = inputList[(i + inputList.count - 1) % inputList.count];
Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)
if (current_point inside clipEdge) then
if (prev_point not inside clipEdge) then
outputList.add(Intersecting_point);
end if
outputList.add(current_point);
else if (prev_point inside clipEdge) then
outputList.add(Intersecting_point);
end if
done
done當算法終止時，將在outputList中找到裁剪後多邊形的頂點。請注意，如果它位於該邊緣作為多邊形的剩餘部分的相同側上的點被定義為邊緣的內側。如果剪裁多邊形的頂點始終沿逆時針方向列出，那麼這等效於測試該點是否位於直線的左側（left表示內部，right表示外部），這可以通過簡單地使用叉積 實現。
ComputeIntersection是函數，為清楚起見在此省略了該函數，它返回線段和無限邊的交點。請注意，僅在已知存在這種相交的情況下才調用它，因此可以簡單地將兩條線都視為無限長。
參看[編輯]
參考文獻[編輯]
- 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, pp. 32–42, 1974