《实验四：基于bsp技术的室内场景渲染和碰撞检测》由会员分享，可在线阅读，更多相关《实验四：基于bsp技术的室内场景渲染和碰撞检测（11页珍藏版）》请在金锄头文库上搜索。
1、实验四：基于 BSP 技术的室内场景渲染和碰撞检测姓名： 班级： 学号：一、实验目的掌握 BSP 的原理；熟悉 Ogre 中基于 BSP 技术的室内场景渲染的使用方法。二、实验仪器pc、visual studio 2010三、实验原理及过程/网上检索 BSP 相关技术/利用 Ogre 实现基于 BSP 技术的室内场景渲染描述程序实现时的思路包括对每个调用的 API 进行详细说明1、 BSP 相关技术（1）BSP 概述BSP Trees 英文全称为 Binary Space Partioning trees，二维空间分割树，简称为二叉树。包括：隐藏面的剔除；室内场景中光照运算；BSP 树的预渲染
2、。（2）BSP 原理 顺序判定BSP：二叉空间分割。用若干平板，每块平板可将场景分成两部分，以这样的方式可以描述整个空间的形态。如果我们为每个板子都设定过其正负面，那么我们就可以很轻松的得到一棵 BSP。在早期显卡上，由于没有硬件 ZBuffer，因此必须从后向前画。当代显卡由于其出色的 ZBuffer，因此如果从前向后渲染，由于后画的比较容易被遮挡而被 ZBuffer CUT 掉，反而效率更高。 筛选优化单单对场景进行顺序判定是不够的，场景中成千上万的三角形没有必要全部渲染，还需要经过筛选。 PVS除了视锥裁减外，BSP 可通过两种方式进行进一步的筛选优化。比较容易理解的是 Portal：凡
3、是入口看不见的，就是看不见的。Portal 的不足在于需要每一帧都进行重新计算，计算量较大；第二种办法就是潜在可见集合 PVS，在生成树的时候，同时就生成好了空间与空间之间的可见关系，这样的话，渲染时候只需要去查询这个 PVS 可见关系表就可以了。例如，当我当前处在 D 的时候，只有 BC 能通过 PVS 测试，因此 A 一开始就可以被 CUT。（3）BSP 渲染 BSP 的渲染流程：1）先获取摄像机所在叶子，并获得此叶子的 PVS 信息；2）从根节点开始；3）如果此节点仍然是节点，判断此节点的可见性，如果全部可见，此节点之下的所有节点全处理；如果全都不可见，中止判断，回到上级节点。4）部分可
4、见应看摄像机在节点分割平面的正面还是反面，如果在正面，则先处理（递归）正节点后处理反节点；如果在反面，则先处理反节点后处理正节点；5）如果此节点是叶子，判断 PVS，并将叶子之中包括的所有三角形进行渲染。2、程序实现思路及调用的相应 API 函数的详细说明如果多边形 A 的每一个顶点都位于由多边形 B 所组成的一个面的正面，那么可以说多边形 A 位于多边形B 的“前面 ”，参考左图。我们可以想象一下，一个盒子是由 6 个面组成的，如果所有的面都朝向盒子的内部，那么我们可以说盒子是一个“凸多边形”，如果不是都朝向盒子的内部，那么盒子就不是“凸多边形”。 图 1.2下面让我们看一下如何确定一个图元
5、集合是否是一个“凸多边形”，伪算法如下：（1）函数 CLASSIFY-POINT参数:Polygon 确定一个 3D 空间中点相对位置的参考多边形。Point 待确定的 3D 空间中的点。返回值:点位于多边形的哪一边。功能:确定一个点位于被多边形定义的面的哪一边。CLASSIFY-POINT (Polygon, Point)Sidevalue = Polygon.Normal * Pointif (Sidevalue = Polygon.Distance)then return COINCIDINGelse if (Sidevalue INFRONT)then return falseretu
6、rn true（3）函数 IS-CONVEX-SET参数:PolygonSet 用来检测是否为“凸多边形”的图元集合。返回值:集合是否为“凸多边形” 。功能:相对于集合中的其它多边形检查每一个多边形，看是否位于其它多边形的“前面”，如果有任意两个多边形不满足这个规则，那么这个集合不为“凸多边形”。IS-CONVEX-SET (PolygonSet)for i = 0 to PolygonSet.Length ()for j = 0 to PolygonSet.Length ()if(i != j & not POLYGON-INFRONT(PolygonSeti, PolygonSetj)th
7、en return falsereturn true在函数 POLYGON-INFRONT 中并没有进行对称的比较，这意味着如果多边形 A 位于多边形 B 的“ 前面”你并不能想当然的认为多边形 B 一定位于多边形 B 的“前面 ”。下面的例子简单的显示了这一点。图 1.3在图 1.3 中我们可以看到多边形 1 位于多边形 2 的“前面”，这是因为顶点 p3、p4 位于多边形 2 的“前面”，而多边形 2 却没有位于多边形 1 的“前面”，因为顶点 p2 位于多边形 1 的“后面”。对于一个 BSP 层次树来说可以用下面结构来定义：class BSPTreeBSPTreeNode RootNo
8、de / 树的根节点class BSPTreeNodeBSPTree Tree / 接点所属的层次树BSPTreePolygon Divider / 位于两个子树之间的多边形BSPTreeNode *RightChild / 节点的右子树BSPTreeNode *LeftChild / 节点的左子树BSPTreePolygon PolygonSet / 节点中的多边形集合class BSPTreePolygon3DVector Point1 / 多边形的顶点 13DVector Point3 / 多边形的顶点 23DVector Point3 / 多边形的顶点 3现在你可以看见每一个多边形由
9、3 个顶点来定义，这是因为硬件加速卡使用三角形来对多边形进行渲染。将多边形集合分割为更小的子集合有很多方法，例如你可以任意选择空间中的一个面然后用它来对空间中的多边形进行分割，把位于分割面正面的多边形保存到右子树中而位于反面的多边形保存到左子树中。使用这个方法的缺点非常明显，那就是如果想选择一个将空间中的多边形分割为两个相等的子集合的面非常困难，这是因为在场景中有无数个可选择的面。如何在集合中选择一个最佳的分割面呢？下面我将对这个问题给出一个比较适当的解决方案。我们现在已经有了一个函数 POLYGON-INFRONT，它的功能是确定一个多边形是否位于其它多边形的正面。现在我们要做的是修改这个函
10、数，使它也能够确定一个多边形是否横跨过其它多边形定义的分割面。算法如下：（4）函数 CALCULATE-SIDE参数 :Polygon1 确定其它多边形相对位置的多边形。Polygon2 确定相对位置的多边形。返回值:多边形 2 位于多边形 1 的哪一边功能:通过第一个多边形对第二个多边形上的每一个顶点进行检测。如果所有的顶点位于第二个多边形的正面，那么多边形 2 被认为位于多边形 1 的“前面”。如果第二个多边形的所有顶点都位于第一个多边形的反面，那么多边形 2 被认为位于多边形 1 的“后面”。如果第二个多边形的所有顶点位于第一个多边形之上，那么多边形 2 被认为位于多边形 1 的内部。最
11、后一种可能是所有的顶点即位于正面有位于反面，那么多边形2 被认为横跨过多边形 1。CALCULATE-SIDE (Polygon1, Polygon2)NumPositive = 0, NumNegative = 0for each point p in Polygon2if (CLASSIFY-POINT (Polygon1, p) = INFRONT)then NumPositive = NumPositive + 1if (CLASSIFY-POINT (Polygon1, p) = BEHIND)then NumNegative = NumNegative + 1if (NumPosi
12、tive 0 & NumNegative = 0)then return INFRONTelse if(NumPositive = 0 & NumNegative 0)then return BEHINDelse if(NumPositive = 0 & NumNegative = 0)then return COINCIDINGelse return SPANNING上面的算法也给我们解答了一个问题，当一个多边形横跨过分割面时如何进行处理，上面的算法中将多边形分割为两个多边形，这样就解决了画家算法中的两个问题：循环覆盖和多边形相交。下面的图形显示了多边形如何进行分割的。图 1.4如图 1.4
13、 所示，多边形 1 为分割面，而多边形 2 横跨过多边形 1，如图右边所示，多边形被分割为 2、3两部分，多边形 2 位于分割面的“前面”而多边形 3 位于分割面的“后面”。当建立一个 BSP 树时，首先需要确定的问题是如何保证二叉树的平衡，这意味着对于每一个叶节点的分割深度而言不能有太大的差异，同时每一个节点的左、右子树需要限制分割的次数。这是因为每一次的分割都会产生新的多边形，如果在建立 BSP 树时产生太多的多边形的话，在图形加速卡对场景渲染时会加重渲染器的负担，从而降低帧速。同时一个不平衡的二叉树在进行遍历时会耗费许多无谓的时间。因此我们需要确定一个合理的分割次数以便于获得一个较为平衡
14、的二叉树，同时可以减少新多边形的产生。下面的代码显示了如何通过循环多边形集合来获得最佳的分割多边形。（5）函数 CHOOSE-DIVIDING-POLYGON参数:PolygonSet 用于查找最佳分割面的多边形集合。返回值:最佳的分割多边形。功能:对指定的多边形集合进行搜索，返回将其分割为最佳子集合的多边形。如果指定的集合是一个“凸多边形”则返回。CHOOSE-DIVIDING-POLYGON (PolygonSet)if (IS-CONVEX-SET (PolygonSet)then return NOPOLYGONMinRelation = MINIMUMRELATIONBestPoly
15、gon = NOPOLYGONLeastSplits = INFINITYBestRelation = 0循环查找集合的最佳分割面。while(BestPolygon = NOPOLYGON)for each 多边形 P1 in PolygonSetif (多边形 P1 在二叉树建立过程中没有作为分割面)计算被当前多边形定义的分割面的正面、反面和横跨过分割面的多边形的数量。NumPositive = 0, NumNegative = 0, NumSpanning = 0for each 多边形 P2 in PolygonSet except P1value = CALCULATE-SIDE(P
16、1, P2)if(value = INFRONT)NumPositive = NumPositive + 1else if(value = BEHIND)NumNegative = NumNegative + 1else if(value = SPANNING)NumSpanning = NumSpanning + 1计算被当前多边形分割的两个子集合的多边形数量的比值。if (NumPositive MinRelation &(NumSpanning BestRelation)BestPolygon = P1LeastSplits = NumSpanningBestRelation = Relation通过除以一个预先定义的常量来减少可接受的最小比值。MinRelation = MinRelation / MINRELATIONSCALEreturn BestPolygon四、实验结果五、实验心得通过本次
