基于倾斜摄影的三维模型单体化方法研究

王 勇，郝晓燕，李 颖

太原理工大学 计算机科学与技术学院，太原 030024

1 引言

随着三维GIS（Geographic Information System）应用的深入，人们发现从三维空间来处理问题可提高直观性与效率，且城市建筑物三维重建是三维GIS的重要组成部分之一。随着航空摄影技术的创新与发展，研究出倾斜摄影测量的新航测技术。它是通过在低空以不同角度对地面进行摄影测量，来获得近地高分辨率的航测影像。倾斜摄影数据的三维建模颠覆了只能从垂直角度观察的局限，同时可从多个视角对三维建筑模型进行观察。

对于倾斜摄影自动化建模而言，其建模机制的原因可以简单归纳为，首先对所拍摄的影像对生成稠密的点云，然后对点云进行抽稀，再构建三角网，最后贴上贴图。在这个过程中，是没有人工干预的。当前的建模算法并不会把建筑、地面、树木等地物区分出来，因此构建出来的是一个连续的不规则三角网。对于这样的数据，本身是无法选中或分离出单个建筑的，需要进行一定的处理才能实现“单体化”。

“单体化”其实指的就是每一个想要单独管理的对象，是一个个单独的、可以被选中分离的实体，可以附加属性，可以被查询统计等等。只有具备了“单体化”的能力，数据才可以被管理，而不仅仅是被用来查看。而对于大多数应用而言，是需要能对建筑等地物进行单独的选中、赋予属性、查询属性等最基本的GIS的功能。因此，单体化成为倾斜摄影模型在GIS应用中所必须要解决的问题。

目前应用较为广泛的单体化方法是以下三种。第一种是利用三角面片中每个顶点额外的存储空间，把对应的矢量面的ID值存储起来，即一个建筑所对应的三角面片的所有顶点都存储了同一个ID值，从而实现在鼠标选中这个建筑时，该建筑可以呈现出高亮的效果。第二种是在三维渲染的时候，动态地把对应的矢量面叠加到倾斜摄影模型上，达到单体化效果。第三种是利用建筑物、道路、树木等对应的矢量面，对倾斜摄影模型进行切割，即把连续的三角网面从物理上分割开，从而实现单体化。

ID单体化预处理时间适中，模型效果一般，并且不支持动态渲染环境。动态单体化预处理时间较短，支持动态渲染环境。但是以上两种单体化方法都没有实现单体化分离，并不是彻底的单体化。切割单体化的优点是实现了单体化分离，但是单体化模型边缘效果较差。本文采用切割的方式进行单体化，切割边界三角面片以对模型进行边缘处理，保证单体化模型边缘效果，使模型边缘和屏幕分辨率一致。

陈学工[1]等人提出一种对三维表面模型进行任意切割的算法，但是该算法在三角形数量和切割面个数非常多时需要对每个切割面与三角面片进行求交运算，所需的时间比较长。刘少华[2]等人提出一种内角动态判定的简单多边形三角剖分算法，思路简单，易于编程实现。但是，该算法的执行有一定的附加条件，并不能普遍地使用。Garland[3]提出一种对原始曲面模型通过层次聚类进行层次性网格分割的多分辨率框架的HFC（Hierarchical Face Clustering）方法。该方法利用一个层次树表示不同的分割级别下的网格分割，并通过不断选择最平滑边执行边的收缩操作进行区域的聚类合并。Sander[4]等人提出一种基于Lloyd-Max Quantization（即K-means方法）的曲面分割方法，通过初始的数据分割，并不断迭代更新分割结果直到收敛为止得到最终分割结果。Levy[5]等人提出一种基于特征曲线抽取的网格分割算法DFEC（Detect Feature-Expand Charts）。该方法基于边关联面二面角获得特征曲线，之后以特征曲线为边界，以边界向内计算其余三角形到特征曲线的距离进行区域的合并。文献[6-8]采用了求交检测中的方向包围盒OBB（Oriented Bounding Box）法来处理切割不规则三角网时的三角形相交问题，但OBB法的方向任意性使得包围盒的相交测试复杂[9]。Möller提出了快速三角形与三角形相交测试算法[10]，对两个不相交的三角形而言，采用该算法检测所花的时间与对三角形的包围盒进行求交测试所花的时间几乎一样。本文根据倾斜摄影数据的特点，采用AABB（Axis Aligned Bounding Box）进行求交检测，提出了一种对倾斜摄影三维模型切割的可分离单体化方法。

2 基于点集的切割单体化

在倾斜摄影自动化建模过程中，先将拍摄的影像生成稠密的点云，即点集合。基于点集的切割单体化针对点集进行操作，切割点集的单体化流程如图1所示。

