基于GPU的海量离散点高程并行插值算法*

王智广,张腾畅,吴相锦,鲁 强1，

(1.中国石油大学(北京)石油数据挖掘北京市重点实验室，北京 102249；2.中国石油大学(北京)计算机科学与技术系，北京 102249;3.北京中油瑞飞信息技术有限责任公司，北京 102206)

1 引言

在遥感测绘技术快速发展的背景下，测绘获得的地形数据规模也随之增大。实际工程有对三维地表上实时渲染海量离散点并支持对其进行基本编辑交互操作的迫切需求。因此，对地表数据进行空间分析具有必要性[1]。三维地表上海量离散点对渲染速率、渲染品质和实时交互具有较高的要求，因此通常采用插值算法实时获取离散点所在地表处的实际高程值，并赋值给该点进行显示[2]。在目前国内外的研究中，对海量离散点的三维实时渲染存在如下2方面的缺陷：

(1) 地表网格实时改变使得渲染速率偏低。已有研究使用CPU实现相应的高程插值算法[3]获取地表某处实际高程，并将其赋给位于该处的地标物，使之嵌入到三维地表网格中[4]，同时由于三维地表是基于细节层次模型LOD(Levels of Detail)结构，其网格结构会实时发生改变，为保证渲染精度需动态执行插值算法[5]，因此当待渲染数据量过大时，整个三维场景的渲染速率大幅降低。

(2) 传统的纹理贴图方式降低了数据渲染品质与空间分析能力[6]。为解决此问题，研究者对矢量数据预处理生成多层纹理对象，并投影到对应层次的三维地表[7]。该方式在某种程度上提高了场景的渲染速率，但使得矢量丧失了立体感，从而降低了渲染品质[8]，同时纹理对象的预处理生成导致其无法较好地支持基本编辑交互操作，极大影响了矢量数据的空间分析能力[9]。

本文在已有研究的基础上，针对海量离散点提出了基于GPU的高程并行插值算法，利用GPU编程语言GLSL(OpenGL Shading Language)[10]编写着色器程序，动态控制图形渲染管线并行获取高程数据和自定义片元着色，在渲染速率和渲染品质上有了极大提高，并支持数据的实时编辑交互。

2 基于GPU的高程插值算法

2.1 原始数据组织

本文算法通过GPU编程实现海量离散点在三维地表上的并行加速渲染与编辑交互，因此高效地对海量离散点数据和原始地表高程数据进行组织与管理[11]直接影响数据在内存与显存间传递的效率，为将离散点渲染量级从百万级提高到千万级提供了数据组织基础。研究内容包含2个方面：

(1) 海量离散点数据组织方式。

根据实际应用要求，离散点的存储方式为按线存储，即一系列离散点组成一条逻辑线，每条线中包含3个指针ptrv、ptrc和ptrf，分别指向GPU对应的3个顶点缓冲区VertexBuffer，这3个缓冲区分别存储线上离散点序列的顶点、颜色和标志3类数据，缓冲区作为内存-显存数据交换区域，为基于GPU的渲染算法提供基础数据。

(2) 三维地表高程数据组织方式。

由于地表网格实时变换，本文算法创建高程纹理队列，用于存储不同分辨率的二维纹理对象，根据当前地表网格采样点变换情况，将数据存入队列内相应的纹理对象中。纹理对象行列数、所占存储大小及其处理最大地表网格数据大小的对应关系如表1所示。

Table 1 Storage of digital elevation model grid data

本文研究的三维地表对象均为规则网格数据，地表数据分层分块组织，每个地形块的采样点个数一致(默认为64×64),单个地表级数不超过表1中所示的8级，根据纹理大小列中数据显示，本文算法的硬件实验环境允许将纹理队列一次性放入显存中。

2.2 算法描述

以2.1节中数据作为输入，本文算法通过高程纹理生成、高程并行插值和图元纹理采样3个主要过程实现海量离散点在三维地表上的实时渲染，为离散点渲染从百万级提高到千万级提供算法基础，算法的流程图如图1所示。

Figure 1 Flow chart of the algorithm proposed in this paper图1 本文算法流程图

对图1所描述算法的具体步骤说明如下：

