EN中文

Journal of Geo-information Science >

2023 , Vol. 25 >Issue 5: 967 - 981

DOI: https://doi.org/10.12082/dqxxkx.2023.220589

An Edge-locking LOD Method for Eliminating Boundary Cracks in 3D Geological Models

  • WANG Zhenjuan ,
  • HUA Weihua , * ,
  • LIU Xiuguo ,
  • ZHENG Peng ,
  • XIAO Yini ,
  • WEN Long
Expand
  • School of Geography and Information Engineering, China University of Geosciences, Wuhan 430074, China
*HUA Weihua, E-mail:

Received date: 2022-08-14

  Revised date: 2022-10-14

  Online published: 2023-04-27

Supported by

National Key Research and Development Program of China(2019YFC0605102)

National Natural Science Foundation of China(41972307)

Fold

Abstract

In response to the problem of poor continuity when using traditional LOD generation algorithms to render large-scale 3D geological models, this paper puts forward a kind of edge-locking LOD method to eliminate boundary cracks in 3D geological models. To begin with, the triangular grid partitioning issue is quickly transformed into a graph partitioning problem using a multi-level graph partitioning algorithm, which divides the triangular grid into a series of clusters and cluster groups of similar size based on spatial adjacency and executes the multi-level graph partitioning algorithm with parallel computation to improve the partitioning efficiency. Next, the grid simplification algorithm based on quadratic error metric locks the boundaries of cluster groups for simplification to generate higher level LOD. In the simplification phase, edge-locking simplification is achieved by increasing the boundary edge weights of cluster groups at each level of LOD, while at the same time, DAG dependencies of clusters and cluster groups at different levels of LOD are constructed from the bottom up. Finally, the LOD progressive data blocks at all levels of the model are efficiently generated and the paging mechanism is utilized to encode cluster and cluster group data blocks, thus taking full account of the spatial adjacency of the data and DAG dependencies so that a minimum number of Pages are loaded simultaneously at runtime. In this paper, the 3D geological models with different scales and complexity constructed from borehole data are selected for data validation, in which A is constructed from 189 borehole data to obtain 21 standard strata with a data size of 50MB and an area of 3337 km2; B is constructed from 6489 borehole data to obtain 43 standard strata with a data size of 139 MB and an area of 123 km2. After accessing the data file in Obj format, the LOD is constructed by performing operations on the model such as delineation of clusters and cluster groups, mesh simplification of constrained outer boundaries, as well as encoding the clusters and cluster groups data of the LOD. The experimental findings indicate that the approach proposed in the paper can generate LOD with a simplification rate of approximately 50% at all levels to eliminate cracks between high and low precision data blocks of the 3D geological model, achieve better continuity expression when visualizing 3D geological models, have better rendering effects, which can satisfy the requirements of high-quality visualization of multi-scale large-scale 3D geological models, and is applicable to urban underground space engineering, digital mines, and other fields, as well as providing support for the transparency of underground space and visualization of large-scale geological models.

Key words： LOD; 3D geological model; crack; edge-locking; cluster; cluster group; multilevel graph partitioning algorithm; QEM algorithm

Cite this article

WANG Zhenjuan , HUA Weihua , LIU Xiuguo , ZHENG Peng , XIAO Yini , WEN Long . An Edge-locking LOD Method for Eliminating Boundary Cracks in 3D Geological Models[J]. Journal of Geo-information Science, 2023 , 25(5) : 967 -981 . DOI: 10.12082/dqxxkx.2023.220589

1 引言

三维地质模型是根据测井数据、剖面数据、等值线、地质图、遥感影像、野外观测数据等多源多精度多维度的数据，采用建模技术，建立起能表达出地表以下各种地质体的多种地质特征的三维网格模型[1⇓⇓⇓-5]。根据数据来源的不同，可将三维地质建模的算法分为基于钻孔数据的建模方法、基于综合地质剖面的建模方法、基于物探数据的建模方法、基于多源混合数据的建模方法[6⇓-8]。基于钻孔数据的建模一直是国内外研究的热点，钻孔数据可信度较高，通过钻孔数据可获得详细的地层信息，李文雅等[9]针对特殊的地层结构，利用钻孔数据，构建了更精细的三维地质模型。综合地质剖面图能够清楚地描述地质体剖面的地质现象和信息，是建模的重要数据来源，基于综合地质剖面图的建模适用于具有复杂地质构造的建模区域，张明明等[10]将离散光滑插值方法、钻孔数据和综合地质剖面信息三者结合起来，并建立了一套可准确描述复杂地质体空间关系的建模流程，提高了建模精度和工作效率。基于物探数据的建模可利用多种物探手段，获得丰富的物探信息，并进行解译、正演或反演来构建三维地质体模型。龚方方等[11]引入电磁信息来提高地质数据丰富度，从而建立能够真实反映地质情况的三维地质体模型。基于多源混合数据的建模方法能融合多种建模数据，创建出精度高、可靠性强的三维地质模型，徐涛等[12]结合多种探测技术，利用多源数据进行互相验证，提出了一种基于BIM技术的三维地质建模方案。曾敏等[13]以南沙核心区为研究区域，有效集成钻孔、野外调查、地质剖面图等数据，在完善了多源数据建模技术的同时，提高了三维地质模型的精度。对于建模范围较大的三维地质模型来说，建模精度的提高势必会产生庞大的数据量，从而造成三维地质模型可视化的负担，因此，大规模三维地质模型的高质量可视化一直备受关注。
对于地质模型的三维可视化来说，越大范围越精细的模型往往具有越多的网格数量，所以在现有计算机硬件的条件下如何渲染大数据体量的地质模型来保证三维可视化的效果是最关键的问题。影响三维地质模型渲染的因素主要有：三维模型的数据量、计算机CPU计算和GPU渲染能力以及CPU与GPU之间的数据传输带宽限制。然而，尽管硬件性能迅速提高，已有图形计算平台的计算能力和内存容量仍然不能满足海量模型数据增长的需要。在CPU和GPU的计算、渲染能力没有根本性提高的前提下，解决上述问题的主要手段是采用细节层次（Level of Details，LOD）技术[14-15]，该技术将大规模的模型划分成块，再通过简化算法生成具有多种分辨率的一系列简化版本，在可视化时，根据模型的可见性和视点位置调用不同分辨率的数据块进行渲染，以减少计算机每次渲染的压力，但在渲染大规模范围的三维地质模型时，由于划分的顺序和方式以及数据块分辨率的不同，相邻数据块或数据块内部网格的边界往往会不一致，从而出现边界裂缝的问题，所以在使用LOD渲染技术时，对裂缝问题的处理是非常必要的[16]。如顶点拉伸法、加边和减边法、限定四叉树法、和裙边法等，顶点拉伸法[17]是对裂缝处的顶点高程进行调整，可能会导致T型节及地形失真；限定四叉树法[18-19]要求相邻格网剖分层差不超过1，导致数据存在冗余，并且需要反复检测相邻格网的剖分层差，计算量大；加边和减边法[20]是通过简单地增加或减少网格的边数来消除裂缝，裂缝的消除效果不理想；裙边法[21]的思想是在块的边界上建立一个由地表到水平面的垂直外包体，当有块间裂缝存在时，在视觉上裂缝将被“垂直裙”遮挡，但并未从本质上消除，不同于2.5D地形，三维模型边界裂缝可查看视角没有锁定，所以约束仍然是平面的，使用裙边法需要进行大量的裁剪并且会产生额外隐藏几何数据，处理效率较低。李朝奎等[22]为消除传统实时优化适应性网格算法（ROAM算法）所产生的裂缝现象，引入了内接正方形插值算法。韩莹等[23]在四叉树算法LOD的基础上，采用跳点法消除裂缝问题，实现了大面积海水场景的高质量三维可视化。
上述许多裂缝解决方法大多属于“后期处理”且存在诸多局限性，因此，本文设计了一种可消除三维地质模型边界裂缝的锁边LOD方法，该方法在传统渐进网格法LOD[24-25]基础上，结合QEM简化算法和多级图分区算法以实现自动锁边LOD数据的构建，并采用分页机制编码数据，避免了LOD复杂的后处理过程，实现了大规模三维地质模型的无边界裂缝可视化表达。

