井下场景渲染.doc

矿山井下场景的实时渲染算法
李大锦1,白成杰2
(1山东师范大学传媒学院数字媒体系, 济南，山东，250014；2山东师范大学物理与电子科学学院，济南，山东，250014)
摘要：在虚拟数字化矿山中，由于井下涉及大量的巷道和机械设备，模型数据量巨大，因此严重制约了渲染速度。针对该问题，提出了一种井下虚拟场景的实时渲染算法。该算法将每个巷道作为一个区域，利用巷道的长方形包围盒进行相机的包围检测来确定相机位置，从而确定可见的巷道区域，在渲染时排除不可见的巷道。同时，为减少包围检测的计算，利用八叉树分割场景来缩小检测范围。实验结果显示该算法可大幅度减少渲染对象， 渲染速度明显优于传统的图形加速算法。
关键词：虚拟矿山；实时渲染；图形加速算法;八叉树
中图分类法：TP391.41 文献类型：A 文章编号：xxxxxxx
A Real-Time Rendering Method for Underground Mine Scenes
Dajin Li1，Chengjie Bai2
(1Department of Digital Media, Communication School of Shandong Normal University, Jinan 250014, China)
(2Physics 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、引言手稿日期：xxxxxxxxxxx 修回日期：xxxxxxxxxxxx
基金项目：山东省自然科学基金（NO.ZR2012FM029）
作者简介: 李大锦(1971－),男,江苏连云港人，讲师，研究领域为计算机图形学和虚拟现实技术。白成杰（1966-）男，济南人，教授，研究方向：图像处理

虚拟矿山是虚拟现实技术在矿业里的应用。借助虚拟数字化矿山系统，可实现井下场景漫游、矿井生产系统的计算机辅助设计、各生产环节的实时监管以及各类灾害的防控和预测。同时借助虚拟矿山环境，还可以完成各类生产操作的模拟训练和救援预案的演练。在虚拟地下矿山系统中，需要实时显示地下场景，这里遇到的一个关键问题是图形的实时显示。图形加速是计算机图形学研究中的主要内容。在通用的图形加速算法中，最经典的算法是层次细节算法（LOD）[7] 和BSP树算法[11]。其中，LOD算法根据视点相对模型的距离，随时改变模型的网格精度，从而减少渲染工作量。基于LOD算法思想，Peter 等[9]和Wolinsky 等[10] 针对大规模地形，分别给出了四边形和三角形网格的分解算法；BSP树是一个二叉分割树，可以对模型或场景进行多次划分，每次划分将场景分为两个部分，通过这种空间划分确定场景的可见多边形。除此之外，图形加速算法还有imposter 算法[12,13]、体素算法、布告板方法等。这类算法的基本思想是利用图像代替模型，从而提高渲染速度。因此这些算法都被称为基于图像的绘制算法[14]，Imposter算法是在一定的时间范围内，将较远的模型渲染成一幅纹理，并利用该纹理代替模型。
上述通用的加速方法可有效地减少渲染的多边形数量，尤其对于室外场景，能大幅度提高渲染速度。但矿山井下场景不同于一般的室外场景，渲染范围被限制在巷道内，在某一时刻，只需渲染极少的巷道及其内的模型。随着相机的移动，渲染范围也会发生较快的变化，如果单纯采用经典的LOD方法虽然也可以降低计算机的渲染负担，但是处于不可见范围内的模型仍然可能需要花费较多的时间来处理。传统的BSP树只能处理静态的场景，如果动态添加物体，需重新构建BSP树，而构建BSP树本身就是一个非常复杂的过程。在地下巷道中，由于可见的巷道长度一般情况下并不很长，因此 imposter算法也不能发挥其明显的优势。
对井下场景而言，提高渲染速度最有效的方法是确定场景在某一瞬间的可见巷道。本文根据井下场景的特点，给出了一种简单、快速的渲染算法。该算法通过判断相机位置来确定渲染范围，通过八叉树对井下场景进行分割，在计算可见范围时，先利用八叉树确定相机大概位置，再利用巷道的包围和进行相机的包围检测来确定巷道的可见性。
2、数据结构
我们将每一条巷道作为一个可见的区域，用一个表来索引巷道内的实体对象。如果相机处于该区域时，那么该区域的巷道处于可见状态。当相机靠近两个或多个巷道相交的交叉口时，相交的几个巷道都有可能是可见的。因此在渲染可见巷道的同时，渲染与之相连的巷道及其中的模型。同样，我们建立一个索引表来索引和当前巷道相连的所有其他巷道。在判断相机处于哪一个巷道区域内时，需要做包含测试。对于每一个巷道，构建其长方体包围盒，利用包围盒进行包围测试。一个巷道区域可用以下的结构体来表示：
typedef struct {
char * RoadwayName;
bool Viewable;
ObjectType *ObjList;
int *ConnectedRoadway;
BoxType BoudingBox;
}ViewArea;
其中，BoudingBox 是巷道区域的包围盒；变量Viewable代表当前巷道区域的可见性；列表ObtList存储了当前巷道内所有的实体对象。列表ConnectedRoadway建立了和当前巷道相连接的所有巷道的索引。
一个大型的虚拟矿山系统往往包含大量的巷道，如果将相机和所有巷道的包围体逐个进行包围检测，将严重降低渲染速度。我们采用八叉树来减少检测时间，将整个虚拟场景的最小包围正方体作为八叉树的根节点，然后依次将正方体平均分割为8个正方体空间（如图1所示）。如果假设在相连巷道的交叉口处，相连的巷道不超过k个，我们规定节点空间满足下列条件之一时停止空间分割：
a、节点空间包含的巷道数不超过k个。
b、节点空间不包含任何巷道。
c、节点空间小于或等于某个最小尺寸时。

a 井下各条巷道的包围盒

b 八叉树空间分割
图1.利用八叉树对场景进行分割

最小空间的大小可视情况而定，我们将之定义为最小巷道包围立方体的大小。一个巷道可能穿过八叉树的几个节点，因此八叉树的每个节点要建立对穿越该节点空间的所有巷道区域的索引。八叉树节点的数据类型用以下结构体定义：
typedef struct OCTRNODE{
CubeType Cubespace;
struct OCTRNODE *child[8];
int *RoadwayIndex;
} *Octree ;
Cubespace 表示是节点的正方形空间；child[8]是8个子树；表RoadwayIndex是对穿越该节点的所有巷道区域的索引。
3、算法
在系统的预处理阶段，构建所有的巷道区域，并建立一个巷道区域列表AL，然后对场景进行空间分割，建立八叉树T。如果场景不需要动态调入模型，AL和T一旦建立，则不需要改变。如果需要动态添加模型，而且添加的模型是巷道内的机械、材料等物体，只需将添加的模型加入到相应巷道区域的对象列表ObjList。如果动态调入巷道模型，则需要确定该巷道穿越哪些叶子节点，并在相应的叶子节点内添加对该巷道的索引。
如果当前活动相机为C，在确定可见区域时，从八叉树T的根节点的子树开始搜索，直到找到一个包围C的叶子节点L。对穿越该叶子节点的所有巷道区域进行包围测试，将包含C的巷道区域标识为可见状态。如果相机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)
AL[i]. Viewable=true;
All the areas connected to AL[i] are also
Set viewable }
Return L;
}
在检测可见区域时，为了减少八叉树搜索时间和包含检测时间，可利用上一次的检测结果。 在动画的每一个帧时间内，首先判断相机C是否仍然被当前的可见巷道区域所包含。如果被当前巷道区域包含，则直接渲染当前的可见巷道及与之相连接的巷道。如不被当前可见巷道区域所包含，则改变当前的可见巷道区域的可见性，然后在上一次检测时搜索到的八叉树叶子节点L内检测其他巷道，如果有巷道区域包含相机C，则将这些区域标识为可见状态，如果该叶子节点内没有巷道区域包含相机，那么重新搜索T，找到新的叶子节点。
整个渲染算法描述如下：
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;
else
L= AREASEARCH ( A,T,C);
Render the visible areas;
}
return;
}
因为八叉树每个节点产生八个子树，所以沿着八叉树搜索时，每向下前进一层，需要在下一层的八个子空间中进行包围检测。但是，因为相机始终是处于巷道中的，所以相机也始终处于八叉树的某些节点空间之内。我们可以通过相机与当前节点立方体的8个顶点距离来判断相机处于哪一个子空间之内。方法是：
在建立八叉树时，按照当前节点空间的八个顶点的位置对定点进行编号（如图2所示），每个顶点对应一个子空间。子空间按编号顺序存放在数组child[]之中。 这样，只需计算相机C距离哪个顶点最近，便可直接确定相机处于哪个子空间，并在数组child[]中直接找到下一层节点。如在图2中，相机离1号顶点最近，则从子节点child[0]开始继续向下搜索。
设八叉树的深度为h。八叉树搜索的次数最多为h, 巷道区域包含检测最多为k次。所以，本算法的时间复杂度为：O(h+k)。

