利用多边形骨架线生成房屋模型算法研究

王 飞，李成名

(中国测绘科学研究院，北京 100830)

利用多边形骨架线生成房屋模型算法研究

王 飞，李成名

(中国测绘科学研究院，北京 100830)

城市作为人类生活的重要聚集地，是三维GIS应用的主要领域。本文结合房屋的二维轮廓数据与屋顶的基本信息(倾斜角度、屋顶高度、纹理属性)，以“骨架线提取—房屋模型构建”为框架，提出了一种基于多边形骨架线自动生成简单房屋模型的算法，详细描述了该方法的基本思想，并在试验结果的基础上证实了该算法的有效性。

多边形；骨架线；屋顶模型；可视化

城市作为人们生存和活动的重要场所，在人类的社会、经济、政治生活中起着至关重要的作用[1]。近年来，大范围地形及城市三维建模是可视化领域的一个研究热点，方法较多，所生成的模型细节层次也不尽相同，大致有如下几种[2]：根据DEM重建逼真的地形表面形态，通过叠加正射影像数据生成具有很强真实感的虚拟场景；使用CAD、3ds Max等建模软件逼真设计模型的精细结构和材质特征，不仅可以表现外观，还能充分表现实体的内部形态，可用来进行真三维实体的建模；利用摄影测量、激光扫描或其他地面测量手段采集三维数据和实际影像纹理，从而恢复实体的三维状态；根据建筑物底部轮廓线(如DLG)和相应的高度属性进行三维重建，用于表现较低细节水平的城市景观。然而三维数据的生成，不仅消耗大量的人力物力财力，而且效率不高。三维房屋模型构建的难点和关键是三维屋顶模型的构建。目前，人工建模仍然是构建三维建筑模型的主要技术，但其构建的效率水平很低。针对这一问题，本文提出一种新的快速构建简单三维房屋模型的方法。根据现有的二维矢量房屋数据(建筑物底部轮廓线)，结合建筑物的高度信息、屋顶倾角及屋顶限高信息，运用多边形骨架线生成算法，快速完成简单三维房屋模型的构建。

1 房屋的骨架线提取

简单的建筑屋顶一般分为人字型屋顶和阶跃型屋顶两种[3]。人字形屋顶即坡屋顶，在建筑中应用较广泛，主要分为单坡式、双坡式、四坡式、折腰式等。本文所涉及的坡屋顶是由建筑的多边形基底面，按一定倾角向上延伸的斜屋面所构成，由于斜屋面在空间上进行相交，会形成多条屋脊线，这些屋脊线互相连接，将各个斜屋面围成一个封闭的多边形。生成坡屋顶的三维模型的关键是正确找到屋脊线，即可以描述房屋基底面的骨架线[4-5]。

1.1 多边形数据的分析

经过多年的发展，二维房屋数据已比较完善，一般以矢量面数据的方式进行存储。房屋数据大致可以分为两类：

1.1.1 凸多边形

如果把一个多边形的所有边中，任意一条边向两方无限延长成为一直线时，其他各边都在此直线的同旁，那么这个多边形就叫做凸多边形，其内角应该全不是优角(如图1所示)。凸多边形根据是否包含多变形(洞)，又可以分为无洞凸多边形、有洞凸多边形。

图1 凸多边形

1.1.2 凹多边形

如果把一个多边形的所有边中，有一条边向两方无限延长成为一直线时，其他各边不都在此直线的同旁，那么这个多边形就叫做凹多边形，其内角中至少有一个优角(如图2所示)。凹多边形根据是否包含多变形(洞)，又可以分为无洞凹多边形、有洞凹多边形。

图2 凹多边形

1.2 提取多边形的骨架线

在几何学中，骨架线是对多边形形状的抽象描述[6]。骨架线在某些方面与中轴线具有相似的特性[7]，但不同的是：骨架线是由直线段构成，而中轴可以由曲线构成。Aichholzer等[8]于1995年提出了一种新的简单多边形的内部结构的骨架线，是由多边形的角平分线构成的角平分线网络。骨架线的形成，可以采用具有固定角度的斜坡的构建原理，通过模拟平行切割屋顶获取屋顶的骨架线。在二维视图中，骨架线表现在多边形的边内缩；即多边形的边以恒定速度缩小，顶点沿着角平分线以恒定速度内移[9-10]。Aichholzer[11]将这种现象描述为两种事件：①边事件：不相邻边E0和E2进行相交，E1边消失，长度收缩为零，如图3(a)所示；②分割事件：相邻边E0和E1同时与对边E3相交，将对边E3一分为二，即分割整个多边形，如图3(b)所示。分两步详述骨架线的生成算法：

