Voronoi-based Variational Reconstruction of Unoriented Point Sets
- Abstract
- 1 Introduction
- 2 Estimating Unoriented Normals
- 3 Generalized Eigenvalue Problem
- 4 Implementation
- 5 Results
- 6 Conclusion
Voronoi-based Variational Reconstruction of Unoriented Point Sets
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌）是由乌克兰数学家格奥尔吉·沃罗诺伊建立的空间分割算法。灵感来源于笛卡尔用凸域分割空间的思想。沃洛诺伊图的单元被称为泰森多边形。
Abstract
我们介绍了一种从无向点集重建密闭表面的算法。使用输入点集的 Voronoi 图，我们推导出一个张量场，其主轴和偏心率分别表示表面法线的局部最可能方向和对该方向估计的置信度。然后通过求解广义特征值问题来计算隐式函数，使其梯度与张量场的主轴最对齐，从而提供最佳拟合等值面重建。我们的方法具有许多显著特征，尤其：隐式函数优化提供了对噪声的弹性、对数据的可调整拟合以及重建表面的可控平滑度。最后，使用简单网格（可能仅限于输入数据周围的薄壳）和（一个）各向同性拉普拉斯算子使数值处理简单而稳健。
输入仅有位置信息的点云，输出重建出的多分辨的网格。
图 1：Sforza。我们的变分方法允许对未处理的点集（3D 扫描 Sforza，200K 点）进行高保真重建。通过优化计算的标量函数的等值线提取最终网格。
1 Introduction
从点云重建表面是由许多 CAGD（Computer Aided Geometric Design 计算机辅助几何设计）、基于点的图形和逆向工程应用程序推动的，在这些应用程序中，需要将表面的分散点样本转换为适当的、密闭的表面网格。特别具有挑战性的是由激光扫描仪和手持式数字化仪生成的点集，因为它们通常嘈杂（由于测量的固有不确定性）、无组织（由于合并多个扫描）并且可能包含大孔（由于采集过程中的遮挡）。在这种情况下，表面重建只能是近似的，而不是插值的，因为数据点比实际样本点更能表明与表面的接近程度。
虽然许多算法现在可以有效地重建定向点（即，在每个样本处提供法线的点集），但很少有方法能够以可控的平滑度近似原始（未定向）点集。在本文中，我们介绍了一种基于 Voronoi 的变分方法来进行表面重建，它可以同等地处理无向点集和有向点集，甚至可以利用法线的置信度（如果可用）。由于我们的技术基于在嵌入空间中定义的变分定义的隐函数的等值线，我们保证密闭性和平滑性，同时提供对数据拟合的控制。
1.1 Related Work
这篇文章比较早，2007年的，就不放相关工作了。
1.2 Overview
我们的方法结合了谱方法的通用性和弹性，因为它可以将原始的、无方向的和嘈杂的点集作为输入。它还通过法线方向评估的全局拟合和平滑度控制提供基于泊松的重建质量。当点集包含法线信息时，该算法表现同样出色，甚至利用法线的置信度度量来提高重建表面的质量。为了为点集表面重建提供统一的变分框架，算法分两个主要步骤进行。首先，如果没有提供法线信息，我们将对点集引起的无方向法线执行新颖的 Voronoi-PCA 估计（第 2 节）。第一步产生一个张量场，它对（无方向的）法线方向（通过其最大特征值的特征向量）和近似置信度（通过其各向异性）进行编码。其次，通过广义特征值问题（第 3 节）计算隐式函数，以使其梯度最适合法线方向。算法的细节及其实现在第 4 节中给出，一系列测试和比较在第 5 节中介绍。
图 2：重建过程一目了然。从左到右：输入点集；它的 Voronoi 图；显示为（重新缩放）椭圆的单元格的协方差矩阵；通过 Delaunay （音：狄劳内）细化添加的 Steiner（音：斯坦纳） 点（各向同性张量分配给 Steiner 点）；分段线性函数
f
f
f（广义特征值问题的解）重建出的曲线（
f
f
f 的等值线）对输入数据最佳拟合。
2 Estimating Unoriented Normals
如果没有法线信息可用，我们的首要目标是根据输入点集估计推断表面的无向法线（及其可靠性）。请注意，我们不会尝试推断方向，因为这项全局任务将在我们方法的第二步中承担。
2.1 Background
在过去的几年里，点集的法线估计受到了很多关注。已经提出了各种策略，通过例如局部拟合 [CP03] 来保证高阶精度。然而，当点集嘈杂且非结构化时，大多数方法都会求助于两种流行技术中的一种，这两种技术都易于实现。
主成分分析 (PCA)
用于估计法线方向的传统技术是通过局部主成分分析。主要思想是在每个输入点周围定义一个小邻域，计算该邻域内点的协方差矩阵，并从关联到最小特征值的特征向量推导法线方向得到的协方差矩阵。已经提出了许多变体来提高对噪声的抵抗力。
Voronoi 极点
另一种用于估计法线方向的常用技术本质上是全局的，因为它需要构建输入点集的 Voronoi 图。然后提取称为极点的 Voronoi 顶点子集，并用于估计每个样本点的法线方向。在没有噪声和足够密集的样本的情况下，即使对于不规则采样，这种方法也可以提供可靠的法线估计，收敛速度取决于 Voronoi 单元的伸长率。
2.2 A Voronoi-PCA Approach to Normal Estimation
鉴于 PCA 和 Voronoi 极点各自的优点，我们提出了一种结合了它们两种特性的新型法线逼近技术。我们首先在一个非常大的边界球上添加虚拟样本点后计算输入点集的 3D Voronoi 图（因此输入点的所得 Voronoi 单元不会延伸到无穷大）。由于这些单元的形状反映了空间中点的全局分布，一个关键的观察结果是样本点的 Voronoi 单元的协方差矩阵不仅提供了法线方向的估计，而且还衡量了它的可靠性估计是。事实上，与最大特征值相关联的特征向量表示细胞沿其被拉长的轴（见插图），如果样本都位于一个公共流形上，则这是法线方向的一个很好的近似值。此外，估计的置信度与 Voronoi 单元的长度和厚度有关，即与协方差张量的各向异性有关。
2.2 对应插图
Voronoi 单元的协方差矩阵
设
V
V
V 是与样本点
p
p
p 关联的有限 Voronoi 单元。
V
V
V 的协方差矩阵由其相对于其质心
m
m
m 的二阶矩定义：
计算此积分的一种简单方法是将 Voronoi 单元
V
V
V 分解为四面体，以便按照附录 A 中的解释以闭合形式组装最终的协方差矩阵。如果采样质量好，此过程将非常准确，因为每个 Voronoi 细胞又长又窄。然而，如图 3（中）所示，如果存在噪声，Voronoi 单元会变小且各向同性。
图 3：点集的 Voronoi 单元。左图：没有噪声的点集的 Voronoi 图。中间：随着噪声，细胞变得不规则。右图：更密集、更嘈杂的点集显示出更多样的细胞形状。
Voronoi 单元并集的协方差矩阵
为了使我们的估计对噪声点集具有鲁棒性，我们计算了 Voronoi 单元并集的协方差矩阵（附录 A 中也提供了闭合形式的公式）：由于点集的 Voronoi 图划分了整个域，细长的单元是出现在嘈杂区域之外，并且积累足够多的邻居最终会使并集足够长（见图 3（右））。请注意，结合邻近者的影响来提高噪声恢复能力的想法很常见，但我们的技术是自适应的，因为我们根据需要使用尽可能多的邻近者来找到可靠的近似值，如下所述。
估算流程
我们按如下方式实现我们的估计过程：给定一个样本点 p p p，我们首先计算其 Voronoi 单元 V ( p ) V (p) V(p) 的协方差矩阵，并测量其各向异性 σ ∈ [ 0 , 1 ] 为 σ = 1 − i s o t r o p y ( V ) σ ∈ [0, 1] 为 σ = 1 − isotropy(V ) σ∈[0,1]为σ=1−isotropy(V)，其中各向同性 ( V ) (V) (V) 是最小和最大特征值之间的比率。然后我们迭代它的 k k k 个最近邻点 q i {q_i} qi，并对 V ( p ) ∪ V ( q 1 ) V (p) ∪V (q_1) V(p)∪V(q1) 执行相同的过程，然后对 V ( p ) ∪ V ( q 1 ) ∪ V ( q 2 ) V (p) ∪ V (q_1) ∪ V (q_2) V(p)∪V(q1)∪V(q2) 等执行相同的过程，直到各向异性已达到 0.9 的阈值，或者我们达到了最近邻的最大数量（通常 k k k = 50）。然后从这些协方差矩阵中返回具有最大各向异性的矩阵。最后，出于归一化的目的，我们重新缩放这个张量结果，使其最大特征值为单位1。请注意，当采样密集且无噪声时，此评估过程将在单个 Voronoi 单元停止：确实没有动机添加额外的邻域 Voronoi 单元，因为它主要会加厚方程（1）中的积分域 ，从而降低各向异性。
此过程受益于 PCA 的质量（对许多相邻样本的局部分析）和基于 Voronoi 的方法的质量（通过 Voronoi 图对样本重新分配进行全局分析）。我们的 Voronoi-PCA 法线估计技术可以看作是一种积分 PCA 方法，类似于用于曲率估计的其他工作：与基于其估计的极点方法相比，积分（在我们的例子中通过 Voronoi 单元）导致更稳定的估计在极点位置上。由于这种法线估计的质量对我们的重建过程很重要，我们将在第 5.1 节中展示数值实验，表明该过程优于它组合的两种法线估计技术。
3 Generalized Eigenvalue Problem
我们在这个阶段考虑编码法线方向的（协变）张量场已经通过我们的 Voronoi-PCA 方法估计，或者从输入数据中的法线信息（如 n n t nn^t nnt ）导出。我们现在希望计算一个隐式函数，使其梯度与张量场的主轴最佳对齐：对这个标量函数进行等表面处理将提供最佳拟合重建。
3.1 Problem formulation
虽然泊松重建可以直接给我们一个隐式函数，使其梯度最适合法线场，但我们不能求助于这种直接的线性求解，因为通过 Voronoi -PCA 张量只有一个方向场（即无方向的法线）。相反，我们需要找到一个隐式函数 f f f，使其梯度 ∇ f ∇f ∇f 在任何地方都与张量场 C C C 的最大特征值方向最佳对齐，其中“最佳对齐”的概念由法线方向上的局部置信度加权。我们提出以下约束最大化过程来有效地找到这样的函数 f f f ：
给定一个张量场
C
C
C，找到以下的最大化器
f
f
f：
其中 Ω Ω Ω 是定义域， Δ Δ Δ 是拉普拉斯算子。
这个优化问题的解释如下。能量函数 E C D E^D_C ECD ，称为各向异性Dirichlet （音：狄利克雷）能量，直接测量 ∇ f ∇f ∇f 与 C C C 指示的法线方向的对齐。实际上，各向同性张量（即未知法线方向）对该能量几乎没有影响，而各向异性张量（即，对法线方向的高置信度）将发挥重要作用——惩罚可靠数据点的错位。然后我们添加一个约束条件，即 E C D E^D_C ECD 必须在双谐波能量定义的单位球上最大化。就像狄利克雷（谐波）能量是平滑度 f f f 的度量一样，双谐波能量度量 ∇ f ∇f ∇f 的平滑度：因此，这个添加的约束强加了最大化器 f f f 的正则化。 f f f 的少量 L 2 L2 L2 范数被添加以避免必须约束 f f f 的值（在边界上或域内），以及改进条件：由此产生的约束是 f f f 上的类 Sobolev 范数 E B E^B EB。然而，在实践中，会用少量数据拟合来代替这个正则化项，将在 3.3 节中讨论。
求解这种受约束的最大化相当于仔细平衡 ∇ f ∇f ∇f 的平滑度与梯度的对齐：如果它对各向异性 Dirichlet 能量特别有益（即，当法线方向特别可靠时），它将使 ∇ f ∇f ∇f 与 C C C 对齐；在张量各向同性的区域，求解器将偏向函数梯度的平滑度。由于在单纯形网格的两个入射顶点之间翻转 ∇ f ∇f ∇f 的符号显着增加了双调和能量，因此这种全局平衡行为隐含地引起了张量场的一致方向。
3.2 Discrete Formulation
现在假设我们有一个具有 V V V 个顶点 v i {v_i} vi和 E E E 个边 e i {e_i} ei 的 3D 域的四面体网格。每条边 e i e_i ei 都是任意方向的。给定这个在每个顶点 i i i 都有一个张量 C i C_i Ci 的网格，我们希望求解一个基于节点的分段线性函数 f f f，即找到一个向量 F = ( f 1 , f 2 , . . . , f V ) t F = ( f_1, f_2, . . . , f_V )^t F=(f1,f2,...,fV)t 满足前面提到的约束最大化。
离散各向异性 Dirichlet 能量
优化中涉及的能量很容易表达。使用离散形式的表述，通过矩阵组装来构造我们的 3D 能量。因此，
E
C
D
(
F
)
E^D_C(F)
ECD(F)表示为
其中
d
0
d_0
d0 是网格的带符号顶点/边入射矩阵（大小
E
x
V
E x V
ExV）的转置，
⋆
C
1
\star ^1_C
⋆C1 是由
C
C
C 引起的度量的霍奇星(Hodge star)算子。我们用欧几里得对角线霍奇星来近似后一种算子由张量
C
C
C 调整，产生以下对角矩阵：
其中
e
i
e_i
ei 是第 i 个（定向的）边，
∣
e
i
∣
|e_i|
∣ei∣是它的长度，
∣
e
i
∗
∣
|e_i^*|
∣ei∗∣是其双 Voronoi 面的面积。边上的张量
C
C
C 的值是通过对边的每个顶点处的张量值进行平均得到的。
离散双谐波能量
对于双谐波能量，以下（简化的）离散化在实践中表现良好（稍后将通过数据拟合项添加正则化）：
使用与上面相同的符号。
优化过程
使用拉格朗日系数
λ
λ
λ，现在可以将约束优化重写为以下泛函的最大化：
最优性的必要条件是
∂
E
/
∂
F
=
0
∂E/∂F = 0
∂E/∂F=0，得到：
此表达式表示所谓的广义特征值问题 (GEP)，其中
F
F
F 是此 GEP 的特征向量，而
λ
λ
λ 是其对应的特征值。事实上，我们的约束最大化的解就是最大特征值对应的 GEP 的特征向量。
证明：由于 GEP 的特征向量构成一个基础，我们可以将函数 F F F 写成：
3.3 Generalizations
到目前为止，基于 Voronoi 的变分方法不需要参数调整来提供点集的重建。然而可以轻松地扩展这种基本方法，同时保持完全相同的框架。特别是，可以通过多种方式修改包含离散双拉普拉斯算子的矩阵 B B B，以便更好地控制平滑度和/或插值：
• 数据拟合：我们可以通过添加一个控制数据拟合的项来改变优化结果。我们通过在约束中添加拟合因子乘以输入点处函数值的平方和来支持输入点上的 0 值。更改拟合因子将为我们的程序提供可控的数据拟合效果。如数据拟合在空间上变化的变体，很容易设计。
• 张力下的样条能量(Splines-under-tension energy)：我们可以通过狄利克雷能量和双调和能量的线性组合定义单位球，而不是只使用双拉普拉斯算子。它将允许在结果的平滑度与法线方向的拟合之间进行更好的权衡，因为它等同于张力下的样条能量。
矩阵 B B B 需要稍微修改以实现这两个概括，我们将在第 4.3 节中详细介绍。虽然我们只对这两个示例进行了实验（接下来我们将详细介绍它们的实现），但 A A A 和/或 B B B 的其他修改是可能的，但无疑取决于应用程序。
4 Implementation
我们的技术是用 C++ 实现的。我们现在描述该算法以及我们为它的每个步骤所做的实现选择。
4.1 Voronoi-PCA Estimation
由于我们的算法是使用 CGAL 库实现的，因此这一步很简单。在读取输入点集并在大边界球体上添加几个虚拟点后，我们计算其 Voronoi 图。然后，我们使用第 2 节中描述的迭代过程为每个输入点找到一个张量，使用附录 A 中给出的公式来优化协方差矩阵计算。
4.2 Delaunay Refinement
在执行约束优化之前，我们必须细化和改进我们的 Delaunay 四面体网格（先前计算的 Voronoi 图的对偶）：由于点集可以是任意的，因此在初始网格上评估的任何数值近似都将不可避免地导致数值退化（由于 tets 的纵横比差）。需要进行 Delaunay 细化程序：这种简单的基于优先级队列的处理通过添加 Steiner 点迭代改进半径边缘比大于阈值（在我们所有测试中设置为 2）的四面体。在插入三角剖分的每个 Steiner 点，我们将张量 C i C_i Ci设置为 3 x 3 3x3 3x3 单位矩阵，以保持对那里的法线方向不可知。为了限制最终网格的大小，我们将细化限制为输入点集的放大边界框。还可以通过强制最大边长来细化输入数据周围薄壳内的网格，为重要的隐式函数提供更多自由度。图 4 以 2D 和 3D 形式说明了此过程。请注意，此细化过程类似于使用受限八叉树。不过，要指出的是，我们保留了原始点，从而避免了局部 “过平滑 ”的情况，而这种情况会出现在舍弃输入点集而采用替代（常规或自适应）网格的方法中。
图 4：Delaunay 细化。 （上）点集采样曲线的 2D Delaunay 三角剖分（左）通过在输入点周围的壳内添加具有（右）或不具有（中）尺寸约束的 Steiner 点来迭代细化； （底部）3D 示例。
4.3 Solver
我们通过将广义特征值问题 A F = λ B F AF = λBF AF=λBF 转化为经典特征值问题来求解它。我们首先使用 TAUCS 库预先计算 B B B 的 Cholesky 分解；这导致下三角矩阵 L L L 使得 B = L L t B = LL^t B=LLt 。我们现在将 GEP 重写为：
然后，我们使用 ARPACK++ 库中的隐式重启 Arnoldi 迭代方法，将
L
−
1
A
L
−
t
L^{−1}AL^{−t}
L−1AL−t作为 Arnoldi 运算符并仅请求最大特征值。收敛后，我们通过求解
L
t
F
=
G
L^t F = G
LtF=G找到解
F
F
F，因为它对应于原始GEP的最大特征值对应的特征向量。这个特征向量在四面体网格上定义了一个分段线性函数：我们现在准备好进行等值线绘制了。
Additional Terms
我们不仅使用bilaplacian算子，还向
B
B
B 添加了一个数据拟合矩阵（表示为
D
D
D）乘以参数
μ
f
i
t
μ_{fit}
μfit，如第 3.3 节所述。矩阵
D
D
D 是一个简单的对角矩阵，仅在与输入点对应的行上有 1（即，除了 Delaunay 细化添加的 Steiner 点之外的所有点）。参数
μ
f
i
t
μ_{fit}
μfit不仅允许我们调整数据拟合量，还可以调整连接组件之间的分离（见图 8）。另请注意，我们始终至少包含少量数据拟合项 (
μ
f
i
t
>
1
0
−
4
μ_{fit} > 10^{−4}
μfit>10−4) 以有效替代平滑约束中的
ε
ε
ε 正则化项。类似地，我们添加
μ
Δ
d
0
t
⋆
1
d
0
μΔd^t_0\star^1d_0
μΔd0t⋆1d0 以提供对平滑度的更多控制，如第 3.3 节所述。一旦用户选择了系数
μ
f
i
t
μ_{fit}
μfit 和
μ
Δ
μΔ
μΔ 的值，求解器就会按照矩阵
B
B
B 设置为：
B
=
(
d
0
t
⋆
1
d
0
)
2
+
μ
f
i
t
D
+
μ
Δ
d
0
t
⋆
1
d
0
B = (d^t_0\star^1d_0)^2 + μ_{fit}D + μΔd^t_0\star^1d_0
B=(d0t⋆1d0)2+μfitD+μΔd0t⋆1d0 的说明继续进行。
4.4 Contouring
为了找到要提取的等值线，我们首先评估所有输入点（不是 Steiner 点）的结果函数，然后选择等值线的中值（离群值可能会影响平均值；我们发现中值提供了更稳健的等值线）。对于最终等高线，可以使用简单的marching tetrahedra算法或基于 Delaunay 的表面网格划分算法。我们更喜欢后者，因为它生成的网格具有更少的元素，并且网格元素的质量有保证（所有三角形角度都在 20 到 140 度之间）。图 9 说明了具有三个统一大小标准的基于 Delaunay 的网格划分算法的输出。
5 Results
在展示我们的重建技术的结果之前，我们将对我们的 Voronoi-PCA 方法进行一些数值实验。
图 5：二维中的极点与协方差矩阵。一个点集对两条平行线进行采样；（下）从左到右，我们缓慢移动底线的采样；基于极点的正态估算值用蓝色表示，而我们基于协方差的正态估算值（从显示的 Voronoi 单元中得出）用红色表示；（上）两条曲线比较了基于极点的结果（蓝色，非常不连续）和基于协方差的估算值（红色），使用的是底线点移动时的角度误差（单位：度）。
5.1 Voronoi-PCA Estimation
我们首先通过检查一个非常简单的点集配置来说明我们的基于积分的法线估计技术与通常的基于极点的方法相比如何提供改进的数值，其中 2D 点沿两条平行线均匀采样。当底线缓慢移动时，Voronoi 单元的形状发生变化，触发（通常是不连续的）基于极点的正常估计的变化。因为我们的方法依赖于细胞的积分矩，所以它对偏移的敏感度明显较低，如图 5 中的曲线所示。另请注意，虽然
k
k
k 近邻 PCA 近似会在（基于欧几里得的）邻居包括两条线的点，我们的方法受益于 Voronoi 图的全局性质，使其对稀疏采样更加稳健。
下一个实验将我们对 3D 参数化曲面的常规估计技术与基于极点和基于点的 PCA 方法进行比较。我们使用不同的采样标准对高度场
z
=
s
i
n
(
x
)
c
o
s
(
y
)
z = sin(x)cos(y)
z=sin(x)cos(y)（其法线已知）进行采样：
• 无噪声：高度场首先在区间
[
−
π
,
π
]
2
[−π, π]^2
[−π,π]2 的参数空间中的规则网格上采样，采样率从20×20 个样本到100×100 个样本。
• 参数空间中的噪声。然后在参数空间中的抖动网格上对高度场进行采样，具有与上述相同的不同密度。噪声均匀且各向同性，最大幅度为网格间距的一半，使其随采样密度成比例。
• 嵌入空间中的噪音。第一种情况（规则网格）的样本现在使用一半网格间距的各向同性均匀噪声在嵌入空间中抖动。
图 6：参数曲面上的法线估计。 （上）无噪声采样，（中）参数空间中添加的噪声，（下）嵌入空间中添加的噪声。这些图显示了以度为单位的平均角度偏差作为采样密度的函数。蓝色为基于极点的估计，绿色为基于点的 PCA，红色为我们对单个 Voronoi 单元的协方差估计。
在这三种情况下，我们测量每个样本密度的法线估计值和真实法线之间的平均角度偏差。对于基于点的 PCA 技术，我们总是使用 8 个最近的邻居，因为它会导致最佳估计。如图 6 所示，我们的方法在所有测试中与它所基于的两种法线估计技术一样好或更好。公平地比较各种法线估计技术是出了名的难，因为许多参数都在起作用，例如采样密度、采样各向异性、噪声和异常值——因此我们的测试并不打算进行广泛和结论性的。尽管如此，我们进行了其他几个实验，这些实验都显示了使用基于 Voronoi 的协方差方法的数值相关性。对我们的法线估计技术的理论分析，应该利用 Voronoi 图、主成分分析和可能的几何测量理论，这个留待未来工作。
5.2 Surface Reconstruction
作为概念验证示例，我们从二维实验开始，以举例说明我们的方法与在同一单纯形网格上执行的基于泊松的方法之间的异同。如图 7 所示，第一个点集（密集、无噪声）很容易使用极点标记（红/蓝点是极点）定向，这允许我们使用泊松方程进行重建。这两种方法都会导致非常相似的重建曲线。当采样稀疏时，基于极点的定向过程无法提供“正确”的定向，泊松重建反映了这一错误，而最佳隐函数保持不变。
图 7：与二维泊松重建的比较。 （上）我们的方法与密集点集的泊松重建非常相似，可以可靠地推导出法线方向； （底部）对于稀疏/嘈杂的无向数据集，局部方向容易出错，而我们的变分方法仍然有效。
我们还说明了调整参数的效果（为清楚起见，在 2D 中）。 μ Δ μΔ μΔ 允许控制平滑度（图 8，顶部）。 μ f i t μ_{fit} μfit 控制输入点的拟合，从而控制两个分量的分离（图 8，中间）。它还提供了一种方法来增加嵌套组件的隐式函数的对比度（图 8，左下角）。还显示了一个来自稀疏数据集的形状完成示例，该示例是使用我们的样条线在张力下的能量获得的（图 8，底部/中间）。我们最后一个 2D 示例说明（图 10）对点集的稀疏性和数据中的噪声（包括少数离群值）的弹性。
我们还处理了许多从（激光范围）扫描仪发出的 3D 点集。展示了具有 14K 点的高尔夫球杆头（图 11）、小猫模型（图 9）、兔子（图 12）和具有 250K 点的半身模型（图 1）。此外，我们在图 13 中显示，我们的方法应用于原始的、无方向的点集（206K 点）恢复了与 泊松重建相似的表面，并为其提供了额外的法线信息。我们注意到，即使在八叉树深度为 11 时，基于泊松的网格也相对过度平滑，这主要是由于法线插值到八叉树叶上。如果需要这种过度平滑，我们可以类似地在输入点周围插入张量场，或者通过调整我们的两个参数来简单地增加平滑度（如图 8 所示）。
图 8：重建参数。 （上）调整 μ ∆ μ∆ μ∆（从左到右）可以轻松调整所得的平滑度，（中）而 μ f i t μ_{fit} μfit 控制与输入点的拟合（中和右），从而可以准确地分离和捕获附近的精细表面层。 （底部）数据拟合允许重建嵌套组件（左）；使用我们的张力下样条能量（中）可以轻松完成稀疏数据集的顺利完成；还可以准确捕获不同几何复杂性的单独组件。
图 9：Kitten。 （上）20K 输入点集、Steiner 点和隐函数，以及通过 marching tetrahedra 获得的阴影重建表面。 （底部）分辨率不断提高的三个输出网格。
图 10：噪声和稀疏弹性。 （上）我们的方法可以处理从密集（左）到稀疏（右）的原始数据集，而无需任何参数调整； （底部）类似地，即使在异常值（右）的情况下，结果也会随着噪声（左、中）而优雅地下降。
图 11：高尔夫球杆。扫描点集（14k 点），以及从不同角度看到的重建。
讨论
我们的方法提供了基于 Voronoi 的方法（通过 PCA 估计法线）、基于隐式的方法（因为隐式函数被全局优化以允许通过等值线平滑逼近）和光谱技术（因为我们的优化过程是可表达的）之间的独特组合作为广义特征值问题）。它在经验上与定向点集重建技术（例如泊松重建）的结果相匹配，但不需要法线方向。
最后，对于海量数据，我们的贡献和泊松重建之间的混合方法可能是最理想的：我们的方法可用于定向原始的、无方向的点集的子采样版本，从而为初始点集引入一个方向，泊松在其上然后可以执行解决。此外，由于法线方向的置信度估计可能成为新型扫描设备提供的测量的一部分，我们的技术可以直接利用这些附加信息。类似地，可以通过
μ
f
i
t
μ_{fit}
μfit 的局部变化来合并样本点的置信度。
6 Conclusion
我们提出了一种重建水密表面的算法，为有向和无向点集提供了统一的方法。如果没有可用的法线信息，我们的技术首先通过一种新颖的抗噪声 Voronoi-PCA 程序估计法线方向和估计的置信度。然后重建继续寻找一个隐式函数，该函数优化其梯度与估计/提供的法线方向之间的对齐。我们方法的显着特征包括在广义特征值问题中使用张量来平衡基于数据置信度的拟合和平滑度，以及添加数据拟合和平滑度控制的能力。
未来的工作
我们希望研究我们的正常估计技术的理论特性及其在尺寸检测中的应用。此外，为了实现理想指标函数，论文（以及泊松重建）中使用的
L
2
L^2
L2 范数显然是不合适的，因为急剧的过渡被过度惩罚了。相反，
L
1
L^1
L1 范数在这种情况下最好。然而，这种规范所需的计算开销是否值得带来额外的好处，这一点并不明显。最后，我们将张量转换为定向矢量场（即
∇
f
∇f
∇f ）的方法可能会为四边形重新网格化等应用提供一种新方法，因为（曲率）张量场可以沿着我们的技术线进行处理以提供曲率-无需用户交互的对齐网格。
图 12：Bunny。 （左）Bunny 数据集的广义特征值问题解的特征向量（假色）参见图 4； （右）底部的孔被填充。
图 13：与 3D 泊松重建的比较。在没有任何法线信息的情况下，我们的方法（左）会产生与提供定向法线的泊松重建（八叉树深度 11）相似的形状（尽管不太平滑）。