[发明专利]一种基于GPU加速的维诺图三维网格重构方法

摘要

本发明涉及一种基于GPU加速的维诺图三维网格重构方法，包括以下步骤：利用k‑dtree查找三角网格与输入点数据的空间邻近关系并将邻近关系解释为点数据的维诺图，利用空间切割算法计算维诺图和三角网格的交集并以此计算点数据的能量，更新点位置，多次迭代直至能量函数收敛，并通过Delaunay三角化算法构造新的网格。本发明借助GPU强大的并行计算能力，大大提高了算法的计算速度和效率。

主权项

1.一种基于GPU加速的维诺图三维网格重构方法，其特征在于：包括以下步骤：(1)输入任意一个三角面片模型并在该模型表面上均匀采样，根据组成模型的每个三角面片面积大小所占比例选择其面片上的点数，利用kd-tree搜索点集中每个采样点附近的k个近邻点，将这些近邻点的索引线性储存起来；(2)将步骤(1)中的输入模型的位置和权重值，模型上的采样点集数据和由kd-tree搜索出的采样点集的邻近点索引信息传入GPU，根据点集和模型顶点的数量选择以点并行或者以面片并行的策略，在GPU的每个线程中，选择离输入该线程的每个模型三角面片的重心最近的点作为第一次与这一面片进行迭代的点，在每次迭代中，计算通过重心的近邻点和三角面片中心点计算的中垂面与此三角面片的交点对作切割，并在切割过程中记录下次迭代点的索引和记录切割后的多边形的顶点位置；(3)将步骤(2)中的多边形polygon作为RVD数据记录，并通过利用共享存储器sharedmemory写速度快的策略进行优化，利用这种GPU算法，能较快的算出RVD，利用RVD可以优化模型的质量。