CN119206055B - 一种从显式几何到隐式几何的快速转换方法及系统 - Google Patents

Abstract

本发明涉及一种从显式几何到隐式几何的快速转换方法及系统，其方法包括对输入的三角形网格构建线性边界体层次结构，并构建八叉树结构；利用八叉树结构的节点作为采样点，对每个采样点并行化计算自适应网格无符号距离场；利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号；根据自适应网格无符号距离场和自适应网格无符号距离场的符号确定符号距离场的数据，完成隐式几何到显式几何的转换。本发明可快速实现隐式几何到显式几何的转换，在保持高精度的同时大幅提高转换效率的方法，可提升图形处理、物理模拟以及应用场景的性能。

Description

一种从显式几何到隐式几何的快速转换方法及系统

技术领域

本发明涉及计算机辅助设计技术领域，尤其涉及一种从显式几何到隐式几何的快速转换方法及系统。

背景技术

在计算机辅助设计(CAD)、计算机图形学等领域，几何模型的表示与处理是核心方法之一。几何模型通常分为两类：显式几何和隐式几何。显式几何(如STL、OBJ格式)通常通过顶点、边、面等数据结构直接表示物体的表面信息，广泛应用于三维建模、渲染和制造等领域。隐式几何则通过函数(如符号距离场，Signed Distance Field,SDF)间接表示物体的表面，通过判断空间点到物体表面的距离来定义几何形状。隐式几何在碰撞检测、物理模拟、和形状优化等领域具有独特优势。

显式几何的优点在于其表示的直观性和易于编辑，但在一些复杂的几何操作和分析中(例如布尔运算、碰撞检测和物理模拟)，显式几何的计算效率较低。相比之下，隐式几何由于其连续性和解析性，在这些应用中表现出更高的计算效率和灵活性。然而，显式几何和隐式几何的转换过程通常计算复杂且耗时，特别是在处理复杂场景或大规模几何数据时，这种转换往往成为整个工作流程中的瓶颈。

目前，已有多种方法尝试解决显式几何到隐式几何的高效转换问题。如基于神经网络的隐式表示方法、基于维诺图表的方法等。尽管如此，这些方法在处理效率和精度上仍然存在改进空间，特别是在大规模或实时应用中，仍然需要进一步优化。

因此，开发一种能够快速将显式几何模型转换为隐式几何模型的方法，尤其是在保持高精度的同时大幅提高转换效率的方法，对于提升图形处理、物理模拟以及相关领域的整体性能具有重要意义。这种方法的实现将为多个工业和研究领域提供强大的工具，有助于推动相关方法的发展和应用。

发明内容

本发明所要解决的技术问题是针对上述现有技术的不足，提供一种从显式几何到隐式几何的快速转换方法及系统。

本发明解决上述技术问题的技术方案如下：一种从显式几何到隐式几何的快速转换方法，包括如下步骤：

对输入的三角形网格构建线性边界体层次结构，并基于所述线性边界体层次结构构建八叉树结构；

利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场；

利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号；

根据自适应网格无符号距离场和自适应网格无符号距离场的符号确定符号距离场的数据，完成隐式几何到显式几何的转换。

本发明的有益效果是：本发明的从显式几何到隐式几何的快速转换方法，通过对三角形网格构建线性边界体层次结构和八叉树结构，并基于所述八叉树结构的节点计算自适应网格无符号距离场，再结合三角形网格的伪法线确定无符号距离场的符号，最终确定符号距离场的数据，完成隐式几何到显式几何的转换，在保持高精度的同时大幅提高转换效率的方法，可提升图形处理、物理模拟以及应用场景的性能。

在上述技术方案的基础上，本发明还可以做如下改进：

进一步：所述对输入的三角形网格构建线性边界体层次结构具体包括如下步骤：

以三角形网格的每一三角形面片质心坐标作为初始数据，利用魔法位方法，将以32位二进制整数表征三角形面片的质心位置坐标交织成以64位二进制整数表征的第一莫顿码，并针对每一个三角形面片计算其轴对齐包围盒；

对所述三角形面片的质心位置的第一莫顿码按照大小顺序进行排序，利用并行化算法确定每个所述第一莫顿码对应的三角形面片的划分位置，并按照预设的分类方法将三角形面片的划分节点分成的叶节点和内部节点存储至两个不同的独立数组中，得到第一二叉基数树；

按照一一对应的关系为每个所述第一二叉基数树分配对应的所述轴对齐包围盒，并对所述第一二叉基数树的叶节点到根节点的路径进行并行处理，使得每一个所述第一二叉基数树的内部节点和叶节点均匹配对应的所述轴对齐包围盒，得到线性边界体层次结构。

上述进一步方案的有益效果是：通过将所述三角形面片的质心位置坐标转换成64位的第一莫顿码，这样可以方便确定对应三角形面片的划分位置，从而构建出第一二叉基数树，然后对所述第一二叉基数树分配对应的所述轴对齐包围盒，完成线性边界体层次结构的构建。

进一步：所述预设的分类方法为：

针对每个三角形面片，比较其左右两个三角形面片的第一莫顿码的共同前缀长度，并确定划分方向和划分节点；

将所有以所述第一莫顿码表示的三角形面片作为叶节点，基于所述叶节点确定划分位置，并根据所述叶节点是否处于所述划分节点的位置判断所述划分节点是否为内部节点。

上述进一步方案的有益效果是：通过左右两个三角形面片的第一莫顿码的共同前缀长度可以精确找到划分方向和划分节点，然后根据该所述三角形面片是否处于所述划分节点的位置判断所述划分节点是否位内部节点，从而完成对叶节点和内部节点的划分，方便后续构建八叉树结构和无符号距离场。

进一步：所述基于所述线性边界体层次结构构建八叉树结构具体包括如下步骤：

给定八叉树的划分层次，将所述三角形网格的包围空间按照所述八叉树的划分层次均匀划分为与体素数据一一对应的三维网格，并利用所述体素数据构建第二二叉基数树；

基于所述第二二叉基数树确定对应的第二莫顿码，利用所述第二莫顿码确定所述八叉树的所有层级节点，并为所有所述层级节点分配内存，存储所述八叉树的层级节点信息；

基于设定的父子节点关系，采用并行化处理方法确定每个层级节点的父子节点，并得到八叉树结构；

其中，所述父子节点关系为所述八叉树的任意两个内部节点之间的共同前缀长能够被三整除，且二者的共同前缀长除以三后的差值为一。

上述进一步方案的有益效果是：通过给定的八叉树划分层次对三角形网格的包围空间均匀划分，既可以得到与体素数据一一对应的三维网格，从而可以实现第二二叉基数树的构建，这样即可根据由二叉基数树确定的第二莫顿码确定所述八叉树的所有层级节点，从而确定层级节点的父子节点，并得到八叉树结构。

进一步：所述利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场具体包括如下步骤：

计算所述八叉树结构的所有节点所处位置的第二莫顿码，并剔除重复的莫顿码，将互不相同的所述第二莫顿码对应的八叉树结构的节点作为采样点p；

确定所述采样点p在最近的所述三角形面片上的投影点x的位置，基于R－TREE的空间缩减方法计算采样点p到最近的所述三角形面片的距离；

自上而下遍历所述线性边界体层次结构，并将所述线性边界体层次结构的所有节点逐一存储至堆栈S中；

针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为内部节点，则计算该节点到轴对齐包围盒的最小距离和最小最大距离，并进行最小边界框剪枝处理，通时将新增的内部节点存储至堆栈S中，直至所述堆栈S中所有节点均被处理完成；

针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为叶节点，则计算该采样点到叶节点代表的三角形面片的距离，并将所有的距离中的最小值作为采样点到三角形网格的最小距离，完成无符号距离场的构建。

上述进一步方案的有益效果是：通过剔除重复的第二莫顿码，这样可以大大提高计算效率，通过根据采样点p在最近的所述三角形面片上的投影点x的位置可以精确计算出采样点p到最近的所述三角形面片的距离，然后基于线性边界体层次结构的节点的左子节点或右子节点的是否为内部节点来进行最小边界框剪枝处理，最后针对左子节点或右子节点为叶节点的节点，其到计算该采样点到叶节点代表的三角形面片的距离，再确定最小距离，即可完成无符号距离场的构建。

进一步：利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号具体包括如下步骤：

根据所述采样点p在最近的所述三角形面片上的投影点x的位置确定三角形网格的伪法线，具体包括：当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片内时，则根据所述采样点p和投影点x确定三角形片面的法线，当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片的边上时，定义面i和j之间的边分别具有法线n_i和n_j，则三角形面片边的伪法线n_edge＝π·n_i+π·n_j，当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片的顶点上时，三角形面片顶点的伪法线为n_vertice＝∑a_in_i，其中，a_i为第i个面对应的顶角的角度值；

基于所有三角形面片的伪法线确定三角形网格的伪法线，并根据三角形网格的伪法线确定采样点p的投影点x到查询点p的方向向量r＝p－x，并根据方向向量r与投影点x处的法线或伪法线的点积确定查询点p的符号。

上述进一步方案的有益效果是：通过采样点p在最近的所述三角形面片上的投影点x的位置可以准确计算出三角形片面的伪法线，然后得到整个三角形网格的伪法线，从而可以准确得到无符号距离场的符号。

进一步：所述的从显式几何到隐式几何的快速转换方法还包括如下步骤：

将符号距离场的数据储存在vtk非结构化网格中，抽取其等值面，完成隐式几何的可视化。

上述进一步方案的有益效果是：通过将符号距离场的数据储存在vtk非结构化网格中，可以方便将符号距离场的数据映射到可视化图形数据结构中，实现隐式几何的可视化。

进一步：所述将符号距离场的数据储存在vtk非结构化网格中，抽取其等值面具体包括如下步骤：

初始化vtk非结构化网络，并将所述八叉树结构数据中点坐标添加到vtk非结构化网络中，根据所述八叉树结构的数据类型创建六面体单元，并将所述六面体单元添加至vtk非结构化网络中；

将所述符号距离场的数据以点数据的形式写入vtk非结构化网格中；

初始化等值面值，并获取符号距离场的表面轮廓，通过vtk非结构化网络中的等值面过滤器模块对符号距离场进行等值面提取，并映射到可视化图形数据结构中。

上述进一步方案的有益效果是：通过将所述符号距离场的数据以点数据的形式写入vtk非结构化网格中，这样方便进行等值面提取，并映射到可视化图形数据结构中，实现隐式几何的可视化。

本发明还提供了一种从显式几何到隐式几何的快速转换系统，包括构建模块、第一计算模块、第二计算模块和转换模块：

所述构建模块，用于对输入的三角形网格构建线性边界体层次结构，并基于所述线性边界体层次结构构建八叉树结构；

所述第一计算模块，用于利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场；

所述第二计算模块，用于利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号；

所述转换模块，用于根据自适应网格无符号距离场和自适应网格无符号距离场的符号确定符号距离场的数据，完成隐式几何到显式几何的转换。

本发明还提供了一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，实现所述的从显式几何到隐式几何的快速转换方法。

附图说明

图1为本发明一实施例的从显式几何到隐式几何的快速转换方法的流程示意图；

图2为本发明一实施例的八叉树结构的示意图；

图3为本发明一实施例的三角形面片划分的区域图解示意图；

图4为本发明一实施例的不同维度下的隐式几何示意图；

图5为本发明一实施例的初始的隐式几何和转换后的隐式几何示意图；

图6为本发明一实施例的从显式几何到隐式几何的快速转换系统的结构示意图。

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本发明，并非用于限定本发明的范围。

如图1所示，本发明提供一种从显式几何到隐式几何的快速转换方法，在NVIDIAGeForceRTX4080laptop上实现了该算法的构造，(gpu参数为：7424个CUDA核心，12GBGDDR6显存，显存位宽192bit，核心频率1510MHz，显存频率2250MHz，加速频率1930MHz，cpu参数为：Windows11Ultimate64bits/IntelI9CPU＠2.3GHz/32GRAM)。本文使用VisualStudio2019，CUDA12.0工具包来实现该算法的开发，使用thrust库实现gpu排序、规约等基础算法的使用，并使用vtk库实现符号距离场的等值面的抽取，包括以下步骤：

S1：对输入的三角形网格构建线性边界体层次结构，并基于所述线性边界体层次结构构建八叉树结构；

S2：利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场；

S3：利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号；

S4：根据自适应网格无符号距离场和自适应网格无符号距离场的符号确定符号距离场的数据，完成隐式几何到显式几何的转换。

本发明的从显式几何到隐式几何的快速转换方法，通过对三角形网格构建线性边界体层次结构和八叉树结构，并基于所述八叉树结构的节点计算自适应网格无符号距离场，再结合三角形网格的伪法线确定无符号距离场的符号，最终确定符号距离场的数据，完成隐式几何到显式几何的转换，在保持高精度的同时大幅提高转换效率的方法，可提升图形处理、物理模拟以及应用场景的性能。

在本发明的一个或多个实施例中，所述对输入的三角形网格构建线性边界体层次结构具体包括如下步骤：

S11：以三角形网格的每一三角形面片质心坐标作为初始数据，利用魔法位方法，将以32位二进制整数表征三角形面片的质心位置坐标交织成以64位二进制整数表征的第一莫顿码，并针对每一个三角形面片计算其轴对齐包围盒；

本发明的实施例中，以stanfordbunny.stl文件作为显式几何输入源，该模型有112402个三角形面片，编写一个读取stl文件的程序，读取三角形网格数据，并将其储存在cpu端创建的内存中，随后将其拷贝至gpu端以供后续的并行化计算。随后，运用“魔法位”方法，将以32位二进制整数表示的三角形面片的质心位置坐标，按照z，y，x的先后顺序交织成64位二进制整数表示的第一莫顿码。

S12：对所述三角形面片的质心位置的第一莫顿码按照大小顺序进行排序，利用并行化算法确定每个所述第一莫顿码对应的三角形面片的划分位置，并按照预设的分类方法将三角形面片的划分节点分成的叶节点和内部节点存储至两个不同的独立数组中，得到第一二叉基数树；

为了构建线性边界体层次结构，本发明采用了并行化构建二叉基数树的算法，首先对先前生成的第一莫顿码按照大小顺序排序，因为第一莫顿码的空间特性，通过对第一莫顿码进行排序使得相近的莫顿码代表的三角形面片在空间中位置也是相近的。

具体地，在本发明的一个或多个实施例中，所述预设的分类方法为：

S121：针对每个三角形面片，比较其左右两个三角形面片的第一莫顿码的共同前缀长度，并确定划分方向和划分节点；

S122：将所有以第一莫顿码表示的三角形面片作为叶节点，基于所述叶节点确定划分位置，并根据所述叶节点是否处于所述划分节点γ的位置判断所述划分节点是否为内部节点。

这里，识别出内部节点和叶节点后，将内部节点和叶节点分别储存在两的独立的数组之中，记为I和L，叶节点的排列顺序按叶节点的初始顺序排列，即第一莫顿码的按大小排列的顺序，而内部节点的排列顺序则能够通过简单定义节点布局，使得内部节点的根节点位于数组I的第一个位置I₀，任何内部节点的子节点在数组I内的索引都根据其各自的划分位置进行分配。具体而言，如果其左侧子节点覆盖多个叶节点(该节点为内部节点)，则需将该左子节点储存在I_γ，如果该左侧子节点是叶节点(该节点不是内部节点)，则需将该左子节点储存在L_γ。类似地，右子节点需储存在I_γ+1或L_γ+1。凭借这种节点布局，能够通过找到适当的分割位置来识别子节点，从而完成二叉基数树的构建。

S13：按照一一对应的关系为每个所述第一二叉基数树分配对应的所述轴对齐包围盒，并对所述第一二叉基数树的叶节点到根节点的路径进行并行处理，使得每一个所述第一二叉基数树的内部节点和叶节点均匹配对应的所述轴对齐包围盒，得到线性边界体层次结构。

由于第一二叉基数树的结构与对应的线性边界体层次结构是相同的，因此在计算得到每一三角形面片的轴对齐包围盒后，按照一一对应的关系为每个第一二叉基数树的叶节点分配其对应的轴对齐包围盒，随后从叶节点到根节点的路径并行处理使得每一个第一二叉基数树的内部节点也分配好对应的轴对齐包围盒。每个线程从一个叶节点开始，通过在基数树构建过程中记录的父指针向上遍历树。

需要指出的是，本发明的实施例中，使用原子计数器跟踪有多少线程访问了每个内部节点，随后当第一个线程完成处理后，第一个线程立即终止，而第二个线程则继续处理节点。最后为二叉基数树内部节点分配对应的轴对齐包围盒，最终实现线性边界体层次结构的构建。

在本发明的一个或多个实施例中，所述基于所述线性边界体层次结构构建八叉树结构具体包括如下步骤：

S14：给定八叉树的划分层次，将所述三角形网格的包围空间按照所述八叉树的划分层次均匀划分为与体素数据一一对应的三维网格，并利用所述体素数据构建第二二叉基数树；

在本发明的实施例中，由于在不改变分辨率的情况下，减少采样点能够显著提高计算效率，因此使用八叉树结构的节点作为采样点，为实现构建输入网格的八叉树结构，首先设置一个给定的八叉树划分层次，在本案例中设置为10，即八叉树结构的维度为512x512x512，随后使用并行化的三角形网格体素化方法得到八叉树的给定层次的所有节点，具体而言是在每个线程中，将整个三角形网格的包围空间按预设划分层次划分为均匀的三维网格，每个网格单元对应一个体素，每个线程独立处理一个体素，检查每个三角形面片是否与当前体素相交，并记录相交信息，随后复用二叉基数树构建方法为体素数据构建二叉基数树。

S15：基于所述第二二叉基数树确定对应的第二莫顿码，利用所述第二莫顿码确定所述八叉树的所有层级节点，并为所有所述层级节点分配内存，存储所述八叉树的层级节点信息；

随后在构建好体素数据的第二二叉基数树后，利用第二莫顿码的特性找到八叉树结构的所有层级节点，假设给定第二莫顿码的每个3k位前缀直接映射到k级的八叉树节点。

S16：基于设定的父子节点关系，采用并行化处理方法确定每个层级节点的父子节点，并得到八叉树结构；

其中，所述父子节点关系为所述八叉树的任意两个内部节点之间的共同前缀长能够被三整除，且二者的共同前缀长除以三后的差值为一。

具体地，在体素数据的二叉基数树上，如果某一节点的共同前缀长δ是三的倍数，则表示该节点是八叉树的内部节点，例如如果某一节点的共同前缀长δ＝0，则该节点是八叉树中的根节点，同理若某一节点的共同前缀长δ＝3，则该节点是八叉树中根节点的某一个子节点，因此对于共同前缀长为δ_parent的父节点，和共同前缀长度为δ_children的子节点，如果 能够被三整除，则在该子节点和父节点之间能够生成一个八叉树节点。

实际中，首先为每个线程设置一个计数器并初始化为零，找到每个线程找到的八叉树节点数目，然后执行设定算法找到来找到所有层级的八叉树节点的数目并为其分配内存，随后计算并储存八叉树节点信息，并且由于第二莫顿码的特性，若两个内部节点间的共同前缀长能够被三整除，且二者的共同前缀长除三后的差值为一，则表明这两个节点之间存在父子节点关系，基于上述关系采用并行化的策略，为每个节点找到父子节点关系，最终完成八叉树的构建，如图2所示，2(a)、2(b)和2(c)分别为前视角、俯视角和侧视角的八叉树结构的示意图。

在本发明的一个或多个实施例中，所述利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场具体包括如下步骤：

S21：计算所述八叉树结构的所有节点所处位置的第三莫顿码，并剔除重复的莫顿码，将互不相同的所述第三莫顿码对应的八叉树结构的节点作为采样点p；

这里，使用前文构建的八叉树结构的网格节点作为采样点。然而，由于相邻的八叉树结构的节点之间共享网格点，这些查询中存在大量的重复计算。具体来说，每个八叉树结构的节点需要对其八个角点分别进行查询，但由于这些角点通常被多个八叉树结构的节点共享，大部分查询实际上是重复的。为了避免这种情况，本发明的实施例中，为每个角点根据其所处位置计算莫顿码，通过使用第三莫顿码，确保每个角点只进行一次查询，提升了整体计算的效率。

S22：确定所述采样点p在最近的所述三角形面片上的投影点x的位置，基于R－TREE的空间缩减方法计算采样点p到最近的所述三角形面片的距离；

在本发明的实施例中，为计算采样点p到三角形网格的最小距离，需要计算采样点p到最近的三角形面片的最小距离，而计算采样点p到最近的三角形面片的距离首先需要判断采样点p的投影点x是落在是在边上、顶点上还是在三角形面片内。原因是在三种不同的情况下，应该分别计算采样点p到线、点或平面的距离。当采用点p投影到三角形面片内时，根据投影点x的位置能够将三角形面片划分为7个区域之一，如图3所示。如果投影点x位于R1区域上，那么点到三角形的面片最近距离等于点到三角形平面的距离。如果投影点x位于R2、R3或R4区域中，则应该计算到相应线的距离，对于区域R5、R6或R7，应该计算到相应顶点的距离。另外，由于后续需要使用角权重伪法线算法计算距离场的符号，所以在计算点到三角形面片距离的过程中需要记录点投影的区域。

在计算点到三角形网格的最小距离时，使用基于R－TREE的空间缩减方法方法加速这一过程，为了使用该方法首先需了解最小距离和最小最大距离的概念。最小距离(MinDist)是查询点与包围盒内某个空间对象之间距离的下限或乐观估计。然而，查询点与最近对象之间的实际最小距离可能要比最小距离大，因此需要使用最小最大距离(MinMaxDist)作为第二个度量，它提供了实际对象与查询点之间距离的上限。换句话说，最小最大距离提供了查询点与包围盒中的某个空间对象之间距离的保守估计，即在一组最大距离中找到最小距离。在构建好查询点到包围盒的最小距离和最小最大距离之后，本发明的剪枝策略为如果采样点到A包围盒的最小最大距离小于采样点到B包围盒的最小距离，则查询点到B包围盒中的空间对象的距离必然不是最小距离，因此，B包围盒内的空间对象均不需计算，即可直接对其进行剪枝。因此，利用该基于R－TREE的空间缩减方法进行最小距离计算能够减少需要计算的三角形面片数目能够加快计算效率。

S23：自上而下遍历所述线性边界体层次结构，并将所述线性边界体层次结构的所有节点逐一存储至堆栈S中；

这里，每次存入一个根节点，随后再根据是否符合剪枝条件，根据节点的父子关系，依次存入需要处理的节点直至所有节点全部被处理完。

S24：针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为内部节点，则计算该节点到轴对齐包围盒的最小距离和最小最大距离，并进行最小边界框剪枝处理，通时将新增的内部节点存储至堆栈S中，直至所述堆栈S中所有节点均被处理完成；

S25：针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为叶节点，则计算该采样点到叶节点代表的三角形面片的距离，并将所有的距离中的最小值作为采样点到三角形网格的最小距离，完成无符号距离场的构建。

在本发明的一个或多个实施例中，利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号具体包括如下步骤：

S31：根据所述采样点p在最近的所述三角形面片上的投影点x的位置确定三角形网格的伪法线；

具体地，当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片内时，则根据所述采样点p和投影点x确定三角形片面的法线；

当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片的边上时，定义面i和j之间的边分别具有法线n_i和n_j，则三角形面片边的伪法线n_edge＝π·n_i+π·n_j，当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片的顶点上时，三角形面片顶点的伪法线为n_vertice＝∑a_in_i，其中，a_i为第i个面对应的顶角的角度值；

S32：基于所有三角形网格的伪法线确定三角形网格的伪法线，并根据三角形网格的伪法线确定采样点p的投影点x到查询点p的方向向量r＝p－x，并根据方向向量r与投影点x处的法线或伪法线的点积确定查询点p的符号。

通过采样点p在最近的所述三角形面片上的投影点x的位置可以准确计算出三角形片面的伪法线，然后得到整个三角形网格的伪法线，从而可以准确得到无符号距离场的符号。

可选地，在本发明的一个或多个实施例中，所述的从显式几何到隐式几何的快速转换方法还包括如下步骤：

S5：将符号距离场的数据储存在vtk非结构化网格中，抽取其等值面，完成隐式几何的可视化。

通过将符号距离场的数据储存在vtk非结构化网格中，可以方便将符号距离场的数据映射到可视化图形数据结构中，实现隐式几何的可视化。

在本发明的一个或多个实施例中，所述将符号距离场的数据储存在vtk非结构化网格中，抽取其等值面具体包括如下步骤：

S51：初始化vtk非结构化网络，并将所述八叉树结构数据中点坐标添加到vtk非结构化网络中，根据所述八叉树结构的数据类型创建六面体单元，并将所述六面体单元添加至vtk非结构化网络中；

S52：将所述符号距离场的数据以点数据的形式写入vtk非结构化网格中；

S53：初始化等值面值，并获取符号距离场的表面轮廓，通过vtk非结构化网络中的等值面过滤器模块对符号距离场进行等值面提取，并映射到可视化图形数据结构中。

这里，初始化等值面值为零，映射到可视化图形数据结构中之后，通过vtk渲染模块的配合，将生成的等值面呈现出来，实现符号距离场的三维可视化。此过程能够动态调整视角和等值面参数，以便更好地分析和展示几何特征，实现隐式几何的可视化，如图4和5所示，其中，图4中(4a)为网格维度为128＊128＊128下，时间为153.3ms时的隐式几何示意图，图4中(4b)为网格维度为256＊256＊256下，时间为243.3ms时的隐式几何示意图，图4中(4c)为网格维度为512＊512＊512下，时间为560.2ms时的隐式几何示意图。图5中(5a)为初始的显式几何示意图，图5中(5b)为转换后的显式几何示意图。可以看出，本发明的方法转换前后图像几乎没有失真，在保持高精度的同时大幅提高转换效率。

需要特别指出的是，隐式几何的可视化完成后，还可以将提取的等值面数据设置为写入器的输入源。根据需要，使用VTK中的vtkSTLWriter模块，将提取的等值面数据导出为STL格式。这一过程能够将隐式几何转化为显式几何，从而在隐式建模完成后实现模型的构建和保存。通过这种转换，能够为隐式几何和显式几何之间建立连接的桥梁，方便后续的应用和分析。

如图6所示，本发明还提供了一种从显式几何到隐式几何的快速转换系统，包括构建模块、第一计算模块、第二计算模块和转换模块：

所述构建模块，用于对输入的三角形网格构建线性边界体层次结构，并基于所述线性边界体层次结构构建八叉树结构；

所述第一计算模块，用于利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场；

所述第二计算模块，用于利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号；

所述转换模块，用于根据自适应网格无符号距离场和自适应网格无符号距离场的符号确定符号距离场的数据，完成隐式几何的可视化及到显式几何的转换。

本发明还提供了一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，实现所述的从显式几何到隐式几何的快速转换方法。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (9)

1.一种从显式几何到隐式几何的快速转换方法，其特征在于，包括如下步骤：

对输入的三角形网格构建线性边界体层次结构，并基于所述线性边界体层次结构构建八叉树结构；

利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场；

利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号；

根据自适应网格无符号距离场和自适应网格无符号距离场的符号确定符号距离场的数据，完成隐式几何到显式几何的转换；

所述利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场具体包括如下步骤：

计算所述八叉树结构的所有节点所处位置的第三莫顿码，并剔除重复的莫顿码，将互不相同的所述第三莫顿码对应的八叉树结构的节点作为采样点p；

确定所述采样点p在最近的三角形面片上的投影点x的位置，基于R－TREE的空间缩减方法计算采样点p到最近的所述三角形面片的距离；

自上而下遍历所述线性边界体层次结构，并将所述线性边界体层次结构的所有节点逐一存储至堆栈S中；

针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为内部节点，则计算该节点到轴对齐包围盒的最小距离和最小最大距离，并进行最小边界框剪枝处理，通时将新增的内部节点存储至堆栈S中，直至所述堆栈S中所有节点均被处理完成；

针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为叶节点，则计算该采样点到叶节点代表的三角形面片的距离，并将所有的距离中的最小值作为采样点到三角形网格的最小距离，完成无符号距离场的构建。

2.根据权利要求1所述的从显式几何到隐式几何的快速转换方法，其特征在于，所述对输入的三角形网格构建线性边界体层次结构具体包括如下步骤：

以三角形网格的每一三角形面片质心坐标作为初始数据，利用魔法位方法，将以32位二进制整数表征三角形面片的质心位置坐标交织成以64位二进制整数表征的第一莫顿码，并针对每一个三角形面片计算其轴对齐包围盒；

对所述三角形面片的质心位置的第一莫顿码按照大小顺序进行排序，利用并行化算法确定每个所述第一莫顿码对应的三角形面片的划分位置，并按照预设的分类方法将三角形面片的划分节点分成的叶节点和内部节点存储至两个不同的独立数组中，得到第一二叉基数树；

按照一一对应的关系为每个所述第一二叉基数树分配对应的所述轴对齐包围盒，并对所述第一二叉基数树的叶节点到根节点的路径进行并行处理，使得每一个所述第一二叉基数树的内部节点和叶节点均匹配对应的所述轴对齐包围盒，得到线性边界体层次结构。

3.根据权利要求2所述的从显式几何到隐式几何的快速转换方法，其特征在于，所述预设的分类方法为：

针对每个三角形面片，比较其左右两个三角形面片的第一莫顿码的共同前缀长度，并确定划分方向和划分节点；

将所有以所述第一莫顿码表示的三角形面片作为叶节点，基于所述叶节点确定划分位置，并根据所述叶节点是否处于所述划分节点的位置判断所述划分节点是否为内部节点。

4.根据权利要求2所述的从显式几何到隐式几何的快速转换方法，其特征在于，所述基于所述线性边界体层次结构构建八叉树结构具体包括如下步骤：

给定八叉树的划分层次，将所述三角形网格的包围空间按照所述八叉树的划分层次均匀划分为与体素数据一一对应的三维网格，并利用所述体素数据构建第二二叉基数树；

基于所述第二二叉基数树确定对应的第二莫顿码，利用所述第二莫顿码确定所述八叉树的所有层级节点，并为所有所述层级节点分配内存，存储所述八叉树的层级节点信息；

基于设定的父子节点关系，采用并行化处理方法确定每个层级节点的父子节点，并得到八叉树结构；

其中，所述父子节点关系为所述八叉树的任意两个内部节点之间的共同前缀长能够被三整除，且二者的共同前缀长除以三后的差值为一。

5.根据权利要求1所述的从显式几何到隐式几何的快速转换方法，其特征在于，利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号具体包括如下步骤：

根据所述采样点p在最近的所述三角形面片上的投影点x的位置确定三角形网格的伪法线，具体包括：当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片内时，则根据所述采样点p和投影点x确定三角形片面的法线，当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片的边上时，定义面i和j之间的边分别具有法线n_i和n_j，则三角形面片边的伪法线n_edge＝π·n_i+π·n_j，当所述采样点p在最近的所述三角形面片上的投影点x位于三角形面片的顶点上时，三角形面片顶点的伪法线为n_vertice＝∑a_i n_i，其中，a_i为第i个面对应的顶角的角度值；

基于所有三角形面片的伪法线确定三角形网格的伪法线，并根据三角形网格的伪法线确定采样点p的投影点x到查询点p的方向向量r＝p－x，并根据方向向量r与投影点x处的法线或伪法线的点积确定查询点p的符号。

6.根据权利要求1所述的从显式几何到隐式几何的快速转换方法，其特征在于，还包括如下步骤：

将符号距离场的数据储存在vtk非结构化网格中，抽取其等值面，完成隐式几何的可视化。

7.根据权利要求6所述的从显式几何到隐式几何的快速转换方法，其特征在于，所述将符号距离场的数据储存在vtk非结构化网格中，抽取其等值面具体包括如下步骤：

初始化vtk非结构化网络，并将所述八叉树结构数据中点坐标添加到vtk非结构化网络中，根据所述八叉树结构的数据类型创建六面体单元，并将所述六面体单元添加至vtk非结构化网络中；

将所述符号距离场的数据以点数据的形式写入vtk非结构化网格中；

初始化等值面值，并获取符号距离场的表面轮廓，通过vtk非结构化网络中的等值面过滤器模块对符号距离场进行等值面提取，并映射到可视化图形数据结构中。

8.一种从显式几何到隐式几何的快速转换系统，其特征在于，包括构建模块、第一计算模块、第二计算模块和转换模块：

所述构建模块，用于对输入的三角形网格构建线性边界体层次结构，并基于所述线性边界体层次结构构建八叉树结构；

所述第一计算模块，用于利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场；

所述第二计算模块，用于利用角权重伪法线算法计算三角形网格的伪法线，利用三角形网格的伪法线计算自适应网格无符号距离场的符号；

所述转换模块，用于根据自适应网格无符号距离场和自适应网格无符号距离场的符号确定符号距离场的数据，完成隐式几何到显式几何的转换；

所述第一计算模块利用所述八叉树结构的节点作为采样点，利用线性边界体层次结构结合最小边界框剪枝方法，对每个采样点并行化计算自适应网格无符号距离场具体包括如下步骤：

计算所述八叉树结构的所有节点所处位置的第三莫顿码，并剔除重复的莫顿码，将互不相同的所述第三莫顿码对应的八叉树结构的节点作为采样点p；

确定所述采样点p在最近的三角形面片上的投影点x的位置，基于R－TREE的空间缩减方法计算采样点p到最近的所述三角形面片的距离；

自上而下遍历所述线性边界体层次结构，并将所述线性边界体层次结构的所有节点逐一存储至堆栈S中；

针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为内部节点，则计算该节点到轴对齐包围盒的最小距离和最小最大距离，并进行最小边界框剪枝处理，通时将新增的内部节点存储至堆栈S中，直至所述堆栈S中所有节点均被处理完成；

针对所述堆栈S中的任一节点，若该节点的左子节点或右子节点为叶节点，则计算该采样点到叶节点代表的三角形面片的距离，并将所有的距离中的最小值作为采样点到三角形网格的最小距离，完成无符号距离场的构建。

9.一种计算机可读存储介质，存储有计算机程序，其特征在于：所述计算机程序被处理器执行时，实现权利要求1－7任一项所述的从显式几何到隐式几何的快速转换方法。