2 锁边LOD数据构建

2.1 算法总体思路

本文采用多级图分区划分算法[26]和QEM简化算法[27]预先生成LOD渐进网格，然后使用分页机制编码LOD数据，构建LOD的算法流程如图1所示，具体步骤为：
图1 锁边LOD的算法流程

Fig. 1 Algorithm procedure of edge-locking LOD

（1）利用多级图分区方法构建叶子集群，即LOD 0级数据，每个集群包括124~128个三角形[28]；
（2）对于每个LOD层级：
① 再次采用多级图分区算法完成集群的分组，得到多个集群组合；
② 对同一个组合中的面片进行合并，得到一个临时集群组合 L；
③ 算法对其内部的三角面片进行简化，面片数降低为原来的一半，得到简化后的面片组合 L '；
④ 对简化后的面片组合 L '进行拆分，得到新的集群。
（3）对上述过程进行迭代计算，直到最后只剩下一个集群作为根节点。
对于构建锁边LOD的总体代码框架为：
（1）构建三角形索引和材质索引的关联数组。
（2）BuildLODData：构建LOD数据。
① 遍历所有Section（数据结构1），给每个Section构建Cluster（数据结构2）。ClusterTriangles：将Section拆分成一个或多个Cluster；使用GraphPartitioner（数据结构3）划分网格：GraphPartitioner内部使用了Metis第三方开源库，Metis能够高效地提供高品质的网格划分，同时具有低填充率的特点，能够保证网格划分的效果和效率；并行地构建Cluster。
② 检测是否需要用粗糙代表(Coarse representation)代替原始的静态网格数据。使用粗糙代表替换原始的顶点缓冲，去掉旧的拷贝数据，以减少峰值内存持续时间，在并行构建地质模型的巨大网格时，这一点尤为重要。
数据结构1：Section//具有相同纹理属性的三角网格
{
1. MaterialIndex;//纹理索引
2. NumTriangles;//网格数量
3. MinVertexIndex;//记录最大顶点索引
4. MaxVertexIndex;//记录最小顶点索引
}
数据结构2：Cluster //集群
{
//网格数据
1. Verts; //顶点
2. Indexes; //索引
3. MaterialIndexes; //纹理索引
4. BoundaryEdges; //边界边
5. ExternalEdges; //扩展边
6. AdjacentClusters; //相邻的集群
//包围盒数据
7. Bounds; //包围盒
8. MeshBoundsMin; //网格包围盒
//所在的集群组数据
9. GroupIndex; //索引
10. GroupPartIndex; //编码索引
}
数据结构3：GraphPartitioner //多级图分区算法
{
//图数据
1. Offset; //索引位移
2. Num; //数量
3. Adjacency; //邻边列表
4. AdjacencyCost; //邻边权重列表
5. AdjacencyOffset; //邻边位移列表
//范围数据
6. Ranges; //范围
7. RangeIndex; //范围索引
}
数据结构4：ClusterGroup //集群组
{
//包围盒
1. Bounds;
2. LODBounds;
//误差
3. MinLODError;
4. MaxParentLODError;
//层级和网格索引
5. MipLevel;
6. MeshIndex;
//页表索引
7. PageIndexStart;
8. PageIndexNum;
//子节点索引
9. Children;
}
③为所有Section调用BuildDAG构建有向无环图（有向无环图：Directed Acylic Graph，简称DAG）并构建ClusterGroup（数据结构4），加速减面减模。
④如果使用粗糙代表，则调用BuildCoarseRepresentation构建粗糙代表的数据，然后使用粗糙网格范围修正网格Section信息，同时遵守原始序号和保留材质。
关键算法部分的伪代码：
BuildLODData()//构建LOD数据
{
for (NumTriangles: MeshTriangleCounts)
{
if (NumTriangles)
{
Cluster Triangles;//为每个Section构
建1或多个Cluster
{
Initialize Data;//初始化共享边、
边界边、边哈希等
Handle Hash;//并行地处理边哈希
Handle Edge;并行地查找共享边
和边界边
Incoherent Triangle;//处理不连贯
的三角形集
Graph Partitioner;//划分网格
Build Cluster;//并行地构建Cluster
}
}
}
CoarseRepresentation();
for (MeshIndex in NumMeshes)
{
Build DAG;//构建DAG，以减面减模，并且附加Cluster和Group到对应数组中
}
}

2.2 基于三角网格的集群构建

与针对整体模型而构建LOD不同的是，本文充分考虑到最佳可见面片数和固定的屏幕像素数量应差不多相等，而非与模型总面片数呈正相关，因此需要根据空间关系划分三角形集群，将网格分成类似于Voronoi图的不规则区块，而非基于四叉树等方式所划分成的规则区块，从而实现每帧所渲染的三角形数目基本恒定，使模型不会因面片数的改变而发生过于不合理的变化，与此同时，集群将作为LOD模型和组成集群组数据的基元。
本文需按照网格模型拓扑结构划分网格模型的表面，根据输入模型的三角形网格，先将三角形划分成集群，以达到多线程批量处理三角形数据提高渲染效率的目的。集群的构建使用了计算机科学中的多级图分区算法。多级图分区算法主要分为3个步骤：粗化、初始划分、细化。给定一个带权图 G V , E， V为顶点集合， E为边集合， G V , E首先被粗化成包含顶点数较少的小图，然后对粗化后的小图进行k路初始划分，这时由于进行过粗化，点的数量会大大减少，在划分结束后，各个子图将被逐级细化，直到恢复最初点的数量，得到原始的图，算法框架如图2所示。
图2 多级图分区算法框架示意

Fig. 2 Multilevel graph partitioning framework

（1）粗化。给定一个图 G 0   ( V 0 , E 0 )， V 0为顶点集合， E 0为边集合，在粗化过程中，经过多个步骤将 G 0逐步映射为一系列的小图 G 1   ( V 1 , E 1 )，…， G m   ( V m , E m )， 其中| V 1| > | V 2| >…> | V m|，具体步骤 如下：
① 将原图 G i中一组顶点集合 V i v融合成下一级粗化图 G i + 1中的一个顶点 V i；
② 在顶点融合过程中，对于顶点关联的边按如下操作：对于顶点 i 、 j，如果边 e ( i , j )不属于图 G i，且 i与 j之间有经过顶点集合 V i v之中的顶点通路，则将 e ( i , j )添加到图 G i + 1   ( V i + 1 , E i + 1 )中；
③ 新顶点 V i的权值替换为原来顶点集合 V i v中全部顶点权值之和；
④ 新生成边的边权值为满足规则的边的边权值和，规则为：一个顶点是i或者j，另一个顶点属于被融合的顶点集合范围内。
如图3所示，原图（a）中的顶点融合为（b）中的新顶点，并得到粗化后的图，使得原图与粗化图保持边割相同，并且粗化图的平衡划分使得原图的划分同样平衡。
图3 顶点融合示意

Fig. 3 Vertex combination

（2）初始划分。在图粗化到一定程度之后，对被粗化的图进行初次划分。将图 G m   ( V m , E m )进行k路划分，使得图 G m   ( V m , E m )的顶点 V m划分成大致相等的 k个部分，分别为 V 1， V 2，…， V k，其中每个分区的顶点个数 V i = V 0 ∕ k。分区通常用长度为 V m的向量 P m表示，其中对于 V m中的每一个顶点 v i m， P m v i m是一个1到k之间整数，由于在粗化的过程中，粗化图顶点和边的权值可反映原图的权值状况，因此包含了足够的信息可以对图在保证最小边权的情况下进行有效的平衡划分。多级图分区算法中在初始划分阶段可以使用分级嵌套算法进行划分，该算法步骤如下：
① 随机选取粗化图的一个顶点 v，编号为0；
② 按照广度优先方式从编号为0处开始遍历全图，设置与编号为0的相邻顶点均为编号1，与编号1相邻的顶点均为编号2，以此类推，直至所编号的数目为图总顶点数的一半时，算法结束。
图4中给出了分级嵌套算法的一个例子。图中边割线展示了2种可能的划分情况，顶点0为初始顶点，按照广度优先遍历并编号，当编号后的顶点数达到顶点总数一半时停止，编号顶点是一部分，剩余顶点为另一部分。
图4 采用分级嵌套算法进行编号

Fig. 4 Numbering by hierarchical nesting algorithm

（3）细化。在此阶段粗化图 G m的划分分区 P m会回溯图 G m - 1， G m - 2，…，并将 G m投影成原图。由于 G i + 1的每个顶点 v都含有图 G i顶点集合 V i v的一个独立子集，因此可通过将顶点集合 V i v分配给 P i + 1 [ v ]，再从 P i + 1中还原得到 P i，例如， P u =   P i + 1 v   ∀ u ∈ V i v。
虽然 P i + 1是 G i + 1的局部最小划分，但是细化后的划分 P i可能不再是 G i的局部最小划分。由于 G i更加精细，所以会有更大的自由度优化 P i以减少边割。因此，仍然可以使用局部细化启发式算法来优化划分 G i + 1的划分。每进行一次细化，算法会对细化后的划分使用优化算法。划分优化算法的最基本思想是在划分后的两个部分中选择两个顶点集合进行互换，如果得到的新划分有更小的边割，则采用新的划分。特别地，如果 A和 B是二分的两部分，优化算法会选择 A ' ∈   A和 B ' ∈ B使得 A \ A ’ ⋃ B '和 B \ B ’ ⋃ A '成为边割更小的划分。
为了避免图中出现孤岛，在分区处理时还需要为那些空间上相近但是没有连接关系的面片添加一些额外的边，可调用Metis库解决此问题。通过上述算法拆分构建了最原始的集群数据后，每个集群的轮廓边界数目为尽可能最少，从而来保持渲染的效率，其次，集群内部的三角形数量都保持在124~128个，以确保光栅化的效率。面对具有上百万个面的三维地质模型，本文设置集群数据遵守最少边界和均匀面积2个条件进行多级图分区算法反复切割分组，生成最初的LOD0的集群数据，如图5所示。对于LODn集群数据的生成，通过多级图分区算法，对LODn-1级数据进行减面操作，生成新的集群数据，并额外存储记录对应的误差值。
图5 集群示意图

Fig. 5 Cluster group

2.3 基于集群的分组

对于大范围的地质模型来说，仅将网格划分为一系列集群数据块之后就进行锁边简化，往往会因为集群层级数量过大，而导致边界上的受限顶点会传播到层次结构的上层，产生链式反应，从而导致三角形数量的激增和质量的下降，如图6（a）所示，区块边界的简化程度严重不足，本应平滑的区域却出现较密集的网格。由于集群是由多个三角网格组成的，因此，在集群数据构建好后，本文将多网格组合的集群看作一个“大网格”，将集群也进行分区， 以减少集群的层级数量从而避免上述弊端，如图6（b）所示。
图6 锁边简化显示效果

Fig. 6 Display of lock edge simplifies

对满足最多共享边和更少边界边两个条件的集群进行分组，再次使用多级图分区算法，最小化边切割代价图的划分优化，这里将集群看作图节点，连接集群的三角形看作图边，共享三角形的边数量看作图边权重，集群组看作分区，用于在空间上闭合集群的附加图边，对于集群组的孤岛问题，可添加空间信息和最小图边切割最小锁定边，并使用Metis库解决。
经过集群分组后，每个集群组的集群数量保持在8~32个。此时，根据预处理集群构建的集群组即为LOD0级数据，如图7所示。集群组的结构中只包含包围盒、LOD误差、层级和网格索引、子节点集群索引等数据。其中LOD误差是一个范围，包括当前节点最小误差值和父节点最大误差值。
图7 集群组示意

Fig. 7 Cluster group

对于更高级LOD集群组的生成，根据低级LOD的集群组经过集群合并简化，得到新的集群，这些集群数据将加入由其他低级LOD新生成的集群数据，组成新的集群组合。重复以上述过程，直到最终只有一个集群时结束操作。

2.4 集群组锁边简化

解决好划分数据块的问题之后，还要考虑如何简化一系列集群组，以生成不同分辨率的版本。考虑到目前计算机的局限性，在渲染三维模型（包括三维地质模型）时，往往需要平衡效率和质量，具体表现为，当相机靠近模型时，模型质量对可视化影响较大，需提高模型精度，增加计算性能成本，反之，远离模型时，首要考虑模型效率，可降低精度要求，减少计算成本。鉴于此，需要根据精度需求来调用不同层级的LOD集群组数据块。
本文在构建好LOD0数据之后，为在此基础上构建更高级别的LOD数据，需要以集群组为操作基元对LOD0的数据实施网格简化，防止过度简化。
这里基于QEM算法对LOD数据进行简化。QEM算法将会在流形的三角形网格的表面上折叠一条边，以实现减面的目的。本小节将边折叠问题转换为减少顶点数问题，如图8所示，将一条边2个相邻顶点收缩到了一个顶点。
图8 收缩边转换为减少顶点

Fig. 8 Shrinking edges converts to reducing vertices

现在求解的关键是寻找一对最优收缩的顶点对（ v 1， v 2），将其收缩转化为一个顶点 v -。在这个过程中，主要求解2个问题：① 计算顶点对的误差度量，来确定最优收缩点对；② 计算收缩后的顶点 v -的坐标。首先，考虑到地质模型对空间拓扑关系的准确性，收缩后的顶点 v -要与原模型距离最近，因此，本文将二次误差测量作为误差度量。
对于顶点对（ v 1， v 2）收缩成一个顶点 v -。首先定义 v i所对应的原始三角形面片的集合为 T r i ( v i )，用隐式函数表达平面为 a x + b y + c z + d = 0，其中系数满足 a 2 + b 2 + c 2 = 1，将顶点 v记为 v = x , y , z , 1 T，将平面的法向量记为 p = a , b , c , d T，为每个顶点分配一个二次误差测度矩阵 Q，如式（1）所示。
Q =   ∑ i = 1 m p i p i T
式中： i表示第 i个平面， m表示顶点有 m个邻面， p i表示第 i个邻面的法向量，并且做单位化处理。由三维空间中顶点到平面的公式可知：顶点 v -到平面的平方距离 d ( v - ) 2如式（2）所示。
d ( v - ) 2 = v - T p p T v - T =   v - T ( p p T ) v -
式中：记 K p = ( p p T )，令 Q v i =   ∑ p ∈ T r i ( v i ) K p 为顶点 v -的二次误差测度矩阵，当把边（ v i， ν j）收缩到顶点 v -时，则最优收缩点的二次误差测度 ∆ v -为式（3）。
∆ v - = ∑ p ∈ T r i ( v i ) ⋃ T r i ( v j ) v - T K p v - =   v - T Q ( v - ) v -
在实施边收缩时，要依次选取更新后误差最小的边进行迭代直到满足需求为止。需要注意的是还要分情况处理系数矩阵的是否可逆，若可逆，则采用上述方法进行求解，若不可逆，则比较 v 1、 v 2以及 v 1 + v 2 ∕ 2的边收缩代价，选择最小的代价，并且保留 ∆ v -最大的点即可，对于无法保留一些重要模型特征问题，通过引入提前标记来预处理数据，假如某个顶点是地质模型特征点，则赋予该点一个较大的 ∆ v -值，同理，对于模型边界也采用同样的方法，避免因边折叠导致的变形。
由于每层次的集群和集群组是依赖空间相邻关系所划分的，因此，在简化过程中，每个集群组在约束范围内都能搜寻最合适的顶点对进行多线程简化，每个集群组各自执行内部的QEM简化算法，互不干扰。为避免出现如图9（a）所示的边界裂缝问题，在简化时还需保证集群组的边界不变，使得网格简化发生在集群组内部，从而实现如（b）中的平滑过渡。
图9 边界裂缝解决前后示意

Fig. 9 Boundary cracks before and after solving

具体简化过程为如图10所示，先选择LODn级中划分好的集群组 L，标记保留集群组 L边界，在集群组 L内部，通过误差度量计算得到三角网格中每个顶点的二次误差 ∆ v -，定义每条边两端点的二次误差之和为该边的边折叠代价，这是确定边折叠次序的关键；在集群组 L边界处，根据标记设置集群组合边界的边折叠代价 ∆ v -为最大。这样边折叠代价最大的边就会被存放到堆底，一定简化率内都不会被折叠，实现边界的自动锁定，而在集群组合内部的三角网格将通过QEM算法进行减半简化并拆分得到新一级LOD对应的三角网，即简化后的集群组   L '，将 L '进行重新拆分，得到（d）中属于LODn+1的4个新集群。由于需要保证每级LOD的集群块数据大小相近，从而可执行并行计算，因此每个集群块数据在每个LOD层级都被简化为上一级三角面片数量的一半。
图10 LOD数据生成示意

Fig. 10 Generation of LOD

基于集群和集群组分块的锁边方式消除裂缝的原理如图11所示，在不同级别LOD切换时，由于已对集群进行分组，相邻级别LOD会交替使用已锁定的集群组边界，LOD0级集群组的边界成为LOD 1级集群组的内部，同理，LOD1级集群组的边界也会成为LOD2级集群组的内部，在LOD0级切换至LOD2级的过程中，首先会锁定LOD0级的集群组边界，将LOD0切换至LOD1，然后再锁定LOD1级的集群组边界并解锁LOD0的集群组边界 ，将LOD1切换为LOD2。该过程中，某级边界上的锁边不会一直保持锁定状态，因为不同级别的集群组边界是不同的。因此，在多级LOD切换时，会先锁定一个级别，再解锁下一个级别，不会积累密集的锁定边。
图11 切换锁边LOD解决边界裂缝示意

Fig. 11 Switching edge-locking LOD to resolve boundary cracks

2.5 LOD的集群数据关系

在LOD数据构建完后，LOD的集群和集群组数据存在一定依赖关系。在从低级别LOD生成高级别LOD过程中，会将低级LOD的集群组锁边，在集群组内部将低级LOD的集群重新划分为更简化的集群，这些更简化的集群将与其他经过简化算法的集群重新组合成更大更粗糙的集群组，这些集群组是属于更高级别LOD的。这种集群组锁边的LOD生成方式，将每个集群建立了一个DAG的逻辑结构，而非是树结构，这样可避免某级别LOD的集群组一直锁住边界，从而导致渲染出来的模型细节出现混乱的空间关系。现以LOD0和LOD1为例，LOD0和LOD1的集群数据对应的依赖关系如图12所示，其中LOD0的集群数据为叶子节点。
图12 集群关系示意图

Fig. 12 Relationship of Clusters

在DAG中，每个节点都被分配了一个几何误差。由于在执行简化算法过程中，仅仅演示了一条边的收缩，而三维地质模型具有大量的三角形数据，所以必须满足一定的条件以方便对GPU做并行的选择。理想情况下，几何误差应使用Hausdorff距离[29]来计算，本文使用了一个更节省运算时间的方法，采用集群三角形面积之和来近似代替，采用此种方法，主要是考虑到原始网格是很密集的，通过高精度的算法进行简化，所产生的均匀网格意味着面积是跟DAG 结构是相关的，Hausdorff算法所产生的几何误差往往需要修正，以遵守DAG节点之间的顺序。
相对于原始网格而言，简化后网格中的几何图形会发生位移，使得对于每个节点，与父节点相关的误差总是高于任何子节点的误差。这一属性可以在一个简单的自下而上的方法中执行，其中叶子节点的几何误差被设置为0，并递归增加每个节点的几何误差，直到它大于其所有子节点的几何误差。同样，父节点包围盒必须被扩大，以包围DAG中所有子节点的包围盒，以确保单调的视图相关的误差函数。
在2.4小节，以集群组为单位对LOD0级数据进行减面，减面至原始集群组一半，并将集群组看作整体，重新划分集群组的集群组成，直至生成一个集群，在划分集群成集群组的过程中，我们会保存集群误差和集群组误差。
对于单个集群来说，LOD误差只是一个数值。对于集群组来说，LOD误差则是一个范围：最小LOD误差和父节点最大LOD误差。假设集群组A中8个集群的误差如图13（a）所示，经过合并简化之后，重新生成集群组B，误差如（b）所示。对于集群组A的误差范围，最大范围取集群组A子集群的最小误差，为0.1；最大范围取高级别LOD集群B的子集群最大误差，为0.7。对于集群组B，强制要求所有生成的新集群具有与该最大误差相同的LOD误差，所以B中所有集群的LOD误差均为0.7。如果任何其他集群如集群组B包含多个新生成的集群，父节点最大LOD误差将大于集群组A的父节点最大LOD误差。这样就可以保证LOD0级数据的误差小于其集群组所在的上一级的所有集群所在级别的误差，即所生成的集群组，自上而下合并的关系时是依照降序排列的，以便在GPU上可以快速并行地选择调用LOD数据。
图13 不同层级集群的LOD误差

Fig. 13 LOD Errors of Clusters at different levels

3 基于集群数据的LOD编码

在模型渲染过程中，当GPU发现当前的网格精度跟目标有一定的差距时，就会告诉CPU异步加载更高精度的数据进来。但是此处需要对加载跟卸载的内容进行详细评估，以保证可见的数据是DAG的有效子集，从而避免不同LOD之间出现裂缝情况。前文中讲到为了保证前后两级LOD之间无缝衔接，合并简化是以集群组为单位进行的。当相机拉近或远离模型时，当前集群组会被其下一级或者上一级集群组替换。因此，在向GPU内存发送渲染数据时是以集群组为单位进行加载，否则显示结果就会出问题。
因此本文中对集群和集群组进行编码处理，其中集群记录三角形顶点、索引等数据，集群组只记录了所包含的集群索引信息。考虑到每个集群的顶点数据、属性尺寸等均不同，为了避免内存碎片化问题，我们将集群数据编码到Page(Page：物理页，内存分页管理机制的单位)中，并设定每个Page的内存空间不超过128 K。集群数据在Page中的存放会充分考虑数据在空间上的相邻关系，同时也会考虑集群组在DAG上的层级关系，其目标是为了保证在运行时同时加载最小数目的Page。
为了保证任何时刻都有可渲染的数据，将第一个Page用来保存DAG的根节点以及从根节点往下尽可能多的上层节点，并把该Page设置成常驻，存储在GPU中。如图14所示，如果以集群组作为基本单元填充Page的话，会导致Page中存在较多的空间浪费，因此需要将集群组拆分成多个部分并分别填入不同的Page中以填充Page中未被使用的部分，而当需要加载该集群组时，就将该集群组所对应的Page全部加载进来，这样做的好处是减少了Page的空间浪费，缺点则是需要同时加载的Page数目增多了。为了提高效率，将拆分后的集群存放到一系列连续的Page上，在需要时就都请求这一串连续的Page。为了实现这一点，还需要设置一个ClusterGroupPart数据结构进行记录（数据结构5）。
图14 Page编码划分示意

Fig. 14 Page coding division

如图15，当一个新的Page被分配或者开始记录一个新的集群组时，一个新的ClusterGroupPart将被创建。并且集群将被记录到ClusterGroupPart中。
数据结构 5：ClusterGroupPart
{
//ClusterGroup分拆后的全部或一部分
1. Clusters;
2. Bounds; //包围盒
3. PageIndex; //页表索引
4. GroupIndex; //所在的Group索引
5. HierarchyNodeIndex; //层次结构节点索引
6. HierarchyChildIndex; //层次结构子节点索引
7. PageClusterOffset; //页表Cluster列表偏移
}
图15 集群编码示意

Fig. 15 Clusters encoding

4 实验及结果分析

4.1 实验环境

本文基于Unreal Engine 5.0引擎在8核2.30GHz的I7-11800H、16GBRAM CPU和24GB的NVIDIA GeForce RTX 3060 Laptop GPU上进行三维地质模型的LOD生成与编码，算法运行在Windows 10上，并通过内存映射文件使用操作系统的虚拟内存，编程语言使用C++，通过将生成的LOD集群数据根据需要以Page数据块载入到GPU上来实现快速渲染出无边界裂缝的三维地质模型效果。

4.2 实验分析

实验所使用的三维地质模型数据来自团队自主研发的多源数据三维地质建模系统Smart3dMap，无论是基于钻孔还是剖面图、地形的多源地质模型，常用的建模结果都是用三角网格表示，因此本文暂时仅考虑使用基于钻孔构建的三维地质模型来进行验证分析。为了说明本文方法在不同规模与复杂程度的三维地质模型上的适用性，本文分别选取了模型A和B进行实验，其中模型A由189个钻孔数据构建得到21个标准地层，包含102万个三角网格和289万个顶点，数据大小为 50 MB，占地面积为3337 km2，建模地层深度为 500 m；模型B由6489个钻孔数据构建得到43个标准地层，包含264万个三角网格和785万个顶点，数据大小为139 MB，占地面积为123 km2，建模地层深度为500 m。根据前文所述方法，首先将Obj格式模型数据载入到内存中，然后进行LOD 0级的集群块划分，在此基础上迭代直至构建完地质模型的LOD数据，详细信息如表1所示。
表1 预处理后的集群和集群组数据

Tab. 1 Preprocessed clusters and cluster groups （个）

A模型 B模型 A模型 B模型
集群数 集群组数 集群数 集群组数 集群数 集群组数 集群数 集群组数
LOD 0 8184 411 20799 1046 LOD 9 20 1 52 3
LOD 1 4173 209 10599 526 LOD 10 10 1 27 5
LOD 2 2129 106 5434 271 LOD 11 5 1 14 1
LOD 3 1090 55 2785 138 LOD 12 3 1 6 1
LOD 4 558 28 1424 71 LOD 13 2 1 3 1
LOD 5 284 14 733 37 LOD 14 1 1 2 1
LOD 6 144 7 377 19 LOD 15 - - 1 1
LOD 7 74 4 193 10 合计 16 715 842 42 548 2136
LOD 8 38 2 99 5
从表1可知，当分解的集群数量只有一个时LOD生成过程结束，且每一级LOD集群数量较上一级都减少了1/2左右。不同于传统的LOD组织，在切换时并不会完整的调度某一级LOD数据，而是渐进更新，效果具体见图16和图17。
图16 模型LOD切换状态

Fig. 16 Switching of model LOD

图17 模型地层结构图可视化

Fig. 17 Model tratigraphic structure diagram

表2给出了A模型各级LOD渲染时的三角网格数量、简化率和渲染时长，其中三角形网格数量在每次迭代中的简化率为约为50%，所以当前级别LOD的三角网格数量为上一级LOD三角网格数量的一半左右，而渲染时长也基本控制在2 s以内，并且随着网格数量的减少，渲染时长也会相应地缩短。
表2 渲染LOD时的数据统计

Tab. 2 Statistics for rendering LOD

LOD级别 三角网格数量/个 简化率/% 渲染时长/ms
LOD0 10 29 388 无 1896
LOD1 523 841 0.49 1016
LOD2 267 215 0.49 517
LOD3 136 773 0.49 299
LOD4 70 074 0.49 146
LOD5 35 680 0.49 132
LOD6 18103 0.49 156
LOD7 9257 0.49 160
LOD8 4784 0.48 97
LOD9 2514 0.47 118
LOD10 1260 0.50 34
LOD11 630 0.50 14
LOD12 378 0.40 5
LOD13 252 0.33 2
LOD14 126 0.50 1
另外，为了和常规方法构建的LOD进行比较，本文使用Smart3dMap建模软件分别对A和B构建了4层基于四叉树的LOD数据，构建时相邻级别抽稀比为50%，不同方法渲染模型的帧率数据如表3所示，在没有构建LOD的时候，渲染时会将整个模型载入到渲染管线中，因此导致渲染帧率很低，采用基于四叉树方法构建LOD后，现实情况有明显改善，而本文方法构建的数据显示会更流畅。
表3 模型显示帧率 (帧)

Tab. 3 Frame rate of model display

无LOD 四叉树LOD 本文方法
A模型 28 48 57
B模型 12 41 55
在可视化时通过多次检查、旋转、放大和缩小三维地质模型来评估渲染效果。图16为模型LOD集群可视化的展示效果，图16（a）为A模型某层级LOD的整体集群可视化效果，图16（b）（c）是图16（a）中黑框位置的放大，图16（b）为相机切换到特定位置时，精度为LOD1级可视化效果（红实线内均为LOD1的集群数据），图16（c）为相机拉近一定距离时，模型的红实线内精度切换到LOD 0级可视化情况，在由图16（b）更新到图16（c）时，只是将红实线内的集群由LOD1级切换至LOD0级，红实线外部集群还均保持在LOD1级。图17（a）和图17（b）分别为模型A和B利用本文算法的最终可视化效果。
利用本文方法与未使用多级图分区和自动锁边的渐进网格法LOD渲染模型A和B来进行对比验证，实验结果如图18所示，在放大模型某一位置时，采用锁边LOD方法渲染出的模型未出现传统渐进网格法LOD所难以避免的边界裂缝问题。
图18 采用不同渲染方法的可视化

