㈠ BSP是什麼
我還以為有人再問ASP的新動向BSP呢（B-Business)，原來仍然是討論圖形技術的程序員。
BSP是一種數據結構，用於基於空間劃分的索引方式，一般三維圖形應用利用它進行空間遮擋關系計算的加速，而二維圖形應用則利用它進行空間查詢。它的基本思路就是對空間進行逐級劃分形成二分樹狀結構。具體內容可以參考CloudWu的一篇簡介性文章，我把它貼出來。
- 信區: Programe .Bull編程討論(黃石)-------------------------------------
信件: 37 Sent Local 日期: 27 Nov 97 07:13:45
來自: Cloud Wu 已讀: 是 已回信 : 否
給: All 標記:
主題: BSP樹--製作3D Engine
------------------------------------------------------------------------------
... 這是一篇介紹BSP樹的文章,原文在我U/L的 UGRPG.ZIP 中,因為我的
... E文實在不怎麼樣,所以在只能在看過原文後,根據自己的理解寫一篇
... C文的(不是翻譯),如果有什麼BUG,請各位大蝦多多Debug. :)
BSP 樹
------
解釋BSP樹的運用,最好是從一個例子開始.設想一個很簡單的DOOM關卡的例子.
A---------------------------------a----------------------------------B
| | | |
| | y | |
d1 | | b1
| | f' | |
| | | |
| C--------------------f-----------------------D |
| | | | | |
| | | f" | | |
| d | | b |
| | | | | |
| | e" e e' g' g g" | |
d2 | | | | b2
| | | | | |
| | | | | |
| | E F | |
| | x | |
| | | |
G---------------------------------c----------------------------------H
----c1---- ----------------------c2-------------------- -----c3-----
這個關卡由一個屋子套在另一個屋子裡構成.玩家被封閉在矩形ABHG中.
先給出幾個定義.(如圖)
我們用矢量定義直線,所以
a = (A,B) e = (E,C) f = (C,D) g = (F,D)
當一個點在直線矢量方向的左邊時,我們稱點在直線的左邊.
因此,在這個例子里,a的左邊什麼也沒有;所有的東東都在它的右邊.注意這些
依賴與我們對a的定義,如果我們定義 a = (B,A) 則所有的東東都在a的左邊.
面是玩家看到的直線的一邊.例如牆e,就有兩個面(e'和e").不是所有的牆都有
兩個面 -- 如果玩家只能看見牆的一面,那麼這堵牆就只有一個面.
面是由矢量方向定義的,直線的兩個面分別被稱作左表面和右表面.
這個例子中的BSP樹是這樣的:
f
/ / \
/ a,d1,b1 e
/ / / d2,c1 g
/ / / c2 c3,b2
每個節點都是一條直線.所有在直線左邊的東東都在它的左子樹上,所有在它
右邊的東東都在它的右子樹上.
注意 d 面不是完全在 f 面的右邊或左邊.為了描述這種情況,我們把它分為
了兩個部分,一個部分放在左子樹,一部分放在右子樹.因而,我們必須產生新
的面來構造BSP樹.
我將在後面解釋BSP數是怎樣創建的.首先,我將給出使用BSP樹來產生一幅畫的方法.
假設玩家站在點'x',看著北方.
我們從樹的頂端直線 f 開始.我們站在直線 f 的右邊,所以我們向樹的左子
樹進行下去.這是因為我們想最先畫最遠的多邊形.
我們來到了最左的節點.請在筆記本上記下節點上的東東--"a,d1,b1".
當我們不能再往下時,回到父節點.現在回到了根節點,我們還不能馬上去右子樹.
首先,我們看見了 f 面--寫在這個節點上的.我們已經在我們列出的表上得到了
處在它後面的所有東東,我們還將看見它前面的東東,但是我們必須先把它記入我
們的表中.注意,f 面有兩個表面--f' 和 f".既然我們已經知道我們處在直線 f
的右邊,當然就只能看到它的右表面--所以我們在筆記本上記下 f".現在本子上
寫著 a,d1,b1,f".
注意,如果我們是看著南方(視線遠離 f 面),看不到 f 的任何一個面和 f 的那
一面後的所有東東.在這種情況下,我們就不必做前面這些.
現在我們向下到節點 e.我們在 e 的右邊,所以要往左子樹去,這樣便得到了一個
葉節點.現在把 d2,c1 記下來.
再回來,看看該記下 e 的哪一面.應該是 e'.現在筆記本上寫著
a,d1,b1,f",d2,c1,e'.
向右子樹,來到 g 節點.我們在左邊,所以向右得到 c3,b2,再回來,檢查 g (我
們在左邊,應為g'),去最後一個節點得到 c2,回溯,回溯,回溯,回到根節點,遍歷
完成.
最後筆記本上寫著:
a d1 b1 f" d2 c1 e' c3 b2 g' c2
如果我們以這個次序來畫這些牆,將得到正確的圖象.建議你使用3D-buffer而
不要用畫家演算法,這樣速度要快的多.
創建 BSP 樹
-----------
BSP樹完全是遞歸創建的.唯一的困難是知道何時該停止遞歸.應該注意到葉節
點將被整個放入表中--因此將一組平面放在一個葉節點上的充分條件是它們能
夠以任何次序畫出來而不致有錯.也就是說,無論玩家站在哪兒,這一組牆之間
都不會被別的擋住.
好吧,讓我們開始:選擇一個面 f (這個選擇相當隨便--最好是選一個面,它能
最少的分割其它面.當然,分割是不可避免的).分割 d 面和 b 面,因為它們被
直線 f 分開了.(用DOOM中的說法,去分割區域的線被稱為節點線 _nodeline_ )
然後把 f 左邊的東東放在左子樹,右邊也如此:
f
/ / / a,d1,b1 b2,c,d2,e,g
我們可以不再處理左子樹--因為牆 a,d1,b1 構成一個凸多邊形,從任意角度
看它們都互不重疊.然而在另一邊,平面 e 卻使得從特定點去觀察平面 d2 會
被其擋住,所以我們從 e 處分開,這就造成了平面 c 的分割,但是同樣被分割
的平面 a 卻不用被分割,這是因為 a 不在現在分析的平面中.
第二級 BSP 樹為:
f
/ / / a,d1,b1 e
/ / \
/ d2,c1 b2,c2,g
現在,c1 和 d2 從不重疊,顧而我們將它們作為另一個葉節點.下一步我們
從 g 處分開,將 c2 分成 c2 和 c3,剩下的節點都是葉節點.
下面這棵 BSP 樹的最簡單運用--再給一個例子來加深印象.考慮一下站在
y 點向北看的情況.因為看不到 f 面,你只用搜索左子樹.這樣馬上就得到
了需要的循序: a,d1,b1.
精華
----
如果我們在每個節點上為每個子樹定義一個特定空間,記錄子樹中的信息,
這樣我們就能以錐形視野比較這些信息將一些不可見的多邊形截掉(屏幕
左邊和右邊的東東)--如果它們不相交,這樣你就不必搜索整個子樹.DOOM
就是這樣做的,在一個巨大的 BSP 樹中用特定空間儲存了每一級的完整
(*entire*)信息.
下面是搜索 BSP 樹的偽代碼.函數 left() 當第二個輸入矢量在第一個輸
入矢量的左邊時返回 TRUE.這就是兩個矢量的點積,...
... Sorry,小D這一句不太明白
>This is a simple dot proct, and by pre-calculating the slope of the
>nodeline can be done with one multiply and one subtract.
vector player ; player's map position
; 玩家在地圖上的位置矢量
vector left_sightline ; vector representing a ray cast through
; the left-most pixel of the screen
; 描述發射到屏幕最左邊的光線的矢量
vector right_sightline ; the right-most pixel of the screen
; 描述發射到屏幕最右邊的光線的矢量
structure node
{
vector vertex1
vector vertex2
node left_subtree
node right_subtree
face left_face
face right_face
box bounding_box
bool terminal_node
face terminal_node_faces[lots]
}
recurse(node input)
if (cone defined by left and right sightlines does not intersect the node's
bounding box)
return
fi
if node.terminal_node
; terminal node - add faces to list
; 葉節點--將平面填入表中
add(node.terminal_node_faces)
return
fi
if left(vertex2-vertex1,player-vertex1)
; player is to the left of the nodeline
; 玩家在節點線的左邊
if not left(vertex2-vertex1,right_sightline)
; sight points right - we are looking at the face
; 視線指向右邊--我們正看著這個面
recurse(node.right_subtree)
add(node.left_face)
fi
; now go down the left subtree
; 現在向左子樹搜索
recurse(node.left_subtree)
else
; player is to the right of the nodeline
; 玩家在節點線的右邊
if left(vertex2-vertex1,left_sightline)
; sight points left - we are looking at the face
; 視線指向左邊--我們正看著這個面
recurse(node.left_subtree)
add(node.right_face)
fi
; now go down the right subtree
; 現在向右子樹搜索
recurse(node.right_subtree)
fi
return
end recurse
這不是正規的代碼--象數據結構之類的很多東東都沒寫. :)