一种基于kd树的实时大规模地形可视化实现方法

摘要

本发明公开了一种基于kd树的实时大规模地形可视化实现方法，包括下述步骤：将地形按点云空间分块，并利用kd树分层，离线地建立LOD模型，所述建立LOD模型是负责由地形点云数据获得多分辨率模型数据以及模型的各分辨率间切换；在线时利用外部存储算法将离线构造的LOD模型数据载入内存，所述外部存储算法负责将外存的LOD模型数据向内存调度；对内存中的LOD模型数据使用简化的地形剔除技术，所述地形数据剔除技术负责剔除不可见的LOD模型数据，减少传输到图形硬件的数据量；利用三维引擎优化技术对剔除后的数据进一步的减少传输到图形硬件的数据量以及计算量。本发明实现简便，显示效率高，在具有一般基于不规则三角网可视化算法优良的可视化效果的同时，大大提高了可视化速度。

说明书

技术领域

本发明涉及大规模地形点云的三维可视化的技术领域，特别涉及一种基于 kd树的实时大规模地形可视化方法。

背景技术

地形点云三维可视化，就是根据计算机图形学的原理，将三维地形数据（包 括离散的点云和点间形成的三角形片集的点序列）经过视图变换、模型变换、 投影变换和视区变换等一系列操作，最后在二维的屏幕上显示出来。而当地形 数据量很大时，要进行变换的操作数量也会随之剧增，这就需要使用一些提高 地形数据三维可视化效率的算法，才能满足其实时显示的要求。

业界对高效的地形数据三维可视化研究的成果主要集中在LOD模型构造算 法上面，对三维可视化的其他研究还包括地形数据剔除技术和三维引擎的优化 使用等。

LOD模型构造算法，能够根据需求动态地调整显示对象模型的精度，大大 减小可视化的数据量，以达到提高可视化效率的目的。这种算法的关键是如何 建立一个高效的多分辨率模型，涉及到二叉树、四叉树、kd树等空间划分方法、 各种内存管理技术和各种Delaunay三角网更新或者规则点云分布三角网构建方 法等。

地形数据剔除技术，能够在地形数据不会被显示的时候将其剔除，即不发 往图形硬件去绘制，以大幅减少可视化的数据量，达到提升显示速度的目的。 该技术的关键是如何高效地定位可见的地形数据。

三维引擎的优化使用，能够在显示地形数据量不变的情况下大大的减小传 输的数据量和重复计算量，以大大提升显示速度的目的。常见的优化有三角形 条带化和OpenGL顶点数组和索引数组的使用。

现有的基于TIN的高质量的海量地形点云可视化算法，基本是采用了记录 三角网简化的过程信息。虽然避开了实时进行Delaunay三角网的更新这一复杂 的过程，但是复杂性仍然非常高，效率不理想。

本发明的方法，正是在具有基于TIN可视化算法的高质量显示的同时，很 好地改善了效率。

发明内容

本发明的目的在于克服现有技术的缺点与不足，提供一种复杂性低、可视 化效率高的基于kd树的实时大规模地形可视化实现方法。

为了达到上述目的，本发明采用以下技术方案：

一种基于kd树的实时大规模地形可视化实现方法，包括下述步骤：

将地形按点云空间分块，并利用kd树分层，离线地建立LOD模型，所述建 立LOD模型是负责由地形点云数据获得多分辨率模型数据以及模型的各分辨率 间切换；

在线时利用外部存储算法将离线构造的LOD模型数据载入内存，所述外部 存储算法负责将外存的LOD模型数据向内存调度；

对内存中的LOD模型数据使用简化的地形剔除技术，所述地形数据剔除技 术负责剔除不可见的LOD模型数据，减少传输到图形硬件的数据量；

利用三维引擎优化技术对剔除后的数据进一步的减少传输到图形硬件的数 据量以及计算量。

