产品STL模型布尔运算方法

摘要

本发明提供一种产品STL模型的布尔运算方法，其特征在于构建产品STL模型的动态空间索引结构，基于该结构获取两STL模型相交三角面片，并根据空间三角面片的位置关系，计算相交三角面片的交线段，通过建立离散交线段的动态空间索引结构实现交线段的邻近排序，根据交线对相交三角面片进行细分，以交线为分界线将参与布尔运算的STL模型划分为两个子STL模型，将分割后的子STL模型按照不同的方式组合，实现STL模型的交、并或差布尔运算。实例证明该方法获取交线数据准确，能有效提高产品STL模型的布尔运算效率，并可处理各种复杂型面产品的STL模型的布尔运算。

说明书

所属技术领域

本发明提供一种产品STL模型布尔运算方法，属于计算机辅助设计领域。

背景技术

产品STL模型可实现基于产品外形采样数据点云的曲面模型快速精确重构，目前已在产品逆向工程领域获得广泛应用。对逆向工程系统输出的产品STL模型进行布尔运算，可实现产品STL模型的剪裁、拼接等操作，并可构造出具有复杂型面特征的产品STL模型。

对现有的技术文献检索发现，张金义等在学术期刊《工程图学学报》2002，12(1)，P53-61上发表的论文“统一于三角面片的可靠多面体布尔集合运算”中，采用多面体一致关系的判断和推理方法，根据多面体位置关系实现产品STL模型的布尔运算，该算法保证了形状规则、数据量少的产品STL模型布尔运算的可靠性，但对形状复杂、数据量大的产品STL模型其几何推理过程效率低。

郭开波等在学术期刊《华中科技大学学报》(自然科学版)2006，34(7)，P96-99上发表的论文“STL模型布尔运算的实现”中，采用邻接表作为产品STL模型数据结构，建立曲面模型中三角面片的包围盒，遍历包围盒获取相交的三角面片并计算其交线段，将所有交线段排序获取两模型交线，根据交线剖分产品STL模型，实现产品STL模型的布尔运算，但三角面片邻接表的建立及维护过程繁琐，需重复遍历邻接表计算交线段，算法运行效率低。

唐敏等在学术期刊《软件学报》1999，12(10)，P1291-1297上发表的论文“非正则精确模型的布尔操作”中，采用非正则精确模型作为几何对象数据结构，基于该模型进行数据对象的层次求交，实现产品STL模型的布尔运算，该算法避免了由于计算误差引起的裂纹以及拓扑生成的不一致，但非正则精确模型结构复杂，获取产品STL模型交线过程繁琐，求交速度慢。

综上所述，现有的针对产品STL模型的布尔运算方法存在三角面片求交速度慢，缺乏统一的构建产品STL模型拓扑结构的有效数据结构，算法运行效率低等问题。

发明内容

本发明的目的在于提供一种产品STL模型布尔运算方法，以有效缩短复杂外形产品的开发周期，降低产品成本。其技术方案为：

产品STL模型布尔运算方法，其特征在于步骤依次为：1)读产品STL模型数据到存储器中，并为产品STL模型数据建立线性链表存储结构，改进R^*-树得到适合于存储产品STL模型的动态空间索引结构R^*S-树，基于该结构建立产品STL模型的动态空间索引结构；2)基于产品STL模型的动态空间索引结构获取交线数据；3)根据交线数据对相交三角面片进行细分；4)将细分后三角面片添加到产品STL模型动态空间索引结构中，重新建立产品STL模型动态空间索引结构，遍历该索引结构，自适应扩张查找位于交线两侧的三角面片，以交线为分界线将产品STL模型分成两个子STL模型，实现产品STL模型的分割；5)根据布尔运算类型，将分割后产品STL模型进行组合，实现产品STL模型的交、并或差布尔运算。

为实现发明目的，所述的产品STL模型布尔运算方法，在步骤1)中，改进R^*-树动态空间索引数据结构得到R^*S-树的方法具体是：将三角面片及索引结点MBR即最小包围矩形统一表示为四维点对象(x，y，z，r)，其中x，y，z为MBR中心坐标，r为MBR外接球半径值，通过三角面片集合的聚类分簇，构建产品STL模型动态空间索引结构。

