二叉空間分割

---

二叉空間分割是一種用於計算機圖形學和演算法幾何學中將空間劃分為較小部分的資料結構。BSP是在3D計算機圖形學環境中開發的。BSP 包括諸如幾何形狀操作、地理空間和光線追蹤等應用。

這是一個兩步過程

步驟 1 - 建立 BSP 樹。

步驟 2 - 顯示樹。

建立 BSP 樹

二叉空間分割的視覺化表示

二叉空間分割演算法遞迴地將空間劃分為兩個半空間。因此，請記住每個多邊形圖形中都有一個分割區域。

瞭解在樹中建立 BSP 的步驟 -

• 我們將首先將演算法應用於樹的根節點，即 A。

• 然後我們將 BSP 演算法 B 應用於左節點，將 C 應用於右節點，其中 A 是其父節點或根節點。

• 現在，我們開始使用 B 節點進行最左邊的第二次分割槽，我們只需將子節點D 新增到左側，將E 新增到右側節點。

• 完成最左邊的節點後，我們開始使用 C 節點進行最右邊的第二次分割槽，我們只需將節點F 新增到左側，將 G 新增到右側節點。

顯示樹

讓我們以樹遍歷為例，

Fa, A, B, C, D, E, Fb --- (LDR)

• 如果視點在後面，則按中序遍歷樹。

• LDR 表示為

Process of left sub-tree -> Process of current-node -> Process of right sub-tree.

讓我們以樹的反向遍歷為例，

Fb, E, D, C, B, A, Fa --- (RDL)

• 如果視點在前面，則反向或中序遍歷樹。

• RDL 表示為

Process of right sub-tree -> Process of current-node -> Process of left sub-tree.

二叉空間分割的優點

• 在二叉樹上很容易理解和實現程式。

• 它可以提高可擴充套件性和最佳化效能。

• 遊戲行業透過基於 BSP 更新或開發整個遊戲來很好地利用 BSP。

二叉空間分割的缺點

• 生成 BSP 需要大量時間。

• 它不能解決 VSD（視覺表面檢測）問題。

結論

我們都知道二叉空間分割是一種資料結構，但藉助它，我們還可以建立一棵二叉樹，其中所有節點都有兩個分支。此技術可用於製作 3D 遊戲。例如，Doom 遊戲非常流行，它是使用 BSP 演算法開發的。