目前电缆三维设计成果体系已基本建立, 数字化设计成果的数据量越来越大, 三维可视化作为数字化成果的一部分, 其数据量也变得越来越大. 尤其在电缆工程的三维可视化中, 由于电缆和支架的几何结构简单, 并不会占据大量的内存空间, 而大量结构复杂的电缆井和管沟的三维模型则占据了接近80%的内存空间, 因此对电缆井和管沟进行模型简化, 减少存储的数据量是当前研究工作的重点与难点所在. 另外受限于软硬件技术的发展水平, 计算机无法实现短时间内加载大量数据的要求, 而且由于电缆铺设过程中具有线路繁复、模型复杂而且地形不确定性大等特点, 使得电缆铺设场景中三维模型的数据组织更加困难. 因此必须寻求一种适用于电缆工程的三维数据简化和组织调度方法, 来实现三维场景的快速显示和交互.

当前对电缆工程可视化的研究主要集中在三维管线可视化的研究, 文献[1]在原有的平面二维系统基础上引入了高程信息, 实现了由二维到三维的转变. 文献[2]主要利用近景测量技术与结构实体法对管线进行了三维建模, 然而该研究主要对地上管线有效, 对于重建大范围地下管线及管理具有一定的难度. 在文献[3]提出了一种去除三维模型冗余结构的简化方法, 但对于结构复杂的模型会存在过度简化的情况, 无法保留模型的特征信息. 同时在文献[4]中介绍了一种基于SQL Server和OpenGL的管线模型构建方法. 在文献[5]中介绍了基于ArcGIS Engine平台进行综合三维管线可视化的方法. 文献[6]为了运用GRASS实现三维可视化, 提出了基于PostgreSQL和PostGIS设计并构建地下管线综合数据库, 利用AutoCAD进行管线三维建模的方法. 在文献[7]中建立一种计算模型顶点曲率, 简化三角面片模型, 由曲率来决定权值比重的方法, 并将权值最小的三角形去除. 文献[8]对网格优化算法进行了改进, 引入了递进网格的相关概念. 而文献[9]为了提高大量数据条件下的地形渲染的效率, 提出了一种六边形的四剖分算法, 提升了LOD模型简化的精度, 提高了模型渲染的加载速度.

当前研究虽然对三维数据加载速度的提高有一定效果, 但数据存储量仍然较大. 针对目前存在的问题, 提出一种三维模型外表面提取算法来对电缆工程中的模型进行简化, 减小数据量. 因为电缆工程所具有的特殊性, 在三维场景中, 较低的LOD层级LOD1-2的情况下, 电缆线和支架占据内存量较大, 电缆井和管沟所占内存较小; 而在实际工程中, 大量应用的则是包含内外结构的更高等级的LOD, 即LOD3-4. 在LOD3-4中, 电缆井和管沟则占据了大量的内存, 电缆线和支架则对整个工程的数据量影响很小, 如图1所示. 所以将研究重点置于对电缆井和管沟进行简化的研究上^{[8, 9]}.

1 基于外表面提取算法的电缆场景三维模型简化设计 1.1 三维场景下的电缆工程细节层次模型

针对电缆场景下的电缆和支架模型结构较为简单的情况, 在实际工程中, 只需对其进行LOD1-2的两级定义. 电缆的两级LOD组织如下: LOD1是矢量点、线, 即显示的是电缆管线整体特征; LOD2是电缆管线的粗模, 是细节层次较为丰富的模型, 包含了电缆的外层结构^[10-12]. 而支架的两级LOD组织则是: LOD1是不具有厚度信息的矩形模型; LOD2是长方体的支架模型, 如图2所示.

相对于工程中结构较复杂的模型, 如电缆井、管沟而言, 则需要LOD层级更高更丰富的LOD模型来进行描述. LOD4层级的模型通常包含大量且较为详细的几何和语义的信息^[13]. 与LOD3模型相比, LOD4模型包含了模型的具体内部结构和特征. LOD3与LOD4之间的差异是巨大的. 因为LOD4模型不再是整体的块模型, 而是包含了对所描述物体的内部结构表示. 正是因为有了这样详细的信息, LOD4模型可以支持各种三维场景下的应用展示, 但同时由于CityGML中的LOD4模型在文件大小方面过于庞大, 无法在时效性要求较高的应用场景中有效地呈现和传输数据. 虽然与LOD4相比, 转化为LOD3模型后数据大小减小了很多, 但模型细节简化不够精细, 仍具有较多冗余部分而且有着较大的数据量^{[14, 15]}. 为此提出了一个新的子LOD, 它具有更小的文件大小, 更加简化的几何结构. 由于新提出的LOD包含内部结构特征, 即在LOD4和LOD3之间, 所以命名为LOD3.5. LOD3.5模型既具有丰富的数据, 足以进行可视化; 又能够支撑广泛的应用程序, 且需要比LOD3模型小得多的存储空间. LOD3.5和LOD3模型差距大的原因如下:

