CN106384386A - Lod模型生成中网格处理方法、系统以及3d重建方法和系统 - Google Patents

Abstract

本发明公开了一种LOD模型生成中网格处理方法、系统以及3D重建方法和系统。其中，在LOD模型生成过程中处理网格的方法包括：获得初始网格；剪切所述初始网格以得到多个LOD分区；通过网格合并将当前层级的LOD分区缝合以得到合并的网格；对合并的网格应用网格简化以得到下一层级的LOD分区；对下一层级的LOD分区迭代执行所述网格合并直至得到最终的合并的网格。对于由快速增长的3D重建技术来带的日益增长的需求而言是鲁棒的且可扩展的。其优化了三个主要的网格操作，在大型数据集上的实验表明其具有鲁棒性和可扩展性。

Description

LOD模型生成中网格处理方法、系统以及3D重建方法和系统

技术领域

本发明实施方式涉及LOD(Level-of-detail，细节层次)模型生成中网格处理方法、系统以及3D(三维)重建方法和系统。

背景技术

过去十年，通过改进的计算硬件和无人机摄影的普及化使得大型3D重建成为可能。这些重建的3D模型具有从建筑建模、城市规划、测量、遗迹保护的典型使用到例如机器人技术中的障碍回避和3D打印等的较新领域的应用的广泛应用。商业上的无人机摄影尤其在近几年快速发展。毫无疑问，未来将会需要甚至更大型的且更高质量的3D重建模型。

处理这种大型数据的可能的方式是分治法(divide-and-conquer)。相同的技术已应用于多视角立体重建(multi view stereo，MVS)步骤，其是产生捕获的对象或场景的高密度点云的必需步骤并且是大型LOD模型生成的前期步骤。此后，从点云的每个簇中提取网格面。这意味着所产生的网格面通常是片段的且不连续的。而且，通常这些初始网格面的尺寸太大以至于无法通过互联网传输，而限制了其使用性。理想的解决办法是根据这些初始网格面生成多分辨率模型或细节层次(LOD)网格，以满足模型的不同层次的精确度需求。例如，传输应用要求最详细的模型，而简化的模型最适合于在线传输和快速预览场景。仅通过产生LOD形式的网格可使得大型3D重建模型不断发展并且更加实用。

然而，已开发的大多数网格操作技术着眼于处理单个对象，几乎不应用于处理这种大型数据。在用于这种大型数据时，这些技术中的一些开始暴露出了一些问题，而这些问题过去几乎没有引起关注。而且，将片段的且高密度的初始网格转换成连续的LOD形式网格需要混合数个种网格操作，这又增加了一层难度。

发明内容

在计算机图形学中，细节层次(LOD)是对模型保真度和渲染速度之间取舍(tradeoff)的研究。基本思想是使用简化的模型表示不重要或进一步远离视点的对象以降低渲染负荷。多年以来许多研究者已提出不同的方法生成LOD模型并将其投入应用。著作“3D图形的细节层次(Level of Detail For 3D Graphics)”是LOD方面的非常好的概观并且其中介绍的经典技术至今仍然相关。在所有LOD架构之外，本发明是在离散LOD上做出的。离散LOD是指不同细节层次的相同模型是离散的并且每个层次首先离线产生并且基于观察者和模型之间的距离在运行时选择合适的渲染水平。优势在于模型的每个层次是静止的并且由此可对图形硬件产生影响以增加其渲染速度。相对于其他架构，例如连续LOD或视相关LOD，离散LOD更加容易编程，因为其将网格简化与渲染解耦。这种解耦还使得离线网格简化并行化并且由此更加可扩展。图5示出了单个对象离散LOD的典型例子。

与之前所述的简单的、单个对象LOD示例不同，本发明面临的课题是规模大得多并且不断增长，在LOD流程中还必须使用分治技术。由此，本发明提供了一种LOD模型生成中网格处理方法、系统以及3D重建方法和系统。

一方面，依照本发明实施方式的一种在LOD模型生成过程中处理网格的方法可以包括：获得初始网格；剪切所述初始网格以得到多个LOD分区；通过网格合并将当前层级的LOD分区缝合以得到合并的网格；对所述合并的网格应用网格简化以得到下一层级的LOD分区；对所述下一层级的LOD分区迭代执行所述网格合并直至得到最终的合并的网格。

在本发明的另一实施方式中，所述方法还包括对合并的网格存在的孔进行孔填充以使相邻网格表面相适应。

可选地，所述孔填充可包括第一填充处理：构建带有已知的孔的拓扑结构的网格补丁；将目标网格上的孔的边界顶点映射至该网格补丁的边界顶点；使用该边界顶点的位置作为约束条件对内部顶点进行平滑。此外，所述孔填充还可包括第二填充处理：对网格补丁进行初始三角化；通过增加内部顶点对三角化进行细化；将增加的内部顶点放置在使补丁表面与相邻表面相适应的位置。

其中，对网格补丁进行初始三角化可以包括：定义三角形的两个误差函数：W_面积和W_{二面角-角度}，其中，W_面积是指三角形的面积，W_{二面角-角度}是指与相邻三角形的最大二面角角度；定义网格补丁误差函数W为W_面积的总计的最小误差或W_{二面角-角度}的最大值的最小误差；通过使W最小化来完成初始三角化。

此外，或作为选择，所述第二填充处理还包括：平滑新填充的孔的表面，最小化边界顶点和增加的内部顶点之间的正常差异。

在本发明的可选实施方式中，所述第一填充处理用于大于或等于预定阈值的孔，所述第二填充处理用于小于所述预定阈值的孔。

可选地，所述剪切可以包括：定义切断平面；在所述初始网格中查找所有与该切断平面交叉的三角形；将所述交叉的三角形沿着剪切线分离成小三角形；通过使用所述小三角形的几何中心作为测试点将所有的小三角形标记在所述切断平面的任一侧，并且除去该侧中不需要的三角形。

可选地，所述网格合并可以包括：沿着待合并网格的合并侧切掉预定偏移量以建立待合并网格之间的合并空隙；沿着待合并网格的合并侧通过匹配两个合并网格之间的最近距离边界顶点建立待合并网格之间的桥；对所述待合并网之间孔进行孔填充以完成合并。此外，或可选地，所述网格合并还包括：沿着边界遍历所述桥，并且记录桥的顺序，检查不连续的顺序，通过桥的顺序查找交叉的桥，并丢弃所述交叉的桥。

可选地，本发明各种不同实施方式基于QSlim算法采用下述二次曲面方程进行所述网格简化：

其中，Q_v表示为二次曲面，v表示顶点，p表示顶点的支持平面，planes(v)表示v的支持平面集合，K_p表示网格中顶点至支持平面的平方距离矩阵，α∈[0,1]确定了所检测的平面区域的重要程度，β∈[0,1]确定了平面区域的简化优先级，K_{planar region plane(v)}表示网格中顶点至所属的特征平面的平方距离矩阵。