优选的，所述建立LOD模型，包括建立离线LOD模型和建立在线的LOD 模型两部分，所述建立离线LOD模型需要读取三次点云数据文件：第一次读取 获得点的总数，根据提前限定的每个分块内的点的最大点数，设定每个分块的 位置和大小；第二次读取记录前面设定的每个分块的内点数；第三次读取时用 经典的逐点插入法进行Delaunay三角化，并将对应分块记录的点数递减；当递 减为零时，查找对应分块内外接圆越过分块边缘的三角形和它们的顶点，记录 为分割三角带和点云包围圈；对在分块内而不在点云包围圈内的点进行改进的 kd树空间划分，获得按照树的层次顺序排列的存储在一维数组点云数据，将该 点云数据、分割三角带和点云包围圈存储到外存中；清除该分块占用的内存， 继续读取，直到所有点云数据读完。

优选的，所述的改进的kd树空间划分包括第一改进和第二改进，所述第一 改进是kd树的划分方向改为要划分区域的长轴方向；第二改进是kd树的划分 点为满足每次划分尽量将不完整的一层向左子树分布。

优选的，所述的建立在线的LOD模型，包括简化的模型分辨率决策准则和 动态更新Delaunay三角网两部分；所述简化的模型分辨率决策准则根据每个分 块内的点密度和分块与视点的距离，计算出分块需要切换至的模型分辨率，在 长度为l的物体在与它相距d的视点的观察下，被投影到屏幕上；且有如下的关 系式：

$n_p=\frac{l}{2d\tan \frac{\alpha }{2}}{N}_p$

其中α为视角，N_p为屏幕在视点视野范围内的纵向切线上的像素数目，n_p是该物体投影到屏幕上在该切线上占用的像素数目；

当n_p＝1时，即此时物体投影到屏幕在切线上占用一个像素时，下式即为模 型分辨率决策的基本准则，公式如下：

$l=\frac{2d\tan \frac{\alpha }{2}}{N_p}$

此时，长度小于等于l的物体在屏幕上被压缩在一个像素内，这时的物体的 细节已经无法分辨了，所有在该物体上的点云只需用一个顶点表示即可。

优选的，所述的动态更新Delaunay三角网使用一种成熟的插入和删除点的 Delaunay算法，同时在更新三角形的更新一个N×7的二位数组，其中N代表 三角形的个数，7列分别是三角形的序号、三个顶点和三个顶点相对的相邻三角 形序号。该二维数组表示了整个三角网的拓扑结构。

优选的，所述的外部存储算法包括改进的数据预读、视椎体投影的数据补 充和增量计算三部分；所述改进的数据预读使用了两层的预读区，即在一般预 读区外围再设定一个分辨率更低的预读区；所述的视椎体数据补充，是将视椎 体映射到二维平面，然后找出与映射相交的分块；所述的增量计算，是将由所 述改进的数据预读和所述的视椎体数据补充获得的调度列表中的分块中需要调 度的数据，即对应需要分辨率的LOD模型数据和在内存中对应分块中已有的数 据做比较，算出需要调度的具体到一个点的数据。

优选的，所述的地形数据剔除技术，与所述视椎体数据补充一致，并直接 使用其计算结果。

优选的，所述的三维引擎优化使用，由简化的三角形条带化和顶点对象缓 冲区的使用两部分组成；所述的简化的三角形条带化，基于一个包含三角形的 序号、三角形逆时针排列的三个顶点和三角形的三个相邻三角形的序号的三角 网拓扑结构数据，并按照以下方法得出：

优选的，所述的三维引擎优化使用的具体步骤如下：

（a）根据结构矩阵，在三角网的外围边界上找出一个三角形A，该三角形 必须满足其三边都有相邻的三角形，然后找出A三角形的一个相邻的三角形B， 该三角形必须满足其有一边没有相邻的三角形，三角形B就是起始三角形；

（b）螺旋式由外至内地找相邻三角形，由起始三角形B开始，沿着远离A 的方向，在结构矩阵中依次查找出下一个相邻的、靠外的三角形，标记并将其 加入到三角形条带中；

（c）结束，当找不到没有标记的三角形时，三角形条带完毕，并查找出结 构矩阵中没有加入到条带的三角形，单独添加到游离三角形链中。

优选的，所述的顶点对象缓冲区的使用是在一般的三维引擎优化，即 OpenGL的顶点数组和索引数组结合使用的基础上，加入顶点缓冲区对象的使 用。

本发明相对于现有技术具有如下的优点及效果：

1、本发明实现简便，显示效率高，在具有一般基于不规则三角网可视化算 法优良的可视化效果的同时，大大提高了可视化速度。

