实验四基于BSP技术的室内场景渲染和碰撞检测.docx
《实验四基于BSP技术的室内场景渲染和碰撞检测.docx》由会员分享，可在线阅读，更多相关《实验四基于BSP技术的室内场景渲染和碰撞检测.docx（17页珍藏版）》请在冰点文库上搜索。
实验四基于BSP技术的室内场景渲染和碰撞检测
实验四：
基于BSP技术的室内场景渲染和碰撞检测
姓名：
班级：
学号：
一、实验目的
掌握BSP的原理；
熟悉Ogre中基于BSP技术的室内场景渲染的使用方法。
二、实验仪器
pc、visualstudio2010
三、实验原理及过程
//网上检索BSP相关技术
//利用Ogre实现基于BSP技术的室内场景渲染描述程序实现时的思路包括对每个调用的API进行详细说明
1、BSP相关技术
（1）BSP概述
BSPTrees英文全称为BinarySpacePartioningtrees，二维空间分割树，简称为二叉树。
包括：
隐藏面的剔除；室内场景中光照运算；BSP树的预渲染。
（2）BSP原理
Ø顺序判定
BSP：
二叉空间分割。
用若干平板，每块平板可将场景分成两部分，以这样的方式可以描述整个空间的形态。
如果我们为每个板子都设定过其正负面，那么我们就可以很轻松的得到一棵BSP。
在早期显卡上，由于没有硬件ZBuffer，因此必须从后向前画。
当代显卡由于其出色的ZBuffer，因此如果从前向后渲染，由于后画的比较容易被遮挡而被ZBufferCUT掉，反而效率更高。
Ø筛选优化
单单对场景进行顺序判定是不够的，场景中成千上万的三角形没有必要全部渲染，还需要经过筛选。
ØPVS
除了视锥裁减外，BSP可通过两种方式进行进一步的筛选优化。
比较容易理解的是Portal：
凡是入口看不见的，就是看不见的。
Portal的不足在于需要每一帧都进行重新计算，计算量较大；
第二种办法就是潜在可见集合PVS，在生成树的时候，同时就生成好了空间与空间之间的可见关系，这样的话，渲染时候只需要去查询这个PVS可见关系表就可以了。
例如，当我当前处在D的时候，只有BC能通过PVS测试，因此A一开始就可以被CUT。
（3）BSP渲染
ØBSP的渲染流程：
1）先获取摄像机所在叶子，并获得此叶子的PVS信息；
2）从根节点开始；
3）如果此节点仍然是节点，判断此节点的可见性，如果全部可见，此节点之下的所有节点全处理；如果全都不可见，中止判断，回到上级节点。
4）部分可见应看摄像机在节点分割平面的正面还是反面，如果在正面，则先处理（递归）正节点后处理反节点；如果在反面，则先处理反节点后处理正节点；
5）如果此节点是叶子，判断PVS，并将叶子之中包括的所有三角形进行渲染。
2、程序实现思路及调用的相应API函数的详细说明
如果多边形A的每一个顶点都位于由多边形B所组成的一个面的正面，那么可以说多边形A位于多边形B的“前面”，参考左图。
我们可以想象一下，一个盒子是由6个面组成的，如果所有的面都朝向盒子的内部，那么我们可以说盒子是一个“凸多边形”，如果不是都朝向盒子的内部，那么盒子就不是“凸多边形”。
图1.2
下面让我们看一下如何确定一个图元集合是否是一个“凸多边形”，伪算法如下：
（1）函数CLASSIFY-POINT
参数:
Polygon – 确定一个3D空间中点相对位置的参考多边形。
Point – 待确定的3D空间中的点。
返回值:
点位于多边形的哪一边。
功能:
确定一个点位于被多边形定义的面的哪一边。
CLASSIFY-POINT （Polygon, Point）
Sidevalue = Polygon.Normal * Point
if （Sidevalue == Polygon.Distance）
then return COINCIDING
else if （Sidevalue < Polygon.Distance）
then return BEHIND
else return INFRONT
（2）函数 POLYGON-INFRONT
参数:
Polygon1 – 用来确定其它多边形是否在其“前面”的多边形。
Polygon2 – 检测是否在第一个多边形“前面”的多边形。
返回值:
第二个多边形是否在第一个多边形的“前面”。
功能:
检测第二个多边形的每一个顶点是否在第一个多边形的“前面”。
POLYGON-INFRONT （Polygon1, Polygon2）
for each point p in Polygon2
if （CLASSIFY-POINT （Polygon1, p） <> INFRONT）
then return false
return 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（PolygonSet[i], PolygonSet[j]））
then return false
return true
在函数POLYGON-INFRONT中并没有进行对称的比较，这意味着如果多边形A位于多边形B的“前面”你并不能想当然的认为多边形B一定位于多边形B的“前面”。
下面的例子简单的显示了这一点。
图1.3
在图1.3中我们可以看到多边形1位于多边形2的“前面”，这是因为顶点p3、p4位于多边形2的“前面”，而多边形2却没有位于多边形1的“前面”，因为顶点p2位于多边形1的“后面”。
对于一个BSP层次树来说可以用下面结构来定义：
class BSPTree
{
BSPTreeNode RootNode // 树的根节点
}
class BSPTreeNode
{
BSPTree Tree // 接点所属的层次树
BSPTreePolygon Divider // 位于两个子树之间的多边形
BSPTreeNode *RightChild // 节点的右子树
BSPTreeNode *LeftChild // 节点的左子树
BSPTreePolygon PolygonSet[] // 节点中的多边形集合
}
class BSPTreePolygon
{
3DVector Point1 // 多边形的顶点1
3DVector Point3 // 多边形的顶点2
3DVector Point3 // 多边形的顶点3
}
现在你可以看见每一个多边形由3个顶点来定义，这是因为硬件加速卡使用三角形来对多边形进行渲染。
将多边形集合分割为更小的子集合有很多方法，例如你可以任意选择空间中的一个面然后用它来对空间中的多边形进行分割，把位于分割面正面的多边形保存到右子树中而位于反面的多边形保存到左子树中。
使用这个方法的缺点非常明显，那就是如果想选择一个将空间中的多边形分割为两个相等的子集合的面非常困难，这是因为在场景中有无数个可选择的面。
如何在集合中选择一个最佳的分割面呢？
下面我将对这个问题给出一个比较适当的解决方案。
我们现在已经有了一个函数POLYGON-INFRONT，它的功能是确定一个多边形是否位于其它多边形的正面。
现在我们要做的是修改这个函数，使它也能够确定一个多边形是否横跨过其它多边形定义的分割面。
算法如下：
（4）函数 CALCULATE-SIDE
参数 :
Polygon1 – 确定其它多边形相对位置的多边形。
Polygon2 – 确定相对位置的多边形。
返回值:
多边形2位于多边形1的哪一边
功能:
通过第一个多边形对第二个多边形上的每一个顶点进行检测。
如果所有的顶点位于第二个多边形的正面，那么多边形2被认为位于多边形1的“前面”。
如果第二个多边形的所有顶点都位于第一个多边形的反面，那么多边形2被认为位于多边形1的“后面”。
如果第二个多边形的所有顶点位于第一个多边形之上，那么多边形2被认为位于多边形1的内部。
最后一种可能是所有的顶点即位于正面有位于反面，那么多边形2被认为横跨过多边形1。
CALCULATE-SIDE （Polygon1, Polygon2）
NumPositive = 0, NumNegative = 0
for each point p in Polygon2
if （CLASSIFY-POINT （Polygon1, p） = INFRONT）
then NumPositive = NumPositive + 1
if （CLASSIFY-POINT （Polygon1, p） = BEHIND）
then NumNegative = NumNegative + 1
if （NumPositive > 0 && NumNegative = 0）
then return INFRONT
else if（NumPositive = 0 && NumNegative > 0）
then return BEHIND
else if（NumPositive = 0 && NumNegative = 0）
then return COINCIDING
else return SPANNING
上面的算法也给我们解答了一个问题，当一个多边形横跨过分割面时如何进行处理，上面的算法中将多边形分割为两个多边形，这样就解决了画家算法中的两个问题：
循环覆盖和多边形相交。
下面的图形显示了多边形如何进行分割的。
图1.4
如图1.4所示，多边形1为分割面，而多边形2横跨过多边形1，如图右边所示，多边形被分割为2、3两部分，多边形2位于分割面的“前面”而多边形3位于分割面的“后面”。
当建立一个BSP树时，首先需要确定的问题是如何保证二叉树的平衡，这意味着对于每一个叶节点的分割深度而言不能有太大的差异，同时每一个节点的左、右子树需要限制分割的次数。
这是因为每一次的分割都会产生新的多边形，如果在建立BSP树时产生太多的多边形的话，在图形加速卡对场景渲染时会加重渲染器的负担，从而降低帧速。
同时一个不平衡的二叉树在进行遍历时会耗费许多无谓的时间。
因此我们需要确定一个合理的分割次数以便于获得一个较为平衡的二叉树，同时可以减少新多边形的产生。
下面的代码显示了如何通过循环多边形集合来获得最佳的分割多边形。
（5）函数 CHOOSE-DIVIDING-POLYGON
参数:
PolygonSet – 用于查找最佳分割面的多边形集合。
返回值:
最佳的分割多边形。
功能:
对指定的多边形集合进行搜索，返回将其分割为最佳子集合的多边形。
如果指定的集合是一个“凸多边形”则返回。
CHOOSE-DIVIDING-POLYGON （PolygonSet）
if （IS-CONVEX-SET （PolygonSet））
then return NOPOLYGON
MinRelation = MINIMUMRELATION
BestPolygon = NOPOLYGON
LeastSplits = INFINITY
BestRelation = 0
循环查找集合的最佳分割面。
while（BestPolygon = NOPOLYGON）
for each 多边形P1 in PolygonSet
if （多边形P1在二叉树建立过程中没有作为分割面）
计算被当前多边形定义的分割面的正面、反面和横跨过分割面的多边形的数量。
NumPositive = 0, NumNegative = 0, NumSpanning = 0
for each 多边形P2 in PolygonSet except P1
value = CALCULATE-SIDE（P1, P2）
if（value = INFRONT）
NumPositive = NumPositive + 1
else if（value = BEHIND）
NumNegative = NumNegative + 1
else if（value = SPANNING）
NumSpanning = NumSpanning + 1
计算被当前多边形分割的两个子集合的多边形数量的比值。
if （NumPositive < NumNegative）
Relation = NumPositive / NumNegative
else
Relation = NumNegative / NumPositive
比较由当前多边形获得的结果。
如果当前多边形分割了较少的多边形同时分割后的子集合比值可以接受的话，那么保存当前的多边形为新的候选分割面。
如果当前多边形和最佳分割面一样分割了相同数量的多边形而分割后的子集合比值更大的话，将当前多边形作为新的候选分割面。
if （Relation > MinRelation &&
（NumSpanning < LeastSplits ||
（NumSpanning = LeastSplits &&
Relation > BestRelation））
BestPolygon = P1
LeastSplits = NumSpanning
BestRelation = Relation
通过除以一个预先定义的常量来减少可接受的最小比值。
MinRelation = MinRelation / MINRELATIONSCALE
return BestPolygon
四、实验结果
五、实验心得
通过本次实验主要目的在于掌握BSP的原理并熟悉Ogre中基于BSP技术的室内场景渲染的使用方法。
BSP原理可概括为：
建立BSPTrees的最初想法是获得一个图元的集合，这个集合是场景的一部分，然后分割这个图元集合为更小的子集合，必须注意子集合必须为“凸多边形”。
这意味着子集合中任一个多边形都位于相同集合中其它多边形的“前面”。
BSP的出现解决了遮挡判定和可见物筛选两个问题，硬件ZBuffer出现后，可见物筛选成为重中之重；而对于可见物筛选除了视锥裁剪外，还可通过Portal和PVS技术来实现并了解各个技术的优缺点，Portal复杂，PVS简单；本次实验对BSP的渲染流程也有了一定的认识，对Ogre知识的学习还需强化。
六、主要代码
//BSP.h
#ifndef__BSP_H__
#define__BSP_H__
#include"SdkSample.h"
#include"FileSystemLayer.h"
#ifOGRE_PLATFORM==OGRE_PLATFORM_APPLE||OGRE_PLATFORM==OGRE_PLATFORM_IPHONE
#include"macUtils.h"
#endif
usingnamespaceOgre;
usingnamespaceOgreBites;
class_OgreSampleClassExportSample_BSP:
publicSdkSample
{
public:
Sample_BSP（）
{
mInfo["Title"]="BSP";
mInfo["Description"]="Ademooftheindoor,orBSP（BinarySpacePartition）scenemanager."
"AlsodemonstrateshowtoloadBSPmapsfromQuake3.";
mInfo["Thumbnail"]="thumb_bsp.png";
mInfo["Category"]="Geometry";
}
StringVectorgetRequiredPlugins（）
{
StringVectornames;
names.push_back（"BSPSceneManager"）;
returnnames;
}
protected:
voidlocateResources（）
{
//loadtheQuakearchivelocationandmapnamefromaconfigfile
ConfigFilecf;
cf.load（mFSLayer->getConfigFilePath（"quakemap.cfg"））;
mArchive=cf.getSetting（"Archive"）;
mMap=cf.getSetting（"Map"）;
#ifOGRE_PLATFORM==OGRE_PLATFORM_APPLE||OGRE_PLATFORM==OGRE_PLATFORM_IPHONE
//OSXdoesnotsettheworkingdirectoryrelativetotheapp,
//InordertomakethingsportableonOSXweneedtoprovide
//theloadingwithit'sownbundlepathlocation
if（!
Ogre:
:
StringUtil:
:
startsWith（mArchive,"/",false））//onlyadjustrelativedirs
mArchive=Ogre:
:
String（Ogre:
:
macBundlePath（）+"/"+mArchive）;
#endif
//addtheQuakearchivetotheworldresourcegroup
ResourceGroupManager:
:
getSingleton（）.addResourceLocation（mArchive,"Zip",
ResourceGroupManager:
:
getSingleton（）.getWorldResourceGroupName（）,true）;
}
voidcreateSceneManager（）
{
mSceneMgr=mRoot->createSceneManager（"BspSceneManager"）;//theBSPscenemanagerisrequiredforthissample
}
voidloadResources（）
{
/*NOTE:
Thebrowserinitialiseseverythingatthebeginningalready,soweusea0initproportion.
Ifyou'renotcompilingthissampleforusewiththebrowser,thenleavetheinitproportionat0.7.*/
mTrayMgr->showLoadingBar（1,1,0）;
//associatetheworldgeometrywiththeworldresourcegroup,andthenloadthegroup
ResourceGroupManager&rgm=ResourceGroupManager:
:
getSingleton（）;
rgm.linkWorldGeometryToResourceGroup（rgm.getWorldResourceGroupName（）,mMap,mSceneMgr）;
rgm.initialiseResourceGroup（rgm.getWorldResourceGroupName（））;
rgm.loadResourceGroup（rgm.getWorldResourceGroupName（）,false）;
mTrayMgr->hideLoadingBar（）;
}
voidunloadResources（）
{
//unloadthemapsowedon'tinterferewithsubsequentsamples
ResourceGroupManager&rgm=ResourceGroupManager:
:
getSingleton（）;
rgm.unloadResourceGroup（rgm.getWorldResourceGroupName（））;
rgm.removeResourceLocation（mArchive,ResourceGroupManager:
:
getSingleton（）.getWorldResourceGroupName（））;
}
voidsetupView（）
{
SdkSample:
:
setupView（）;
//modifycameraforclosework
mCamera->setNearClipDistance（4）;
mCamera->setFarClipDistance（4000）;
//setarandomplayerstartingpoint
ViewPointvp=mSceneMgr->getSuggestedViewpoint（true）;
//QuakeusestheZaxisastheupaxis,somakenecessaryadjustments
mCamera->setFixedYawAxis（true,Vector3:
:
UNIT_Z）;
mCamera->pitch（Degree（90））;
mCamera->setPosition（vp.position）;
mCamera->rotate（vp.orientation）;
mCameraMan->setTopSpeed（350）;//makethecameramoveabitfaster
}
StringmArchive;
StringmMap;
};
#endif
//BSP.cpp
#include"SamplePlugin.h"
#include"BSP.h"
usingnamespaceOgre;
usingnamespaceOgreBites;
#ifndefOGRE_STATIC_LIB
SamplePlugin*sp;
Sample*s;
extern"C"_OgreSampleExportvoiddllStartPlugin（）
{
s=newSample_BSP;
sp=OGRE_NEWSamplePlugin（s->getInfo（）["Title"]+"Sample"）;
sp->addSample（s）;
Root:
:
getSingleton（）.installPlugi
升级会员 