(1)在LOD3模型中, 一些模型表面的结构, 如电缆井的管线入口和出口具有较为复杂的形状, 而在LOD3.5中, 则只用一个表面来代表这些结构.

(2)在LOD3模型中, 包含着模型外表面的厚度信息, 而在LOD3.5中则不存在.

因此, LOD3.5模型可以保留三维模型的重要特性, 同时具有更小的数据大小.

如图3列举了电缆井中的转角井、四通井以及管沟进行LOD模型简化后的效果示意图.

1.2 模型外表面提取算法

在对电缆工程三维模型进行简化时, 提取模型的外部表面是必须进行的步骤. 虽然外部特征和内部特征可以在CityGML中定义, 但一些输入模型可能并不一定能够将这些特征区分为外部和内部. 例如, 从IFC或KML等其他数据格式转换而来的CityGML模型可能不会定义每个表面是内部还是外部. 因此, 我们需要为一些输入的模型找到外表面, 同时, 这也是LOD4到LOD3转换的一个重要步骤. 在三维环境中, 电缆井和管沟的外表面难以提取, 来形成CityGML的LOD3模型. 首先, 一个模型可能有不同的布局以及不同的高度, 这样不能通过简单地挤压来代表模型本身. 其次, 计算机程序很难确定电缆井和管沟的内部结构, 也很难找到它们的外表面, 而且在建模过程中还可能会出现大量的曲面结构, 增加了实现模型高精度简化的难度. 针对这些存在的问题, 对光线跟踪算法进行改进, 提出了一种模型外表面提取算法^[16-18]. 经过数据处理, CityGML模型被分解成多个具有相应语义信息的块模型, 通过检查这些块模型的可见性来找到外表面. 我们的算法如下: 第一步是找到外部, 它是建筑的一个包围球体, 如图4所示. 接下来, 检查每个表面对边界球上的点的可见性. 表面的可见性是由光线跟踪算法确定的, 假设观察光线从球面上的点发射. 例如, 如图4所示, 点P11在包围球上的任何一点上都不可见, 因此包含该点的任何表面都不能位于建筑模型的外部外壳上. 如果从表面随机生成的3个点在边界球上都是可见的, 那么这些表面就被认为是可见的, 因此在建筑的外壳上也是可见的. 为了避免一些外部表面在边界球中不可见的故障判断, 程序还会检查生成的外部壳体的连续性. 如果在表面上存在孔洞, 程序将再次检查孔洞内的表面, 看看它们是否是外部的. 算法的流程如算法1.

使用光线跟踪算法对建筑进行可见性检验, 对于从边界球上的给定点s射向目标表面上的点p的每一条光线, 可以表示为:

${I_s} + \left( {{I_p} - {I_s}} \right)t,t \in R$

(1)

其中, ${I_s} = \left( {{x_s},{y_s},{{\textit{z}}_s}} \right)$ 和 ${I_p} = \left( {{x_p},{y_p},{{\textit{z}}_p}} \right)$ 表示点s和点p的坐标. 对于模型中其他每一个点p,p所在的平面可以表示为:

${p_0} + \left( {{p_1} - {p_0}} \right)u + \left( {{p_2} - {p_0}} \right)v,u、v \in R$

(2)

其中, ${p_k} = \left( {{x_k},{y_k},{{\textit{z}}_k}} \right)$ k=0,1,2是曲面p上3个非共线点的坐标. 光线与平面的交点 $p'$ 计算公式为:

${I_s} + \left( {{I_p} - {I_s}} \right)t = {p_0} + \left( {{p_1} - {p_0}} \right)u + \left( {{p_2} - {p_0}} \right)v$

(3)

