泊松表面重建
摘要
我们表明，从有向点的表面重建可以作为空间泊松问题。该泊松公式一次考虑所有点，而不依赖于启发式空间划分或混合，因此对数据噪声具有高度弹性。与径向基函数方案不同，我们的泊松方法允许本地支持的基函数的层次结构，因此该解决方案简化为良好条件的稀疏线性系统。我们描述了一种空间自适应多尺度算法，其时间和空间复杂度与重建模型的大小成比例。通过对公开可用的扫描数据进行试验，我们展示了比以前可实现的更详细的表面重建。
1.引言
从点样本重建3D表面是已经在计算机图形学中充分研究的问题。它包括导入扫描数据，填充表面孔，以及重新划分现有模型。我们提出了一种通过解泊松方程进行表面重建的新方法。
参考之前所做的相关研究（第2节），我们使用隐式函数框架来解决表面重建问题。具体地，像[Kaz05]一样，我们计算三维指示函数chi;（在模型内的点处定义为1，在外部的点处定义为0），然后通过提取适当的等值面来获得重建的表面。
我们的主要观点是，从模型表面采样的有向点与模型的指示函数之间存在一个整体关系。具体而言，指示函数的梯度是几乎无处不在的矢量场（因为指示函数几乎无处不在），除了在表面附近的点，它等于向内表面法线。因此，有向点样本可以被视为模型指示函数梯度的样本（图1）。
图1 二维泊松重建的直观图解
计算指示函数的问题因此可以简化为对梯度算子的反求，即找到使梯度最接近由样本定义的矢量场的标量函数chi;，即 。如果我们应用散度算子，这个变分问题就会转化为标准泊松问题：计算标量函数chi;，其拉普拉斯算子（梯度的散度）等于矢量场的散度
我们将在第3节和第4节中进行精确定义。
将表面重建公式化为泊松问题提供了许多优点。许多隐式曲面拟合方法将数据分割成用于局部拟合的区域，并且进一步使用合成函数组合这些局部近似。相比之下，泊松重建是一种全局解决方案，可以同时考虑所有数据，而无需借助启发式分区或合并。因此，与径向基函数（RBF）方法一样，泊松重建创建了非常光滑的表面，可以稳健地逼近噪声数据。但是，虽然理想的RBF是全局支持的并且是无衰减的，但泊松问题允许局部支持的函数的层次结构，因此其解决方案简化为条件良好的稀疏线性系统。
此外，在许多隐式拟合方案中，隐函数的值仅在样本点附近受到约束，因此重建可能包含远离这些样本的伪表面片。通常，通过引入辅助“表面外”点（例如[CBC * 01，OBA * 03]）来减弱该问题。利用泊松表面重建，这种表面很少出现，因为隐函数的梯度在所有空间点都受到约束，特别是远离样本的地方它被限制为零。
泊松系统因其在存在不完美数据时的弹性而众所周知。例如，“梯度域”操纵算法（例如[FLW02]）有意地修改梯度数据，使得它不再对应于任何真实的潜在场，并且只依赖于泊松系统来恢复全局最佳拟合模型。
在解决泊松问题方面已经进行了广泛的跨学科研究，并且已经开发出许多有效且稳健的方法。我们的问题实例的一个特有方面是，只需要求出在重建表面附近泊松方程的精确解。这允许我们利用自适应泊松求解器来开发重建算法，其空间和时间复杂度与重建表面的大小成比例。
2.相关工作
表面重建 从有向点重建表面在实践中存在许多困难。点采样通常是不均匀的。由于采样不准确和扫描错误配合，位置和法线通常是有噪声的。并且，扫描期间的可达性约束可能使某些表面区域缺少数据。鉴于这些挑战，重建方法试图推断未知表面的拓扑结构，准确地拟合（但不过度拟合）噪声数据，并合理地填充空洞。
有几种方法基于组合结构，例如Delaunay三角测量（例如[Boi84，KSO04]），alpha;形状[EM94，BBX95，BMR * 99]或Voronoi图[ABK98，ACK01]。这些方案通常会创建一个三角形网格，可以插入全部或大部分点。在存在噪声数据的情况下，所得到的表面通常是锯齿状的，因此在后续处理中进行平滑（例如[KSO04]）或重新调整（例如[BBX95]）处理。
其他方案直接重建近似表面，通常以隐式形式表示。我们可以将这些方法广泛地分类为全局或局部方法。
全局拟合方法通常定义以点为中心的径向基函数（RBF）的隐函数（例如[Mur91，CBC * 01，TO02]）。然而，理想的RBF（多谐波）是全局支持和非衰减的，因此解决方案矩阵过于密集。大数据集的实用解决方案涉及自适应RBF减少和快速多极方法[CBC * 01]。局部拟合方法一次考虑附近点的子集，一种简单的方案是估计切平面并将隐式函数定义为距离最近点[HDD * 92]的切平面的有符号距离。有符号距离也可以累积到体积网格[CL96]中。对于函数的连续性，可以将几个附近点的影响混合在一起，例如使用移动最小二乘法[ABCO * 01，SOS04]。不同的方法是通过自适应地细分空间来形成点邻域，例如利用自适应八叉树。使用统一的多级分区可以在八叉树结构上进行混合，并且可以启发式地选择每个八叉树节点内的局部隐式补丁的类型[OBA * 03]。
我们的泊松重建结合了全局和局部拟合方案的优势。它是全局的，因此不涉及用于形成局部邻域、选择表面补丁类型和选择混合权重的启发式决策。然而，基函数与环境空间而不是数据点相关联，是局部支持的，并且具有简单的分层结构，这会产生稀疏、条件良好的系统。我们解决指示函数的方法类似于Kazhdan [Kaz05]的基于傅立叶的重建方案。事实上，我们在附录A中表明，我们的基本泊松公式在数学上是等价的。实际上，快速傅里叶变换（FFT）是解决密集周期泊松系统的常用技术。然而，FFT需要 时间和 空间，其中r是三维网格分辨率，在高分辨率时算法的速度受到抑制。相比之下，泊松系统允许自适应离散化，从而产生可扩展的解决方案。
泊松问题 泊松方程出现在众多应用领域。例如，在计算机图形学中，它用于高动态范围图像的色调映射[FLW02]，图像区域的无缝编辑[PGB03]，流体力学[LGF04]和网格编辑[YZX * 04]。多重网格泊松解决方案甚至已经适用于高效的GPU计算[BFGS03，GWL * 03]。
泊松方程也用于传热和扩散问题。有趣的是，Davis等[DMGL02]使用扩散填充重建表面的孔。给定固定的有符号距离函数d形式的边界条件，它们的扩散方法基本上解决了齐次泊松方程Delta;d= 0以创建跨越边界的隐式表面。他们使用局部迭代解决方案，而不是全局多尺度泊松系统。
Nehab等[NRDR05]使用泊松系统将2.5维高度场拟合到采样位置和法线。它们的方法适合给定的参数曲面，非常适合从单次扫描重建曲面。然而，在样品是从多次扫描的并集中获得的情况下，它们的方法不能直接应用于获得连贯的水密表面。
3.泊松重建方法
输入数据S是样本的集合，每个样本由点s.p和面向内的法线组成，假设位于未知模型M的表面上或附近。我们的目标是通过近似模型的指示函数并提取等值面来重建表面的水密三角形近似，如图2所示。
图2 “犰狳人”模型扫描点（左），我们的泊松面重建点（右），
以及通过三维体积沿平面的指示器功能可视化点（中）。
关键的挑战是从样本中准确计算指示函数。在本节中，我们推导出指示函数的梯度与表面法线场的积分之间的关系；然后，我们通过给定有向点样本的求和来近似该表面积分；最后，我们从该梯度场作为泊松问题重建指示函数。
定义梯度场 由于指示函数是分段常数函数，因此对其梯度场的显式计算将导致在表面边界处具有无界值的矢量场。为避免这种情况，我们将指示函数与平滑滤波器卷积并考虑平滑函数的梯度场。以下引理形式化了平滑指示函数的梯度与表面正态场之间的关系。
引理：给定带有边界的实M，让 表示M的指示函数，是pisin;处的向内表面法线， 是平滑滤波器，并且表示它平移到点p。平滑指示函数的梯度等于通过平滑表面法线场获得的矢量场：
证明：为了证明这一点，我们展示了向量场的每个分量的相等性。计算平滑指示函数相对于x的偏导数，得到：
（第一个等式是在M之外等于0，在内部等于1。第二个是基于 。最后一个基于散度定理。）
类似的论证表明，等式两边的y和z分量相等，从而完成了证明。
近似向量场 当然，我们无法评估表面积分，因为我们还不知道表面几何性质。然而，有向点集的输入提供了足够的信息以用离散求和来近似积分。具体来说，使用点集S将划分为不同的小面片，我们通过点样本s.p的值与小面片的面积的乘积来估算小面片的积分：
应该注意的是，尽管方程1适用于任何平滑滤波器，但实际上，在选择滤波器时必须小心。特别是，我们希望过滤器满足两个条件。一方面，它应该足够窄，以便我们不会过度平滑数据。而另一方面，它应该足够宽，以便上的积分很好地接近由贴片区域缩放的s.p处的值。能较好平衡这两个要求的滤波器是高斯滤波器，其方差等于采样分辨率。
解决泊松问题 形成了矢量场以后，我们想解函数使得，但是通常是不可积的（即它不是路径无关的），因此通常不存在精确的解。为了找到最佳最小二乘近似解，我们应用散度算子来形成泊松方程
在下一节中，我们将更详细地描述这些步骤的实现。
4.实施方案
我们首先在假设点样本均匀分布在模型表面上的情况下提出我们的重建算法。我们在模型表面附近定义了一个高分辨率的函数空间，并且在远离它的位置定义更粗糙的分辨率，表示向量场作为该空间中函数的线性和，建立并求解泊松方程，并提取所得指示函数的等值面。然后我们扩展我们的算法以解决非均匀采样点的情况。
4.1.问题的离散化
首先，我们必须选择能够使问题离散化的功能空间。最直接的方法是从常规三维网格开始[Kaz05]，但是这种统一结构对于精细细节重建变得不切实际，因为空间的维度在分辨率上是立方的，而表面三角形的数量是平方增长的。
幸运的是，隐式函数的精确表示仅在重建表面附近是必要的。这促使使用自适应八叉树表示隐函数然后解决泊松系统（例如[GKS02，LGF04]）。具体来说，我们使用样本点的位置来定义八叉树O并将函数F o与树的每个节点oisin;O相关联，选择树和函数以满足以下条件：
1.矢量场可以精确有效地表示为F o的线性和。
2.可以有效地求解以F o表示的泊松方程的矩阵表示。
3.可以在模型表面附近精确有效地评估作为F o之和的指示函数的表示。
定义函数空间给定一组点样本S和最大树深度D，我们将八叉树O定义为最小八叉树，其属性是每个点样本都落入深度为D的叶节点。
接下来，我们定义一个函数空间，作为固定的单位积分基函数F：R 3→R的平移和尺度的范围。对于每个节点oisin;O，我们将F o设置为单位积分“节点函数”以节点o为中心，并以o的大小展开：
其中o.c和o.w是节点o的中心和宽度。
该函数空间 具有类似于传统小波表示的多分辨率结构。更精细的节点与更高频率的函数相关联，并且当靠近表面时，函数表示变得更加精确。
选择基函数在选择基函数F时，我们的目标是选择一个函数，使公式2中定义的矢量场可以精确有效地表示为节点函数{F o}的线性和。
如果我们要将每个样本的位置替换为包含它的叶节点的中心，那么向量可以有效地表示为{F o}的线性和：
这样，每个样本将对与其叶节点函数对应的系数贡献单个项（法向量）。由于采样宽度为2-D并且样本全部落入深度为D的叶节点中，因此固定引起的误差永远不会太大（最多为采样宽度的一半）。在下一节中，我们将展示如何通过使用三次线性插值来进一步减少误差，以获得子节点精度。
最后，由于最大树深度D与2-D的采样宽度相关，因此平滑滤波器应近似于具有2-D方差的高斯滤波器。因此，F应该近似具有单位方差的高斯滤波器。
为了提高效率，我们通过简化的函数逼近单位方差高斯，以便（1）得到的散度和拉普拉斯算子是稀疏的，（2）的评价函数表示为F o的线性和，在某点q处仅需要对接近q的节点 求和。因此，我们将F设置为盒式滤波器的第n阶卷积，其自身产生基函数F：
其中
注意，当n增加时，F更接近于高斯滤波器，并且其支持范围变得更大；在我们的实现中，我们使用n = 3的分段二次近似。因此，函数F定义在作用域为[-1.5,1.5] 3中，并且对于八叉树节点的基函数，最多有53 -1 = 124个相同深度的其他节点函数与其重叠。
4.2矢量场定义
为了获得子节点精度，我们避免将样本的位置固定到包含叶节点的中心，而是使用三次线性插值将样本分布在最近的八个节点上。因此，我们将指示函数的梯度场的近似定义为：
其中Ngbr D（s）是最接近s.p的八个深度D节点，{alpha;o，s}是三线性插值权重。（如果相邻点不在树中，我们会对其进行优化以包含它们。）
由于样本是均匀的，我们可以假设面片的面积是恒定的并且是平滑指示函数梯度的良好近似，最多相差一个常数系数，我们将证明常数系数的选择不会影响重建。
4.3 泊松解
定义了矢量场以后，我们想求函数使得的梯度最接近，即泊松方程 的解。
求解的一个挑战是，虽然和的坐标函数在空间 中，但是函数和却不一定在此空间中。
为了解决这个问题，我们需要求解函数，使得在空间上的投影最接近于的投影。由于函数F o一般不形成正交基向量，因此
全文共9994字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[616]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