另一方面，依照本发明实施方式的一种3D重建方法可以包括：通过多视角立体重建MVS获得对象的点云；从所述点云获取网格表面；基于所述获取的网格表面，采用上述各种不同实施方式所述的网格处理方法生成LOD网格；采用生成的LOD网格完成所述对象的3D重建。

再一方面，依照本发明实施方式的一种在LOD模型生成过程中处理网格的系统可以包括：

获得模块，用于获得初始网格；

剪切模块，用于剪切所述初始网格以得到多个LOD分区；

合并模块，用于通过网格合并将当前层级的LOD分区缝合以得到合并的网格；

简化模块，用于对所述合并的网格应用网格简化以得到下一层级的LOD分区；

其中，对所述下一层级的LOD分区迭代执行所述网格合并直至得到最终的合并的网格。

优选地，所述系统还包括对合并的网格存在的孔进行孔填充以使相邻网格表面相适应的填充模块。可选地，所述填充模块可用于执行第一填充处理：构建带有已知的孔的拓扑结构的网格补丁；将目标网格上的孔的边界顶点映射至该网格补丁的边界顶点；使用该边界顶点的位置作为约束条件对内部顶点进行平滑。此外，所述填充模块还可用于第二填充处理：对网格补丁进行初始三角化；通过增加内部顶点对三角化进行细化；将增加的内部顶点放置在使补丁表面与相邻表面相适应的位置。其中，对网格补丁进行初始三角化可包括：定义三角形的两个误差函数：W_面积和W_{二面角-角度}，其中，W_面积是指三角形的面积，W_{二面角-角度}是指与相邻三角形的最大二面角角度；定义网格补丁误差函数W为W_面积的总计的最小误差或W_{二面角-角度}的最大值的最小误差；通过使W最小化来完成初始三角化。在本发明的可选实施方式中，所述第二填充处理还可包括：平滑新填充的孔的表面，最小化边界顶点和增加的内部顶点之间的正常差异。

在本发明的选择性实施方式中，所述第一填充处理用于大于或等于预定阈值的孔，所述第二填充处理用于小于所述预定阈值的孔。

优选地，所述剪切可包括：定义切断平面；在所述初始网格中查找所有与该切断平面交叉的三角形；将所述交叉的三角形沿着剪切线分离成小三角形；通过使用所述小三角形的几何中心作为测试点将所有的小三角形标记在所述切断平面的任一侧，并且除去该侧中不需要的三角形。

优选地，所述网格合并可包括：沿着待合并网格的合并侧切掉预定偏移量以建立待合并网格之间的合并空隙；沿着待合并网格的合并侧通过匹配两个合并网格之间的最近距离边界顶点建立待合并网格之间的桥；对所述待合并网之间孔进行孔填充以完成合并。可选地，所述网格合并还可包括：沿着边界遍历所述桥，并且记录桥的顺序，检查不连续的顺序，通过桥的顺序查找交叉的桥，并丢弃所述交叉的桥。

优选地，本发明实施方式的系统基于QSlim算法采用下述二次曲面方程进行所述网格简化：

其中，Q_v表示为二次曲面，v表示顶点，p表示顶点的支持平面，planes(v)表示v的支持平面集合，K_p表示网格中顶点至支持平面的平方距离矩阵，α∈[0,1]确定了所检测的平面区域的重要程度，β∈[0,1]确定了平面区域的简化优先级，K_{planar region plane(v)}表示网格中顶点至所属的特征平面的平方距离矩阵。

又一方面，依照本发明实施方式的一种3D重建系统可以包括：

第一获取单元，通过多视角立体重建MVS获得对象的点云；

第二获取单元，从所述点云获取网格表面；

生成单元，基于所述获取的网格表面，采用上述各种不同实施方式所述的网格处理方法生成LOD网格；

重建单元，采用生成的LOD网格完成所述对象的3D重建。

依照本发明各种实施方式，其对于由快速增长的3D重建技术来带的日益增长的需求而言是鲁棒的且可扩展的。其优化了三个主要的网格操作，所述网格操作主要用于流程、固定由前述重建步骤产生的具有挑战性的网格瑕疵、合并网格而无需重叠要求或不产生衰减三角形、将通用简化算法优化为适于城市场景网格。在大型数据集上的实验表明其具有鲁棒性和可扩展性。

附图说明

图1示出了依照本发明实施方式的网格处理方法的示例流程。

图2示出了依照本发明实施方式的3D重建方法的示例流程。

图3示出了依照本发明实施方式的网格处理系统的示例架构。

图4示出了依照本发明实施方式的3D重建系统的示例架构。

图5示出了单个对象离散LOD的典型例子。

图6示出了一种原始的LOD设计。

图7a示出了采用原始LOD设计获得的3D重建图像示例。

图7b示出了在简化过程中约束边界产生不期望的星形网格结构。

图8示出了依照本发明实施方式的一种LOD设计。

图9示出了孔的定义。

图10示出了横跨分区的孔检测。

图11a示出了孔填充算法的典型输入。

图11b示出了未进行细化和整形的孔填充算法。

图11c示出了进行了细化和整形的孔填充算法。

图11d示出了孔填充算法与真实地面的比较。

图12示出了典型的输入数据规模。

图13示出了原始孔填充算法中α的效果。

图14示出了新的孔填充方法。

图15示出了新方法中采用的稀疏线性体系。

图16示出了原始孔填充算法与新方法的视觉比较(线架构(wireframe))。

图17示出了原始孔填充算法与新方法的视觉比较(表面)。

图18示出了新方法的限制。

图19示出了在简化新方法填充的区域之后出现陌生的自交叉。

图20示出了剪切中可能的情况。

图21示出了合并算法的输入。

图22a示出了合并算法的步骤1。

图22b示出了合并算法的步骤2。

图22c示出了合并算法的步骤3。

图23示出了和进步算法的最终结果。

图24示出了处理桥交叉问题。

图25示出了QSlim几何误差公司的目的。

图26示出了QSlim和本发明实施方式的简化方法的比较，其中，输入中黑色区域为检测到的平面区域。

图27示出了QSlim和本发明实施方式的简化方法的比较。

图28示出了用于实验的大型数据集。

图29示出了Toulouse的第5级LOD网格。

图30示出了Toulouse的第4级LOD网格。

图31示出了Toulouse的第3级LOD网格。

图32示出了Toulouse的第2级LOD网格。

图33示出了Toulouse的第1级LOD网格。

图34示出了Toulouse的第0级LOD网格。

具体实施方式

为了便于理解本发明技术方案的各个方面、特征以及优点，下面结合附图对本发明进行具体描述。应当理解，下述的各种实施方式只用于举例说明，而非用于限制本发明的保护范围。

