关键词: 逆向工程, 散乱数据, 三角剖分, 局部增量, 网格扩张

Abstract: In order to deal with the trend of increasing large scattered data points set in reverse engineering, a space partition strategy with its corresponding data structure and encoding method was proposed to improve the triangulating and search efficiency. At the same time, the concepts of inner-connection and outer-connection were put forward and the direct triangulation algorithm from 3D scattered points based on the local incremental mesh expansion method was provided. The computational complexity of this algorithm was O(N). Compared to the typical triangulation algorithms, it has significantly reduced its time complexity and improved the mesh quality.

Key words: reverse engineering, scattered points, triangulation, local increment