大规模城市建筑物的一种混合LOD 实时绘制算法

陈鹏宇

（四川大学计算机学院，成都610065）

0 引言

当今时代，数字城市[1]成为城市发展研究的热点，其基础为计算机技术、大规模存储技术等，通过宽带网络建联，运用全球定位系统、地理信息系统、工程测量技术、仿真虚拟等技术，对城市进行多分辨率、多尺度、多时空和多种类的三维描述。大量、复杂的建筑物作为其主要地物，也是数字城市的重点研究对象之一，其自动生成的速度快慢、效果逼真与否，都将直接关系到数字城市的建设发展。目前，绘制大型城市建筑物场景，需要处理大量的数据，许多研究人员提出了各种各样的方法，如GLOD 模型[2]、Out-of-Core[3-4]、Relief Map、Block Map 等基于图像[5-6]的绘制技术，以上方法虽可实现大规模城市建筑物的绘制，但大都是在构建聚合体上工作的，容易产生视差误差。

本文提出一种新的混合绘制方法，即基于点、基于线、基于splatting 多边形等混合图元的LOD 模型，根据视距，选择不同类型、不同数量的点、线等简单离散图元构成LOD 的近似表示，从而提高绘制性能，保证LOD 模型与输入模型视觉上的一致性，此方法适用于单个建筑，可提高视觉质量，并通过使用高对比度的简化几何图形作为LOD 图元减少内存使用，解决大规模城市建筑物三维场景可视化中常见的渲染数据复杂度过高，绘制速率较慢等问题。

1 算法概述

本文提出的大规模城市建筑物混合LOD 实时绘制算法的原理与流程如图1 所示。该算法基于三维图形学中透视投影原理设计，对输入的三维建筑模型进行计算和分析，提取出基于点和基于线的三维模型表示。其中，点图元通过抖动采样[7]完成，并生成点图元渐进LOD 模型序列；线图元通过对输入的几何结构进行边界线段分析提取，并采用颜色聚类算法进行分割，并生成线图元渐进LOD 模型序列。而后根据输入模型与视点的距离远近，及其投影于屏幕空间的面积大小（可通过透视投影变换和视口变换计算），即将屏幕投影区域作为LOD 模型选择器，确定无缝表示该建筑对象所需的点、线图元数量，按照距离远、面积小，选择线图元，距离逐渐缩小、面积增大，逐步添加点图元的原则，从点、线图元队列中选择对应的图元。对于视距较近而点、线模型无法提供无缝覆盖时，本文采用一种曲面细分算法，使用Splatting 多边形进行填补。

本算法的优势在于点和线段作为离散图元，具有独立的颜色属性，可不通过纹理映射进行着色，在降低显存消耗的同时均衡GPU 的负载，提高场景实时绘制的性能。

图1 混合LOD实时绘制算法原理与流程

2 点线生成和排序

输入三维建筑物模型将通过不同的方法转换为一组点和线表示的LOD 模型。

2.1 点线生成

点图元采样的目的是生成基于点的三维模型表示，且采样点需具有良好的视觉质量，具有点图元分布均匀，可以避免锯齿、采样效率高等特性。本文采用抖动采样，即将平面分成n×n 的网格，在每个网格中进行随机采样，使任意2 个同层级的采样点处于不同的网格行或者列上，采样点的颜色通过纹理映射直接获得，每个采样点对应的网格层级编号作为属性保存并用于后续创建LOD 模型。

线模型的生成由两个相邻网格面之间的角度控制。若角度小于180°，则一个相邻边缘提取和表示为主要结构的轮廓，并使用较亮的颜色进行着色。另外，需注意如图2 所示情况，一条完整边缘线段上的颜色变化较为有序、明显，先将纹理转换到L*a*b 色域，使用三维欧氏距离计算出各像素点之间的视觉感知差异，分析几何边上的颜色着色梯度，对比相邻像素的视觉差异，提取颜色聚类，将颜色聚类之间的分界点作为子线段的顶点，从而将完整的几何边分割为使用不同颜色着色的更为精确的子线条。

图2

2.2 点线排序

点排序为输入模型创建一个基于点的LOD 模型渐进序列，该序列的任意前缀都是一种简化的基于点的模型LOD 表示，并且递增的添加细节。在点采样的过程中，为每一采样点都被分配一个序号（层级值），根据序号对整个点集进行升序（本文采用堆排序）排序，在相同层级中，使用Fish-Yates 算法进行局部重排，从而为输入模型生成所需的点LOD 模型。

线排序点排为输入模型创建一个线的LOD 模型渐进序列，该序列中包含完整的几何边缘线段和按颜色聚类细分的子线段2 种不同的线段模型，且存储于两个不同序列中。首先，给每个完整线段分配一个序号（即唯一ID）；然后将被细分的线段按与完整线段的从属关系构成集合，故细分线组与对应完整线组有相同序号。本文用长度作为排序键值，使用升序排序（本文使用堆排序）算法对细分线组和完整线组进行排序。同时，为避免重叠和Z-Fighting，本文采取的完整线和子线段的替换策略是：若一完整边缘线段对应的任一细分线可见，则用细分线代替完整线；若一完整边缘线段的细分线均不可见，则用完整线代替。

3 LOD选择

点、线LOD 模型渐进序列提供了一种灵活的方法来绘制大规模城市场景模型。其所需点线数量，从预处理好的序列中进行选择。我们的目标是选择好的表示形式来绘制大规模城市建筑物模型，在使绘制图元数量最小化的同时，保证视觉效果良好。本文使屏幕空间容错因子ω=0，即使屏幕空间的像素点覆盖错误率为0，以获得最优的绘制输出结果。

