基于World Wind 三维模型加载的视锥裁剪改进算法研究
时间：2022-09-08 07:51:24
摘要：为了解决World Wind中三维模型加载速度慢、效率低、占用内存高、显示效果不佳等问题。该文通过研究World Wind运行机制，分析三维模型的显示原理并对其显示过程中所采用的视锥裁剪算法进行了改进。实验结果表明，该文提出的视锥裁剪改进算法可有效提高三维模型加载速度，减小内存占用率，为基于world wind的后续研究打下良好基础。
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）10-2414-04
Abstract： In order to solve the problem of 3D Model loading in the World Wind， for example low speed， low efficiency， high memory and the display effect is not well and so on. By studying the World Wind running mechanism. This paper analysis of the 3D model which used for the display principle and improved the frustum culling algorithm which be used in the process of showing . the experimental results shows that the 3D model loading becomes faster and the footprint smaller. Now there will be a good basis of the further research based on World Wind.
Key words： World Wind；3D model；frustum culling
随着地理信息技术的快速发展，越来越多的科研机构和科技公司开始研发三维地理信息系统。在众多三维地理信息系统中，美国NASA开发的World Wind因其开源性而受到了广大科研人员的青睐。在多数以World Wind为平台的科研开发中，一般需要先将三维模型加载于其中，而后再依照所需进行后续研究。然而三维模型在加载World Wind的过程中，往往会出现加载速度慢、效率低、占用内存高、显示效果不佳等问题，为后续科研带来很大不便。
针对以上问题，该文基于World Wind的运行机制，对其内部的瓦片金字塔结构以及用于三维模型显示的视锥裁剪算法进行了研究。在对World Wind视锥裁剪算法分析后发现三维模型加载问题大多与此有关。通过比较多种视锥裁剪算法后，基于World Wind特性，该文改进了World Wind原有视锥裁剪算法[1]。经实验表明，改进后的视锥裁剪算法有效的解决了World Wind中三维模型加载速度慢等问题。
1 World Wind
1.1World Wind概述
World Wind是美国NASA研发的开放性三维地理信息系统。在数据源方面，World Wind依借NASA庞大的卫星资源，可以随时调用MODIS、Landsat、GLOBE、SRTM等多颗卫星的数据信息[2]。同时再将Landsat卫星数据图像和雷达遥感数据结合后，通过World Wind界面，用户可以感受到遨游三维地球的美妙体验。World Wind不仅提供了地球数据，还提供了月球数据。在浏览地球的同时，用户还可以通过World Wind近距离的观测月球。 World Wind还能自动更新卫星数据，这使得World Wind可以在全球范围内跟踪火山爆发、海啸、地震以及各种近期事件。而且根据用户需要，World Wind还提供了城市、交通、经纬线、国界等参考层。同时在World Wind三维地球仪上，还可以接收到来自GPS接收机的数据以及各种坐标信息。
此外，用户还可以对界面中的地球或者其他行星进行放大、缩小、旋转、倾斜等操作。同时World Wind还提供了与软件功能相对应的卫星数据层次，用户可按需进行调整。如图1所示。
1.2 World Wind瓦片金字塔体系
为了解决模型加载问题，该文深入World Wind内部研究其运行机制。在具体研究中，该文发现World Wind采用了瓦片金字塔模型结构体系。把一幅图像按照一定的比例尺寸分割成若干的小正方形栅格，其中每个栅格就是一张瓦片[3]。在瓦片的基础上，把一幅图像由小到大依次分割成多个区域。分割后，就会按照层级呈现出数据量由少至多、图像比例由小到大的无顶金字塔结构。如图2所示。
根据瓦片金字塔结构[4]，我们可以将World Wind分割成以下形态。如图3所示。
构建瓦片金子塔时，首先定义其第0层，把原始数据作为底层，然后按照需求进行分块，形成第0层瓦片矩阵。由第0层做基础，按照每2*2个像素合成1个像素的方法构建第1层，依照先例对其分块，形成第1层瓦片矩阵。以此类推，最终构成整个瓦片金字塔[5]。瓦片金子塔的优势在于它是一种类似于多分辨率的层次模型，能够在提高显示速度的前提下保证显示精度。在地形绘制时，根据不同区域的特征，往往需要不同分辨率的纹理影像数据和高程模型数据。针对这种情况，影像金字塔和数字高程模型金字塔无需进行实时重采样就可为其提供数据。
作为大型三维地理信息系统，World Wind需要对海量的数据进行处理。在具体的运行中，得益于瓦片金字塔结构体系，World Wind可以在减少完成地形绘制所需总耗时的前提下提高系统的输出输入执行效率，进而提升系统的整体性能。
2 三维模型加载
2.1 KML与KMZ
由于World Wind不提供房屋建筑等三维模型数据，所以在进行与三维模型有关的研究时，首先需要去采集三维模型数据。由于制作三维模型费时费力，对科研进度有很大影响。为了省时省力，在对三维模型没有特定要求的情况下，科研人员一般都会选择从互联网上下载三维模型来进行相关研究。
鉴于KML文件具有海量的模型库，World Wind也提供了KML模型文件的加载接口。因此下载三维模型时，KML文件成为科研人员的首选。KML是一种基于XML文件格式和语法的语言，同XML一样，KML里面包含了属性、名称等标签来显示模型信息，如点坐标、经纬度、高度以及超链接等[6]。KML文件、dae文件、图片文件夹，三者共同压缩后形成可加载的KMZ三维模型文件。
2.2 KMZ文件批量加载的实现
由于World Wind提供的KMZ文件加载接口每次只能加载一个三维模型，而针对三维模型的研究往往需要对一定区域的多个三维模型进行加载。为了解决这个问题，该文改进了World Wind中加载三维模型的KMLViewer类，最终实现了三维模型在World Wind上的批量加载。
与此同时，问题也随之出现。在对单个三维模型进行加载时，World Wind三维模型加载速度慢、效率低、占用内存高、显示效果不佳等问题并不明显。但是在多个三维模型批量加载时，可以明显的看到World Wind出现了卡滞现象，而且多数三维模型的纹理加载失败呈现透明状态，左边框架里的选项也消失不见，CPU内存使用率急剧升高，电脑濒临死机状态。如图4所示。
World Wind中三维模型批量加载的问题严重影响了后续研究的开展。为了解决这个问题，该文对三维模型批量加载类的代码进行分析后，最终选择改进视锥裁剪算法来解决该问题。
3 视锥裁剪
视锥体是指采用空间变换矩阵计算出的一个由六个面组成的有效显示范围[7]。如图5所示。
根据视锥裁剪算法原理，三维地理信息系统只显示视锥体范围内的三维模型，对范围外的模型一律不再显示，因此视锥裁剪算法能有效地提高三维地理信息系统的显示效率。通过研究java版World Wind代码，该文发现World Wind中的视锥体首先显示球面数据，而后显示新加载的模型区域。这虽然能显示球体完整的DEM等数据，但会影响World Wind中新加载的三维模型显示效率，造成模型加载速度慢、效率低、内存占用高等问题。
基于以上问题，该文在研究对比了多种视锥裁剪算法后，对World Wind中的视锥裁剪算法进行了改进。刘牧曾提出对模型区域建立最小包围球体的想法[8]，在针对单个模型或小面积模型区域时，这种方法还比较有效。但随着模型区域面积的扩大，长和宽也会随之变大，但高度基本不变。所以在对大面积模型区域进行包裹时，最小包围球其实只有小半个球体包围着模型区域，这就造成了空间上的大量冗余，加重了程序运行负担。由于大面积模型区域类似于一个不规则的长方体，所以长方体会更加合适包裹三维模型区域。该文对视锥裁剪算发改进的基础思想就是构建一个基于三维模型区域的最小长方体，通过对视锥裁剪算法的改进，让视锥体优先显示最小长方体中的三维模型区域，而后显示球体的DEM等数据，这样能有效的解决三维模型加载速度慢、效率低、占用内存高等问题。算法步骤如下：
首先，按照模型区域的长宽高来定义一个包围它的最小长方体。其次，通过长方体中两条对角线的交点找到长方体的中心点L，设L的坐标为（x0，y0，z0），x0，y0，z0可为任意值。长方体的具体构建将在World Wind的JOGL中予以实现。然后，分别定义视锥体的六个面为A、B、C、D、E、F，通过World Wind中的frustum类找到与六个面相对应的投影矩阵。如图6所示。
根据投影矩阵得出对应六个面的个基本平面方程。以左剪切平面为例可得以下方程：
其中的x.y.z则代表任意一点的坐标。将x.y，z代入其中，如果所得值大于0，则说明此点在左切面内侧。同理，将此点坐标分别代入六个面的方程中，如果都大于0，则此点在视锥体内。根据视锥裁剪算法原理，视锥体只显示与其相交或者在其内部的物体，于是六个方程计算数值都大于0的此点可显示，否则不予显示。最后，将包围模型区域的最小长方体中心点L的坐标（x0。y0.z0）分别代入六个平面方程中。如果结果全部大于0，则说明该中心点在视锥体内，可判定最小长方体与视锥体相交或者在视锥体内部，按照视锥体的显示原理，判定对此最小长方体中的三维模型区域予以显示，否则不予显示。
4 实验对比与结果
最后，该文通过实验来验证该算法的可行性。首先选择一块三维模型较多的区域作为实验区。由于美国华盛顿市KMZ模型资源比较丰富，所以本文选择华盛顿某地作为实验区域。
由于World Wind加载模型后无法让球体自动显示加载区域。为了方便进行实验，该文对World Wind的KMZ加载类进行改进，在World Wind加载模型后，球体会自动旋转到模型区域并放大进行显示。运行World Wind后，按照前文给出的方法对模型区域的三维模型进行批量加载。打印显示最小长方体的视锥体六个面坐标，在与Google Earth中三维模型区域实际坐标对比后，可以看出新建的最小长方体成功锁定了视锥体，使其精准的固定在三维模型区域位置范围内。如图7所示。
随后查看World Wind中三维模型区域显示效果。效果如图8所示。
通过实验对比可以看出，改进视锥裁剪算法后的World Wind中三维模型区域显示效果较好。右上角360软件显示的CPU占有率只有百分之四十一，相比改进前的百分之九十二，节省了一倍还多。而且在实际加载中，速度也得到明显提高，没有出现卡滞现象。
5 结论
鉴于科学研究对World Wind中多个三维模型加载显示的需求，该文改进了World Wind中的视锥裁剪算法，经过实验验证，最终解决了World Wind中三维模型加载显示速度慢、效率低、内存占用率高、显示效果不佳等问题。
作为一个开源三维地理信息系统，World Wind从以来就一直被开发者进行完善和提高。该文站在前人的基础上，对World Wind又进行了一定的改进，希望能为后续的研究提供便利。
参考文献：
[1] Ulf Assarsson & Tomas Moller.Optimized.View Frustum Culling Algorithms for Bounding Boxes[J].Journal of Graphics Tools，2000（1）：9-22.
[2] Bell D G.， Kuehnel， F.NASA World Wind： Opensource GIS for MissionOperations.Aerospace Conference，2007（10）：1-9.
[3] 周波，祝忠明，刘再东.遥感影像的瓦片金字塔切割与边界填充研究[J].计算机与信息技术，2011（10）：29-31.
[4] 卢小平，田继辉，张剑伟，等.多尺度DEM数据的组织与管理方法研究[J].测绘通报，2010，（6）：12-15.
[5] 戴晨光，张永生，邓雪清.一种用于实时可视化的海量地形数据组织与管理方法[J].系统仿真学报，2005 （2）：406-409.
[6] 袁琪，闵栋，邹俊伟.KML文件的信息隐藏技术[J].北京邮电大学学报，2011（1）：140-144.
[7] 张芹，吴北平，孙华等.视景体可视范围的确定及应用[J].测绘科学，2009（4）：179-181.
[8] 刘牧.实时三维漫游系统中关键技术研究与实现[D].济南：山东大学，2009：23-24.