2、本发明在外存中只存储点云数据和少量的三角形数据，绝大多数的三角 形数据实时地在内存中生成和存放，故较其他可视化算法大大减少了外存的使 用。

3、本发明充分利用了多核处理器的优势，相比其他可视化算法更能适应以 后的多核发展方向。

4、本算法能容易地实现针对不同硬件平台平衡显示效果和显示速度矛盾。

附图说明

图1是本发明算法的框图；

图2（a）是本发明第一次读入点云数据时的示意图；

图2（b）是本发明第二次读入点云数据时的示意图；

图3（a）是本发明对kd树第一改进前的空间分割效果图；

图3（b）是本发明对kd树第一改进后的空间分割效果图

图4（a）是本发明对kd树第二改进前的空间分割效果图；

图4（b）是本发明对kd树第二改进后的空间分割效果图；

图5（a）是本发明对kd树第二改进前的树的结构及在内存的存储状况图；

图5（b）是本发明对kd树第二改进后的树的结构及在内存的存储状况图；

图6（a）是本发明的改进的数据预取范围图；

图6（b）是本发明的改进的视点移动时的数据预取范围图；

图7是本发明所述的外存算法的增量数据交换示意图；

图8是本发明所述的模型分辨率决策准则原理图；

图9是本发明生成的三角形网及其拓扑结构示意图；

图10（a）是本发明的简化的视椎体投影示意图；

图10（b）是本发明的分块和视椎体投影图；

图11是OpenGL的顶点数组、索引数组和顶点缓冲区对象使用比较图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方 式不限于此。

实施例

如图1所示，本实施例提供的基于kd树的实时大规模地形可视化实现方法， 包括下述步骤：包括下述步骤：

将地形按点云空间分块，并利用kd树分层，离线地建立LOD模型，所述建 立LOD模型是负责由地形点云数据获得多分辨率模型数据以及模型的各分辨率 间切换；

在线时利用外部存储算法将离线构造的LOD模型数据载入内存，所述外部 存储算法负责将外存的LOD模型数据向内存调度；

对内存中的LOD模型数据使用简化的地形剔除技术，所述地形数据剔除技 术负责剔除不可见的LOD模型数据，减少传输到图形硬件的数据量；

利用三维引擎优化技术对剔除后的数据进一步的减少传输到图形硬件的数 据量以及计算量。

该方法具体实施分为离线预处理和在线实时处理两部分；所述离线处理对 应着建立LOD模型算法的离线LOD模型的建立部分；所述在线实时处理的主 线程和Delaunay三角化、条带化子线程对应了建立LOD模型算法的在线的LOD 模型更新部分；所述在线实时处理的主线程包括外部存储算法和地形数据剔除 技术；所述在线实时处理的Delaunay三角化、条带化子线程包括了三维引擎的 优化使用。

如图2（a）和图2（b）所示，本实施例的建立离线LOD模型在第一次和 第二次读入点云数据时分别确定点云总数和分块的位置和大小。本实施例对一 般的计算机硬件采取分块内平均大约10000个点，由此算出分块的大小和位置。 在第三次读数据时，每读入一个点，都用经典的逐点插入法进行Delaunay三角 化，并将对应分块记录的点数减一。当某分块记录的点数递减为零时，查找该 分块中外接圆越过分块边缘的三角形和它们的顶点，记录为分割三角带和点云 包围圈。对在分块内但不在点云包围圈内的点进行改进的kd树空间划分，获得 按照树的层次顺序排列的存储在一维数组点云数据。将该点云数据、分割三角 带和点云包围圈存储到外存中。当完成上述步骤，清除该分块占用的内存，以 供新读入的点云数据使用。这样的步骤一直进行，直到所有点云数据读完。

如图3(a)、图3(b)所示，本实施例对kd树进行的第一个改进，(a)(b)(c)(d) 分别为顺序的四次空间划分，图3(a)为经典的kd树顺序按照x、y、x、y的方向 划分，图3(b)为本实施例第一改进之后的划分，该划分每次都把需要划分的区域 的长轴作为划分方向。可见改进后的划分子空间中出现狭长形状的较少，这样 更均匀的空间划分能够更好地用于构造多分辨率模型。