下面参考方法、系统、设备、装置和编程以及计算机程序产品的示例框图来描述本发明。应当理解的是，示例框图中的每一个框及其组合可通过编程指令来实现，所述编程指令包括计算机程序指令。这些计算机程序指令可被装载至计算机或其他可编程数据处理装置，这样在计算机或其他可编程数据处理装置上执行的指令产生用于实现框图或流程图中指定的功能的指令。这些计算机程序指令还可存储在计算机可读存储器中，可指示计算机或其他可编程数据处理装置以特定方式运行，这样，存储在计算机可读存储器中的指令产生包括实现框图或流程图中指定的功能的指令的制造品。计算机程序指令还可装载至计算机或其他可编程数据处理装置，以产生一系列在所述计算机或其他可编程装置中执行以产生计算机执行程序的操作步骤，这样，在所述计算机或其他可编程装置上执行的指令提供实现在框图或流程图中指定的功能的步骤。编程指令还可存储于电子线路中和/或通过电子线路实施以实现本发明的各个功能、步骤。

网格处理方法

图1示出了依照本发明实施方式的一种在LOD模型生成过程中处理网格的方法。如图1所示，所述可以包括，但不限于：

110.获得初始网格；

120.剪切所述初始网格以得到多个LOD分区；

130.通过网格合并将当前层级的LOD分区缝合以得到合并的网格；

140.对所述合并的网格应用网格简化以得到下一层级的LOD分区；

150.对所述下一层级的LOD分区迭代执行所述网格合并直至得到最终的合并的网格。

在本发明的选择性实施方式中，所述方法还可以包括对合并的网格存在的孔进行孔填充以使相邻网格表面相适应。可选地，所述孔填充可包括第一填充处理，如下：构建带有已知的孔的拓扑结构的网格补丁；将目标网格上的孔的边界顶点映射至该网格补丁的边界顶点；使用该边界顶点的位置作为约束条件对内部顶点进行平滑。此外，所述孔填充还可包括第二填充处理，如下：对网格补丁进行初始三角化；通过增加内部顶点对三角化进行细化；将增加的内部顶点放置在使补丁表面与相邻表面相适应的位置。

其中，对网格补丁进行初始三角化可以包括：定义三角形的两个误差函数：W_面积和W_{二面角-角度}，其中，W_面积是指三角形的面积，W_{二面角-角度}是指与相邻三角形的最大二面角角度；定义网格补丁误差函数W为W_面积的总计的最小误差或W_{二面角-角度}的最大值的最小误差；通过使W最小化来完成初始三角化。

此外，或作为选择，所述第二填充处理还可以包括：平滑新填充的孔的表面，最小化边界顶点和增加的内部顶点之间的正常差异。

在本发明的可选实施方式中，所述第一填充处理用于大于或等于预定阈值的孔，即大孔，所述第二填充处理用于小于所述预定阈值的孔，即小孔。所述预定阈值可以根据实际需要进行确定，例如，600个顶点。

可选地，在本发明的一种实施方式中，所述剪切可以包括，但不限于：定义切断平面；在所述初始网格中查找所有与该切断平面交叉的三角形；将所述交叉的三角形沿着剪切线分离成小三角形；通过使用所述小三角形的几何中心作为测试点将所有的小三角形标记在所述切断平面的任一侧，并且除去该侧中不需要的三角形。

可选地，在本发明的一种实施方式中，所述网格合并可以包括，但不限于：沿着待合并网格的合并侧切掉预定偏移量以建立待合并网格之间的合并空隙；沿着待合并网格的合并侧通过匹配两个合并网格之间的最近距离边界顶点建立待合并网格之间的桥；对所述待合并网之间孔进行孔填充以完成合并。此外，所述网格合并还可以包括：沿着边界遍历所述桥，并且记录桥的顺序，检查不连续的顺序，通过桥的顺序查找交叉的桥，并丢弃所述交叉的桥。

可选地，在本发明各种不同实施方式中，基于QSlim算法采用下述二次曲面方程进行所述网格简化：

其中，Q_v表示为二次曲面，v表示顶点，p表示顶点的支持平面，planes(v)表示v的支持平面集合，K_p表示网格中顶点至支持平面的平方距离矩阵，α∈[0,1]确定了所检测的平面区域的重要程度，β∈[0,1]确定了平面区域的简化优先级，K_{planar region plane(v)}表示网格中顶点至所属的特征平面的平方距离矩阵。

依照本发明各种实施方式，其对于由快速增长的3D重建技术来带的日益增长的需求而言是鲁棒的且可扩展的。其优化了三个主要的网格操作，所述网格操作主要用于流程、固定由前述重建步骤产生的具有挑战性的网格瑕疵、合并网格而无需重叠要求或不产生衰减三角形、将通用简化算法优化为适于城市场景网格。在大型数据集上的实验表明其具有鲁棒性和可扩展性。

3D重建方法

图2示出了依照本发明实施方式的一种3D重建方法。如图2所示，所述重建方法可以包括，但不限于：

210.通过多视角立体重建MVS获得对象的点云；

220.从所述点云获取网格表面；

230.基于所述获取的网格表面，采用上述各种不同实施方式所述的网格处理方法生成LOD网格；

240.采用生成的LOD网格完成所述对象的3D重建。

依照本发明各种实施方式，其对于由快速增长的3D重建技术来带的日益增长的需求而言是鲁棒的且可扩展的。其优化了三个主要的网格操作，所述网格操作主要用于流程、固定由前述重建步骤产生的具有挑战性的网格瑕疵、合并网格而无需重叠要求或不产生衰减三角形、将通用简化算法优化为适于城市场景网格。在大型数据集上的实验表明其具有鲁棒性和可扩展性。

网格处理系统

图3示出了依照本发明实施方式的一种在LOD模型生成过程中处理网格的系统。如图3所示，网格处理系统可以包括，但不限于获得模块310、剪切模块320、合并模块330以及简化模块330。其中，获得模块310可用于获得初始网格，剪切模块320可用于剪切通过所述获得模块310获得的初始网格以得到多个LOD分区，合并模块330可用于通过网格合并将当前层级的LOD分区缝合以得到合并的网格，以及简化模块340可用于对所述合并的网格应用网格简化以得到下一层级的LOD分区，其中，对所述下一层级的LOD分区迭代执行所述网格合并直至得到最终的合并的网格。

在本发明的可选实施方式中，所述系统还可包括对合并的网格存在的孔进行孔填充以使相邻网格表面相适应的填充模块。可选地，所述填充模块可用于执行第一填充处理：构建带有已知的孔的拓扑结构的网格补丁；将目标网格上的孔的边界顶点映射至该网格补丁的边界顶点；使用该边界顶点的位置作为约束条件对内部顶点进行平滑。此外，所述填充模块还可用于第二填充处理：对网格补丁进行初始三角化；通过增加内部顶点对三角化进行细化；将增加的内部顶点放置在使补丁表面与相邻表面相适应的位置。其中，对网格补丁进行初始三角化可包括：定义三角形的两个误差函数：W_面积和W_{二面角-角度}，其中，W_面积是指三角形的面积，W_{二面角-角度}是指与相邻三角形的最大二面角角度；定义网格补丁误差函数W为W_面积的总计的最小误差或W_{二面角-角度}的最大值的最小误差；通过使W最小化来完成初始三角化。在本发明的可选实施方式中，所述第二填充处理还可包括：平滑新填充的孔的表面，最小化边界顶点和增加的内部顶点之间的正常差异。