Fig. 18 Visualisation with different rendering methods

5 结语

（1）本文针对三维地质模型的数据体量大以及计算机硬件的不足而导致多分辨模型可视化时出现的边界裂缝问题，设计了一种适用于三维地质模型的锁边LOD方法，通过多级图分区算法将网格划分转化为图分区问题，三角网格被划分成一系列面数基本固定的集群，将LOD切换粒度降低到三角形集群层级，实现批处理，设计集群组的索引数据来组织集群，在集群组的基础上迭代计算不同层级LOD数据；使用基于边折叠的QEM算法约以50%的简化率对低一级的集群组数据进行简化，该过程中保持集群组边界锁定，实现了LOD构建；同时，将LOD数据写入Page块中，从而解决了三维地质模型的边界裂缝问题，为实际工程提供更准确和高质量的模型视觉效果。
（2）本算法在生成LOD的过程中，实现了自动进行锁边的效果，可有效显示无边界裂缝的三维地质模型，能满足多尺度大规模三维地质模型的高质量可视化要求，适用于城市地下空间工程、数字矿山等领域，实验表明该方法可解决切换LOD时高低精度数据块之间的裂缝问题，具有较好的渲染效果，为后续的三维可视化分析提供显示支持。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
张源. 城市三维地质建模方法研究[J]. 矿山测量, 2021, 49(1):65-68,88.

[ Zhang Y. Research on urban 3D geological modeling method[J]. Mine Surveying, 2021, 49(1):65-68,88. ]

[2]
戴粤, 戴吾蛟. 基于Surfer平台的FLAC3D三维地质建模方法与模型验证[J]. 工程勘察, 2022, 50(3):43-46.

[ Dai Y, Dai W J. Three-dimensional geological modeling based on Surfer FLAC3D and its verification[J]. Geotechnical Investigation & Surveying, 2022, 50(3):43-46. ]

[3]
刘鑫, 李季秀, 胡立堂. 基于多源数据融合的复杂地质矿区三维地质建模[J]. 工程勘察, 2021, 49(12):35-39.

[ Liu X, Li J X, Hu L T. 3D geological modeling of complex geological mining area based on multi-source data fusion[J]. Geotechnical Investigation & Surveying, 2021, 49(< W>1 2):35-39. ]

[4]
王金鑫, 赵光成, 禄丰年, 等. 真三维地质模型构建的球体测地线八叉树网格方法[J]. 地球信息科学学报, 2019, 21(8):1161-1169.

DOI

[ Wang J X, Zhao G C, Lu F N, et al. Sphere geodesic octree grid method for true three-dimensional geological model construction[J]. Journal of Geo-Information Science, 2019, 21(8):1161-1169. ] DOI:10.12082/dqxxkx.2019.180682

DOI

[5]
黄岸烁, 张宝一. 一种基于距离场的三维地质空间属性插值方法[J]. 地质与勘探, 2019, 55(6):1510-1517.

[ Huang A S, Zhang B Y. A method of three-dimensional geo-spatial attribute interpolation based on the distance field[J]. Geology and Exploration, 2019, 55(6):1510-1517. ] DOI:10.12134/j.dzykt.2019.06.017

DOI

[6]
郑通科, 陈庆, 袁峰, 等. 三维矿体模型快速构建方法研究[J]. 合肥工业大学学报(自然科学版), 2015, 38(1):98-102.

[ Zheng T K, Chen Q, Yuan F, et al. Research on fast building of three-dimensional orebody models[J]. Journal of Hefei University of Technology (Natural Science), 2015, 38(1):98-102. ]

[7]
张海翔, 李占东, 李阳, 等. “双控”地质建模技术的实践与认识——以渤海湾盆地SZ36-1油田为例[J]. 石油地球物理勘探, 2021, 56(3):603-611,415.

[ Zhang H X, Li Z D, Li Y, et al. Practice and understanding of double controlled geological modeling technology: A case study on SZ36-1 Oilfield in the Bohai Bay Basin[J]. Oil Geophysical Prospecting, 2021, 56(3):603-611,415. ] DOI:10.13810/j.cnki.issn.1000-7210.2021.03.019

DOI

[8]
Zhang Q, Zhu H H. Collaborative 3D geological modeling analysis based on multi-source data standard[J]. Engineering Geology, 2018, 246:233-244. DOI:10.1016/j.enggeo.2018.10.001

DOI

[9]
李文雅, 李丽娟. 三维地质精细化建模在古贤水利枢纽中的应用[J]. 人民长江, 2021, 52(S1):117-119,129.

[ Li W Y. Application of 3D geological fine modeling in Guxian Water Conservancy Project[J]. Yangtze River, 2021, 52(S1):117-119,129. ] DOI:10.16232/j.cnki.1001-4179.2021.S1.026

DOI

[10]
张明明, 李晓晖, 袁峰, 等. 地层三维建模及面模型插值方法对比研究[J]. 安徽地质, 2015, 25(3):182-186.

[ Zhang M M, Li X H, Yuan F, et al. Comparative study between three-dimensional strata modeling and surface model interpolation[J]. Geology of Anhui, 2015, 25(3):182-186. ]

[11]
龚方方, 胡继华. 基于物探数据的三维地质建模研究——以新疆吐鲁番盆地为例[J]. 产业与科技论坛, 2019, 18(10):92-94.

[ Gong F F, Hu J H. Research on 3D geological modeling based on geophysical data: A case study of Turpan Basin in Xinjiang[J]. Industrial ＆ Science Tribune, 2019, 18(10):92-94. ] DOI:10.3969/j.issn.1673-5641.2019.10.045

DOI

