Just My Life & My Work

二元空間分割樹 (BSP Tree)

計算機圖學中已經有提過二元空間分割樹 (Binary space partitioning)二元空間分割樹2 (Binary space partitioning2),這裡以遊戲設計的角度談兩種方式來做二元空間分割樹對齊軸 (Axis-aligned)對齊多邊形 (Polygon-aligned)

二元空間分割樹 (BSP Tree)的建立是由使用平面來將空間一分為二,接著將幾何排序到兩個空間,如果空間有許多物件,可以遞迴繼續將空間一分為二。

對齊軸 (Axis-aligned)可以用以下兩張圖解釋:

場景中有五個物體,以平行軸的方式來切割空間,如上圖可以四條線(四個平面)來得到五個子空間

以切平面來當作內部節點,建立起二元空間分割樹,有此圖就可以很快地找到目標物體。遊戲設計教學書籍常見的應用是k-d tree

對齊多邊形 (Polygon-aligned)可以用以下兩張圖解釋:

場景有六道牆,以平行多邊形的方式來切割空間,如上圖可以三條線(三個平面)來得到四個子空間

以切平面來當作內部節點,建立起二元空間分割樹,有此圖就可以很快地找到目標物體。

參考:WiKi – Binary space partitioning、WiKi – k-d tree

廣告

隨意留個言吧:)~

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

標籤雲

%d 位部落客按了讚: