海滨城市三维场景的混合图元渲染方法*

周圣川， 胡振彪， 马纯永， 陈　戈

(1.青岛市勘察测绘研究院，山东 青岛 266033; 2.海陆地理信息集成与应用国家与地方联合工程研究中心，山东 青岛 266033;

3.中国海洋大学信息科学与工程学院，山东 青岛 266100)



海滨城市三维场景的混合图元渲染方法*

周圣川1，2， 胡振彪1，2， 马纯永3， 陈戈3

(1.青岛市勘察测绘研究院，山东 青岛 266033; 2.海陆地理信息集成与应用国家与地方联合工程研究中心，山东 青岛 266033;

3.中国海洋大学信息科学与工程学院，山东 青岛 266100)

摘要：本文提出一种适用于海陆一体场景的大规模城市三维可视化方法。使用多重抖动采样和颜色聚类算法将城市三维模型转换为由点、线等简单图元构成的层次细节模型，通过屏幕空间投影面积进行层次细节(Level-of-detail，LOD)模型的选择，以较少数量的简单图元合成模型的近似表示，实现城市建筑的LOD渲染。实验表明，该方法具有较高的真实感，可以大幅提高城市级大场景的渲染效率，并且与几何LOD等方法相比，其性能受水体模型渲染的影响更小，更适用于海陆一体的海滨城市场景渲染。

关键词：层次细节模型；混合渲染；海滨城市可视化；虚拟现实

尽管经历了多年的研究和产业化应用，大规模城市三维场景的实时可视化渲染仍然是一个亟需解决的瓶颈问题。尤其是在海滨城市可视化方面，由于要同时进行水体和城市模型的渲染，数据和算法复杂度极高，因此难以实现交互式或者实时的大规模场景渲染。目前，在大规模城市三维可视化系统中广泛采用和研究的技术主要有几何LOD模型[1-2]、Out-of-Core[3-5]，以及Relief Map、Block Map等基于图像的渲染[6-9]技术。以上方法虽然可以实现大规模城市三维场景的可视化，但是不可避免地会引入几何形变、平行视差，以及可见性不完整等视觉精度上的损失。同时，上述方法也都使用了与水体渲染[10]相同的三角网格加纹理的数据模型，空间复杂度高，在叠加大规模水体渲染时，性能往往呈现非线性下降。

本文提出一种基于混合图元的层次细节模型，将距离视点较远的三维模型转换为由点和直线等简单离散图元构成的LOD近似表示，以提高复杂城市模型的渲染性能。通过计算输入模型的屏幕空间投影面积精确地选择LOD模型中离散图元的数量，在提高渲染性能的同时保证LOD模型与输入模型视觉上的一致性,从而解决大规模城市三维场景可视化中常见的渲染数据复杂度过高，以及渲染视觉质量损失等问题。该方法在包含大规模水体的滨海城市场景中，受水体渲染的性能影响更小，更适用于海陆一体城市场景的渲染。

1混合LOD模型构建

本文基于人眼视觉对边缘极度敏感的原理[11]提出一种混合图元渲染方法。城市三维场景，尤其是现代城市场景，由大量的建筑组成，并且这些建筑和周边环境之间有着较为明显的边界。建筑的边界一般是由包含多种颜色的直线段构成。因此，传统的LOD方法，通常会在原本应保持几何连续性的模型边界上产生不连续的噪声图元和锯齿。另一方面，距离视点较远的模型经过透视投影变换之后，一般在最终的渲染缓冲区中仅表示为少量的像素点。因为人眼的视觉对边缘极度敏感，而直线段的三维渲染结果具有良好的抗锯齿与反走样性质，且线段、点等离散图元在渲染过程中像素大小固定，不受投影变换影响，具有很好的着色填充性质。所以，在距离视点较远时，三维模型可以使用极少量的点和直线段，甚至可以只使用直线段进行近似表示。点和直线段作为离散的图元具有独立的颜色属性，可以不通过纹理映射进行着色，在降低显存消耗的同时均衡GPU的负载，提高海陆一体场景的整体渲染性能。

1.1 点图元采样

点图元采样的目的是生成基于点的三维模型表示。点图元是三维图形学理论中最简单的渲染图元类型，因为其结构简单，所以具有比常用的三角网格图元更好的渲染性能。具有良好视觉质量的基于点的三维模型表示应该具有以下性质：(1)点图元均匀地分布在模型表面；(2)采样算法能够将低频失真转为高频特征，避免产生锯齿等噪声；(3)构成层次细节模型的采样点子序列不应该违反性质(1)和(2)；(4)城市三维场景的数据量巨大，点模型的采样应该具有较高的效率。

如图1所示，本文使用多重抖动采样生成具有上述特征的点模型。首先在多边形上进行多分辨率的网格划分，然后进行采样。采样的过程遵循N-rooks条件，即：随机在网格中进行采样点选择，任意2个同层级的采样点处于不同的网格行或者列上。采样点的颜色通过纹理映射获得，每个采样点对应的网格层级编号作为属性保存并用于创建层次细节模型。

图1　多重抖动点图元采样

1.2 线图元采样

单一的基于点的模型一般不适用于表示城市建筑等具有大量低频几何结构以及明显的几何边界的三维模型，所以本文引入了点、线等多种图元混合的三维模型表示方法。

线模型的构建以多边形之间的夹角进行判断。如果2个邻接多边形之间的角度不为180°，那么邻接的边即被提取出进行采样，作为建筑模型的边界。提取出的直线使用在直线上出现次数最多的颜色进行着色。

图2　基于颜色聚类的线模型采样

此外，需要注意的一种情况是在一条几何边上可能出现如图2所示的颜色变化。此时，本文通过分析几何边上的颜色着色梯度，提取颜色变化的关键点，将完整的几何边细分为使用不同颜色着色的子线条。

首先，使用如下公式将纹理由RBG色域转换到L×a×b色域：

X=0.412 453×R+0.357 580×G+0.180 423×B，

Y=0.212 671×R+0.715 160×G+0.072 169×B，

Z=0.019 334×R+0.119 193×G+0.950 227×B，

L*=116×f(Y/YN)-16，

a*=500×[f(X/XN)-f(Y/YN)]，

b*=200×[f(Y/YN)-f(Z/ZN)]，

其中：

在L×a×b色域中，像素点之间的视觉感知差异与色彩值成正相关，可以通过三维欧氏距离计算得出。本文首先使用一个一维的高斯滤波器对几何边上的所有像素点进行平滑滤波处理，过滤纹理图像中的高频噪声信号；然后，使用一维卷积核[-1,0,1]在几何边上进行逐像素的滤波，通过对比相邻像素的视觉差异提取颜色聚类。如图2所示，经过以上操作，颜色聚类之间的分界点，也就是子线段的顶点，对应卷积操作后像素值序列中的极大值点。通过上述操作可以将提取出的三维对象几何边界按照着色变化分割成更为精确的子线段。

2混合LOD模型构建

2.1 点图元排序

本文通过对点序列重新排序，生成一个支持渐进层次细节变换的点序列。该序列的任意前缀子序列都是原始模型的一个层次细节模型。这样，就可以通过三维模型的投影面积，在LOD选择阶段生成不同视距下的三维模型多分辨率表示。

如前文所述，对于使用多重抖动采样方法生成的点云三维模型，在进行采样时每一个点样本都被赋予了层级索引值，使采样生成的点序列具有了渐近层次细节特征。本文进一步地对采样的结果按照层级索引值的升序进行排序，使最终的点序列中任意长度的前缀子序列都构成一个三维模型的层次细节表示。为了保证同一层级采样点分布的均匀性，对具有相同层级索引值的采样点使用洗牌算法进行了局部重排列。

2.2 线图元排序

