三维模型分割方法、装置以及包含该装置的图像处理系统

摘要

提供一种用于对三维模型进行分割的方法，包括：有界平面生成步骤，用于根据输入的三维模型的三角形网格数据对所述三维模型中包含的所有三角形进行处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；轮廓图提取步骤，用于通过所述生成的有界平面来提取出所述三维模型的轮廓图；和轮廓图分割步骤，用于根据所述生成的有界平面的信息以及所述三维模型的顶点邻接图的信息，将所述提取出的轮廓图分割成一个子图或者至少两个相互不重叠的子图。还提供对三维模型进行分割的装置及其具有该装置的图像处理系统。通过本发明的方法、装置和系统，可提高三维模型分割的精确性和效率。

权利要求

1.一种用于在目标检测系统、局部匹配系统或模型检索系统中对作为所述目标检测系统、局部匹配系统或模型检索系统的输入的视频图像的三维模型进行分割的方法，包括：有界平面生成步骤，用于根据所述三维模型的三角形网格数据对所述三维模型中包含的所有三角形进行处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；

轮廓图提取步骤，用于通过所述生成的有界平面来提取出所述三维模型的轮廓图；和轮廓图分割步骤，用于根据所述生成的有界平面的信息以及所述三维模型的顶点邻接图的信息，将所述提取出的轮廓图分割成满足预定条件的一个子图或者至少两个相互不重叠的子图，其中，所述顶点邻接图通过以下方式构建：根据所述三维模型的三角形网格数据，以三维模型的顶点为节点，在被一个或多个三角形所共有的每两个顶点之间添加一条边，从而构建顶点邻接图，其中，所述预定条件包括以下中的任意一个：

该子图的顶点数量小于预定的第一阈值；

该子图含有的有界平面数量小于预定的第二阈值；

该子图含有的所有有界平面中不存在候选分割面；和

该子图中不存在可将与该子图对应的轮廓图分割为至少两个子图的候选分割面。

2.如权利要求1所述的方法，还包括在所述有界平面生成步骤之前的预分割步骤，用于根据所述三维模型的三角形网格数据中所包括的三角形数据和顶点数据，将该三维模型预分割成一个子模型或者至少两个相互分离的子模型，其中，所述方法对于所述子模型中的每一个子模型分别执行所述有界平面生成步骤、轮廓图提取步骤和轮廓图分割步骤，以便将每一个子模型都分割成满足预定条件的一个子图或者至少两个相互不重叠的子图。

3.如权利要求2所述的方法，其中，所述预分割步骤包括：

根据所述三维模型的三角形网格数据，构建顶点邻接图；

确定顶点邻接图是否为连通的，其中，如果顶点邻接图中的任意一对顶点之间都存在路径相连，则该图是连通的，否则不连通；和如果确定顶点邻接图不是连通的，则对应于顶点邻接图中的互不连接的子图来将三维模型分割为至少两个相互分离的子模型。

4.如权利要求2所述的方法，其中，所述预分割步骤包括：

根据所述三维模型的三角形网格数据，构建三角形邻接图；

确定三角形邻接图是否为连通的，其中，如果三角形邻接图中的任意一对三角形之间都存在路径相连则该图是连通的，否则不连通；

如果确定三角形邻接图不是连通的，则对应于三角形邻接图中的互不连接的子图来将三维模型分割为至少两个相互分离的子模型；

其中，所述三角形邻接图通过以下方式构建：

根据所述三维模型的三角形网格数据，以三维模型的中的三角形为节点，在拥有公共点的每两个三角形之间添加边，从而构建三角形邻接图。

5.如权利要求1-4中任一项所述的方法，还包括在所述轮廓图分割步骤之后的模型重建步骤，用于根据所述分割成的一个子图或者至少两个相互不重叠的子图以及所述三维模型的三角形网格数据来进行三角化处理，以便重建组成所述三维模型的、由三角形网格来表达的一系列立体部件。

6.根据权利要求1-4中任一项所述的方法，其中，所述有界平面生成步骤包括：将所述三维模型中包含的所有三角形中的每一个三角形作为子平面，使得满足聚合条件的子平面聚合成一个新的子平面，直到所有的子平面不能再聚合为止，从而生成广义平面；

对所述广义平面中的每一个进行如下处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；

对位于该广义平面上的三角形，创建三角形邻接图，如果在该邻接图中，该广义平面上的三角形可被划分到若干个分离的子平面中，且每个子平面包含多个相互连接的三角形时，则将该广义平面划分为所述若干个分离的子平面，其中，所述三角形邻接图通过以下方式构建：根据所述三维模型的三角形网格数据，以三维模型的中的三角形为节点，在拥有公共点的两个三角形之间添加边，从而构建三角形邻接图，如果在将该广义平面划分成的所述若干个分离的子平面中的两个或更多个子平面同时与另外的同一个平面相互连接，则将这些子平面组合起来作为一个组合的有界平面，由所述组合的有界平面以及将该广义平面划分成的所述若干个分离的子平面中的无需组合的有界平面共同组成所述的适用于对所述三维模型进行分割的有界平面，其中，当所述两个或更多个子平面分别与所述另外的同一个平面存在至少一个公共点时，该两个或更多个子平面被认为同时与该另外的同一个平面相互连接，以及其中，在顶点邻接图中，如果连接到某个子平面上的顶点处于该子平面的同一侧，则将该子平面作为是所述的无需组合的有界平面中的独立的有界平面。

7.根据权利要求6中所述的方法，其中，子平面可聚合的条件包括：所述子平面的法线方向相同或相反；以及

所述子平面的顶点处于同一个平面上，

其中，以与子平面相关的三角形的法线方向作为该子平面的法线方向。

8.根据权利要求1-4中任一项中所述的方法，其中轮廓图提取步骤通过以下方式提取出所述三维模型的轮廓图：以所述三维模型的顶点作为轮廓图的顶点，各个顶点之间不存在连接；

对于有界平面生成步骤所生成的每个有界平面，从有界平面生成步骤所生成的有界平面中查找与之相连接的有界平面，获取处于该有界平面和 与之相连接的有界平面的边界上的顶点，并将各顶点相互连接以得到若干线段；和在所得到的若干线段之中选择互不重叠的、与有界平面的内部边不同的线段作为轮廓线，以得到所述三维模型的轮廓图，其中，每条轮廓线至少要连接到两个不同的有界平面，而且在每一个有界平面内，都存在一个三角形使得它的某一条边包含该轮廓线，以及其中，内部边仅在一个有界平面内，或者被同一有界平面上的两个或多个三角形所共有。

9.一种在目标检测系统、局部匹配系统或模型检索系统中用于对作为所述目标检测系统、局部匹配系统或模型检索系统的输入的视频图像的三维模型进行分割的装置，包括：有界平面生成单元，用于根据所述三维模型的三角形网格数据对所述三维模型中包含的所有三角形进行处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；

轮廓图提取单元，用于通过所述生成的有界平面来提取出所述三维模型的轮廓图；

轮廓图分割单元，用于根据所述生成的有界平面的信息以及所述三维模型的顶点邻接图的信息，将所述提取出的轮廓图分割成满足预定条件的一个子图或者至少两个相互不重叠的子图，其中，所述顶点邻接图通过以下方式构建：根据所述三维模型的三角形网格数据，以三维模型的顶点为节点，在被一个或多个三角形所共有的每两个顶点之间添加一条边，从而构建顶点邻接图，其中，所述预定条件包括以下中的任意一个：

该子图的顶点数量小于预定的第一阈值；

该子图含有的有界平面数量小于预定的第二阈值；

该子图含有的所有有界平面中不存在候选分割面；和

该子图中不存在可将与该子图对应的轮廓图分割为至少两个子图的候选分割面。

10.一种图像处理系统，其包括如权利要求9所述的用于对三维模型进行分割的装置，其中所述图像处理系统是目标检测系统、局部匹配系统或模型检索系统。

说明书

三维模型分割方法、装置以及包含该装置的图像处理系统

技术领域

[0001] 本发明总体上说涉及图像处理的技术领域，更具体而言，涉及对三维模型进行分割的方法、装置以及包含该装置的图像处理系统。

背景技术

[0002] 随着计算机技术和计算机辅助设计CAD建模工具的发展，三维模型得以广泛使用。与此同时，三维模型越来越精细，数据量越来越大。为了有效地存储、处理、渲染、传输这些模型，三维模型分割技术引起了广泛关注。三维模型分割技术可将复杂的模型分割成为相对简单、数据量小的模型，进而单独处理这些数据量较小的模型，大大提高了存储、处理、渲染等工作效率；同时分割结果对输入模型给出了结构化的描述，便于模型管理和重复使用。

[0003] 到目前为止，已经提出了大量的模型分割技术。根据分割结果，这些技术可大体上分为两类：1、基于面片的技术；在这种技术中，三维网格被分割为一系列不同的面片基元，例如平面、柱面、球面等；这类技术可作为预处理手段，有助于提取模型的低层次特征；2、基于立体部件的技术；在这种技术中，三维网格被分割成一系列立体基元，如长方体、球体、锥体等；这类技术从较高层次上描述了输入模型的结构，在目标检测、局部匹配等领域具有很高的应用价值。下面通过引用相关文献对现有的模型分割技术进行逐一地简介。

[0004] 参考文献列表：

[0005] [非专利文献-1]作者为Besl，P.J.，Jain，R.，名称为：Segmentationthrough Variable-Order Surface Fitting，发表于IEEE PAMI，10(2)，1988，167-192；

[0006] [非专 利文 献-2]作者 为Garland，M.，Willmott，A.，Heckbert，P.S.，名称：Hierarchical Face Clustering on Polygonal Surfaces，发 表 于 Proceedingof Symposium on Interactive 3D Graphics，2001，214-223；