在本发明的选择性实施方式中，所述第一填充处理用于大于或等于预定阈值的孔，所述第二填充处理用于小于所述预定阈值的孔。

在本发明的各种实施方式中，所述剪切可包括：定义切断平面；在所述初始网格中查找所有与该切断平面交叉的三角形；将所述交叉的三角形沿着剪切线分离成小三角形；通过使用所述小三角形的几何中心作为测试点将所有的小三角形标记在所述切断平面的任一侧，并且除去该侧中不需要的三角形。优选地，所述网格合并可包括：沿着待合并网格的合并侧切掉预定偏移量以建立待合并网格之间的合并空隙；沿着待合并网格的合并侧通过匹配两个合并网格之间的最近距离边界顶点建立待合并网格之间的桥；对所述待合并网之间孔进行孔填充以完成合并。可选地，所述网格合并还可包括：沿着边界遍历所述桥，并且记录桥的顺序，检查不连续的顺序，通过桥的顺序查找交叉的桥，并丢弃所述交叉的桥。

在本发明的各种实施方式中，所述网格处理系统基于QSlim算法采用下述二次曲面方程进行所述网格简化：

其中，Q_v表示为二次曲面，v表示顶点，p表示顶点的支持平面，planes(v)表示v的支持平面集合，K_p表示网格中顶点至支持平面的平方距离矩阵，α∈[0,1]确定了所检测的平面区域的重要程度，β∈[0,1]确定了平面区域的简化优先级，K_{planar region plane(v)}表示网格中顶点至所属的特征平面的平方距离矩阵。

依照本发明各种实施方式，其对于由快速增长的3D重建技术来带的日益增长的需求而言是鲁棒的且可扩展的。其优化了三个主要的网格操作，所述网格操作主要用于流程、固定由前述重建步骤产生的具有挑战性的网格瑕疵、合并网格而无需重叠要求或不产生衰减三角形、将通用简化算法优化为适于城市场景网格。在大型数据集上的实验表明其具有鲁棒性和可扩展性。

3D重建系统

图4示出了依照本发明实施方式的一种3D重建系统。在本发明实施方式中，所述3D重建系统可以包括：

第一获取单元410，通过多视角立体重建MVS获得对象的点云；

第二获取单元420，从所述点云获取网格表面；

生成单元430，基于所述获取的网格表面，采用以上各种不同实施方式所述的网格处理方法生成LOD网格；

重建单元440，采用生成的LOD网格完成所述对象的3D重建。

依照本发明各种实施方式，其对于由快速增长的3D重建技术来带的日益增长的需求而言是鲁棒的且可扩展的。其优化了三个主要的网格操作，所述网格操作主要用于流程、固定由前述重建步骤产生的具有挑战性的网格瑕疵、合并网格而无需重叠要求或不产生衰减三角形、将通用简化算法优化为适于城市场景网格。在大型数据集上的实验表明其具有鲁棒性和可扩展性。

以上基于方法、系统的各种不同实施方式对本发明进行了详细说明，下面以具体的应用对本发明进行举例说明。

应用示例

如前所述，与之前所述的简单的、单个对象LOD示例不同，本发明面临的课题是规模大得多并且不断增长，在LOD流程中还必须使用分治技术。LOD流程之前的步骤是MVS，其产生高密度不连续的网格表面。这些初始网格作为LOD流程的输入。需要注意的是，这些初始网格均处于共有协同系统中，因此，它们在其边界区域附近重叠。

一种原始设计是将每个初始网格处理为单个对象并且独立地产生LOD网格，参见图6。虽然这个设计具有非常好的扩展性，但是主要缺点在于相邻的网格之间具有边界差异。一种补救方法是在网格简化过程中约束或限制这些边界，但是这将大大破坏网格简化的有效性，因为固定的顶点的比例会快速增加并产生星形的过度简化的网格，参见图7a和7b。

因此，本发明实施方式采用四叉树(quad-tree)设计。参见图8。首先将所有输入网格剪切(trim)为全局2D栅格(global 2D grid)，较小的矩形网格称为分区(tiles)。每个方向上分区的数目为2ⁿ，其中，n为自然数。将该输入层级称为第n级LOD。在产生每个下一级的LOD过程中，首先通过网格合并将2×2当前层级的LOD分区缝合。随后，将所有网格瑕疵(mesh artifacts)固定在每个合并的网格中。最后，对合并的网格应用网格简化以得到下一级的LOD。按顺序重复该三步处理直至获得唯一一个最终合并的网格(即，第0级的LOD)。层级的数目随后为n+1，并且，在第n级，分区的总数为2ⁿ×2ⁿ＝2²ⁿ。因此，通过移至下一级，分区的数目减少为当前层级的四分之一。

四叉树设计可解决网格中的边界差异问题以及过度简化问题。该设计还降低了文件数目和网络I/O开销(overhead)，这是因为降低了总网格数。例如，如果获得2⁴×2⁴＝16×16＝256个分区作为输入，那么总共将产生2⁸+2⁶+2⁴+2²+2⁰＝341个离散的网格，相比较而言，在具有该层级数量的LOD的原始设计中，网格总数为2⁸×5＝1280。可见，总网格数得以显著减少。本发明实施方式的该设计是可扩展的，因为在产生下一级LOD时仅仅使用局部相邻的网格，其可以分布式进行。在每个层级仅需要一次数据聚合。分区的粒度、LOD层级的数目和简化比例取决于硬件限制和应用目的。总体而言，分区的粒度更加精细并且LOD层级更深趋于花费更长的时间，但是需要较少的强力机器(powerful machines)和更高的并行化(parallelization)。

可采用三种主要网格操作来实施这种设计，即，孔填充(hole filling)、剪切与合并(trimming and merging)、简化(simplification)。“孔填充”的目的在于固定初始网格存在的瑕疵(artifacts)，所述瑕疵可以是由于清除了非流形(non-manifold)网格而在流程内部动态产生的。“剪切”应用于初始网格以除去重叠区域而“合并”用于除去边界差异并向上移动四叉树。“简化”是LOD生成的核心，其中，简化可在维持网格几何保真度的同时减少网格尺寸。下面深入讨论每一个操作。

【孔填充】

理论上，网格中涉及两种类型的孔，即，边界孔和拓扑孔(topological hole)，参见图9。在此讨论边界孔并且简便起见简要参考边界孔作为孔。首先呈现实际的孔填充算法并讨论其限制和问题。随后介绍处理所述限制和问题的方法。

