齊次空間裁剪

齊次空間裁剪是指發(fā)生在vertex shader之后，透視除法( 頂點坐標/w )之前的一段操作。其目標非常直接，因為我們并沒有必要去渲染視錐體之外的物體，如下圖：

只有位于視錐體之內(nèi)的部分，我們才需要去光柵化該三角面，因此裁剪就是將所有不在視錐體之內(nèi)的三角面進行剔除的一個過程，而齊次空間裁剪則是將這個過程在四維的齊次空間進行。

本文目錄：

• 1 簡單裁剪及其缺陷
• 2 齊次空間裁剪
  • 2.1 點與面的關(guān)系判斷
  • 2.2 線與面的關(guān)系判斷和求交點
  • 2.3 凸多邊形與面的剪裁
  • 2.4 凸多邊形與視錐體的剪裁
  • 2.5 齊次坐標下的裁剪
  • 2.6 三角形組合(triangle assembly)
• 3 總結(jié)
• Reference

1 簡單裁剪及其缺陷

首先舉一個非常直觀的裁剪方法，假設現(xiàn)在所有的頂點都已經(jīng)經(jīng)過的model，view，perspective 和 透視除法的操作，那么我們的視錐體的三維空間范圍應該轉(zhuǎn)化為了

的三維標準立方體范圍，此時檢查每一個頂點的坐標，如果有任意一維超出了標準立方體的范圍，則將這個頂點所屬的三角面完全剔除。

這種方法的優(yōu)點是簡單直觀并且效率很高，在早期硬件性能較低的時候有不少的游戲制作確實采用了這種方法。但其缺點也是非常明顯的，如果一個三角形并不是完全在標準立方體之外的話(即一部分在內(nèi)，一部分在外)，那么將這個三角形面完全剔除似乎并不是一種合理的方法，其得到裁剪的效果如下：

仔細觀察琪亞娜的腦殼和底邊的衣物，有許多突兀的缺損一部分的情況，而這正是簡單裁剪的問題，我們希望得到的裁剪結(jié)果在邊緣應該是平滑的，如下圖所示，從單個三角面的角度考慮：

三角形ABC是待被裁剪的三角面，plane是裁剪平面(橫截面角度觀察)，plane左邊為外側(cè)，右邊為內(nèi)側(cè)，我們希望保留內(nèi)側(cè)部分，如果按照簡單裁剪的方法，由于點A位于裁剪平面外側(cè)，則整個三角面都會被拋棄。正確的做法應該是求出CA，AB與裁剪平面plane的交點P1，P2。并將P1,P2,B,C重新組合成2個新的三角面，即P1P2B 和 P1BC，接下來就會一步步去具體介紹如何達到這種效果。

2 齊次空間裁剪

2.1 點與面的關(guān)系判斷

想要進行三角面的裁剪，重要的是能夠正確判斷三角面的裁剪空間的位置關(guān)系，而三角面與裁剪空間的位置關(guān)系是由構(gòu)成三角面的邊與裁剪空間的關(guān)系決定的，更進一步，邊與裁剪空間的關(guān)系則是由構(gòu)成這條邊的兩個頂點與裁剪空間的關(guān)系決定的。

理清上面的邏輯，我們所要做的第一步便是判斷點與裁剪空間的關(guān)系(即點在內(nèi)部還是外部)，不過這里做一個小小的簡化，先不直接考慮點與裁剪空間的關(guān)系，而是考慮點與單一裁剪平面的關(guān)系(這其實是判斷與裁剪空間關(guān)系的基礎，后文會做詳細解釋)。

如上圖所示，依然從橫截面去觀察裁剪平面與點。一個平面可由一個平面上的點

和法線向量決定，此時平面上任意一點 滿足。且法線所指的一半空間為外側(cè)，另一半空間為內(nèi)側(cè)，任給一點不難得出：

1 如果

，則點在裁剪平面外側(cè)

2 如果

，則點在裁剪平面上 (一般不考慮這種特殊情況)

3 如果

，則點在裁剪平面內(nèi)側(cè)

現(xiàn)在我們已經(jīng)知道了如何判斷任給一點與裁剪平面的關(guān)系了，按照本小節(jié)開頭所提到的，接下來應該通過點與裁剪平面的關(guān)系去判斷線與裁剪平面的關(guān)系了。

2.2 線與面的關(guān)系判斷和求交點

其實有了點與裁剪平面關(guān)系判斷的基礎之后，線與平面的關(guān)系判斷已經(jīng)十分直觀了。如上圖所示，裁剪平面定義與 2.1節(jié)中一致，任取一條線段，其兩頂點為

和，設， 。(的幾何含義為向量在法線上帶符號的投影距離)。不難得出：

1 如果

，則邊完全處于裁剪平面外側(cè)

2 如果

，則邊完全處于裁剪平面內(nèi)側(cè)

3 如果

，則邊與裁剪平面相交與點

當邊與裁剪平面相交時，我們需要求出交點

(因為此交點 可能 在之后幫助構(gòu)成新的三角形)，計算過程易得如下：

其中

(這里利用了一下三角形相似性質(zhì))