可以解得 $\left( {t',u',v'} \right)$ 为:

$\left[ \begin{array}{c} {t'} \\ {v'} \\ {u'} \\ \end{array} \right] = {\left[ {\begin{array}{*{20}{c}} {{x_s} - {x_p}}&{{x_1} - {x_0}}&{{x_2} - {x_0}} \\ {{y_s} - {y_p}}&{{y_1} - {y_0}}&{{y_2} - {y_0}} \\ {{{\textit{z}}_s} - {{\textit{z}}_p}}&{{{\textit{z}}_1} - {{\textit{z}}_0}}&{{{\textit{z}}_2} - {{\textit{z}}_0}} \end{array}} \right]^{ - 1}}\left[ {\begin{array}{*{20}{c}} {{x_s} - {x_0}} \\ {{y_s} - {y_0}} \\ {{{\textit{z}}_s} - {{\textit{z}}_0}} \end{array}} \right]$

(4)

如果 $p' = {I_s} + \left( {{I_p} - {I_s}} \right)t'$ 在表面P上, 则对 $p'$ 进行检测, 如果在P上, 则p在s上是不可见的. 完成外部提取算法后, 将外部壳体表面转化为LOD3建筑构件, 生成LOD3模型. 其他表面将在转换过程中被移除.

在实际的电缆工程应用中, 与LOD4模型相比, LOD3.5模型减少对三维模型厚度的渲染并不会影响实际的电缆模型展示效果和可视分析.

2 基于多细节层次的三维R-树索引数据调度方法

针对电缆工程三维数据量大, 存储路径多且复杂等特点以及其特有的查询需求, 特提出了一种基于多细节层次的三维R-树索引数据调度方法, 来对上文简化后的电缆井和管沟的三维LOD数据进行组织调度^[14]. 该方法的实施分为以下3个步骤.

(1)节点筛选. 根据节点筛选算法的原则: 先从底层节点向上进行筛选, 再从最高层节点向下进行一遍筛选. 接着将目标模型的数据插入. 由此可以避免节点重叠的情况出现, 也就可以避免由此带来的选择错误问题, 进而可以选出最优叶节点.

(2)节点分裂. 对于兄弟节点中所出现的各种情况, 如上溢现象、重叠等, 采用二分为三的算法进行分裂操作, 将出现上述现象的节点进行重组, 得到3个小节点. 在分裂后想要得到形状与尺寸均最优的节点, 就需要对发生重叠和覆盖的情况时, 节点的评价标准进行综合分析.

(3)多细节层次索引结构的建立. 经过前两步的节点筛选、节点分裂的操作, 已经使得生成的R-树具有了良好的树形, 可以使得重要模型的数据自动地分配到R-树的高层节点, 从而利用R-树来对数据进行高效的调用.

2.1 节点筛选算法

评判本算法是否最优, 取决于将目标模型的数据插入已选节点后, 将其上溯至根节点的路径上, 对于在路径上的各层节点的影响是否最小. 对于R-树结构的特殊性, 当原节点范围内出现新的模型目标时, 插入新数据的操作不会对节点和父节点的范围产生影响. 如果目标不再被包含在集合的所有子节点中, 那么就在集合中选择一个子节点, 当把目标模型的数据插入其中时, 使得该子节点的效果达到最优, 再依次向下进行遍历操作, 寻找最优节点, 直至叶节点所在, 即可停止^[19].

通常把覆盖范围和重叠范围作为R-树树形质量的评价标准, 但考虑到本索引方法对于多细节层次数据的调用功能的特殊性, 故对R-树的各层节点形状也有要求, 形状更接近于立方体为最佳, 即在三维空间中各个坐标轴上的长度要尽可能保证相等, 故定义了如式(5)所示的三维柯西值作为评价标准.

$\forall X,Y,Z > 0,\exists {\left( {\frac{{X + Y + Z}}{3}} \right)^3} \ge X \times Y \times Z$

(5)

只有在X、Y、Z相等时, 等式才成立. 假设 $X \times Y \times Z$ 的值一定, 当三者相等时, ${\left( {\dfrac{{X + Y + Z}}{3}} \right)^3}$ 的值最小, 此时节点在三维空间中的形状就更接近立方体. 所以, 将X、Y、Z三个赋予相同大小的权重值所得到的R-树为最优. 综合节点重叠、节点覆盖和节点形状这3个评价因子, 将评价标准定义为式(6)所示:

$Metric = \dfrac{1}{3}Overlap + \dfrac{1}{3}Overlay + \dfrac{1}{3}Shape$

(6)

定义节点的边长分别为X、Y、Z, Overlap代表模型数据插入子节点后, 该节点与相邻节点之间重叠部分的体积变化值; Overlay代表着该节点插入模型数据前后的体积变化值; Shape是由式(5)定义的三维柯西值的变化值. 具体的算法明细如算法2.

算法入口, R-树, 待插目标T: 简化后的电缆井和管沟三维模型子集.

算法出口, 经过选择的电缆井和管沟模型子集, 并命名为叶节点L.

2.2 节点分裂算法

R-树的子元组的数目是有限的. 当插入操作使得数目超过最大值时, 上溢的节点需要分裂为小节点. 这个过程是一种有约束的条件下在三维空间中进行分裂的过程. 在执行算法时, 一直坚持二分为三的原则. 当一个节点出现上溢现象时, 在其兄弟节点中寻找二者互相重叠最严重的节点, 把包含在这两个节点中的子元素分为三个子节点, 这样可以在减少重叠的同时, 对节点形状进行改进优化^{[20, 21]}. 对于没有重叠部分的兄弟节点, 继续沿用一分为二的方式. 最后, 对于分裂后的节点, 为其定义评价标准, 如式(7):

$Metric = \dfrac{1}{3}Overlap + \dfrac{1}{3}Overlay + \dfrac{1}{3}Shape$

(7)

为达到最优的算法效果, 将式(7)中的3个因子赋予相同的权重. 算法流程如算法3所示.

算法入口, 出现上溢现象的叶节点L1.

算法出口, 调整后的R-树.

2.3 多细节层次索引结构的建立

对于三维空间中的目标模型而言, 需要建立多尺度的LOD模型描述机制, 来对其内外部空间特征进行详细描述. 此外, 对于不同层级下的LOD模型进行简化, 可以实现对模型有选择性的筛选保留. 之前的算法所建立的R-树结构, 有着良好的树形, 基于此提出多细节层次三维R-树索引结构, 来对三维空间中的模型数据进行快速索引调用.

本方法与传统方法的不同点在于, 可以实现对重要目标模型数据的管理和调用. 对于子节点所管理的重要模型数据, 父节点可从中选择与子节点数目相同的重要模型数据, 此操作对于整个R-树的数据量影响有限.

从R-树的根节点开始, 向下进行遍历操作, 若对于其中的某节点, 视点距其的最小距离超过了该节点层次所描述的最远距离, 就不需要考虑其所包含的目标; 相反, 则需要考虑, 并对其进行描述. 在实际情况中, 要结合视距来选择合适的LOD模型.

3 实验结果与分析 3.1 实验环境设置

实验仿真基于北京市某区电缆设计工程, 运用本文方法对电缆三维场景的数据进行实验, 并测试可视化效果. 三维电缆井和管沟模型的数量为175个, 原始场景中总的数据量为2 GB. 算法的性能取决于两个因素: 1)存储模型数据量的大小; 2)查询相应时间. 数据量越小, 查询响应时间越短代表着算法越优.

具体的软硬件配置如表1所示.

3.2 结果分析

共进行3个实验, 对不同种类电缆井模型进行简化实验; 接着对简化后的模型进行响应时间与加载帧率的对比测试; 最后对整体三维场景下的漫游效果进行测试.

三维模型的结构简化与多细节层次索引结构调度的整体思想和流程如图5所示.

实验1. 电缆三维场景模型简化测试

在实验1中, 针对原始三维场景中占据大量内存的LOD4和LOD3层级的电缆井模型进行简化, 得到LOD3.5模型. 对比3种不同层级下的模型数据量, 选取了三种常见的电缆井模型, 分别是三通井、四通井和转角井. 可以看出, 简化后的模型不仅保留了原有模型的结构特征, 更大幅减小了数据量, 达到了预期实验目的. 结果如图6所示.

实验2. 对使用文中算法和使用传统R-树三维场景对比测试

1)查询响应时间的对比测试

首先用外表面提取算法对电缆三维场景中的模型进行简化, 使得整个三维场景的数据量大幅减小, 接着对简化后的数据分别应用本文算法和传统R-树索引算法进行索引组织调度. 实验在不同的尺寸比例下进行查询响应测试, 结果如图7所示, 随着比例的增加, 所需的查询时间也相应地增加. 在相同的比例下, 本文算法所需的时间要明显比传统R-树方法的短, 特别是随着比例的增加, 这种差别越来越明显, 本方法的优势也更加突出.

2)加载帧率的对比测试

