空間資料結構我這個是專案中用來解決一些問題，包括在引擎中的場景管理！做了一個ppt來演講，所以地下有的直接就用ppt的內容或者截圖~
二維下使用四叉樹、Kd-tree等等在三維下使用八叉樹、bvh-tree、BSP-tree
BVH-tree在動態場景下使用（游戲使用的最多）；Oc-tree八叉樹是對于室外大場景來說的；BSP-tree是對于室內場景；
用途：場景管理、碰撞檢測、LOD、光線追蹤、 視椎體面剔除、幾何加速；
KD-tree（以光追為例）
其每次將空間劃分為兩部分，且劃分依次沿著x-axis，y-axis，z-axis，即如圖中所示，第一次橫著將2維空間分為上下，第二次再豎著將上下兩個子空間分別劃分為左右部分，依次遞回劃分，終止條件與八叉樹類似，但是是以空間劃分為依據；
回圈以下步驟：
1 依次沿著x-axis,y-axis,z-axis劃分，使得空間被劃分的更加平衡
2 劃分的位置由空間中三角面的分布決定，具體細節不展開
3 葉子節點存盤對應空間的所有物體或三角面資訊，中間節點僅存盤指標指向兩個子空間
4 當劃分空間太小或是子空間內只有少量三角形則停止劃分
區別：直接對空間進行劃分，都是二分空間！比如先左右劃分當前場景，再對子場景進行上下的劃分
優點：
利用KD-Tree的結構來構建AABB的好處是倘若光線與哪一部分空間不相交，那么則可以省略該部分空間所有子空間的判斷程序，在原始的純粹的AABB之上更進一步提升了加速效率，
缺點：
缺點是判斷包圍盒與三角面的是否相交較難，因此劃分的程序不是那么想象的簡單，其次同一個三角面可能被不同的包圍盒同時占有，這兩個不同包圍盒內的葉節點會同時存盤這一個三角形面
近十年來 用的比較少；
層次包圍盒樹 (Bounding Volume Hierarchy Based On Tree)
不再以空間作為劃分依據，而是從物件的角度考慮，即三角形面（主要是應用于動態場景）
層次包圍盒樹（BVH樹）是一棵多叉樹，用來存盤包圍盒形狀，它的根節點代表一個最大的包圍盒，其多個子節點則代表多個子包圍盒，此外為了統一化層次包圍盒樹的形狀，它只能存盤同一種包圍盒形狀， 演算法核心大概：形狀的位移/旋轉/伸縮更新對應的葉節點，然后一級一級更新上面的節點，使它們的包圍體包住子節點， 構造時間復雜度只有O(NlogN)，
區別：利用了Bounding box（AABB）從物體來開始劃分
**優點：**現代用的最多
1、每次劃分一般選擇最長的那一軸劃分，假設是x軸，那么劃分點選擇所有三角面的重心坐標在x坐標上的中位數進行劃分，如此便能保證劃分的三角形左右兩邊三角形數量盡可能差不多，當然也就使得樹形結構建立的更加平衡，深度更小，平均搜索次數更少，提高了效率，這些都是資料結構的知識，相信大家掌握的都不錯，就不多贅述了，
2、與KD-Tree一樣，中間節點不存盤物體三角面資訊，只在葉節點中存盤，終止條件可設定為當前包圍盒內三角形數量足夠少 （e.g. 5個）
四叉樹與八叉樹：
二維使用四叉樹、
三維是使用的八叉樹（室外大場景）為了防止滿樹，優化需要線性八叉樹（tree本質上就是陣列）
遞回分割立方體
-
F: 子立方體被場景內容填充滿內容標記為F(full)該子立方體不再被分割；
-
E:子立方體沒有場景內容標記為E(empty)該子立方體不再被分割；
-
葉子節點是F或E;（缺點）
松散四叉樹/八叉樹：減少邊界問題
解決四叉樹/八叉樹一個問題，物體有可能在邊界處來回（即在A象限也在B象限），從而導致物體總是在切換節點，從而不得不斷更新四叉樹/八叉樹，除此之外較小的物體可能因為其特殊位置被存盤到一個具有非常大的包圍盒體積的八叉樹節點中，
在《Game Programming
Gems》中該問題被描述為層次劃分程序中產生的“粘性（Sticky）”區域，較小的物體卻保持在樹的較高層次，降低了劃分的效率
而松散四叉樹/八叉樹正是解決這種邊界問題的一種方式：
- 首先它定義一個節點有入口邊界(inner boundary)，出口邊界(outerboundary)，
- 判定一個物體現在在哪個節點
- 若物體還沒添加進四叉樹/八叉樹，則檢測現在位于哪個節點的入口邊界內;
- 若物體先前已經存在于某個節點，則先檢測現在是否越出該節點的出口邊界，若越出再檢測位于哪個節點的入口邊界內，
在非松散的四叉樹/八叉樹中，入口邊界和出口邊界是一樣的，而松散四叉樹/八叉樹的松散，是指出口邊界比入口邊界要稍微寬些（各節點的出口邊界也會發生部分重疊，松散比較符合這種描述），從而使節點不容易越過出口邊界，減少了物體切換節點的次數，
隨之而來一個問題就是，如何定義出口邊界的長度，因為太短會退化成正常四叉樹/八叉樹，太長又可能會導致節點存盤冗余的物體，而在一篇關于松散四叉樹/八叉樹的論文里，實驗表明出口邊界長度為入口邊界2倍時可以表現得很好，
線性八叉樹：
BSP樹（Binary Space Partitioning Tree）：二叉空間分割
在游戲工業算是老功臣了，第一次被應用用是在1993年的商業游戲《DOOM》上，可是隨時渲染硬體的進步，基于BSP樹的渲染慢慢淘汰，但是即使在今天，BSP仍是在其他分支（引擎編輯器）不可或缺的一個重要資料結構，
（用在室內場景）用空間超平面，遞回的將空間分割為凸多面體，用二叉樹表示被分割的的空間（AVL樹），場景中的平面都有前平面與后平面（平面法向量的為前平面）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/336323.html
標籤：其他
上一篇：二十一天——打卡第三天