有效計算觀察射線與一組物體之間的第一個交點的最佳方法是什麼？

Question

例如：

有效計算觀察射線與一組三個物體（一個球體，一個錐體和一個圓柱體（其他3D基元））之間的第一個交點的方法。

Answer 1

你正在尋找的是一個空間分區方案。處理這個問題有很多選擇，並且在這方面也有大量的研究。克里斯特愛立信的Real-Time Collision Detection是一個很好的閱讀。

該書中涵蓋的一個簡單方法是定義一個網格，將所有對象分配給它相交的所有單元格，並且沿着與該線相交的網格單元前後移動，與與該網格單元格關聯的每個對象相交。請記住，一個對象可能與更多的網格單元格相關聯，所以計算出的交點可能實際上不在當前單元格中，但實際上稍後。

下一個問題將是你如何定義該網格。不幸的是，沒有一個好的答案，你需要考慮哪種方法最適合你的情況。其他感興趣的分區方案是不同的樹結構，如kd-,Oct-和BSP-trees。你甚至可以考慮使用與網格相結合的樹木。

編輯
正如指出的那樣，如果你的設置實際上是這三樣東西，你肯定更好的只是每一個相交，並只挑選最早的。如果你正在尋找射線球，射線柱等交叉點測試，這些並不是很難，而且一個快速谷歌應該提供你可能需要的所有數學。 :)

Answer 2

「計算效率」取決於該集有多大。

對於一小組三個，只是依次測試它們中的每一個，它是真的不值得嘗試優化。

對於較大的集合，查看劃分空間的數據結構（例如KD-Trees）。整個章節（甚至整本書）都致力於解決這個問題。我最喜歡的參考書是An Introduction to Ray Tracing（編輯安德魯·S。格拉斯納）

或者，如果我誤解你的問題，你實際上需要的算法對於特定類型的對象射線對象路口，見同一本書！

Answer 3

我假設你有一個射線d =（dx，dy，dz），從o =（ox，oy，oz）開始，你可以找到參數t，使得交點p = o + d *噸。 （類似於this頁面，其描述了使用P2-P1作爲d，P1作爲o和u作爲t的射線平面相交）

我會問的第一個問題是「這些物體是否相交」？

如果不是那麼你可以作弊一點，並檢查有序的射線碰撞。由於您有三個物體可能會或不會每幀移動，因此需要預先計算它們距相機的距離（例如，從它們的中心點）。依次測試每個物體，通過距相機的距離，從最小到最大。雖然空白空間是現在渲染中最昂貴的部分，但這比僅對三者進行測試並取最小值更有效。如果你的圖像高分辨率，那麼這是非常有效的，因爲你在像素數量上分攤成本。

否則，對所有三種，並採取最小值...

在其他情況下的測試，你可能想使這兩種方法的混合體。如果您可以按順序測試兩個對象（例如，沿着圓柱形隧道向下移動一個球體和一個立方體），但測試第三個並獲取最小值以查找最終對象。

Answer 4

那麼，這取決於你真的想做什麼。如果您希望爲簡單場景中的幾乎每個像素生成一個正確的解決方案，一個非常快速的方法是預先爲每個像素預先渲染所有對象的「前面有什麼」使用掃描轉換（也稱爲z緩衝區）將顏色轉換爲背景項目緩衝區。這有時被稱爲項緩衝區。

使用該預計算，您可以知道將要拍攝到場景中的幾乎所有光線都可見。因此，您的光線環境相交問題會大大簡化：每條光線都會碰到一個特定的物體。

當我在做這個many years ago時，我正在製作一些公認的簡單場景的實時光線追蹤圖像。我在相當一段時間裏沒有重新訪問過這些代碼，但是我懷疑用現代編譯器和圖形硬件的性能會比我看到的好幾個數量級。 PS：當我在90年代初期進行文獻搜索時，我首先閱讀了關於物品緩衝區的想法。我最初發現它在（我相信）從70年代後期的ACM文件中提到。可悲的是，我沒有可用的源代碼，但簡而言之，這是一個非常古老的想法，並且非常適合掃描轉換硬件。