[12]
Xu T, Mo F, Lin X T, et al. 3D geological modeling method and its application in complex Karst area based on BIM technology[J]. Construction Technology, 2022, 51(1 1):42-44,77.

[13]
曾敏, 赵信文, 陈松, 等. 基于多源数据融合的广州南沙核心区三维工程地质建模[J]. 华南地质, 2022, 38(2):281-291.

[ Zeng M, Zhao X W, Chen S, et al. 3D engineering geological modeling of the Nansha core area of Guangzhou based on multi-source data coupling[J]. South China Geology, 2022, 38(2):281-291. ]

[14]
陈鹏宇. 大规模城市建筑物的一种混合LOD实时绘制算法[J]. 现代计算机, 2020(1):3-7.

[ Chen P Y. A hybrid LOD real-time rendering algorithm for large-scale urban buildings[J]. Modern Computer, 2020(1):3-7. ] DOI:10.3969/j.issn.1007-1423.2020.01.001

DOI

[15]
李媛媛, 罗训. 基于虚拟现实的渲染优化算法[J]. 计算机系统应用, 2019, 28(6):178-182.

[ Li Y Y, Luo X. Rendering optimization algorithm based on virtual reality[J]. Computer Systems & Applications, 2019, 28(6):178-182. ] DOI:10.15888/j.cnki.csa.006962

DOI

[16]
王振武, 吕小华, 韩晓辉. 基于四叉树分割的地形LOD技术综述[J]. 计算机科学, 2018, 45(4):34-45.

DOI

[ Wang Z W, Lv X H, Han X H. Survey of terrain LOD technology based on quadtree segmentation[J]. Computer Science, 2018, 45(4):34-45. ] DOI:10.11896/j.issn.1002-137X.2018.04.005

DOI

[17]
宋力兵, 龚华军, 王新华. 基于改进的约束四叉树LOD全球地形实时绘制[J]. 计算机与数字工程, 2013, 41(10):1668-1671,1697.

[ Song L B, Gong H J, Wang X H. Global terrain real-time rendering based on improved constraint quad-tree and level of detail algorithm[J]. Computer ＆ Digital Engineering, 2013, 41(10):1668-1671,16 97. ]

[18]
刘振东, 李成名, 武鹏达, 等. 去LoD层级约束的海量三维地形裂缝实时消除算法[J]. 测绘通报, 2018(7):48-52.

[ Liu Z D, Li C M, Wu P D, et al. A level constraints removed algorithm for avoiding crack in massive 3D terrain[J]. Bulletin of Surveying and Mapping, 2018(7):48-52. ] DOI:10.13474/j.cnki.11-2246.2018.0208

DOI

[19]
袁凌, 李丹, 陶飞. 三维场景实时建模中地形生成算法优化[J]. 武汉大学学报·信息科学版, 2017, 42(10):1387-1393.

[ Yuan L, Li D, Tao F. Optimization of terrain generation algorithm in three-dimensional real-time modeling[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10):1387-1393. ] DOI:10.13203/j.whugis20160100

DOI

[20]
汤延辰, 郭星, 张功营, 等. 一种多控制因子LOD大规模地形绘制算法[J]. 微电子学与计算机, 2019, 36(4):99-104.

Guo X, Zhang G Y, et al. A LOD large-scale terrain rendering algorithm with multiple control factors[J]. Microelectronics ＆ Computer, 2019, 36(4):99-104. ] DOI:10.19304/j.cnki.issn1000-7180.2019.04.020

DOI

[21]
欧阳志恒, 崔光茫, 赵巨峰, 等. 基于分层级各向异性滤波的图像景深渲染算法[J]. 光学技术, 2018, 44(4):469-475.

[ Ouyang Z H, Cui G M, Zhao J F, et al. A layered image depth of field rendering algorithm using anisotropic filtering[J]. Optical Technique, 2018, 44(4):469-475. ] DOI:10.13741/j.cnki.11-1879/o4.2018.04.015

DOI

[22]
李朝奎, 王宁, 吴柏燕, 等. 一种新的ROAM算法及其在地形建模中的应用[J]. 地球信息科学学报, 2018, 20(9):1209-1215.

DOI

[ Li C K, Wang N, Wu B Y, et al. A new ROAM algorithm and its application in terrain modeling[J]. Journal of Geo-Information Science, 2018, 20(9):1209-1215. ]

[23]
韩莹, 杨丽芳, 郭娜. 基于LOD技术的多分辨率海水场景实时仿真[J]. 计算机仿真, 2020, 37(7):409-413.

[ Han Y, Yang L F, Guo N. Real-time simulation of multi-resolution seawater scene based on LOD technology[J]. Computer Simulation, 2020, 37(7):409-413. ]

[24]
Cignoni P, Ganovelli F, Gobbetti E, et al. Batched multi triangulation[C]// 2005 IEEE Visualization Conference (VIS 05). 2005:207-214. DOI:10.1109/vis.2005.12

DOI

[25]
Yoon S E, Salomon B, Gayle R, et al. Quick-VDR: Interactive view-dependent rendering of massive models[C]// IEEE Visualization 2004. IEEE, 2004: 131-138. DOI:10.1109/VISUAL.2004.86

DOI

[26]
Heuer T, Sanders P, Schlag S. Network flow-based refinement for multilevel hypergraph partitioning[J]. ACM Journal of Experimental Algorithmics, 2019, 24:1-36. DOI:10.1145/3329872

DOI

[27]
Zhou G Y, Yuan S D, Luo S M. Mesh simplification algorithm based on the quadratic error metric and triangle collapse[J]. IEEE Access, 8:196341-196350. DOI:10.1109/ACCESS.2020.3034075

DOI

[28]
Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs[J]. SIAM Journal on Scientific Computing, 1998, 20(1):359-392. DOI:10.1137/s1064827595287997

DOI

[29]
廖定安, 肖海慧, 王成杰. 基于Hausdorff测度的图像分割算法研究[J]. 自动化技术与应用, 2019, 38(8):89-92.

[ Liao D A, Xiao H H, Wang C J. Study on image segmentation algorithm based on Hausdorff measure[J]. Techniques of Automation and Applications, 2019, 38(8):89-92. ] DOI:10.3969/j.issn.1003-7241.2019.08.021

DOI

Options
Outlines

/

〈 〉