类似的，对线模型进行重排序的目的是生成一个支持多分辨率层次细节变换的线序列。在线模型的生成过程中，产生了2种不同的线段模型——完整的几何边缘线段和按照颜色聚类细分的子线段。线段模型可以用于加强模型的几何边缘，消除点渲染结果中的锯齿等噪声，同时减少渲染的点图元数量。完整的几何边缘线段可以直接在模型距离视点较远时作为层次细节模型使用；在模型距离视点较近时，使用精确着色的分割线段逐渐替换完整的几何边缘线段可以明显地改善图像质量，实现混合图元表示的反走样。构建基于线的连续层次细节模型就是创建一种用于存储线段模型的LOD数据结构，该数据结构可以实现连续地、动态地使用分割子线段替换对应的完整几何边缘线段，实现基于线的LOD模型选择和切换。

本文将完整的几何边缘线段与分割子线段分别存储于2个顺序结构中，其中每一个完整线段分配一个唯一的索引ID并使用顺序队列存储；所有的分割线段按照其从属关系构成集合，每一个线段集合和其对应的完整线段具有相同的ID，并使用如图3所示的线性表结构进行存储。为了避免深度值冲突(Z-Fighting)造成的渲染图形闪烁，本文采取的替换策略是，对于任意一个完整线段，其对应的分割线段集合中有任一子线段可见，则将该完整线段设为不可见，对应的所有分割子线段设为可见；当一个完整线段的所有分割子线段均不见时，使用完整的几何线段进行渲染，所有的分割子线段不进行渲染处理。

图3　线模型数据结构

为了实现动态的层次细节模型切换，对每一个分割线段集合，本文提取其中最长的子分割线段的长度作为排序的键值；然后，使用排序算法按照升序对存储分割线段集合的顺序表进行排序；在排序后，通过索引ID对存储完整线段的顺序表进行重排列，使每一个完整线段和其对应的分割线段集合在顺序表中的索引ID一致，即具有相同的线性表下标值或索引值。通过上述重排列算法，在可视化过程中如果从完整线段顺序表中提取了一个前缀子序列进行渲染，可以在分割子线段集合顺序表中选择对应的后缀序列进行渲染，从而在实现渲染精度动态变化的同时避免分割子线段和完整线段之间的重叠。

假设一个三维模型可以由N条完整边缘线段近似表示，则本文中构建的基于线的层次细节模型中包含了i,i∈[0,N]个细节层次；其中，第级的层次细节模型由完整线段顺序表中的前N-i条几何边缘线段，和子分割线段集合顺序表中的后i个集合元素中的所有子分割线段构成。

本文构建的LOD数据结构可以直接编译成OpenGL中的顶点缓冲区对象或者顶点数组对象，所以LOD模型的选择和渲染都可以通过1～2个OpenGL渲染函数调用完成，具有极高的效率。

3混合LOD模型渲染

通过对点、线图元的采样和排列组织，本文构建了基于点、线图元的连续层次细节数据模型。上述模型提供了极具伸缩性的LOD性质与数据存储结构，可以用于实时LOD模型渲染。在渲染过程中，通过自适应地确定需要的点和线图元数量，从预处理好的点、线序列中选择相应的子序列构成输入模型的层次细节表示，进行高性能的可视化输出。

3.1 线图元渲染

线模型可以生成平滑的模型轮廓，并在模型距离视点较远时实现无缝渲染。对于分割线段集合元素，当其中最长的子分割直线段可见，也就是投影面积大于1个像素时进行渲染，否则使用对应的完整直线段进行渲染。本文中线段的渲染宽度都设置为1像素，所以线段的投影面积可以使用线段的投影长度近似表示。

假设三维模型的近似表示由直线段集合L构成，集合中线段L的长度为li，线段所覆盖的模型投影面积可以通过如下公式求解：

则说明线模型能够完整覆盖模型的表面，构成无缝的模型近似表示；反之，需要在线段之间增加点图元，填充未被直线覆盖的区域。

