曲面网格修复中的一种快速搜索方法

A Rapidly Search Method in Repairing Surface Mesh

提出了一种应用于搜索曲面网格修复过程中缺陷网格的边搜索算法。为了提高算法的效率,采用了升高维数处理问题的方法,将三维空间中的边转换为六维空间中的点建立了单元边二叉树。同时将搜索分为全局和局部搜索两个部分,全局搜索中将三维空间中判断包围盒相交转换为六维空间中判断点在区域内。从而将时间复杂度降为O(nlogn)。并通过编程,用实例证明该算法可准确、快速搜索出缺陷网格单元。

This paper addresses an edge-searching algorithm applied to searching disfigurement meshes in the process of repairing surface mesh. In order to improve the efficiency of this algorithm, using the method of hoisting dimension, change an edge in 3D to a point in 6D and create cell-edge binary tree. At the same time, the search process is divided into two steps： global search and local search, in the process of global search judging the intersection of surrounding-box in 3D will be changed into judging the point in a given region in 6D. So decrease the time-complexity to O（ nlog n）. And by making program, using examples to improve this algorithm can search disfigurement meshes exactly and rapidly.