資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究資料結構中的BSP樹
在計算機科學中，二進位制空間分割（BSP）是一種方法，它透過使用超平面作為分割來遞迴地將空間細分為兩個凸集。這種細分過程產生了物件在區域內表示為樹形資料結構（稱為BSP樹）的形式。
二進位制空間分割發明於1969年，當時是在3D計算機圖形學的背景下發明的，其中BSP樹的結構允許快速訪問場景中物件的有關空間的資訊，這些資訊在渲染中很有用，例如相對於給定位置的觀察者的物件從前到後的排序。BSP的其他應用包括：在CAD中對形狀進行幾何運算（構造實體幾何），3D影片遊戲和機器人技術中的碰撞檢測，光線追蹤以及其他涉及處理複雜空間場景的應用。
概述
二進位制空間分割被視為一種遞迴地劃分場景為兩部分的通用過程，直到劃分滿足一個或多個要求。它可以被視為其他空間樹結構（如k-d樹和四叉樹）的泛化，其中用於劃分空間的超平面可以具有任何方向，而不是像k-d樹或四叉樹那樣與座標軸對齊。當在計算機圖形學中實現以渲染由平面多邊形組成的場景時，劃分平面通常選擇與場景中多邊形定義的平面重合。劃分平面的具體選擇和完成劃分過程的標準取決於BSP樹的目的。例如，在計算機圖形渲染中，場景被劃分，直到且除非BSP樹的每個節點僅包含可以以任意順序渲染的多邊形。當實現背面剔除時，因此每個節點都包含一組凸多邊形，而當渲染雙面多邊形時，BSP樹的每個節點僅包含單個平面中的多邊形。在碰撞檢測或光線追蹤中，場景可以細分為一些易於進行碰撞或光線相交測試的基元。
生成
BSP樹的典型實現是使用畫家演算法渲染多邊形（即雙面多邊形，即沒有背面剔除）。每個多邊形都指定了一個正面和一個背面，可以任意選擇，並且僅影響樹的結構，而不影響所需的結果。這樣的樹是從場景中所有多邊形的未排序列表構建的。從該多邊形列表構建BSP樹的遞迴演算法是
- 從列表中選擇一個多邊形A。
- 在BSP樹中構建一個節點N，並將A新增到該節點的多邊形列表中。
- 對於列表中的每個其他多邊形
- 如果該多邊形完全位於包含A的平面的前面，則將該多邊形移動到A前面的節點列表中。
- 如果該多邊形完全位於包含A的平面的後面，則將該多邊形移動到P後面的節點列表中。
- 如果該多邊形與包含A的平面相交，則將其分成兩個多邊形，並將它們移動到分別位於P後面和前面的多邊形列表中。
- 如果該多邊形位於包含A的平面內，則將其新增到節點N的多邊形列表中。
- 將此演算法應用於位於A前面的多邊形列表。
- 將此演算法應用於位於A後面的多邊形列表。
更新於： 2020年1月8日
1K+ 瀏覽量
廣告