在给定透视投影下，设输入模型T 由n 个三角形组成，T={t1,t2,…,tn}，其屏幕空间投影面积可以近似为：

设x 表示屏幕的分辨率。考虑到全视场θ 和在观察方向从视点到模型d 的距离，单位投影面积和单位投影长度可计算为：

假设原始模型是由一个点集近似Sp={P1,P2,…,Pm}和一个线集Sl={L1,L2,…,Ln}绘制。点集有一个投影面积，线集有一个投影面积。为了获得可靠的绘制输出，特别是为了避免有间隙，我们需要：

3.1 线选择

我们使用投影面积作为线的LOD 选择器。当且仅当该组中最长的细分线可见（大于1 像素）时，才绘制该细分线组；否则，将绘制相应的完整线。我们首先从使用投影长度作为标准的细分线组的排序序列中选择一个后缀，然后从完整线排序序列中绘制相应的前缀，以避免重叠。

假设输入模型近似为一个线集Sl={L1,L2,…,Ln}，我们用li表示直线的长度。图像平面上直线的长度可以近似为其中对应投影变换。则线集合所覆盖的栅格区域为：

我们使用类似于式（3）的条件来决定是否全部选择线图元绘制。。如果条件为真，则只选择线绘制模型。否则，我们计算需要由点覆盖的投影面积来填补间隙。

3.2 点选择

点填充线结构之间的空隙，并提供立面细节。我们首先绘制线条，然后计算覆盖立面所需的点的数量。在我们的方法中，每个点都表示为一个点画面（即，与像平面对齐的平面圆形单元）与大小。点的数量取决于三角形的近似投影面积与线的近似投影面积之间的差异，他们的计算方程是（1）和（4）。然后点的数量：

系数fp的值用于增加点密度，系数fp只用于点，因为线的长度不随细分而变化。

3.3 splatting选择

上述方法主要是针对中距离和远距离的视距。如果距离较近，预计生成的实际点图元数将小于所需点图元数目np。在这种情况下，我们使用splatting 多边形来填充点、线绘制区域之间的间隙。

本文使用Doo-Sabin 曲面细分算法[8]来获得splatting 多边形填补采样点之间的缝隙和空洞。Doo-Sabin算法和基于点的模型绘制使用完全一致的绘制数据模型，如VBO 等，且完全在GPU 中进行处理，所以不会引入额外的数据，无需使用额外的纹理贴图，可节省大量的显存和内存空间。

Doo-Sabin 算法采用的是逼近型顶点分裂模式，算法过程如下：

（1）几何规则：设Mk为一控制网格, Fk为网格中任意多边形，记多边形顶点为（0 ≤i ≤n），对应的细分后的多边形为Fk+1，生成的新顶点为：

（2）算法实现：①根据公式（1）、（2）计算起始网格各面上新顶点位置，生成新顶点；②判断原顶点在不在边界上，若不在，为各原始顶点生成一个对应的新新V-面；否则不进行此操作；③判断边是不是边界边，若不是，为每条原始边建立一个对应的新E-面；否则不进行此操作；④为各原始面建立对应的新F-面；⑤按照细分规则，重新进行连接；⑥计算各新产生的面和新产生的顶点的法向矢量；⑦一次迭代完成。

另外，经过Doo-Sabin 算法生成的splatting 多边形使用点图元的颜色进行着色，并使用混合技术与邻近的几何图元进行颜色融合，以获得更好的绘制效果。

3.4 混合表示

如图3 所示，为离散图元的LOD 数据结构组织与绘制混合过程。在选择了表示形式并确定了每个图元（点、线、splatting 多边形）的数目之后，我们可以综合他们的混合表示形式，通过排序序列生成简化模型。

图3

4 实验结果与性能比较

4.1 实验结果

本文对北京首都机场、上海虹桥机场2 个三维场景建筑物进行了算法测试。我们通过对比本文提出的算法与传统GLOD 算法[9]生成图像的视觉质量，给出了两种算法的绘制性能结果。本实验平台为配置Intel Core i5-7500 处理器和NVIDIA GTX1080 显卡的台式计算机。实验结果如图4 所示。

图4A1 北京首都机场（使用混合LOD算法）

图4B1 北京首都机场（使用GLOD算法）

图4A2 上海虹桥机场（使用混合LOD算法）

图4B2 上海虹桥机场（使用GLOD算法）

图4A1、A2中使用了离散点、线、splatting 多边形组成的混合LOD 模型；图4B1、B2为使用传统LOD 算法生成的图像。通过对比可知，两种方法在人眼视觉可察中，生成的图像无明显差别。

4.2 性能比较

本文对北京首都机场、上海虹桥机场2 个场景建筑物的混合LOD 模型、GLOD 模型在相同的测试平台上，通过输出横穿场景的漫游动画并统计每一帧的平均绘制时间的方式进行性能对比，结果如表1 所示，可得出本文提出的混合LOD 算法是GLOD 算法速率的3 倍。

表1 绘制性能比较（每帧平均渲染时间，单位ms）

5 结语

本文提出一种新的LOD 方法来绘制大规模城市建筑物，主要思想是通过使用线、点和splatting 多边形的混合方法来绘制，并使用了一种评价指标进行了对比。此方法实现了交互帧率，与传统GLOD 方法保持视觉相似效果的同时，提高了约3 倍速率。但是此方法也有一些局限，本文提出的模型采样和绘制方法，在处理某些具有特殊色彩和亮度的高频特征时，可能会出现视觉精度损失，采用何种方法克服，是本文下一阶段研究的重点。