图3 骨架线生成事件

1.2.1 凸多边形骨架线生成算法

凸多边形，只会触发边事件，骨架线算法通过以下几个步骤生成：

输入：凸多边形P的顶点V1，V2，…，Vn(逆时针方向排列)的坐标；

输出：凸多边形P的骨架线。

(1) 初始化：①循环遍历多边形P的顶点，计算多边形的每条边Ei=ViVi+1和每个顶点Vi应的角平分线Bi；②循环遍历所有顶点角平分线Bi，判断其与相邻的角平分线Bi-1和Bi+1是否相交。如果相交，根据交点到对应的顶点Vi-1和Vi之间的边Ei的垂直距离LEi的大小，得到距离最近的交点Ii，并将交点根据距离LEi的大小进行排序存储到队列中(如图4(a)所示)。

图4 凸多边形骨架线生成步骤

(2) 判断优先队列是否为空，若不为空进行以下步骤(如图4所示)：①取出队列中的第一个交点I，顶点Vc和Vd的角平分线相交而成；②判断顶点Vc和Vd是否已处理，如果已处理，则跳过以下步骤，直接继续循环步骤(2)；③判断顶点Vc的上个顶点Va的上个顶点是否与Vd相同，若相同则说明这3个点形成一个交点I，输出3个骨架线VcI、VdI、VaI，并对3个顶点进行标记处理，跳过以下步骤，直接继续循环步骤(2)；④输出两个骨架线VcI、VdI骨架线，并对两个顶点进行标记处理；⑤根据交点I生成新的顶点V，并调整顶点和边的前后链接关系。重复步骤(1)中的②方法。循环继续。

1.2.2 凹多边形骨架线生成算法

凹多边形，触发边和分割事件，骨架线算法通过以下几个步骤生成：

输入：凸多边形P的顶点V1，V2，…，Vn(逆时针方向排列)的坐标；

输出：凸多边形P的骨架线。

(1) 初始化：①循环遍历多边形P的顶点，计算多边形的外凸顶点的角平分线；②计算相邻凸顶点的角平分线的交点和内凹顶点与相应对边的交点，并标记交点事件(边和分割事件)，根据交点到对应的顶点Vi-1和Vi之间的边Ei的垂直距离LEi的大小，得到距离最近的交点li，并将交点根据距离LEi的大小进行排序存储到队列中(如图5(a)所示)。

图5 凹多边形骨架线生成步骤

(2) 判断优先队列是否为空，若不为空进行以下步骤(如图5所示)：①取出队列中的第一个交点I，判断该交点的事件类型，如果交点I的事件类型为边事件，执行凸多边形的步骤(2)；否则执行以下步骤；②判断顶点是否已处理，如果已处理则跳过以下步骤，直接继续循环步骤(2)；③输出骨架线VcI，并且对该顶点进行标记处理；④根据交点I生成新的顶点V，并将队列一分为二，调整顶点和边的前后链接关系。重复步骤(1)中的②方法。循环继续。

2 基于骨架线生成屋顶模型

骨架线是用与原形状连通性和拓扑结构相一致的直线段作为理想表达的一种对象表示，多边形骨架线的本质是对多边形的抽象描述，即可以描述多边形轮廓的最切实际的线段连线。根据多边形骨架线，结合屋顶的倾斜角度、高度和墙高度信息参数，将骨架线进行立体化和三角剖分，生成三维屋顶模型(平屋顶或尖屋顶)，最后进行纹理贴合，生成完整屋顶模型。

2.1 骨架线进行立体化

立体化就是根据房屋轮廓线生成的骨架线，结合屋顶的倾斜角度和限高信息参数，生成屋顶的三维骨架轮廓。此过程可以通过以下步骤：输入：房屋轮廓线的二维骨架面；输出：房屋轮廓线的三维骨架面。

