基于STL三角网格模型孔洞修补的研究
2012-06-09闫涛
闫涛
（南通大学 计算机科学与技术学院，江苏 南通 226019）
STL（Stereolithogrphy Interface）文件格式是由美国3DSystem公司于1987年定制的，其使用三角形面片来表示三维实体模型，己成为众多CAD软件的标准数据输入和输出模块，也被视为正、逆向工程设计转换到快速原型的一种公认的标准，当模型由CAD或逆行工程软件建成后，即可直接输出到快速原型系统构建实体模型。
STL文件必须遵循一定的规范才能正确地描述三维实体模型，包括：1）共顶点规则，每一个三角面片必须与其相邻的每一个面片共两个顶点；2）取向规则，单个面片法向量符合右手法则且其法向量必须指向实体外面；3）充满规则，小三角面片必须布满三维模型的所有表面，不得有任何遗漏。但是，在实际的应用中，STL文件会存在各种不同的错误，常见的错误主要有：孔洞、重叠、错位和不共顶点等。孔洞是STL文件中最常见的一种错误，主要是在对多个大曲率曲面相交构成的表面模型三角化过程中，进行拼接时有小的曲面丢失而造成的。这些孔洞的存在会影响许多后续的操作，如快速原型制造、有限元分析等。国内外许多学者对此都进行了研究。但由于大多数算法在构造新三角片时仅仅采用原有的孔洞多边形顶点，而没有增加新的顶点，难以获得较好的用于填补孔洞的三角片形状，修补效果不够理想。
笔者在研究原有算法的基础之上，针对封闭式STL三角网格模型中存在的孔洞，根据实际的需求来添加新的顶点，从而获得新的三角形面片，算法主要包括孔洞边界的提取及非独立孔洞的分裂，确定孔洞边界点的平滑度，构造新的三角形面片。
1 孔洞边界的提取
对于封闭式的STL三角网格曲面，如果网格曲面中没有孔洞，那么该曲面中的每一条边都有两个邻接三角片，则这样的边称之为内部边。如果存在某条边只有一个邻接三角片，那么这条边称之为边界边，则该条边是构成孔洞多边形的一条边，而边界边的两个端点称之为边界点。边界点所在的三角形则称为边界三角形。如图1所示，所有相互连接的边界边就构成了一个完整的孔洞。
图1 孔洞基本信息Fig.1 Basic information of Holes
根据STL三角网格模型的取向规则，每个三角形面片的三个顶点的排列必须符合右手法则，即沿着平面片法矢相反的方向观察，三个顶点应该是逆时针排列。因此，按逆时针方向，如图2所示，将每条边的两个端点分别定义为起点和端点。那么，在一个独立孔洞边界的提取过程中先识别到一条边界边，以该边为起始边，然后在该边终点所在的其他边中查找以该终点为起点的边界边，以此类推，直到一条边界边的终点为起始边的起点，那么，一个孔洞的边界提取就此结束[1]。如图3所示，如果以孔洞内部为观察点，那么孔洞的边界按顺时针排列。
图2 三角形边的定义Fig.2 Definition of the triangle edge
图3 孔洞边界的排列Fig.3 Arrangement of the Hole boundary
而对于非独立的孔洞，如图4（a）所示，共顶点属于两个不同孔洞的边界点。那么将共顶点再作为另一个孔洞的起始点，任选一条以共顶点为起点的边界边，继续查找，此时会出现两种情况：1）如果找到原始的起始点，一个孔洞边界提取结束；2）如果找到了以共顶点为新起始点的起始点，那么一个新的孔洞边界提取结束。再选另外以共顶点为起点的边界边开始另一个孔洞边界的提取。这样就可以将非独立孔洞分裂为多个独立孔洞，如图4（b）所示。
图4 孔洞的分裂Fig.4 Hole split
2 孔洞边界点平滑度的确定
孔洞常会出现在三角网格模型的特征线上，为了使修补后的孔洞区域和原有的区域尽量保持原有的特征，本文在对孔洞修补之前先确定孔洞边界点的平滑度，然后计算孔洞边界点的平均平滑度，在修补时对小于平均平滑度的顶点先行修补。
如图5所示，在三角网格模型中，顶点的平滑度可以通过该顶点所在的三角形的夹角的平均值来确定，如果夹角的平均值越小，就表明该点所在的区域越趋于平滑[2]。三角形的单位法向量可以根据三角形的3个顶点来计算，即：
邻接三角形的夹角可以通过它们的外法矢来计算[3]，公式如下：
图5 顶点邻接的三角形的法矢Fig.5 Vertex adjacent of the triangles’normals
3 孔洞中新三角形的添加
本文在孔洞中添加新的三角形主要是从孔洞的边界点和其邻接的两条边界边的夹角来考虑[4]。
如图6所示，内角θ会有下面几种情况：
图6 孔洞相邻边的内角Fig.6 Angles of adjacent edges in the holes
对于孔洞的内角按下面的方式处理[5]：
1）如果θ≥180°，将不对其处理，再寻求下一个顶点。
2）如果θ≤90°，那么连接θ两条边的两个端点，生成新的三角形。如图7所示，新生成的三角形的3条边的方向根据STL三角网格模型的规则，按逆时针方向排列。为了保持孔洞的完整性，新三角形其中新添加的边将作为孔洞的一条边，而另外两条边则从孔洞中删除。
图7 θ≤90°的处理Fig.7 Processing of angles less than or equal 90°
3） 如果 90°＜θ＜180°，那么计算由连接 θ两条边的两个端点生成的新三角形的外心，分别连接外心和θ以及其两条边的端点，生成两个新的三角形。如图8所示，同样按照STL三角网格模型的规则，新增的两个三角形的边按逆时针方向排列，其中外心同θ的连线是两个新三角形的邻接边，它的方向在两个三角形中按各自的方形排列。而在保持孔洞的完整性中，将原来的两条边删除，将外心和原来两条边的端点所构成的边加入孔洞的边中。
图8 90°＜θ＜180°的处理Fig.8 Processing of angles between 90°to 180°
三角形的外心到其各个顶点的距离相等，如图9展示了三角形的外心，针对3D空间，三角形的外心计算如下：
图9 三角形的外心Fig.9 Circumcenter of the triangle
设三角形的 3 个 顶 点 为 v1（x1，y1，z1），v2（x2，y2，z2），v3（x3，y3，z3），则：
那么外心的坐标为：
4 新增顶点的合法性验证
如果新增加的顶点不在孔洞所构成的多边形之内，那么构成的新三角形将会和原有的三角形发生重叠[6]。对其合法性验证的方法是：如图10所示，假设P为新增加的顶点，
图10 新增点的位置Fig.10 Location of the new point
5 应用实例
在上述算法设计和研究的基础上，作者在Visual Studio.Net 2008集成环境下，采用C#作为开发语言，结合CsGL开发了一个原型系统。在此系统中采用交互的方式，人为地挖出仿真孔洞，然后运用设计的算法对其进行了修补。图11为一个足部的三角网格模型的原始图及孔洞修补后的效果图的对比，在原型系统中以面片的形式显示。图12对孔洞区域放大后原始图与孔洞修补后效果图的对比，以线的形式显示。
图11 原始图及修补效果的对比Fig.11 Original graphics and comparison of the effect of repair
图12 孔洞区域的放大Fig.12 Enlarged the hole area
6 结 论
作者在认真研究和分析众多学者的研究成果的基础之上，提出了一种针对STL三角网格模型孔洞修补的算法。该算法考虑孔洞区域的平滑度，并根据实际情况增加新的三角片的顶点，因此获得了被修补区域三角片形状较为优化的修补结果。 通过实践证明该算法比较稳定可靠，能够满足实践中的需求。
[1]Liu H，Hu Q，Li L，et al.A study of the method of reconstructing the bionic scaffold for repairing defective bone based on tissue engineering[C]//Proceedings of PROLAMAT 2006，IFIP TC5 International Conference，Shanghai，2006（207）：650-657.
[2]袁天然.三角网格模型光顺、简化和缝补技术的研究及应用[D].南京:南京航空航天大学，2007.
[3]Botsch M，Pauly M，Rossl C，et al.Geometric modeling based on triangle meshes[R].New York：ACM，2006.
[4]ZHAO Wei，GAO Shu-ming，LIN Hong-wei.A robust holefilling algorithm for triangular mesh[J].Visual Computer，2007，23（2）:987-997.
[5]杜佶，张丽艳，王宏涛，等.基于径向基函数的三角网格曲面孔洞修补算法[J].计算机辅助设计与图形学学报，2005，17（9）:1976-1982.DU Jie，ZHANG Li-yan，WANG Hong-tao，et al.Hole repairing in triangulai meshes based on radial basis function[J].Journal of Compuyer-aided&Computer Graphics，2005，17（9）:1976-1982.
[6]成欣，周明全，耿国华，等.空间三角网格曲面的补洞方法[J].计算机应用研究，2006，23（6）:158-160.CHENG Xin，ZHOU Ming-quan，GENG Guo-hua，et al.Holefilling method for reconstruction of trianglar mesh[J].Application Research of Computer，2006，23（6）:158-160.