3.2 点图元渲染

点模型可以在近距离渲染时填充线段之间的空隙并提供模型表面的着色细节。具体方法是在线模型渲染后，计算完全覆盖模型表面所需要的点数量，从点模型的存储序列中选取对应的前缀子序列传入渲染管线。

在求出无缝渲染所需的点数量后，从经过预处理和重排序的点序列中选取前np个点进行渲染就可以得到无缝的三维模型层次细节表示。

3.3 曲面细分渲染

当视点距离渲染对象较远时，点和线段组成的混合渲染模型可以取得较好的空间覆盖效果。但是，由于点的空间覆盖能力有限，实际存在的采样点数量可能小于渲染所需的点数量np。此时，本文使用曲面细分算法填补采样点之间的缝隙和空洞。

如图4所示，本文使用与法线方向垂直的正方形作为曲面细分的结果，扩大点图元的空间覆盖范围。给出相机垂直方向方向向量U，点图元法线N，点图元坐标Pi，点图元采样密度s，则水平方向和垂直方向的曲面细分方向向量可以分别表示为：H=U×N和V=H×N。

曲面细分向量Tij∈{0，1}，j∈{0，1}则可以通过如下方法计算得出：

Tij=Pi+(2i-1)·H/|H|·s+(2j-1)·V/|V|·s。

此外，经过曲面细分生成的多边形使用点图元的颜色进行着色，并且使用混合技术(Alpha-blending)与临近的几何图元进行颜色融合以获得更好的渲染视觉效果。

图4　基于点的曲面细分填充

3.4 图元混合策略

在进行渲染图元的选择后，每一种离散渲染图元(点、线、Splatting多边形)的数量已经确定，本文提出一种混合渲染模型，从离散图元的序列中提取层次细节模型并进行混合，合成输入模型的混合层次细节表示。

图5　混合渲染策略

如图5所示为离散渲染图元的层次细节数据结构组织与渲染数据混合过程。本文首先根据投影面积选择子分割线段集合序列的一个后缀子序列进行渲染；然后，从完整线段序列中选择未被分割子线段集合替换的前缀序列进行线模型的渲染。

假设经过采样的离散点图元序列的第个LOD层级中包含了ni个采样点。如果在离散点序列中存在2个相邻的采样层级r和r+1，满足如下关系：

则本文选择离散点序列中的前np个点进行渲染。否则整个离散点图元序列被传入曲面细分引擎，以着色多边形的形式进行渲染输出。在渲染过程中，混合图元使用FXAA(Fast Approximate Anti-aliasing)方法进行反走样，去除其中的高频噪声信号。

图6　渲染结果

4实验结果与讨论

本文使用总数据量为52 GB的包含海陆模型的青岛市城市三维场景对算法进行测试。实验平台为配置Intel Core I7-3740处理器，NVidia Quadra K2000显卡，4 GB内存的图形工作站。处理后的三维场景总共包含72.6 M的直线段和1.7 G的采样点。

图6a所示为使用混合LOD模型进行城市三维场景渲染的结果。图6b中使用了动态范围无关算法[13]比较了混合LOD模型与原始模型的视觉差异。其中，具有明显差异的像素点使用红色标识，具有细微差异的像素点使用绿色标识，视觉等价的像素点用灰色标识。可以看出，混合LOD模型的视觉效果与原始模型基本一致，只有6%～7%的像素点呈现明显差异。这种差异在大规模城市场景的渲染结果中是难以被察觉的。

使用本文算法可以实现完整城市级大场景的可视化，通过视锥裁剪后的渲染帧速约为每秒65～70帧(见图6c)。图6d所示为使用本文方法进行海滨城市三维场景渲染的结果，其中使用本文方法进行渲染的平均帧速为122 fps，使用纯三角网格渲染方法的平均帧速为15 fps。

图7　渲染图元数量

/ms