为实现发明目的，所述的产品STL模型布尔运算方法，在步骤2)中，设参与布尔运算的两STL模型为S₁和S₂，根据STL模型S₁动态空间索引结构，判断STL模型S₂动态空间索引结构中结点MBR与STL模型S₁的相交关系，若不相交，则STL模型S₁和STL模型S₂无交线；若相交查找STL模型S₁与STL模型S₂动态空间索引结构中相交的数据结点，该数据结点中存储的三角面片即为STL模型S₁和STL模型S₂相交的三角面片；提取相交数据结点中存储的三角面片，求交获取交线段，采用R^*S-树建立离散交线段动态空间索引结构，基于该结构各层结点的空间邻近关系实现交线段的邻近排序。

为实现发明目的，所述的产品STL模型布尔运算方法，在步骤2)中，采用R^*S-树建立离散交线段动态空间索引结构，基于该结构各层结点的空间邻近关系实现交线段邻近排序的步骤具体是：①以任一交线段为起始线段，查询离散交线段动态空间索引结构中到起始线段某端点距离为零的数据结点；②获取该数据结点中存储的交线段，该交线段与起始线段相连组成新的起始线段；③查询离散交线段动态空间索引结构中到新起始线段端点距离为零的数据结点，若存在距离为零的数据结点执行步骤②；④输出两STL模型一条交线，如果两复杂STL模型交线不止一条，执行步骤①。

为实现发明目的，所述的产品STL模型布尔运算方法，在步骤4)中，产品STL模型分割具体步骤如下：①以产品STL模型中位于交线上的任一三角面片为初始迭代面片；②查找产品STL模型中包含初始迭代面片非交线边的三角面片；③判断查找到的三角面片是否以交线为边界，若不存在交线边界则停止查找交线边方向上的三角面片，查找产品STL模型中包含其它边界的三角面片，执行③；④若两STL模型存在多条交线，提取下一条交线，执行①；⑤将查找到的三角面片从产品STL模型中分割出来，沿交线将产品STL模型分成两个子STL模型。

为实现发明目的，所述的产品STL模型布尔运算方法，在步骤5)中，产品STL模型布尔运算方法具体是：设两STL模型为S₁和S₂，交线将STL模型S₁分成两个子STL模型，即位于STL模型S₂内部和外部的STL模型，交线同样将STL模型S₂分成两个子STL模型，STL模型S₁和STL模型S₂布尔运算公式如下：

S₁∩S₂＝S₁inS₂+S₂inS₁

S₁∪S₂＝S₁outS₂+S₂outS₁

S₁-S₂＝S₁outS₂+S₂inS₁

S₂-S₁＝S₂outS₁+S₁inS₂

以上公式中S₁inS₂和S₁outS₂分别表示STL模型S₁位于STL模型S₂内部和外部的子STL模型，S₂inS₁和S₂outS₁分别表示STL模型S2位于STL模型S₁内部和外部的子STL模型。STL模型的交运算是将STL模型S₁中的S₁inS₂与STL模型S₂中的S₂inS₁组合成一张曲面，并运算是将STL模型S₁中的S₁outS₂与STL模型S₂中的S₂outS₁组合成一张曲面，差运算是将STL模型S₁中的S₁outS₂与STL模型S₂中的S₂inS₁组合成一张曲面或将STL模型S₂中的S₂outS₁与STL模型S₁中的S₁inS₂组合成一张曲面。

本发明与现有技术相比，具有以下优点：

1)采用R^*S-树组织产品STL模型的动态空间索引结构，基于该结构实现邻近三角面片的快速查询，可对各种复杂型面的产品STL模型进行布尔运算；

2)通过逐层查找动态空间索引结构各层结点，可准确定位两STL模型相交的三角面片，快速求解产品STL模型交线，有效提高了产品STL模型的求交效率；

3)基于动态空间索引结构快速获取位于交线两侧的三角面片，实现产品STL模型的分割，有效提高了产品STL模型的布尔运算效率。

附图说明

图1是本发明程序流程图；

图2是本发明所建立的产品STL模型动态空间索引结构整体结构示意图；

图3是本发明动态空间索引结构索引结点规范化表示示意图；

图4是本发明三角面片集合的空间聚类分簇实现流程图；

图5～图9是本发明对球模型所建立的动态空间索引结构各层结点MBR模型图；

图10是本发明两相交产品STL模型空间位置示意图；

图11是本发明两相交产品STL模型动态空间索引结构相交第一层结点示意图；

图12是本发明两相交产品STL模型动态空间索引结构相交叶结点示意图；

图13是本发明两相交产品STL模型动态空间索引结构相交数据结点示意图；

图14是本发明两相交三角面片无交线的情况示意图；

图15是本发明两相交三角面片有交线的情况示意图；

