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

摘要

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

主权项

一种基于kd树的实时大规模地形可视化实现方法，其特征在于，包括下述步骤：将地形按点云空间分块，并利用kd树分层，离线地建立LOD模型，所述建立LOD模型是负责由地形点云数据获得多分辨率模型数据以及模型的各分辨率间切换；在线时利用外部存储算法将离线构造的LOD模型数据载入内存，所述外部存储算法负责将外存的LOD模型数据向内存调度；对内存中的LOD模型数据使用简化的地形剔除技术，所述地形数据剔除技术负责剔除不可见的LOD模型数据，减少传输到图形硬件的数据量；利用三维引擎优化技术对剔除后的数据进一步的减少传输到图形硬件的数据量以及计算量；所述建立LOD模型，包括建立离线LOD模型和建立在线的LOD模型两部分，所述建立离线LOD模型需要读取三次点云数据文件：第一次读取获得点的总数，根据提前限定的每个分块内的点的最大点数，设定每个分块的位置和大小；第二次读取记录前面设定的每个分块的内点数；第三次读取时用经典的逐点插入法进行Delaunay三角化，并将对应分块记录的点数递减；当递减为零时，查找对应分块内外接圆越过分块边缘的三角形和它们的顶点，记录为分割三角带和点云包围圈；对在分块内而不在点云包围圈内的点进行改进的kd树空间划分，获得按照树的层次顺序排列的存储在一维数组点云数据，将该点云数据、分割三角带和点云包围圈存储到外存中；清除该分块占用的内存，继续读取，直到所有点云数据读完；所述的外部存储算法包括改进的数据预读、视椎体投影的数据补充和增量计算三部分；所述改进的数据预读使用了两层的预读区，即在一般预读区外围再设定一个分辨率更低的预读区；所述的视椎体数据补充，是将视椎体映射到二维平面，然后找出与映射相交的分块；所述的增量计算，是将由所述改进的数据预读和所述的视椎体数据补充获得的调度列表中的分块中需要调度的数据，即对应需要分辨率的LOD模型数据和在内存中对应分块中已有的数据做比较，算出需要调度的具体到一个点的数据。