[0007] [非专利文献-3]作者为Zhang，Y.，Paik，J.，Koschan，A.，Abidi，M.A.，名称为：A Simple and Efficient Algorithm for Part Decomposition，发表于Proceeding of International Conference on Image Processing，2002，273-276；

[0008] [非专利文献-4]作者为S.Katz，G.leifman：A.Tal，名称为：Meshsegmentation using feature p oint and core extraction，发表于The VisualComputer，21(8-10)：865-875，2005；

[0009] [非专利文献-5]作者为R.Liu，H.Huang，名称为：Segmentation of3d meshes through spectral clustering，发表于Pacific conference onComputer graphics and applications，298-305，2004；

[0010] [非专利文献-6]作者为R.Seidel，名称为：A simple and fastincremental randomized algorithm for computing trapezoiddecompositions and for triangulating polygons，发表于ComputationalGeometry：Theory and Applications，Vol.1，No.1，51-64，1991；

[0011] [非专利文献-7]作者为Joseph O’Rourke，名称为：Computationalgeometry in C(second edition)，发表于Cambridge University Press，page.1-40；

[0012] [非专利文献-8]作者为Nina Amenta，Marshall Bern，ManolisKamvysselis，名称为：A new voronoi-based surface reconstructionalgorithm，发表于ACM SIGGRAPH，415-421，1998；

[0013] [非专利文献-9]作者为王志强，肖立瑾，名称为：多边形的简单性，方向及内外点的判别算法，发表于《计算机学报》，No.2，Vol.21，183-187，1998。

[0014] 作为现有的一种方法，[非专利文献-1]中的方法属于上述的第一类技术，本方法采用区域增长的方法对深度图进行分割。在这种方法中，首先计算出每个顶点对应的平均曲率和高斯曲率；然后根据曲率构建种子区域，并用二次多项式来表达；接着对每个种子区域，计算周围的顶点对该区域的隶属度，根据隶属度进行区域增长并更新种子区域，直到各个区域不再增长为止。由于曲率对局部噪声很敏感，该方法抗噪声能力较差。

[0015] 作为现有的一种方法，[非专利文献-2]中的方法属于上述第一类技术，本方法通过三角形聚类，从而达到分割的目的。在这种方法中，首先利用三角形之间的邻接关系建立对偶图，在对偶图中，每个三角形作为一个节点，初始状态下每个三角形面作为独立的聚类；然后计算对偶图中各条边的收缩指标；然后根据平面度、三角形间的方向差异等属性，将对偶图中的某些对偶边收缩，也即将对偶边连接的两个节点合并为1个，相邻的两个聚类从而合并成一个大的聚类，直到对偶图中的所有边不能收缩为止。

[0016] 作为现有的一种方法，[非专利文献-3]中的方法属于上述第二类技术。在本方法中，首先计算各个顶点对应的高斯曲率；然后根据设定的阈值，标记具有较大的负曲率的顶点作为边界点；然后，随机选择非边界点作为种子进行聚类，直到碰到边界顶点为止。这种方法易于实现，然而非常依赖于预先设定的阈值。

[0017] 作为现有的一种方法，[非专利文献-4]中的方法属于上述第二类技术。本方法将输入模型由粗到精逐渐分割为若干部分，这种方法引入了MDS(Multidimensional Sealing)变换，使得分割结果具有空间位置不变性，提出了一种鲁棒的特征点提取方法，从而将三维模型分割为若干部分，并且引入了割集方法进一步改善各个部分的边缘。该方法理论上可以得到不错的分割结果，然而计算量比较大，不利地影响了实际应用。

[0018] 作为现有的一种技术，[非专利文献-5]中的方法属于上述第二类技术。在该方法中，首先计算描述三维模型的各个面片之间相似度的对偶图，其中面片之间的相似度结合了面片之间的测地距离和角度距离；接着采取谱聚类的方法实现三维模型分割。这种方法需要预先设置聚类的数目，而且对于具有平滑边缘的模型可能得不到自然的分割结果。

[0019] 综合来看，现有的三维模型分割技术通常会应用到一些复杂的特征，诸如：曲率、三角形面间的测地距离、突起函数(Protrusion function)等。这些特征的精确计算比较困难，而且它们对局部噪声很敏感。目前的方法存在的主要问题有：1、对噪声敏感的特征诸如曲率的引入，使得技术抗噪声能力较弱；2、模型分割技术比较复杂，计算量比较大，影响分割效率，如[非专利文献-4]中的方法；3、采用目前的方法，分割得到的结果通常以面片或面片组合的方式来表达，而不是封闭的三维实体；4、早期的模型分割方法通常存在过分割的问题。

发明内容

[0020] 为了克服上述现有技术中的缺陷，本发明的目的在于提供对三维模型进行分割的方法、装置以及包含该装置的图像处理系统，使得能够对三维模型进行准确和高效的分割。

[0021] 根据本发明的实施例，提供一种用于对三维模型进行分割的方法，包括：有界平面生成步骤，用于根据输入的三维模型的三角形网格数据对所述三维模型中包含的所有三角形进行处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；轮廓图提取步骤，用于通过所述生成的有界平面来提取出所述三维模型的轮廓图；和轮廓图分割步骤，用于根据所述生成的有界平面的信息以及所述三维模型的顶点邻接图的信息，将所述提取出的轮廓图分割成一个子图或者至少两个相互不重叠的子图，其中，所述顶点邻接图通过以下方式构建：根据所述三维模型的三角形网格数据，以三维模型的顶点为节点，在被一个或多个三角形所共有的每两个顶点之间添加一条边，从而构建顶点邻接图。

[0022] 根据本发明的实施例，还提供一种用于对三维模型进行分割的装置，包括：有界平面生成单元，用于根据输入的三维模型的三角形网格数据对所述三维模型中包含的所有三角形进行处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；轮廓图提取单元，用于通过所述生成的有界平面来提取出所述三维模型的轮廓图；轮廓图分割单元，用于根据所述生成的有界平面的信息以及所述三维模型的顶点邻接图的信息，将所述提取出的轮廓图分割成一个子图或者至少两个相互不重叠的子图，其中，所述顶点邻接图通过以下方式构建：根据所述三维模型的三角形网格数据，以三维模型的顶点为节点，在被一个或多个三角形所共有的每两个顶点之间添加一条边，从而构建顶点邻接图。

[0023] 本发明的其他实施例还提供一种视频图像处理系统，其具有根据本发明的如上所述的用于分割三维模型的装置。这种图像处理系统例如是目标检测系统、局部匹配系统、模型检索系统。

[0024] 此外，本发明的其他实施例还提供一种存储有机器可读取的指令代码的程序产品，所述指令代码由机器读取并执行时，可执行如上所述的根据本发明的用于分割三维模型的方法。

[0025] 如上所述，根据本发明的实施例的三维模型分割方法和装置可将输入的三维模型由粗到细地逐层分割为若干部分，直到不能分割为止。且每个部分均为封闭的立体部件。从而使得可以对输入的三维模型进行有效地分割，并利用分割结果对输入的三维模型进行精确地分析和重构。

附图说明

[0026] 参照下面结合附图对本发明实施例的说明，会更加容易地理解本发明的以上和其它目的、特点和优点。附图中的部件不是成比例绘制的，而只是为了示出本发明的原理。在附图中，相同的或类似的技术特征或部件将采用相同或类似的附图标记来表示。

[0027] 图1是示出了根据本发明的实施例的用于对三维模型进行分割的方法的流程简图；

[0028] 图2a-2c是示出了在根据本发明的实施例的三维模型分割方法中，将待分割三维模型预先分割为若干个相互分离的子模型的示意性简图；

[0029] 图3a-3c是示出了在根据本发明的实施例的三维模型分割方法中进行有界平面提取的一个实例的示意图；

[0030] 图4a-4b是示出了在根据本发明的实施例的三维模型分割方法中进行轮廓图提取的一个实例的示意图；

[0031] 图5是示出了在根据本发明的实施例的三维模型分割方法中，根据提取到的有界平面、轮廓图等信息进行模型分割的一个实例的示意流程图；

[0032] 图6是示出了如图5中所示的流程图中步骤S510的处理的一个实例的示意流程图；

[0033] 图7是示出以图4中示出的有界平面1为分割面，对输入的三维模型进行分割而得到的各个子图均包含选定的分割面的一个实例的简图；

[0034] 图8a-8d是示出了在根据本发明的实施例的三维模型分割方法中，根据选定的候选分割面对输入三维模型进行分割得到的结果中存在子图位于选定分割面的一侧，但不含选定的分割面的情况的一个实例的简图；

[0035] 图9a-9c是示出了在根据本发明的实施例的三维模型分割方法中，根据选定的候选分割面对输入的三维模型进行分割得到的结果中存在跨越选定分割面的子图的情况的一个实例的简图；

[0036] 图10a-10c是示出了在根据本发明的实施例的三维模型分割方法中进行洞判别处理的一种情况的一个实例的简图；

[0037] 图11a-11b是示出了在根据本发明的实施例的三维模型分割方法中进行洞判别处理的另一种情况的一个实例的简图；

[0038] 图12a-12b是示出了在根据本发明的实施例的三维模型分割方法中中，对分割结果中的各个实体重新组织的示意图；

[0039] 图13是示出了根据本发明的实施例用于分割三维模型的装置的示意框图。

具体实施方式

[0040] 下面参照附图来说明本发明的实施例。在本发明的一个附图或一种实施方式中描述的元素和特征可以与一个或更多个其它附图或实施方式中示出的元素和特征相结合。应当注意，为了清楚的目的，附图和说明中省略了与本发明无关的、本领域普通技术人员已知的部件和处理的表示和描述。

[0041] 图1是示出了根据本发明的实施例对输入的待分割三维模型进行分割的方法的流程简图。如图所示，根据本发明的该实施例的分割三维模型的方法100开始于步骤S100。在有界平面生成步骤S110，根据输入的三维模型的三角形网格数据对该三维模型中包含的所有三角形进行处理，以生成至少一个适用于对该三维模型进行分割的有界平面。在轮廓图提取步骤S120，通过所生成的有界平面来提取出三维模型的轮廓图。在轮廓图分割步骤S130，根据所生成的有界平面的信息以及三维模型的顶点邻接图的信息，将所提取出的轮廓图分割成一个子图或者至少两个相互不重叠的子图。其中，顶点邻接图通过以下方式构建：根据三维模型的三角形网格数据，以三维模型的顶点为节点，在被一个或多个三角形所共有的每两个顶点之间添加一条边，从而构建顶点邻接图。

[0042] 下面将结合附图对各步骤进行详细描述。

[0043] 有界平面生成步骤S110的目的在于将组成模型表面的三角形合理组织，得到一系列(至少一个)适用于对三维模型进行分割的有界平面。根据本发明的该实施例，输入的三维模型需要以三角形网格来表达，基本数据元素包括模型的顶点和组成模型表面的三角形。输入的待分割三维模型可以具有各种形式，例如，通过扫描产生的点云模型、通过各种建模工具产生的参数化模型、或者以多边形(而不是三角形)网格表示的模型等等。在应用根据本发明的方法之前，首先需要将这些形式表达的三维模型转化为三角形网格的形式。可利用各种现有的方法实现这种转化。例如，若输入的是多边形表达的三维模型，可以应用上述的[非专利文献-7]所公开的方法将各个多边形转化为一系列三角形；若输入的是点云模型，可以利用上述的[非专利文献-8]中所述的方法将其转化为三角形网格的形式。有界平面可能由一个或多个封闭区域组成。

[0044] 该步骤主要由两个子步骤组成：1、通过组合所有的三角形，获取所有的广义平面；2、从获得的广义平面中，检测到所有的有界平面，便于后续的轮廓图提取、分割、重建等处理。

[0045] 在子步骤1中，首先初始化以三角形网格来表达的待分割三维模型中的每一个三角形，即，将每一个组成待分割模型表面的三角形作为一个子平面，有多少个三角形就有多少个子平面，其中以三角形的法线方向作为子平面的法线方向。三角形法线方向可由公知的计算公式计算得到，此处的法线方向指垂直于三角形平面且指向待分割三维模型外部的方向。然后，将满足聚合条件的子平面聚合成一个新的子平面，直到所有的子平面不能再聚合为止。在此，通过子平面聚合处理得到的平面称为“广义平面”。此处，子平面可聚合的条件是：(1)法线方向相同或相反；(2)顶点处于同一个平面上。

[0046] 图3a-3c是示出了在根据本发明的实施例的三维模型分割方法中进行有界平面提取的一个实例的示意图。图3a示出了一个三角形网格表达的三维模型，该模型含有20个顶点和36个三角形。图3b表示经过第一个子步骤后得到的广义平面，总共检测到10个广义平面。为了描述简洁清楚起见，图3b中仅示出了其中的三个广义平面，即，广义平面1，广义平面2和广义平面3。

[0047] 在子步骤2中，应用平面自身的几何特征以及平面间的关系等信息，将子步骤1得到的广义平面进行处理以得到一系列有界平面。有关平面自身的几何特征以及平面间的关系的信息包括：各平面上包括的顶点及其坐标，平面之间的连接关系，对于某一个平面，除了该平面上的顶点之外其他顶点与该平面的相对位置，各平面上的三角形数据等。以如前所述的方式对输入的三维模型进行了的三角形网格表达之后，就相应地可获得这些信息。当两个平面存在至少一个公共点时，两平面被认为相互连接。对所有检测到的广义平面中的每一个进行如下处理，直到所有的广义平面都不需处理为止。

[0048] 1)根据输入三维模型的三角形网格数据，对位于该广义平面上的三角形创建三角形邻接图。如果该三角形邻接图不连通时，即该广义平面上的三角形可被划分到若干个分离的子平面中，且每个子平面包含一个或多个相互连接的三角形(这些三角形具有至少一个公共点)时，该广义平面才需要处理，即，将该广义平面划分为若干个子平面。例如图3b中的广义平面1和广义平面2分别可以划分为两个互不相连的子平面，而广义平面3不需要进行这种划分。三角形邻接图是表达三角形连接关系的图。在创建三角形邻接图时，以三角形网格数据中包括的各个三角形作为节点，如果两个三角形拥有公共点，则在由该两个三角形表示的节点之间添加一条边，由此得到三角形邻接图。可以通过分别连接该两个三角形中的任意点，例如两个三角形的中点，来添加该边。如果三角形邻接图中的任意一对节点(即两个三角形)之间存在路径相连，则认为该三角形邻接图是连通的。这里的路径通常是由一条边或多条边组成的。

[0049] 2)如果通过上述处理1)获得的两个或多个子平面同时与另外同一个平面相连接，则这些子平面需要组合起来作为一个组合的有界平面，以方便模型分割。例如，在图3b中，子平面2-1和子平面2-2均与有界平面3相连接，因此这两个子平面被组合在一起成为一个组合的有界平面；而且沿着这个组合的有界平面，图3a-3c中所示的三维模型可被分割为两部分。在具体实施过程中，可通过迭代方式进行有界平面的检测处理，即，更新子步骤1产生的广义平面以使得平面的数目不再变化。因此在开始时，此处的“另外同一个平面”指的是子步骤1得到的广义平面，之后，此处的“另外一个平面”就可能是指已经更新得到的有界平面了。

[0050] 3)在通过上述处理1)获得的子平面中，对于某一子平面，在顶点邻接图中，如果连接到该子平面上的顶点处于该子平面的同一侧时，该子平面可以称为“独立的”有界平面，即，无需与其他平面进行组合的有界平面。例如，在图3b中，与子平面1-1相连接的四个顶点处于该子平面的同一侧，因此子平面1-1可作为独立的有界平面；同理平面1-2亦可称为独立的有界平面。然而，子平面2-1和子平面2-2不满足该条件，因此它们是有界平面但不是独立的有界平面。此外，图3b中的广义平面3也被认为是无需与其他子平面进行组合处理的有界平面(参见图3c)。在此，顶点邻接图是根据输入三维模型的三角形网格数据而构建的、描述顶点连接关系的图。在构建顶点邻接图时，以三维模型的顶点为节点，如果两个节点被一个或多个三角形(即，输入的三角形网格数据中包括的三角形)所共有，则在该两个节点之间添加一条边，从而构建出顶点邻接图。

[0051] 图3c给出了经过子步骤2处理后的结果，有界平面的数量为11个。其中广义平面1被划分为两个有界平面：分别与图3b中的子平面1-1和子平面1-2对应的有界平面11以及有界平面1，而其余有界平面分别与上述子步骤1得到的广义平面对应，即，其余平面保持不变。需要注意，为了描述清楚和简洁起见，图中并未示出全部的有界平面。

[0052] 可见，上述有界平面生成处理是采取迭代的方式进行的，即，对子步骤1中产生的广义平面进行更新，直到平面的数目不再变化为止，由此得到一个或者多个有界平面。此外，从上面的描述可知，“有界平面”是适用于对所述三维模型进行分割的，即，满足上述相应条件的平面。有界平面包括无需与其他平面进行组合的有界平面(例如图3c中的有界平面11，有界平面1和有界平面3)，以及包括对需要组合的子平面进行组合处理得到的组合的有界平面(例如图3c中的有界平面2)。

[0053] 本领域技术人员理解，取决于待分割的三维模型，有界平面生成步骤S110所生成的有界平面的数量可以是一个或者多个。

[0054] 下面将描述如图1中的所示的轮廓图提取步骤S120的细节。该步骤利用检测到的有界平面的数据，提取三维模型的轮廓并以图的方式表达之。在此过程中，根据有界平面之间的连接关系，判断处于相互连接的两平面边缘上的线段是否为轮廓线。最后，以模型顶点作为顶点，以提取到的轮廓线作为边，构建输入的待分割模型对应的轮廓图。每个有界平面的数据例如包括有关落在该面上的顶点、三角形、法线方向以及面积等的信息。

[0055] 在该步骤中，主要采用如下两个基本规则来确定轮廓线：1)内部边不能作为轮廓线。如果一条边仅在某一个有界平面内，或者被同一有界平面上的两个或多个三角形所共有时，该边被判定为内部边。2)每条轮廓线至少要连接到两个不同的有界平面，而且在每一个有界平面内，都存在一个三角形使得它的某一条边包含该轮廓线。

[0056] 按照上面两条原则，在轮廓提取过程中，首先初始化轮廓图，以输入的待分割三维模型的顶点作为轮廓图的顶点，顶点之间不存在连接，即，图中只有顶点没有边。然后采取以下步骤在相应顶点之间添加轮廓线，以得到输入三维模型的轮廓图。

[0057] 1)对每个有界平面，查找与之相连接的有界平面。例如，在图4a中，有界平面1和有界平面2存在四个公共点A、B、C和D，因此有界平面1和有界平面2相互连接。

[0058] 2)对每个有界平面，按照如下方式依次处理每一个与之相连接的有界平面，以提取轮廓线。

[0059] ●获取处于该有界平面和与之相连接的那个平面边界上的顶点，并根据这些顶点的位置，将它们排序。如图4a中，位于有界平面1和2边界上的顶点有4个，经过排序后，它们是A-B-C-D。

[0060] ●将排序后的顶点顺序连接。如图4a中，将落在有界平面1和2边界上的4个顶点：A、B、C和D顺序连接，得到3条线段即：AB，BC和CD。

[0061] ●对每一条线段，判断其是否满足轮廓线的条件。如果满足，在轮廓图中相应的两顶点之间添加连接的边。如图4a所示，线段B-C被有界平面2上的三角形T2-2和T2-3所共有，因此它是内部边，不能作为轮廓线；线段A-B被有界平面1的三角形T1-1的一条边所包含，同时被有界平面2上的三角形T2-1所包含，因此该线段满足轮廓线的条件，在轮廓图中节点A和B之间添加一条边；同理线段C-D也是轮廓线。

[0062] 上述的提取轮廓线的处理，是针对每一个有界平面都要进行的。此外，在上面的处理中，如图4a所示出的位于有界平面1和2边界上的顶点有4个，需要经过排序以得到A-B-C-D的有序组合。进行排序是为了减少所涉及的处理负荷，属于优化方案。也可以不对所获取的顶点进行排序。例如，在图4a-4b所示出的实例中，如果不对获得的顶点A，B，C，D进行排序，则将各个顶点任意连接后得到的线段的数量大于3，例如，除了线段AB，BC和CD之外还得到其余的线段AC，BA，DC等等。但是，这些其余的线段或者因为不满足上述的作为轮廓线的条件而被剔除，例如线段AC，或者因为是重叠的线段而被剔除，例如，线段BA，DC分别与线段AB，CD重叠，属于同一条边。因此，即使不对所获得的顶点进行排序，也可以得到输入三维模型的准确的轮廓图。

[0063] 下面将描述如图1中所示的轮廓图分割步骤S130的细节。

[0064] 该步骤的处理根据前面步骤的处理所获得的有界平面、顶点邻接图等信息，将从轮廓图提取步骤S120输入的轮廓图由粗到细，逐层分割分割为一个子图或者至少两个相互不重叠的子图。图5示出了在根据本发明的实施例的三维模型分割方法中，根据提取到的有界平面、轮廓图等信息进行模型分割的一个实例的示意流程图。如图5所示，在候选分割面检测步骤S500，从在前面的处理中检测到的有界平面中，查找所有候选分割面。对于任意一个候选分割面，输入三维模型的顶点分布在该候选分割面的两侧，即，该候选分割面可能将输入的三维模型分割为若干个部分。在模型分割步骤S510，逐一利用所查找到的候选分割面对输入的轮廓图进行分割，直到将输入的轮廓图分割为一个子图或者至少两个独立的子图为止，或者处理完所有的候选分割面为止。在终止条件判断步骤S520，对分割得到的各个子图，判断其是否需要继续分割。如果不需要，则直接输出该子图(S530)。否则，应用该子图含有的候选分割面对其继续分割(S540)。

[0065] 下面通过具体实例对图5中所示的各个步骤的处理进行详细描述。

[0066] 候选分割面检测步骤S500的目的在于从检测到的有界平面中，查找所有可能的适用于对三维模型进行分割的有界平面作为候选分割面。每个候选分割面必须满足两个条件：1)该候选分割面上顶点的数目不得小于4。如果顶点数目小于4，说明沿着该候选分割面进行模型分割时需要添加额外的顶点，处理会变得比较复杂。2)除了该候选分割面自身包含的顶点外，其他顶点分布在该候选分割面的两侧。这里所述的其他顶点指的是待分割三维模型的所有顶点中除了该候选分割面自身包含的顶点之外的顶点。作为优选实施方式，也可以只选择连接到该候选分割面的顶点作为其他顶点，这样，得到的候选面相对少一些，有助于减小处理复杂度。

[0067] 例如，如图4a-4b所示的三维模型包含20个顶点、36个三角形，通过有界平面检测步骤得到12个平面(为描述清楚和简洁起见，图中未全部示出)。其中，有界平面1上含有8个顶点，另外有4个顶点处于有界平面1的上方，8个顶点处于有界平面1的下方，因此有界平面1同时满足候选分割面的两个条件，有界平面1是一个候选分割面。而有界平面2上含有8个顶点，其余12个顶点均处于有界平面2的后侧，因此有界平面2不是候选分割面。通过该步骤的处理，图4a-4b所示的三维模型中含有1个候选分割面，即有界平面1。

[0068] 模型分割步骤S510的目的在于根据候选分割面，将输入的轮廓图分割为若干个互不重叠的子图。图6示出了如图5中所示的流程图中步骤S510的一个实例的示意流程图。可见，在该步骤的处理中，各个候选分割面被逐一尝试，直到输入的轮廓图被分割为至少两个子图，或者所有的候选分割面被处理完为止(即，利用所有的候选分割面进行分割都只将三维模型分割成一个子图的情形，后面将详细描述)。如图6所示，对于选定的某个候选分割面，首先通过该选定的候选分割面将轮廓图分割为一个子图或者至少两个分离的子图，且每个子图均含有该选定的候选分割面(步骤S610)；其次，判断前一步骤得到的子图是否含有洞，如果有，则处理洞，使得洞不能独立存在(步骤S620)；最后，采取参数化处理来控制分割结果(步骤S630)。下面将依次介绍各个步骤的处理。

[0069] 假设经过前面的处理，得到输入三维模型的候选分割面的数目为n个(n≥1)。对于n个候选分割面中的第i个选定的候选分割面，步骤S610的处理将输入的轮廓图沿着选定的第i个候选分割面分割为一个子图或者至少两个分离的子图，使得各个子图均含有该第i个选定的候选分割面。为实现该目的，该处理主要由以下三个过程完成。

[0070] 1)对由前面的轮廓图提取处理获得的轮廓图进行修正以得到修正的轮廓图。即，将位于选定的候选分割面上的轮廓线删除，为模型分割做准备。在如图4a-4b所示的三维模型中，假设以有界平面1为选定的候选分割面，该候选分割面上含有8个顶点；删除这8个顶点之间的边后，轮廓图变成如图7所示的轮廓图。在图7中，用实心方框和实心菱形标记属于该选定的候选分割面上的顶点。

[0071] 2)根据修正后轮廓图顶点之间的连接关系，将修正后的轮廓图分割为一个子图或者至少两个不连接的、即分离的子图。在此，如果一个子图中的顶点没有任意路径可以到达另一个子图中的顶点，则认为该两个子图是分离的。

[0072] 如图7所示，修正的轮廓图由两个互不连接的子图构成，因此可将输入模型的各个顶点按照它们之间的连接关系，划分到该两个子图中。子图1包含位于选定的候选分割面上的四个菱形顶点和位于选定的候选分割面上方的四个圆形顶点；子图2包含位于选定的候选分割面上的四个方框顶点和位于选定的候选分割面下方的八个星形顶点。

[0073] 在如图8b-8c所示的实例中，修正的轮廓图由三个互不连接的子图构成，相应地将输入模型的各个顶点划分到三个子图中去，分别以菱形、圆形和星形标记。

[0074] 在如图9b-9c所示的实例中，修正的轮廓图由三个互不连接的子图构成，输入模型的各个顶点相应地被划分到三个子图中去，分别以菱形、圆形和星形标记。

[0075] 在如图10b所示的实例中，根据选定的候选分割面，输入轮廓图可分割为四个子图，标记为子图1、2、3和4。

[0076] 在如图11b所示的实例中，根据选定的候选分割面，输入轮廓图分割为两个子图，标记为子图1和子图2。

[0077] 3)对上述过程2得到的各个子图，进行必要的再组织，使得所有子图都含有选定的分割面。

[0078] 根据是否包含选定的候选分割面，前一过程2得到的各个子图可以分为两类：第一类含有选定的候选分割面；第二类不含有选定的候选分割面。如果前一步骤中所有的子图均属于第一类时，则这些子图不需要重新处理。

[0079] 例如图7所示，子图1和子图2均包含选定分割面，因此这些子图不需要进一步处理。图10b和图11b所示的各个子图都包含选定的分割面，因此这些子图也不需要这一步的处理。

[0080] 如图8c所示的三维模型中，根据选定的候选分割面，可以得到三个子图：子图1、子图2和子图3。子图1和子图3包括图8a标记的候选分割面，属于第一类；而子图2不包含选定的候选分割面，属于第二类。因此，该分割结果需要进一步处理。

[0081] 图9a-9c所示模型根据选定的候选分割面，可以得到三个子图：子图1、子图2和子图3。其中子图1和子图3包含图9a标记的候选分割面，属于第一类；而子图2不包含选定的候选分割面，属于第二类。因此，该分割结果需要进一步处理。

[0082] 当存在属于第二类的子图时，这些子图需要处理。对第二类的子图，按照如下两种情况分别来处理。

[0083] 1)该子图的各个顶点完全处于选定的分割面一侧。通过顶点邻接图或被分割以得到该子图的轮廓图，将该子图和与其相连接的且处于同侧的子图重新组合得到一个新的子图，并将该子图从第二类子图中去除。在此，子图与子图相连接指的是顶点邻接图或被分割以得到该子图的原始轮廓图中这些子图的顶点之间存在连接，即，具有至少一个公共点。

[0084] 在图8c示出的实例中，三个子图与选定的分割面的关系分别为：子图1的各个顶点位于选定分割面的上方，子图2和子图3的各个顶点处于选定分割图的下方；与此同时，通过顶点邻接图，子图2与另外两个子图顶点之间存在连接。因此，将子图2与子图3合并，组成一个新的子图。子图2不与子图1合并，因为子图2与子图1不在同侧。这时，图8所示模型可以分为如图8d所示的两个部分，并且这两个部分均包括选定的分割面，可见图8d中的子图1′对应于子图8c中的子图1，而子图2′对应于图8c中的子图2和3组合得到的子图。

[0085] 2)该子图的顶点分布在选定的候选分割面的两侧，而且通过顶点邻接图或被分割以得到该子图的轮廓图，与属于第一类的子图相连接，则将该子图和与其相连接的第一类的各个子图重新组合为一个新的子图，将该子图从第二类子图中删除。

[0086] 在如图9c示出的实例中，三个子图与候选分割面的关系为：子图1的顶点处于选定的候选分割面上方，子图2的顶点分布在选定的获选分割面两侧，子图3的顶点处于选定分割面的下方。与此同时，子图2的顶点通过顶点邻接图连接到子图1和子图3的顶点。因此，子图2将和子图1、3合并，组成一个新的子图。因此，图9所示的三维模型利用选定的候选分割面进行分割处理后得到一个子图，即，与输入的待分割三维模型相应的子图。当然，也可以采用其他方式将图9a-9c中示出的模型分割成至少两个子图，但这不在本发明讨论的范围内，在此不再详述。

[0087] 接下来，步骤S620依据步骤S610得到的各个子图之间的关系，以及它们与选定的候选分割面之间的位置关系，判断各个子图是否对应于洞，然后处理洞以保持输入模型的形状在分割后不发生改变。如果存在洞，则将洞和其最近的实体结合起来，使得分割结果中不存在独立的洞。为此，步骤S620的处理包括三个子步骤：1、对每个子图，根据其轮廓信息，获取它们在选定的分割面上对应的有界区域；2、对每个子图，判断其是否为洞；3、对被判定为洞的子图进行处理。下面将依次介绍这三个子步骤。

[0088] 1)对前一步骤S610获取的各个子图，获取它们在选定的分割面上的各个区域。

[0089] 对每个子图，根据其落在选定的候选分割面上的轮廓线信息，获取封闭区域，即，轮廓线闭合的区域。对于轮廓线不闭合的情况，例如可以采取本领域公知的顶点凸包方法来获取近似的封闭区域，或者采取现有的其他方法来获取相对精确的封闭区域。具体细节在此不再赘述。

[0090] 通过本步骤，例如对于图10b所示的四个子图，可以获取如图10c所示的四个封闭区域。

[0091] 2)本子步骤利用在上一子步骤中获得的子图在选定的候选分割面上的各个封闭区域之间的关系，以及各个子图与选定的候选分割面之间的关系，实现洞的识别。在这个步骤中，根据各个子图落在选定的候选分割面上的封闭区域之间的关系，由外而内逐一判断。

[0092] 首先将最外面的封闭区域对应的子图判定为实体。此处，实体是区别于洞而言的。这一规则是符合实际情况的。根据这一原则，在如图10b所示的实例中，子图1对应的部分被判定为实体；对图11b所示的两个子图而言，子图1落在选定的候选分割面上的封闭区域在子图2相应的封闭区域的外侧，因此子图1对应的部分被判定为是实体。

[0093] 下面介绍除了最外面的封闭区域对应的子图以外的其它子图的判别方法。为使得介绍清楚、简洁，首先定义与某一个子图最近的子图这一概念。对某一个子图A而言，其最近的子图B首先必须是一个实体，同时子图B对应的区域必须包含子图A对应的区域而且是所有包含子图A对应区域的区域中最小的。如图10c所示，对于子图3而言，子图1就是其对应的最近的子图，因为子图1对应的区域是包含子图3对应区域的所有区域中最小的，而且子图1对应的部分是实体。同理，子图1也是子图2和4所对应的最近的子图。

[0094] 根据某一子图和与其最近的子图之间的关系，以及它们与选定的分割面的位置关系，按照如下原则确定该子图是否代表一个洞。

[0095] ●如果该子图和与其最近的子图的各个顶点，相对于选定的候选分割面而言，处于完全相反的位置，则该子图被判定为实体。如图10c所示，除选定的候选分割面上的各个顶点外，子图3的各个顶点完全处于选定分割面的前方，而子图1的各个顶点完全处于选定分割面的后方，因此子图3对应的部分被判断为实体。

[0096] ●如果该子图和与其最近的子图的各个顶点，相对于选定的分割面而言，处于同一侧，则该子图被判定为洞。如图10c所示，除选定的分割面上的各个顶点外，子图2的各个顶点位于选定的分割面的后方，同时子图1的各个顶点也处于选定分割面的后方，因此子图2对应的部分被判定为洞。同理，子图4对应的部分被也被判定为洞。

[0097] ●以上两条原则都不满足时，则应用下面这条原则：以选定的候选分割面为基准，如果从该子图处于该选定分割面上的顶点出发，连接到其他有界平面上的有向线段与该选定的候选分割面的法线向量处于选定的候选分割面的两侧时，则该子图对应的部分被判定为洞，否则被判定为实体。此处的连接是指通过轮廓线相连，即，由属于该子图且位于选定的候选分割面上的顶点出发，到其他有界平面上的顶点为止的连线。在此，默认有界平面的法线方向指向模型表面的外侧。如图11b所示，从子图2处于选定分割面上的顶点出发，连接到其他有界平面上的轮廓线(以点划线表示)和选定的分割面的法线向量(以实线表示)在该选定的候选分割面的两侧，即，一个处于该选定的候选分割面下侧，一个位于其上侧，因此子图2对应的部分被判定为洞。

[0098] 3)在对洞的处理的子步骤中，为保持输入三维模型的形状，需要将各个洞和与其最近的子图组合在一起，使得分割结果中不存在独立的洞。如图10c所示，子图2和子图4将被组合到子图1中去，成为一个新的实体。图11b中所示的子图2将被组合到子图1中去，成为一个新的实体。

[0099] 然后，将只包含在洞内的有界平面设置为非候选分割面，这样做可以防止洞被切分，同时可以减少模型分割的复杂度和处理负荷。

[0100] 在图6的流程图中的步骤S630中执行参数化控制处理。根据应用的不同，这一步骤可设置参数，对分割结果进行控制，例如使得只有小的部分或者只有大的部分才能从输入的三维模型中被分割出来。例如，为判断某一子图A是否能被分割出来，以子图A和与其最近的子图在选定的候选分割面上相应的封闭区域的面积之间的比值为参数，如果该比值小于某一预先设定的阈值，则子图A能被分割出来，否则子图A需要和与其最近的子图组合称为一个新的子图，而不能作为独立的部分被分割出来。

[0101] 下面，通过一个实例来具体说明。如图12所示，实体1在选定的候选分割面上的对应封闭区域的面积计算为Area1＝392.994，而实体2在分割面上的对应封闭区域的面积为Area2＝119.56，则Area2/Area1＝0.3。当用户设定的阈值小于0.3时，实体2就不能被分割出来，而同实体1组合在一起成为一个物体；如果用户设定的阈值大于或等于0.3时，实体2与实体1分别作为两个物体被分割出来。需要注意，图12中的模型与图10中的模型对应。上面提到，在图10中，两个子图2和4都被判定为洞且与子图1组合。因此，在图12中的实体1是指由图10中子图1+2+4构成的新的实体。

[0102] 本领域技术人员理解，还可以设置其他参数来表示三维模型中物体的“大”和“小”。例如，可以通过对子图所对应的部分的体积大小之间的比值来确定相应的部分能否从输入三维模型中被分割出来。

[0103] 步骤S630中的参数化控制处理并不是必须的。这种处理是为了增强模型分割的灵活性，因此属于一种优化方案。例如，通过设置相关参数和阈值，可以控制三维模型分割的“粒度”，即，从三维模型中分割出来的子模型是多一些还是少一些。显然，这可以根据实际需要进行相应调整。

[0104] 接着，在图6的流程图中的步骤S640判断通过利用第i个选定的候选分割面进行上述的分割处理后所得到的子图的数目是否大于“1”，即，是否将输入三维模型分割成至少两个子图。如果步骤S640的判断结果为“是”，则在步骤S650输出分割得到的子图，并且流程回到图5中的步骤S520。如果步骤S640的判断结果为“否”，即，通过利用第i个选定的候选分割面进行上述的分割处理后所得到的子图的数目不大于“1”(等于1)，则令i＝i+1(步骤S660)，并利用第(i+1)个选定的候选分割面，重复执行步骤S610-S640的处理。如果利用了n个候选分割面中的所有分割面进行分割，都没有将三维模型分割成至少两个子图，即，都只是将输入三维模型分割成一个子图(步骤S680)，则流程也回到图5中的步骤S520。例如，图10a-10c中示出的情形就是将输入三维模型分割成一个子图，即，与该三维模型本身对应的子图。从图6可看出，只要n个候选分割面中任意一个分割面可将三维模型分割成至少两个互相不重叠的子图，就进入图5中的步骤S520判断是否针对这些子图的分割结果终止分割，而不再利用n个候选分割面中的其他分割面分别对三维模型进行分割处理。本领域技术人员理解，作为可替选方案，也可以依次利用n个候选分割面中的每一个分割面都来进行如上所述的分割输入三维模型的处理，所得到的与各个候选分割面对应的各种分割结果可根据实际需要进行选择使用。

[0105] 此外，在上述的利用候选分割面对三维模型进行分割的处理中，也可以不查找候选分割面，而是直接应用在前面的处理中检测到的所有有界平面作为分割面来对三维模型的轮廓图进行分割。其处理方式以上述利用候选分割面的分割处理方式类似，在此不再赘述。

[0106] 再回到图5的流程，在步骤S520，对图6中步骤S650或S680的处理获得的子图进行终止条件的判断，以确定该子图是否需要继续分割，即，是否满足终止分割的条件。可采取如下准则进行判断，如果某一子图满足下面规则的任意一项，则该子图不需要继续分割。

[0107] ●该子图的顶点数目小于8。因为任意三维物体至少要包含4个不共面的顶点。例如三棱锥不能被分割。在此，数字“4”是模型可分割所允许的最小数字，其可以根据实际情况进行修改。

[0108] ●该子图的面的数目小于6。因为任意三维物体至少要包含4个不同的平面。例如三棱锥不能被分割。数字“4”是模型可分割所允许的最小数字，其可以根据实际情况进行修改。

[0109] ●该子图的所有有界平面中，不存在候选分割面。如图7中的子图1含有的六个有界平面中，不存在候选分割面。同理如图7所示的子图2，如图8所示的子图1均不含有候选分割面。

[0110] ●虽然该子图含有候选分割面，但所有候选分割面都不能将该子图分割为两个或更多个部分。如图11的模型中，子图1虽然含有候选分割面，但是通过该分割面不能将该子图分割为两个或多个部分，则该模型亦不能继续分割。

[0111] 如果步骤S520的判断确定需要对某子图进行继续分割，则应用该子图含有的候选分割面对其继续分割(S540)，即，以该子图含有的候选分割面作为选定的候选分割面，对该子图所对应的轮廓图进行分割，直到将与该子图所对应的轮廓图分割为至少两个相互不重叠的子图。对子图进行接续分割的具体处理方式与上述参照图5-6描述的分割处理类似，在此不再赘述。

[0112] 上面已经结合各附图对根据本发明的实施例的对三维模型进行分割的方法进行了详细描述。作为可替选的实施方式，在示出了根据本发明的实施例的用于对三维模型进行分割的方法的流程简图的图1中执行有界平面生成步骤S110图之前，还可以执行三维模型预分割步骤。该步骤的目的在于将输入的由三角形网格描述的三维模型分割为若干个独立的、互不相连的部分。该步骤的处理尤其适用于一个场景中摆放着多个独立的物体的情况。在该步骤的处理中，首先根据输入三维模型的三角形网格数据，构建顶点邻接图。然后，判断顶点邻接图是否是连通的：如果顶点邻接图中的任意一对节点之间存在路径相连，则该图是连通的，否则不连通。这里的路径通常是指由一条边或多条边组成的。如果顶点邻接图不是连通的，即邻接图由若干个互不连接的、分离的子图组成，则对应于这些子图，输入三维模型可分割为若干互不连接的子模型。如果顶点邻接图是连通的，则输入的待分割三维模型在预分割步骤中不被分割，仍是一个三维模型。

[0113] 图2a-2c是示出了在根据本发明的实施例的三维模型分割方法中，将待分割三维模型预先分割为若干个相互分离的子模型的一个实例的示意性简图。图2a表示输入的待分割三维模型，图2b表示所创建的顶点邻接图，可见顶点邻接图由四个互不相连的、分离的子图组成。相应地，图2a的模型可以被分割成如图2c所示的4个独立的子模型。

[0114] 作为可替选方案，也可以采用三角形邻接图来实现上述的模型预分割的处理。当三角形邻接图不连通时，可以将输入的三维模型分割为若干个独立的子模型。从上面对根据本发明的具体实施例的描述可知，待分割三维模型包含两部分基本数据：模型顶点以及组成模型表面的三角形。如果将三角形邻接图分割成几个分离的子图，也即将组成三维模型表面的三角形进行划分，则可以实现模型顶点的划分；如果将顶点邻接图分割为几个分离的子图，也即将模型顶点进行划分，则可以实现组成输入模型表面的三角形的划分。因此，采用三角形邻接图来实现模型预分割处理与上述的采用顶点邻接图来实现模型预分割处理是类似的，在此不再赘述。

[0115] 如果输入的模型经过预分割被分割成多个三维子模型，则对每个分割得到的三维子模型进行如上所述的处理。容易理解，这种预分割处理有助于降低后续处理的计算量和复杂度，因此是一种优化处理。如果不执行模型预分割的处理，也并不影响根据本发明的三维模型的分割的实现。

[0116] 作为另一个可替换实施方式，在图1的流程图的步骤S130之后，还可以执行三维模型的轮廓图重建处理。在该轮廓图重建处理中，根据从步骤S120获得的输入三维模型的轮廓图，以及该轮廓图含有的有界平面的信息，对通过利用选定的候选分割面对三维模型分割得到的各个子图进行处理，从而重建出构成待分割三维模型的相应的立体部件，并以三角形网格的形式表达之。如上所述，在利用选定的候选分割面进行模型分割的过程中，选定的候选分割面以及其它的部分有界平面会发生变化，这些有界平面需要重新三角化才能确保三维模型的封闭性。与此同时，没有发生变化的有界平面的数据可以直接使用，从而减少重建的处理负荷。此外，输入三维模型的原始的三角形网格数据有助于矫正新生成的三角形的方向。

[0117] 具体而言，对于在分割过程中产生变化的有界平面，可采取与前述的对判定为洞的子图进行处理类似的处理方法，得到该有界平面上的封闭区域并以多边形表达之。然后可以采用现有的各种多边形三角化技术，得到一系列三角形。例如，可以采用上述[非专利文献6]中介绍的方法，该方法可实现简单多边形(包括凹多边形和凸多边形)和复杂多边形(含有洞的多边形)的三角化。在应用该方法之前，首先需要判断各个多边形的方向以及多边形之间的包含关系，从而适当组织各个多边形使得最外围的多边形的方向为逆时针，而内部的多边形的方向为顺时针。例如，可以利用上述[非专利文献-9]中公开的方法来判断多边形的方向。在对所有发生变化的有界平面完成重建处理后，根据三维模型的原始三角形网格数据，对新产生的三角形的方向进行矫正，使得所有三角形的法线方向指向三维模型表面的外侧。

[0118] 经过三维模型的轮廓图重建处理，可得到构成输入的待分割三维模型的、由三角形网格表达的一系列封闭的立体部件。

[0119] 在此需要说明，虽然为了更为清楚地描述根据本发明实施例的分割三维模型的方法，其中各个处理步骤是结合不同附图中不同模型实例分别进行说明的，但是，本领域技术人员了解，对上述各附图中提及的每一种模型，都能够通过根据本发明的这种分割三维模型的方法来进行分割处理。其中的细节不再赘述。

[0120] 根据本发明的其他实施例，还提供了一种用于对三维模型进行分割的装置。图13是示出了根据本发明的一个实施例用于分割三维模型的装置的示意框图。如图所示，该用于分割三维模型的装置1000包括：有界平面生成单元1200，用于根据输入的三维模型的三角形网格数据对三维模型中包含的所有三角形进行处理，以生成至少一个适用于对三维模型进行分割的有界平面；轮廓图提取单元1300，用于通过所生成的有界平面来提取出三维模型的轮廓图；轮廓图分割单元1400，用于根据所生成的有界平面的信息以及三维模型的顶点邻接图的信息，将所提取出的轮廓图分割成一个子图或者至少两个相互不重叠的子图。

[0121] 作为可替选实施方式，图13中的用于分割三维模型的装置1000还可以包括预分割单元1100，用于根据输入的三维模型的三角形网格数据中所包括的三角形数据和顶点数据，将该输入三维模型预分割成一个子模型或者至少两个相互分离的子模型。有界平面生成单元1200、轮廓图提取单元1300和轮廓图分割单元1400对于预分割单元1100生成的一个子模型或者至少两个相互分离的子模型中的每一个执行相应处理，以便将每一个子模型都分割成一个子图或者至少两个相互不重叠的子图。

[0122] 作为另一种可替选实施方式，图13中的用于分割三维模型的装置1000还可以包括模型重建单元1500，用于根据所分割成的一个子图或者至少两个相互不重叠的子图以及三维模型的三角形网格数据来进行三角化处理，以便重建组成该三维模型的、由三角形网格来表达的一系列立体部件。

[0123] 本领域技术人员了解，如图13中示出的装置1000所包括的有界平面生成单元1200，轮廓图提取单元1300，轮廓图分割单元1400，以及预分割单元1100和模型重建单元
1500可以被配置成执行上面结合图1，5，6描述的各种处理，以及虽然没有在这些附图中示出但是已经在上面的各种具体实例中充分描述的用于分割三维模型的方法。

[0124] 上述装置中各个组成单元可通过软件、硬件或其组合的方式进行配置。配置可使用的具体手段或方式为本领域技术人员所熟知，在此不再赘述。

[0125] 本发明的其他实施例还提出了一种图像处理系统，其配备有根据上述图13示出的根据本发明的实施例的用于对三维模型进行分割的装置，因此可用于实现上述的根据本发明的实施例的对三维模型进行分割的方法。

[0126] 这种图像处理系统例如可以是目标检测系统、局部匹配系统、模型检索系统，等等。

[0127] 此外，根据本发明上述实施例的用于对三维模型进行分割的方法可以通过存储有机器可读取的指令代码的程序产品进来实现。这些指令代码由机器例如计算机读取并执行时，可执行根据本发明上述实施例的对三维模型进行分割的方法的各个操作过程和步骤。该程序产品可以具有任意的表现形式，例如，目标程序、解释器执行的程序或者提供给操作系统的脚本程序等。

[0128] 相应地，用于承载上述存储有机器可读取的指令代码的程序产品的存储介质也包括在本发明的公开中。所述存储介质包括但不限于软盘、光盘、磁光盘、存储卡、存储棒，等等。

[0129] (附记1)：一种用于对三维模型进行分割的方法，包括：

[0130] 有界平面生成步骤，用于根据输入的三维模型的三角形网格数据对所述三维模型中包含的所有三角形进行处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；

[0131] 轮廓图提取步骤，用于通过所述生成的有界平面来提取出所述三维模型的轮廓图；和

[0132] 轮廓图分割步骤，用于根据所述生成的有界平面的信息以及所述三维模型的顶点邻接图的信息，将所述提取出的轮廓图分割成满足预定条件的一个子图或者至少两个相互不重叠的子图，其中，所述顶点邻接图通过以下方式构建：

[0133] 根据所述三维模型的三角形网格数据，以三维模型的顶点为节点，在被一个或多个三角形所共有的每两个顶点之间添加一条边，从而构建顶点邻接图。

[0134] (附记2)：如附记1所述的方法，还包括在所述有界平面生成步骤之前的预分割步骤，用于根据输入的三维模型的三角形网格数据中所包括的三角形数据和顶点数据，将该输入三维模型预分割成一个子模型或者至少两个相互分离的子模型，其中，所述方法对于所述子模型中的每一个子模型分别执行所述有界平面生成步骤、轮廓图提取步骤和轮廓图分割步骤，以便将每一个子模型都分割成满足预定条件的一个子图或者至少两个相互不重叠的子图。