如图4（a）、图4（b）和图5(a)、图5(b)所示，本实施例对kd树的第二个 改进效果，本改进意在提高存储空间使用效率。图4（a）中改进前和图4（b） 中改进后的空间分布均匀程度类似，没有明显的差别。如图5(a)、图5(b)所示， 第二改进是尽量将不完整的一层向左子树分布，由于为了提高存储效率和灵活 性，本实施例采用一维数组来存储kd树划分的数据，具体操作是：若kd树中 某节点存储在位置n，其左子节点则存储在2n，其右子节点则存储在2n+1。改 进二在这种存储方式下可以克服内存空间浪费的缺点，图中的改进就减少了7 个单位内存块的浪费。需要说明的是，这样的改进带来的问题是，最后的一层 丢失了和父节点的联系信息，而这对于我们的算法是没有影响的。

如图6（a）和图6（b）所示，和一般的只在视点周围一定范围内设定一个 预读区不一样，本实施例在经典的预读区外再设定了外层预读区，如图6的（a） 中的a区域外层的b区域。为了节省内存，外层预读区的预读数据低于由模型 分辨率决策准则计算所得的分辨率。当视点缓慢移动的时候，预读区跟随着如 图移动，这样产生的调度列表在增量计算的时候有很大部分会获得较好的结果。

如图7所示，本发明的内存和外存存储LOD的模型数据，即kd树划分的 点云数据，都是用一维数组，这在当要进行数据交换的时候是非常简便和迅速 的。于是，在外部存储算法中的预读数据和视椎体投影补充后，针对得到的调 度列表里面的每个分块，对比内存中已存在的一维数组中的数据，计算需要调 度进内存的点块即可。由于数据是按照划分层次顺序存储的，每次的调度都是 连续的一片数据，效率很高。

如图8所示，本发明的模型分辨率决策准则计算可以由此获得。长度为l的 物体在与它相距d的视点的观察下，被投影到屏幕上。其中α为视角，N_p为屏 幕在视点视野范围内的纵向切线上的像素数目，n_p是该物体投影到屏幕上在该 切线上占用的像素数目。所述简化的模型分辨率决策准则根据每个分块内的点 密度和分块与视点的距离，计算出分块需要切换至的模型分辨率；其说明如下：

长度为l的物体在与它相距d的视点的观察下，被投影到屏幕上。其中α为 视角，N_p为屏幕在视点视野范围内的纵向切线上的像素数目，n_p是该物体投影 到屏幕上在该切线上占用的像素数目。各个量间有以下式（1）关系：

$n_p=\frac{l}{2d\tan \frac{\alpha }{2}}{N}_p---\left(1\right)$

当n_p＝1时，即此时物体投影到屏幕在切线上占用一个像素时，上式变为式 （2）：

$l=\frac{2d\tan \frac{\alpha }{2}}{N_p}---\left(2\right)$

此时，长度小于等于l的物体在屏幕上被压缩在一个像素内。这时的物体的 细节已经无法分辨了，所有在该物体上的点云只需用一个顶点表示即可。

式子（2）就是本实施例中模型分辨率决策的基本准则，其基本的思路就是， 当分块内当前层点云的平均点距小于等于l时，即认为模型层次切换条件满足， 此时模型将被切换到更粗糙的分辨率层次，满足新的分辨率层次中分块内点云 平均点距大于l；相对地，如果存在更细节的层次中点云的平均点距也大于l， 则也进行切换，保证当前层次中点云的平均点距恰大于l。

而该式计算比较复杂，且由于屏幕的分辨率和视角对于所有的分块是一样 的，故可以对其进一步简化。第一个简化是将计算的对象由点变成分块，这样 可以大大减少计算量。第二个简化是（2）式可以进一步简化为式（3）：

l=k_cd    （3）

该简化得以进行是由于屏幕的分辨率和视角对于所有的分块是一样的，经 过这两步简化，在进行模型分辨率切换的时候CPU的计算量非常小。在公式（3） 中，k_c可以变换如下

$k_c=\frac{2d\tan \frac{\alpha }{2}}{N_p}$