(1) 初始化：①循环遍历所有骨架线，将骨架线与屋顶轮廓线组成的骨架面，依次存储到队列中。并将所有的骨架点(如图6(a)Vi所示)标记为未处理。以单个骨架面AV1V2V3E为例进行计算。

(2) 取出骨架面AV1V2V3E中的骨架点Vi，判断是否为空，若不为空则进行以下步骤，否则退出(图6(b)所示)：①取出骨架点V1，判断该点是否已处理，若已处理，则直接跳过以下步骤，直接循环步骤(2)，否则进行下一步骤(由于骨架点具有对称性，因此可以只计算一次即可)；② 计算骨架点V1到屋顶轮廓线AE的垂直距离L1；③根据上步骤的垂直距离L1，结合屋顶倾角信息，计算骨架点V1到轮廓面的垂直距离H1，即骨架点V1的高度Z1值，并将该骨架点V1标记为已处理。

(3) 取出骨架面AV1V2V3E中的骨架点V1，判断是否为空，若不为空则进行以下步骤，否则退出：①取出骨架面AV1V2V3E中的骨架线AV1，判断屋顶限高Z值是否在骨架线高度值范围内。若不在范围内，说明该骨架线没有削平点，直接循环步骤(3)；否则有削平点Xi，判断是否第一次出现削平点。如果是第一次，则记下该削平点，否则生成闭合削平顶X1V1V2X2(如图6(c)所示)。②判断是否取出所有骨架面，如果没有，则循环步骤①；否则，生成闭合的削平的骨架面AV1V2V3E(如图6(c)所示)。

(4) 如果没有削平点，生成的三维骨架面如图6(a)所示；否则，生成的三维骨架面如图6(d)所示。

(5) 最后根据屋顶轮廓线和墙的高度信息，进行屋顶抬高处理(如图6(e)、6(f)所示)。

图6 屋顶高度信息的计算

2.2 骨架线三角剖分

由于采用了OpenGL图形编程接口，因此必须从几何图元的点、线和多边形开始构造三维模型。构造三维立体时，从共面性能考虑，特别推荐使用三角形。它具有建模、变换、光线处理、色彩处理、动画，以及其他更先进的高级图形处理能力，如纹理映射、物体运动模糊效果等，可以制作真实感强烈的三维立体图形[12]。因此，笔者选择三角形作为几何图元，即将多边形进行三角化。

借助开源的三角化库Triangle对骨架面进行三角化，如图7所示。

图7 屋顶三角化

2.3 屋顶模型生成与纹理贴图

在三维图形中，物体的外观不仅仅包括形状，不同物体的表面有着不同的颜色和图案。纹理贴图是一种能大幅度提高三维图像真实性的三维图像处理技术，使用这项技术可以减少纹理衔接错误；实时生成剖析截面显示图；有更真实的雾、烟、火和动画效果；提高变换视角看物真实性；模拟移动光源产生的自然光影效果。因此，一个简单有效的、提高物体的真实感的方法就是纹理贴图，如图8所示。

图8 屋顶纹理贴图

3 算法实现及评价

3.1 算法实现

本文基于多边形骨架线的房屋模型生成的基本思想，采用目前主流的C++编程语言和开源OSG图形渲染引擎，开发了基于房屋模型自动建模系统。该系统通过LOD技术对房屋数据进行可视化，当处于视线范围之内时，才可以显示房屋数据。可以将矢量数据存储在服务器端，并发成服务，在客户端可以通过该算法，根据矢量数据实时的生成三维模型并将其显示出来。图9为根据真实的平面矢量数据生成的三维房屋模型的可视化效果。

图9 试验成果示意图

3.2 算法评价

经过试验验证，对该算法进行讨论分析，主要有以下几点：

(1) 算法占用了很少的计算机资源。在程序运行过程中，程序只需要很短的运行时间就可以进行大规模房屋模型的生成。如试验中一张包含500多个房屋面的SHP数据，只需几秒的时间就可以自动生成三维房屋模型；而人工进行建模，可能是几天的工作量，因此节约了大量的时间和成本。

(2) 自动化三维管网建模更加精细化。由于自动化的三维管网全部由计算机计算并生成模型，精度和准确度更高，能够很好地避免人工建模过程中可能出现的误差和错误。

