減少計算而光線追蹤

Question

我寫我自己的3D遊戲引擎（我花了一年），我想創造我的CPU上運行的光線跟蹤（而不是GPU！）

就目前而言，射線追蹤過程如下簡化：

1. 爲每個輸出像素投射射線。
2. 如果當前射線碰到物體，設置輸出像素的顏色爲「白色」
3. 否則設置爲黑色

爲了提高光線跟蹤器的速度，我添加了一個球形邊界框每個實體。如果當前射線與邊界框相交，它將運行與實體的每個三角形的相交測試。

我在射線三角交點和射線點距離上使用了最快的方法，但每條射線都必須測試每個可能相交的實體的每個三角形。

因此，使用大約10000多個多邊形渲染一個對象（1920x1080）需要5分多鐘，我想這不是我想要的。

有什麼辦法減少我需要檢查的三角形數量嗎？

問候，芬蘭人

Answer 1

有沒有減少，我需要檢查三角形的量的方法嗎？

是的。

這聽起來像你的場景由三角列表組成，並且你正在線性迭代列表並檢查每個三角形以找到最接近的三角形。這是線性搜索並具有運行時間，n =三角形的數量。

您可以通過使用volumetric kd-trees或bounding volume hierarchies存儲您的三角形，從而減少該平均O(log(n))時間。就個人而言，我更喜歡kd-trees，但任何一種方法都可行。請注意，BVH通常在動畫場景中表現更好。

請注意，加速結構可能包含構造或遍歷的細微缺陷，因此您可能需要開發一些方法來使用樸素列表方法（用於參考圖像）和結構化方法呈現相同的場景。在我的愛好追蹤器中，我這樣組織：

AbstractScene - 所有場景類型的基類。大多數代碼僅與AbstractScene字段和方法交互。

KDScene - 將場景實現爲kd-tree的派生類。

​​- 將場景實現爲BVH的派生類。

NaiveScene - 將場景實現爲三角形列表的派生類。

還有其他加速結構，如grids (aka voxels)。