包圍體是篩選,不是物件交點
射線追蹤器可能要測試很多圖元。如果一個包含多個圖元的區域被射線錯過,便可跳過其中所有圖元。包圍體層次結構(BVH)把這些保守區域組織成樹,目的是避免部分昂貴的圖元測試;射線碰到盒子,本身不代表碰到盒內任何圖元。
定義 6.1.1
(射線區間與閉軸對齊盒)
射線為 ,其中 且 。我們尋找 的交點,假設 ;上界可為 。軸對齊盒子是閉集合 ,所有界均有限且 。射線可以從盒內出發,碰到面、邊或角在此閉盒模型中均算相遇。
相交三組平行板
定義 6.1.2
(單一座標的平行板區間)
對 的第 個座標,使 成立的參數 組成區間
最小值及最大值處理 的兩種符號。若 ,該座標永不改變:若 ,則沒有任何 滿足條件,否則每個 都滿足。不要除以零。
定理 6.1.3
(閉盒測試)
若沒有零方向座標排除盒子,便把所有非零方向的 與 相交。射線區間與盒子相遇,當且僅當交集非空;等價地,其最大下端點不大於最小上端點。
證明
(座標條件與同一個參數)
點 屬於 ,當且僅當對 都有 ,而且三個條件在同一個 下成立。
若 ,不等式減去 後除以 ,方向不變,得 。若 ,除以 會令兩個不等號反向,得 。兩種情況的解集都是 ,較小的商在前;公式中的最小值與最大值自動作出選擇。若 ,條件化為 ,與 無關:對所有 成立,或對所有 都不成立。
因此, 給出盒內一點,當且僅當它屬於 與所有 的 的交集,並且沒有任何零方向條件失敗。若有一個失敗,就沒有 滿足,射線錯過盒子。最後,有限個閉區間 有公共點,當且僅當 :這樣的公共點 對所有 滿足 ;反過來, 內的任何 都屬於每個區間。
證明透視
各項假設在哪裏起作用
這個證明有一個不顯眼的要點:三個座標條件是作為參數的集合相交,而不是作為空間中點的集合相交,因為同一個 必須同時滿足全部條件。所以射線可以穿過三個平行板在空間中的區域,卻仍然錯過盒子:區間 可以互不相交。
的符號只用了一次,就是決定哪個商是進入點、哪個是離開點。若去掉最小值與最大值, 時會得到進入大於離開的區間,被誤當成空集。 要單獨處理,因為此時商不存在,平行板條件只是對 的是非判斷。盒子與區間的閉性用在最後一步:最大下端點等於最小上端點,就是一個公共參數,即邊界接觸;若盒子是開集,這種相等情況便是錯過。界有限且 保證每個非零方向的 是真正的有界區間。
射線計算例子
例題 6.1.4
(平行座標)
取 ,,其中 。第一組平行板允許 ;其餘兩個方向為零,起點座標都在各自區間內。因此盒交區間為 。若第二個起點座標改為 ,該平行板對所有 都會排除盒子。
例題 6.1.5
(從盒內出發的射線)
對 及 ,第一組平行板允許 。與 相交得到 :進入參數為負,不代表從盒內出發的射線會錯過盒子。
例題 6.1.6
(正負混合的方向與擦過稜邊)
取 ,,其中 。 平行板給出 。對 ,,兩個商為 和 ,取最小值與最大值得 。 方向為零,且 ,沒有附加限制。 與 的交集是 ,並非空集:射線在 碰到稜邊 ,在閉盒模型中算作相交。
把起點移到 ,則 區間為 ,與 不相交,射線錯過盒子。
常見錯誤
(對每條射線都以下界商作進入點)
對 , 平行板的兩個商是 和 。若把 當進入點、 當離開點,便得到看似為空的 ,射線會被誤判為錯過。正確區間是 :射線在面 進入,在 離開。
常見錯誤
(把負的進入參數當作錯過)
從盒內出發的射線,平行板進入參數為負,如第二個例子。測試會與 相交,把下端點抬高到 ;並不會因為進入參數為負而排除盒子。
反例模式
碰到盒子不代表碰到圖元
一個小三角形可以位於大包圍盒的一角。射線穿過盒子的另一部分時,會碰到盒子卻錯過三角形。只有當保證包含該三角形的盒子被排除時,平行板測試才能排除它;否則仍需要真正的三角形相交測試。
安全遍歷與最近交點
定義 6.1.7
(保守層次結構)
包圍體層次結構是保守的,指每個葉盒包含分派給該葉子的所有圖元,每個圖元至少出現在一個葉子中,且每個內部盒包含其全部子盒。
由根開始,盒交區間為空時排除節點;在未被排除的葉子測試圖元。
命題 6.1.8
(保守剪枝)
設層次結構是保守的,且運算精確。(a) 排除盒交區間為空的節點,不會丟失參數在 內的圖元交點。(b) 若已知有效圖元交點 ,再排除盒區間下端點嚴格大於 的節點,不會丟失參數 的圖元交點。
證明
(祖先盒在相同參數下包含交點)
設圖元 在 被擊中,, 是子樹中有葉子存放 的任一節點。由保守性,該葉盒包含 ,而每個祖先盒都包含其下的盒,所以 。由閉盒測試, 的盒交區間非空且含 ;因此 (a) 不會排除 ,通往該葉子的所有祖先都會被訪問。
對 (b),若 ,則 屬於 的盒交區間,其下端點至多為 ,並非嚴格大於 。因此 同樣不會被排除。
保留相等情況,可避免在平手規則重要時悄悄丟掉同距交點。先走較近的盒子可能更早找到有用上界,但正確性不依賴遍歷次序。對允許區間有限的「任何交點」陰影查詢,找到區間內有效圖元交點後可立即停止;此查詢不要求最近交點。
若許多盒子重疊或射線穿過大多數節點,層次結構可能沒有成效,最壞情況仍須檢查整棵樹。命題假設包圍盒保守且比較精確;浮點捨入、無效數值、邊界慣例和穩健圖元測試均須明確處理。包圍盒若不能保證包含圖元,無論樹形如何都可能錯失交點。
練習
快速檢查
(第一條例子射線若限制 ,盒交區間是多少?)
把兩個區間相交。
解答 · 答案
與 相交得到 。
快速檢查
(對 、 且 ,求區間。)
方向為負,取較小的商作進入點。
解答 · 答案
第一座標在 穿過 、在 穿過 ;其餘座標保持在盒內。區間為 。
快速檢查
(節點盒交區間為 ,已知有效交點 。該節點能否包含更近交點?)
比較下端點與 。
解答 · 答案
不能。射線上所有位於該盒的點均有 ,而所有後代交點都在盒內。
快速檢查
(為何盒交區間非空不足以報告三角形交點?)
想想三角形佔包圍盒的多少。
解答 · 答案
三角形可能只佔包圍盒的一小部分。射線可穿過盒子而不碰到三角形,故仍須測試圖元相交。