動機
投影得到連續幾何,影像卻只儲存有限陣列。光柵化要決定每個取樣位置由哪些圖元覆蓋,以及在該位置應有甚麼屬性;可見性則是另一個問題:多個三角形可以覆蓋同一樣本,但不透明畫面通常只顯示最近的一個。覆蓋、插值及深度比較若混成一件事,便難以分辨裂縫、扭曲紋理與穿透物件的不同成因。
本文先假設三角形已裁剪至視錐內並完成投影。像素取樣位置必須明確,例如像素中心;影像座標採用向上的垂直軸。若屏幕行號向下增加,必須轉換座標或相應符號。幾何推導先採精確算術,實作時還要讓相鄰三角形一致計算共同邊及邊界歸屬。
一個像素不是一個點。像素可以理解為有限影像區域,而點樣本只問某一位置的值。判斷中心落在三角形內,並不等於算出三角形覆蓋像素的面積比例。移動邊緣與細小特徵尤其能顯示兩者差異。因此先建立正確的離散規則,再討論它如何近似所需影像量,才不會把反鋸齒當成幾何正確性的替代品。
定義
定義 2.1.1
(有向邊函數與重心座標)
對影像點 ,定義 ;有向邊左方的值為正。設三角形 逆時針且非退化,,則
分母是有向面積的兩倍。分母為零時,投影三角形沒有二維內部,不能使用這套除法。順時針三角形可重新排序,或一致處理符號;不能不作修改便要求三個邊函數全部非負。
概念視角幾何
權重是有向面積之比
是三角形 有向面積的兩倍,當 依逆時針排列時為正。因此 等於 的有向面積除以 的面積,其餘權重同理:每個權重是對應頂點的對邊所成小三角形佔整個三角形面積的比例。在面積為 的三角形 中,點 給出小三角形 ,面積為 ,故 ,與 相符。點在三角形之外時,小三角形的方向相反,權重因而為負。
定義 2.1.2
(深度緩衝與片段屬性)
深度緩衝在每個樣本儲存至今接受的最近深度。本文約定除法後深度越小越近,初值設在所有有效幾何之後。片段是圖元在某個覆蓋樣本提出的候選貢獻。頂點屬性可以是紋理座標、顏色或其他量,應先說明它在原三角形上如何變化,再選插值規則。
深度值可以是上節的規範化深度,不必是相機的歐氏距離。以下不透明可見性論證假設所有有效片段都參與比較,通過時更新深度;丟棄片段、透明混合及其他測試需要另外說明。
定理 / 命題
定理 2.1.3
(重心重建與覆蓋判準)
對上述非退化三角形, 且 。點屬於閉三角形的充要條件是三個權重皆非負。任何影像座標的仿射函數 都滿足 。
定理 2.1.4
(透視修正屬性插值)
設裁剪後頂點為 ,其中 ;屬性在原三角形重心參數上仿射變化。若投影樣本的屏幕重心權重是 ,則
這裏 是原三角形權重;向量屬性逐分量套用公式。
正分母假設確保三角形內部不會出現總分母為零,正常視錐裁剪可保證它。定理不表示任意物理量都在表面仿射變化;它只正確投影一個已選定的分片仿射模型。插值法向量只有長度非零時才能正規化,再作單位向量使用。兩個相反單位法向量以相同原表面權重平均會得到零,此時正規化沒有定義。模型必須另行指定法向量或著色約定,不能擅自以微小長度作分母。
命題 2.1.5
(深度緩衝的最小值不變量)
在某個樣本,所存深度初值 位於所有有效幾何之後。深度為 的有效不透明片段以任意次序到達,當且僅當片段深度嚴格小於所存深度時,才取代所存深度與顏色。則處理 個片段後,所存深度是 ,與次序無關。若此最小值只由一個片段取得,所存顏色就是該片段的顏色。
證明思路
證明
(由仿射函數得到重心權重)
每個邊函數對 都是仿射的。三個權重在三個頂點分別取標準基底值,故其總和是在三個非共線點皆為一的仿射函數,必恆等於一。同理,仿射映射 在三頂點與 一致,因此處處重建 。非負權重給出凸組合;反過來,凸組合代入邊函數亦全非負。最後對重建公式施加仿射函數,便得到屬性插值結論。
證明
(由原表面權重到屏幕權重)
第二個定理從齊次點 出發,其中 。除法後的影像點為
屏幕重心表示唯一,故 。除以各自的 再正規化,便恢復 ;代入 完成證明。裁剪產生的新頂點,須先按原邊參數插值其屬性,才進行這一步。
證明透視
先插值兩個仿射量,再取商
屏幕權重適合投影後三角形,卻不是原表面權重。證明找出的差異恰好是頂點的齊次分母。按此模型, 與 分別在屏幕上仿射變化;逐樣本取商才重建原屬性。因此光柵器可以沿掃描行增量更新兩個平面函數,再作一次除法。單純插值 後正規化,並不能補回投影改變的權重。
不透明可見性另有一個初等證明,對片段數目作歸納。
證明
(對片段數目作歸納)
記 ,並斷言:處理 個片段後,所存深度為 ;若 只由一個片段取得,所存顏色便是該片段的顏色。 時,因 ,片段被接受。假設斷言對 成立,現有第 個片段。若 ,它取代深度與顏色;新的最小值是 ,只由此片段取得,亦正是所存的內容。否則 ,狀態不變,且 。若 只由一個片段取得,該片段不可能是第 個(否則會得出 ),所以它是前 個之中唯一的最小者,由歸納假設,所存顏色就是它的顏色。最小值與片段次序無關。深度相等時的顏色選擇須另定規則,因此顏色的結論假設最小值唯一。
此結論只關於實際取樣位置,不能保證連續場景的一切細節都有被取樣。
例題詳解
例題 2.1.6
(完整計算一個覆蓋測試)
三角形為 ,樣本是 。分母為 ,三個邊函數為 ,權重是 ,皆非負並重建該點。另一樣本 的權重是 ,故在第一個頂點對邊之外。頂點值為 的仿射顏色分量,在首個樣本取值 。
例題 2.1.7
(錯誤插值造成紋理扭曲)
投影邊中點的屏幕權重為 ,齊次分母為 ,紋理座標為 。直接線性插值得 ;正確值是 。原表面權重為 ,所以同一屏幕中點在表面參數上較接近近端。這正是上節空間中點反例的插值版本。
以下互動使用另一組裁剪分母 ,修正後中點為 ;請與上面 、修正中點為 的例子比較。
例題 2.1.8
(除法後深度不應修正兩次)
仍在同一中點,取裁剪深度 、。頂點除法後深度為 ,正確樣本深度是其屏幕線性平均 。驗算:原權重 給出 、,商亦是 。若把通用透視修正公式錯套在已除法深度上,反而得到錯誤的 。
增量運算與共同邊
固定一條邊後,可展開成 ,其中 、。向右移一個樣本加 ,向上移一個樣本加 ,故只需在包圍盒角落初算一次,再沿掃描行用加法更新。包圍盒仍須真正包含所需樣本中心,增量技術只節省運算,沒有改變覆蓋定義。
若所有邊界都接受,共同邊樣本會被兩個三角形畫兩次;若全部拒絕,則產生裂縫。半開規則把邊界只交給其中一個。對本文向上軸及一致逆時針繞序,一種規則是:邊函數為零時,只接受垂直增量為正,或垂直增量為零而水平增量為負的有向邊。把非零邊反向,歸屬必定相反。其他一致規則亦可;影像行方向不同時,不應死背邊的名稱。
反例模式
邊界取閉區間只對不透明顏色無害
命題:讓兩個三角形都接受邊函數為零的樣本,只是把共同邊上的樣本以同一顏色畫兩次。對不透明顏色這是對的。現在把一對半透明三角形(透明度 、顏色 )以 混合到背景 上:只被覆蓋一次的樣本變為 ;共同邊上被兩個三角形覆蓋的樣本變為 ,形成明亮的接縫。以半開規則把邊界只交給其中一個三角形,每個樣本都恢復為 。
線段光柵化也可用增量隱函數。對水平座標遞增、斜率介乎零與一的線段,在兩個候選樣本的中點檢查隱式直線值,決定下一步維持原行還是上移一行;清除固定分母後可用整數更新。其他八分區需交換軸或符號。獨立線圖元的規則未必與填色三角形邊界相同,因此診斷用線框稍有差異不一定表示三角形覆蓋錯誤。
可見性、精度與影像測量
背面剔除與隱藏面移除不是同一問題。對繞序一致、封閉且不透明的表面,可按朝向剔除背面;但兩個正面仍能重疊,必須靠逐樣本深度判斷。開放薄片、鏡射變換與雙面材質,均要求先重新檢查剔除假設。
深度緩衝不需要把三角形作全域排序。以中心深度排序無法處理相交,亦不能處理前後關係隨影像位置改變的情況。普通透明物件則不能只保留最近片段,因為遠處仍有貢獻;需要保存相關層次並按透明模型混合。
標準透視深度形如 ,其中 ,導數為 。因此遠處相同的深度表示增量,可能對應更大的實際距離差。近乎共面的表面在四捨五入後交替勝出,便形成深度爭鬥。在不裁掉必要場景的前提下,把近面適度推遠可能改善這種深度分配;具體效果仍取決於格式及約定。任意加微小偏移不能取代理解比較規則與幾何關係。
移動邊緣跨過單一點樣本時會突然改變結果。多樣本可更細緻地近似覆蓋,但任何固定有限樣本組都可能漏掉足夠細的特徵。嚴格反鋸齒模型應先指定像素濾波器,再近似它對影像的積分。下一節的紋理濾波處理表面內部相關取樣問題;增加樣本減少某些誤差,並不等於精確面積測量或完全消除混疊。
常見錯誤
反例模式
某個位置的前後關係不能代表整個三角形
兩個重疊三角形的深度可以在局部寫成 、。在 ,第一個較近;在 ,第二個較近。不存在一個適用整個重疊區域的單一先後次序,所以中心排序無法正確畫出兩者。深度緩衝正因在每個位置分別比較,才可處理此情況。
某個量應如何插值,取決於模型假設它在哪個空間仿射變化。紋理座標與顏色並不會自動被每種著色模型同等看待。
常見錯誤
(對已除法的深度再作透視修正)
平面三角形的規範化深度在屏幕上已是仿射,屏幕插值本身便正確。若在屏幕中點、 的情況下,把透視商用於投影後頂點深度 ,得到 ,而正確值是 (見第三個例題),即除以 做了兩次。應逐個量判斷它在屏幕空間仿射,還是在原三角形上仿射,只修正後者。
常見錯誤
(不論繞序都要求三個邊函數非負)
判準 假設 。對順時針三角形 ,;在內部樣本 ,三個邊函數值是 ,要求三者非負的測試會拒絕這個樣本。除以 得權重 ,或先交換兩個頂點恢復逆時針次序再測試。
總結
邊函數同時提供覆蓋測試及重心權重;一致邊界歸屬避免裂縫和重複覆蓋。不透明深度測試逐樣本維持最小值。透視修正把屏幕權重除以頂點齊次分母再正規化;除法後深度本身則已屏幕線性。這些結果描述離散樣本,不應混同連續像素積分。
練習
快速檢查
(對三角形 ,求 的重心權重,並判斷 是否在內。)
先算分母 。
解答 · 引導解答
分母為 ,、,故首點權重是 。第二點的權重為 ,有負數,所以在外;第一個負權重指出其違反的對邊。
快速檢查
(對邊 ,展開邊函數,求向右及向上一步的增量,並測試 。)
展開行列式,讀出 與 的係數。
解答 · 引導解答
。向右增量為負四,向上為三。在 取負一,位於有向直線右方。反向整條邊會把符號全部翻轉,因此內外及邊界約定也要一致轉換。
快速檢查
(給定 、、,求透視修正值,與直接線性插值比較。)
先求兩個和 與 。
解答 · 引導解答
分母為 ,分子為 ,故結果是 。原表面權重 亦給同一答案。直接插值為 ,對遠端頂點給了過大權重。
快速檢查
(一個樣本依次收到不透明片段深度 ,初值為一。列出更新;若最後片段半透明(alpha 為 ),單純保留最近顏色有何不足?)
把每個新深度與所存值比較。
解答 · 引導解答
深度依次由一變成 、,拒絕 ,最後變成 。不透明模型只顯示最後接受的顏色。半透明近層仍應透出背後部分顏色;直接覆蓋並丟棄遠層會失去此貢獻,必須保留或重算背景,再按明確透明模型合成。