三角网格模型错误检测及修复算法研究.pdfVIP

54 2008年 11月 中国制造业信息化 第 37卷 第21期 三角网格模型错误检测及修复算法研究 裴如兵，程筱胜，戴 宁 (南京航空航天大学 机电学院，江苏 南京 210016) 摘要：三角网格模型在计算机辅助设计中得到了广泛的应用，但是由于模型常见的一些错误给后 续处理带来了极大的困难。针对这个问题，在对常见错误分析的基础上，通过建立相应的数据结 构，系统地提出了处理各种错误的算法，最后通过实例验证了算法，取得了理想的修复效果。 关键词 ：三角网格模型 ；错误 ；检测；修复 中图分类号：TP391。72 文献标识码 ：A 文章编号：1672—1616(2008)21—0054—04 经三维测量仪扫描物体模型所取得的点云数 将其分为以下几类：退化网格、自交网格、不合理 据 ，在测量的过程中可能因为噪声或是测量时因为 边、孤立网格、重叠网格、孔洞。在三角网格模型 模型的死角以及人为的因素等，而造成点云数据的 中，导致错误网格形成的原因主要有：点云数据的 缺失以及误差的产生，由点云数据网格化后也有可 缺失、噪声、拓扑关系混乱、顶点数据误差、三维重 能会产生错误的网格。LeongE，2j特别针对 了快速 建软件重建过程中三角化算法的缺陷。原始点云 原型加工的需求提出会影响加工过程的几项错误 数据的噪声点或点云数据缺失可能产生网格的边 网格情形，包括退化、不合理边、孔洞等等，这些情 界与模型中的其他三角片没有共同的顶点的孤立 形严重影响了网格模型的后续处理，如快速原型制 网格，也可能形成孔洞；拓扑关系的混乱可能导致 造、有限元分析等。 某条边有3条或3条以上的相邻边；顶点数据误差 国内外对三角网格模型的错误检测及修复算 容易导致重叠三角片和 自交三角片的产生；三维重 法 已经有一些研究。Bischoff等l3j将三角网格模 建软件 自身三角化算法的不完善可能会产生三边 型转化为体素表示法对网格模型错误进行了自动 共线的退化网格 。 修复，但只对退化、不正常边等问题进行修复；Van Niekerk等lJ将文件 的错误分成结构性错误和几 2 错误检测及修复算法 何性错误2类，但只修复了其中的三角面片丢失和 2．1 数据结构 重叠等问题；李江峰等E5J将边界错误作为一种类 目前大多数三角网格模型文件仅包含三角面 型来统一考虑，并设计了相应的修补算法，然而边 片的顶点的坐标信息，缺少三角面片之间的拓扑信 界错误不能覆盖所有的复杂错误情况；赵吉宾 息，后续处理极为不便，因此必须设计合理的数据 等l6j通过扫描边对象链表的标志项来检查错误进 结构来描述文件的拓扑信息，使其不但能反映三角 行修复，该方法的拓扑数据结构效率低，修复成功 形面片的几何结构，而且能反映出相邻关系，以利 率不高。总体而言，现有的三角网格模型错误修复 于文件的检测和修复。基于以上考虑，本文设计了 研究大多是针对其 中的某一类或几类错误，提出的 3个结构体：顶点 (CVertex)、边 (CEdge)和三角面 算法不够完善。针对上述不足，本