計算機圖形學的裁剪演算法，實現任意多邊形與直線、圓的裁剪？

01-05

最近在看計算機圖形學，發現裁剪演算法比較有意思，因為裁剪習題窗口都是矩形，自己在想如何實現任意多邊形，當與直線進行相交時，該如何轉變演算法，想繼續延伸到圓、多邊形。

GPU 只把完全不可見的三角形殺掉，不會對部分可見的三角形做裁剪。即只會 cull，不會 clip。

cull 發生在光柵化之前，在齊次坐標系下，通過三角形三個頂點的 x y z 和 w 的關係無腦判斷 to be or not to be。在 NV 的硬體里由 VPC 完成。
由於不存在 clip，所以沒啥好說的。

GPU 是個弱智的蠻牛，clip 這麼複雜的事情是不會做的。（攤手啊）

對 NV 的流水線感興趣的可以閱讀官方文章 Life of a triangle

補充下：

W=0的Clip還是要做的。 @空明流轉

另外對於Clip Plane（包括Clip Distance），也應該是要做Clip的。不用做的Clip主要是Viewport Clip。 @空明流轉

穿透view frustum邊界的三角形是會被clip的。 @Yubo Zhang

GPU會建立一個遠大於viewport的虛擬窗口，只有和那個窗口不覆蓋的三角形被徹底滅掉。其他都會留著，讓rasterizer決定哪些pixel有效。near plane可能還是要特別對待的，因為w為負，會被映射到奇怪的地方。

另外，在 @李宏偉的答案中提到的OpenGL ES不支持自定義clip plane的原因是錯誤的。OpenGL ES支持自定義的clip plane。API沒有的原因是，但凡純可編程流水線，就不需要clip plane的API，而在shader里clip就是了。

@Yong He說我的回答不正確，為了捍衛正理，我只好多添加一點料。

首先講一點點GPU的模塊設計，簡化來講，一個GPU有多個Core，一個Core可以帶多個SM和一個raster。每一個Core負責屏幕上的一個tile，如下圖所示。假設一個GPU有3個core，那麼屏幕就被分成三塊，每一個塊都有一個core來負責繪製。一個三角形經過projection之後，會被計算它被哪些tile相交，就把這個三角形扔到負責這個tile的core中去。

+---+---+---+---+---+---+ | 0 | 1 | 2 | 0 | 1 | 2 | +---+---+---+---+---+---+ | 1 | 2 | 0 | 1 | 2 | 0 | +---+---+---+---+---+---+ | 2 | 0 | 1 | 2 | 0 | 1 | +---+---+---+---+---+---+

core中的raster收到一個三角形這個時候就啟動啦。raster分幾個部分，第一部分是初始化，它會計算三角形的邊的公式，用於後續的rasterization，然後它還會求一個初始的quad（GPU Core再把一個tile再分成好幾個Quad)。這個初始的Quad的意思是這個三角形中最上最左的且與這個三角形相交的Quad。raster其第二部分是rasterization，它根據一個初始Quad和三角形邊的公式，迅速的找出剩下的與三角形相交的Quad。

你看如果一個三角形不在tile裡面，raster的初始化部分就失敗了。根本不用往下走，這個計算是非常簡單的，而且與clipping space裡面相比，完全沒有內存寫的問題。這才是現代GPU的做法。

不要被A trip through the Graphics Pipeline 2011誤導了。

===================================================

俺來回答下，各位大牛就在我身上踩過去吧。

首先，題主的這個想法挺好的，實現任意直線和多邊形的裁剪。不過這玩藝有啥用啊？我一下子沒有想到耶。延伸開來說三個點

1. GPU現在是怎麼做culling的，就是Frustum和Triangle的Culling。教科書上說，甚至大部分的面試題都說，在Vertex Shader下面有一個流水線模塊，專門作Culling，對三角形進行裁剪。尼瑪，要是真是這樣，硬體工程師要瘋了。這玩藝有多複雜你知道嗎？這個演算法就算弄出來，硬體的面積得有多大啊，然後這個模塊會不會成為性能瓶頸啊，那麼多的讀寫算。所以答案是，GPU根本不這麼做。GPU是把沒有裁減過的三角形直接作rasterize，反正超出viewport的那麼部分就不畫了嘛。你看這個多簡單。

2. GPU還是有culling模塊的，不過那個模塊只對用戶自定義的clip plane作裁減。估計這個模塊Mobile GPU上都沒有，不然為啥OpenGL ES不支持自定義的clip plane啊。

3. 基於1，題主你就不要費腦筋在Vertex這個層面想了，放到屏幕空間，不就是一個stencil mask的事兒，反正你的直線，圓和多邊形最後都要rasterize到屏幕上，那麼在屏幕空間裡面做一個AND操作不就K.O.了。不要搞這麼高大上的計算幾何嘛。

謝邀。我覺得@李宏偉的說法是不準確的。GPU上確實有三角形的裁剪單元，而且裁剪是在齊次坐標系中進行的。對於x,y方向，GPU並不是不執行裁剪，而是放寬了裁剪範圍，這樣很多超出一點的三角形可以不用裁剪，提升性能。但超出很多的三角形仍然會被裁剪。另外對於所有包含w&<0的頂點也必須裁剪，否則無法光柵化。@李宏偉在他的答案中提到tile based渲染器，然而這個問題和tiled是沒有什麼關係的。因為你仍然需要判斷一個投影后的三角形和tile有沒有重疊關係。計算邊的方程都是在定點數空間完成的，這意味著所有的坐標必須先被裁減到一個有限的範圍內才能轉化成定點數。其次就算你用浮點數做相交檢測，仍然需要通過裁剪來去除在z範圍之外的三角形，否則連有效的邊的方程都無法得到。

凸多邊形和平面的裁剪問題是有意義的。凹多邊形一般都表達為凸多邊形的組合。某些時候在建BVH或者kd樹的時候對大多邊形進行裁剪可以提高構造出來的樹的質量。但是多邊形和圓的裁剪問題可能意義不大，因為圓一般也是表達為多邊形的，這類問題在計算實體幾何中會出現，例如通過布爾運算進行建模。

凸多邊形和平面的裁剪是非常簡單的。按順時針或逆時針順序遍歷所有的邊，並且維護兩個頂點列表，list1表示在平面正側的頂點，另一個列表list2維護負側頂點。如果這條邊跨越了平面，那麼計算交點，然後把位於正側的頂點放進list1, 負側頂點放進list2, 交點同時放進list1, list2。當你掃完所有邊之後兩個list裡面的頂點就形成了分割後的多邊形。

題主想問的不是GPU裡面用不用吧，就是裁剪演算法～