基于多细节层次结构扩展合并的快速三维可视化方法

文/李秀怡

基于多细节层次结构扩展合并的快速三维可视化方法

文/李秀怡

三维模型可视化技术近年来得到迅速发展，已经应用于如游戏、地理信息系统、电子商务展示等多个领域。随着移动终端的普及以及大数据时代的到来，对三维模型实时显示的速度和精度不断提出更高的要求。本文通过建立多细节层次结构，依据最小距离实现对相邻三维模型的扩展合并，以减少读取模型的数据量，达到简化模型的目的。通过实验研究证明，将其应用于三维可视化可以提高三维模型显示效率。

三维可视化 多细节层次模型 扩展合并

随着计算机视觉技术的快速发展，以及人们对信息实时共享和用户体验感受需求的不断提升，三维模型可视化技术近年来得到迅速发展，已经应用于如游戏、地理信息系统、电子商务展示等多个领域。三维模型的可视化功能对于路径导航、位置查询，以及信息展示有着重要的推动作用，在移动服务领域有着广阔的应用前景，人们可以通过移动终端设备获得当前所处城市位置，并获得身临其境的三维可视化服务（如信息推荐、商品展示以及室内导航等），极大地提高了三维模型可视化技术的普及率。然而，由于一些客观条件的影响，比如移动设备计算和存储能力较弱、无线网络带宽较小等，都会影响三维模型处理处理与显示的速度，降低客户端显示效果，影响用户体验度。而三维模型数据的传输和大量计算也需要较高配置要求，这些因素都可能阻碍三维可视化技术应用成果的普及。

为此，在本文中我们提出一种对多细节层次模型进行扩展合并的算法，基于此算法实现三维模型的快速动态可视化。这种方法可以在减少传输数据的同时，尽可能保留原模型的视觉特征，并且可以根据用户视点选择需要可视化的模型细节层次。在此过程中，三维模型的大小和清晰度可以随着用户视点而发生动态变化。

1 三维模型的多细节层次模型的产生

细节层次(Level ofDetail,简称LOD)模型是指对同一个场景或场景中的物体,使用具有不同细节的描述方法得到一组模型,供绘制时选择使用。由于人们通常用多边形网格(特例为三角形网格)来描述场景中的图形物体,因而LOD模型自动生成模型就转化为三维多边形网格简化问题。为物体提供不同的LOD描述是控制场景复杂度和加速图形绘制速度的一个非常有效的方法, LOD模型在复杂3D场景的快速绘制、飞行模拟器、3D动画、交互式可视化和虚拟现实等领域得到广泛应用。

LOD的生成可以追溯到20世纪80年代。1982年，Rubin[2]结合光线跟踪算法，提出了复杂场景的层次表示算法及相关的绘制算法,从而使计算机能以较少的时间绘制复杂场景。90年年代以后，随着虚拟现实和数据可视化等计算机新兴领域的出现，对交互式图形应用系统的图形生成速度提出更高的要求，随之掀起了对多LOD生成技术的研究热潮，诸多研究人员提出了很多有意义的研究结果。

2 三维可视化技术发展与应用

自从三维可视化技术得到广泛应用以来，在三维模型实现的算法精度与绘制速度之间一直存在着矛盾。虽然随着计算机新技术的发展不断有新算法提出，可以一定程度上缓解这种矛盾。但是大数据时代的到来，使三维场景应用的数据量急速膨胀，面向各种移动终端的应用需求也迅速扩展，使这种矛盾又变得突出起来。

目前的三维可视化技术水平，在处理医学影像、生物试验数据以及工程数据等方面配备优越的硬件设备，可以实现海量数据的显示与漫游，透视数据的内部细节，还可以对动静态分子结构数据进行可视化分析。目前的可视化技术手段已经深入化工、生物化学、制药等行业，应用于机械设计、通信、辅助设计领域，游戏、大地测量等领域，已经展示了其独特的优越性，取得了有目共睹的良好效果。

传统意义上的三维可视化技术是指运用计算机图形学和图像处理技术,将三维空间数据转换为二维图像或图形模型,并在计算机上显示、处理及交互的理论、方法和技术。而随着相关数据技术的不断深入发展，三维可视化技术在注重系统功能的同时也越来越注重用户的视觉体验度。当前三维可视化应用系统的基本框架包括数据采集与处理模块、三维模型生成模块和面向用户的浏览模块。本文的重点工作内容在后两部分，对三维模型细节进行相应处理，然后应用于可视化平台。

3 多细节层次结构扩展合并

3.1 三维场景模型间相邻关系检测

通过语义网格对三维场景中显示模型的全连接图进行剪枝分割，对分割后的连通子图，采用三角网生长算法生成Delaunay三角网。Delaunay三角网检测相邻关系具有以下特性：最接近、唯一性、最优性、最规则、区域性以及具有图多面体的外壳。图1给出了一个Delaunay三角网的示例。从图1中可以看出，Delaunay三角网能够较为准确的检测出模型之间的空间相邻关系，再通过对三角网的分割，删除节点不属于同一类型的边，则能准确找出模型之间的语义空间相邻关系，为模型合并做好准备。

