Just a Computer Graphics Studio & My Life

Binary Space Partioning Tree英文簡稱為BSP Tree,二元空間分割樹,簡稱為二叉樹。它於1969年被Schumacker在文章《Study for Applying Computer-Generated Images to Visual Simulation》首次提出,並被ID公司第一次使用到FPS遊戲Doom中,Doom的推出獲得了空前的成功,不僅奠定了ID公司在FPS遊戲開發的宗師地位,也使BSP技術成為室內渲染的工業標準,從BSP產生到現在已經有30多年了,其間雖然產生了大量的室內渲染的算法,但卻無人能撼動它的地位,對於以摩爾定律發展的計算機業來說這不能不是一個奇蹟。

※為什麼使用BSP Tree

一個BSP Trees如同它的名字一樣是一個層次樹的結構,這個樹的葉節點保存了分割室內空間所得到的圖元集合。現在隨著硬體加速Z緩衝的出現,我們只需要用很小的代價就可以對空間中的圖元進行排序,但是在90年代初由於硬體的限制,使用BSP的主要原因是因為它可以對空間中的圖元進行排序來保證渲染圖元的順序是按照由後至前進行的,換句話說,Z值最小的物體總是最後被渲染。當然還有其他的算法可以完成這個功能,例如著名的畫家演算法,但是它與BSP比較起來速度太慢了,這是因為BSP通常對圖元排序是預先計算好的而不是在運行時進行計算。從某種意義上說BSP技術實際上是畫家算法的擴展,正如同BSP技術的原始設計一樣,畫家演算法也是使用由後至前的順序對場景中的物體進行渲染。

產生BSP tree的步驟:

Step 1: Make a list of all the walls.
Step 2: Choose one of the walls, “the splitter wall" to split up the space into two parts, P1 and P2.
Step 3: Put all of the walls that are completely in front of the splitter wall into one list, called “front".
Step 4: Put all of the walls that are completely in back of the splitter wall into another list called “back".
Step 5: If the splitter wall intersects any of the walls, split that wall into two parts, putting the part of the wall in front of the splitter wall into the front list and the other part in the back list.
Note: for simplification, this algorithm doesn’t address walls that lie on the same line as the splitter wall.
Step 6: The splitter wall is placed in the bsp tree. The first wall simply becomes the root of the tree. Thereafter, the wall is placed in the bsp tree to the right of its parent wall if in the scene the wall is in front of the parent wall. The wall is placed in the bsp tree to the left of the parent wall if in the scene the wall is in back of the parent wall.
Step 7: Recursively split up the P1 space until you are left with one line segment only. Then recursively split up the P2 space until there is only one line segment remaining.

最後的繪出的場景。

俯視場景,分別標出牆的號碼。

第一次選擇C牆(從A-H任意選),F牆被分割為F1和F2牆。在C牆前面的有F1、G、H牆,而在後面的有A、B、D、E、F2牆。

第二次選擇G牆(從1、G、H牆任意選)。在G牆前面的有F1牆,而在後面有H牆。

依上述類推,右子樹為前方,左子樹為後方,最後產生的BSP樹。BSP樹並不唯一,因為每次牆都可以任選。

參考:Binary Space Partitioning、WiKi – Binary Space PartitioningBSP技術詳解

Advertisements

Comments on: "二元空間分割樹 (Binary Space Partitioning Tree)" (4)

  1. 天佑我圖學 said:

    第一段的 Shumacker 好像是 “Schumacker" 少了一個 c

    喜歡

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

    喜歡

  3. […] 這篇來講使用二元空間分割樹 (Binary Space Partitioning Tree)如何來畫一個場景,接續我撰寫的二元空間分割樹 (Binary Space Partitioning Tree)。 […]

    喜歡

發表留言

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s

標籤雲

%d 位部落客按了讚: