摘 要

Abstract II

1 绪论 1

1.1 3D打印模型分割概述 1

1.2本文的研究内容和意义 1

2 三维模型分割算法概述 3

2.1 三维模型分割概述 3

2.2 国内外不同原理的三维模型分割算法 3

3 STL文件的处理 9

3.1 STL文件简介 9

3.2 STL文件的数据冗余性 9

3.3 STL文件的数据冗余性 10

3.3.1 开发环境搭建 10

3.3.2 STL文件的加载算法 10

3.3.3 STL模型的拓扑结构实现 11

3.3.4 STL文件去重算法 14

3.4 STL文件的可视化 15

3.4.1 OpenGL简介 15

3.4.2 STL文件的显示 15

3.5 本章小结 17

4 基于机器学习的三维模型分割 18

4.1 本文使用的三维模型数据库 18

4.2网格几何特征的提取 19

4.2.1三维网格特征介绍 19

4.2.2三维网格特征计算 19

4.2.3本文所使用的三维网格特征 21

4.3 Adaboost分类器及其算法简介 22

4.4 Adaboost分类器训练集构建简介 23

4.5 实验结果及分析 24

4.6 本章小结 24

5 总结与展望 25

5.1 总结 25

5.1 展望 25

致 谢 28

摘 要

近来3D打印技术在越来越多的领域大放光彩，例如航天领域（可以缩短新部件的研发周期）、汽车零件制造、建筑、医疗、手办等。由于目前3D打印机其自身限制，所能够打印的实体模型的尺寸也有一定的限制。在工业制造领域，模型分割技术可以在很大程度上解决待加工零件或者模型因体积过大等造成的加工尺寸问题。模型分割，其目标不单是把大模型分割成适合加工要求的小型模型，更要方便后期的加工和装配。因此通过模型的分割处理，可以提升3D打印机的加工效率。

本文首先利用Python对STL文件进行读取和数据分析，然后对STL文件进行拓扑排序，然后对前人提出的一种基于机器学习的三维网格分割算法进行了改进。根据实验结果可知利用机器学习能够对实体网格模型进行分割，并且分割的结果在一定程度上是有意义的。机器学习分割后的效果取决于学习过程中数据量的规模，以及各种控制因子，在时代技术进步的今天，我们也可以利用机器学习达到对模型分割的效率和质量。

关键词：三维网格分割；STL文件处理；机器学习；

Abstract

In recent years, 3D printing applications are very broad, such as the aerospace field (which can shorten the development cycle of new parts), auto parts manufacturing, construction, medical, hand and so on. Due to the current size of the 3D printer can print a certain limit. In the field of industrial manufacturing, the model segmentation technology can solve the processing size problem of the part to be machined or the model is too large. Model segmentation, the goal is not only to split the large model into a small model suitable for processing requirements, but also to large-scale complex model is divided into simple, moderate size, easy processing and assembly of the sub-model. So the model segmentation can improve the processing capacity and efficiency of 3D printing equipment.

In this paper, we use Python to read and analyze STL files, then rank the STL files, and then improve the three-dimensional grid segmentation algorithm based on machine learning. According to the experimental results, it can be seen that machine learning can segment the three-dimensional grid model, and the result of segmentation is generally visual

Key Words：3D mesh segmentation；STL file processing；machine learning；

1 绪论

1.1 3D打印模型分割概述

三维网格模型分割是指使用网格模型的几何和拓扑特征，把网格划分为数量一定、样式简单的并且相互连通的子集合网格片。模型分割被广泛应用于三维建模、仿真设计、网格变形、动画制作、纹理映射等技术之中，三维模型有意义的分割则是理解和预处理的基础。

通常人类在对形状进行识别时，识别的一部分基于分割。例如，人类看到物体的第一印象之中往往包含着这个物体的三维特征例如高度、宽度、颜色、以及部分躯干之间的结构和连接。对模型的分割后的部分，大体上符合人类视觉习惯的部分体都可以算作有意义的分割。有意义的分割又对于具有明显占有优势特征的网格模型显来说，模型的存储和传输都是十分有意义的。

1.2本文的研究背景和意义

3D打印技术的优势是可以在很短的时间内将任意复杂的三维模型打印成实物模型。虽然其优点不言而喻，但不能忽略的是3D打印机与传统的加工设备一样，不能直接加工那些空间尺寸过大的模型。为了解决之一问题，可以先将大尺寸的原模型使用一定的方法分割成一组尺寸相对较小的模型部件，然后分别加工，最后进行拼接。

模型分割可以在很大程度上解决待打印的模型存在的体积过大等造成的问题。从现阶段的研究工作来看，大多数分割方法和目标以及应用领域不尽相同，在通用性上不强，忽略了分割效率和分割后的组合效率问题，不适应空间尺寸过大模型的快速成型。分割效率也难以保证，通常需要大量的人工操作。当今世界处在人工智能开始盛行的前夜，机器学习是人工智能的核心，也已经被应用到许多领域，和我们的生活息息相关。它是一门很多领域相互交叉的综合性学科，研究的是计算机如何去模拟或者代替人类的某些行为，通过现有的知识重新组织后不断改善。我们可以利用机器学习完成模型的分割，那些需要人工操作，并且工作量大，步骤繁琐的步骤就由计算机代替人类去完成。

同样的我们能否也让3D打印模型的分割实现自动化呢，并提高分割的质量、效率和解决分割后装配的效率低下的问题。答案是肯定得。

本文在前人的基础上改进了前期STL数据获取和计算的问题，利用机器学习来分割模型。基于Mac OS平台，使用Python对STL文件进行读取和数据分析，然后进行拓扑排序，利用处理好的数据，计算机器学习所需要的各种数据，最后训练计算机，让计算机拥有对三维网格模型分割的能力。本文实验的主要步骤如下。

Step1：搭建Python开发环境和安装本文所需基本Python库。

Step2：编写Python代码对STL文件进行处理。

Step3：计算模型的几何特征，包括曲率、形状直径、二面角等。

Step4：编写Adaboost分类器进行机器学习。最后对模型进行分割。

2 三维模型分割算法概述

2.1 三维模型分割概述

现阶段的三维模型数据来源主要有：点云、多面体和网格曲面。多面体是指由四个或四个以上多边形所围成的多面体。网格曲面即自由表面的一系列空间三角形或者是四边形的组合。三维网格模型即使用这样的三角形或四边形逼近或者无限逼近的三维实体。点云即表示模型的空间分布特征和表面特性的相同的空间参考系下的海量点集合。三维网格模型的优点明显，它表达实体模型的方式简单并且一致、模型单元的处理也十分方便。三维网格模型已经被广泛应用于快速成型技术、有限元分析等领域。现在通常使用STL 文件格式来描述三维模型，它使用三角形面片来逼近三维模型的表面。格式不是研究的重点问题，所以本文研究的是三维网络模型的分割^[4]。

常见的三维网格分割算法有分水岭算法、K均值算法、区域增长、Mean-Shift算法、模糊聚类法算法和层次集算法等。

上述提到的大多数算法都被应用于三维模型的分割，但是其结果不都是有意义的。这里给出三维模型分割的定义^[4]，设S 是具有n 个顶点的三维多边形网格模型。S₁，S₂，...，S_k是S的一个分割，每个S_i称为S的一个子块，当且仅当：

1．∀，1≤i≤k，S_i∈S；

2．∀i，S_i是连通的；

3．∀i，j，i≠j，1≤i，j≤k，S_i和S_j没有公共的面片，也就是他们的交集只能是顶点或者边；

4．；

2.2 国内外不同原理的三维模型分割算法

（1）分水岭分割算法

“分水岭”是指从相邻的两条河流或高地之间的地形出发的，两侧沿边坡登陆入不同的河流。在1982年，Serra^[5]提出了一个分水岭图像分割方法。基本思想是将图像视为地形。图像中像素的灰度值表示点的“高度”。而受影响地区称为盆地，局部最大值及其受影响区域变为峰值，其边界形成了分水岭（如图2.3所示）。 因此，图像被划分成一个独立的区域，边界相互连接在一起。

图2.3 分水岭示意图

1991年，Vincent等建立基本的计算方法，首先将二维图像分割推广并且应用于任何实体网格表面的特征分割问题。分水岭算法分为两个步骤:分拣过程和淹水过程。首先对每个顶点的高度函数进行排序，排序模式从低到高，然后在排序过程中实现洪泛过程，即对每个顶点使用先进先出的数据结构 h级本地高度确定和标记最小影响字段。由于分水岭算法表示输入图像的最大点，为了获得网格表面的边缘信息，通常使用顶点梯度作为输入数据，也就是如公式(1-1)所示：

基于分水岭方法的这一分割算法对弱边缘响应良好。但同时也会因为模型网格中的噪声、物体表面细微的曲率变化，而产生过度分割的现象。为消除分水岭算法可能产生的过度分割，一种方法是先验知识去除不相关的边缘信息；另一种方法可以消除一些微小变化，即修改梯度函数同时进行阈值处理。

（2）基于聚类分析的分割算法

该分割算法对于具有明显曲率变化的实体模型分割来说非常有效，但对于变化不明显的模型来说，它不能做任何事情。加兰等人在2001年提出了分层面片聚类方法，使用三角形面片之间的关系来执行表面网格的迭代合并，以分离模型的平面（如图2.4所示）。 算法的分割结果是一个区域，分可以看出分割的结果不适合3D模型的实体分割。

图2.4 聚类分析图

在 2002 年，Shlafman 等^[27]提出K 均值的聚类法。首先，算法确定每个簇的初始聚类中心; 再根据最小距离原则将样本集中的每个样本划分给一个簇; 再计算每个集群中所有样本的平均值，重新作为集群中心。重复操作，直到集群中心不再更改，这就是基于 K 均值的聚类法但是可能过分割。Katz 等^[26]在 2003 年提出了一种基于糊聚类的层次分割算法，很好地解决了过分割和边界锯齿^[4]（如图2.5所示）

图2.5 K均值分割效果图

设相邻两个三角面片f_i,f_j的测地距离为Geod(f_i,f_j)，角距离为AngDist(a_i,j)。

面片对偶图上的弧权重定义为：

将具有最大相对距离的两组三角形指定为初始分割集，并且针对每个分组集合计算属于集合的其他分块的概率，然后使用迭代将可能性概率的精度增加来把模型分割为两部分。 最后，把剩余的两个部分分为另一个分割集，以便构建分区集之间的准确边界，以获得最终的分割结果。因此聚类分析需要对数据进行多次迭代。当模型的网格密度较大时，计算复杂度增加。因此，对于体积巨大的网格模型来说，基于K均值的聚类分割是计算密集型和低效的。

（3）基于骨架提取的分割算法