图2：多细节层次模型生成

表1：动态可视化时间（毫秒）

3.2 多细节层次模型的生成与合并

在相邻关系的基础上，通过将最近的模型进行合并，从而生成多细节层次模型，如图2所示。图2中圆形表示原始三维模型。合并顺序的选择如下：计算每个模型之间的距离，按照距离由小到大的顺序进行合并，每一次合并后重新计算模型间的距离，并进行调整。具体而言，合并后节点的相邻节点是其子节点相邻节点的集合，合并后节点与其相邻节点之间的距离为其所有子节点与该相邻节点之间的最小距离。

模型之间的距离计算遵循如下原则：

（1）模型间距离为三维距离，充分考虑模型在三维空间的分布；

（2）模型间距离为模型所有几何特征之间的最近距离，即充分考虑模型本身的大小；

（3）模型间距离考虑模型的语义距离，即如果模型之间被网格分割，则模型间距离为无穷大。

按照上述方法生成多细节层次模型如下：模型1,2距离最近，首先进行合并生成D，然后4与5合并生成C，D与3合并后生成B，最后C与B合并生成A。

生成多细节层次模型之后，实现基于扩展的合并。设待合并模型为A与B，则分别对A与B的边进行延伸与连接，选择其中能够相交的模型，并计算相交后体积的增量，选择增量最小的模型作为合并后的结果。

对于一个二维模型合并情况的示例如图3所示。通过对边的延长，从而实现模型的合并。对于三维模型，则需要在每个平面上进行相应的操作。

图3：基于扩展的合并算法

4 快速三维可视化

多细节层次模型可以使用离线的方式生成，生成后存储于服务器，在需要时可以直接实现动态可视化，因此具有较高的效率。

基于合并后的模型实现快速三维可视化过程如下：

首先获取用户当前视点位置；基于多细节层次模型的根节点计算视点的角度是否包含，如不包含则不进行可视化；如果包含，则计算当前视点距多细节层次模型根节点之间的距离与根节点面积之比r，如果r大于所预设的值，则将根节点标注为可视并返回，否则，对于根节点的子节点进行上述计算与比较，并根据r与预设值的比较实现迭代处理，直到全部节点返回并选择出可视节点。预设值可以根据不同应用进行灵活调整，从而实现自适应的多细节层次结构。

在可视化实现过程中，将所要展示三维的多细节层次模型结构传输到浏览器，该结构不包括具体的几何信息只包含节点的相互关系与节点所指向的具体三维模型ID。然后获取用户当前视点并基于该视点与系统性能，在连续细节层次模型的架构上选择所需要载入的三维模型，并检测本地缓存中是否已载入，如没有则利用Websocket[7]将所需模型从服务器端载入并存储于本地缓存中。

5 实验结果

表1给出了本文所提出的算法对于三维模型可视化效率的提高实验，从中可以看出通过采用多细节层次模型，能够减少可视化耗时达到60%以上。

6 结束语

随着大数据时代的到来和图形图像技术的飞速发展，对三维模型实时显示的速度和精度不断提出更高的要求。本文通过建立多细节层次结构模型，依据最小距离实现对相邻三维模型的扩展合并，以减少读取模型的数据量和简化模型，进而达到提高三维可视化性能。今后将在三维模型纹理压缩等方面进行更深入研究，以期待更好的研究效果。

[1]潘志庚,马小虎,石教英.多细节层次模型自动生成技术综述[J].软件学报,1998,3(09).

[2]Run in SM.The representation and display of sense with a wide range of detail,The Graphics and Image Processing,1982(19):291-299.

[3]Hansen CD.The Visualization Handbook[M].Burlington:Elsevier Butterworth Heinemann,2005:30-34.

[4]朱恒.关于数字城市三维建模可视化技术分析[J].遥感测绘,2017(01).

[5]章孝灿,黄智才,戴企成,潘云鹤.GIS中基于拓扑结构和凸壳技术的决速TIN生成算法[J].计算机学报,2002.

[6]Bo Mao,Yifang Ban.Web-based Visualisation of the Generalised 3D City Models using HTML5 an X3DOM.

[7]Bo Mao,Zhiang Wu,Jie Cao.A Framework For online Spatio-Temporal data Visualization Based on HTML5. International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences, Volume XXXIX-B2,2012.XXII ISPRS Congress,25 August-01 September 2012,Melbourne,Australia.

作者单位江苏省电子商务省级重点实验室（南京财经大学） 江苏省南京市 210000

江苏省高校自然基金（16KJB520016）。

李秀怡（1979-），硕士研究生。研究方向为图像处理。