由点云数据生成三角网格曲面的区域增长算法

A Region-growing Algorithm for Triangular Mesh Surface Reconstruction from Point-cloud Data

提出一种新的由点云数据生成三角网格曲面的区域增长算法.该算法充分利用点云内在的几何与拓扑信息,使用一组检测过滤规则,对曲面进行快速网格重构.算法包括两部分:首先对点云做预处理完成数据精简,其次使用一组检测规则,从种子三角形出发,针对每个活动边,在点云中选择匹配点与其构成新的三角形,并通过不断更新边界,使剖分区域不断增长.所使用的检测规则,可以针对活动边与预选择匹配点之间的不同位置关系采用不同的阈值,从而避免了重叠与自交三角形的生成,防止产生错误拓扑,确保了重构三角网格曲面的质量.同时针对区域增长算法中的前沿分裂问题,在数据结构中采用反向重合边,使剖分过程始终保持一个前沿边界.实验结果表明,该算法具有运算速度快、结果准确性好、适用范围广等优点.

A new region-growing algorithm is presented for triangular mesh surface reconstruction from pointcloud data. The algorithm makes the full use of geometric and topological information inherent in the pointcloud data and adopts a series of examining rules to reconstruct triangular mesh surface rapidly. The algorithm consists of two steps： Firstly, an initial data thinning is performed to reduce the data set size. Secondly, the process of the region-growing is started from an initial to form a satisfied triangle for each active edge in the triangle and is followed by choosing an appropriate point boundary of advancing front. The triangulated region is growing repeatedly by updating boundary repeatedly. According to the relative position between the active edge and the candidate points, in presented examining rules, different thresholds are used. This avoids generating overlapping facets, self-intersection and wrong topology. The examining rules ensure the quality of reconstructed triangular mesh surface. In accordance with the problem of the advancing front broken, the overlapping edge of the opposite direction is used. This ensures to have only one boundary of advancing front throughout.Experimental results show that the algorithm has many advantages, such as high efficiency, accuracy and generality.