快速軸對準單元遍歷算法

Question

• 給定一個軸線對準方在給定的線段從點S1要點S2相等的尺寸A，B，C和D.
• 的四個單元劃分。

什麼是最快的方式來找到段（如果有的話）遍歷單元格，按遍歷順序排序？

在上面的例子中，正確的結果是：

• 段1：[d]
• 段2：[A，B]
• 段3：[C ，D，B]
• 段4：[]
• 段5：[C]

Answer 1

你可以試試"A Fast Voxel Traversal Algorithm for Ray Tracing" Amanatides和Woo。

它旨在處理大網格，但該原理對於您的應用程序也可能有用。

Answer 2

下面可僅使用簡單的線相交公式來完成：

觀察到您的網格由6條線段（3個水平，3個垂直）。如果要將這些分段中的每一個分段擴展到無窮大（使它們成爲線條，而沒有開始點或結束點），則將2D空間劃分爲16個區域。

定義一個4x4的區域陣列。對於每個這樣的區域，存儲哪條線（如果有的話）將其劃分在北側，東側等。這將是我們的遍歷數據結構。

現在，要查找給定查詢段S遍歷的單元格，從u開始到v結束，我們將使用此遍歷數據結構執行從u到v的行走，以跟蹤我們所在的區域目前在和在哪個位置我們正在退出該區域。

• 將Au確定爲u所在的區域，將Av確定爲v所在的區域。由於區域的軸對齊特性，每個區域不應超過4次比較（x座標爲2，y爲2）。
  此外，將當前位置定義爲p，將當前區域定義爲A;最初，這些將分別是你和Au。

• 首先，報告A作爲S穿過的區域。確定段*（p，v）與A的4個邊的每一邊的分界線之間的第一個交點。如果這樣的交點q被找到時，包含q的邊確定哪個相鄰區域將成爲我們的新A - 在這種情況下，我們的新p將成爲交點q，使用這個新的A和p，重複這一步
  如果沒有交點發現，p必須位於相同的區域中v和步行完成

* （p，v]含義：p和v之間的段，除p以外但包括訴