[0135] (附记3)：如附记2所述的方法，其中，所述预分割步骤包括：

[0136] 根据所述三维模型的三角形网格数据，构建顶点邻接图；

[0137] 确定顶点邻接图是否为连通的，其中，如果顶点邻接图中的任意一对顶点之间都存在路径相连，则该图是连通的，否则不连通；和

[0138] 如果确定顶点邻接图不是连通的，则对应于顶点邻接图中的互不连接的子图来将三维模型分割为至少两个相互分离的子模型。

[0139] (附记4)：如附记2所述的方法，其中，所述预分割步骤包括：

[0140] 根据所述三维模型的三角形网格数据，构建三角形邻接图；

[0141] 确定三角形邻接图是否为连通的，其中，如果三角形邻接图中的任意一对三角形之间都存在路径相连则该图是连通的，否则不连通；

[0142] 如果确定三角形邻接图不是连通的，则对应于三角形邻接图中的互不连接的子图来将三维模型分割为至少两个相互分离的子模型；

[0143] 其中，所述三角形邻接图通过以下方式构建：

[0144] 根据所述三维模型的三角形网格数据，以三维模型的中的三角形为节点，在拥有公共点的每两个三角形之间添加边，从而构建三角形邻接图。

[0145] (附记5)：如附记1-4中任一项所述的方法，还包括在所述轮廓图分割步骤之后的模型重建步骤，用于根据所述分割成的一个子图或者至少两个相互不重叠的子图以及所述三维模型的三角形网格数据来进行三角化处理，以便重建组成所述三维模型的、由三角形网格来表达的一系列立体部件。

[0146] (附记6)：根据附记1-5中任一项所述的方法，其中，所述有界平面生成步骤包括：

[0147] 将所述三维模型中包含的所有三角形中的每一个三角形作为子平面，使得满足聚合条件的子平面聚合成一个新的子平面，直到所有的子平面不能再聚合为止，从而生成广义平面；

[0148] 对所述广义平面中的每一个进行如下处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；

[0149] 对位于该广义平面上的三角形，创建三角形邻接图，如果在该邻接图中，该广义平面上的三角形可被划分到若干个分离的子平面中，且每个子平面包含多个相互连接的三角形时，则将该广义平面划分为所述若干个分离的子平面，其中，所述三角形邻接图通过以下方式构建：

[0150] 根据所述三维模型的三角形网格数据，以三维模型的中的三角形为节点，在拥有公共点的两个三角形之间添加边，从而构建三角形邻接图，

[0151] 如果在将该广义平面划分成的所述若干个分离的子平面中的两个或更多个子平面同时与另外的同一个平面相互连接，则将这些子平面组合起来作为一个组合的有界平面，由所述组合的有界平面以及将该广义平面划分成的所述若干个分离的子平面中的无需组合的有界平面共同组成所述的适用于对所述三维模型进行分割的有界平面，其中，当所述两个或更多个子平面分别与所述另外的同一个平面存在至少一个公共点时，该两个或多个子平面被认为同时与该另外的同一个平面相互连接，以及其中，在顶点邻接图中，如果连接到某个子平面上的顶点处于该子平面的同一侧，则将该子平面作为是所述的无需组合的有界平面中的独立的有界平面。

[0152] (附记7)：根据附记6中所述的方法，其中，子平面可聚合的条件包括：

[0153] 所述子平面的法线方向相同或相反；以及

[0154] 所述子平面的顶点处于同一个平面上，

[0155] 其中，以与子平面相关的三角形的法线方向作为该子平面的法线方向。

[0156] (附记8)：根据附记1-7中任一项中所述的方法，其中轮廓图提取步骤通过以下方式提取出所述三维模型的轮廓图：

[0157] 以所述三维模型的顶点作为轮廓图的顶点，各个顶点之间不存在连接；

[0158] 对于有界平面生成步骤所生成的每个有界平面，从有界平面生成步骤所生成的有界平面中查找与之相连接的有界平面，获取处于该有界平面和与之相连接的有界平面的边界上的顶点，并将各顶点相互连接以得到若干线段；和

[0159] 在所得到的若干线段之中选择互不重叠的、与有界平面的内部边不同的线段作为轮廓线，以得到所述三维模型的轮廓图，其中，每条轮廓线至少要连接到两个不同的有界平面，而且在每一个有界平面内，都存在一个三角形使得它的某一条边包含该轮廓线，以及其中，内部边仅在一个有界平面内，或者被同一有界平面上的两个或多个三角形所共有。

[0160] (附记9)：根据附记1-8中任一项中所述的方法，其中所述轮廓图分割步骤包括：

[0161] 候选分割面检测子步骤，用于从所生成的有界平面中，查找所有候选分割面，其中，对于任意一个候选分割面，其顶点的数目大于等于4，并且所述三维模型的顶点分布在该候选分割面的两侧；

[0162] 模型分割子步骤，用于逐一利用所检测到的候选分割面中的分割面作为选定的候选分割面来对所述轮廓图进行分割，直到将所述轮廓图分割为一个子图或至少两个相互不重叠的子图；和

[0163] 终止条件判断子步骤，对模型分割子步骤得到的各个子图，判断其是否需要继续分割，如果需要，则以该子图含有的候选分割面作为选定的候选分割面，对该子图所对应的轮廓图进行分割，直到将与该子图所对应的轮廓图分割为至少两个相互不重叠的子图。

[0164] (附记10)：根据附记9中所述的方法，其中所述模型分割子步骤包括通过选定的候选分割面来执行以下处理：

[0165] 通过该选定的候选分割面将轮廓图分割为一个子图或至少两个相互不重叠的子图，使得所有子图都包含该选定的候选分割面；

[0166] 将所得到的子图中被判断为洞的子图和与该子图的最近的、作为实体的子图结合起来，以便获得新的实体；和

[0167] 对分割得到的各个实体进行处理，以便确定将哪些实体作为分割的结果。

[0168] (附记11)：根据附记10中所述的方法，其中，所述的通过所述选定的候选分割面将轮廓图分割为一个子图或至少两个相互不重叠的子图的处理包括：

[0169] 将位于所述选定的候选分割面上的轮廓线删除，以获得修正的轮廓图；

[0170] 根据修正的轮廓图的顶点之间的连接关系，将修正后的轮廓图分割为一个子图或至少两个分离的的子图；和

[0171] 对所得到的各个不连接的子图进行再组织，从而使得所有子图都含有所述选定候选分割面，其中，对于不含有所述选定的候选分割面的子图，如果该子图的各个顶点完全处于选定的候选分割面一侧，通过顶点邻接图或被分割以得到该子图的轮廓图，将该子图和与其相连接的且处于同侧的子图重新组合得到一个新的子图，如果该子图的顶点分布在选定的候选分割面的两侧，而且通过顶点邻接图或被分割以得到该子图的轮廓图与含有所述选定的候选分割面的子图相连接，则将该子图和与其相连接的子图重新组合为一个新的子图，由未经重新组合的子图以及由重新组合得到的新子图组成从轮廓图分割得到的所述一个子图或至少两个相互不重叠的子图。

[0172] (附记12)：根据附记10中所述的方法，其中，所述的对被判断为洞的子图进行处理以获得新的实体的处理包括：

[0173] 对于每个子图，根据其轮廓线信息，获取其在选定的候选分割面上对应的封闭区域，利用所获取的、该子图在选定的候选分割面上的各个封闭区域之间的关系，以及该子图与选定的候选分割面的关系，判断该子图是否为洞；和

[0174] 对被判断为洞的子图进行处理，以便获得新的实体。

[0175] (附记13)：根据附记12中所述的方法，其中判断子图是否为洞的处理包括：

[0176] 将处于最外面的封闭区域所对应的子图判断为实体；

[0177] 根据除了处于最外面的封闭区域所对应的子图之外的其他子图和与所述其他子图最近的子图之间的相互关系，按照如下原则分别判断其他子图是否为洞：

[0178] 1)若该子图和与其最近的子图，完全处于选定的候选分割面的同一侧，则判断该子图为洞；

[0179] 2)若该子图和与其最近的子图，处于选定的候选分割面的完全相反的一侧，则判断该子图为实体；

[0180] 3)以选定的候选分割面为基准，如果从属于该子图且落在该选定的候选分割面上的顶点出发连接到其它有界平面的有向线段以及该选定的候选分割面的法线向量位于该选定的候选分割面的两侧时，判断该子图为洞，否则判断该子图为实体；

[0181] 其中，对某一个子图，与其最近的子图是一个实体，同时该最近的子图对应的封闭区域包含该子图相应的封闭区域而且是包含该子图相应的所有封闭区域中最小的。

[0182] (附记14)：根据附记13中所述的方法，还包括将被判断为洞的子图和与该子图最近的子图组合在一起，使得分割得到的子图中不存在独立的洞，并将只包含在该洞内的有界平面设置为非候选分割面。

[0183] (附记15)：根据附记10中所述的方法，其中，所述的确定将哪些实体作为分割的结果的处理通过预先设置的参数对分割结果进行控制，使得只有满足预定条件的部分才能从三维模型中被分割出来。

[0184] (附记16)：根据附记15中所述的方法，其中，所述预先设置的参数是子图和与其最近的子图在选定的候选分割面上相应区域面积的比值，如果该比值小于预先设定的阈值，则该子图能被分割出来，否则，该子图和与其最近的子图被组合称为一个新的子图，而不能作为独立的部分被分割出来。

[0185] (附记17)：根据附记9中所述的方法，其中，所述终止条件判断子步骤在某一个子图满足以下任意一个条件时判断不需要对该子图继续进行分割：

[0186] 该子图的顶点数量小于预定的第一阈值；

[0187] 该子图含有的有界平面数量小于预定的第二阈值；

[0188] 该子图含有的所有有界平面中不存在候选分割面；和

[0189] 该子图中不存在可将与该子图对应的轮廓图分割为至少两个子图的候选分割面。

