[汇编]井下场景渲染

[汇编]井下场景渲染 矿山井下场景的实时渲染算法 12李大锦,白成杰 12 (山东师范大学传媒学院数字媒体系, 济南，山东，250014;山东师范大学物理与电子科学学院，济南，山东，250014) 摘要:在虚拟数字化矿山中,由于井下涉及大量的巷道和机械设备,模型数据量巨大,因此严重制 约了渲染速度。针对该问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ,提出了一种井下虚拟场景的实时渲染算法。该算法将每个巷道作为一 个区域,利用巷道的长方形包围盒进行相机的包围检测来确定相机位置,从而确定可见的巷道区域, 。实验结果显示该在渲染时排除不可见的巷道。同时,为减少包围检测的计算,利用八叉树分割场景来缩小检测范围 算法可大幅度减少渲染对象, 渲染速度明显优于传统的图形加速算法。 关键词:虚拟矿山,实时渲染,图形加速算法;八叉树 中图分类法:TP391.41 文献类型:A 文章编号:xxxxxxx A Real-Time Rendering Method for Underground Mine Scenes 12Dajin Li，Chengjie Bai 1(Department of Digital Media, Communication School of Shandong Normal University, Jinan 250014, China) 2(Physics and Electronics Science School of Shandong Normal University, Jinan 250014, China) Abstract: Digital virtual mine system involves a mass of roadways and mechanical equipments. The huge amount of model data will seriously reduce rendering speed. This paper presents a real-time rendering algorithm for virtual scenes of underground mine. We looked on each roadway as a region, and used rectangular bounding box of roadway to test the camera inside or outside roadway, so as to determine the visible regions. The invisible roadway regions would be discarded in the rendering. In order to reduce the calculation of inside-outside testing, we used octree to narrow the scope of testing. The experimental results show that the algorithm can significantly reduce rendering objects, and rendering speed was much faster than traditional algorithms of rendering acceleration. Key words: virtual mine; real-time rendering; graphics acceleration algorithm; Octree 数字化矿山系统，可实现井下场景漫游、矿井生产系统的 1、引言 计算机辅助 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 、各生产环节的实时监管以及各类灾害的 虚拟矿山是虚拟现实技术在矿业里的应用。借助虚拟防控和预测。同时借助虚拟矿山环境，还可以完成各类生 产操作的模拟训练和救援预案的演练。在虚拟地下矿山系所有其他巷道。在判断相机处于哪一个巷道区域内时，需统中，需要实时显示地下场景，这里遇到的一个关键问题要做包含测试。对于每一个巷道，构建其长方体包围盒，是图形的实时显示。图形加速是计算机图形学研究中的主利用包围盒进行包围测试。一个巷道区域可用以下的结构要内容。在通用的图形加速算法中，最经典的算法是层次 体来 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示: [7] [11]细节算法(LOD)和BSP树算法。其中，LOD算法typedef struct { 根据视点相对模型的距离，随时改变模型的网格精度，从 RoadwayName; char * [9]而减少渲染工作量。基于LOD算法思想，Peter 等和bool Viewable; [10] Wolinsky 等针对大规模地形，分别给出了四边形和三ObjectType *ObjList; 角形网格的分解算法;BSP树是一个二叉分割树，可以int *ConnectedRoadway; 对模型或场景进行多次划分，每次划分将场景分为两个部 分，通过这种空间划分确定场景的可见多边形。除此之外，BoxType BoudingBox; [12,13]图形加速算法还有imposter 算法、体素算法、布告}ViewArea; 板方法等。这类算法的基本思想是利用图像代替模型，从其中，BoudingBox 是巷道区域的包围盒;变量而提高渲染速度。因此这些算法都被称为基于图像的绘制Viewable代表当前巷道区域的可见性;列表ObtList存储[14]算法，Imposter算法是在一定的时间范围内，将较远的了当前巷道内所有的实体对象。列表ConnectedRoadway模型渲染成一幅纹理，并利用该纹理代替模型。建立了和当前巷道相连接的所有巷道的索引。 上述通用的加速方法可有效地减少渲染的多边形数一个大型的虚拟矿山系统往往包含大量的巷道，如果量，尤其对于室外场景，能大幅度提高渲染速度。但矿山将相机和所有巷道的包围体逐个进行包围检测，将严重降井下场景不同于一般的室外场景，渲染范围被限制在巷道低渲染速度。我们采用八叉树来减少检测时间，将整个虚内，在某一时刻，只需渲染极少的巷道及其内的模型。随拟场景的最小包围正方体作为八叉树的根节点，然后依次着相机的移动，渲染范围也会发生较快的变化，如果单纯将正方体平均分割为8个正方体空间(如图1所示)。如采用经典的LOD方法虽然也可以降低计算机的渲染负果假设在相连巷道的交叉口处，相连的巷道不超过k个，担，但是处于不可见范围内的模型仍然可能需要花费较多我们规定节点空间满足下列条件之一时停止空间分割:的时间来处理。传统的BSP树只能处理静态的场景，如 果动态添加物体，需重新构建BSP树，而构建BSP树本a、节点空间包含的巷道数不超过k个。身就是一个非常复杂的过程。在地下巷道中，由于可见的 巷道长度一般情况下并不很长，因此 imposter算法也不b、节点空间不包含任何巷道。能发挥其明显的优势。 对井下场景而言，提高渲染速度最有效的方法是确定c、节点空间小于或等于某个最小尺寸时。场景在某一瞬间的可见巷道。本文根据井下场景的特点， 给出了一种简单、快速的渲染算法。该算法通过判断相机 位置来确定渲染范围，通过八叉树对井下场景进行分割， 在计算可见范围时，先利用八叉树确定相机大概位置，再 利用巷道的包围和进行相机的包围检测来确定巷道的可 见性。 2、数据结构 我们将每一条巷道作为一个可见的区域，用一个表来 索引巷道内的实体对象。如果相机处于该区域时，那么该 区域的巷道处于可见状态。当相机靠近两个或多个巷道相 交的交叉口时，相交的几个巷道都有可能是可见的。因此 在渲染可见巷道的同时，渲染与之相连的巷道及其中的模 型。同样，我们建立一个索引表来索引和当前巷道相连的 在系统的预处理阶段，构建所有的巷道区域，并建立一个巷道区域列表AL，然后对场景进行空间分割，建立八叉树T。如果场景不需要动态调入模型，AL和T一旦建立，则不需要改变。如果需要动态添加模型，而且添加的模型是巷道内的机械、材料等物体，只需将添加的模型加入到相应巷道区域的对象列表ObjList。如果动态调入巷道模型，则需要确定该巷道穿越哪些叶子节点，并在相应的叶子节点内添加对该巷道的索引。 如果当前活动相机为C，在确定可见区域时，从八叉树T的根节点的子树开始搜索，直到找到一个包围C的 叶子节点L。对穿越该叶子节点的所有巷道区域进行包围测试，将包含C的巷道区域标识为可见状态。如果相机a 井下各条巷道的包围盒 C正好处于几个巷道的交叉口处，那么相机有可能同时处于几个巷道区域的包围盒之内，这时几个相交的巷道将同时被标识为可见状态。 算法用伪代码描述如下: Octree AREASEARCH ( AL,T,C ) { Search T to find the leaf L includes C; for ( the i’th area in L) { if( A L[i] includes C) b 八叉树空间分割 AL[i]. Viewable=true; 图1.利用八叉树对场景进行分割 All the areas connected to AL[i] are also最小空间的大小可视情况而定，我们将之定义为最小 巷道包围立方体的大小。一个巷道可能穿过八叉树的几个 Set viewable } 节点，因此八叉树的每个节点要建立对穿越该节点空间的Return L; 所有巷道区域的索引。八叉树节点的数据类型用以下结构} 体定义: 在检测可见区域时，为了减少八叉树搜索时间和包含typedef struct OCTRNODE{ 检测时间，可利用上一次的检测结果。 在动画的每一个 帧时间内，首先判断相机C是否仍然被当前的可见巷道CubeType Cubespace; 区域所包含。如果被当前巷道区域包含，则直接渲染当前struct OCTRNODE *child[8];的可见巷道及与之相连接的巷道。如不被当前可见巷道区 域所包含，则改变当前的可见巷道区域的可见性，然后在int *RoadwayIndex; 上一次检测时搜索到的八叉树叶子节点L内检测其他巷} *Octree ; 道，如果有巷道区域包含相机C，则将这些区域标识为可Cubespace 表示是节点的正方形空间;child[8]是8见状态，如果该叶子节点内没有巷道区域包含相机，那么个子树;表RoadwayIndex是对穿越该节点的所有巷道区重新搜索T，找到新的叶子节点。域的索引。 3、算法 整个渲染算法描述如下: RENDERSCENE(AL, T) { L= AREASEARCH ( A,T,C); Render the visible areas; for ( each frame) { Search the current visible areas in the leaf L; if ( C is inside the current visible areas ) Render the current visible areas; else if (C is inside the other areas of L) Change areas’ visibility; Render visible areas; 图2.在八叉树中根据子空间的编号顺序存放子节点 else L= AREASEARCH ( A,T,C);4、结果 在配置为intel CPU 2.3G Hz/NAVID GF 6400 M/ Render the visible areas;Winxp 的笔记本电脑上，采用c++和OPENGL编程，我 们分别采用本文算法和LOD、BSP算法渲染一个包含66} 条巷道，720个模型，总面片数逾70万的井下场景。本 return; 文算法的平均帧率达到50FPS以上，速度明显超过了传} 统的LOD、BSP算法。表1列出了在相同的条件下，本因为八叉树每个节点产生八个子树，所以沿着八叉树文算法和LOD，BSP算法的渲染帧率比较。图3是利用搜索时，每向下前进一层，需要在下一层的八个子空间中本文算法渲染的的截图。因为不改变模型网格，所以对于进行包围检测。但是，因为相机始终是处于巷道中的，所较远的物体渲染质量不受影响。 以相机也始终处于八叉树的某些节点空间之内。我们可以 表1.本文算法和其他算法的效率比较 通过相机与当前节点立方体的8个顶点距离来判断相机 算法 巷道数 多边形数 平均FPS 处于哪一个子空间之内。方法是: LOD 66 7402000 30 BSP 66 7402000 35 在建立八叉树时，按照当前节点空间的八个顶点的位 置对定点进行编号(如图2所示)，每个顶点对应一个子本文算法 66 7402000 51 空间。子空间按编号顺序存放在数组child[]之中。 这样， 只需计算相机C距离哪个顶点最近，便可直接确定相机 处于哪个子空间，并在数组child[]中直接找到下一层节 点。如在图2中，相机离1号顶点最近，则从子节点child[0] 开始继续向下搜索。 设八叉树的深度为h。八叉树搜索的次数最多为h, 巷道区域包含检测最多为k次。所以，本算法的时间复 杂度为:O(h+k)。 2009, 61(11):20-28 [3] Li D. J.. Development of a Simulation System of Coal-Mine Work Training[J]. Applied Mechanics and Materials.2011:, Vol.94-96:2051-2056 [4] Mallett L., Unger R. Virtual reality in mine training.[R] Society for Mining, Metallurgy, and Exploration, Inc.,2007: 1-4. [5] 吴元峰，李大锦.一个煤矿作业仿真系统的开发[J].系统仿真学报, 2012,24(1):259-262. [6] 王兵建，周心权，王海燕等.煤矿重大事故模拟虚拟现实系统的开 发与应用[J].矿冶工程，2007,27(2):14-17. [7] James H. Clark. Hierarchical geometric models for visible surface algorithms [J]. Communications of the ACM. 1976, 19(10): 547 – 554 [8] Hoppe, H. Smooth view-dependent level-of-detail control and its application to terrain rendering[C]//In proceedings of Visualization Conference, IEEE Computer Society, 1998: 35-42. [9] Peter L., David K., William R. and etc. Real-time, continuous level of detail rendering of height fields[C]//In proceedings of SIGGRAPH’96, New York, ACM Press.1996: 109-118.. [10] Wolinsky, M., Sigeti, D.E.; Miller, M.C. and etc. ROAMing terrain: Real-time Optimally Adapting Meshes[C]// In proceedings of Visualization Conference’97. IEEE Press, 1997: 81-88, [11] Henry Fuchs, ZviM. Kedem,Bruce F.Naylor, On visible Surface Generation by a Priori Tree Structures[J]. ACM SIGGRAPH Computer 图3 本文算法渲染的图像结果 graphics, 1980,Vol. 14(3): 124 - 133 [12] Maciel P., Shirley, P.: Visual Navigation of Large Environments 5、结论 Using Textured Clusters [C]//Proceedings of the ACM Siggraph 本文提出的井下场景的实时渲染算法利用了巷道的Symposium on Interactive 3D Graphics’95, New York, ACM Press. 1995: 遮挡，通过简单的包围测试事先剔除了看不见的巷道，从95-102 而大量减少了渲染对象，有效地提高了渲染速度。与LOD[13]Jeschke S. Accelerating the Rendering Process Using Impostors[D]. 算法相比，本文算法不修改模型网格，所以能够保证图像PhD thesis, University Rostock, 2005. 质量。此外，在动态添加巷道模型时，也不像BSP树算[14] S. B. Kang. A survey of image-based rendering techniques, 法那样需要重新构建BSP树，只需要判断新添加的巷道VideoMetrics[J]. SPIE, 1999, 3641:2-16. 穿过八叉树的哪些叶子节点。所以本文算法简单，易实现。[15]Qin L.,Xiang W.,Yongjia Z. ShulingD., Real-Time Visualization for 还可以应用到其他室内场景的渲染。Large Scale Terrain Based on Linear Quadtree[C]//Proceedings of Asia Simulation Conference 2012, Berlin ,Germany, Springer, pp: 331-339. 参考文献 [16] D Demir, K Beketayev, GH Weber, PT Bremer, etc. Topology [1] Kizil M S, Hancock M G, Edmunds O T. Virtual Reality as a exploration with hierarchical landscapes[C]//Proceedings of the Training Tool [C]//Proceedings of the Australian Institute of Mining and Workshop at SIGGRAPH Asia 2012. New York, ACM press, 2012: Metallurgy Youth Congress, Brisbane, Australia, Australasian Institute of 147-154,. Mining & Metallurgy , 2001. pp: 9-12. [2] T J Orr, L G Mallet, K A Margolis. Enhanced fire escape training for mine workers using virtual reality simulation [J]. Mining Engineering:,