基于自适应R-树的大数据量铁路三维设计模型渲染方法

摘要

本发明公开一种基于自适应R-树的大数据量铁路三维设计模型渲染方法，按下列步骤进行：在铁路三维设计软件中生成铁路线路、站场、路基、桥梁和隧道等专业的设计方案；生成铁路各专业设计方案对应的三维模型，统称为铁路三维设计模型；实现适应设计方案频繁调整并匹配三维设计模型空间分布形态的自适应R-树；使用自适应R-树存储铁路三维设计模型；在铁路各专业设计方案优化调整过程中更新自适应R-树；在铁路三维设计软件的场景渲染过程中使用基于自适应R-树和缓冲区的模型滤除方法。有益效果是：在普通显卡条件下大幅度提高了大数据量铁路三维设计模型的渲染速度，使得铁路三维设计软件能够在广大铁路设计人员的普通PC中流畅运行，摆脱了对高性能图形工作站的依赖。

说明书

技术领域

本发明涉及地理信息系统和铁路设计技术领域，具体的说是一种基于自 适应R-树的大数据量铁路三维设计模型渲染方法，该方法可用于铁路三维 设计软件的开发实现。

背景技术

随着计算机软、硬件技术的发展，铁路三维设计技术逐渐走向成熟。铁 路系统比较复杂，涉及线路、站场、路基、桥梁和隧道等数十个设计专业， 并且经过的省、市地域广，空间跨度大，这决定了铁路三维设计模型的数据 量相当巨大。采用一般的渲染方法直接绘制大数据量的铁路三维设计模型， 对计算机显卡的绘图性能要求非常高，需要高性能图形工作站才能够正常显 示出图形效果。如果不解决普通显卡条件下的大数据量铁路三维设计模型渲 染速度慢的问题，铁路三维设计软件也就无法在广大铁路设计人员的普通 PC机中推广使用。

普通显卡条件下的大数据量三维模型渲染的核心思想是：在场景渲染阶 段使用基于空间索引的模型滤除方法，对无需绘制的三维模型进行快速滤 除，减少显卡的绘图数据量，从而提高渲染速度。其中，滤除的速度主要由 空间索引的检索效率决定。不同的空间索引适合不同分布形态的三维模型， 合适的空间索引匹配合适的空间分布形态，才能产生最高的检索效率，才能 最大程度的提高渲染速度。

传统的大数据量三维模型渲染方法主要使用格网、BSP树、四叉树和八 叉树等规则型空间索引技术，适合于在空间各个方向分布较为均匀的三维模 型。铁路空间跨度大，并且沿线设施集中于线路附近，这决定了铁路三维设 计模型的空间分布形态为大范围、狭长条带状、不规则空间分布，显然与传 统方法的空间索引不匹配。相对而言，R-树更适合铁路三维设计模型的空间 分布形态，但是各专业设计方案不断进行优化调整的过程中，可能会频繁触 发比较费时的R-树节点分裂或结构紧凑操作，从而影响铁路设计的工作效 率，还可能使R-树的深度和广度比例失衡，导致R-树的检索效率降低。

发明内容

本发明的目的在于克服上述已有技术的缺点，提出一种普通显卡条件下 的大数据量铁路三维设计模型快速渲染方法，使铁路三维设计软件能够在广 大铁路设计人员的普通PC机中较为流畅的运行，摆脱对高性能图形工作站 的依赖。

本发明的技术方案是：一种基于自适应R-树的铁路三维设计模型渲染 方法，具体包括以下步骤：

（1）在铁路三维设计软件中生成铁路线路、站场、路基、桥梁和隧道专 业的设计方案；

（2）生成上述铁路各专业设计方案对应的三维模型，统称为铁路三维设 计模型；

步骤（1）和（2）已有成熟技术。

（3）实现适应设计方案频繁调整并匹配三维设计模型空间分布形态的自 适应R-树：

3-1）自适应R-树数据结构：

3-1-a）将自适应R-树的数据结构派生于Guttman R-树数据结构，继承 Guttman R-树的所有特征；

步骤3-1-a）已有成熟技术。

3-1-b）将自适应R-树的叶子节点中存储的空间对象分为有效对象和无 效对象；

3-1-c）在自适应R-树的数据结构内设一个有效对象数组，用于存储所 有叶子节点中的有效对象；同时内设一个计数变量统计叶子节点中存储的无 效对象的个数；

3-2）自适应R-树的插入方法：

3-2-a）使用Guttman选择叶子节点方法，在自适应R-树中选中待插入 的有效对象应该存入的叶子节点；

