動機
畫家先畫遠處,再把近處覆蓋上去。對不透明圖形,渲染器也可以按這個次序寫入像素:最後留下的顏色來自最近的表面。然而,給每個多邊形只算一個中心深度,未必能為整張圖排出正確次序。兩個傾斜表面在畫面不同位置可能互換前後。二叉空間劃分(BSP)的辦法是先用平面切開跨越它的多邊形,再根據觀察點的位置遍歷這些碎片。
這裏研究的是物體空間中的可見性算法,並非說所有圖形管線都使用 BSP。假設場景由有限個平面凸多邊形組成,運算精確,觀察點固定;射線參數越小表示越近。表面不透明,所討論的採樣射線有唯一最近交點。重合和浮點誤差需要另外約定。
平面如何劃分問題
設分割平面為 ,其中 。正、負開半空間分別滿足 與 。根據凸多邊形頂點的符號分類;若多邊形跨越平面,就將它裁成兩個閉凸多邊形,它們在平面上共用邊界。跨越邊從 到 的交點為
這是因為 。兩個端點嚴格異號,保證 。已在平面上的頂點和整條共面的邊,需要一致的去重與邊界歸屬規則;分母為零時不能套用這個交點公式。若頂點屬性在原多邊形上按仿射方式變化,也要用相同的邊參數插值。
定義 2.7.1
(有限多邊形 BSP)
在每個節點,選取一個尚未處理的多邊形碎片所在的平面。把所有與該平面共面的碎片存在節點中;切開跨越平面的碎片,將非共面部分分別送入正、負子樹。重複直至沒有碎片。樹根據場景建立,隨後由觀察點決定遍歷次序。
命題 2.7.2
(構造必定終止)
設輸入為有限個凸多邊形,共有 個互異的支撐平面。在每條由根到葉的路徑上,各節點的平面都是輸入多邊形互異的支撐平面,所以每條路徑至多有 個節點,樹是有限的。這裏不聲稱樹平衡,也不給出碎片數目的上界。
證明
(每個節點用掉自己的支撐平面)
用平面切割只會把多邊形換成它自己的碎片,因此每個碎片都保留其所屬輸入多邊形的支撐平面。平面為 的節點存下所有位於 的碎片,所以送入子樹的碎片都不以 為支撐平面。於是一條路徑不會兩次選用同一支撐平面,節點數不超過 。每次切割凸多邊形只產生兩塊,故每個節點只向它的兩個子樹各送出有限個碎片。每條路徑至多 個節點的二叉樹是有限的。
這個論證並不保證樹平衡,也不保證碎片少:選平面不當可能造成大量切割。
遍歷為甚麼正確
定義 2.7.3
(由遠至近遍歷)
設觀察點 不在任何節點平面上。遍歷平面為 的節點時,先訪問位於平面中與 異側的子樹,再繪製存於節點的碎片,最後訪問與 同側的子樹。每個子樹按同一規則遍歷。
定理 2.7.4
(每條射線上的由遠至近次序)
假設觀察點 不在任何節點平面或表面上。對於從 出發的射線,按遍歷次序列出的碎片交點,沿射線距離不增,重合交點除外。因此,用不透明顏色依次覆蓋時,每個有唯一最近交點的採樣點最終保留最近交點的顏色。
證明
(一個平面把射線分成三個有序區塊)
設 ,射線為 ,。因為 關於 是仿射函數,射線只有穿過平面後才能到達負半空間;正半空間的交點則在穿越之前。若射線從未穿越,就不會到達負半空間或平面。因此,沿該射線,遠側子樹的交點都在節點平面交點之後,節點交點又在近側交點之後。 時交換正負即可。對有限樹歸納,每個子樹內部已按遠至近排列,三個區塊連接後仍保持該次序。唯一最近交點最後寫入,所以不透明覆蓋得到其顏色。
證明透視
遍歷證明中各項假設的作用
條件 只用一次:它決定哪個子樹是遠側,也是唯一需要嚴格分側的地方。關鍵一步是 對 是仿射的。沿射線至多變號一次,表示遠側子樹、節點平面、近側子樹這三個區塊佔據射線參數上互不相交且有先後的區間,於是完全不必比較距離。對樹歸納使論證閉合:每個子樹都是較小的樹,具有相同性質,它的交點區塊整個落在自己的區間內。唯一最近交點的假設只在最後一句使用,用來把最後一次覆蓋解讀為可見表面。證明中沒有用到任意兩點之間的歐氏距離、樹是否平衡,也沒有用到碎片的形狀。
結論比較的是同一條射線上的點,並不是說異側半空間中的任意一點都比同側任意一點更遠。投影不相交的兩個碎片可以用任一次序繪製。節點中共面的多邊形若在同一點重疊,就出現等深並列,仍須另定規則。
如果觀察點恰在分割平面上,嚴格異側的規則沒有定義。不包含在平面內的射線會立刻進入一側,且不會在正參數處與該平面上的節點碎片相交;整條射線位於平面的情形則另屬退化情況。實作必須明確規定並列策略或改變觀察點,不能假裝觀察點位於嚴格一側。
概念視角算法
由正負號驅動的樹遍歷
遍歷就是對二叉樹作中序走訪,節點上唯一的判斷是 的正負,每個節點只依觀察點算一次,正負號決定先進入哪個子樹。整個繪製次序最多只需每個節點一次符號判斷,不涉及射線、像素或深度比較,而且與定理中逐條射線的次序是同一個物件。
例題
例題 2.7.5
(切割與改變觀察點)
在 平面中,以直線 類比三維分割平面。線段從 到 ,交點參數 ,故 。把 至 放入負子樹,把 至 放入正子樹。
取觀察點 ,再看三維射線 ,假設三個小平面片分別在 與它相交,中間的片存於節點。參數分別為 ,因此訪問負子樹、繪製節點、訪問正子樹會讓 的顏色最後寫入。上面被切開的線段未必與這條射線相交:遍歷只排列實際交點,並不保證每個碎片都會被擊中。觀察點移到負側後,兩個子樹的訪問次序反轉,樹本身無需重建。
平面符號說明物體位於分割面的哪一側;射線參數只排列這條射線上實際遇到的交點。區分這兩個概念,才能正確理解證明。
例題 2.7.6
(同一棵樹,兩個觀察點)
在平面上計算,以線段代替多邊形。令 為 、 的線段, 由 到 , 為 、 的線段。根節點存放 ,並取 。對 ,、,故 ,。 至 一段放入負子樹; 至 一段與整條 (其上 )放入正子樹。
觀察點為 時,,故次序為負子樹、、正子樹。沿 向 減小方向的射線,在 與 相交,在 與 相交,並且不碰到 的兩段(其 )。遍歷先訪問負子樹(沒有交點),再到 (),最後訪問正子樹中的 ():參數不增。觀察點為 時,,先訪問正子樹。同一條直線在 與 相交,在 與 相交,仍然是不增次序,而樹完全相同。
例題 2.7.7
(觀察點在分割平面上(邊界情況))
沿用上例的 和 ,把觀察點放在 ,則 ,嚴格分側的規則沒有答案。射線 立刻進入正半空間,它只在 與直線 相交,該點不在 上(因 ),並在 與 相交,交點為 。對這條射線,兩種子樹次序給出相同的圖像,因為節點中沒有碎片能在正距離上被擊中。射線 則整條位於平面內:它沿整個區間 與 相交,不存在唯一最近交點。這種正好側視的情況需要明確的約定,例如捨棄正好側視的多邊形,或改變觀察點。
畫家次序的限制
設兩個表面在同一投影區間 的深度函數為 與 ,深度較小者較近。在 , 較近;在 , 較近。無論如何排列這兩個完整多邊形,都不能同時正確覆蓋兩個採樣點。可沿 的交線切開後再排列碎片;交線上仍須處理等深。兩個中心深度相等也不能解決這個問題。
反例模式
按中心深度對整個多邊形排序
命題:把整個多邊形按中心深度由大到小繪製,每個採樣點必定留下最近的表面。上面兩個多邊形的中心深度都是 ,所以兩種次序都是合法的排序。若先畫 、最後畫 ,採樣點 顯示 ,但 ,其實 較近。若先畫 ,採樣點 顯示 ,但 ,其實 較近。在交線 把兩個多邊形都切開即可修正: 在 較近, 在 較近,每一對碎片都有合法的局部次序。
定理依賴不透明覆蓋。透明表面通常都會貢獻顏色,需要適當的合成規則,而不是只保留最後一次寫入。光柵化還需要一致的裁剪和邊界歸屬,才能避免裂縫或重複覆蓋。精確幾何次序本身不能證明浮點實作穩健;曲面或運動幾何也需要更新表示和樹。
常見錯誤
常見錯誤
(把遍歷次序當成所有點的距離次序)
取平面 和觀察點 。點 位於遠側的負半空間,距離為 ;點 位於近側的正半空間,距離為 。因此遠側半空間可以有比近側某點近得多的點。定理只排列同一條射線上的交點。
常見錯誤
(對位於平面內的邊套用交點公式)
對平面 和從 到 的邊,,所以 ,求 的公式會除以零。應先對頂點分類:兩個端點都在平面上的邊屬於節點的共面集合,不用切割;只有一個端點在平面上的邊,只在該端點與平面相交。
練習與解答
快速檢查
(設 。切割從 到 的邊。交點在哪裏?哪一部分位於負側?)
先計算 與 。
解答 · 答案
,,所以 ,。從 到 之前的點為負, 在平面上,其餘開線段為正。
快速檢查
(若 ,三個遍歷區塊如何排列?解釋穿越平面的射線。)
這時哪一側是遠側?
解答 · 答案
先正子樹,再節點,最後負子樹。射線從負側出發,正側交點必須在穿過平面之後,所以比平面交點和穿越前的負側交點遠。這是沿射線的由遠至近次序,不是任意空間點之間的距離比較。
快速檢查
(兩個不透明碎片在同一射線的參數分別為 和 。若中心深度排序導致先畫 再畫 ,結果為何錯誤?)
哪個碎片最後寫入?
解答 · 答案
參數 的顏色覆蓋參數 ,留下較遠的顏色。正確畫家次序是先 後 。深度緩衝則可按採樣點比較深度,但也需要自己的清除值和等深規則。
快速檢查
(節點的兩個共面多邊形在同一射線距離重疊,定理能選出唯一顏色嗎?)
檢查唯一最近交點的假設。
解答 · 答案
不能。交點等深,不滿足唯一最近交點的假設。必須規定並列規則或調整場景表示;交換子樹次序也不能區分兩個節點碎片。