Analytic Marching

三维形状表面是嵌入在三维欧氏空间中的二维流形，而三维网格则是关于此流形表面的显式的分段线性近似表达。因三维网格具有容易存储、表示和渲染等优点，它在计算机图形学、虚拟现实等领域应用广泛。此外三维形状表面也可以被隐式场函数的等值面所隐式表达，从隐式场到三维网格的转换称之为网格化或等值面提取算法。现有的以移动立方体（marching cubes）算法[1]为代表的三维表面网格化方法因其需要对隐式场离散采样的特性，难以在恢复三维物体局部细节和算法执行时间之间得到较好的平衡。

为避免传统方法所带来的缺陷，观察到深度神经网络的超平面排列（hyperplane arrangement）机制[2]所带来的分段线性属性与三维表面网格自身的分段线性属性一致，我们提出了直接从表征了隐式场函数的多层感知机进行等值面提取的新理论，然后据此进一步提出基于解析的三维表面多边形网格生成的新算法[3]。实验结果表明，该算法生成的三维网格在精度上优于现有方案，能恢复出具有复杂拓扑的三维表面，并且执行时间远低于高采样率下的移动立方体算法[1]。

三维物体形状表面最常用的表示是多边形网格（polygonal mesh），然而具有复杂拓扑结构的多边形网格一般难以直接获得。借助隐式场函数，我们可以将三维形状表面定义成标量值场函数的等值面，其中最常用的三维形状隐式场函数是符号距离场。符号距离场是三维欧式空间中的标量场，对于在三维欧式空间中给定的坐标点，其数值大小是该点到二维流形表面的欧式距离，其数值符号区分了二维流形的内外部。

使用隐式场能够描述具有复杂拓扑结构的三维形状表面。将三维标量场的等值面网格化则能将隐式场表示转换成显式的网格表示。然而现有的以移动立方体（marching cubes）算法[1]为代表的网格化过程的精度往往取决于对隐式标量场采样的分辨率，并且转换之后往往会丢失局部细节。若采样率过低，则三维形状表面的细节会丢失；若采样率过高，则网格化过程的转换效率过低。

针对现有方法的缺点，本文探讨了如何从编码了给定三维形状表面的标量值场函数的多层感知机出发，使用多边形网格化算法，将隐式场函数的等值面转换成显式的多边形网格，并在转换的过程中尽可能地保持精度和提高转换效率的问题。

在对本文的方法进行描述之前，首先需要简要定义与多层感知机相关的各个概念。严格的定义以及详细的推导论证请参见原论文，在此处不过分展开。

为了严谨地描述使用线性修正单元（ReLU）的多层感知机，我们约定使用如下的表述来定义使用线性修正单元的多层感知机。

根据多层感知机固有的超平面排列性质，即对上层输入空间进行超平面划分的性质。我们定义了这些划分出来的子区域，并称之为区域（region）或胞腔（cell）。

紧接着，为了以另一种形式计算得到这些胞腔的具体表达，我们需要定义多层感知机的状态。形象地说，二元值状态向量描述了各个神经元的激活与否。有效的状态向量与多层感知机的胞腔一一对应，因此我们可以使用状态向量来确定是哪一个胞腔。

此外，借助已经定义好的状态向量的概念，我们可以将非线性的多层感知机映射在给定的胞腔范围内退化为简单的线性映射。

类似地，我们也可以将多层感知机各个神经元的输出的非线性映射退化为在给定胞腔范围内的简单线性映射。

在我们的问题里，我们的目标是学习一个符号距离场，我们所关注的区域是与零值面相交的那些胞腔。于是我们在多层感知机最末尾堆叠一个线性回归层用于拟合符号距离场数值。

如果该胞腔的确是与零值面相交，那么我们称之为解析胞腔（analytic cell）；由此相交得到的多边形面片我们称之为解析面片（analytic face）。

此外，我们还探究了这种解析面片的表达在何种条件下才能构成封闭的、分段线性的三维表面。并给出了如下的定理。该定理所需的条件是非常容易满足的，因此该定理是适用的。这表明在大多数任何情况下本方法都能获得精确的、封闭的、分段线性的三维表面。

根据已经定义的符号和概念，我们不难给出一个算法，使用该算法能得到精确的、封闭的、分段线性的三维表面。我们称该算法为analytic marching[3]（此处向著名的marching cubes算法[1]致敬）。