通过Chrome Dev tools对电缆三维场景加载时间进行记录, 对使用本文算法和只使用传统R-树方法的三维电缆场景漫游过程分别记录加载帧率, 结果如图8所示. 先使用外表面提取算法对模型进行简化, 再用多细节层次的三维R-树索引数据调度方法实现的三维场景的加载帧率总体上要比只使用传统R-树方法实现的三维场景的帧率要高, 基本保持在40 fps左右.

实验3. 电缆工程三维场景图漫游效果测试

图9(a)为电缆三维场景中某一视点的三维场景全貌图, 图9(b)、图9(c)、图9(d)为该三维场景下的细节图, 在整个漫游缩放的过程中, 电缆工程中的模型显示流畅, 能够实现与用户的良好交互.

4 结论与展望

针对电缆三维场景下加载速度慢的问题, 本文提出了一种基于外表面提取算法的三维模型简化与多细节层次的三维R-树索引数据调度方法. 通过对占据大量内存的电缆井和管沟模型进行简化, 即保留了电缆三维场景的结构特征, 又大幅减小了数据存储量. 然后根据多细节层次的R-树索引结构组织调度简化后的模型数据, 最终能够实现提高电缆模型三维场景的加载速度, 有效实现了电缆工程中三维模型的流畅展示以及与用户的良好交互的目标. 为电网工程数字化移交中的三维场景的交互可视化提供了支撑方法. 下一步将电缆工程三维可视化技术应用到运检中, 进一步补充和完善相关技术, 实现对电缆工程的有效保障 .