谁能告诉我'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 product, 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
fiif node.terminal_node
  ; terminal node - add faces to list
  ; 叶节点--将平面填入表中
  add(node.terminal_node_faces)
  return
fiif 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)
fireturn                                                                         end recurse这不是正规的代码--象数据结构之类的很多东东都没写. :)... 希望有人看了好文章后,也介绍给大家,毕竟看E文狠头痛 :(
>这封信如果可以发在 BBSGAME(or GAMEMAKE) 区,请转载.... 江    ┏━┓┏    ┏━┓      ┳━┓吴 BBS ID: Cloud Wu
... 城 浪 ┃    ┃    ┃  ┃┃  ┃┃  ┃云 E-mail: [email protected]
...    子 ┗━┛┗━┛┗━┛┗━┛┻━┛洋 http://www.nease.net/~cloudwu-!- 蓝波-快信/DOS v2.30
 * Origin: Jingle BBS 武汉劲捷电子信息站 (027)364-8668,363-6678  (6:663/2)