图7中所示为不同视距下混合LOD模型渲染的图元数量。可以看出，点图元的数量与线图元和多边形图元相比，以更快的速度收敛。这表明距离视点较远的渲染对象大多数是单纯地通过线图元进行表示的。虽然城市建筑多彩多样，但是对于距离视点较远的对象，其绝大多数细节经过透视投影后难以被观察到，通过直线表示的模型提供了清晰的轮廓和主体着色，经过实验验证(见图6b)与原始模型无明显差异，是一种较为有效的简化模型表示方法。此外，只有非常少的渲染对象以Splatting多边形的形式进行渲染，这与本文基于屏幕空间投影面积进行层次细节模型选择和渲染的原理吻合。

近年来，海洋水体可视化算法[10]普遍较为依赖片元着色器的计算能力，本文提出的渲染模型通过避免在LOD模型中使用纹理贴图降低渲染流水线中的片元着色器负载，从而提高海陆一体场景的整体渲染效率。为了评估本文算法的性能，本文在图6c的大场景中随机选取了3个数据量约为2GB的滨海城市场景进行实验。将混合LOD模型、几何LOD模型[13]与原始模型在相同的测试平台上通过输出横穿场景的漫游动画并统计每一帧的平均渲染时间的方式进行性能对比。实验结果如表1所示，本文提出的混合LOD算法与原始模型相比可以获得约10倍的性能提升，与几何LOD方法相比可以获得约4倍的性能提升。在加入海水水体渲染后，使用原始模型与几何LOD模型都出现了70至90%的性能下降；而使用混合LOD模型的渲染系统性能只出现了轻微的下降，横向比较中，海水水体的渲染时间也有明显减少。结果表明，本文算法具有更高的加速比，与海洋可视化算法结合的渲染性能较高，适用于海陆一体的海滨城市场景渲染。

5结语

本文提出了一种适用于海陆一体城市场景的LOD渲染方法。构建了由点、线等简单图元组成的三维模型近似表示，并基于屏幕空间投影面积进行了动态的LOD选择，实现了混合模型渲染输出。该方法构建的模型数据量小，具有较高的真实感，可以实现城市级三维场景的渲染，与基于三角网格与纹理贴图的渲染方法相比性能有明显的提高，且更适用于海陆一体城市场景的渲染，在“数字青岛”等海滨城市仿真与相关的地理信息系统应用项目中取得了良好的实用效果。

本文提出的模型采样和渲染方法在处理某些具有特殊色彩和亮度的高频特征时可能会出现视觉精度损失，如何通过渐进蓝噪声采样等方法改善采样点的均匀和随机分布将是本文下一阶段的研究重点。

参考文献：

[1]Hoppe H. Progressive meshes [C].//Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. New York: ACM, 1996: 99-108.

[2]Sander P V, Snyder J, Gortler S J, et al. Texture mapping progressive meshes [C].//Proceedings of the 28th annual conference on Computer graphics and interactive techniques. New York: ACM, 2001: 409-16.

[3]Peng C, Cao Y. A gpu-based approach for massive model rendering with frame-to-frame coherence[J]. Computer Graphics Forum, 2012, 31(2): 393-402.

[4]Yoon S E, Salomon B, Gayle R, et al. Quick-vdr: Out-of-core view-dependent rendering of gigantic models[J]. IEEE Transactions on Visualization and Computer Graphics, 2005, 11(4): 369-382.

[5]Gobbetti E, Marton F. Far voxels: A multi-resolution framework for interactive rendering of huge complex 3d models on commodity graphics platforms[J]. ACM Transactions on Graphics, 2005, 24(3): 878-885.

[6]刘波， 王章野， 王丽英，等. 大规模城市场景的高效建模及其实时绘制[J]. 计算机辅助设计与图形学学报， 2008， 20(9)： 1153-1162.