孔是拓扑特征，其可通过使用半边(Half-Edge)数据结构容易地检测，所述Half-Edge数据结构是表示网格的最常见的方式。每个非边界边缘可与两个三角形面相邻而边界边缘仅仅与一个面相邻，使另一侧开放，并由此成为孔的一部分。随后通过穿过所有的边界半边缘，可检测所有孔并且将每个孔表示为边界半边缘(或顶点)的有序列表。在本发明实施方式中，使用CGAL(Computational Geometry Algorithms Library，计算几何算法库)多面体数据结构，其本质上是代表网格的半边数据结构。

在本发明的一种实施方式中，LOD设计所有输入网格剪切为2D栅格结构并且每个矩形网格被称为分区。如何检测横跨分区存在的这么大的孔，像图10(左)中举例说明的一个孔。

孔的检测可通过首先识别和选择当投影在XY平面时具有未完全覆盖范围的所有分区。分区的覆盖范围可定义为其投影面积相对于矩形面积(即，完全矩形分区的面积)的比例。其投影面积可通过使用边界孔半边作为限制的边缘总计其2D限制的德劳内三角化(delaunay triangulation)中的三角形而发现。对投射面积的另一快速估算是计算其投射顶点的2D凸面外壳的面积。例如，CGAL提供了方便地计算两个值的软件包(packages)。随后对于所有那些未完全覆盖分区的选择向外扩张一个相邻的环的分区。最后，合并所选择的分区并且进行孔检测。参见图10。

在本发明的一种实施方式中，所述孔填充算法可分解为三个主要步骤：

1.初始三角化(Initial triangulation)。首先定义三角形的两个误差函数，W_面积和W_{二面角-角度}，W_面积是指三角形的面积，W_{二面角-角度}是指与相邻三角形的最大二面角角度。随后定义网格补丁(mesh patch)误差函数W为W_面积的总计的最小误差或其三角化的W_{二面角-角度}的最大值的最小误差。因此，网格补丁的初始三角化是使W最小化的初始三角化并且这可通过动态编程查找。

2.细化(Refinement)。初始三角化具有基本封闭的孔，但是三角化太粗糙以至于无法显示出自然样貌的补丁(patch)，因为其缺乏内部顶点。本步骤基于一些启发式标准(heuristic criteria)在三角化上迭代地增加更多的内部顶点。该标准由称为α的参数控制。简言之，较高的α导致细化程度更高并且花费更长的时间运行。

3.整形(Fairing)。在细化步骤中插入新的顶点之后，整形要将它们放置在使得补丁表面与相邻表面看起来自然的位置。这通过重复平滑新填充的孔的表面、最小化边界顶点和在细化步骤中插入的新的顶点之间的正常差异来完成。

这三个步骤在图11a，11b，11c，11d中进行图示。其中，没有细化步骤，初始三角化会产生奇怪的形状。在细化和整形步骤之后，填充的网格补丁的形状与相邻表面相适应。

因为算法中的步骤1的彻底动态编程检索，算法中的步骤1在O(n³)时间运行。在步骤2中的运行时间复杂性更难以精确界定，因为插入的顶点的数目与补丁的表面积和参数α成比例升高，但表面积无法很好地在3D空间中的孔上进行定义。在实际中，可产生好看的网格补丁，与不同的相邻形状相适应但对于微调参数和使用给定输入预测总运行时间而言是非常需要技巧的。

在本发明的另一种实施方式中，提供了改进的孔填充算法。在本发明实施方式中，孔的出现来自于三个来源。

1)它们是MVS步骤产生的初始网格的瑕疵。已知像水面、大楼的窗户等的反射表面无法重建并在网格表面留下大孔。

2)在下述的剪切和合并过程中，为了进行填充以作为合并的目的而故意产生孔。

3)孔填充算法有时产生非流形网格。通过清除非流形表面，其产生新的孔。

孔的最后两个来源由于其尺寸有限可通过该算法有效处理。然而，初始网格中的瑕疵对算法带来了很大的挑战，因为它们具有很大的输入尺寸并且覆盖了很大的面积。大的输入尺寸将减慢步骤1，由于其O(n³)运行时间的本质，并且较大的面积也将减慢步骤2和步骤3。

本发明的发明人在具有intel i7-4770K CPU的机器上进行了试验，该CPU具有四核运算器并支持8线程和32GB内存。试验结果如图12和表1所示。

表1：孔填充算法的评估

从上面的表格可以看出，当输入尺寸增加时运行时间呈指数形式逐渐升高。为了解决问题，在本发明的又一种实施方式中，可通过分解步骤1中的动态编程将算法扩展为支持多线程。虽然这可将运行时间成功提高若干倍(several folds)，但这种加速仍然受到机器核心数目的限制并且无法扩大规模，而大孔的尺寸实际上没有上限。

而且，本发明的发明人发现参数α的缺省值(即，)(其确定了细化的程度)无法产生看起来令人满意的网格补丁。所述发明人通过反复实验调整参数并最终设定α的缺省值约1.8。参见图13。

最后，本发明的发明人凭借另一完全不同的方法处理了这些类型的大孔。该方法受到下述内容的启发：大多数这些大孔本质上是平坦的。初始三角化步骤通常是多余的，因为最低的误差结果是可预期的，其仅仅是平面。实际上也不是必须要迭代地细化网格补丁以适应邻近的网格。在本发明的又一实施方式中，该新方法的基本思想是首先构建带有已知拓扑结构的网格补丁并且将目标网格上的边界顶点映射至该网格补丁的边界顶点。随后使用边界顶点位置作为约束条件对内部顶点进行平滑。参见图14。

平滑问题可表示为稀疏的线性体系(sparse linear system)Ax＝B。例如，参见图15所示的例子。

所有的内部顶点位于其相邻一环的平均位置并且所有边界顶点被固定。由于矩阵的稀疏本质，线性体系可使用像双共轭梯度方法这样的线性求解器(linear solver)在大致O(n²)时间内快速求解。得到的网格补丁是带有粗略等密度顶点的平滑表面。为了进一步利用大孔边界的形状通常简单的事实，通过降低采样，提取每个第k个顶点作为输入来近似输入边界。首先设定输入阈值，例如500或1000，随后降低采样输入顶点，这样其等效输入尺寸低于阈值。以这样的方式，最终可限制填充大孔的运行时间。

当孔较大，几乎为平面和凸面时，该方法运行最佳。运行速度极快并且得到的网格补丁的品质可与来自原始算法的网格补丁的品质媲美，参见图16、17。

另外，因为该方法未考虑任何像最小化与相邻三角形的二面角的角度这样的美学标准，其得到的网格补丁看起来不自然。该方法还产生了自交叉。参见图18。

幸运的是，这些大孔通常属于平面区域，像自然现象中的湖或河，并且网格补丁可与相邻表面完全混合。因此，本发明实施方式的LOD设计成对小孔和大孔分别处理，即小孔使用原始算法，对大孔使用基于新的线性体系的方法。在本发明的一种实施方式中，将大孔阈值设为600个顶点，并且很好地实现了平衡结果。