有了以上的基礎之后，便能更進一步進行任意凸多邊形與單一裁剪平面的剪裁了！

2.3 凸多邊形與面的剪裁

對于任意凸多邊形，只需逐邊遍歷，判斷邊與裁剪平面的關(guān)系，有必要時求出交點，并保留所有在平面內(nèi)側(cè)的頂點即可，思路非常直接，這里直接給出偽代碼實現(xiàn)參考(可以隨便設計一個例子，過一遍代碼流程就能清楚的理解了)。

//clip_plane為裁剪平面的自定義結(jié)構(gòu)體，vert_list存儲了待裁剪凸多邊形的所有頂點 //num_vert為頂點個數(shù)，in_list為需要保留下來的裁剪平面內(nèi)側(cè)頂點的列表 static int clip_with_plane(clip_plane c_plane, vec3* vert_list, int num_vert, vec3* in_list) {int i;int in_vert_num = 0;int previous_index, current_index;for (i = 0; i < num_vert; i++){//從最后一個點開始，遍歷所有邊current_index = i;previous_index = (i - 1 + num_vert) % num_vert;vec3 pre_vertex = vert_list[previous_index]; //邊的起始點vec3 cur_vertex = vert_list[current_index]; //邊的終止點float d1 = cal_project_distance(c_plane, pre_vertex );float d2 = cal_project_distance(c_plane, cur_vertex );//如果該邊與裁剪平面有交點，則計算交點并存入in_listif (d1 * d2 < 0){float t= get_intersect_ratio(pre_vertex,cur_vertex,c_plane); //求出t值vec3 I = vec3_lerp(pre_vertex,cur_vertex,t);in_list[in_vert_num] = I;in_vert_num++;}//如果終止點在內(nèi)側(cè)，直接存入in_listif (d2 < 0 ){in_list[in_vert_num] = cur_vertex ;in_vert_num++;}}return in_vert_num; }

tips: 這里給出的偽代碼只計算了交點的頂點坐標。同理uv坐標，法向向量等屬性值可以插值得到，讀者可以根據(jù)自己實現(xiàn)的軟件渲染器做相應更改即可。

2.4 凸多邊形與視錐體的剪裁

在2.3節(jié)介紹了如何將一個凸多邊形與一個單一平面進行裁剪并保留內(nèi)側(cè)頂點的過程，可這與一開始的目標卻是不同的，我們希望的是將一個凸多邊形(三角面)與一個三維的空間進行裁剪，更準確的說是與視錐體進行裁剪，該如做到后者呢？這其實是非常直觀的，正如在2.1小節(jié)提到的與單一平面進行裁剪是與空間進行裁剪的基礎，做法如下：

如上圖所示的一個視錐體由6個平面組成，分別為：

top plane: 經(jīng)過點P(0,0,0)，法線為

bottom plane: 經(jīng)過點P(0,0,0)，法線為

left plane: 經(jīng)過點P(0,0,0)，法線為

right plane: 經(jīng)過點P(0,0,0)，法線為

near plane: 經(jīng)過點P(0,0,-n)，法線為

far plane: 經(jīng)過點P(0,0,-f)，法線為

其中，

分別為近投影平面，和遠投影平面的距離,為fov的大小。法線推導較為容易，這里省略了。

對于這樣一個由6個平面組成的視錐體進行裁剪，只需依次以每一個面進行裁剪，并且前一次裁剪的輸出為下一次裁剪的輸入即可。參考偽代碼如下：

clip_with_plane(top_plane, vert_list, num_vert, in_list) //對top_plane裁剪得到的in_list，為下一步對bottom裁剪的輸入,依次類推 clip_with_plane(bottom_plane, in_list, num_vert, in_list2) clip_with_plane(left_plane, in_list2, num_vert, in_list3) clip_with_plane(right_plane, in_list3, num_vert, in_list4) clip_with_plane(near_plane, in_list4, num_vert, in_list5) clip_with_plane(far_plane, in_list5, num_vert, in_list6)

(這里的代碼以為了方便理解優(yōu)先，不代表最終實現(xiàn))

最終得到的in_list6 就是在視錐體范圍之內(nèi)的所有頂點了，不過到目前為止雖然看起來已經(jīng)完成了剪裁所有過程(還少一個把頂點重新裝配為三角面的過程)，但是并沒有和齊次空間有多大的關(guān)聯(lián)，別急，下面一節(jié)我們便將所有的步驟轉(zhuǎn)化到齊次空間進行。

2.5 齊次坐標下的裁剪

齊次坐標指由

構(gòu)成的四維坐標，其一般由世界坐標系下的頂點坐標經(jīng)過model，view，perspective變換得到，在此基礎之上再進行一步透視除法，那么原視錐體所對應的空間就會變?yōu)?的標準立方體。

顯然，此時的6個平面分別為

，根據(jù)2.4節(jié)的方法，可以得到被標準立方體裁剪過后的內(nèi)側(cè)的頂點集合，完成裁剪過程。

但實際上，并不需要進行透視除法再進行裁剪，完全可以在齊次空間這樣一個四維空間下找出6個需要裁剪的超平面即可。那么現(xiàn)在的問題就轉(zhuǎn)化為，找到4維齊次空間下，對應