Liu B, Wang Z Y, Wang L Y, et al. Efficient modeling and real-time rendering of large-scale urban scenes[J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(9):1153-1162(in Chinese).

[7]马纯永， 陈勇， 韩永，等. 虚拟城市仿真中一种基于GPU的绘制加速算法[J]. 中国海洋大学学报(自然科学版)， 2010, 40(7): 141-144.

Ma C Y, Chen G, Han Y, et al. A GPU-based rendering accleration algorithm from urban simulation[J]. Periodical of Ocean University of China: Nature Science Edition, 2010,40(7),141-144(in Chinese).

[8]Cignoni P, Di Benedetto M, Ganovelli F, et al. Ray-casted blockmaps for large urban models visualization[J]. Computer Graphics Forum, 2007, 26(3): 405-13.

[9]Andujar C, Brunet P, Chica A, et al. Visualization of large-scale urban models through multi-level relief imposters[J]. Computer Graphics Forum, 2010, 29(8): 2456-2468.

[10]李文庆. VV-Ocean海洋环境仿真与海洋数据动态可视化系统的研究与实现[D].青岛： 中国海洋大学, 2011.

Li W. Research and implementation of VV-Ocean System on Marine Environment Simulation and Data Visualization[D]. Qingdao: Ocean University of China, 2011(in Chinese).

[11]Burr D C, Morrone M C, Spinelli D. Evidence for edge and bar detectors in human vision[J]. Vision Research, 1989, 29(4): 419-431.

[12]Luebke D P. Level of Detail for 3d Graphpics[M]. Burlington: USA Morgan Kaufmann Pub, 2003.

[13]Aydin T, Cadik M, Myszkowski K, et al. Video quality assessment for computer graphics applications[J]. ACM Transactions on Graphics, 2010, 29(6): 161-173.

责任编辑陈呈超

A Hybrid Rendering Approach for 3D Seaside Urban Scenes Visualization

ZHOU Sheng-Chuan1，2， HU Zhen-Biao1，2， MA Chun-Yong3， CHEN Ge3

(1.Qingdao Geotechnical Investigation & Surveying Research Institute， Qingdao 266033， China; 2.National & Local Joint Engineering Reseach Center for Sea-land Geographics Information Integration and Application， Qingdao 266033, China; 3.College of Information Science and Engineering, Ocean University of China， Qingdao 266100, China)

Abstract:A novel hybrid level-of-detail algorithm for large-scale seaside urban scenes rendering is introduced. We combine point, line, and splat-based rendering to synthesize large-scale urban city images. Points and lines are extracted through multi-jittered sampling and color-clustering, and encoded in a data structure that allows for automatically LOD selection. A screen-space projected area is used as the LOD selector. The algorithm selects lines for long distance views, uses points for midum-distance views, and introduces splatting for close-ups. Architecture models are then represented by few lines and points and provide high realistic rendering results. The experiment shows our approach is significantly faster than the textured models for rendering large-scale urban scenes, and is more suitable for seaside urban scenes visualization. The quality of the results is indistinguishable from the original as confirmed by algorithmic metrics.

Key words:level-of-detail； hybrid rendering； seaside city visualization； virtual reality

中图法分类号：TP391.9

文献标志码：A

文章编号：1672-5174(2016)01-138-07

作者简介：周圣川(1986-)，男，博士，高级工程师，主要研究方向为过程式建模、大规模数据可视化。E-mail：zhoushengchuan@qq.com

收稿日期：2014-03-04；

修订日期：2014-12-10

*基金项目：中央高校青年教师科研专项基金项目(201213019)

DOI：10.1644/j.cnki.hdxb.20140054

引用格式：周圣川， 胡振彪， 马纯永， 等. 海滨城市三维场景的混合图元渲染方法[J].中国海洋大学学报(自然科学版)，2016,46(1)：138-144.

ZHOU Sheng-Chuan，HU Zhen-Biao，MA Chun-Yong ，et al. A hybrid rendering approach for 3D seaside urban scenes visualization[J]. Periodical of Ocean University of China, 2016, 46(1): 138-144.

Supported by Research Funds for the Youth Teacher of Central University(201213019)