图16是本发明根据R^*S-树将杂乱交线段排序获取交线数据示意图；

图17是本发明两相交的空间球示意图；

图18是本发明两相交空间球交线示意图；

图19～图20是本发明两相交空间球相交三角面片的细分效果；

图21是本发明产品STL模型分割前示意图；

图22是本发明产品STL模型分割后示意图；

图23是本发明实施例兔子模型；

图24是本发明实施例两产品STL模型位置关系示意图；

图25～26是本发明实施例兔子模型分割后在球模型内部和外部的子STL模型；

图27～28是本发明实施例球模型分割后在兔子模型内部和外部的子STL模型；

图29是本发明实施例兔子模型与球模型布尔交运算后的STL模型；

图30是本发明实施例兔子模型布尔减球模型后的STL模型；

图31是本发明实施例球模型布尔减兔子模型后的STL模型；

图32是本发明实施例球模型布尔并兔子模型后的STL模型。

具体实施方式

下面结合附图对本发明作进一步说明。

图1是本发明产品STL模型布尔运算的程序实现流程图。产品STL模型数据输入程序1负责读入STL模型数据文件，并为其创建线性存储结构。产品STL模型动态空间索引结构构建程序2采用嵌套的MBR对产品STL模型进行动态空间聚类划分，为数据输入程序1所生成的数据线性链表建立改进的动态空间索引结构R^*S-树。产品STL模型交线获取程序3根据参与布尔运算的两STL模型动态空间索引结构各层结点MBR的相交关系，获取两模型动态空间索引结构中相交的数据结点，通过相交数据结点中的三角面片求交获取交线段，采用R^*S-树建立离散交线段的动态空间索引结构，基于该索引结构中各层结点的空间邻近关系实现交线数据邻近排序，获取两STL模型交线。相交三角面片细分程序4根据程序3中获取的交线段将相交三角面片进行三角细分。产品STL模型分割程序5重新建立细分后的产品STL模型的动态空间索引结构，遍历查找该索引结构，自适应扩张查找位于交线两侧的三角面片，以交线为分界线将产品STL模型分成两个子STL模型，实现产品STL模型的分割。产品STL模型布尔运算程序6根据布尔运算的类型，将两STL模型分割后的子STL模型按照不同的方式组合，实现产品STL模型的交、并或差布尔运算。

图2中，产品STL模型动态空间索引结构分为索引层和数据层，索引层由内部结点、叶结点和数据结点构成；数据层为数据链表，其结点具有访问上级索引层的能力。索引层结点分为索引结点和数据结点，数据结点只有指向具体空间数据对象的指针。索引结点结构体中的type标识用于判断该结点是内部结点还是叶结点，type等于0表示该结点为内部结点，type等于1表示该节点为叶结点。叶结点的子结点为数据结点，通过数据结点获取具体数据对象。

图3中，将产品STL模型中三角面片及索引节点MBR统一表示为四维点对象(x，y，z，r)，其中x，y，z为MBR中心坐标，r为MBR外接球半径值。对于产品STL模型动态空间索引结构各层结点的子结点数的上限M和下限m，以及结点重新插入数目R的取值，均由用户根据产品STL模型的规模自行设置，通常取m＝M×40％，且$1\le m\le \frac{M+1}{2},$R＝M×30％。

图4中，将索引结点中心距离最远的一对结点MBR的中心作为初始簇集中心，将数据对象添加到距簇集中心最近的簇集中，更新各簇集中心，并与原来的簇集中心进行比较，若簇集中心相同或分簇次数超过最大分簇次数则结束分簇，否则继续分簇。

图5～图9是本发明球模型所建立的动态空间索引结构各层结点MBR模型图。产品STL模型中三角面片数据数量为952，所采用的索引参数m＝8、M＝20，重新插入结点数R＝6。其中图5是球模型产品STL模型，图6是动态空间索引结构根结点MBR，图7是第二层结点MBR，图8是叶结点MBR，图9是数据结点MBR，从图中可以看出，采用动态空间索引结构可准确实现产品STL模型的空间聚类划分。

图10中，调用产品STL模型交线获取程序3快速获取两产品STL模型相交三角面片，设进行布尔运算的两STL模型为S₁和S₂，根据STL模型S₁动态空间索引结构，判断STL模型S₂动态空间索引结构中结点MBR与STL模型S₁的相交关系，若不相交，则STL模型S₁和STL模型S₂无交线；若相交查找STL模型S₁与STL模型S₂动态空间索引结构中相交的数据结点，该数据结点中存储的三角面片即为与目标STL模型相交的三角面片。