图1 基于点集切割的单体化流程

根据图1，基于点集的切割单体化方法步骤描述如下：

（1）如图1，图中虚线即切割线，切割线将原始点集分为内外两个部分。

（2）利用凸壳算法[11]生成每一个点子集的边界，即得到单体化模型边界。

（3）对每一个点子集进行三角剖分，并用LOP（Local Optimization Procedure）算法进行优化。

最终得出单体化倾斜摄影模型如图2所示。

图2 基于点集的切割单体化

图2中，基于点集的切割单体化方法最主要的缺点是单体化模型的效果比较差，切割后模型的底边会带有明显的锯齿，该锯齿为三角面片的边界。

本文针对基于点集的单体化方法提出改进，在进行切割时不直接针对点集进行操作，而采用切割三角面片的方式进行单体化。

3 基于切割三角面片的单体化方法

本文所述倾斜摄影模型的可分离单体化方法首先绘制切割多边形，使用AABB包围盒进行求交检测，以排除大量不相交的三角面片，然后对相交的三角面片进行裁剪并重构，之后进行纹理重构并构建多层LOD（Levels Of Detail）以输出单体化模型。如图3所示，描述了以三维模型作为输入数据实现单体化的基本流程。

图3 基于切割三角面片的单体化流程

本文重点研究输入三维模型后的绘制多边形、求交检测和裁剪三角面片的环节。多边形选择需要进行单体化的建筑，并确定切割路径。包围盒利用简单几何形状包裹，排除不可能相交的三角面片，留下有可能相交的三角面片进行求交检测。

综合分析借鉴国内外研究及实践案例，确定技术思路：即以广州市城市总体规划为基础，以广州市“十三五”期间绿色建筑发展要求为目标，通过遴选建立影响绿色建筑分布的评价因子体系，运用AHP分析法确定权重大小，再对全市规划建设用地进行评价打分后，获得绿色建筑用地空间星级潜力分布图，并以此作为制定广州市及各区绿色建筑发展目标及重点推荐发展绿色生态示范区的依据（图1）。

3.1 绘制切割多边形

由于现有算法无法识别倾斜摄影模型的边界，需要先手动绘制切割多边形，以选取需进行单体化的三维模型。如图4，为某一倾斜摄影建筑模型的不规则三角网面，虚线为切割多边形。切割多边形边竖直投影在三角面片上的线即为切割路径。

由于包围盒一般用于解决凸的物体[12]，需先对切割多边形进行凹凸性判断并进行凸化处理。多边形的凹凸性判断可以归结为判断多边形每个顶点的凹凸性，为此引入叉乘判别法[13]。

根据多边形顶点的凹凸性，可以判断多边形的凹凸性，对于凸多边形可以进行下一步求其AABB包围盒；而凹多边形要先求其凸包，然后将凹顶点投影到所在的凸包上[14]，即可完成凹多边形的凸化处理，再得出其AABB包围盒。

图4 切割多边形示意图

3.2 求交检测

为减少计算切割多边形与三角面片求交点的运算量，需先采用包围盒进行求交检测，得出与切割多边形相交可能性较高的三角面片。在实际应用中建筑模型以立方体居多，包围球的紧密性显得较差。在对倾斜摄影模型单体化过程中，有实时性的要求，而OBB实现起来较为困难。OBB在创建阶段相对复杂，其中包括了大量的矩阵运算，计算代价较大，需用时间较长，不适用于单体化求交检测。AABB是平行于空间坐标系的，所以它的表现形式是线性的，简单且有利于程序的实现。AABB相较OBB具有构造快、相交测试简便的优点[15]，在速度上和存储处理上仅次于包围球法[16]，因此本实验采用AABB。

利用多边形对三维模型进行切割，首先需要判断切割多边形与哪些三角面片发生相交。AABB利用简单的几何形状体来包围切割多边形和三角面片，只有当包围盒是相交的，其包围的对象才有可能相交；当包围盒不相交时，其包围的对象一定不相交。这样就可以预先排除大量不可能相交的三角面片，从而快速找到相交的三角面片，并对可能与切割多边形相交的三角面片进行保存。由于AABB的不紧密性[17]，还需要对这些可能相交的三角面片进行实际的计算。已经排除掉不可能相交的三角面片，所以计算量与之前相比已经减少了很多。计算切割多边形边与被切三角面片的交点，可以利用计算空间中两直线交点的方法得出交点的空间坐标。

3.3 裁剪三角面片

裁剪需要考虑切割多边形与三角面片相交时的情况。主要有如图5所示的五种情况。