该算法的核心思想是，由一个状态向量出发，逐个求解相邻的状态向量，直至求解收敛完成。这个过程就好比是在三维表面移动游走，以解析的方式遍历所有可能的解析面片。

① 首先我们随机初始化一个三维坐标点，然后使用基于优化的方式使该坐标点移动至三维物体表面。这可以通过求解如下的优化问题获得初始解。

④ 依据解析面片表达，使用顶点枚举技术计算得到解析面片的所有边界顶点。同时记录其相应的边界平面。

借助已有的对多层感知机的线性区域估计的理论研究，我们不难推导得到本算法的计算复杂度为如下（详细过程请参见原论文）。简言之，复杂度与多层感知机的深度成指数关系，与多层感知机的宽度成多项式关系。

在实际应用时，可以使用多点初始化的方式，这有助于恢复出潜在分离的各个独立的三维表面。并且支持并行计算，大大加速了计算速度。

我们的采取直接训练多层感知机的方式，采用如下的训练目标函数。其中的单位梯度正则项有助于使得学习得到的符号梯度场平滑。

我们使用常用的ShapeNet数据集进行实验，并使用常用的指标（CD、EMD、IOU、F）进行定量比较，同时记录时间、多边形面数等信息。具体实验设置请参见原论文。

为了探究各种结构多层感知机的影响，我们进行了消融实验。实验结果表明，选取恰当的网络宽度和深度是取得高效率的关键。

为了探究不同种类物体的形状复杂度，我们对其余种类物体也进行了实验，实验结果表明，在ShapeNet数据集中，似乎飞机的形状复杂度比较低，而椅子的形状复杂度较高。

此外，为了和主流的网格化算法进行性能对比，我们进行了比较实验。所选取的网格化算法以此为：移动立方体算法[1]（MC）、贪婪网格化算法（GM）、移动四面体算法[4]（MT）、对偶轮廓算法[5]（DC）。他们都是基于离散空间采样的算法，因此根据采样率我们在其末尾添加数字（例如MC512表示采样512立方个样本的移动立方体算法[1]）。据我们所知，我们的算法似乎是第一种基于神经网络解析的网格化算法，因此我们的算法只有一种分辨率，即绝对精度。

实验结果表明，我们方法均取得传统离散采样方法的精度上界。并且相比高采样率下的其余算法具有较低的求解时间。

限于篇幅和展示分辨率限制，我们仅在此展示移动立方体算法[1]与本算法所获得网格的局部细节对比，更多结果请参见原论文。可以观察到，移动立方体算法[1]所获取得到的网格只是潜在三维表面的离散近似。在一些细节方面并不能很好地恢复出高曲率三维表面。而我们的算法能够很好地恢复出绝对精确的三维物体表面，并具备多边形纹理的特点。

在实际应用场景中，我们的算法具有替代传统marching cubes算法[1]的可能性。本算法无需离散采样，而是使用基于解析的技术直接从表征了三维物体场函数的多层感知机中无损解析出多边形网格。但是本方法具备一定的局限性，首先本算法只适用于以分段线性为激活函数的神经网络，其次该神经网络需要完全刻画三维物体而不额外取决于其余输入。

受启发于多层感知机的局部线性性质与三维网格的分片线性性质一致这一基本观察，我们基于已有工作提出了适用于在三维欧氏空间中解析神经网络的新理论，以此为基础进一步提出了一种基于解析的三维表面网格化算法[3]。该算法相比现有的以移动立方体算法[1]为代表的离散采样网格化方法，具备能够恢复出高曲率三维细节、解析速度快等优点。本工作具备一定的理论研究参考价值和实际应用价值。

[1] Lorensen, W. E. and Cline, H. E. Marching cubes: A high resolution 3d surface construction algorithm. In SIGGRAPH, pp. 163–169. ACM, 1987.

[3] Jiabao Lei, Kui Jia. Analytic Marching: An Analytic Meshing Solution from Deep Implicit Surface Networks[J]. arXiv e-prints, 2020. arXiv:2002.06597.

[4] Doi A, Koide A . An Efficient Method of Triangulating Equivalued Surfaces by using Tetrahedral Cells[J]. Ieice Transactions on Information & Systems, 1991, 74(1):214-224.