動機
三角形可能橫跨相機視域的邊界。只因一個頂點在外便整個拒絕,會失去可見部分;完全保留它,則可能在投影時遇到零分母。裁剪位於兩者之間:精確留下圖元在允許區域內的部分。結果未必仍是三角形,所以必須保留多邊形連接次序,以及新頂點的屬性意義。
前面的幾何與光柵筆記建立了座標變換及透視商式。本節把它們組成一個有限程序:位置與屬性一起裁剪,再把保留的凸多邊形三角化,使用一致邊界歸屬,最後比較深度。若交點位置正確但紋理座標錯誤,畫出的仍是錯誤表面;幾何與屬性不能分開隨意處理。
以下先證明精確算術及非退化輸入的結果。實作仍要指定近邊界數值政策、共同邊的一致計算及深度相等時的規則。對每條不等式各自加一個小容差,並不自動證明沒有裂縫或重疊。我們會區分幾何結論與額外數值要求。
定義
定義 7.2.1
(齊次半空間與攜帶數據)
裁剪位置為 ,半空間寫成 ,其中 固定且非零。慣用對稱視域採用 、、。頂點紀錄包括位置、所有假定在除法前仿射變化的屬性,並可攜帶相對原三角形的重心座標。
這些齊次不等式在四維空間形成凸錐。一般具有正近面距離的透視相機,其有效保留幾何具有正 ,可作透視除法。單看六條不等式亦會接受零向量,但零向量不是射影點;輸入須來自有效非零幾何表示,不能任意以四個零當作頂點。
定義 7.2.2
(有向多邊形與取樣規則)
凸多邊形以循環排序頂點表示,相鄰頂點相連,最後一點亦連回第一點。裁剪及除法後,影像三角形使用一致逆時針繞序。有向邊 的函數為 ;內部要求三條邊值為正,零值則依一個一致半開規則決定歸屬。
凸性是下述單一頂點列表算法的條件。非凸多邊形裁剪後可能分成不相連部分,未必能用一條普通封閉頂點列表正確表示。三角形本身是凸的,而凸集合與半空間的交集仍凸,因此逐面裁剪始終留在安全輸入類別內。
定理 / 命題
定理 7.2.3
(單一平面的凸多邊形裁剪)
設非退化凸多邊形的循環頂點為 ,保留半空間為 。這裏在內包含邊界,即 。對每條有向邊 ,四種輸出為:兩端在內,輸出 ;只有 在內,輸出交點;只有 在內,先輸出交點再輸出 ;兩端在外,不輸出。跨界邊的交點是
邊界端點可與計算交點重合。刪除連續重複頂點及末尾重複的首點後,所得正是原多邊形與半空間的交集,亦可能為空或降維。
定理 7.2.4
(裁剪與重新三角化保留仿射屬性)
假設屬性在原三角形重心參數上仿射變化。每次產生裁剪交點時,使用與位置相同的參數 插值其原重心座標,便保留了原表面的屬性。對所得多邊形作任意非退化三角化,在齊次分母為正的共同影像點使用透視修正插值,結果皆相同。
定理沒有保證不同原三角形之間的屬性平滑,只保證細分同一仿射表面模型不會改變它。材質接縫、面法向量及類別標籤應使用各自的邊界或平面著色約定,不能把離散標籤任意解釋成線性變化數值。
證明思路
證明
(沿邊界遍歷與四種邊情況)
沿邊有 。兩端嚴格異側時,唯一零點給出公式,而且位於零與一之間;邊界端點亦可由同一公式得到。兩端在外時,兩個負值的凸組合仍為負,故整條邊不可能進入。
沿多邊形循環邊界前進,內部邊段保留原次序。離開半空間後,交集邊界沿裁剪平面返回下一個進入點;凸性保證這段連線位於原多邊形內。四種情況正好按順序建立這些邊界片段。因此輸出是交集;若不再有面積,結果可能是空、點或線段,不應當作非退化三角形填色。只要結果的仿射維度仍為二,便可繼續論證;中途若降維,對填色表面直接丟棄,因後續交集不能恢復面積。這便證明六個半空間的填色程序。
證明
(攜帶的重心座標重現原表面)
設原屬性為 ,原頂點重心向量為三個標準基底。交點攜帶 ,其分量和仍為一,位置及 都符合原模型。歸納可知每輪皆保留此關係。在新三角形內,兩個仿射重建若於三頂點相同,便處處相同,因此重新三角化不改原重心座標。透視只改影像參數,修正商式會恢復同一表面值。
證明透視
不變量是原表面的座標描述
攜帶重心座標不只是攜帶最後顏色,而是記錄每個新點在原三角形的來源。每次裁剪都維持分量和及位置對應,所以改變計算分解不會改變表面。這亦提供直接除錯方法:在裁剪邊先檢查屬性與來源是否一致,比等到紋理畫錯才猜測原因容易得多。
例題詳解
例題 7.2.5
(三角形裁剪成四邊形)
令 ,頂點為 、、,保留 。三個值為負一、一、一,兩交點參數皆為 。保留多邊形為 ,維持原順時針繞序。若光柵測試要求逆時針,須反轉次序或調整符號。只保留原內部頂點,會錯誤地只剩線段 ;扇形三角化則給出兩個三角形。
概念視角幾何
把裁剪看成對重心座標三角形的切割
把原三角形的點寫成 ,其中 且 。由線性可知, 變成 ,即對 三角形的一次半平面切割。所以裁剪就是重心空間中的多邊形切割,保留下來的座標正是攜帶的座標。在四邊形的例子中,、,得 ,其邊界在 與 的中點與兩邊相交。
例題 7.2.6
(裁剪屬性須用原邊參數)
若 、、屬性為零及四,進入交點參數是 ,因此 。其屏幕參數卻是 。若用此屏幕參數裁剪屬性,會得到二而不是一。以屏幕權重作透視修正則得 ,與攜帶值一致。
例題 7.2.7
(共同對角線只有一個擁有者)
把頂點為 的正方形沿上升對角線分開。樣本 對兩三角形的共同邊值皆為零。向上影像軸下,零邊只在垂直增量為正,或水平而向左時接受。故 擁有此樣本,其反向不擁有。一致繞序的兩三角形恰好覆蓋一次;兩邊皆閉則畫兩次,即使不透明顏色恰巧相同,混合或樣本計數仍會受影響。
完整程序與可見性
每個裁剪面開始時建立空輸出列表,把 初始化為輸入最後一點。依次把每點當作 ,套四種情況,再設 。結果送入下一面;空列表或仿射維度低於二便停止,因本文處理填色面積。循環初始化不能省略,否則最後到第一點的邊沒有被測試。少於三個相異非共線影像點的結果,不貢獻填色面積。
凸多邊形 的扇形三角化使用 ,其中 。除 外,每點沿由 出發的射線,會落在某條相對邊與該頂點形成的三角形內;先丟棄零面積扇形三角形,其餘內部互不重疊,除邊界外覆蓋原多邊形。內部對角線也必須採相同半開規則。覆蓋用的邊界偏置不應加到插值重心值上,兩者用途不同。
對正面積影像三角形,邊函數除以面積分母得到屏幕權重。正齊次分母下,表面屬性為
常見錯誤
(對除法後的深度再作透視修正)
除法後深度 本身在屏幕上仿射,不應修正兩次。
每個不透明樣本保留最小有效深度,對片段數目歸納可證它始終是已見最小值。相等深度的顏色及有限精度捨入仍須另定;理想最小值與次序無關,沒有消除這些實作問題。
裁剪移除視域之外的幾何,深度比較處理視域內的遮擋,背面剔除則另依朝向、拓撲及材質假設。薄雙面片不能只因為已三角化,便當成封閉單面實體。
常見錯誤
反例模式
所有頂點在外,仍可能有可見部分
三角形 的頂點全部在正方形 外,卻包含原點並覆蓋正方形部分。沒有原頂點在內,不足以安全拒絕。所有頂點違反同一半空間,是安全簡單拒絕的充分條件,並非完全在外的必要條件;其他完全在外的三角形會由裁剪化為空;對部分可見三角形,保留部分的頂點可能全是新交點。
裁剪命題中的凸性假設不能隨意去掉。
反例模式
U 形多邊形令單一列表規則失效
對非凸的 U 形多邊形 套用四種情況,保留 。真正的交集是兩個互不相交的單位正方形 與 。沿邊走一遍得到單一循環 ,它以沿 的零寬度橋把兩個正方形連起來。由 作扇形三角化會產生三角形 ,它包含點 ,但該點位於兩個正方形之間的空隙。補救辦法是先把非凸輸入分成凸塊,或使用能輸出多個循環的裁剪器。
常見錯誤
(把每個三角形擴大一個 )
浮點實作若反向處理同一條共同邊,獨立求交可能略有不同。精確證明只指定目標,不是一個完整無裂縫數值實作。重用共同幾何、規範邊的計算次序或採用明確定點覆蓋方案,可建立一致性;任意擴大所有三角形則可能產生重疊,並改變正在畫的表面。
總結
半空間裁剪由四種邊情況構成。攜帶原重心座標讓位置與仿射屬性同步,並證明重新三角化不改變表面。半開覆蓋指定共同樣本唯一歸屬,不透明深度測試再選最近貢獻。各步有自己的不變量與數值條件。
練習
快速檢查
(線段滿足 ,位置為 ,屬性為二及十。求離開交點及屬性。)
解答 · 答案
參數為 ,交點為 ,屬性為 。位置與屬性使用同一參數,不能把最終座標值擅自當成權重。
快速檢查
(把逆時針三角形 按 裁剪,列循環結果及兩三角形分解。)
解答 · 答案
交點為 。循環結果是 。扇形分解為 及 ,面積為一及 ,總保留面積為 。
快速檢查
(新頂點原重心座標為 ,原屬性為 ,求屬性。之後再裁剪,為何仍要攜帶重心向量?)
解答 · 答案
值為 。原重心向量標示同一原表面模型;再次插值它便維持不變量。只相對最新多邊形另造權重,可能失去與原頂點屬性的關聯。
快速檢查
(初深度為一,片段深度依次為 。嚴格小於測試接受哪些?交換兩個相等深度的顏色,會發生甚麼?)
解答 · 答案
第一個 更新,第二個相等值失敗,最後 更新。近片段到來前,先到的相等深度顏色勝出;交換它們會改變此中間顏色,最終最近顏色則不變。最小深度的次序獨立性,不表示重合表面的顏色必然唯一。