的6個超平面，再直接進行裁剪。

假設一個點

是屬于裁剪空間內(nèi)部的，那么經(jīng)過透視除法之后，應該滿足如下幾個不等式：

那么這3個不等式的6個邊界，其實也就對應了我們想要的4維齊次空間下的6個平面了，即：

好了，現(xiàn)在得到了想要的平面，那么對四維空間下對平面的裁剪其實完全與三維空間中是一致的，只要找出能夠做到如下兩點方法即可：

1 需要能夠判斷點與面的關(guān)系，即內(nèi)側(cè)還是外側(cè)，并可以借此進一步推斷邊與面的關(guān)系

2 倘若邊與平面相交，需要能夠求出邊與平面的交點，即插值系數(shù)t

首先看第一點，這其實已經(jīng)由上文的3個不等式已經(jīng)給出了，如果滿足對應的不等式則就處于對應平面的內(nèi)側(cè)，否則就在外側(cè)。 再看第二點，我們以

平面為例(其它平面可以類推得到)，假設邊與該平面交點為，插值系數(shù)為，作圖如下：

(橫軸可以代表x或y或z，圖中代表x) 此時

，又該交點在平面上，則點坐標的第一維與第四維應該相等，列出如下式子并計算出得：

最終只需要把三維空間內(nèi)對平面裁剪的偽代碼當中關(guān)于 判斷點與平面的關(guān)系，邊是否與平面相交以及求得插值系數(shù)

的部分替換為上文剛剛所講述的方法，即可得到完整的齊次空間裁剪的偽代碼，這里就不再重寫一遍了。

tips： 除了對

裁剪之外，一般還會在之前再增加一個平面的裁剪(只要是一個極小數(shù)即可，并不一定要是1e-5)，該舉措的目的是只保留下的點，防止裁剪之后的透視除法階段出現(xiàn)除0錯誤。

2.6 三角形組合(triangle assembly)

經(jīng)過以上所有步驟裁剪之后，得到的是所有再裁剪空間內(nèi)部的頂點，我們需要的是將這些頂點重新組合成1個或多個三角形面，再輸入光柵化渲染管線。這里實現(xiàn)方法較為直觀，直接給出偽代碼(關(guān)注后半部分即可)：

void draw_triangles(unsigned char* framebuffer, float *zbuffer, PhongShader& shader,int nface) {int i;//vertex shaderfor (i = 0; i < 3; i++){shader.vertex_shader(nface, i);}//homogeneous clippingint num_vertex = 3;num_vertex = clip_with_plane(W_PLANE, vert_list, num_vertex , in_list1);num_vertex = clip_with_plane(X_RIGHT, in_list1, num_vertex , in_list2);num_vertex = clip_with_plane(X_LEFT, in_list2, num_vertex , in_list3);num_vertex = clip_with_plane(Y_TOP, in_list3, num_vertex , in_list4);num_vertex = clip_with_plane(Y_BOTTOM, in_list4, num_vertex , in_list5);num_vertex = clip_with_plane(Z_NEAR, in_list5, num_vertex , in_list6);num_vertex = clip_with_plane(Z_FAR, in_list6, num_vertex , in_list7);//triangle assemblyfor (i = 0; i < num_vertex - 2; i++) {//構(gòu)成三角面的3個頂點索引int index0 = 0;int index1 = i + 1;int index2 = i + 2;vec4 clipcoord_attri[3];clipcoord_attri[0] = in_list7[index0];clipcoord_attri[1] = in_list7[index1];clipcoord_attri[2] = in_list7[index2];rasterize_triangle(clipcoord_attri, framebuffer,zbuffer,shader);} }

(這里的代碼以為了方便理解優(yōu)先，不代表最終實現(xiàn))

同樣的，如果讀者對代碼有些疑問，可以找一個具體的例子從齊次剪裁開始走一遍流程即可。

齊次空間裁剪與簡單裁剪效果對比：

看看腦殼和下面，差別還是挺明顯的！

tips： 有一點需要注意的是，在三角形重新組合的時候，組合的頂點順序往往是很重要的，一般與原三角形頂點順序保持不變(如原來是逆時針存儲頂點，現(xiàn)在還是逆時針重新組合)，這是為了在背面剔除的時候不受影響。關(guān)于這一點，以上給出的偽代碼已經(jīng)考慮到了，包括裁剪過程中存入in_list的順序，和重新組合三角形的方法。

3 總結(jié)

以上就是關(guān)于齊次空間裁剪的全部內(nèi)容了，寫的略微有些冗雜，但是也算是把每一個小步驟都給講出來了。核心就是求得需要保留下來的頂點集合，再重新組合成新三角形即可。

Reference

1 Clipping using homegeneous coordinates by James F. Blinn and Martin E. Newell

2 CLIPPING by Kenneth I. Joy

3 Clipping implementation 這里有比較完整的實現(xiàn)代碼，上面兩個是原理相關(guān)

總結(jié)

以上是生活随笔為你收集整理的计算面平均边_计算机图形学补充2：齐次空间裁剪(Homogeneous Space Clipping)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。