3-2-b）在步骤3-2-a）选中的叶子节点中查找第一个无效对象，如果找 到，则将待插入的有效对象存储到第一个无效对象所占用的存储位置，然后 自底向上更新自适应R-树的各层节点的包围盒，从而避免触发费时的自适 应R-树的节点分裂操作；如果没有找到，则执行步骤3-2-c）；

3-2-c）使用与Guttman插入方法插入当前处理的有效对象；插入成功之 后，判断自适应R-树的深度是否超过单个叶子节点的最大存储空间对象个 数M；如果超过，则销毁自适应R-树的所有节点，计算合适的M值，然后 对有效对象数组中的空间对象使用Guttman插入方法重新生成各层节点，从 而优化R-树的深度和广度比例；

3-2-d）M值通过枚举逼近法求解以下方程得到：

M^(M+1)<=N，

式中：M为单个叶子节点的最大存储空间对象个数，N为有效对象数组 中的元素个数；

3-3）自适应R-树的删除方法：

3-3-a）使用与Guttman查找叶子节点方法，找到当前处理的有效对象所 在的叶子节点；

3-3-b）在步骤3-3-a）中找到的叶子节点中，将待删除的有效对象所在 的存储位置用无效对象代替，并从有效对象数组中删除待删除的有效对象， 从而避免触发费时的R-树的结构紧凑操作，同时无效对象计数增加1；

3-3-c）判断无效对象个数是否超过有效对象的个数，如果超过，则销毁 自适应R-树的所有节点，计算合适的M值，然后对有效对象数组中的空间 对象使用Guttman插入方法重新生成各层节点，优化自适应R-树的深度和 广度比例；

3-3-d）M值通过枚举逼近法求解以下方程得到：

M^(M+1)<=N，

式中：M为单个叶子节点的最大存储空间对象个数，N为有效对象数组 中的元素个数；

（4）使用自适应R-树存储铁路三维设计模型：

4-1）将铁路三维设计模型类派生于步骤3-1-a）的有效对象类，从而保 证自适应R-树的叶子节点能够存储铁路三维设计模型；

步骤4-1）已有成熟技术。

4-2）使用步骤3-2）的自适应R-树的插入方法将铁路线路、站场、路基、 桥梁和隧道专业的三维设计模型插入到自适应R-树中；

（5）在铁路各专业设计方案优化调整过程中更新自适应R-树：

5-1）优化调整铁路线路、站场、路基、桥梁和隧道专业的某一个设计 方案，形成新的设计方案；

5-2）使用步骤3-3）的自适应R-树的删除方法将步骤5-1）中优化调整 的设计方案对应的三维设计模型删除，然后将上述三维设计模型从计算机内 存中删除；

5-3）对步骤5-1）中新的设计方案，生成新的三维设计模型，然后使用 步骤3-2）的自适应R-树的插入方法将上述新的三维设计模型插入到自适应 R-树中；

（6）在铁路三维设计软件的场景渲染过程中使用基于自适应R-树和缓 冲区的模型滤除方法：

6-1）提供输入接口，允许用户在输入两个缓冲区参数阀值，分别为可 视空间范围包围盒在X轴和Y轴方向的变化值，目的在于避免不必要的重 复检索自适应R-树；

6-2）进行第一次场景渲染时，以当前可视空间范围的包围盒在X和Y 轴方向外扩给定阀值后的包围盒为输入条件，检索自适应R-树，获得树中 所有与上述外扩后的包围盒存在空间范围重叠的铁路三维设计模型，送达显 卡进行渲染，从而不重叠的三维设计模型被滤除，减少了显卡的绘图数据量；

6-3）实时监测当前可视空间范围是否发生变化；如果当前可视空间范 围没有发生变化，则不断执行步骤6-3）；如果当前可视空间范围发生变化， 则判断当前可视空间范围的包围盒相对上一次场景渲染时可视空间范围的 包围盒的变化幅度是否超出给定的阀值，并按以下步骤处理：

6-3-a）如果X轴和Y轴两个方向都未超出阀值，则显卡仍然绘制将上一 次场景渲染时的数据，从而避免了不必要的重复检索自适应R-树；

6-3-b）如果X轴和Y轴任意一个方向超出阀值，则执行与步骤6-2）中 第一次场景渲染时相同的处理，然后执行步骤6-3）。

本发明的显著效果是：在普通显卡条件下大幅度提高了大数据量铁路三 维设计模型的渲染速度，在相关对比测试中发现提速幅度达170%～210%， 使得铁路三维设计软件能够在广大铁路设计人员的普通PC中流畅运行，摆 脱了对高性能图形工作站的依赖，促进了铁路三维设计软件的推广和使用。

附图说明

图1为本发明的流程步骤图；