(3) 便于三维功能分析。在自动化生成的房屋模型场景中能够很容易地进行三维功能分析，如通视分析、距离量测分析等。

4 结束语

本文通过试验，初步形成了以二维房屋多边形数据为数据源，结合房屋的倾斜角度、限高等信息，自动构建三维房屋模型的可行性方案。该方案计算量小，速度快，三维模型生产效率高，能灵活地解决带洞或不带洞的凸凹多边形房屋建模问题。但是从实用化角度方面，仍然需要进一步改善，包括对二维矢量数据的房屋属性字段标准的规范制定，以及圆形房屋的建模问题，最终才能建立更贴近真实效果、更实用的房屋简单三维模型构建系统。

[1] 王继周，李成名，林宗坚. 城市三维数据获取技术发展探讨[J]. 测绘科学，2004，29(4): 71-73.

[2] 朱庆，李德仁，龚健雅，等. 数码城市GIS的设计与实现[J]. 武汉大学学报(信息科学版)，2001，26(1): 8-11.

[3] 程亮，李满春，龚健雅，等. LiDAR数据与正射影像结合的三维屋顶模型重建方法[J]. 武汉大学学报(信息科学版)，2013，38(2): 208-211.

[4] 陈宇军. 多边形坡屋顶屋脊线的递归算法[J]. 建筑科学，2007(1): 86-89.

[5] LAYCOCK R G，DAY A M. Automatically Generating Roof Models from Building Footprints[C]∥The 11th International Conference in Central Europe on Computer Graphics，Visualization and Computer Vision.Plzen: UNION Agency-Science Press，2003: 81-84.

[6] 黄利民，张跃鹏. 利用三角网方法实现面域骨架线的自动生成[J]. 测绘学院学报，2002，19(4): 262-264.

[7] 胡鹏，王海军，邵春丽，等. 论多边形中轴问题和算法[J]. 武汉大学学报(信息科学版)，2005，30(10): 853-857.

[8] AICHHOLZER O，ALBERTS D，AURENHAMMER F，et al. Straight Skeletons of Simple Polygons[C]∥Proceeding of 4th International Symposum of LIESMARS.Wuhan:[s.n.]，1995: 114-124.

[9] CACCIOLA F. A CGAL Implementation of the Straight Skeleton of a Simple 2D Polygon with Holes[C]∥2nd CGAL User Workshop.[S.l.]:CGAL，2004.

[10] AICHHOLZER O，AURENHAMMER F. Straight Skeletons for General Polygonal Figures in the Plane[C]∥Proceedings of the Second Annual International Conference on Computing and Combinatorics.[S.l.]：Springer-Verlag，1996: 117-126.

[11] AND P F，OBDRZALEK S. Straight Skeleton Implementation[C]∥ Proceedings of the Spring Conference on Computer Graphics.Budmerice：[s.n.]，2001:210-218.

[12] 陈绪兵，夏华，肖跃加，等. 三维原型的OpenGL真彩光照方法[J]. 计算机辅助设计与制造，2002(3): 53-55.

ResearchonAlgorithmsforSolvingRoofModelbyUsingStraightSkeletonofPolygon

WANG Fei，LI Chengming

(Chinese Academy of Surveying and Mapping, Beijing 100830, China)

City, as an important place of human life, is the main field of 3D GIS application. A method to automatically generate the roof model based on straight skeleton of polygon is presented, with skeleton line extraction-housing model as the framework, based on 2D contour data of housing and the basic information of the roof (angle, roof height, texture attributes). At last the basic idea of the method is described and the effectiveness of the algorithm is verified by experimental results.

polygon; straight skeleton; roof model; visualization

P208

A

0494-0911(2017)01-0069-05

王飞，李成名.利用多边形骨架线生成房屋模型算法研究[J].测绘通报，2017(1)：69-73.

10.13474/j.cnki.11-2246.2017.0015.

2016-03-08

测绘地理信息公益性行业科研专项(201412003)；国家科技支撑计划(2015BAJ06B00)；中国测绘科学研究院基本科研业务费(7771520)

王 飞(1987—)，男，硕士生，主要从事三维地理信息系统研究。E-mail: wangfei-921@163.com