实验四基于BSP技术的室内场景渲染和碰撞检测

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）BSP原理Ø 顺序判定BS

2、P：二叉空间分割。用若干平板，每块平板可将场景分成两部分，以这样的方式可以描述整个空间的形态。如果我们为每个板子都设定过其正负面，那么我们就可以很轻松的得到一棵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个面组成的，如果所有的面都朝向盒子的内部，那么我们可以说盒子是一个“凸多边形”，如果不是都朝向盒子的内部，那么盒子就不是“凸多边形”。         

5、0;                                        图1.2下面让我们看一下如何确定一个图元集合是否是一个“凸多边形”，伪算法如下：（1）函数CLASSIFY-POIN

6、T参数:Polygon  确定一个3D空间中点相对位置的参考多边形。Point  待确定的3D空间中的点。返回值:点位于多边形的哪一边。功能:确定一个点位于被多边形定义的面的哪一边。CLASSIFY-POINT (Polygon, Point)Sidevalue = Polygon.Normal * Point if (Sidevalue = Polygon.Distance)then return COINCIDINGelse

7、0;if (Sidevalue < Polygon.Distance)then return BEHINDelse return INFRONT（2）函数 POLYGON-INFRONT参数:Polygon1  用来确定其它多边形是否在其“前面”的多边形。Polygon2  检测是否在第一个多边形“前面”的多边形。返回值:第二个多边形是否在第一个多边形的“前面”。功能:检测第二个多边形的每一个顶点是否在第一个多边形的“前面”。POLYGON-INFRONT (

8、Polygon1, Polygon2)for each point p in Polygon2if (CLASSIFY-POINT (Polygon1, p) <> INFRONT)then return falsereturn true（3）函数 IS-CONVEX-SET参数:PolygonSet  用来检测是否为“凸多边形”的图元集合。返回值:集合是否为“凸多边形”。功能:相对于集合中的其它多边形检查每一个多