调用产品STL模型交线数据获取程序3，计算两产品STL模型中相交三角面片的交线段。将空间三角面片的位置关系划分为以下两种情况：1)其中一个三角面片与另一三角面片所在平面不相交，即三角面片三个顶点均在另一个三角面片所在平面的同侧；2)两三角面片相交。若为情况1)，两三角面片不相交，不进行求交运算；若为情况2)，判断两三角面片是否共面，如果共面则利用三角面片三条边与另一三角面片求交获取两三角面片交线段，将各交点平均值作为交点，否则计算两三角形所在平面的交线l，通过l与两三角面片求交获取交线段，确定交线段的端点对应于l上的参数值t₀₀、t₀₁、t₁₀和t₁₁。如图14所示，若t₀₁≤t₁₀或t₁₁≤t00，两三角面片没有交线；如图15所示，若t₀₁>t₁₀或t₁₁>t₀₀，两三角面片相交，根据参数值分布求解两三角面片的交线段，令交线段的起点和终点对应的直线l上参数值分别为t₀和t₁，根据公式$t_0=\left(\begin{array}{cc}{t}_{10}& (t_{00}\le t_{10})\\ t_{00}& (t_{00}>t_{10})\end{array}\right),$$t_1=\left(\begin{array}{cc}{t}_{01}& (t_{01}\le t_{11})\\ t_{11}& (t_{01}>t_{11})\end{array}\right)$计算t₀和t₁的值，获取交线段。相交三角面片的交线段是一组杂乱无序的线段，要获取完整交线需对其排序，采用R^*S-树建立离散交线段的动态空间索引结构，基于该结构各层结点的空间邻近关系实现交线段的邻近排序。两产品STL模型交线数据的获取过程如图16所示，线段E₀为起始线段，查询R^*S-树索引结构中到E₀端点P₀距离为零的数据结点MBR₁，获取MBR₁中存储交线段E₁；连接E₀与E₁并查询R^*S-树索引结构中到E₁端点P₁距离为零的数据结点MBR₂，获取MBR₂中存储交线段E₂；连接E₁与E₂，迭代查询R^*S-树索引结构中数据结点，直至查询到所有交线段，最终获取两STL模型一条交线。

图17为本发明两相交的球示意图，建立两球的动态空间索引结构，调用产品STL模型STL模型交线数据获取程序3求两模型的交线，如图18所示。调用相交三角面片细分程序4，以交线段端点为细分点对相交三角面片进行三角约束Delaunay细分，约束边界为交线段和三角面片的三条边，左侧球相交三角面片的细分效果如图19所示，右侧球相交三角面片的细分效果如图20所示。

将细分后三角面片添加到产品STL模型动态空间索引结构中，重新建立产品STL模型动态空间索引结构。以交线为公共边界的三角面片位于交线的两侧，遍历产品STL模型动态空间索引结构，自适应扩张查找位于交线两侧的三角面片，以交线为分界线将产品STL模型分成两个子STL模型，实现产品STL模型的分割。调用产品STL模型分割程序5实现产品STL模型的分割，图21所示为分割前产品STL模型，三角面片T₁为初始迭代面片，由三角面片T₁查找到三角面片T₂和三角面片T₃，由三角面片T₂查找到三角面片T₄和三角面片T₅，由三角面片T₃查找到三角面片T₆，由三角面片T₄查找到三角面片T₇和三角面片T₈，调用STL模型分割程序5，实现该STL模型的分割，分割效果如图22所示。

调用产品STL模型布尔运算程序6，两产品STL模型进行布尔运算。将图5所示的产品STL模型与图23所示的兔子模型进行布尔运算，两产品STL模型的空间位置如图24所示，求取两模型交线后，基于该交线分割两STL模型，图25是发明实施例兔子模型分割后在球模型内部的子STL模型，图26是发明实施例兔子模型分割后在球模型外部的子STL模型，图27是发明实施例球模型分割后在兔子模型内部的子STL模型，图28是发明实施例球模型分割后在兔子模型外部的子STL模型。根据产品STL模型布尔运算类型，对兔子模型和球模型进行布尔交、并或差布尔运算，图29是发明实施例两模型布尔交运算后STL模型，图30是发明实施例兔子模型布尔减球模型后STL模型，图31是发明实施例球模型布尔减兔子模型后STL模型，图32是发明实施例两模型的布尔并运算后STL模型。

其它产品STL模型的布尔运算方法同上。