图2为本发明的自适应R-树的插入方法的工作流程图；

图3为本发明的自适应R-树的删除方法的工作流程图；

图4为本发明基于自适应R-树和缓冲区的模型滤除方法的工作流程图；

图5为本发明的可视空间范围包围盒的变化缓冲区概念示意图；

图6（a）为本发明用于效果验证的铁路线路、路基和桥梁三维设计模型；

图6（b）为本发明用于效果验证的铁路线路、路基和隧道三维设计模型；

图6（c）为本发明用于效果验证的铁路线路、路基和站场三维设计模型；

图7为使用本发明技术前后的大数据量铁路三维设计模型渲染速度对比 图；

图8为使用本发明技术后大数据量铁路三维设计模型渲染速度增幅示意 图。

具体实施方式

如图1所示，以C++程序设计语言和OpenGL绘图环境为例，基于自适 应R-树的大数据量铁路三维设计模型渲染方法按照以下步骤实施：

（1）在铁路三维设计软件中生成铁路线路、站场、路基、桥梁和隧道等专 业的设计方案。

（2）生成铁路各专业设计方案对应的三维模型，统称为铁路三维设计模 型。

步骤（1）和（2）已有成熟技术。

（3）实现适应设计方案频繁调整并匹配三维设计模型空间分布形态的自 适应R-树：

3-1）改进Guttman R-树的数据结构，形成自适应R-树数据结构：

3-1-a）将自适应R-树的数据结构派生于Guttman R-树数据结构，继承 Guttman R-树的所有特征；

步骤3-1-a）已有成熟技术。

3-1-b）将自适应R-树的叶子节点中存储的空间对象分为有效对象和无 效对象；实现一个空间对象类、一个有效对象类和一个无效对象类，其中有 效对象类和无效对象类都从空间对象类派生；所有插入自适应R-树的空间 对象都是有效对象，当一个对象从自适应R-树中删除后，在上述删除对象 所在叶子节点中的存储位置用一个无效对象代替删除前的对象，无效对象与 删除前的有效对象具有相同的包围盒数据，但是没有图形数据；

3-1-c）在自适应R-树的数据结构内设一个有效对象数组，用于存储所 有叶子节点中的有效对象；同时内设一个计数变量N₁统计叶子节点中存储 的无效对象的个数；

3-2）如图2所示，改进Guttman R-树的插入方法，降低铁路各专业设 计方案频繁调整时触发R-树节点分裂操作的概率，并自动优化R-树的深度 和广度比例，形成自适应R-树的插入方法：

3-2-a）使用Guttman选择叶子节点方法，在自适应R-树中选中待插入 的空间对象O₁应该存入的叶子节点L₁；

3-2-b）在叶子节点L₁中查找第一个无效对象；如果找到，则将O₁存储 到第一个无效对象所占用的存储位置，然后自底向上更新自适应R-树的各 层节点的包围盒；如果没有找到，则执行下一步；

3-2-c）使用与Guttman插入方法，将O₁存储到L₁中，然后判断自适应 R-树的深度h是否超过单个叶子节点的最大存储空间对象个数M；如果超 过，则销毁自适应R-树的所有节点，计算合适的M值，然后对自适应R-树 中的有效对象使用Guttman插入方法重新生成各层节点，优化R-树的深度 和广度比例；

3-2-d）M值通过枚举逼近法求解以下方程得到：

M^(M+1)<=N，

式中：M为最大存储空间对象个数，N为自适应R-树中的所有有效空间 对象个数；

3-3）如图3所示，改进Guttman R-树的删除方法，降低铁路各专业设 计方案频繁调整时触发R-树结构紧凑操作的概率，并自动优化R-树的深度 和广度比例，形成自适应R-数的删除方法：

3-3-a）使用Guttman查找叶子节点方法，找到待删除的空间对象O₂所 在的叶子节L₂；

3-3-b）在删除叶子节点L₂中的空间对象O₂时，将O₂所在的存储位置 用无效对象代替，无效对象个数N₁增加1，并从有效对象数组中删除O₂；

3-3-c）判断无效对象个数N₁是否超过有效对象的个数N₂；如果超过， 则销毁自适应R-树的所有节点，计算合适的M值，然后对自适应R-树中的 有效对象使用Guttman插入方法重新生成各层节点，优化R-树的深度和广 度比例；

3-3-d）M值通过枚举逼近法求解以下方程得到：

M^(M+1)<=N，

式中：M为最大存储空间对象个数，N为自适应R-树中的所有有效空间 对象个数；

（4）使用自适应R-树存储铁路三维设计模型：

