The Research and Implementation in 3D Scene Real-time Speed-up Rendering Techniques

Abstract: 3D environment display is an important part in virtual reality research. According to the traits of large-scale scene rendering，the paper presents the speedup rendering method in LOD，memory management，multi-thread and data pre-fetching policy. Experiments show that these techniques speed up the rendering rate and improve the rendering effect.

Keywords: LOD，memory management，data pre-fetching，large-scale scene rendering

1 引言

三维场景的实时绘制技术一直是国内外的研究热点，近年来，通过国内外学者的不断努力，研究出了很多加速算法，主要有细节层次技术、几何数据高效表示技术、基于图像的绘制技术和基于点的绘制技术等。在大规模三维场景的实时绘制中，实时绘制技术的这些加速算法极大地提高了场景的绘制速度，满足了相关应用领域的各类需求。另一方面，在实际的系统开发和相关的技术应用中，对于大规模场景的实时绘制速度仍然还有进一步提高的需求。大规模的三维场景涉及到大量的空间数据，而计算机的内存资源和计算能力是有限的，这种矛盾决定了不可能将大规模三维场景的空间数据事先一次性调入内存，而必须是根据当前场景绘制的需要，在内外存之间进行动态的调度。数据调度的执行效率直接影响到场景绘制的连贯性和交互能力，对大规模空间数据的可视化效果具有举足轻重的作用，本文通过多层次细节模型、多线程处理以及数据预调度等策略的综合运用，改进了场景数据动态调度的效率，使场景绘制更加高效、流畅。

2 视点无关的多层次细节模型技术

视点无关多层次细节模型（view-independent LOD）技术[1]是利用预处理产生不同细节的多边形模型，存放在存储空间中，显示时根据视点的位置调用合适的细节模型，此后若视点改变再切换成不同细节的多边形模型。

多层次细节算法一般包含3个主要部分，分别是生成、选择以及切换。LOD的生成就是生成不同细节层次的模型表示，系统中采用手工方式生成具有不同细节层次的模型，每一个模型有3种不同细节层次，纹理大小分别为256×256、512×512和1024×1024。LOD选择的任务是在给定一个物体的细节层次时，必须做出一个选择，决定绘制其中的哪一个层次模型。本系统根据视点与模型节点的距离来决定选取模型的细节层次。如图1所示，细节层次最精细的LOD的距离是从0到一个自定义值r1之间，当到物体的距离小于r1时，这个LOD层次的模型是可见的。下一层的LOD距离在之间，其中，如果到物体的距离大于或者等于r1，同时小于r2，就使用这一层次的LOD。如果距离范围为（r2，r）3，则调用最粗糙的LOD模型来粗略表示物体。当距离大于r3时，物体由于距离视点较远，将不绘制该物体。

3 模型对象内存管理策略

在三维场景漫游系统中，场景模型数据量大，而显示设备的内存有限，很难把所有模型一次性加载到内存中。但若只加载当前视域范围内的模型到内存，当用户视域范围改变时，再从外存中调入所需数据，将大大增加场景绘制的时间，降低绘制效率。为此，若在内存中通过一定的规则保留部分已加载到内存中的模型，当视域范围改变时，只需加载不在内存中

本文采用最近未使用（Not Recently Used，NUR）算法来进行模型对象内存管理，实现该算法的基本设计思想是：在内存中开辟一个列表来存放当前已加载到内存中的模型，并为系统设定一个允许模型驻留在内存中的最大值。每一个加载到内存中的模型都会设置一个引用位，以此作为是否被替换的标志。当系统加载到内存中的数量未达到设定的最大值是，不删除内存中的模型，将模型直接加入到绘制列表中，否则根据模型节点引用位的值确定需要从内存中移除的模型。系统内存管理策略如图2所示。

运用该算法能有效地提高场景实时渲染的效率。当程序分别加载50、100、150个模型时，未使用该内存管理策略和使用内存管理策略的帧速率对比如表1所示。在使用了内容管理策略之后，模型数量分别为50、100和200时，场景绘制的帧速率分别提高了21.46%、30.02%和28.72%。

4 大规模三维场景实时漫游的多线程处理

在大规模三维场景实时交互绘制中，通过设置子场景的覆盖范围和观察者的可视区域，能够限制任一时刻最多有几个子场景与视景体部分相交。当观察者移动使得相交的子场景发生变化时，则需要进行数据调度，读入新的数据，释放旧数据所占用的内存空间。为了保持场景绘制的稳定连贯，不被数据调度过程中断，适合于采用多线程机制。实验证明，场景可视化处理与数据调度相比更复杂，需要花费更多的时间，因此在系统中使用一个后台数据调度线程用于数据预处理与调度和一个绘制线程用于场景绘制。

后台数据调度线程的主要任务是根据观察者的当前位置与运动参数，预先判断下一步将要“进入”可视区域的子场景，选择适当的时机将该子场景涉及的空间数据从硬盘读入内存；另外，将内存中暂时不需要绘制的子场景占用的空间释放。

当进入实时漫游状态，系统启动后台数据调度线程将初始的子场景数据调入，初始场景可以是固定的，也可由用户指定。由于不同子场景空间数据量不同，因此系统对预调度数据采用临时分配存储空间方式，将指向该数组空间的指针存放在用于与绘制线程通信的缓冲区中，同时将调入的子场景编号以及对应子场景中所加载的模型节点编号存放在缓冲区中。此外，随着观察视点的移动，后台数据调度线程根据视点位置、可视域参数、运动方向与速度，判断下一步哪些子场景与可视域相交，将当前不在内存中的场景数据加载到内存。

