一种用于三维城市建筑物的可视域分析算法
2018-02-28靳海亮李留磊袁松鹤耿文轩
靳海亮，李留磊，袁松鹤，耿文轩
(河南理工大学测绘与国土信息工程学院，河南 焦作 454000)
可视性分析包括通视分析和可视域分析，作为三维GIS的一种重要的空间分析方法，在城市规划[1]、选址[2]、军事[3]和考古等方面有着广泛的应用。通常情况下可视性分析是基于数字高程模型的，产生了很多基于规格格网地形数据和不规则格网地形数据的通视分析算法[4-6]，并基于此进行地形的可视域分析。基于城市建成区数据的可视性分析从20世纪70年代开始，Benedikt-[7-8]等借助于计算机图形学技术进行城市建成区的可视性分析研究，但也只是在二维方面适用，并没有扩展到三维空间。
随着三维城市GIS的发展，基于地形数据和城市建筑三维模型数据的通视分析和可视域算法也得到了广泛的研究。尹长林[9]等采用平行投影、点和多边形关系的计算方法确定视线和建筑物的通视情况，然后基于通视分析进行可视域分析，可视域分析的精度受到采样视线多少的影响。王明孝[3]等则利用数字高程模型数据叠加建筑物高度信息生成城市建筑物模型，然后基于此进行可视性分析，可视域计算方法需要根据通视分析进行。Yang[10]等提出可视球的概念，实质上是在视点所在平面上以一定间隔生成采样视线，再在其垂直方向上按照同样采样间隔旋转得到更多采样视线，以进行可视性分析。韩俊[11]综合考虑地形数据和建筑物模型数据，采用了基于图形处理器(graphics processing unit，GPU)加速的深度缓存可视分析算法，算法的实现效率较高但需要依赖于硬件且实现过程较复杂。Suleiman[12]等基于视点构造单位球体，计算地形及建筑物模型的多边形面片在单位球体上的投影，取各个方向上投影中距离视点最近的多边形面片区域作为可视区域。Pyysalo[13]等采用体素的方法来表达城市建筑物并叠加在地形数据上进行通视分析和可视域分析，将地形和建筑物数据作为一个整体，无法只针对建筑物进行可视域分析，进行可视域分析时也必须基于通视分析进行，可视域分析的精度依赖于采样视线的数量。Suleiman[14]等假设地形和建筑物模型由一系列的三角面片构成，建筑物和地形用不同的ID进行标识，建筑物模型可以被单独列出但是在进行可视域分析时还需要根据通视分析进行实现，同样也无法根据建筑物的特点进行可视域的分析。周永望[15]等通过扩展二维空间句法，对三维城市的通视性进行计算，并不能进行某一点的可视域的计算。
上述研究多是将地形数据和建筑模型数据作为整体考虑进行可视性分析，并没有根据建筑物模型数据和地形数据的差别分别讨论各自的可视性分析方法，而且即使单独考虑建筑物的可视性分析，其通视性分析的方法也是基于地形数据的通视性分析的计算方法，忽略了建筑物模型数据的特点，计算出来的可视域精度也就需要依赖采样视线的数量。
在城市环境中，地形一般起伏不大，因此本文不考虑城市地形数据对可视域分析的影响，针对城市建筑物模型进行可视域分析算法的研究。
1 城市建筑物模型的创建
本文只考虑城市建筑物对视点的可视域影响，因此只需对城市建筑物进行模型的创建，保证得到的建筑物模型相互之间是独立的，每个建筑物模型由一系列的三角面片构成。
2 基于通视分析的城市建筑物可视域算法原理
假设建筑物模型是由一系列的三角形面片构成的，而且每个建筑物模型可通过其ID进行识别。下面对基于通视分析的城市建筑物可视域算法的实现原理进行解释：
(1) 取建筑物模型集合中n个建筑物模型中的一个，得到所有构成该模型的三角形面片，设三角形面片总数为k。
(2) 设置视点，取该模型的一个三角面片的中点作为目标点和视点构成一线段，计算该线段所在的直线。
(3) 计算直线和建筑物集合中每个模型的三角面片所在面的交点，判断该交点是否同时在该线段上和三角形内，若在则说明相交，否则不相交。取距离视点最近的交点，若该交点不是目标点则说明不可视，否则可视。重复以上步骤，即可得到该视点的可视域。
根据以上原理可知其时间复杂度为O(n×k×n×k)，其中n为建筑物模型的数量，k为构成建筑物模型的三角形面片平均数，一般情况下k要远大于n。
3 算法的设计与实现
3.1 算法实现所需的具体数据结构
Struct ColladaCoponent
{
String ccID;∥模型的名称
List
Vector3 midVector;∥模型的中心点
List
List
List
List
Bool isOrthoModel;∥标记该模型是否为单面可视模型
Float disTovPerm;∥记录模型中心点到视点的距离}
3.2 算法的主要步骤
(1) 根据构成建筑物模型的三角面片的每个点坐标计算模型的最小矩形包围盒、包围盒的底部轮廓点(逆时针排序)、包围盒的中心点坐标和建筑物高度。
(2) 设置视点及视点的视距，计算视点和每个建筑物模型的最小矩形包围盒中心点的距离，判断该距离和视距的大小关系确定在视距范围内的建筑物模型。
(3) 根据每个模型的包围盒角点和视点，计算矩形包围盒的可视角点，连接视点和可视角点生成锥体，锥体的棱代表视线的方向，锥体的棱的交点为视点。如图1(a)所示。
(4) 为了简化计算过程，同时保证得到的可视面一定可视，当视点高度大于建筑物模型高度时，认为该建筑物模型的顶部可视。
(5) 步骤(4)中已经讨论顶面可视的判断条件，因此只需考虑侧面的可视性。从图1(a)可知建筑物模型的可视面有一面或多面，生成的锥体的底面多边形将会比较复杂，为了简化计算过程，需减少锥体棱的数量。根据模型包围盒的底部轮廓点，选择和视点在水平面上的投影成最大夹角的两点作为锥体底面上的点。若此两点构成的边为建筑物模型底部轮廓边，则标记该模型为单面可视模型，作为锥体底面点，否则标记该模型为多面可视模型，同样作为锥体底面点，并将在两点之间的底部轮廓角点加载至模型底部轮廓可视角点集合。根据以上得到的两点，取其在垂直方向上的包围盒角点作为锥体底面上的另外两点，四点逆时针排列构成锥体的底面，如图1(b)所示。根据以上过程，生成每个模型的锥体底面。
图1 模型锥体示意图
(6) 取视距范围内的一模型作为当前模型，根据步骤(2)中模型距离视点的距离，得到小于当前模型距离视点距离的模型作为待投影模型，计算视点和当前模型中点构成的射线和待投影模型的中点和视点构成的射线之间的夹角，若小于90°则计算待投影锥体底面在当前模型锥体底面所在平面上的投影区，计算投影区和当前模型锥体底面多边形的差集，计算结果按逆时针排序。遍历建筑物集合中的模型，重复以上过程，若差集不为空则说明当前模型的锥体多边形存在可视域，若为空则说明当前模型的锥体底面多边形不存在可视区域，计算效果如图2(a)，该效果图中的模型均为单面可视模型，可直接根据差集坐标集合进行可视化。
图2 不同投影情况下的可视域实现效果
(7) 根据步骤(6)，取锥体底面存在可视区域即差集不为空的模型，若该模型为多面可视模型，将差集中的点投影到水平面上得到投影线段和视点构成三角形，计算该三角形的非投影边和模型底部轮廓可视角点集合中的点依次构成的线段的交点，剔除不在两交点之间的模型底部轮廓可视角点，将交点和两交点之间的底部轮廓可视角点逆时针排列。差集中的点构成的多边形是不规则的，每个点的Z值也不一样，为简化计算取差集中点坐标的最小最大Z值，作为可视区域在垂直方向上的边界。根据差集中的点坐标的XY值和最小最大Z值，按照逆时针方向从模型底部到模型顶部生成可视墙面对应的区域边界点坐标，可视域计算效果如图2(b)所示图中点v为视点，线段a为视线，abcd围成的区域为可视区域。遍历建筑物集合，重复以上计算过程，得到所有模型的可视墙面区域边界点坐标，最后进行可视化。
3.3 算法复杂度分析
首先假设建筑物模型集合中共有n个建筑物模型，每个建筑物模型包含3k个点。计算每个建筑物模型的最小矩形包围盒，其时间复杂度为On×3k。计算n个建筑物模型的锥体的复杂度为rOn，r为每个建筑物模型的底部轮廓点的数量，r为常数4。计算锥体之间的投影，最坏情况为n个建筑物模型正好相互遮挡，时间复杂度为On×(n-1)/2，计算投影承载面上多边形之间的差集。因此本算法的时间复杂度为On×3k，与基于通视分析的城市建筑物可视域计算方法的时间复杂度相比有了较大的提高。
3.4 试验验证
算法实现基于三维可视化平台EV-Globe，其提供的EV-Globe SDK包含了可视化控件GlobeWindow和读取DAE格式模型数据的类ColladaModel。本文通过SketchUp软件生成DAE格式的建筑物模型。在型号HP g4、i3系列CPU、内存2 GB的笔记本上，利用Visual Studio2010集成开发环境中，基于C#语言和EV-Globe SDK实现基于通视分析的城市建筑物可视域算法和本文算法，效果分别如图3(a)和图3(b)所示，图中点v为视点，abcd围成的建筑物表面区域为可视区域。二者耗时对比见表1。
表1 基于通视分析的可视域算法和本文算法耗时对比
图3 可视域实现效果
4 结 语
本文考虑建筑物模型相对规则的特点，计算得到每个建筑物的最小矩形包围盒，基于视点和最小矩形包围盒得到包围盒的可视角点，再根据视点和可视角点得到锥体，计算模型锥体在另一模型锥体底面所在面上的投影区，计算投影区和锥体底面多边形的差集，从而得到每个模型的可视面，使建筑物模型的可视域计算不再需要通过计算模型三角面片上的每个点的通视性得到，既简化了计算过程，提高了计算效率，也保证了可视域计算效果的正确性。
[1] 李德仁，赵中元，赵萍.城市规划三维决策支持系统设计与实现[J].武汉大学学报(信息科学版),2011,36(5)：505-509.
[2] 眭海刚，朱庆，龚健雅.基于DEM及GIS的最佳位置的自动确定[J].武汉测绘科技大学学报,1998,24(2)：138-141.
[3] 王明孝，王晶杰.基于城市建筑物的战场环境可视分析[J].地理空间信息,2012,10(1)：57-60.
[4] 应申，李霖，梅洋，等.增量法地形可视计算与分析[J].测绘学报,2007,36(2)：192-197.
[5] 王晨昊，汤晓安，马伯宁，等.基于距离场映射的地形可视域分析方法[J].测绘学报,2011,40(5)：563-568.
[6] 张立朝，赵鹏，张合朝.地形分析中栅格中间层构建的尺度适应性[J].测绘通报,2017(1)：130-133.
[7] BENEDIKT M L. To Take Hold of Space: Isovists and Isovistfields[J].Environment and PlanningB: Planning and Design,1979,6: 47-65.
[8] TURNER A, DOXA M, O’SULLIVAN D, et al.From Iso-vists to Visibility Graphs: A Methodology for the Analysis of Architectural Space[J].Envrionment and PlanningB:Planning and Design,2001,28:103-121.
[9] 尹长林，许文强.基于3DGIS的城市规划可视性分析模型研究[J].测绘科学,2011,36(4)：142-144.
[10] YANG P PJ, PUTRA S Y, LI W. Viewsphere: a GIS-Based3D Visibility Analysis for Urban Design Evaluation[J].Environment and PlanningB: Planning and Design,2007,34: 971-992.
[11] 韩俊.基于三维仿真的空间可视分析研究与实现[D].郑州：信息工程大学,2011.
[12] SULEIMAN W, JOLIVEAU T, FAVIER E. A New Algorithm for 3D Isovists[C]∥Advances in Spatial Data Handling.[S.l.]：Springer Berlin Heidelberg, 2013:464-474.
[13] PYYSALO U, OKSANEN J, SARJAKOSKI T.Viewshed Analysis and Visualization of Landscape Voxel Models[C]∥Proceedings of the 24th International Cartographic Conference. Santiago Chile：[s.n.],2009.
[14] SULEIMAN W, JOLIVEAU T, FAVIER E. 3D Urban Visibility Analysis with Vector GIS Data[C]∥GISRUK，2011(1)：12.
[15] 周永望，田朝前，李敏.基于三维空间句法的城市空间通视性分析[J].计算机工程与应用, 2014,50(1)：240-244.
