Abstract: An effective algorithm for triangulation mesh of implicit surfaces is proposed. From a seed point on the surface starting, the boundary of generated mesh is considered as expanded polygon, and the point on this polygon corresponding to minimum angle is considered as expanded point. The generated triangles from expanded point can be computed, and furthermore, in order to prevent new triangles from overlapping existing triangles, collision detection must be done. In the process of triangulation mesh, due to dynamic expanded polygon, above steps are repeated until expanded polygon is empty. This algorithm is used to triangulation mesh of analytical and variational implicit surfaces respectively. The result of experiment shows that this algorithm is capable of good meshing quality without the need for remeshing step, and meshes adapt to the local curvature of the surfaces, and thus the effectiveness of this algorithm is demonstrated.

Key words: implicit surface, triangulation mesh, curvature, expanded polygon, collision detection

摘要： 提出一种有效的隐式曲面三角网格化算法。从隐式曲面上的一个种子点开始，生成网格的边界作为扩张多边形，且该多边形最小角对应的顶点为扩张点，计算从扩张点处欲生成的三角网格，为了防止新生成的三角网格和已经存在的三角网格重叠，要进行冲突检测。在隐式曲面三角网格化的过程中，扩张多边形是不断变化的，需要重复上述步骤，直至没有扩张多边形时结束。该算法分别应用于解析隐式曲面和变分隐式曲面的三角网格化。实验结果表明，该算法不需要重新网格化的步骤，生成的三角网格具有较高的质量，且三角网格随曲率适应性变化，因此说明了该算法的有效性。

关键词: 隐式曲面, 三角网格化, 曲率, 扩张多边形, 冲突检测