4-1）将铁路三维设计模型类派生于步骤3-1-a）的有效对象类，从而保 证自适应R-树的叶子节点能够存储铁路三维设计模型；

步骤4-1）已有成熟技术。

4-2）使用步骤3-2）的自适应R-树的插入方法将铁路线路、站场、路基、 桥梁和隧道专业的三维设计模型插入到自适应R-树中；

（5）在铁路各专业设计方案优化调整过程中更新自适应R-树：

5-1）优化调整铁路线路、站场、路基、桥梁和隧道专业的某一个设计 方案，形成新的设计方案；

5-2）使用步骤3-3）的自适应R-树的删除方法将步骤5-1）中优化调整 的设计方案对应的三维设计模型删除，然后将上述三维设计模型从计算机内 存中删除；

5-3）对步骤5-1）中新的设计方案，生成新的三维设计模型，然后使用 步骤3-2）的自适应R-树的插入方法将上述新的三维设计模型插入到自适应 R-树中；

（6）如图4所示，在铁路三维设计软件的场景渲染过程中使用基于自适 应R-树和缓冲区的模型滤除方法：

6-1）提供输入接口，允许用户在输入两个缓冲区参数阀值dX和dY， 如图5所示，分别为可视空间范围包围盒在X轴和Y轴方向的变化值，目 的在于避免不必要的重复检索自适应R-树；在OpenGL绘图环境中，可视 空间范围是OpenGL中的视景体范围；

6-2）场景渲染是计算机显卡不断重绘铁路三维设计模型的过程；进行 第一次场景渲染时，以当前可视空间范围的包围盒E₁在X和Y轴方向外扩 给定阀值后的包围盒E₂为输入条件，检索自适应R-树，获得树中所有与E₂存在空间范围重叠的铁路三维设计模型，送达显卡进行渲染，从而不重叠的 三维设计模型被滤除，减少了显卡的绘图数据量；

6-3）实时监测当前可视空间范围是否发生变化；如果当前可视空间范 围没有发生变化，则不断执行步骤6-3）；如果当前可视空间范围发生变化， 则判断当前可视空间范围的包围盒E₁相对上一次场景渲染时可视空间范围 的包围盒E₀的变化幅度是否超出给定的阀值dX和dY，并按以下步骤处理：

6-3-a）如果X轴和Y轴两个方向都未超出阀值，则显卡仍然绘制将上一 次场景渲染时的数据，从而避免了不必要的重复检索自适应R-树；

6-3-b）如果X轴和Y轴任意一个方向超出阀值，则执行与步骤6-2）中 第一次场景渲染时相同的处理，然后执行步骤6-3）；

本发明基于自适应R-树的大数据量铁路三维设计模型渲染方法的效果 通过以下实验数据体现：

1.实验条件

实验采用的PC机CPU型号为Intel Core i5CPU6503.2GHZ，内存为 DDR3类型3.5GB容量，显卡型号为NVIDIA GeForce405。实验采用一个自 主研发的铁路三维设计软件，数据为大饭铺至马栅铁路可行性研究阶段的铁 路三维设计模型，包括线路、站场、路基、桥梁和隧道等专业三维设计模型 共计约7000个，三维场景的局部渲染效果如图6（a）、图6（b）和图6（c） 所示。在铁路三维设计软件中，预先设定自适应R-树的叶子节点的最大存 储空间对象个数M值为6，经过自适应R-树插入操作，最终建立的自适应 R-树深度为5，叶子节点的最大存储空间对象数M值仍然为6，R-树的深度 和广度比例比较平衡。

2.试验结果

帧率是反映渲染速度的一个重要指标，含义为场景不断刷新时，显卡每 秒钟所绘制场景数中铁路三维设计模型的次数。帧率的值越大，代表渲染速 度越快。在同样显卡配置条件下，渲染速度越快，则表明铁路三维设计软件 对硬件配置要求越低。帧率可以采用多次绘制取平均的方法进行计算，计算 公式如下：

$\mathrm{FPS}=\frac{N}{\underset{i=0}{\overset{N}{\Sigma }}{T}_i/1000},$

其中，FPS为帧率，N为绘制次数；T_i为第i次绘制耗费的时间，单位为毫 秒。

预先对系统中的所有铁路三维设计模型建立显示列表，然后以50米为 步长，沿铁路线路对大饭铺至马栅的所有铁路三维设计模型进行虚拟现实漫 游，每5步计算并输出一次帧率数值。测试结果如图7所示，发现使用本发 明方法后自主研发的铁路三维设计软件渲染速度相对全部模型直接绘制的 方法明显提高。帧率增加的幅度如图8所示，发现最低增幅达到170%左右， 最高增幅达到210%左右。