面向牙科三维网格数据的非流形结构检测及快速修复
Non-Manifold Structure Detection and Fast Restoration for Dental 3D Mesh Data
-
摘要: 针对现有口腔扫描设备获取的网格数据存在自相交、孔洞等一系列问题,提出一种快速、有效的自相交检测算法.为了降低全局网格自相交检测的时间复杂度,引入一种特殊的八叉树算法,利用细分的思想把三角面片放置在不同的立方体内以实现快速自相交检测,并通过删除操作消除错误连接;为了修复上一步骤中形成的大量网络孔洞,设计一种特殊的双边数据结构,能够快速有效地检测单连通封闭孔洞,并正确处理多个孔洞共用同一顶点的问题;孔洞修复完成后,利用拉普拉斯平滑策略对孔洞区域进行处理,获得过渡自然平滑的补洞效果.在80套口腔内扫描数据上的实验结果表明,所提算法不仅能够快速检测网格数据的自相交区域,而且能够高效完成补洞操作;与现有算法相比,在网格数量大于100万的数据上,处理速度提高大约10倍.Abstract: Aiming at a series of problems such as self-intersection and holes in the mesh data obtained by the existing oral scanning equipment, a fast and effective self-intersection detection algorithm is proposed. To reduce the time complexity of global mesh self-intersection detection, a special octree structure is imported, with a subdivision strategy, the triangular facets are placed in different cubes to detect self-intersection and eliminate incorrect linkages by deleting operations. However, this will bring a lot of holes. To remedy these holes, a special bilateral data structure is designed, which can quickly and effectively detect single-connected closed holes and correctly process vertices shared by multiple holes. After remedying the holes, the Laplacian smoothing strategy is used to process the hole area, and achieve an effect that the hole is filled with natural and smooth transition. Experiments on the eighty sets of mouth scansshow that the proposed algorithm can not only rapidly detect the self-intersecting region of mesh data, but also efficiently complete the hole filling operation. Compared with the existing algorithm, the processing speed is about 10 times faster on the data with more than 1 million meshes.