基于映射法的散乱点云Delaunay三角剖分曲面重构方法

摘要

本发明涉及一种基于映射法的散乱点云Delaunay三角剖分曲面重构方法，属于计算机图形学、虚拟现实技术领域。具体操作步骤为：①获取目标的原始点云数据。②获取原始点云数据中每个点的K阶邻域和单位法向量。③将点云数据进行分片。④参数化已分片的点云到二维平面。⑤在二维平面内对点云进行Delaunay三角剖分并映射回对应的三维空间。⑥优化初始三角网格模型。与已有技术相比较，本发明方法能够在进行大规模点云数据网格建模时，在保证三角网格的质量的同时，能够较快的实现散乱点云的三角网格化，对于海量点云效果更佳。

主权项

一种基于映射法的散乱点云Delaunay三角剖分曲面重构方法，其特征在于：其具体步骤如下：步骤一、获取目标的原始点云数据；设定点云数据坐标系：建立空间直角坐标系，以水平向右方向为X轴正方向，竖直向上方向为Z轴正方向，垂直于X轴和Z轴所确定的平面的轴为Y轴；它们的正方向符合右手规则；所述原始点云数据包含三维坐标信息，还包含每个点的法向量信息；步骤二、获取原始点云数据中每个点的K阶邻域和单位法向量；在步骤一操作的基础上，获取原始点云数据中每个点的K阶邻域和单位法向量，具体操作步骤为：步骤2.1：获取原始点云数据中每个点的K阶邻域；步骤2.2：在步骤2.1操作的基础上，获取八叉树点云数据中每个点的单位法向量，具体操作分为2种情况：情况1：如果八叉树点云数据中每个点包含法向量信息，对每个点的法向量进行单位化得到其单位法向量；情况2：如果八叉树点云数据中每个点不包含法向量信息，则采用主元分析法计算点云数据的单位法向量；其步骤如下：步骤2.2.1：对于点云中任意一点P，通过公式(1)使用最小二乘法为点P和点P的K阶邻域计算出一个局部平面S；$S(n,d)=\arg {\min }_{(n,d)}\underset{i=1}{\overset{k}{\Sigma }}{(n·P_i-d)}^2---\left(1\right)$其中，n为平面S的单位法向量；d为点P到坐标原点的距离，P_i为点P的k个邻近点，k为正整数，4≤k≤100；步骤2.2.2：找到点P以及点P的k个邻近点的质心P＇，并通过公式(2)获得半正定协方差矩阵M；然后对半正定协方差矩阵M进行特征值分解，将半正定协方差矩阵M的最小特征值对应的特征向量作为点P的法向量；$M=\underset{i=1}{\overset{k}{\Sigma }}(P_i-P^{\prime }){(P_i-P^{\prime })}^T/k---\left(2\right)$步骤2.2.3：对步骤2.2.2得到的点P的法向量进行单位化得到点P的单位法向量；步骤2.2.4：由于步骤2.2.3计算出的单位法向量方向与真实的单位法向量可能相反，因此需要判断单位法向量方向是否需要进行调整，如果单位法向量方向与真实的单位法向量相反则进行调整；判断单位法向量方向是否需要进行调整以及调整方法为：在八叉树点云数据的所有点中，找到其Z坐标值最大的点A，然后选取点A的邻域中任意一点N，计算向量NA与点A的单位法向量na之间的夹角β(NA,na)，如果β(NA,na)>π/2，则将点A的单位法向量变换方向；以点A为基准点调整其k个邻域点的单位法向量n₁方向，计算单位法向量na与单位法向量n₁之间的夹角β(na,n₁)，如果β(na,n₁)>π/2，则改变该邻域点的单位法向量方向；此后再依次以点A的邻域点为基准点，调整点A的邻域点的邻域点的单位法向量，重复此过程，直到所有单位法向量都调整完毕；步骤三、将点云数据进行分片；在步骤二计算点云数据单位法向量的基础上，对点云数据进行分片；具体操作步骤如下：步骤3.1：搜索种子点；所述搜索种子点的方法为：在步骤二得到的点云数据中，从未分片的点中随机选取一个点O＇，将点O＇的k个邻域点的单位法向量投影到点O＇与点O＇的单位法向量确定的平面上，形成k条射线，对每一条射线L，以射线L的起点为起点，经过点O＇形成一个新的射线，如果该射线与射线L的夹角全部大于π或者全部都小于π，则点O＇为种子点，否则，点O＇不是种子点；如果点O＇不是种子点，重复该步骤，直到找到一个种子点O；步骤3.2：将步骤3.1得到的种子点O加入到待拓展队列Queue中，将该种子点为点云分片s的第一个点，同时将种子点标记为已分片；步骤3.3：若待拓展队列Queue不为空，从队列中取出一个点Q，遍历点Q的k个邻域点，判断点Q的当前邻域点的法向量与种子点O的法向量夹角α是否低于一个阈值θ，其中，θ为人为设定值，如果α≤θ成立，则将该邻域点加入待拓展队列Queue和当前的点云分片s中，同时标记该邻域点为已分片；重复此过程，直到待拓展队列Queue为空时，点云的一个分片的分割完成；步骤3.4：重复执行步骤3.1至步骤3.3，直到所有的种子点都标记为已分片；步骤3.5：经过步骤3.1至步骤3.4的操作，如果存在少数点没有被划分到任意一个分片当中，或者分片中的点的数量少于阈值σ，其中，σ为人为设定值，5≤σ≤100，将这样的点称为未分片点；对于未分片点，将其划分到含有最多当前未分片点的领域点的分片中；步骤3.6：对每一个分片的边缘进行拓展；其具体操作方法为：遍历分片中全部点，查看每个点的邻域点的所属分片，若邻域点的分片和该点的分片不同，则将该点加入到邻域点所属的分片中；经过步骤三的操作，即可完成全部点云数据的分片；步骤四、参数化已分片的点云到二维平面；在步骤三对点云数据分片的基础上，进行分片点云的无网格参数化，将空间的三维点云影射到二维平面空间；其具体操作步骤如下：步骤4.1：从步骤三得到的分片中，取一个未参数化的分片，将该分片中的种子点O加入待参数化队列Queue2；步骤4.2：若待参数化队列Queue2不为空，从待参数化队列Queue2中取出一个点B，将点B标记为已调整，将点B直接投影射到以点O和点O的法向量确定的平面上，得到投影点B′；对于点B的k个邻域点中的每一点D，将点D直接投影射到以点O和点O的法向量确定的平面上，得到投影点D′；沿着B′D′的方向将B′D′延伸，得到一条长度为|BD|的线段，该线段记为B′D″，点B′和点D″为线段B′D″的两个端点；点D″为点D经过一次调整后得到的映射点；将点D″加入到点D的调整点集合coSet中；如果点D为未调整，则将点D加入待参数化队列Queue2中；步骤4.3：重复步骤4.2直到待参数化队列Queue2为空；步骤4.4：依次遍历步骤4.1中所述分片中的点，对每一点计算其调整点集合coSet中所有点的坐标平均值，将此均值坐标作为参数化结果；经过步骤4.1至步骤4.4的操作，完成了一个分片的无网格参数化；步骤4.5：重复执行步骤4.1至步骤4.4，直到所有的分片都完成无网格参数化；步骤五、在二维平面内对点云进行Delaunay三角剖分并映射回对应的三维空间；在步骤四操作的基础上，对全部无网格参数化结果的点云分片进行德劳内三角网的构建；具体操作步骤为：步骤5.1：采用德劳内三角网格的方法重构无网格参数化结果的点云分片，德劳内三角网所具有的空圆特性和最大最小角特性，保证了德劳内三角网中不会出现过于狭长的三角形，使得三角网的构建更合理与准确；步骤5.2：经过步骤5.1对所有的点云分片进行德劳内三角网构建完成后，将全部分片的构网结果返回到三维空间，得到原始点云数据的初始三角网格模型；步骤六、优化初始三角网格模型；在步骤五初始三角网格模型的基础上，进行网格重叠和空洞的优化；具体操作步骤如下：步骤6.1：统计步骤五得到的初始三角网格模型中，每条边使用的次数count；若某一条边使用次数count＝3，则表示共同使用该边EF的有3个三角形，其中点E和点F为边EF的两个端点；计算使用此边的三角形所在平面之间的夹角，选择其中夹角最小的两个三角形，将这两个三角形分别称为第一三角形和第二三角形，将另外一个三角形称为第三三角形；第一三角形、第二三角形和第三三角形的另外一个顶点分别用符号G、H和I表示；选取边EF的中点J，如果∠GJI>∠HJI，则删除第二三角形；否则，删除第一三角形；重复该步骤，直到每条边的使用次数count均不大于2；步骤6.2：统计步骤6.1得到的三角网格模型中，每条边使用的次数count；若某一条边使用次数count＝1，将此边称为边界边RT，其中点R和点T为边RT的两个端点；将使用边界边RT的三角形的另外一个顶点用符号V表示；将点R和点T称为孔洞点；搜索点R和点T的邻域点中的孔洞点，并组成点集SET；选取边RT的中点U；如果点集SET不为空，则遍历点集SET中的点W，选取∠VUW中的最大值对应的点W_max；将点W_max、R和T组成一个新的三角形加入到三角网络模型中，同时更新ΔW_maxRT的三条边的使用次数count；如果点集SET为空，将边界边RT的使用次数count值更新为2；重复该步骤，直到每条边的使用次数count均等于2；经过上述步骤的操作，得到原始点云数据的最终三角网格模型。