基于BSP树的启发式阴影生成算法

1、收稿日期:2005-11-25第23卷 第11期计 算 机 仿 真2006年06月文章编号:1006-9348(200606-0220-04基于BSP 树的启发式阴影生成算法刘恒1,江南2,魏楠1(1.南京大学城市与资源学系,江苏南京210093;2.中科院南京地理与湖泊研究所,江苏南京,210008摘要:阴影的生成在虚拟现实领域一直是个难题,特别是针对动态光源的大规模场景,目前还没有较成熟的阴影算法。通过对现有阴影生成算法和场景组织算法的研究,该文提出了基于二维空间分割树(BSP 树的启发式阴影生成算法:首先创建场景BSP 树,随着观察者视点的改变,选取视剪裁体内的节点创建以光源为视点的遮挡

2、体B SP 树,然后通过对该BSP 树的遍历拣选出阴影启发区内的物体,经过处理后BSP 树只留下一些生成阴影必要的多边形大大减少了计算量,最后能够快速生成阴影。关键词:阴影;二维空间分割树;启发式中图分类号:TP391 文献标识码:AA a lgor ith m of H eur istic ShadowB ased On B SP T reeL I U H eng 1,JI A NG N an2(1.D epa rt m en t o fU rban and R esources ,N anji ng U n i v ersity,N an jing Jiang su 210093,Chin

3、a ;2.N an jing Instit u te o fG eography and L i mno logy ,N an ji ng J i angsu 210008,Ch i naAB STRACT :Shadow p lays an i m por tan t ro l e i n rea li stic i m age synthes is .Bu t the bu il d i ng o f the shadow is a d ifficu lt problem i n the field of the v irtua l rea lity .N ow aday s ,there

4、 is not a better a lgor ith m i n t he m ass scene .By t he study i ng o f the a lgor ith m of bu il d i ng shadow and the organ ization o f the scene ,th is paper descr i bes t he algo rit hm o f heur i stic shado w based on the B inary Space P artiti on i ng trees (BSP trees.A t first ,w e bu ild

5、a BSP tree o f scene ,and se lect the node o f the tree ,w hich is c li pped by the frustu m o f the sight .T hen we bu il d the BSP tree o f t he o cclusion us i ng the se lected node and se lect the objec ts w hich are i n the heuristic zone o f the shado w ag a i n .A fter se lec t t w ice ,t he

6、re are som e po lygons that a re necessary to the bu ild i ng o f the shadow in the BSP tree o f t he o cc l usion .So ,w e can bu ild the shadow rap i d ly .K EY W ORDS :Shadow ;BSP tre es;H eur istic1 引言阴影是计算机生成的虚拟场景中重要的一部分,它有利于场景的真实感,并且提供重要的深度信息和场景中物体相对位置的信息。实际上,与其它可视化的信息如高度、纹理、透视、移动相比,阴影更能有力地表达场

7、景中物体的精确位置、尺寸。但是阴影的生成需要进行大量的计算,具有阴影的场景在渲染时会造成时间上的很大牺牲,特别是当碰到复杂场景和多边形数量增加时渲染速度会大大降低,以至于场景的渲染满足不了最基本的视觉要求(低于25帧/秒。因而一直以来阴影的生成在虚拟现实领域中都是一个比较有挑战性的问题。针对阴影的生成,国内外学者提出了一些算法,目前最为常用的有Shadow M app ing 和Shadow V o l um e 算法,在此基础上发展出Shadow V o lu m e BSP (SVBSP 、H iera rch ica l Shadow V o l um e 等算法,这些算法在不同程度上解

8、决了虚拟场景中的阴影生成问题。本文在已有阴影算法基础上提出了基于BSP 树的启发式阴影算法,该算法利用虚拟场景中可以容忍一些误差出现的特性以及尽量减少计算阴影面的原则实现室内大规模动态光源场景的阴影生成。2 启发式阴影生成步骤整个方法的过程如下:步骤一,构建场景BSP 树,并拣选出处于视剪裁体内的多边形集;步骤二,以光源为视点通过对场景BSP 树 in 节点的遍历建立阴影遮挡体BSP 树,用以!220!剔除不会生成阴影的遮挡体;步骤三,根据光源属性、位置和观察者视点位置建立阴影启发区;步骤四,遍历阴影遮挡体BSP树,选出位于阴影启发区内的节点,根据选出来的阴影面用shadow vo lu m

9、e算法1生成场景阴影。3 算法实现3.1 场景BSP树的生成场景BSP树是在预处理过程中建立的。通过对场景BSP 树的处理可以较快进行物体的拣选,且便于再次构造以光源为视点的阴影BSP树。为了获得较快的拣选效率,BSP树的每个节点中还加上了包围盒属性,即该节点中包含所有多面体的一个立方体,对于根节点来说,包围盒是包含了整个场景的一个大立方体,随着BSP树深度的增加包围盒也逐渐缩小,到叶节点包围盒就是包含一个凸集的立方体。包围盒是在构建每一个子节点时通过比较属于该子节点的各个点的x、y、z坐标来得到的,结果存在一个BOX结构中。除了加上包围盒属性外,BSP 树中还必需有标识各个节点是否处于视锥体

10、的属性,如果节点处于视锥体内该属性值为 in,如果节点处于视锥体外该属性值为 out,加上该标识一方面是为了方便识别要渲染的节点,另一方面是为了在构建阴影遮挡面的BSP树时识别哪些节点该处理,哪些该舍去。用C+语言定义BSP树及树节点的结构如下:class BSPT reeN ode P o lygon m_D i v ider;/节点的分割面BoundBox m_Box;/节点的包围盒BSPT reeN ode*m_pL eft N ode;/左子节点BSPT reeN ode*m_pR i gh t N ode;/右子节点bo o lm_bInS ight;/节点是否可见一个不平衡的二叉树

11、在进行遍历时会耗费许多无谓的时间,因此建立一个BSP树时,首先需要确定的问题是如何保证二叉树的平衡,这意味着对于每一个叶节点的分割深度而言不能有太大的差异。同时,为了防止分割产生过多的多边形影响渲染速度又要限制每一个节点的左、右子树分割的次数。这里采用左右子节点中多边形面的比值和所分割面的数量为指标对多边形集中的每一个面进行遍历2,比较后得出最优的分割面。3.2 拣选出视剪裁体内的多边形拣选视剪裁体内的多边形是通过对场景BSP树的遍历实现的,通过检测每一个节点的包围盒与视锥体的关系确定该节点是否可见:如果节点的包围盒不在剪裁体内则该节点定义为不可见,下面的子节点就不会再进行检测;如果节点的包围

12、盒完全或部分处于剪裁体内都定义该节点可见,然后继续检测该节点的子节点,剔除不在包围盒的部分。在进行拣选时要解决的一个问题是剪裁体的定义。三维开发包中都有剪裁体的概念,它是一个平截台体,是视锥体的一部分,一般是通过两个函数来描述的:一个用于指定视点的空间位置;一个用于定义锥体的大小,该函数中的参数描述的是相对于视点的远近剪裁面的距离和锥体的长宽,在空间中它是相对于视点而言的。但对BSP树进行拣选需要的是具有实际空间位置的视锥体,因此还需做一个变换。常用的变换方法有两种:一种是直接根据所给的参数用空间几何方法计算;另一种方法是假定视点在原点(0,0,0点,根据视锥体上下两个面的夹角fovy、近剪裁

13、面near、远剪裁面far值计算出平截台体八个顶点的座标,然后通过旋转、平移矩阵变换得到八个顶点的实际位置。三维图形开发包中的矩阵运算可以简化计算,因此采用第二种方法。首先计算近剪裁面四个顶点的座标 :图1 视锥体截面由图1可看出y方向上的数值为:|y|= near*tan(fovy/2,根据长宽比asp ect可得出x方向上的数值:|x|=|y|*asp ect,这样就可得出近剪裁面四个顶点的座标,用同样的方法可得出远剪裁面的四个顶点的座标3。将所得的顶点坐标与当前的变换矩阵m ut相乘便得到平截台体八个顶点的实际空间坐标,在漫游过程中随视点的变换也可用同样的方法获得新的剪裁体坐标。剪裁体求

14、出后,对BSP树进行遍历实现拣选,将子节点和页节点标识为 in和 out。3.3 构建光线遮挡体BSP树阴影遮挡面BSP树的构建是在场景BSP树拣选的基础上进行的。树节点的结构和场景树节点的结构稍有不同,定义如下:ShadowBSPT reeN odePo lygon m_Sil houe tte;/节点轮廓面Po lygon m_D i v i der;/分割面BoundBox m_Box;/节点的包围盒ShadowBSPT reeN ode*m_pL eft N ode;/处于该节点的shadow vo l um e内的子节点ShadowBSPT reeN ode*m_pR i gh t

15、N ode;/处于该节点的shadow vo lu m e外的子节点Po lygonSet m_Po lygonSe t;/节点所包含的多边形集boo lm_b InShadow;/节点是否处于阴影启发区域内!221!在生成BSP树时,以光源位置为 视点对场景BSP树标识为 in的物体进行遍历。从距离光源最近的叶节点开始处理,以该叶节点为根节点,根据节点所含的凸集生成该节点的阴影轮廓4,并以光源和轮廓的一条边构成分割面,面两侧的空间分别对应左节点空间和右节点空间,通过遍历将场景BSP树中的节点分别加到遮挡体BSP树的两个子节点中,并以同样的方式对子节点进行递归处理。处理过程中有两个重要步骤:第

16、一,场景BSP树的节点加入到遮挡面BSP树时要根据分割面重新进行分割,由于分割是在每个节点的边界盒基础上的,因此分割时只需做节点的删除添加操作即可;第二,对每一个节点的凸集进行是否处于阴影体的判断,如果处于上层次节点的阴影体内则该凸集就不加入BSP树中,因为它已经处于阴影范围内不会再产生阴影5。生成遮挡体BSP树的伪代码如下:Crea teShadowBSP(L i gh t P ositi on,SceneT ree,ShadowT ree N odeBSPT reeN ode nea rest N ode=G et N e arest N ode(Scene T ree,L ightPos

17、 ition;/找到场景中距离光源位置最近且不处于阴影体的节点w h ile(nearest N ode.m_Po l ygonSet处于阴影体中 /剔除节点D ele teN ode(SceneT ree;/重新得到最近的节点nea re st N ode=SceneT ree.G et N ea rest N ode(L ight Po sition;/给阴影树的节点赋值ShadowT reeN ode.m_Po lygonS et=nearest N ode.m_ Po lygon Set;ShadowT reeN ode.m_Box=Ca lcula teBox(nearest N o

18、de.m_P o l ygonSet;ShadowT reeN ode.m_S ilhoue tte=G enera teSil houe tte (ne arest N ode.m_P o lygonSe t;ShadowT reeN ode.m_D iv i de r=G etD i v ider(Shadow T ree.m_S ilhoue tte,L i gh t P os iti on;/将场景BSP树分割为两部分BSPT ree L e ftSubT ree=G e t L eftSubT ree(SceneT ree, ShadowT ree.m_D i v ider;BSPT

19、 ree R ightSubT ree=G et R ightSubT ree(Scene T ree,ShadowT ree,m_D iv i de r;if(L e ftSubT ree的叶节点为空Shado wT re e N ode.m_pL e ft N ode=NU LL;else/继续处理分割后的场景树生成ShadowBSPT ree的左节点Shado wT ree N ode.m_pLe ft N ode=new Shadow T ree N ode;CreateShadowBSP(L i ghtPosition,L eft SubT ree,Shadow T ree N od

20、e.m_pL eft N ode;if(R i gh tSubT ree的叶节点为空ShadowT re e N ode.m_pR ight N ode=NU LL;/继续处理分割后的场景树生成ShadowBSPT ree的右节点elseShadowT reeN ode.m_pR ight N ode=new ShadowT ree N ode;Crea teShadowBSP(L i gh t P ositi on,R ightSubT ree, ShadowT reeN ode.m_pR i gh t N ode;/左右节都处理完毕函数返回return;3.4 阴影启发区的选择和阴影生成当

21、观察者在场景中漫游时,随着视点的改变只需要生成周围一定范围内的阴影,这个范围就是阴影启发区,实际上阴影启发区也是一个类似于视剪裁体的平截台体,阴影启发区的生成与光源位置、光源属性和视点位置有关。对于位置型光源(如点状光源台灯等来说,阴影启发区可以根据光线的衰减系数确定,光线的衰减系数是这样定义的:D=1/(Kc+Kl*d+Kq*d2其中的Kc、Kl、Kq是在定义点光源时所指定的参数,在计算启发区时可以根据场景的需要赋于D值,然后反解出d值,再加上光源的角度 可以计算出阴影启发区四个顶点的坐标。方向型光源(如太阳没有衰减系数,因此启发区根据视点位置确定。在场景漫游时场景中的物体远小近大,对于远处

22、的物体在生成阴影时可以考虑将其剔除,这与现实中的情况是相符的,并不会影响整个场景的真实感效果。在进行计算时,启发区近剪裁面和视平截台体的近剪裁面一致,远剪裁面与近剪裁面的距离为Ld,因为视点与近剪裁面的距离越大场景中的物体看起来就越小,所以Ld是随视点与近剪裁面的距离Sd的增大而减小的,这种减小关系可以是直接的反比例关系,也可以与Sd的对数成反比,具体根据场景在视觉和显示效果上的要求确定,得出Ld值以后便可以计算出启发区。获得启发区后,根据启发区对阴影遮挡体BSP树进行拣选,拣选的过程与对场景BSP树进行拣选的方法一样,经过拣选后处于阴影启发区节点的m_bInShadow值为true,反之为f

23、a lse。拣选完毕便可根据ShadowV o lu m e算法,借助于深度测试和模板缓存对阴影进行渲染。渲染时根据阴影遮挡体BSP树各节点的阴影轮廓面在模板缓存中绘制阴影体,绘制完在整个显示区加上所需的阴影浓度的蒙板,在有阴影体的地方模板值通过测试6,这样,就产生了场景的阴影效果。!222 !3.5 启发式阴影的应用将基于BSP 树的启发式阴影生成方法用于苏州工业园区室内场景中用于增强场景的真实感,根据场景复杂度的不同在实时渲染生成阴影的过程中处理的阴影三角面为所显示三角面总数的45%-80%。图2、图3是在点光源下生成室内阴影的帧截图,图4对整个场景中的物体进行阴影处理,图5采用本文的方法

24、生成阴影。图4生成阴影处理三角面总数为11616个,图5阴影处理三角面个数为7665个,平均帧率提高了2 8帧。 图2整个场景生成阴影 图3 启发式剔除远景阴影4 结束语本文针对具有动态光源的大规模室内场景,以BSP 树算法为基础构建遮挡体BSP 树,并根据不同的光源灵活选择阴影启发区最后生成阴影。该方法在满足视觉效果的同时大大提高了整个场景阴影的生成效率,并且适用于动态光源。要更好的模拟真实的光照效果还存在以下问题:如何在场景中加入多光源,方法中把启发区域的生成放在遮挡体BSP 树构建之后,就是考虑到多光源问题的解决;在静态的室内场景中如果有动态物体,它的阴影如何生成;如何将室内场景扩展为通用场景。这些问题有待进一步研究。参考文献:1Frank i nCC ro w.Shado wA lgor it hm sforC o m pu terG raph icsC .In C o m puter G raph ics (Proceed ings of ACMS I GGRAPH 77,J u ly 1977,ACM:242-248.2 S a m uel Ranta