線段可以穿過視景邊界
一個頂點位於視景體之外,並不表示整條線段不可見。線段可能穿入視景體,再從另一個平面離開。我們可在除以齊次座標之前,透過相交參數區間精確找出保留部分。本篇在精確算術下研究線段。
使用列向量形式的裁剪座標 ,並採用對稱約定
其他圖形 API 或深度約定可能使用不同的近平面不等式。以下方法適用於任何明確指定的線性裁剪空間不等式集合。此約定與現有相機筆記一致,並非聲稱每個管線都相同。
定義 7.1.1
(裁剪空間中的線段裁剪)
輸入是一對裁剪座標 ,由同一個線性變換作用於原始端點而得,並保留它們實際的尺度。原始仿射參數為 ,而
六個裁剪函數為 ;裁剪體是這六個函數同時非負的點集。輸出是集合 ;當 時,還有裁剪後的端點 與 。
若單獨改變一個端點的尺度,這個參數化便會改變。若屬性沿原線段按仿射方式變化,新端點的屬性值必須使用同一個原始 。
每個平面給出一個區間
把六個不等式寫成 ,其中 是六個裁剪函數之一。對某一平面,令 、。由 的線性性,
若兩值都非負,整段線段均滿足該平面;若兩值都為負,原線段沒有點滿足它。其餘情況的邊界參數為
當 ,保留 ;當 ,保留 。這兩種穿越情況下分母均非零。先把保留區間設為 ,再與每個平面容許的區間相交;若下界大於上界則拒絕。若兩界相等,仍留下一個邊界點;如何把它作為圖元繪製需要另外約定。
定理 7.1.2
(區間裁剪的精確性)
對六個裁剪函數中的每個 ,令 ,並記 、。則:
- 若 且 ,則 ;
- 若 且 ,則 ;
- 若 ,則 ;若 ,則 ,其中 。
因此,位於裁剪體內的點的參數集合為 ,它是閉區間 (下界取各下界的最大值,上界取各上界的最小值),或者為空集。
證明
(每個平面給出閉區間,裁剪體對應它們的交集)
函數 是 的仿射函數。
若 ,則在 上 。若 ,則 是兩個負數的凸組合,故為負,所以 。
若 ,則 ,所以 嚴格遞增,並且恰在一點 取零。因為 ,所以 ;又 等價於 ,所以 。由嚴格單調性,,即 。若 ,則 嚴格遞減,,且 ,即 。
點 位於裁剪體內,恰好當六個不等式都成立,亦即 同時屬於六個集合 。每個 是閉區間或空集,閉區間的交集仍是閉區間或空集;其下端是各下端的最大值,上端是各上端的最小值。
證明透視
區間論證中各個假設在哪裏起作用
關鍵一步,是把一個幾何問題(線段哪一部分位於多面體內)換成六個單變量的符號問題。這個替換之所以合法,全因 是仿射函數。有兩個假設支撐它。第一, 是 的仿射函數,是因為端點取的是保留了實際尺度的裁剪座標;若單獨改變一個端點的尺度,被裁剪的曲線就變了。第二,每個裁剪函數對 是線性的,所以與 複合後仍是仿射函數。一元仿射函數是單調的,因此符號至多改變一次,其非負集合是單一區間。
論證能夠收尾,是因為保留的集合是閉集,並且只取交集,不取並集:一個點必須通過每個平面才算在內。不等式不取嚴格形式,才使每個集合是閉的,下界與上界才屬於區間。若不等式改為嚴格,同一論證只會得到半開區間,邊界點便被丟掉。
若條件是非線性的,論證便不成立。透視除法之後,條件 對 不再是仿射的;下面的反例顯示會出甚麼問題。
齊次座標不同的穿越例子
例題 7.1.3
( 變化時從左平面進入)
取 、。對左平面 ,端點值為 、,所以線段在 進入。此時
其餘五個不等式在 全部成立: 在 為 、在 為 ,而 與 都等於 。因此保留區間是 。若某個沿原線段仿射變化的純量屬性在兩端分別為 和 ,新端點的屬性值便是 。
反例模式
先做除法,再沿用同一個參數
一個誘人的說法:先投影兩個端點,再用同一個 插值屏幕座標。對上面的線段,兩端的屏幕 座標為 和 。在 ,這個做法得到 。但裁剪空間中 的真正點是 ,其屏幕座標為 ,剛好落在左邊界上。由於 ,這個做法把新端點放錯了位置。
當 改變時,透視除法對原參數不是仿射運算。應先裁剪齊次線段。投影後,對指定為沿原表面參數仿射變化的屬性使用透視修正插值;平坦或屏幕線性屬性則依各自聲明的插值規則處理。
概念視角代數
屏幕參數是 t 的分式線性函數
沿線段,屏幕點的參數為 ,即投影後的線段已走過的比例,其中 。因此除非 , 的等距步長在屏幕上並不等距。取 、, 得 ,屏幕座標 恰好落在左邊界,與裁剪空間的計算一致。把 當作 來用,正是反例所駁斥的做法。
例題 7.1.4
(兩個端點都在外面,線段仍有一部分可見)
取 、,所以 恆為 。兩個端點都違反某個平面,但線段中段在內。對 :、,所以 ,容許集合為 。對 :、,所以 ,容許集合為 。 與 方向的四個平面給出 ,不產生限制。
保留區間為 ,裁剪後的端點是 與 。若某個屬性沿原線段仿射變化,兩端值為 和 ,則在這兩點的值分別為 與 。
例題 7.1.5
(交集為空而被拒絕)
取 、。逐個平面看: 有 、,所以 ,容許集合為 。平面 有 、,所以 ,容許集合為 。其餘四個函數在兩個端點都非負: 取值 和 , 取值 和 ,。
交集 為空,所以線段被拒絕。這個判斷是精確的:在 (即 )時,點的 ,線段從正方形的角外面經過。注意沒有任何單一平面使兩個端點同時為負;是交集為空才檢測出線段未擊中視景體。
邊界與表示的檢查
平面經過端點時,不應直接使用可能分母為零的穿越公式:先判斷符號情況。若平面值均為零,整條線段都在平面上;若一個為零而另一個為負,與該半空間的交集可能只有端點。合併多個平面後,若當前下界大於上界,即使沒有單個原端點違反所有平面,也須拒絕。
六個不等式蘊含 。當 ,它們還迫使 ;這是沒有射影像的零齊次向量。保留的零向量不能除以 ;實際管線需要對此退化輸入制定規則,或使用確保 為正的適當裁剪範圍。若只因一個保留端點奇異就丟掉整條線段,也可能丟掉其他點。數值容差、有限精度和邊界歸屬規則須另行指定,不能由精確推導直接得到。
常見錯誤
(兩端違反不同平面,不能就此作出判斷)
兩個端點對同一個平面都為負時,可以拒絕線段。反過來並不成立:在上面的拒絕例子中,兩個端點違反不同的平面( 違反 , 違反 ),沒有任何平面使兩端同時為負,線段卻沒有擊中裁剪體。相反,兩個端點各自違反某個平面,也不表示必須拒絕,由 到 的線段便是例子。只有六個區間的交集才能作出判斷。
常見錯誤
(第一次裁剪後重新開始計參數)
若逐個平面裁剪,第二次裁剪是在由 到 的縮短線段上進行,帶有新的參數 。屬性仍須按原始參數插值,即 ;直接使用 會得到錯誤的值。在第一個例子中,裁剪到 後,縮短線段上 的點是 ,所以屬性值對應 ,而不是 。
練習與解答
快速檢查
(對某平面,、。保留哪個區間?)
先判斷哪個端點在容許的一側。
解答 · 答案
此時 ,所以 ,保留區間為 。
快速檢查
(若 ,線段上有點能通過該平面嗎?)
把 用 與 表示。
解答 · 答案
沒有。仿射值 對每個 都等於 ,所以容許集合為空。
快速檢查
(在第一個例子中,若兩端屬性為 和 ,求新端點的屬性值。)
使用原始參數 。
解答 · 答案
。
快速檢查
(若保留區間的上下界都為 ,數學交集是否為空?)
與下界大於上界的情況比較。
解答 · 答案
不為空;它是一個邊界點。它是否繪製出樣本則由另一約定決定。
關於裁剪空間管線及 API 特有細節,可參閱 Khronos 的 OpenGL 4.6 Core Profile 規格第 13.7 節。本文推導明確指定的對稱視景體線段模型,並不表示每個 API 都採用相同深度約定。