一种基于三维散乱稠密点云的三角网格重构方法

摘要

本发明公开了一种面向三维散乱稠密点云，基于三维Delaunay四面体剖分和网格生长法的三角网格重构方法及其理论基础。该理论是基于著名的三角网格重构算法Crust算法理论的进一步推导出的粗略分离特性。本发明基于三维散乱稠密点云的三角网格重构方法，要求在两个距离近或曲率大的对顶曲面部分采样稠密。原理为：先对所有点云进行三维Delaunay四面体剖分，再根据粗略分离特性通过判断三角形的交叉值抽取出属于物体表面的部分三角形面片，再从中选择初始前沿三角形，最后从初始前沿三角形不断扩展形成整个曲面的三角网格。本发明着重改善以往三角网格剖分算法速度慢的问题，从而提高算法速度，并且生成的三角网格质量良好，适应性广。

主权项

一种基于三维散乱稠密点云的三角网格重构方法，其特征在于，先对所有点云进行三维Delaunay四面体剖分，再根据粗略分离特性通过判断三角形交叉值抽取出属于物体表面的部分三角形面片来初始化网格曲面，然后选择初始前沿三角形，最后从前沿三角形扩展形成整个三角网格曲面；具体步骤如下：第一步：导入三维散乱点云数据；第二步：对导入点云数据进行三维Delaunay四面体剖分，所有形成的三角形都为Delaunay三角形，计算每个三角形的交叉值；第三步：根据粗略分离特性通过判断交叉值抽取部分三角形初始化三角网格曲面；第四步：选择初始前沿三角形，从初始前沿三角形不断扩展网格曲面，完善没有抽取出来的物体表面三角形，直到输出整个重构三角网格曲面；所述第三步的过程为：选取交叉值<‑0.2的三角形，选出物体表面的三角形；建立一个空栈，每条前沿边依次加进这个空栈，形成前沿边栈；所述第四步包括如下步骤：步骤4.1：对所述前沿边栈内的栈顶前沿边，定义一个以搜索点为球心的搜索球，搜索球内的候选点与前沿边组成的Delaunay三角形都为候选三角形；如果在搜索范围内没有找到候选点，则该前沿边被认为是边界边；其中，所述搜索球的定义为：选择与前沿三角形在同一平面上并且与前沿边构成正三角形的点为搜索球球心，以前沿边长度为半径的搜索球；步骤4.2：从候选三角形里选取和前沿三角形夹角最大的唯一三角形，使之成为新的前沿三角形；检查新的前沿三角形的各条边原来是否是前沿边，如果原来是前沿边，则跳出所述前沿边栈变为非前沿边；如果原来不是前沿边，则变为前沿边，且将新的前沿边入栈；对所述前沿边栈内的每一前沿边依次重复步骤4.1和4.2，直至所述前沿边栈为空停止。