图2.在八叉树中根据子空间的编号顺序存放子节点
4、结果
在配置为intel CPU 2.3G Hz/NAVID GF 6400 M/ Winxp 的笔记本电脑上，采用c++和OPENGL编程，我们分别采用本文算法和LOD、BSP算法渲染一个包含66条巷道，720个模型，总面片数逾70万的井下场景。本文算法的平均帧率达到50FPS以上，速度明显超过了传统的LOD、BSP算法。表1列出了在相同的条件下，本文算法和LOD，BSP算法的渲染帧率比较。图3是利用本文算法渲染的的截图。因为不改变模型网格，所以对于较远的物体渲染质量不受影响。
表1.本文算法和其他算法的效率比较
算法
巷道数
多边形数

平均FPS
LOD
66
7402000
30
BSP
66
7402000
35
本文算法
66
7402000
51

图3 本文算法渲染的图像结果
5、结论
本文提出的井下场景的实时渲染算法利用了巷道的遮挡，通过简单的包围测试事先剔除了看不见的巷道，从而大量减少了渲染对象，有效地提高了渲染速度。与LOD算法相比，本文算法不修改模型网格，所以能够保证图像质量。此外，在动态添加巷道模型时，也不像BSP树算法那样需要重新构建BSP树，只需要判断新添加的巷道穿过八叉树的哪些叶子节点。所以本文算法简单，易实现。还可以应用到其他室内场景的渲染。
参考文献
[1] Kizil M S, Hancock M G, Edmunds O T. Virtual Reality as a Training Tool [C]//Proceedings of the Australian Institute of Mining and Metallurgy Youth Congress, Brisbane, Australia, Australasian Institute of 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:, 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 graphics, 1980,Vol. 14(3): 124 - 133
[12] Maciel P., Shirley, P.: Visual Navigation of Large Environments Using Textured Clusters [C]//Proceedings of the ACM Siggraph Symposium on Interactive 3D Graphics’95, New York, ACM Press. 1995: 95-102
[13]Jeschke S. Accelerating the Rendering Process Using Impostors[D]. PhD thesis, University Rostock, 2005.
[14] S. B. Kang. A survey of image-based rendering techniques, 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 exploration with hierarchical landscapes[C]//Proceedings of the Workshop at SIGGRAPH Asia 2012. New York, ACM press, 2012: 147-154,.