[0190] (附记18)：根据附记17中所述的方法，其中，所述第一阈值为8，所述第二阈值为6。

[0191] (附记19)：一种用于对三维模型进行分割的装置，包括：

[0192] 有界平面生成单元，用于根据输入的三维模型的三角形网格数据对所述三维模型中包含的所有三角形进行处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；

[0193] 轮廓图提取单元，用于通过所述生成的有界平面来提取出所述三维模型的轮廓图；

[0194] 轮廓图分割单元，用于根据所述生成的有界平面的信息以及所述三维模型的顶点邻接图的信息，将所述提取出的轮廓图分割成满足预定条件的一个子图或者至少两个相互不重叠的子图，其中，所述顶点邻接图通过以下方式构建：

[0195] 根据所述三维模型的三角形网格数据，以三维模型的顶点为节点，在被一个或多个三角形所共有的每两个顶点之间添加一条边，从而构建顶点邻接图。

[0196] (附记20)：如附记19所述的装置，还包括预分割单元，用于根据输入的三维模型的三角形网格数据中所包括的三角形数据和顶点数据，将该输入三维模型预分割成一个子模型或者至少两个相互分离的子模型，其中，所述有界平面生成单元、轮廓图提取单元和轮廓图分割单元被配置成对于所述一个子模型或者至少两个相互分离的子模型中的每一个执行处理，以便将每一个子模型都分割成满足预定条件的一个子图或者至少两个相互不重叠的子图。

[0197] (附记21)：如附记19或20所述的装置，还包括模型重建单元，用于根据所述分割成的一个子图或者至少两个相互不重叠的子图以及所述三维模型的三角形网格数据来进行三角化处理，以便重建组成所述三维模型的、由三角形网格来表达的一系列立体部件。

[0198] (附记22)：根据附记19-21中任一项所述的装置，其中，所述有界平面生成单元被配置成：

[0199] 将所述三维模型中包含的所有三角形中的每一个三角形作为子平面，使得满足聚合条件的子平面聚合成一个新的子平面，直到所有的子平面不能再聚合为止，从而生成广义平面；

[0200] 对所述广义平面中的每一个进行如下处理，以生成至少一个适用于对所述三维模型进行分割的有界平面；

[0201] 对位于该广义平面上的三角形，创建三角形邻接图，如果在该邻接图中，该广义平面上的三角形可被划分到若干个分离的子平面中，且每个子平面包含多个相互连接的三角形时，则将该广义平面划分为所述若干个分离的子平面，其中，所述三角形邻接图通过以下方式构建：

[0202] 根据所述三维模型的三角形网格数据，以三维模型的中的三角形为节点，在拥有公共点的两个三角形之间添加边，从而构建三角形邻接图，

[0203] 如果在将该广义平面划分成的所述若干个分离的子平面中的两个或多个子平面同时与另外的同一个平面相互连接，则将这些子平面组合起来作为一个组合的有界平面，由所述组合的有界平面以及将该广义平面划分成的所述若干个分离的子平面中的无需组合的有界平面共同组成所述的适用于对所述三维模型进行分割的有界平面，其中，当所述两个或多个子平面分别与所述另外的同一个平面存在至少一个公共点时，该两个或多个子平面被认为同时与该另外的同一个平面相互连接，以及其中，在顶点邻接图中，如果连接到某个子平面上的顶点处于该子平面的同一侧，则将该子平面作为是所述的无需组合的有界平面中的独立的有界平面。

[0204] (附记23)：根据附记19-22中任一项中所述的装置，其中轮廓图提取单元被配置成通过以下方式提取出所述三维模型的轮廓图：

[0205] 以所述三维模型的顶点作为轮廓图的顶点，各个顶点之间不存在连接；

[0206] 对于有界平面生成单元所生成的每个有界平面，从有界平面生成单元所生成的有界平面中查找与之相连接的有界平面，获取处于该有界平面和与之相连接的有界平面的边界上的顶点，并将各顶点相互连接以得到若干线段；和

[0207] 在所得到的若干线段之中选择互不重叠的、与有界平面的内部边不同的线段作为轮廓线，以得到所述三维模型的轮廓图，其中，每条轮廓线至少要连接到两个不同的有界平面，而且在每一个有界平面内，都存在一个三角形使得它的某一条边包含该轮廓线，以及其中，内部边仅在一个有界平面内，或者被同一有界平面上的两个或多个三角形所共有。

[0208] (附记24)：根据附记19-23中任一项中所述的装置，其中所述轮廓图分割单元包括：

[0209] 候选分割面检测子单元，用于从所生成的有界平面中，查找所有候选分割面，对于任意一个候选分割面，其顶点的数目大于等于4，并且所述三维模型的顶点分布在该候选分割面的两侧；

[0210] 模型分割子单元，用于逐一利用所检测到的候选分割面中的分割面作为选定的候选分割面来对所述轮廓图进行分割，直到将所述轮廓图分割为一个子图或至少两个相互不重叠的子图；

[0211] 终止条件判断子单元，对模型分割子单元得到的各个子图，判断其是否需要继续分割，如果需要，则以该子图含有的候选分割面作为选定的候选分割面，对该子图所对应的轮廓图进行分割，直到将与该子图所对应的轮廓图分割为至少两个相互不重叠的子图。

[0212] (附记25)：根据附记24中所述的装置，其中所述模型分割子单元被配置成：

[0213] 通过所述选定的候选分割面将轮廓图分割为一个子图或至少两个相互不重叠的图，使得所有子图都包含该选定的候选分割面；

[0214] 将所得到的子图中被判断为洞的子图和与该子图的最近的、作为实体的子图结合起来，以便获得新的实体；

[0215] 对分割得到的各个实体进行处理，以便确定将哪些实体作为分割的结果。

[0216] (附记26)：根据附记25中所述的装置，其中，所述模型分割子单元被配置成通过如下处理来对被判断为洞的子图进行处理以获得新的实体：

[0217] 对于每个子图，根据其轮廓线信息，获取其在选定的候选分割面上对应的封闭区域，利用所获取的、该子图在选定的候选分割面上的各个封闭区域之间的关系，以及该子图与选定的候选分割面的关系，判断该子图是否为洞；

[0218] 对被判断为洞的子图进行处理，以便获得新的实体。

[0219] (附记27)：根据附记26中所述的装置，其中所述模型分割子单元被配置成通过如下处理来判断子图是否为洞：

[0220] 将处于最外面的封闭区域所对应的子图判断为实体；

[0221] 根据除了处于最外面的封闭区域所对应的子图之外的其他子图和与所述其他子图最近的子图之间的相互关系，按照如下原则分别判断其他子图是否为洞：

[0222] 1)若该子图和与其最近的子图，完全处于选定的候选分割面的同一侧，则判断该子图为洞；

[0223] 2)若该子图和与其最近的子图，处于选定的候选分割面的完全相反的一侧，则判断该子图为实体；

[0224] 3)以选定的候选分割面为基准，如果从属于该子图且落在该选定的候选分割面上的顶点出发连接到其它有界平面的有向线段以及该选定的候选分割面的法线向量位于该选定的候选分割面的两侧时，判断该子图为洞，否则判断该子图为实体；

[0225] 其中，对某一个子图，与其最近的子图是一个实体，同时该最近的子图对应的封闭区域包含该子图相应的封闭区域而且是包含该子图相应的所有封闭区域中最小的。

[0226] (附记28)：根据附记25中所述的装置，其中，所述模型分割子单元被配置成通过预先设置的参数对分割结果进行控制，使得只有满足预定条件的部分才能从三维模型中被分割出来。

[0227] (附记29)：根据附记28中所述的装置，其中，所述预先设置的参数是子图和与其最近的子图在选定的候选分割面上相应区域面积的比值，如果该比值小于预先设定的阈值，则该子图能被分割出来，否则，该子图和与其最近的子图被组合称为一个新的子图，而不能作为独立的部分被分割出来。

[0228] (附记30)：根据附记24中所述的装置，其中，所述终止条件判断子单元被配置成在某一个子图满足以下任意一个条件时判断不需要对该子图继续进行分割：

[0229] 该子图的顶点数量小于预定的第一阈值；

[0230] 该子图含有的有界平面数量小于预定的第二阈值；

[0231] 该子图含有的所有有界平面中不存在候选分割面；和

[0232] 该子图中不存在可将与该子图对应的轮廓图分割为至少两个子图的候选分割面。

[0233] (附记31)：根据附记30中所述的装置，其中，所述第一阈值为8，所述第二阈值为6。

[0234] (附记32)：一种图像处理系统，其包括如附记19-31中任一项所述的用于对三维模型进行分割的装置。

[0235] (附记33)：如附记32所述的图像处理系统，其中，所述图像处理系统是目标检测系统、局部匹配系统、模型检索系统。

[0236] (附记34)：一种存储有机器可读取的指令代码的程序产品，所述指令代码由机器读取并执行时，可执行如附记1-18中任何一项所述的方法。

[0237] 在上面对本发明具体实施例的描述中，针对一种实施方式描述和/或示出的特征可以以相同或类似的方式在一个或更多个其它实施方式中使用，与其它实施方式中的特征相组合，或替代其它实施方式中的特征。

[0238] 应该强调，术语“包括/包含”在本文使用时指特征、要素、步骤或组件的存在，但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。

[0239] 此外，本发明的方法不限于按照说明书中描述的时间顺序来执行，也可以按照其他的时间顺序地、并行地或独立地执行。因此，本说明书中描述的方法的执行顺序不对本发明的技术范围构成限制。

[0240] 尽管上面已经通过对本发明的具体实施例的描述对本发明进行了披露，但是，应该理解，本领域的技术人员可在所附权利要求的精神和范围内设计对本发明的各种修改、改进或者等同物。这些修改、改进或者等同物也应当被认为包括在本发明的保护范围内。