Step 1在进行离散点渲染前，将三维地表作为输入数据通过图形渲染管线进行一遍离屏渲染，生成对应的高程纹理对象DTEX并通过调用DMAP.PUT(DISv,DTEX)将其存入高程纹理队列，其中DISv表示当前视距，DISv∈(0，DISmax]，DISmax表示三维场景载入时的视距，设为最大标准视距。

Step 2根据当前视距DISv从高程纹理队列中获取对应的高程纹理对象DTEX=DMAP.GET(DISv)，并通过uniform块数据将DTEX、地表包围盒TB和网格采样间隔SINTVAL封装成统一值块，批量从内存传入GPU显存中。显存中uniform块数据结构如下所示,其中vec3为三维向量数据类型：

uniformUniforms{

Sampler2DDTEX;

Sampler2DIMAGETEX;

floatDISv;

floatSINTVAL;

vec3TB.min;

vec3TB.max;}

结构封装使得内存-显存间的数据传递更加高效。

Step 3执行顶点着色器程序SHv，根据式(1)计算离散点在高程纹理中对应的纹理坐标，并将其作为输出数据传入渲染管线的下一阶段。式(1)中Vertex为图形渲染管线中内置向量型四维向量数据类型vec4的变量，表示被当前着色器处理的顶点的坐标，纹理坐标TC∈[0,1]：

(1)

(2)

Figure 2 Diagram of discrete point图2 离散点分布示意图

Step 4在完成高程插值后，需对顶点坐标进行变换，将其从初始时模型坐标系转换到二维屏幕坐标中，该过程如式(3)所示，三维点坐标通过右乘模型-视图变换矩阵Matrixmv、投影变换矩阵Matrixp和视口矩阵Matrixv完成到二维显示坐标的转换。其中(xm,ym,H0)表示点的模型坐标，(xw,yw,zw)表示经过转换后的屏幕坐标，第三维zw仅表示深度值，用于进行深度裁剪。在图形管线中可实时获取Matrixmv和Matrixp。最后，根据二维显示窗口的参数：起始二维坐标值(x0,y0)、屏幕深度范围(zmin,zmax),显示窗口长度width和显示窗口宽度height，确定视口变换矩阵Matrixv。

(3)

Step 5执行片元着色器程序SHf，其主要完成的功能是根据离散点的采样坐标glpointCoord从对应的图像纹理中获取像素值。如式(4)所示，根据点的采样坐标获取图像纹理对应位置的颜色值。

FragColor=

texture2D(IMAGETEX,PointCoord.xy)

(4)

其中texture2D是GLSL中默认的纹理采样函数，其作用是根据纹理坐标从二维纹理对象对应位置获取元素值。

Step 6如果三维场景视点信息发生变化后导致地表网格数据发生改变，而DMAP中没有相应的高程纹理对象DTEX，则跳转到Step 1；对离散点进行编辑操作并改变数据状态后，跳转到Step 2；否则结束三维场景的渲染。

3 实验设置与结果

3.1 实验环境

本文算法效率主要受硬件条件的影响，表2列出了2组不同的实验环境影响算法执行效率的主要指标，其中CPU均为Intel Xeon系列，GPU均为NVIDIA Quadro系列。如无特殊说明，在接下来内容中，本文用CPU1、CPU2、GPU1、GPU2分别表示表2中的CPU与GPU型号。

Table 2 Hardware environment表2 实验硬件环境

3.2 实验结果

实验主要针对海量离散点在三维地表上进行实时渲染，实验中引入变量k=DISmax/DISv，用以度量当前场景视距；图3～图6是基于本文算法实现的效果图，分别表示在由远到近不同视距对应的k值下离散点的显示情况。由图3～图6中可以看出，离散点能够紧密贴合在各分辨率地表网格上，从显示效果上，离散点的显示具有较强的立体感，同时可以根据视点动态调整朝向，并且算法可为不同属性的点对象贴合不同的纹理图案，从而极大提高渲染品质。

Figure 3 Diagram of rendering while k=1图3 k=1时离散点渲染示意图

Figure 4 Diagram of rendering while k=2图4 k=2时离散点渲染示意图

Figure 5 Diagram of rendering while k=5图5 k=5时离散点渲染示意图

