基于GPU的局部傅里叶变换及其在曲面重构中的应用

沙特国王大学学报基于GPU的局部傅里叶变换穆罕默德·H.放大图片作者：John M.侯赛因ba埃及伊斯梅利亚41522计算机与信息学院计算机科学系b吉达大学计算机科学学院信息技术系，吉达25651，沙特阿拉伯阿提奇莱因福奥文章历史记录：2019年12月18日收到2020年3月7日修订2020年4月12日接受2020年4月18日网上发售保留字：并行和直接计算计算机图形学曲面重构A B S T R A C T曲面重构过程近年来引起了研究人员的极大兴趣曲面重建在可视化、几何造型、多分辨率分析等领域有着重要的应用在本文中，我们提出了一种方法，从一组有向点的表面近似。我们的算法结合了隐式曲面和基于频率的框架，将曲面的指示函数转换为隐式函数，从中我们可以提取所需的曲面。与传统的基于频率的方法相比，我们的方法避免了输入点的体素化，并直接从表面计算傅立叶系数，这减少了解决体素网格所需的内存量，并消除了与体素化对应的数学错误。此外，我们利用最新进展的GPU嵌入在图形卡中，以加速傅立叶系数的计算。最后，通过实例验证了该方法的有效性。©2020作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍由3D采集设备创建的基于点的表面可以减少扫描表面的连接所需的空间。该过程最小化了大规模对象（例如，考古艺术品）的时间和存储复杂性（Boubekeur等人，2005年）。表面的采样点可以与法向量相关联。然而，在许多应用中，样本点之间的连接性代表有益的信息。实际上，曲面重构就是为点基曲面建立一致的连通性信息的过程。事实上，从一组点重建表面是计算机图形学领域中深入研究的方法（Kazhdan，2005; Berger等人， 2017年）。在本文中，我们提出了一种方法来建立一个水密表面从一组定向点，在GPU并行框架中执行。与传统方法相比，*通讯作者：计算机与信息学院计算机科学系，伊斯梅利亚41522，埃及。电 子 邮 件 地 址 ： mohamed_mousa@ci.suez.edu.eg （ M.H.MOUSA ） ，m_ci.suez.edu.eg（M.K. HUSSEIN）。沙特国王大学负责同行审查制作和主办：Elsevier该方法使用输入模型的四面体化而不是体素化。 我们的方法可以总结，见图。（1）从给定的点出发构造kd-树，条件是每个节点都包含一个关于局部切平面的非折叠曲面片。KD树相对于八叉树具有独特的优点，因为它们保证具有至多对数深度，这与最近邻查询所需的时间有关。（2）基于所得到的kd-树，对kd-树单元格生成一组局部三角剖分。(3)从这些局部三角剖分，我们构建了一组四面体表示的内部模型，我们近似的傅立叶系数的集合(4)最后，我们得到了一个隐函数逼近整个流形，从中可以提取等值面。1.1. 贡献本文基于隐式曲面框架，它被认为是曲面重构问题的最快框架。其主要目标是重建一个封闭的表面近似一组给定的定向点。其主要思想是计算代表该流形的特征函数。特征函数除了在流形内部等于1之外，在任何地方都是零值。然后，可以提取该流形的表面作为该函数的等值面与Kazhdan（2005）中提出的方法类似，我们使用傅立叶分析来近似隐函数，https://doi.org/10.1016/j.jksuci.2020.04.0101319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com1432M.H. M.K.穆萨侯赛因/沙特国王大学学报Fig. 1.概述所提出的方法：输入点样本的空间分区使用kd树，最后，一个高度详细的表面被提取作为一个等值面的隐式函数代表的kd树细胞。我们提取表面。然而，我们直接在样本点上应用计算，而不将网格近似为规则体素网格。事实上，任何物体的体素化都会增加计算的容差，并且需要大量的内存来保存体素网格。因此，不需要像在传统傅立叶技术中那样获得具有与所需带宽相同尺寸的体素网格。 因此，较高带宽的计算受益于先前带宽的计算。本文的其余部分组织如下。第2节简要回顾了最新的表面重建技术。第3节说明了如何将基于点的表面转换为作为一组四面体的体积表示。在第4节中，我们介绍了这种体积表示如何减少傅立叶系数的计算，然后在第5节和第6节中介绍了实现问题和结果。最后，我们在第7节结束了我们的论文。2. 相关工作由点集生成曲面是计算机图形学领域的一个发展趋势。许多算法已经被开发出来，以转换点为基础的表面到他们的模拟分段线性曲面（网格）。研究方法可分为三组：（1）使用显式三角剖分解决曲面重构的技术，（2）通过拟合曲面点解决曲面重构的技术，和（3）在隐式框架中将曲面重构作为等值面解决的技术。在显式曲面重构框架中，从点样本创建Delaunay三角剖分或Voronoi图该框架的主要目的是，所获得的表面是基于Delaunay三角剖分或其对偶的子复形，Voronoi图（Cazals和Giesen，2006;Dey，2011）。这些结构近似于给定点的拓扑连通性（Boissonnat和Daniel，1984; Maurya和Magar，2018;Dey和Goswami，2003;Amenta等人， 2001），并且这些类型的方法的主要益处是输出表面的复杂性是输入点的基数的数量级。此外，我们可以使用有效的采样密度来控制创建的曲面的质量然而，这一类别有两个主要缺点。首先，这些方法需要大量的计算来获得Delaunay三角剖分，这对于大规模应用来说可能是浪费的。数据集。其次，当输入点在模型表面上分布不一致时，性能较弱曲面拟合技术通过扭曲基础模型以理想地拟合模型的几何信息来执行曲面重建（Terzopoulos和Vasilescu，1991; Duan和Qin，2004）。这些方法引入了一个基本的形状作为一组相互连接的点与弹簧。然后，根据给定的表面数据，通过改变弹簧刚度或点几何形状来变形形状。与前面的类别一样，这些技术产生的曲面的复杂性与给定点的基数有关。然而，创建的表面的拓扑通常限于基本形状的拓扑，从而限制了可以经由该策略创建的模型的类别。用于重建表面的第三类技术利用输入点来表征3D中的隐函数。基于该函数，获得作为等值面的所需表面（Ohtake等人，2003; Kazhdan等人，2006; Kazhdan，2005; Zhou等人，2011; Kazhdan和Hoppe，2013; Hussein和Mousa，2015）。这类方法的好处是所得到的表面总是水密的，并且隐函数的利用不限制所得到的等值面的拓扑性质。这种技术可以在广泛的3D模型上执行。实际上，这种类型的方法具有时间和空间复杂度取决于所使用的体素化的大小而不是所获得的表面的限制，并且这些方法中的相当多的方法利用多级结构来评估输入点周围的小邻域上的隐函数。这种方法最大限度地减少了时间和空间的COM-整个过程的复杂性。可以对先前的技术进行一些增强以加速计算。例如，Kopcke等人（2019）提出了一种基于GPU的FFT计算，可以加速Kazhdan（2005）中的隐式函数求值。此外，Nvidia 实施了高度优化的cuFFT库（NVIDIA，2019），可在Nvidia GPU上实现FFT还可以用于提取被称为傅立叶描述符（FD）的不变特征，其在形状表示和相似性测量中起重要作用（Arbter等人，1990; Yongyang等人，2017年）。实际上，低阶系数表示模型的整体形状，而高阶系数表示更精细的细节。此外，这些FD是独立的位置，缩放和旋转。然而，使用这两者的FFT 的评估（Kopcke 等人，2019;NVIDIA ，2019）需要将输入模型预处理为等距的体素网格。随着包含更多细节的表面，构建该体素网格消耗越来越多的时间这种冗长的网格建设时 间 是 我 们 在 本 文 中 寻 求 避 免 我 们 将 在 第 6 节 的 后 面 部 分 与（NVIDIA，2019）进行一些比较。我们的方法属于最后一类;然而，我们的计算直接在表面点上进行，避免了对体素网格的需要。对于具有大量点的模型，我们的计算方法需要比构建体素的高维网格少得多的时间来处理所有点，如下所述。3. 四面体化在这一节中，我们展示如何获得表示闭流形M的全局三角剖分的近似。其主要思想是得到一组不相交的局部三角剖分来逼近M的曲面。一个足够稠密的流形由一组定向点组成;因此，如果我们足够接近曲面，则任何点的局部三角剖分都可以简化为2D三角剖分。这里的主要挑战是在流形表面周围创建一组局部邻域，M.H. M.K.穆萨侯赛因/沙特国王大学学报14332条件是每个邻域可以投影到其平均切平面而不折叠。然后，从这些三角形，我们计算局部傅立叶系数，我们将讨论在第4节。M四面体化的主要步骤总结如下：1. 将M的点样本划分为一组非折叠曲面片.2. 三角定位局部区域。3. 对于每个三角面片(a) 将所有三角形与原点连接，形成一组四面体。(b) 对符号四面体进行累加，得到流形的整体符号体积3.1. 构建kd树在这一节中，我们解释如何将M的曲面划分为一组非折叠曲面片。为了实现这个目标，我们使用kd树数据结构，它是一种很好的空间划分数据结构，用于组织任何k维空间中的点kd树被认为是各种应用中用于空间布置的最有效的数据结构之一（Zhou等人， 2008年）。与传统的kd树算法不同，在kd树算法中，树的层次结构是通过“深度优先”导航来构造的，我们的事实上，并行利用同一级别的节点使我们能够从GPU最新进展的并行架构中通过遍历BFS序列，我们利用了GPU并行框架，因为在每个BFS级别，每个单元都生成一个新的线程。因此，在每一级，线程的数量是前一级的两倍。一个重要的kd树层次特征是它可以为同一级别的每个单元提供邻域信息，这是使用marching cubes框架构建表面的要求，我们将在后面讨论。现在，我们演示如何构建kd树。如前所述，主要的挑战是创建一组包含非折叠表面补丁的kd树细胞。为了实现这一目标，我们使用特殊的分裂条件s，以满足所需的分区cri-teria（Boubekeur等人， 2005年）。每个kd树单元Ci被划分，如果SI 在这个牢房里不满足s的正式写法为：算法1：从第i层计算第i层的子节点。该算法采用一组定向点作为输入，并遵循算法1中给出的指令流水线。从AABB（M）开始，M的轴对齐边界框，算法通过如下检查每个节点来并行处理当前级别的所有节点：1. 计算给定单元格的分裂条件。2. 如果满足s，则将最长边的中值计算为分裂面3. 相对于切割平面，将上部和下部子单元标记为给定单元的两个子单元一旦kd树的所有叶子都满足分裂条件s，我们就对每个kd内的局部曲面片进行三角剖分。树叶3.2. 局部三角测量s¼（true如果. ~np;~niii>s8p2Cið1Þ现在，划分步骤完成了，所以对于所有的i假否则其中~ni是平均法线，s表示Ci中允许的相对于~ni 的最大偏差角的余弦。If不满足分割条件si，则沿着最长边的中值分割单元Ci分割条件s保证：局部点相对于平均切平面不折叠，见图12。 二、Ci。换句话说，Ci中的点集，近似于M的表面，不包含任何根据局部切平面的折叠。在任何给定小区Ci处的M的局部三角测量总结如下：1. 求切平面pi。2. 投影所有点pC i到Pi。3. 对投影点进行三角剖分。4. 将三角化点重新投影回原始曲面。图二. 非折叠kd树划分的2D示例。1434M.H. M.K.穆萨侯赛因/沙特国王大学学报M.ðÞ¼ZZZ系列XRRð Þ2X...ð Þp2CijCi j.ΣM不不1K不22@x@yM@zMR3.给定任意胞元C i，切平面pi 取决于我知道了。1n~t指向不正确的ehtð4Þ平均法向量~ni和局部重心mi。对于-mally，mi定义为：-其他1我们将M的封闭体积表示为：mi¼Xpð2ÞVXsV5ht2H通过确定仿射变换H来执行点到pi上的投影，该仿射变换H将pi对准xy平面坐标参考，即，Hpixy-plane.变换H应用于所有点p2Ci. 一旦我们得到点Hpp2Ci，我们去掉z坐标。接下来，我们对这些点应用2D Delaunay三角剖分（Fogel和Teillaud，2015）以获得局部连通性信息。最后，通过逆变换H-1将投影点重新投影回原始表面。这个过程产生了一组局部三角沿表面，图为M型多支管的端面。3 .第三章。在下一节中，我们将展示Eq。（5）可以优化评价M的傅里叶分析。4.傅立叶估值在本节中，我们将介绍如何计算对应于多重M的特征函数wM的傅立叶系数。这个函数是在整个空间上定义的;因此，w：R3！ f0; 1 g. W在M之外消失，使得：3.3. 符号和WP18个p2个MM0否则ð6Þ在这 一节中， 我们展 示如何使 用所得到 的局部三 角剖分集T<$fT;···;Tg来将流形M的封闭体积表示为四面体集H的和。实现WM的傅立叶系数被正式定义为：w^ Mu;v;wZZwx;y;ze-iuxvywzdxdydz7为了实现这个目标，我们必须确保沿着三角形的顶点的顺序gles是一致的;也就是说，对于任何两个相邻的三角形，共同的边必须有不同的方向，从而产生相应三角形法线的一致性M的四面体化是由于函数wMw^ Mu;v;wx;y;z≥2M在M之外消失，Eq. （7）成为：e-i uxv ywz dxdy dz8获得如下：1. 构造四面体的集合H。注意，积分算子是线性算子，从等式（5）和（8），我们得到：2. 求H内每个四面体的符号。w^ Mu;v;w^RRRx;y;z≥2M e-iuxvywzdxdy dz每个四面体ht2H是通过将这三个¼sðhtÞht2Hx;y;ze-iuxvywzdxdy dzð9Þ以坐标O为原点的三角形的顶点。给定任意三角形t p1;p2;p3T，ht的体积计算如下：1/4秒htw^ htt2Tu;v;wX1好的。Xy1z1y zð3Þ其中，w^ht=u;v;w是体积上的部分傅立叶系数的四面体HT。 在下一小节中，我们将数学基础（Kazhdan，2005年），以简化X3y3z3其中，xi;yi;zi表示点pi的几何形状。对于每个四面体ht，我们将四面体的符号s ht定义为：的系数的估计。我们从斯托克斯定理开始 从体积积分到曲面积分。4.1. Stokes在外微积分领域中，斯托克斯定理（Stokes这是一个关于固体上微分结构的积分的陈述这个定理将向量场通过曲面的流动与曲面内部张量场的行为联系起来（Katz，1979）。我们专注于一个特殊的情况称为发散定理或高斯定理。具体地说，发散定理指出，张量场通过闭曲面的向外通量等于表面内部区域的发散。具体地说，如果M<$R3是三维实体，并且F<$Fx;Fy;Fz：R3-！R3是一个向量场函数，该定理将体积积分表示为一个曲面，面积分如下：Zr·FpdvZhFp;~npida10M@M其中r·F 1/4。@Fx@Fy@Fz是F的梯度，~np是(c) Delaunay三角剖分和（d）到原始表面上的反投影点P处的曲面法线。2图3.第三章。（a）局部点集，（b）在平均切平面上的投影M.H. M.K.穆萨侯赛因/沙特国王大学学报1435ð Þ吉夫B1-羟丙基þÞC2W¼ ð Þ ¼ ð Þ ðÞ¼~n012¼-----吉夫茨我吉夫一2012年2月IW2002年2月2日一D4.2. 本地系数本节的目的是将w^htu;v;wt的积分简化为四面体ht边界上的曲面积分。如4.1节所述，我们考虑一个向量场函数，Fuvw<$x;y;z<$：R3-！R3，使得：虽然每个三角形的边界都包含三个角（这意味着三角形的边界不光滑），但斯托克斯定理的结论在h t的两侧上对上述积分的评估产生以下结果（Brandolini等人，1997; Li和Yuan，2009）：r·Fuvww^ht的体积积分 由方程式（9）可以用一个词来表示w^ ht u;v;w第一季度第二季度2016年第3季度面积分如下：w^ htu;v;wRRRx;y;z2hte-i uxv ywz dxdy dz其中，Vht是四面体的体积，参见等式并且Ql定义如下：我爱你我爱你R RR RieK¼RR@ht hFuvwp;~npidal kl klkk20···3其中，~np是在点p处的单位法线，tetrahedron，@t.为了完成w^的计算，我们搜索一个向量场，使用公式（16）和（17），我们可以计算傅里叶系数w^htu;v;w对于所有值u;v;w，非角系数除外htFuvw，其梯度满足等式（十一）、最直接和最简单的选择是如下设置Fuvw效率为0;0;0分。因此，计算的特征函数为偏移了这个非角度项的值。该移位值可以使用等式（（9）如下：0uFuvwx;y;zB@uuie-iuxvywz1我we-iuxvywzCe-i uxv ywzð13Þw^ M=0;0;0±1/4ZZZdx dy dz 18选择这些类型的矢量场的缺点是各向同性的损失（Kazhdan，2005），即，沿着不同的轴具有不同的物理性质换句话说，所产生的char-如Eqs所示。在公式（16）和（17）中，局部傅立叶系数的评估是完全独立的;因此，GPU线程上的并行化是直接的（参见算法2）。特征函数不是旋转不变的。为了克服这个问题，我们选择一个向量场，Fuvw，它与轴的变化无关。以下选择符合所需标准（Kazhdan，2005年）：算法2：计算全局傅立叶系数w^Mu;v;w.0u2Fuvwx;y;zB@u2u2尤埃尤 VY WZ2002年2月2日ive-iuxvywze-i uxv ywzð14Þ每个四面体ht由四条边和四个顶点组成：原点v 0<$O<$$>0;0;0<$p和三角形t;p1的三个顶点x1;y1;z1;p2x2;y2;z2和p3x3;y3;z3. 这四点足以计算四面体四边的法线123. 举例来说p0！p1×p0！p20！p1×p0！p2分系数w^ht被简化为以下细分：w^ htu;v;wZhF;~n012idaZhF;~n023idaZhF;~n031idahF;~n123ida15因此，可以通过计算四面体ht的四个边的子积分来获得w^htu;v;w。下面是斯托克斯定理的例子，即，链的Stokes定理1.（链的斯托克斯定理）如果c是光滑流形M中的光滑k-链，x是M上的光滑k - 1-形式，则5. 执行问题我们利用NVI-DIA的CUDA架构（NVIDIA，2019）对本文中提出的算法进行编码CUDA为GPU提供了一个最近的版本包含了一些对并行化有帮助的重要特性。例如，研究，允许从GPU主机代码的全内核DMA我们的GPUZ@c x¼Zc X执行广泛地利用这些新特征在本文中提到的所有计算中，被注释为“并行化”的部分x;y;z≥2M其等于网格的体积1436M.H. M.K.穆萨侯赛因/沙特国王大学学报’. ΣCPU托管。我们还指出了指定的GPU内核需要在我们的实验中，每个块包含1024个线程。对于kd树构造，级别i处所需的线程的数目最多为2i，因为可能存在不传播到下一级别的因此，我们建议，所需的块网格的尺寸是2i=1024。在我们的结果中，我们注意到kd树的深度最多为17。 对于傅立叶计算，所需线程的数量取决于局部三角形的总数#T。 因此，我们建议，所需的块的网格的尺寸是ΔT=1024。在运行时管理内存是CUDA实现中。事实上，CUDA--尤其是计算能力5.0特性--不支持主机和内核代码之间共享内存的动态内存管理。在傅立叶计算中，三角形的数量（计算的基础）在执行期间不会改变。因此，固定大小的数组被分配来存储三角形，局部体积和傅立叶系数.在构建kd树时会出现问题，因为所需的kd树单元的数量和每个单元中包含的点的数量是完全动态的。输入模型的几何形状在划分步骤中起着重要的作用。为了克服这个问题，我们在内核端创建了一个链表来存储单元信息。当需要更多的空间以最小化内存开销时，此链表的大小此外，我们将一个属性与每个顶点相关联，该属性存储对应单元格的句柄。在我们的实验中，这个链表的管理解决了动态内存分配问题，但它增加了空间内存的复杂性。6. 结果该算法在Intel Core i7 CPU@1.8 GHz和GeForce MX 130 4 GBGPU上进行了评估。我们的算法需要一个定向的点集作为输入。这些点可以很容易地通过采样三角模型或通过结合扫描范围图像。在计算傅立叶系数之后，应用逆变换以获得函数wM的近似。去侦察-见图4。（a）在不同带宽和相应细节级别下重建的霸王龙原始模型表面。表1显示了亲的主要步骤的时间摘要，摆姿势的技术第二列表示每个模型中的样本点每个模型都使用结构所需的表面，相应的等值面的必须提取特征函数wM。回想一下，对于包含在固体中的点，wM等于1，否则等于0在那里-因此，选择等于0：5的等值线，并且我们通过应用MC技术（Lewiner等人， 2003）到kd树的较低单元的角。结果是表示所需曲面连接的点列表和面列表该过程执行如下：1. 在单元角处评估等功能2. 然后在单元角上处理产生的点，并通过扫描获得索引。3. 对单元4. 将生成并存储点和面。图图4显示了不同带宽下霸王龙表面的重建。图3b表示样本点：每个点都有一个法线方向。该点集被划分为深度等于17和6505个节点的kd树每个节点满足等式中定义的条件s（一）. 整体局部三角剖分包含20万个三角形。图3f示出了表面在256、128、64和16的带宽下的面近似显然，采用的带宽越高，获得的表面细节越精细。kd树，如3.1节所述。第3列显示了使用我们的算法进行空间划分步骤所需的将该时间与使用计算几何算法库，CGAL（Fogel和Teillaud，2015），在第4列。如图所示，我们的方法的时间快了5~10倍。每个kd树的单元数量和深度仅取决于表面几何形状，这反过来又影响结果的数量。第五列中的三角形的数目。后续列中显示的带宽B显示了包含时序信息的三列：（我们的）所提出算法的运行时间，（CPU）Frigo等人（2005）提出的基于CPU的FFTW算法的运行时间和（GPU）CUDA工具包（NVIDIA，2019）提出的基于GPU的FFTW算法的运行时间。 对于FFTW算法，Frigo et al. （2005）和NVIDIA（2019），我们添加体素化预处理时间因为算法需要等距的体素网格， B3.事实上，为模型内部的每个体素分配值1（否则为0）是一个非常耗时的过程。相比之下，我们的计算直接在同一组三角形上进行。因此，不需要获得具有与所需带宽相同尺寸的体素网格（Frigo等人，2005年;NVIDIA，2019年）。因此，更高带宽的计算有益于M.H. M.K.穆萨侯赛因/沙特国王大学学报1437¼表1使用所提出的算法对不同大小的模型进行空间划分过程和傅立叶系数评估的时间摘要（以秒为单位），使用CGAL（Fogel和Teillaud，2015）的kd树的CPU实现的相应时序，以及Frigo等人提出的FFTW的CPU和GPU实现。（2005）和NVIDIA，2019年，分别包括体素化预处理时间。模型#Pkd树#TB¼16B¼64B¼128B¼256我们CGAL我们CPUGPU我们CPUGPU我们CPUGPU我们CPUGPU犰狳950 k0.3512.3691.9米0.1105.405.052.459.35.918.9018.314.933.566.640.0Tyra100 K0.0550.371200 K0.0150.550.500.310.940.611.101.851.504.206.504.10兔子37 k0.0220.15070 K0.0060.200.140.100.340.220.390.680.551.332.461.48金星25 K0.0160.10850 K0.0040.160.120.080.230.150.300.460.371.101.660.90骨头18 K0.0130.08937 k0.0030.100.090.070.170.110.240.330.270.891.210.72从先前带宽的计算中。图6显示了表1中所示模型的一些额外结果。为了评估我们的表面重建进展的影响，我们检查了使用所提出的技术与基于体素化的技术（Kazhdan，2005）产生的表面的可视化质量这两种技术都接受一组定向点作为输入，并产生一个水密表面作为输出。图5显示了我们的技术和Kazhdan（2005）在B128的Armadillo模型上的比较。放大的-在该地区的模型的头部Kazhdan（2005年）。除了表面重建之外，傅立叶计算使我们能够将该技术应用于许多应用，例如（但不限于）渐进传输。回想一下，低阶系数表示模型的整体形状，而高阶系数表示更精细的细节。因此，可以用较低的系数来传输模型以表示整体形状，并且如果需要的话，可以稍后传输较高的系数以实现更精细的细节，参见图12。7.第一次会议。7.结论和今后的工作在本文中，我们介绍了一种方法，执行表面重建从一组定向点。我们的方法遵循隐式表面重建框架。我们通过对输入的基于点的表面进行傅立叶分析来实现我们的我们的方法图六、表面重建的斯坦福兔，金星头和快乐的佛像模型。图五.使用（a）基于体素的技术（Kazhdan，2005）和（b）我们的技术在B¼在两个方面不同于使用基于频率的分析的传统方法（1）直接在表面点上进行分析;不需要先前的表面体素化;（2）傅立叶系数计算直接在GPU线程上执行，这减少了处理的总时间成本。此外，所提出的方法是简单和有效的。1438M.H. M.K.穆萨侯赛因/沙特国王大学学报图7.第一次会议。渐进式传播。从左到右：高阶系数相加以获得具有更精细细节的模型。虽然傅立叶变换通常具有良好的性能进行矩形域上的计算，其他trans-forms可能会执行更好的特定模型类型。例如，0-亏格模型使用球体作为自然参数化域，使得球谐变换成为这种情况下的最佳选择。然而，直接计算它的数学公式仍然是我们目前正在研究的一个具有挑战性的问题。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。引用Amenta，Nina，Choi，Sunghee，Kolluri，Ravi Krishna，2001.权力外壳在：第六届ACM实体建模和应用研讨会论文集，SMA '01。ACM，New York，NY，USA，pp.249-266。Arbter，K.，斯奈德，W. E.，Burkhardt，H.，Hirzinger，G.，1990.仿射不变傅立叶描述子在三维物体识别中的应用。IEEE传输模式分析马赫内特尔12（7），640-647。Berger ， Matthew ， Tagliasacchi ， Andrea ， Seversky ， Lee M. ， Alliez， Pierre ，Guennebaud，Gael，Levine，Joshua A.，Sharf，Andrei，Silva，Claudio T.，2017年。 基于点云数据的曲面重构研究综述。 计算机图形论坛36（1），301-329。Boissonnat ， J.D. ， Daniel ， Jean ， 1984. 三 维 形 状 表 示 的 几 何 结 构 。 ACM Trans.Graphics 3（4），266-286.Boubekeur，T.，路透社，P.，Schlick，C.，2005.基于局部重构细分曲面的点基曲面可视化。形状建模国际Brandolini，Luca，Colzani，Leonardo，Travaglini，Giancarlo，1997. 傅立叶变换的平均衰减与多面体中的整数点。 Arkiv for Matematik 35（2），253-275.Cazals，Frédéric，Giesen，Joachim，2006.基于Delaunay三角剖分的曲面重构。Springer，Berlin Heidelberg，Berlin，Heidelberg，第231-276页。Dey，TamalK.，2011年。 曲线和曲面重建：算法与数学分析。剑桥大学出版社，纽约，美国。Dey，Tamal K.，Goswami，Samrat，2003年。一种防水的表面重建器。第八届ACM实体建模与应用研讨会论文集，SM '03。ACM，New York，NY，USA，pp. 127比134Duan，Ye，Qin，Hong，2004.一种基于细分的可变形模型用于未知拓扑曲面重构。Graph. 模型66（4），181-202。Fogel，Efi，Teillaud，Monique，2015. 计算几何算法库。ACM通信Comput.代数49（1），10-12。弗里戈，M.，Johnson，S.G.，2005年fftw3的设计与实现Proc. IEEE 93（2），216-231。Hussein，M. K.，穆萨，M.- H、2015.云环境下的高性能三维物体重建。国际计算机通信创新研究杂志。Eng.3（6），5338-5346。Katz，Victor J.，1979.斯托克斯定理的历史。Math.Mag.52（3），146. Kazhdan，Michael，2005. 从有向点集重建实体模型SGP'05 Proceedings of the third Eurographics symposium on Geometry ，Vienna，Austria.欧洲制图协会。Kazhdan，M.，霍普，H.，2013年。筛选泊松曲面重建。译第32章（三）Kazhdan，M.，Bolitho，M.，霍普，H.，2006. Poisson曲面重建Symp.几何过程。Kopcke，Bastian，Steuwer，Michel，Gorlatch，Sergei，2019。用lift生成高效的fftgpu代码。在：第八届ACM SIGPLAN功能高性能和数值计算国际研讨会论文集，FHPNC 2019。计算机协会，纽约，纽约，美国，pp。1-13号。Lee，John M. ，2003.光滑流形简介。数学研究生教材，卷。218. Springer ，NewYork，NY.Lewiner，Thomas，Lopes，Helio，Wilson Vieira，Antonio，Tavares，Geovan，2003. 具有拓扑保证的移动立方体的有效实现。J. Graphics Tools 8（2），1李慧媛，袁旭，2009.十二面体和四面体上的离散傅立叶分析。数学。计算。78，999-1029。Maurya，S.R.，Magar，G.M.，2018年 贪婪三角剖分算法在海岸沙丘表面重建中的性能。国际技术融合会议（I2CT），pp。 1比6NVIDIA。Cuda工具包文档10.2. 2019. https://docs.nvidia.com/cuda/. NVIDIA。快速傅立叶变换库。2019年。https：//developer.nvidia.com/cufft.Ohtake，Yutaka，Belyaev，Alexander，Alexa，Marc，Turk，Greg，Seidel，Hans-Peter，2003. 多层次的单位分解。ACM Trans.Graph. 22（3），463四百七十Terzopoulos，D.，Vasilescu，M.，1991.使用自适应网格进行采样和重建。In：Proceedings. 1991年IEEE计算机协会计算机视觉和模式识别会议，pp。 70比75徐永阳，谢忠陈占龙梁吴2017.基于位置图和傅立叶描述子的带孔多边形形状相似性度量模型。国际地理学杂志。告知。Sci. 31（2），253-279。Zhou，Kun，Hou，Qiming，Wang，Rui，Guo，Baining，2008.图形硬件上kd树的实时构造。ACM事务处理图表27（5），1-11。Zhou，K.，（1991年），龚，M.，黄，X.，Guo，B.，2011.用于曲面重建的数据并行八叉树。IEEE Trans.视觉计算 Graphics 17（5），669-681.