一、概述
由于投影變換失去了深度資訊，往往導緻圖形的二義性。要消除二義性，就必須在繪制時消除被遮擋的不可見的線或面，習慣上稱作消除隐藏線和隐藏面（或可見線判定、可見面判定），或簡稱為消隐。經過消隐得到的投影圖稱為物體的真實感圖形。
下面這個圖就很好展現了這種二義性。
消隐後的效果圖：
消隐算法的分類
所有隐藏面消隐算法必須确定:
在沿透視投影的投影中心或沿平行投影的投影方向看過去哪些邊或面是可見的
兩種基本算法
1、以構成圖像的每一個像素為處理單元，對場景中的所有表面，确定相對于觀察點是可見的表面，用該表面的顔色填充該像素.
适于面消隐。
算法步驟：
a.在和投影點到像素連線相交的表面中，找到離觀察點最近的表面；
b.用該表面上交點處的顔色填充該像素；
2、以三維場景中的物體對象為處理單元，在所有對象之間進行比較，除去完全不可見的物體和物體上不可見的部分.适于面消隐也适于線消隐。
a.判定場景中的所有可見表面；
b.用可見表面的顔色填充相應的像素以構成圖形；
提醒注意
1.假定構成物體的面不能互相貫穿，也不能有循環遮擋的情況。
2.假定投影平面是oxy平面，投影方向為z軸的負方向。
如果構成物體的面不滿足該假定，可以把它們剖分成互不貫穿和不循環遮擋的情況。
例如，用圖b中的虛線便可把原來循環遮擋的三個平面，分割成不存在循環遮擋的四個面。
二、可見面判斷的有效技術
1、邊界盒
指能夠包含該物體的一個幾何形狀(如矩形/圓/長方體等)，該形狀有較簡單的邊界。
邊界盒技術用于判斷兩條直線是否相交。
進一步簡化判斷
2、後向面消除(Back-face Removal)
思路：把顯然不可見的面去掉，減少消隐過程中的直線求交數目
如何判斷：根據定義尋找外（或内）法向，若外法向背離觀察者，或内法向指向觀察者，則該面為後向面。
注意：如果多邊形是凸的，則可隻取一個三角形計算有向面積sp。如果多邊形不是凸的，隻取一個三角形計算有向面積sp可能會出現錯誤，即F所在的面為前向面也可能出現sp≥0的情況,是以，需按上式計算多邊形F的有向面積。如果sp ≥0，則F所在的面為後向面。
3、非垂直投影轉化成垂直投影
物體之間的遮擋關系與投影中心和投影方向有着密切的關系,是以，對物體的可見性判定也和投影方式有密切的關系。
垂直投影的優點:進行投影時可以忽略z值,即：實物的(x,y)可直接做為投影後的二維平面上的坐标(x,y)
上述讨論說明，垂直投影比非垂直投影容易實作，并且計算量小。是以在進行消隐工作之前，首先應将非垂直投影轉換成垂直投影，進而降低算法的複雜性，提高運算速度。
如何把透視投影變為垂直投影,其本質是把棱台變成長方體。
三、基于視窗的子分算法（Warnack算法）
是一種分而治之(Divide-Conquer)的算法。
1、關系判斷
2、可見性判斷
3、分隔結束條件
4、提高效率的有效的處理技術
5、算法描述
用多邊形的邊界對區域作劃分，其目的是盡量減少對區域劃分的次數－－利用裁剪算法
四、八叉樹算法
為了生成真實感圖形，關鍵問題之一就是對圖像空間的每一個像素進行處理。從場景中所有的在該像素上有投影的表面中确定相對于觀察點是可見表面。為了提高算法效率，自然是希望從可能在像素上有投影的面片中尋找可見表面。八叉樹算法是快速尋找可見面的一種有效方法，是一種搜尋算法。
基本思想：将能夠包含整個場景的立方體，即八叉樹的根結點，按照x，y，z三個方向中的剖面分割成八個子立方體，稱為根結點的八個子結點。對每一個子立方體，如果它包含的表面片少于一個給定的值，則該子立方體為八叉樹的終端結點，否則為非終端結點并将其進一步分割成八個子立方體；重複上述過程，直到每個小立方體所包含的表面片少于一個給定的值，分割即告終止。
那麼對于上述圖所示，視圖平面法向量（1,1,1）那麼此時它的一個排列是0,1,2,4,3,5,6,7，即最遠的八分體是0，與八分體0共享一個面的三個相鄰八分體是1,2和4,與最近八分體7的3個相鄰八分體是3,5和6。
五、Z緩沖器算法
1、算法描述
z緩沖器算法是最簡單的隐藏面消除算法之一。
基本思想：對螢幕上每一個像素點，過像素中心做一條投影線，找到此投影線與所有多邊形交點中離觀察者最近的點，此點的屬性(顔色或灰階)值即為這一螢幕像素點的屬性值。
需要兩個緩沖器數組，即：z緩沖器數組和幀緩沖器數組，分别設為 Zdepth[ ][ ] 與 Frame[ ][ ]
z緩沖器是一組存貯單元，其單元個數和螢幕上像素的個數相同，也和幀緩沖器的單元個數相同，它們之間一一對應。
幀緩沖器每個單元存放對應像素的顔色值；z緩沖器每個單元存放對應像素的深度值;
2、算法實作
算法的複雜性正比于m*n*N，在螢幕大小即m*n一定的情況下,算法的計算量隻和多邊形個數N成正比
3、優缺點
z-Buffer算法沒有利用圖形的相關性和連續性，這是z-Buffer算法的嚴重缺陷，更為嚴重的是，該算法是像素級上的消隐算法。
六、掃描線z緩沖器算法
将z緩沖器的單元數置為和一條掃描線上的像素數目相同。
從最上面的一條掃描線開始工作，向下對每一條掃描線作如下處理：
掃描線算法也屬于圖像空間消隐算法。該算法可以看作是多邊形區域填充裡介紹過的邊相關掃描線填充算法的延伸。不同的是在消隐算法中處理的是多個面片，而多邊形填充中是對單個多邊形面進行填充。
2、資料結構
對每個多邊形，檢查它在oxy平面上的投影和目前掃描線是否相交？
若不相交，則不考慮該多邊形。
如果相交，則掃描線和多邊形邊界的交點是成對地出現
對每對交點中間的像素計算多邊形所在平面對應點的深度（即z值），并和z緩沖器中相應單元存放的深度值作比較。
若前者大于後者，則z緩沖器的相應單元内容要被求得的平面深度代替，幀緩沖器相應單元的内容也要換成該平面的屬性。
對所有的多邊形都作上述處理後，幀緩沖器中這一行的值便反應了消隐後的圖形。
對幀緩沖器每一行的單元都填上相應内容後就得到了整個消隐後的圖。
每處理一條掃描線，都要檢查各多邊形是否和該線相交，還要計算多邊形所在平面上很多點的z值，需要花費很大的計算
為了提高算法效率，采用跟多邊形掃描轉換中的掃描線算法類似的資料結構和算法.
多邊形Y表
實際上是一個指針數組 ,每個表的深度和顯示螢幕行數相同.将所有多邊形存在多邊形Y表中,根據多邊形頂點中Y坐标最大值,插入多邊形Y表中的相應位置,多邊形Y表中儲存多邊形的序号和其頂點的最大y坐标.
邊Y表
要注意：Δx是下一條掃描線與邊交點的x減去目前的掃描線與邊交點的x。
多邊形活化表
邊對活化表
其實這裡最難了解的就是Δyl和Δxr了，這裡的意思就是目前掃描線所處的y值和與該掃描線相交邊的最小y值的內插補點。
就比如說掃描線y=6,與第一個三角形有兩個交點，左交點（4,6），右交點（7,6）那麼Δyl=6-3 Δyr=6-3
3、重溫算法目标
對每一條掃描線，檢查對每個多邊形的投影是否相交，如相交則交點成對出現，對每對交點中間的每個像素計算多邊形所在平面對應點的深度（即z值），并和z緩沖器中相應單元存放的深度值作比較，若前者大于後者，則z緩沖器的相應單元内容要被求得的平面深度代替，幀緩沖器相應單元的内容也要換成該平面的屬性。
對所有的多邊形都作上述處理後，幀緩沖器中這一行的值便反應了消隐後的圖形，對幀緩沖器每一行的單元都填上相應内容後也就得到了整個消隐後的圖。
4、算法步驟
算法描述如下
七、優先級排序表算法
1、算法思想
優先級排序表算法按多邊形離觀察者的遠近來建立一個多邊形排序表，距觀察者遠的優先級低，放在表頭；近的優先級高，放在表尾
從優先級低的多邊形開始，依次把多邊形的顔色填入幀緩沖存儲器中
表中距觀察者近的元素覆寫幀緩沖存儲器中原有的内容
當優先級最高的多邊形的圖形送入幀緩沖器後，整幅圖形就形成了
類似于油畫家繪畫過程，是以又稱為油畫家算法。
2、算法的優缺點
算法的優點:
簡單,容易實作,并且可以作為實作更複雜算法的基礎;
缺點:
隻能處理不相交的面,而且深度優先級表中面的順序可能出錯.
該算法不能處理某些特殊情況。
解決辦法：把P沿Q平面一分為二，從多邊形序列中把原多邊形P去掉，把分割P生成的兩個多邊形加傳入連結表中。具體實作時，當離視點最遠的多邊形P和其他多邊形交換時，要對P做一标志，當有标志的多邊形再換成離視點最遠的多邊形時，則說明出現了上述的現象，可用分割方法進行處理
。
用來解決動态顯示問題時,可大大提高效率
八、光線投射算法
1、算法原理
要處理的場景中有無限多條光線，從采樣的角度講我們僅對穿過像素的光線感興趣，是以，可考慮從像素出發，逆向追蹤射入場景的光線路徑
由視點出發穿過觀察平面上一像素向場景發射一條射線
求出射線與場景中各物體表面的交點
離視點最近的交點的顔色即為像素要填的顔色。
光線投射算法對于包含曲面，特别是包含球面的場景有很高的效率。
作者：王陸
出處：https://www.cnblogs.com/wkfvawl/
-------------------------------------------
個性簽名：罔談彼短，靡持己長。做一個謙遜愛學的人！
本站使用「署名 4.0 國際」創作共享協定，轉載請在文章明顯位置注明作者及出處。鑒于部落客處于考研複習期間，有什麼問題請在評論區中提出，部落客盡可能當天回複，加微信好友請注明原因