图5 切割多边形与三角形位置关系

图5中相交部分为切割三角面片时多边形与三角面片相交的部分。五种情况中，其中（a）中切割多边形有一个顶点位于三角形的内部，有两条边与三角形的一条边相交；（b）中切割多边形有一条边与三角形的两条边相交，并且三角形有一个顶点位于切割多边形内部；（c）中切割多边形有一条边与三角形的两条边相交，且三角形有两个顶点位于切割多边形内部；（d）中切割多边形有一个顶点位于三角形的内部，有两条边分别与三角形的两条边相交，并且三角形有一个顶点位于切割多边形内部；（e）中切割多边形有一个顶点位于三角形的内部，有两条边分别与三角形的两条边相交，且三角形有两个顶点位于切割多边形内部。（a）、（b）切割多边形与三角面片相交的部分形状为三角形，所以不需要几何修正，直接保存即可。对于（c）、（d）、（e）情况，相交部分不满足三角面片的几何特性，需要裁剪后才可保存。

对于图5（c）中，切割多边形一条边与三角形的两条边相交，且三角形有两个顶点位于切割多边形内部的情况，相交部分按以下方式进行裁剪。如图6所示，计算出切割线P与△ABC的边AB和AC的交点分别为点E和F，连接线段CE和FE，线段CE将切割产生的四边形BCFE分成△BCE和△CFE。这样就将由切割多边形切割△ABC所产生的四边形BCFE裁剪为两个三角形，如图6（b）所示。维持了三角面片的几何特性，同时建立各三角面片间的拓扑关系。

图6 针对图5（c）的裁剪与重构

对于图5（d）中，切割多边形两条边分别与三角形的两条边相交，且三角形有一个顶点位于切割多边形内部的情况，相交部分按以下方式进行裁剪。如图7所示，计算出切割线P与△ABC的边AB和AC的交点分别为点E和F，设切割多边形在△ABC内部的一个顶点为D，连接ED和FD，同时将点D与△ABC在切割多边形内的顶点A相连，线段AD将切割产生的四边形AEDF分成△ADE和△ADF。这样就将由切割多边形切割△ABC所产生的四边形AEDF裁剪为两个三角形，如图7（b）所示。维持了三角面片的几何特性，同时建立各三角面片间的拓扑关系。

图7 针对图5（d）的裁剪与重构

对于图5（e）中，切割多边形两条边分别与三角形的两条边相交，且三角形有两个顶点位于切割多边形内部的情况，相交部分按以下方式进行裁剪。如图8所示，计算出切割线P与△ABC的边AB和BC的交点分别为点E和F，设切割多边形在△ABC内部的一个顶点为D，连接ED和FD，同时将点D与△ABC在切割多边形内的顶点A和C相连，线段AD和CD将切割产生的五边形AEDFC分成△ADE、△ADC和△CDF。这样就将由切割多边形切割△ABC所产生的五边形AEDFC裁剪为三个三角形，如图8（b）所示。维持了三角面片的几何特性，同时建立各三角面片间的拓扑关系。

图8 针对图5（e）的裁剪与重构

3.4 重构

重构即是切割后重新组织倾斜摄影模型，维护数据相应的拓扑关系。结合倾斜摄影数据实现切割后的模型显示，针对上述的裁剪，分边可以按照如下过程进行。

如图6（b）所示，将切割线上的与三角面片的交点复制一组，如点E和点F复制一组为点E′和F′，点E′和点F′与切割线一侧的点A建立拓扑关系，形成△AE′F′；点E和点F与切割线另一侧的点B和点C建立拓扑关系，形成△BCE和△CFE。同样，在图7（b）中，将切割线上的点E、点D和点F复制一组为点E′、点D′和点F′，点E、点D和点F与切割线一侧的点A建立拓扑关系，形成△ADE和△ADF；点E′、点D′和点F′与切割线另一侧的点B和点C建立拓扑关系。图8（b）中，将切割线上的点E、点D和点F复制一组为点E′、点D′和点F′，点E、点D和点F与切割线一侧的点A和点C建立拓扑关系，形成△ADE、 △ADC和△CDF；点E′、点D′和点F′与切割线另一侧的点B建立拓扑关系。

4 实验结果

为了验证本方法的有效性，本文在NewMap World平台进行了实验。NewMap World是一款采用C/C++、OpenGL从底层研发的跨平台、跨浏览器的三维地理信息平台，拥有出众的可视化效果、强大的空间分析、方便的数据与功能共享和灵活的异步事件驱动机制的特点。