一个最终的暂时性问题是当对这些类型的网格补丁进行网格简化时，发现另一与这种方法有关的问题。之前提到，初始网格是从自然情景的3D重建获得的，所述自然情景具有自然几何特征或变化，而本方法将产生人工平滑表面。网格简化趋于过度简化这些平滑区域，产生针形和翻转三角形。参见图19。为了解决这个问题，将人工随机噪声引入最终的由线性体系获得的顶点位置。选择这种噪声的幅度作为平均边缘长度的一小部分以维持其影响最小化而防止补丁过度简化。

总体而言，根据本发明实施方式的孔填充算法，将其扩展为支持多线程，将其运行时间改善了数倍(several folds)。从实际使用角度而言，大孔确实出现并且原始算法的性能由于其O(n³)的本质而开始快速衰退。因此，本发明实施另一基于线性体系的算法以专门处理这种大孔。本发明实施方式还应用了降低采样以限制运行时间。虽然该新的方法在通用案例中具有其局限性，但是其在这些大孔通常是平面的和凸面的3D重建情况下运行良好。该方法将运行时间改善了数百倍并且得到的网格品质可与原始算法媲美。

【剪切与合并】

由于LOD流程设计的分治本质，对网格使用剪切和合并，这在其他LOD设计中是不常见的。

<剪切>

剪切是相当直接的网格操作。在本发明实施方式中，首先定义切断平面，随后查找所有与该平面交叉的三角形。随后，将那些交叉的三角形沿着剪切线分离成更小的三角形。最后，通过使用它们的几何中心作为测试点将所有的三角形标记在平面的任一侧，并且除去该侧中想要除去的三角形。存在三种交叉情况，并且可根据交叉边和顶点的数目对这三种交叉情况分类。如下：

(1)1顶点0边：无需操作，标记三角形至平面的+/-侧；

(2)1顶点1边：将三角形分离成两个三角形，增加一个新顶点；

(3)0顶点2边：将三角形分离成三个三角形，增加两个新顶点；

虽然对于许多网格操作而言衰减的三角形是不理想的，但是其在剪切中是可容许的。如果存在三个顶点完全位于剪切平面的衰减的三角形，可简单直接地将其分配给任一侧面并且这不会影响结果。否则，像常规三角形那样处理它们。幸运地是，剪切操作既不会产生非流形网格也不会产生衰减的三角形。参见图20。

其中，运行时间是O(n)，其中，n是面数。

<合并>

已存在多个已开发的网格合并算法。其中一类依赖于对表面重新采样和从重新采样的点云中提取合并的网格表面。虽然它们在通用情况下工作，但是它们是不理想的，因为重新采样会破坏原始网格拓扑结构并且无法保持足够多的几何保真度，这违反了3D重建的最初目标。一些其他方法依赖于发现合并的网格之间的重叠区域并小心地增加新的顶点和面以将其连接起来。然而，该方法无法处理非重叠输入网格。

事实上，本发明实施方式的LOD设计表明合并是特殊情况，因为合并网格(即，分区)被预先处理成矩形，并且已知合并的位置而无需检测重叠区域。图21示出了典型输入的示例。

在本发明实施方式中，通过重设孔填充算法来实施新的合并算法。该合并算法具有三个主要步骤：

1).沿着合并侧切掉微小偏移量(offset)以建立合并网格之间的合并空隙。

2).沿着它们的合并侧通过匹配两个合并网格之间的最近距离边界顶点建立合并网格之间的桥或连接。

3).应用孔填充以完成合并。

这三步骤在图22a、22b、22c和图23中显示。其中，图22a示出了建立合并空隙，图22b示出了建立连接桥，图22c示出了填充孔，图23以仅示出了边界的形式示出了合并算法的最终结果。

最微妙的部分是步骤2。首选，需要设定距离阈值以防止匹配相距太远的顶点，相距太远的顶点通常是错误的。所述阈值可通过缩放因子与桥接空隙(bridging gap)的宽度相乘设定。其次，横跨两个网格的合并边界的数目可能不是1对1配对并且可能发生桥交叉(bridge crossing)问题。这将导致错误的拓扑结构或非流形网格。事实上可检测桥交叉问题，例如，沿着边界遍历(traverse)并且记录桥的顺序并检查不连续的顺序，随后可在步骤3之前简单地丢弃那些交叉的桥。参见图24，左手侧显示了从B1至B5和从C1至C5的准确排序；右手侧显示了当在网格Y中横跨边界C时的桥交叉问题。在寄存B9之后，应当预见到B10，但代替它得到A4，在寄存A5之后，应当预见到A6，但代替它得到B8。

根据本发明实施方式，该合并算法摆脱了重叠的要求，重叠是其他网格合并算法中所必需的。由于在步骤1建立了合并空隙，最终合并的网格不含有衰减的三角形。

【简化】

网格简化是离散LOD生成中使用的核心算法并且过去已提出了多种算法。一些算法是以保真度为基础的，其开始指定误差阈值，随后在该误差界限范围内尽可能简化网格。该误差通常测量为输入和简化网格之间的几何误差，其可以是全局误差或局部误差，这取决于实际操作。一些算法是以预算为基础的，其与保真度为基础的算法相反，代替固定误差界限，以预算为基础的方法设定简化后想要实现的三角形的目标数目。随后应用一系列局部网格操作以简化模型，这最小化误差。

虽然没有一个尺寸拟合所有的简化算法，但是QSlim提出了一个经典方法，其将简化公式化为贪婪算法(greedy algorithm)以最小化每个网格操作步骤过程中的局部几何误差。其最大的贡献在于发明使用矩阵，从而简洁地且方便地表示误差矩阵，所述误差矩阵用于计算一对顶点塌陷之后塌陷顶点的最佳布局。该方法已被证明是成功的，因为其有力且有效并且为全新一类简化算法提供了启示。

在本发明实施方式中，发明人基于QSlim算法提供了一种网格简化方法，有助于保存和强化结构特点。

QSlim算法的总体思路是迭代地选择并破坏一对顶点为新的顶点并且将新的顶点放置在最佳位置，这样，所得到的网格的近似几何误差最小化。如图25所示，每次迭代的目的是使几何误差最小化，所述几何误差被定义为从顶点至其支持平面的平方距离。

假设平面p＝[a b c d]表示由方程ax+by+cz+d＝0界定的平面，其中，a²+b²+c²＝1并且顶点v＝[v₁ v₂ v₃ 1]表示空间中的一些任意点。随后从v至p的平方距离表达为：

squared_dist(v,p)＝(p^Tv)²＝(v^Tp)(p^Tv)＝v^TK_pv

其中：

$K_p={\mathrm{pp}}^T=\left[\begin{array}{cccc}{a}^2& ab& ac& ad\\ ab& b^2& bc& bd\\ ac& bc& c^2& cd\\ ad& bd& cd& d^2\end{array}\right]$