Figure 6 Diagram of rendering while k=10图6 k=10时离散点渲染示意图

实验还测试了传统CPU高程插值算法和本文基于GPU高程插值算法对三维场景渲染速率的影响。测试结果如表3～表6所示。其中n表示待渲染的离散点数量取值，单位是万个，表格中的数据表示在数量级为n、视距为k的情况下场景的渲染速率FPS(Frame Per Second)，单位为帧/秒。传统CPU高程插值算法理论上最大能支持量级为一百万的离散点进行渲染，但实际速率很低，因此本文为将其与基于GPU的高程插值算法进行对比，选取的最大离散点数量为60万个。

Table 3 FPS of CPU1 rendering

Table 4 FPS of CPU2 rendering

Table 5 FPS of GPU1 rendering

Table 6 FPS of GPU2 rendering

3.3 实验分析

(1)图7表示在视距DISv较大情况下，布设的离散点均需显示在二维窗口内时，随着离散点数量增多，2组不同的硬件环境分别执行传统CPU插值算法与本文基于GPU高程插值算法渲染速率对比图；图8则表示在DISv较小情况下离散点的渲染速率对比。

Figure 7 Comparison of rendering rate with far distance图7 远视距下离散点渲染速率对比

由于传统CPU插值获取高程方式只能支持百万级内量级的离散点正常渲染，而本文算法使离散点三维渲染量级扩展到千万级，因此对GPU1、GPU2实现的基于GPU高程插值算法的速率进行进一步测试，其结果图9所示。图9表示了在视距DISv较大，所有离散点均处于二维显示窗口内时，随着点的量级增大，场景帧速率FPS的变换情况。由图9可知，FPS变换分为3个阶段：

Figure 8 Comparison of rendering rate with near distance图8 近视距下离散点渲染速率对比

Figure 9 Diagram of the rendering based on GPU图9 GPU加速渲染离散点速率示意图

①当离散点数量n<50万时，由于场景待渲染模型较少，导致FPS较低，因此n不是影响场景效率的主要因素；

②当离散点数量50万≤n<200万，FPS下降速率较大，其原因是由于n的迅速增大，几何着色器中执行操作的插值算法消耗了大量的时间；

③当离散点数量n≥200万，许多离散点超出视锥体范围，图形渲染管线会对这一部分模型进行裁剪剔除，因此实际渲染数据并未按照线性直接增长，FPS下降速率降低。

从图8的渲染结果可以看出，在视距较小的情况下，只有部分点出现在二维显示窗口内，此时采用传统CPU插值算法，渲染速率随离散点的数量增加明显下降。如果采用基于GPU高程插值算法，其速率下降幅度较小。其原因是：

①采用传统CPU插值算法时，影响系统渲染速率的主要因素是计算离散点高程所消耗的时间，当视距减小后，仍需计算所有离散点高程值，因此速率随之下降较快。

②采用基于GPU高程插值算法，高程的计算由GPU内部的几何着色器并行完成，因此影响渲染速率的主要因素为场景内离散点的数量；当视距减小时，渲染管线将位于视锥体外部的离散点自动裁剪，大规模地减少了待渲染离散点数量。所以，当视点较近时，采用GPU高程插值算法可以保持场景渲染的较高速率。

Figure 10 Diagram of the rendering with the different distances图10 不同视距下GPU渲染离散点速率示意图

4 结束语

本文对基于GPU的海量离散点的高程并行插值算法进行了深入的讨论，在三维地表原始高程数据基础上提出了高程纹理这一结构作为算法的基础，该数据结构可有效地组织不同网格分辨率下的地表高程数据；在此基础上，通过GLSL编写的GPU着色器程序动态控制图形渲染管线，在几何着色器中，通过本文设计的插值算法并行获取离散点高程数据，极大提高了渲染速率，并在着色阶段对纹理进行采样，在不影响效率的前提下提高了渲染品质。最后，通过详细的实验对本文算法进行验证，显示了其可行性。

在海量离散点渲染过程中，视点远近决定了投影在二维显示窗口内离散点的个数，进而直接影响渲染速率。未来将进一步研究视点相关的调度算法，将显示窗口中一次渲染总量控制在一定范围内，提高远视距下场景渲染速率。