计算面平均边_计算机图形学补充2:齐次空间裁剪(Homogeneous Space Clipping)
齊次空間裁剪
齊次空間裁剪是指發(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 跟宝马中国“分家” 华晨汽车损失惨重:净
- 下一篇: 华为余承东:奇瑞、北汽、江淮新车将至,统