9、边形，看是否位于其它多边形的“前面”，如果有任意两个多边形不满足这个规则，那么这个集合不为“凸多边形”。IS-CONVEX-SET (PolygonSet)for i = 0 to PolygonSet.Length ()for j = 0 to PolygonSet.Length ()if(i != j && not POLYGON-INFRONT(PolygonSeti, Polygon

10、Setj)then return falsereturn true在函数POLYGON-INFRONT中并没有进行对称的比较，这意味着如果多边形A位于多边形B的“前面”你并不能想当然的认为多边形B一定位于多边形B的“前面”。下面的例子简单的显示了这一点。                        图1.3在图1.3中我们可以看到多边形

11、1位于多边形2的“前面”，这是因为顶点p3、p4位于多边形2的“前面”，而多边形2却没有位于多边形1的“前面”，因为顶点p2位于多边形1的“后面”。对于一个BSP层次树来说可以用下面结构来定义：class BSPTreeBSPTreeNode RootNode / 树的根节点class BSPTreeNodeBSPTree Tree / 接点所属的层次树BSPTreePolygon Divider / 位于两个子树之间的多边形BSPTreeNode *RightChild&#

12、160;/ 节点的右子树BSPTreeNode *LeftChild / 节点的左子树BSPTreePolygon PolygonSet / 节点中的多边形集合class BSPTreePolygon3DVector Point1 / 多边形的顶点13DVector Point3 / 多边形的顶点23DVector Point3 / 多边形的顶点3现在你可以看见每一个多边形由3个顶点来定义，这是因为硬件加速卡使用三角形来对多边

13、形进行渲染。将多边形集合分割为更小的子集合有很多方法，例如你可以任意选择空间中的一个面然后用它来对空间中的多边形进行分割，把位于分割面正面的多边形保存到右子树中而位于反面的多边形保存到左子树中。使用这个方法的缺点非常明显，那就是如果想选择一个将空间中的多边形分割为两个相等的子集合的面非常困难，这是因为在场景中有无数个可选择的面。如何在集合中选择一个最佳的分割面呢？下面我将对这个问题给出一个比较适当的解决方案。我们现在已经有了一个函数POLYGON-INFRONT，它的功能是确定一个多边形是否位于其它多边形的正面。现在我们要做的是修改这个函数，使它也能够确定一个多边形是否横跨过其它多边形定义的分

14、割面。算法如下：（4）函数 CALCULATE-SIDE参数 :Polygon1  确定其它多边形相对位置的多边形。Polygon2  确定相对位置的多边形。返回值:多边形2位于多边形1的哪一边功能:通过第一个多边形对第二个多边形上的每一个顶点进行检测。如果所有的顶点位于第二个多边形的正面，那么多边形2被认为位于多边形1的“前面”。如果第二个多边形的所有顶点都位于第一个多边形的反面，那么多边形2被认为位于多边形1的“后面”。如果第二个多边形的所有顶点位于第一个多边形之上，那么多边形2被认为位于多边形1的内部。最后一种可能是所有的顶点即

15、位于正面有位于反面，那么多边形2被认为横跨过多边形1。CALCULATE-SIDE (Polygon1, Polygon2)NumPositive = 0, NumNegative = 0for each point p in Polygon2if (CLASSIFY-POINT (Polygon1, p) = INFRONT)then NumPositive = NumPositive 

16、;+ 1if (CLASSIFY-POINT (Polygon1, p) = BEHIND)then NumNegative = NumNegative + 1if (NumPositive > 0 && NumNegative = 0)then return INFRONTelse if(NumPositive = 0 &&a

17、mp; NumNegative > 0)then return BEHINDelse if(NumPositive = 0 && NumNegative = 0)then return COINCIDINGelse return SPANNING上面的算法也给我们解答了一个问题，当一个多边形横跨过分割面时如何进行处理，上面的算法中将多边形分割为两个多边形，这样就解决了画家算法中的两个问题：循环覆盖和多边形相交。下面

18、的图形显示了多边形如何进行分割的。             图1.4如图1.4所示，多边形1为分割面，而多边形2横跨过多边形1，如图右边所示，多边形被分割为2、3两部分，多边形2位于分割面的“前面”而多边形3位于分割面的“后面”。当建立一个BSP树时，首先需要确定的问题是如何保证二叉树的平衡，这意味着对于每一个叶节点的分割深度而言不能有太大的差异，同时每一个节点的左、右子树需要限制分割的次数。这是因为每一次的分割都会产生新的多边形，如果在建立BSP树时产生太多的多边

19、形的话，在图形加速卡对场景渲染时会加重渲染器的负担，从而降低帧速。同时一个不平衡的二叉树在进行遍历时会耗费许多无谓的时间。因此我们需要确定一个合理的分割次数以便于获得一个较为平衡的二叉树，同时可以减少新多边形的产生。下面的代码显示了如何通过循环多边形集合来获得最佳的分割多边形。（5）函数 CHOOSE-DIVIDING-POLYGON参数:PolygonSet  用于查找最佳分割面的多边形集合。返回值:最佳的分割多边形。功能:对指定的多边形集合进行搜索，返回将其分割为最佳子集合的多边形。如果指定的集合是一个“凸多边形”则返回。CHOOSE-DIVIDING-POL

20、YGON (PolygonSet)if (IS-CONVEX-SET (PolygonSet)then return NOPOLYGONMinRelation = MINIMUMRELATIONBestPolygon = NOPOLYGONLeastSplits = INFINITYBestRelation = 0循环查找集合的最佳分割面。while(BestPolygon = NOPOLYGON)for each 多边形P1

21、 in PolygonSetif (多边形P1在二叉树建立过程中没有作为分割面)计算被当前多边形定义的分割面的正面、反面和横跨过分割面的多边形的数量。NumPositive = 0, NumNegative = 0, NumSpanning = 0for each 多边形P2 in PolygonSet except P1value = CALCULATE-SIDE(P1, P2)if(value

22、 = INFRONT)NumPositive = NumPositive + 1else if(value = BEHIND)NumNegative = NumNegative + 1else if(value = SPANNING)NumSpanning = NumSpanning + 1计算被当前多边形分割的两个子集合的多边形数量的比值。if (NumPositive &l

23、t; NumNegative)Relation = NumPositive / NumNegativeelseRelation = NumNegative / NumPositive比较由当前多边形获得的结果。如果当前多边形分割了较少的多边形同时分割后的子集合比值可以接受的话，那么保存当前的多边形为新的候选分割面。如果当前多边形和最佳分割面一样分割了相同数量的多边形而分割后的子集合比值更大的话，将当前多边形作为新的候选分割面。if (Relation > MinRela

24、tion &&(NumSpanning < LeastSplits |(NumSpanning = LeastSplits &&Relation > BestRelation)BestPolygon = P1LeastSplits = NumSpanningBestRelation = Relation通过除以一个预先定义的常量来减少可接受的最小比值。MinRelation = Mi

25、nRelation / MINRELATIONSCALEreturn BestPolygon四、实验结果五、实验心得通过本次实验主要目的在于掌握BSP的原理并熟悉Ogre中基于BSP技术的室内场景渲染的使用方法。BSP原理可概括为：建立BSP Trees的最初想法是获得一个图元的集合，这个集合是场景的一部分，然后分割这个图元集合为更小的子集合，必须注意子集合必须为“凸多边形”。这意味着子集合中任一个多边形都位于相同集合中其它多边形的“前面”。BSP的出现解决了遮挡判定和可见物筛选两个问题，硬件ZBuffer出现后，可见物筛选成为重中之重；而对于可见物筛选除了视锥裁

26、剪外，还可通过Portal和PVS技术来实现并了解各个技术的优缺点，Portal复杂，PVS简单；本次实验对BSP的渲染流程也有了一定的认识，对Ogre知识的学习还需强化。六、主要代码/BSP.h#ifndef _BSP_H_#define _BSP_H_#include "SdkSample.h"#include "FileSystemLayer.h"#if OGRE_PLATFORM = OGRE_PLATFORM_APPLE | OGRE_PLATFORM = OGRE_PLATFORM_IPHONE#include "macUtils.

27、h"#endifusing namespace Ogre;using namespace OgreBites;class _OgreSampleClassExport Sample_BSP : public SdkSamplepublic:Sample_BSP()mInfo"Title" = "BSP"mInfo"Description" = "A demo of the indoor, or BSP (Binary Space Partition) scene manager. ""Also

28、demonstrates how to load BSP maps from Quake 3."mInfo"Thumbnail" = "thumb_bsp.png"mInfo"Category" = "Geometry"StringVector getRequiredPlugins()StringVector names;names.push_back("BSP Scene Manager");return names;protected:void locateResources()/

29、 load the Quake archive location and map name from a config fileConfigFile cf;cf.load(mFSLayer->getConfigFilePath("quakemap.cfg");mArchive = cf.getSetting("Archive");mMap = cf.getSetting("Map");#if OGRE_PLATFORM = OGRE_PLATFORM_APPLE | OGRE_PLATFORM = OGRE_PLATFORM_I

30、PHONE / OS X does not set the working directory relative to the app, / In order to make things portable on OS X we need to provide / the loading with it's own bundle path location if (!Ogre:StringUtil:startsWith(mArchive, "/", false) / only adjust relative dirs mArchive = Ogre:String(O

31、gre:macBundlePath() + "/" + mArchive);#endif / add the Quake archive to the world resource groupResourceGroupManager:getSingleton().addResourceLocation(mArchive, "Zip",ResourceGroupManager:getSingleton().getWorldResourceGroupName(), true);void createSceneManager()mSceneMgr = mRoo

32、t->createSceneManager("BspSceneManager"); / the BSP scene manager is required for this samplevoid loadResources()/* NOTE: The browser initialises everything at the beginning already, so we use a 0 init proportion.If you're not compiling this sample for use with the browser, then lea

33、ve the init proportion at 0.7. */mTrayMgr->showLoadingBar(1, 1, 0);/ associate the world geometry with the world resource group, and then load the groupResourceGroupManager& rgm = ResourceGroupManager:getSingleton();rgm.linkWorldGeometryToResourceGroup(rgm.getWorldResourceGroupName(), mMap, m

34、SceneMgr);rgm.initialiseResourceGroup(rgm.getWorldResourceGroupName();rgm.loadResourceGroup(rgm.getWorldResourceGroupName(), false);mTrayMgr->hideLoadingBar();void unloadResources()/ unload the map so we don't interfere with subsequent samplesResourceGroupManager& rgm = ResourceGroupManager:getSingleton();rgm.unloadResourceGroup(rgm.getWorldResourceGroupName();rgm.removeResourceLocation(m