高效光線追蹤的數據結構

Question

我正在寫一個3D光線追蹤器作爲個人學習項目（Enlight），並遇到了一個有趣的問題，涉及到在光線和物體場景之間進行相交測試。

的情況是：

• 我有一個數字，光線可以與（球狀，盒，飛機等），以及它們的組相交的圖元。總的來說，我稱之爲這些場景對象。
• 我希望能夠通過將對象包裝在一個Transform對象中來使場景中的對象具有任意仿射變換（重要的是，這將允許在場景中的不同位置使用相同基元的多個實例，因爲基元是不可變的）
• 場景中的對象可以被存儲在邊界體積層級（即我做空間分割）
• 我的相交測試與Ray對象表示的部分射線段工作（開始矢量，歸一化的方向矢量，開始距離，結束距離）

問題在於，當光線碰到Transform對象的邊界框時，看起來像對其中包含的已轉換基元進行相交測試的唯一方法是將Ray轉換爲轉換後的座標空間。這很容易，但如果射線沒有擊中任何變形的物體，我需要回退到原始的Ray繼續追蹤。由於變換可以嵌套，這意味着我必須爲每個已完成的相交軌跡保留一大堆Ray。

這當然是整個應用程序的內部循環和主要性能瓶頸。它會被稱爲每秒數百萬次，所以我渴望儘量減少複雜性/避免不必要的內存分配。

有沒有一種巧妙的方法可以避免必須分配新的Ray s /保留Ray堆棧？

還是有一個更聰明的方法來完成這一切？

Answer 1

大多數時間在光線追蹤中，您有幾個（幾十萬個）物體以及更多的光線。可能是數百萬光芒。既然如此，看看你可以在物體上花費什麼樣的計算是有意義的，以便讓它更快/更容易讓光線與它們相互作用。

作爲boyfarrell的建議，緩存將非常有幫助。不僅可以在對象上創建正向和反向轉換，而且還可以將對象的副本保留在全局框架中，這可能是有意義的。它使得創建對象或移動它們變得更加昂貴（因爲變換會發生變化，所以緩存的全局框架副本也會變化），但這可能沒問題。

如果您投射了N條光線並且具有M個物體並且N >> M，那麼理由是每個物體都會有多條光線擊中它。如果我們假設每條光線都碰到一個物體，那麼每個物體都有N/M條射線。這意味着將N/M射線轉換爲每個物體，進行測試，並可能將其反轉回來。或者每個對象的N/M變換最小。但是如果我們緩存轉換後的對象，我們可以對每個對象執行一次轉換以獲得全局框架，然後不需要任何額外的轉換。至少對於命中測試。

Answer 2

定義基本形式的基本形式（單位尺度，以0,0,0爲中心，不旋轉），然後僅使用變換將它們移動到場景中。緩存每個對象中完整的正向和反向轉換的結果。 （不要忘記法向量，你需要它們進行反射）

這會給你測試使用簡化數學命中的能力（將光線逆向轉換到對象空間並用基本形式對象計算命中）然後使用其他變換將命中點和可能的反射向量轉換回現實世界空間。

您需要計算場景中所有物體的交點，並選擇最接近射線原點的點（但不是負距離）。爲了加速實現這個目標，將多個對象包圍在「邊界框」中，計算點擊會非常簡單，並且如果點擊（但所有對象仍將使用其預先計算的矩陣），則將現實世界射線傳遞給封閉對象。