原始的倾斜摄影数据拥有大量的建筑模型，实际应用中需要针对某一建筑进行单独分析。图9所示为原始场景模型数据，有多个建筑模型，从中选择需进行单体化的模型。如图10所示，绿色多边形包围区域即需进行单体化的建筑模型。

图9 原始建筑模型

图10 绘制切割多边形示意图

对于本文提出切割三角面片的单体化方法，实现了单体分离。可实现对所需模型进行提取，而不必提取周围环境数据。能够做到分层的实体对象化管理，并且模型的边缘整齐，展示出很好的视觉效果。图11为本文所述分离的倾斜单体化示意图。

对包含不同三角面片个数的三维模型进行可分离单体化检测，实验数据如表1所示。

从表1可以看出随着三角面片个数的增加，单体化精确度降低，但最终趋于稳定，三角面片的个数的增加对精确度的影响减小。并且误差率在可控，不影响实验的准确率。三维模型单体化的时间合理，该可分离单体化方法性能良好。

图11 切割三角面片倾斜单体化示意图

表 1 可分离单体化性能检测

5 结论

针对基于点集切割单体化的缺点，本文提出通过切割三角面片实现可分离倾斜摄影三维模型的单体化方法。该方法针对切割三角面片时不同的情形进行分析，提出不同相交情况的裁剪方法，实现了倾斜摄影三维模型的单体分离。较基于点集切割单体化方法，该方法得到分离的单体三维模型的边界整齐，单体化模型边界与屏幕分辨率一致。在对单体化三维模型进行分析时，只提取出需要分析的数据，而不必提取周围环境的数据。实验结果表明，本文提出的单体化方法易于实现，显示效果良好，能够高效地对倾斜三维模型进行单体分析。

[1]陈学工，曾俊钢，李小勇.基于三维表面模型的任意切割算法[J].计算机应用研究，2008，25（9）：2850-2852.

[2]刘少华，汤军，吴东胜，等.简单多边形三角剖分的一种快速算法及应用[J].计算机应用与软件，2008，25（3）：79-80.

[3]Garland M，Willmott A，Heckbert P.Hierarchical face clustering on polygonal surfaces[C]//Proceedings of ACM Symposium on Interactive 3D Graphics.New York，USA：ACM，2001：49-58.

[4]Sander P V，Wood Z J，Gortler S J，et al.Multi-chart geometry images[C]//Euro Graphics Symposium on Geometry Processing.Switzerland：Euro Graphics Association Aire-la-Ville，2013：146-155.

[5]Levy B，Petitjean S，Ray N，et al.Least squares conformal maps for automatic texture atlas generation[J].ACM Transactions on Graphics，2002，21（3）：362-371.

[6]花卫华，邓伟萍，刘修国，等.一种改进的不规则三角网格曲面切割算法[J].地球科学—中国地质大学学报，2006，31（5）：619-623.

[7]李运峰，刘修国.基于方向包围盒投影转换的轮廓线拼接算法[J].计算机应用，2011，31（12）：3353-3356.

[8]Hua Weihua，Chen Guoliang，Tong hengjian.Arbitrary cut algorithm based on 3D geological objects represented by TIN structure[C]//17th International Conference on Geo Informatics，Fairfax USA，Aug 12-14，2009：1-4.

[9]马登武，叶文，李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报，2006，18（4）：1058-1061.

[10]Tomas M.Fast 3D triangle-box overlap testing[J].Journal of Graphics Tools，2002，6（1）：29-33.

[11]鲍蕊娜，李向新，麻明，等.基于凸壳技术的Delaunay三角网生成算法研究[J].科学技术与工程，2011，11（4）：764-767.

[12]王海玲，印桂生，陈怀友，等.基于拓扑层次图的碰撞检测算法[J].计算机应用，2011，2（2）：347-350.

[13]马晨，张毅.一种改进的点与多边形关系的叉乘判别法[J].测绘科学，2013，1（1）：125-127.

[14]毛定山，崔先国，李行，等.简单多边形集凸包的快速算法[J].工程图学学报，2007，28（6）：96-101.

[15]白利芳，常朝稳，王禹同，等.基于有效约束的方向包围盒相交测试算法[J].计算机辅助设计与图形学学报，2016，28（10）：1757-1766.

[16]Curtis S，Tamstorf R，Manocha D.Fast collision detection for deformable models using representative-triangles[C]//Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games，Redwood City，CA，USA，Feb 15-17，2008：61-69.

[17]孙劲光，吴素红.基于空间分割与椭球包围盒的碰撞检测算法[J].计算机工程与应用，2016，52（4）：217-222.

[18]胡事民，杨永亮，来煜坤.数字几何处理研究进展[J].计算机学报，2009，32（8）：1451-1469.