Kp将该平面的平方距离信息编码为对称的4×4矩阵数据包，其带有总共10个独特的浮动数字。从点v至一组平面(planes)的平方距离的总和可被有效计算为:

∑_{p∈planes(v)}squared_dist(v,p)＝∑_{p∈planes(v)}(v^TK_pv)＝v^T(∑_{p∈planes(v)}K_p)^v，

其是矩阵Kp的简单总和。在算法的预处理步骤中，将每个三角形各自对应的Kp与每个顶点Q_v相关联，Q_v简单表示为二次曲面，其中，Q_v＝∑_{p∈planes(v)}K_p，其中，planes(v)是v的支持平面集合。

随后，计算每个可行的顶点对V_i,V_j，其是它们塌陷的顶点v'的最佳位置，这样,Error_Vi,Vj＝v′^T(Q_Vi+Q_Vj)^v′被最小化。v'可通过对Error_vi,vj部分求导并将其设定为0而得到的线性体系求解而被快速发现，将所有误差插入堆结构(heap structure)并且在每次迭代中提取最小误差顶点对以执行塌陷(collapse)。在每次塌陷之后，新的顶点v'将从其母顶点中继承二次曲面为Q_v＝(Q_vi+Q_vj)，并且更新堆积树，用于与该新顶点相连的所有受到影响的顶点对。如果该v'无法求解，那么简单地回到将其指定为v_i或v_j或它们的中间点。重复该过程直至达到目标数目的三角形。

据此得到两种结论。首先，QSlim算法的公式表明最小化问题是局部的。塌陷的顶点的最佳位置是由在先顶点集的支持平面集决定的，从所述支持平面继承得到所述塌陷的顶点。该支持平面集从平面的附近生长出来并向外延伸一步。缺乏对全局特征的考虑，这使得QSlim对局部网格噪声敏感。其次，输入网格在MVS步骤总是受到不可避免的噪声的影响。甚至在输入网格中，在实际场景中的完全平的表面可包含噪声。

这产生不理想的结果，网格的平面区域无法积极地充分简化并且其他有价值的富有特征的区域具有相对较高的优先权得到简化。这在3D大规模重建并且场景中包含大量的平的表面时尤其突出。

受到上述内容的启示，在本发明实施方式中，发明人改良了二次曲面公式以使其有利于平面区域中的简化并且切断平面区域中的顶点以形成顶点所属的平面，从而平滑那些平的表面中的噪声。为了这样做，首先检测网格中的平面区域及其平面方程。本发明实施方式对已有的方法进行了优化，使其与本发明应用场景完全匹配，并得到了如下改良的二次曲面方程：

α∈[0,1]确定了所检测的平面区域的重要程度并且迫使对应的顶点切断至其检测到的平面。β∈[0,1]确定了在所有可行的顶点对中这些平面区域的简化优先级。在本发明实施方式的实验中，设定α为0.9，β为0.5。该新的二次曲面在算法开始时初始化并且其他步骤没有改变。图26和27显示了标准QSlim和本发明实施方式改进版本之间的区别。输入网格具有1.9M顶点和3.9M三角形。这两者根据三角形的数目被简化为输入的1％。

上述实验证实了本发明实施方式提出的新设计并且显示出QSlim确实导致顶点更加均匀分布，并且本发明实施方式改进的方法可更加积极地简化平面区域，在富有特征的区域(例如，车、树、房屋拐角和边缘)留下更多细节。

实验

以下使用前面描述的改进的网格操作，通过在单个机器上的大型网格数据集上进行实验来评估本发明实施方式的LOD设计。

<输入数据>

大型数据集命名为Toulouse，其是法国西南部的城市。该数据集通过3D重建系统产生。其已被预先剪切为128×64的分区栅格，由8044个可用分区构成。其总共具有407M顶点和798M面并且在存储器中构成总共31GB的大小。它们将被供给至LOD流程以产生第7级的LOD网格至第0级的网格。其具有4个交叉分区孔并且它们的尺寸非常大。图28显示了在第5级LOD中的数据集，未填充交叉分区孔以使读者明白输入数据集看起来像是什么这样的概念。第6级或第7级太大以至于无法加载在网格浏览器中。

<启动>

本发明实施方式的LOD流程在C++中实施并且集成为3D重建系统中的一部分。流程的流动由python脚本控制。当产生下一级LOD时，用于每个2×2网格的3步处理(即，合并、填充孔、简化)并行运行。为了填充交叉分区的孔，在产生第7级LOD之后添加了额外的步骤以检测其填充。

本发明实施方式的目的是在所有LOD层级上产生平均大小为200KB的LOD网格。因此，在从第7级至第0级的每个层级上设定简化比为0.25以补偿四叉树设计。因为输入文件的平均大小为4MB，所以对第7级的输入设定简化比为0.05。

在本发明实施方式中，运行试验的机器装配有i7-470K CPU，带有四个处理核并且支持8线程和32GB RMA。

<结果>

流程的总的运行时间是21,681秒或大约6小时。下面是实验总结。

表2:大型数据集的实验总结

图29示出了Toulouse的第5级LOD网格，图30示出了Toulouse的第4级LOD网格，图31示出了Toulouse的第3级LOD网格，图32示出了Toulouse的第2级LOD网格，图33示出了Toulouse的第1级LOD网格，图34示出了Toulouse的第0级LOD网格。

实验结果表明由LOD流程产生的所有的网格没有衰减的三角形、非流形边缘和顶点。

综上所述，本发明提出了LOD网格产生流程，其对于由快速增长的3D重建技术来带的日益增长的需求而言是鲁棒的(robust)且可扩展的。其优化了三个主要的网格操作，所述网格操作主要用于流程、固定由前述重建步骤产生的具有挑战性的网格瑕疵、合并网格而无需重叠要求或不产生衰减三角形、将通用简化算法优化为适于城市场景网格。在大型数据集上的实验表明其具有鲁棒性和可扩展性。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到本发明可借助软件结合硬件平台的方式来实现。基于这样的理解，本发明的技术方案对背景技术做出贡献的全部或者部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。

本领技术人员应当理解，以上所公开的仅为本发明的实施方式而已，当然不能以此来限定本发明之权利范围，依本发明实施方式所作的等同变化，仍属本发明权利要求所涵盖的范围。

Claims (24)

1.一种在LOD模型生成过程中处理网格的方法，其特征在于，所述方法包括：

获得初始网格；

剪切所述初始网格以得到多个LOD分区；

通过网格合并将当前层级的LOD分区缝合以得到合并的网格；

对所述合并的网格应用网格简化以得到下一层级的LOD分区；

对所述下一层级的LOD分区迭代执行所述网格合并直至得到最终的合并的网格。

2.如权利要求1所述的方法，其特征在于，还包括对合并的网格存在的孔进行孔填充以使相邻网格表面相适应。

3.如权利要求2所述的方法，其特征在于，所述孔填充包括第一填充处理：