场景绘制线程的主要任务是利用OSG的绘制功能将绘制列表中的场景数据进行实时渲染，绘制出逼真的三维场景。由于后台数据调度线程主要负责预可见区域的计算和预可见数据的调度，然而，预可见区域的计算肯定会存在误差，所以系统在绘制线程中还需要根据当前的视点参数计算准确的可见区域，然后再判断是否当前可见区域范围内的所有可见子场景数据已加载到内存中，如果所需数据已加载到内存，那么绘制线程将进入实质性的绘制阶段，否则，系统将挂起后台数据调度线程，立即调入未加载的可见性数据。

由于后台数据调度线程和场景绘制线程两者之间是以一个三维子场景为单位实现数据交换，需要考虑两者之间的同步问题。因此对应每个子场景的数据空间增加InRendering和InReading互斥标志。InRendering如设置为True，表示该缓冲区中存放的场景数据已经进入绘制状态，后台数据调度线程应处于等待状态，直至该标志被设置为False，退出场景绘制状态。InReading若设置为True，表示该缓冲区中场景的数据正处于调度状态中，场景绘制线程处于等待状态，直至该场景的数据调度完成后，该标志设置为False。多线程机制的引入迎合了大规模三维场景实时绘制的特点，对实现大规模三维场景的实时交互漫游具有显著的优化作用。

5 数据预调度策略

为了保证场景绘制的连贯性，数据调度需要在场景进入可视范围之前完成，这就需要一个预判的过程。由于视点的移动通常是随意的，这种预判不可避免地带来一定的风险，可能发生的情况包括或将最终没有进入可视域的场景数据加载到内存，或者将马上要用到的场景数据没有加载到内存，又或是将马上用到的场景数据错误地释放掉，从而使得系统的处理效率反而极大地降低。在预判的方法上通过参数调整能够一定程度上降低风险，但不能完全避免。

熊汉江等人在文献0中提出了一种通过扩展当前可见区域作为预可见区域的预测方法，主要思想为：根据用户漫游的特点，将运动趋势归纳为前进、后退、左移、右移、左转和右转6种趋势。视景体不同的运动趋势确定了预可见区域不同，视景体运动趋势示意图如图4所示，其中图（a）～（f）分别对应前进、后退、左移、右移、左转和右转。如果在漫游中实时判断6种运动趋势所覆盖的预可见区域，然后再进行综合，会增加许多重复的计算，其中有些数据需要重复计算6次。若通过简单扩展当前可见区域的范围，得到一个能囊括所有运动趋势的规则等腰梯形范围，作为预可见区域，无论视景体以何种趋势运动，其所确定预可见区域都被包含在这个综合区域内。

由于视点位置和朝向可能变化的范围实际上由四个因素决定：当前视点参数向量，下一次决策的时延ε，用户的最大的直线运动速度和最大角速度ω。假设系统中与ω是固定的，则视点向量变化域的定义应该调整为，指整个视点向量取值域内除去预测结果其余的部分。当然，如果考虑到物体本身所占据的空间，那么预测失败情况下视点向量的变化范围还应该进一步缩小。为此，本文采用扩充实际的临域关系，使得它包含满足以下条件的所有视点参数：视点与或的距离小于等于㊣，并且角度变化最大为ωε，如图5中等腰梯形区域。其中表示视点向前运动，表示视点向后运动。

用上述数据预调度策略后，三维场景漫游系统中场景的绘制速率得到了一定的提高。实验环境：CPU为双核Intel（R） E8400 3.00GHz，显卡为ATI Radeon HD 2600 Pro，内存为2.00GB的计算机上，实验结果如表2所示。在实验中，系统分别加载了100、200、300个模型，使用未改进的预调度算法进行浏览，当进行右转操作时，系统的绘制帧速率分别为59.23、43.10、25.73，且在加载300个模型时伴有一定的“停滞”现象；使用改进后的预调度算法后，系统的绘制帧速率比改进前算法分别提高了11.847%、16.107%以及18.09%，且加载300个模型时“停滞”现象消除。

6 实验结果与分析

利用OSG与OpenGL相结合，作者实现了一个基于MFC的视景仿真平台。应用文中的场景实时绘制加速技术，在配置为CPU为双核Intel（R） E8400 3.00GHz，显卡为ATI Radeon HD 2600 Pro，内存为2.00GB的计算机上，对包含不同数目场景模型进行实时绘制实验，结果如表3所示：

从表3中可以看出，当系统加载模型数量为300个，总顶点数为119938、总绘制元素为265681后，平均帧速率从23.17提高到66.00；加载模型数量为400个，总顶点数为354244、总绘制元素为159918时，平均帧速率从19.01提高到55.87。实验结果显示，通过使用本文提出的内存管理策略、改进的数据预调度策略等加速策略提高了场景实时绘制的效率，能较好地实现大场景的动态可视化。

7 结束语

在分析了已有三维场景实时绘制技术的基础上，针对三维场景的特点，实现了基于MFC的视景仿真平台，综合运用视点无关的多层次细节技术、模型对象内存管理策略、大规模场景漫游的多线程技术以及数据预调度策略等实时绘制方法，实验表明，在大规模场景漫游系统中，文中的实时绘制技术有效地提高了场景绘制的速度，改善了场景实时浏览的效果。

参考文献

[1] 孟放，查红彬. 基于LOD控制与内外存调度的大型三维点云数据绘制[J]. 计算机辅助设计与图形学学报，2006，18（1）:1-8.

[2] 熊汉江，罗炜，王伟. 三维GIS中大规模地形数据的动态调度方法[J]. 测绘信息与工程，2006，31（3）:12-14.

[3] Christopher Zach and Konrad Karner. Prefetching policies for remote walkthroughs[R]. Technical report，VRV is Research Center，2001.