新人补钙系列教程之:3D理论 - 二进制空间分割(BSP)树
1. 什么是BSP树
BSP算法的初始数据是一个多边形集,BSP在预处理的时候先在多边形集中选取一个多边形作为支持平面,然后根据这个平面将集合划分成两个部分,每个部分是一个新的子节点,递归进行该过程,直到每个子节点中的多边形都构成一个凸区域(最小凸边型),每个区域是一个叶节点,或成为cell,然后算法预计算在每个区域中可以见到哪些区域,得到PVS(潜在可见集)。
<IGNORE_JS_OP style="WORD-WRAP: break-word; WHITE-SPACE: normal; TEXT-TRANSFORM: none; WORD-SPACING: 0px; COLOR: rgb(51,51,51); FONT: 14px/21px Tahoma, Helvetica, SimSun, sans-serif; ORPHANS: 2; WIDOWS: 2; LETTER-SPACING: normal; BACKGROUND-COLOR: rgb(255,255,255); TEXT-INDENT: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px">
BSP可以说是八叉树的一般化
每个节点都是一条直线.所有在直线左边的东东都在它的左子树上,所有在它右边的东东都在它的右子树上.
<IGNORE_JS_OP style="WORD-WRAP: break-word; WHITE-SPACE: normal; TEXT-TRANSFORM: none; WORD-SPACING: 0px; COLOR: rgb(51,51,51); FONT: 14px/21px Tahoma, Helvetica, SimSun, sans-serif; ORPHANS: 2; WIDOWS: 2; LETTER-SPACING: normal; BACKGROUND-COLOR: rgb(255,255,255); TEXT-INDENT: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px">
好,我们用BSP树来想象一幅画面.
假设玩家站在D房间里面向屏幕右方,代号为点'x'
<IGNORE_JS_OP style="WORD-WRAP: break-word; WHITE-SPACE: normal; TEXT-TRANSFORM: none; WORD-SPACING: 0px; COLOR: rgb(51,51,51); FONT: 14px/21px Tahoma, Helvetica, SimSun, sans-serif; ORPHANS: 2; WIDOWS: 2; LETTER-SPACING: normal; BACKGROUND-COLOR: rgb(255,255,255); TEXT-INDENT: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px">
我们从树的顶端直线 f 开始.我们站在直线 f 的右边,所以我们向树的左子
树进行下去.这是因为我们想最先画最远的多边形.
我们来到了最左的节点.请在笔记本上记下节点上的东东--"a,c"
当我们不能再往下时,回到父节点.现在回到了根节点,我们还不能马上去右子树.
首先,我们看见了 f 面--写在这个节点上的.我们已经在我们列出的表上得到了
处在它后面的所有东东,我们还将看见它前面的东东,但是我们必须先把它记入我
们的表中.注意,f 面有两个表面--f' 和 f".既然我们已经知道我们处在直线 f
的右边,当然就只能看到它的右表面--所以我们在笔记本上记下 f"( 右面 ).现在本子上
写着 a,c,f".
如果我们以这个次序来画这些墙,将得到正确的图象.建议你使用3D-buffer,这样速度要快的多.
下面是搜索 BSP 树的伪代码:
- struct BSP_tree
- {
- plane partition;
- list polygons;
- BSP_tree *front, *back;
- };
- 这个结构体定义在下面的讨论中将被一直使用。它[来源:GameRes.com]表示BSP树的一个接点,包含有一个分割平面,处于分割平面的多边形列表,以及指向子接点的指针。
- void Buld_BSP_Tree( BSP_tree *tree, list polygons )
- {
- polygon *root = polygons.Get_From_List();
- tree->partition = root->Get_Plane();
- tree->polygons.Add_To_List( root );
- list front_list, back_list;
- polygon *poly;
- while( ( poly = polygons.Get_From_List() ) != 0 )
- {
- int result = tree->partition.Classify_polygon(poly);
- switch( result )
- {
- case COINCIDENT: // 共面
- tree->polygons.Add_To_List(poly);
- break;
- case IN_BACK_OF:
- back_list.Add_To_List(poly);
- break;
- case IN_FRONT_OF
- front_list.Add_To_List(poly);
- break;
- case SPANNING:
- polygon *front_piece, *back_piece;
- split_Polygon( poly, tree->partition, front_piece, back_piece );
- back_list.Add_To_List( back_piece );
- front_list.Add_To_List( front_piece );
- break;
- }
- }
- if( !front_list.Is->Empty_List() )
- {
- tree->front = new BSP_tree;
- Build_BSP_Tree( tree->front, front_list );
- }
- if( !back_list->Is_Empty_List() )
- {
- tree->back = new BSP_tree;
- Build_BSP_Tree( tree->back, back_list );
- }
- }
- Buld_BSP_Tree函数根据以上说明的步骤递归地建立BSP树。它使用输入的多边形列表中的第一个多边形所在的平面作为分割平面,假定此列表中的每一个多边形都为凸多边形。
复制代码
代码来源于网络
最新文章
- 13.final关键字
- Golang 文件服务器小结
- Yii2 数据操作Query Builder(转)
- HDU3395 Special Fish(最大费用任意流)
- jQuery源代码阅读之一——jQuery总体结构及jQuery构造函数
- 忘记了MariaDB root密码的解决办法
- POJ 2528 Mayor&#39;s posters(线段树区间染色+离散化或倒序更新)
- 评价软件_搜狗输入法(pc端)
- Unity3D与iOS的交互设计<;ViewController 的跳转>;
- Binding在WPF中的使用
- 域名解析 URL转发
- Openjudge-计算概论(A)-分数求和
- 线性代数-矩阵-【2】矩阵生成 C和C++实现
- Android的四个基本概念(线程通信和GLSurfaceView)
- jenkins配置演示
- 【php-fpm】启动PHP报错ERROR: [pool www] cannot get uid for user &#39;apache&#39;
- Java 新建excle文件并填充模版内容
- CBV源码解析
- UVA 11584 Partitioning by Palindromes (字符串区间dp)
- cakephp引入其他控制器封装方法
热门文章
- hdu 2516 取石子游戏 (博弈)
- 了解腾讯开源的多渠道打包技术 VasDolly源码解析
- Educational Codeforces Round 22 E. Army Creation
- hashCode()方法和equals方法的重要性。
- ASP.NET Identity 使用 RoleManager 进行角色管理 (VS2013RC)
- linux精彩收集
- SQL Server 中使用 Try Catch 处理异常
- centos 安装使用smb
- python 向mysql插入数据
- 【linux高级程序设计】(第十三章)Linux Socket网络编程基础 4