构建带有已知的孔的拓扑结构的网格补丁；

将目标网格上的孔的边界顶点映射至该网格补丁的边界顶点；

使用该边界顶点的位置作为约束条件对内部顶点进行平滑。

4.如权利要求3所述的方法，其特征在于，所述孔填充还包括第二填充处理：

对网格补丁进行初始三角化；

通过增加内部顶点对三角化进行细化；

将增加的内部顶点放置在使补丁表面与相邻表面相适应的位置。

5.如权利要求4所述的方法，其特征在于，对网格补丁进行初始三角化包括：

定义三角形的两个误差函数：W_面积和W_{二面角-角度}，其中，W_面积是指三角形的面积，W_{二面角-角度}是指与相邻三角形的最大二面角角度；

定义网格补丁误差函数W为W_面积的总计的最小误差或W_{二面角-角度}的最大值的最小误差；

通过使W最小化来完成初始三角化。

6.如权利要求4所述的方法，其特征在于，所述第二填充处理还包括：

平滑新填充的孔的表面，

最小化边界顶点和增加的内部顶点之间的正常差异。

7.如权利要求4所述的方法，其特征在于，所述第一填充处理用于大于或等于预定阈值的孔，所述第二填充处理用于小于所述预定阈值的孔。

8.如权利要求1所述的方法，其特征在于，所述剪切包括：

定义切断平面；

在所述初始网格中查找所有与该切断平面交叉的三角形；

将所述交叉的三角形沿着剪切线分离成小三角形；

通过使用所述小三角形的几何中心作为测试点将所有的小三角形标记在所述切断平面的任一侧，并且除去该侧中不需要的三角形。

9.如权利要求1所述的方法，其特征在于，所述网格合并包括：

沿着待合并网格的合并侧切掉预定偏移量以建立待合并网格之间的合并空隙；

沿着待合并网格的合并侧通过匹配两个合并网格之间的最近距离边界顶点建立待合并网格之间的桥；

对所述待合并网之间孔进行孔填充以完成合并。

10.如权利要求9所述的方法，其特征在于，所述网格合并还包括：

沿着边界遍历所述桥，并且记录桥的顺序，检查不连续的顺序，

通过桥的顺序查找交叉的桥，并丢弃所述交叉的桥。

11.如权利要求1所述的方法，其特征在于，基于QSlim算法采用下述二次曲面方程进行所述网格简化：

其中，Q_v表示为二次曲面，v表示顶点，p表示顶点的支持平面，planes(v)表示v的支持平面集合，K_p表示网格中顶点至支持平面的平方距离矩阵，α∈[0,1]确定了所检测的平面区域的重要程度，β∈[0,1]确定了平面区域的简化优先级，K_{planar region plane(v)}表示网格中顶点至所属的特征平面的平方距离矩阵。

12.一种3D重建方法，其特征在于，包括：

通过多视角立体重建MVS获得对象的点云；

从所述点云获取网格表面；

基于所述获取的网格表面，采用权利要求1至11任意一项所述的方法生成LOD网格；

采用生成的LOD网格完成所述对象的3D重建。

13.一种在LOD模型生成过程中处理网格的系统，其特征在于，所述系统包括：

获得模块，用于获得初始网格；

剪切模块，用于剪切所述初始网格以得到多个LOD分区；

合并模块，用于通过网格合并将当前层级的LOD分区缝合以得到合并的网格；

简化模块，用于对所述合并的网格应用网格简化以得到下一层级的LOD分区；

其中，对所述下一层级的LOD分区迭代执行所述网格合并直至得到最终的合并的网格。

14.如权利要求13所述的系统，其特征在于，所述系统还包括对合并的网格存在的孔进行孔填充以使相邻网格表面相适应的填充模块。

15.如权利要求14所述的系统，其特征在于，所述填充模块用于执行第一填充处理：

构建带有已知的孔的拓扑结构的网格补丁；

将目标网格上的孔的边界顶点映射至该网格补丁的边界顶点；

使用该边界顶点的位置作为约束条件对内部顶点进行平滑。

16.如权利要求15所述的系统，其特征在于，所述填充模块还用于第二填充处理：

对网格补丁进行初始三角化；

通过增加内部顶点对三角化进行细化；

将增加的内部顶点放置在使补丁表面与相邻表面相适应的位置。

17.如权利要求16所述的系统，其特征在于，对网格补丁进行初始三角化包括：

定义三角形的两个误差函数：W_面积和W_{二面角-角度}，其中，W_面积是指三角形的面积，W_{二面角-角度}是指与相邻三角形的最大二面角角度；

定义网格补丁误差函数W为W_面积的总计的最小误差或W_{二面角-角度}的最大值的最小误差；

通过使W最小化来完成初始三角化。

18.如权利要求16所述的系统，其特征在于，所述第二填充处理还包括：

平滑新填充的孔的表面，

最小化边界顶点和增加的内部顶点之间的正常差异。

19.如权利要求16所述的系统，其特征在于，所述第一填充处理用于大于或等于预定阈值的孔，所述第二填充处理用于小于所述预定阈值的孔。

20.如权利要求13所述的系统，其特征在于，所述剪切包括：

定义切断平面；

在所述初始网格中查找所有与该切断平面交叉的三角形；

将所述交叉的三角形沿着剪切线分离成小三角形；

通过使用所述小三角形的几何中心作为测试点将所有的小三角形标记在所述切断平面的任一侧，并且除去该侧中不需要的三角形。

21.如权利要求13所述的系统，其特征在于，所述网格合并包括：

沿着待合并网格的合并侧切掉预定偏移量以建立待合并网格之间的合并空隙；

沿着待合并网格的合并侧通过匹配两个合并网格之间的最近距离边界顶点建立待合并网格之间的桥；

对所述待合并网之间孔进行孔填充以完成合并。

22.如权利要求21所述的系统，其特征在于，所述网格合并还包括：

沿着边界遍历所述桥，并且记录桥的顺序，检查不连续的顺序，

通过桥的顺序查找交叉的桥，并丢弃所述交叉的桥。

23.如权利要求13所述的系统，其特征在于，基于QSlim算法采用下述二次曲面方程进行所述网格简化：

其中，Q_v表示为二次曲面，v表示顶点，p表示顶点的支持平面，planes(v)表示v的支持平面集合，K_p表示网格中顶点至支持平面的平方距离矩阵，α∈[0,1]确定了所检测的平面区域的重要程度，β∈[0,1]确定了平面区域的简化优先级，K_{planar region plane(v)}表示网格中顶点至所属的特征平面的平方距离矩阵。

24.一种3D重建系统，其特征在于，包括：

第一获取单元，通过多视角立体重建MVS获得对象的点云；

第二获取单元，从所述点云获取网格表面；

生成单元，基于所述获取的网格表面，采用权利要求1至11任意一项所述的方法生成LOD网格；

重建单元，采用生成的LOD网格完成所述对象的3D重建。