1、三维场景的组织与绘制一一.三维场景的组织与管理三维场景的组织与管理n场景图是一种将场景中的各种数据以图的形式组织在一起的场景数据管理方式。n它是一个K-树,场景图中的每一个节点都是数据的存储结构,父结点会影响子结点。n每个节点信息包括：（1）场景的组织结构信息，如父节点或子节点的句柄；（2）支持绘制流程的各种信息，如节点在当前帧中是否绘制的标识，节点的包围体等；（3）描述表现自身所需的各类特征属性信息，如位置坐标、变换矩阵以及颜色、材质等。1.基于场景图的表达与管理基于场景图的表达与管理场景图oBVH是最常用的数据结构n简单容易理解Simple to understandn编程简单o不过它仅仅
2、存储几何信息n绘制不仅仅是几何信息o场景在BVH基础上扩展了:n光照（Lights）n纹理（Textures）n变换（Transforms）n更多.例:o模拟一个星系n 恒星|旋转 /行星1 行星|旋转 旋转 /卫星A 卫星B 卫星C 卫星D o渲染恒星保存当前矩阵 应用第一个旋转 渲染行星1 保存当前矩阵 运用第二个旋转 渲染卫星A 渲染卫星B 恢复我们保存的矩阵 渲染行星2 保存当前矩阵 运用行星2的旋转 渲染卫星C 渲染卫星D 恢复我们保存的矩阵恢复我们保存的矩阵 n 恒星|旋转 /行星1 行星|旋转 旋转,摇摆 /卫星A 卫星B 卫星C 卫星D行星A摇晃n渲染恒星保存当前矩阵 应用旋转
3、 保存当前矩阵 运用摇晃 渲染行星A 保存当前矩阵 运用旋转 渲染卫星A 渲染卫星B 恢复矩阵 恢复矩阵 恢复矩阵 运用旋转 渲染行星2 保存当前矩阵 运用行星2的旋转 渲染卫星C 渲染卫星D恢复我们保存的矩阵恢复我们保存的矩阵n场景绘制过程o根据游戏的需要,更新场景中的部分结构,从下到上；o场景图的剔除绘制过程：o要修改一个行星的位置,只需修改星结点的属性,不更改任何子节点的属性.o场景图一般包含下列节点:n几何节点n变换节点o平移，旋转，缩放n开关节点通过当前状态对子节点进行选择的节点o把场景中的物体按照绘制状态分类，对相同状态的物体设置一次状态；o状态切换是一个比较耗时的运算；o绘制状态
4、包括：n纹理映射的参数设置n材质参数，包括泛光、漫射光等n各类其他渲染模式：多边形插值、融合等o半条命2.基于绘制状态的场景管理基于绘制状态的场景管理o建立状态树n按状态集进行排序n遵照“尽量使状态转换最少”o按深度优先遍历状态树，依次绘制o由于可见性检测、求交、碰撞等都可归结为空间关系的计算。o对每个物体建立包围体；o对场景建立包围体层次树；o快速判断一个点是否在物体的凸包围体中。3.基于景物包围体的场景组织基于景物包围体的场景组织o常用的场景物体包围体n包围球nAABB包围盒nOBB包围盒n平行六边包围体nK对平行六面包围体二二.优化场景绘制的几何剖分技术优化场景绘制的几何剖分技术常用的三
5、种:o1.BSP树（二叉空间平分树）n应用于深度排序，碰撞检测，绘制，节点裁减和可见性判断，加速三维场景的漫游；n空间中的任意平面把空间分成两部分：一份为二地空间剖分方法；n一直递归下去，结束的条件：o空间中没有物体了；o剖分的深度达到了指定的数值就停下oBSP树的建立n先对物体建立包围体结构，然后以包围体为单位建立场景的BSP树；n剖分方式：o均匀剖分：适于场景中物体分布均匀o平行坐标轴剖分：室内游戏o选取场景中面积最大和遮挡物体最多的面：判断物体与剖分面的关系稍负责BSP（Binary Space Partitioning）树o两种类型:n沿轴（Axis-aligned）n沿多边形(Pol
6、ygon-aligned)o总体思想:n用平面划分多边形n把几何排序后存放到它所属的空间n递归，直到都完成o如果按某种方式遍历，可以得到沿一个轴排序的几何n对于沿多边形的方法很准确n沿轴的方法则结果是近似的沿轴BSP 树(1)o仅能沿x,y或产生一个分裂面最小的 box沿面分裂沿面分裂沿面分裂沿轴BSP 树(2)o每个内部节点拥有一个分割面；o叶子具有几何信息o与BVH 比不同n提供闭合空间，并且有序nBV层次能用任何方式构造（无序）；nBVHs 能够使用任何所需要的BV类型ABCDEPlane 0Plane 1aPlane 1bPlane 201aAB1bC2DE沿轴BSP 树粗略排序o沿视
7、点测试平面o从根递归测试o继续从当前面从前向后排序eye01aAB1bC2DE11a1b202345l沿多边形BSP树用同样的方法-但给的是准确排序oBSP树的遍历：n深度优先n广度优先oBSP树局限性：n不太适合动态场景n构造时间长n常用于地形绘制；n以包围四边形逼近场景，然后迭代地一分为四。o均匀剖分：适于场景中物体分布均匀o平行坐标轴剖分：室内游戏o选取场景中面积最大和遮挡物体最多的面：判断物体与剖分面的关系稍负责n最大的优点：层次剔除o 2.四叉树四叉树n长方体递归地剖分为八个长方体；n构建时间比BSP树短，容易使用。n常用于视域裁剪、碰撞检测。o 3.八叉树八叉树比较技术名称适用场景
8、构建复杂度实用性二叉树尺寸不大的室内场景复杂大部分游戏引擎四叉树室外地形一般仅用于地形绘制八叉树大规模室内空间场景一般复杂游戏引擎均匀八叉树分布均匀的三维场景简单少量三维游戏引擎三三.游戏场景的几何优化游戏场景的几何优化o空间数据结构用来加快渲染和各种查询o为什么需要更快的速度?o图形硬体6个月速度翻倍!o我们总不满足n屏幕分辨率:3000 x1500n真实感:全局光照n几何复杂度:无上界!场景的几何优化oLODn在不影响画面视觉效果情况下，逐步简化景物表面的细节来减少场景的几何复杂性；n四类：o简单取舍型n设置阈值，小于则不绘o平滑过渡型n大于上限，正常绘制；小于，不绘；中间，线性过渡o静态
9、LOD型n预计算同一物体的多个不同精度的版本，根据不同距离切换使用不同的物体n跳跃：增加雾化效果1.层次细节技术(LOD)o动态LOD型n在场景漫游过程中动态地根据相机的位置和物体的重要性动态简化网格；n简化算法：基于顶点的删除基于边的删除：定义代价函数，删除代价最小的边基于面的删除o渐进网格和连续多分辨率绘制l在不同的距离处（从视点)使用不同的层次细节l离视点更近出，使用更多的三角形o目的:n有些看不见的可以不绘制n从而加快绘制速度2.快速可见性判断与消隐o类型类型n物体层的算法：场景聚类技术o决定相对于视点面的前后排列o二叉树和八叉树，入口技术，潜在可见集，单物体分块n顶点层算法：顶点剔除
10、算法o背面剔除o视域剔除o裁剪面剔除n象素层的算法：图像空间排序o深度缓冲消隐o层次缓冲消隐o时空连贯性不同的剪切技术view frustumdetailbackfaceportalocclusiono基于入口技术的可见性判断n适用于室内游戏n根据单元与单元之间的邻接图，通过深度遍历建立单元与单元的入口序列，从而得到单元对单元的可见性集合。n入口技术的优点：o方便定义场景：可方便地动态创建和修改场景o快速绘制Images courtesy of David P.Luebke and Chris Georgesl平均:裁减去 20-50%多边形l加速:from slightly better t
11、o 10 timesl上面的建筑中l球是要画的对象l分割带有门的单元(建立图)l对于每一帧:定位视点的位置，并把整个场景2D AABB初始化*绘制当前单元用带有w.r.t.AABB 的视点六面体裁减方法对最近的单元遍历(通过门户)遍历门户的 AABB&AABB 交叉Goto*o遮挡面剔除技术n基于阴影体的遮挡剔除o选择遮挡体，生成一个阴影体：尺寸最大的多边形或多个三角形组成的一个大的凸包；o利用包围盒测试与遮挡体的关系o基于视点的遮挡剔除o对多个遮挡体，按重要性排序l主要思想:完全在另一个后的物体可以被裁剪l效率问题很难解决l这个领域有很多研究最终图像l表明“入口裁剪”属于遮挡裁剪类型l简单的
12、方法是剖其背离视点的面l用于:闭合面(例如:球 sphere)不管是否我们只知道这个面是否可见(例如:室内的墙)l两种方法(屏幕空间,视空间)l通常用API完成lOpenGL:glCullFace(GL_BACK);lD3D：SetRenderState(D3DRS_CULLMODE,TRUE);l怎样确定是背向面?l首先,必须有一个连续朝向的多边形must have consistently oriented polygons,e.g.,counterclockwise012front facing012back facinglTwo ways in different spaces:scr
13、een space102front012backeyefrontbackeye spacelBound every“natural”group of primitives by a simple volume(e.g.,sphere,box)lIf a bounding volume(BV)is outside the view frustum,then the entire contents of that BV is also outside(not visible)lDo what we always do in graphicslUse a hierarchical approach,
14、e.g.,a spatial data structure(BVH,BSP,scene graph)lWhich stages benefits?Geometry and Rasterizer Bus between CPU and GeometryrootcameraUse some kind of occlusionrepresentation ORfor each object g do:if(not Occluded(OR,g)render(g);update(OR,g);end;end;lTarget:urban scenerydense occlusionviewer is abo
15、ut 2 meters above groundlAlgorithm:Process scene in front-to-back using a quad treeMaintain a piecewise constant horizonCull objects against horizonAdd visible objects occluding power to the horizonlTo process tetrahedron(which is behind grey objects):find axis-aligned box of projectioncompare again
16、st occlusion horizonculledlWhen an object is considered visible:lAdd its“occluding power”to the occlusion representationOcclusion Culling with DirectX9 o实现实现nIDirect3DQuery9 函数函数:oRender every objects bounding mesh oFor every object:nBegin query nRe-render the bounding mesh nEnd query nRetrieve occl
17、usion query data.If the pixels visible are greater than zero,the object should be rendered.Otherwise,the object should be occluded from rendering.oStep 1:nA bounding mesh is usedoStep 2:nObject Declaration oFor the occlusion process,interfaces of LPDIRECT3DQUERY9,LPD3DXRENDERTOSURFACE,LPDIRECT3DSURF
18、ACE9,and LPDIRECT3DTEXTURE9 need to be declared.nSetting up the Occlusion Objects oThe query itself must be created,along with the texture and the render-to-surface.oD3DUSAGE_RENDERTARGET is used during the creation of the textureoThe surface itself is obtained through the GetSurfaceLevel()function
19、of LPDIRECT3DTEXTURE9.nCulling the Objects oFirst,the LPD3DXRENDERTOSURFACE is activated and cleared.oSecond,every objects bounding mesh is rendered.The meshes are re-rendered and then their occlusion queries are retrieved.o Finally,the surfaces scene is ended and deactivated.nThe Render LoopoScreenshot of Result一个D3D漫游系统的绘制o建模:n模型导入n程序生成o绘制:n纹理映射n特殊技巧o漫游控制:n第一人称n第三人称视角o例子地形的绘制与漫游o基于高度图生成地形高度o基于四叉树来遍历绘制o采用LOD加速o纹理压缩减少存储量