是在算法系统启动的时候就确定了的，或者是当改变视角α会相应改变，可 以认为是“常量”。而各分块每一层次的点云间平均距离l也是可以提前算出来 的，由于本发明每个分块的大小是固定相同的，kd树的相同层次节点数是相 同的（除了该层节点未满），所以每个分块中各个层次的点云间平均距离l也是 在读入数据之后就固定相同的，也可以认为是“常量”。所以实现的时候甚至可 以计算出每个分辨率层次对应的只需视点与每个分块的d与之对比即可获 得需要切换到的分辨率层次。

如图9所示，本发明在动态更新Delaunay三角网中同时更新的表示三角网 的拓扑结构的数据就是图中右方的表，称为结构矩阵。该数据结构是一个n×7的 表，七列的对应解释为：NO为三角形的序号，V1、V2、V3分别是该三角形 逆时针排列的三个顶点；OT1、OT2、OT3分别是该三角形的三个相邻三角形 的序号，它们分别与V1、V2、V3相对，如果该序号为0，则表明该顶点对应 的边上没有相邻的三角形。根据该拓扑结构，很容易得到各个三角形间的相邻 连接关系。通过这个相邻关系由外至内地查找连接着的三角形，最后形成一个 三角形带，就是本文三角形条带化的基本思想。

该算法的步骤是：

（a）根据结构矩阵，在三角网的外围边界上找出一个三角形A，该三角形 必须满足其三边都有相邻的三角形。然后找出A三角形的一个相邻的三角形B， 该三角形必须满足其有一边没有相邻的三角形。三角形B就是起始三角形。

（b）螺旋式由外至内地找相邻三角形。由起始三角形B开始，沿着远离A 的方向，在结构矩阵中依次查找出下一个相邻的、靠外的三角形，标记并将其 加入到三角形条带中。

（c)结束。当找不到没有标记的三角形时，三角形条带完毕。并查找出结构 矩阵中没有加入到条带的三角形，单独添加到“游离三角形”链中。

需要注意的是，这只是一个简单快速的三角形条带化算法。它可能会在条 带化的过程中遗漏部分三角形，所以需要在完成条带化的时候检查三角形的添 加情况，将没有被添加的加入到一条称为“游离三角形”的链中。

如图10(a)和图10（b）所示，本实施例中的视椎体数据补充和地形数据剔 除技术，都将视椎体映射到二维平面，即只利用视椎平截头体的八个顶点的平 面坐标，由此得到一个在xy平面上的凸多边形。然后找出与该多边形相交的分 块，这些分块就是可见的分块。

所述查找多边形和分块相交的算法，过程为判断各个分块的四个顶点与多 边形的包含关系，四个顶点只要有一个位于多边形内部，则判断该分块与多边 形相交。本发明使用的判断顶点与多边形的包含关系的算法是经典的判断点是 否在多边形内部的点线判别法，其基本原理是通过判断点和多边形的边的同侧 关系判断点是否在多边形内部。

如图11所示，所述顶点对象缓冲区的使用是在一般的三维引擎优化，即 OpenGL的顶点数组和索引数组结合使用的基础上，加入顶点缓冲区对象的使 用。图中的上面的图是仅仅使用顶点数组的传输示意图，每次更新Delaunay三 角网后，点云数据都需要重新排列，然后再发往图形硬件渲染。其优点在一次 全新的绘制当中，传输的数据量是最少的，而缺点是重新排列点云数据需要大 量的处理时间；图中的中间的图是结合顶点数组和索引数组的传输示意图，每 次更新Delaunay三角网后，点云数据不需要重新排列，只需要改变索引数组， 其优点是大大减少重新排列点云数据的处理时间，缺点是增加了索引数组的传 输，并且同时传输两个数组会造成图形硬件的带宽使用不合理，波动大。图中 的下图是在使用顶点数组和索引数组的基础上再加入顶点缓冲区对象的传输示 意图，该使用将预读的数据异步地存储到顶点缓冲区对象中，当计算完需要绘 制三角形条带时，再向图形硬件传输索引数组，这样，图形硬件的带宽使用波 动会更小，提高了图形硬件的带宽使用效率。更重要的是，当点云数据已经存 在图形硬件中的时候，就不需要再传输顶点数组，这样大大减少了传输的数据 量，从而提高了可视化效率。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实 施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、 替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。