STL文件毗邻关系的建立与切片算法研究_谢存禧

华南理工大学学报(自然科学版)JournalofSouthChinaUniversityofTechnology

(NaturalScienceEdition)

Vol.28　No.3

March　2000

STL文件毗邻关系的建立与切片算法研究

谢存禧,李仲阳,成晓阳

(华南理工大学机械电子工程系,广东广州5100)

摘　要:通过对STL文件结构的分析,引入无向图数据结构,建立了三角形网格之间的毗邻关系,以顺利进行三角形网格的查寻,实现分层切片.对分层切片算法进行了研究,讨论了切片过程中可能出现的问题,提出了相应的解决办法,最后建立了双向链表来表示切片后的CAD模型截面轮廓.

关键词:快速原型;STL文件;切片算法

中图分类号:TH16;TP311.5　　文献标识码:A　　文章编号:1000-565X(2000)03-0033-06

STL文件是用一系列小三角形面片对CAD模型表面进行三角化离散而得到的.分层切

片是用截平面(一般沿高度方向进行切片,截平面可表示为:z=ci,i=1,2,…,n)截交上述小三角形面片,形成由小段折线构成的封闭多边形边界.快速原型就是填充该平面图形,沿高度方向逐层迭加,最后形成物理模型.

三角形面片网格在STL文件中是散乱分布的,只有对这些网格以某种关系进行组织,然后求出截平面与三角形网格棱边的交点,构成有序点集,才能成为有意义的平面边界.

文献[1]提出了一种智能化的快速成型切片算法,该算法通过建立三角形网格的毗邻边表资料,使得切割完一个三角形网格后,能利用毗邻资料查找到下一个待切割的三角形网格……最终返回起点,得到一个有序切割点列.但是该方法未考虑当截平面切割到三角形网格顶点时的情形,在该情形下,无法搜索到下一个待切割的网格,将造成切片算法失败;另外,毗邻资料的建立依赖于三角形顶点的排序,这使得网格间毗邻边表资料的建立方法过于复杂

[2]

.

本文引入无向图数据结构来建立三角形网格的毗邻关系,方法简单明晰,并考虑到了切

点为三角形网格顶点的情况,使得切割完一个网格后,能顺利找到下一个待切割的三角形网格.切片得到的数据结构是一个双向链表,它的结点数据域由截平面与三角形网格棱边的交点以及该网格的法矢构成.

1毗邻三角形网格的数据结构

STL文件是以三角形网格来表示CAD模型表面的,每个三角形网格由它的3个顶点以

1.1　STL文件的数据结构

及单位法矢构成,其数据结构形式是:

　　typedefstructtriangle{

　收稿日期:1999-04-28　　修稿日期:1999-06-15　作者简介:谢存禧(1940-),男,教授,博士生导师,主要从事机器人、环保汽车、机械设计与理论的研究.

　34华南理工大学学报第28卷　

V1[3];　　　　　//三角形顶点1V2[3];

V3[3];n[3];

//三角形顶点2//三角形顶点3//三角形网格单位法矢

}triangle;

其中,三角形网格的单位法矢并不,它由三角形顶点V1,V2,V3与连接顺序确定,若顶点的坐标值为xi,yi,zi(i=1,2,3),则该网格的单位法矢可由下式计算:

n=

N1i+N2j+N3k

2N1

2+N2

2+N3

.(1)

式中,i,j,k分别为沿x,y,z轴的单位矢量,N1=y1(z2-z3)+y2(z3-z1)+y3(z1-z2),N2=z1(x2-x3)+z2(x3-x1)+z3(x1-x2),N3=x1(y2-y3)+x2(y3-y1)+x3(y1-y2).

1.2　三角形网格的毗邻关系

三角形网格在STL文件里是散乱分布的,即每个三角形网格出现在STL文件里的位置都是任意的,为了进行切片工作,需要建立起三角形网格之间的连接关系.

一个正确的STL文件中,三角形的每一条棱边有且只有两个三角形网格共享.若一对三角形网格共享一条边,则称它们之间相互毗邻,因此,每个三角形有且仅有3个三角形网格与之毗邻.以图1所示立方体为例,将其分割成编号为0,1,2,…,11的12个网格,分层切片则是根据网格间的毗邻关系顺序求出截平面与三角形网格棱边的交点,并构成一个有序数据序列(见图2).

图1　立方体表面的三角形划分Fig.1　Thedivid_triangleofthecube_surfaces

图2　对三角形网格分层切片Fig.2　Slicingtotrianglenets

若T表示三角形网格,则各网格之间的毗邻关系可以用图3所示无向图G来表示:

抽象地将G表示为:

G=(T,{E});

(2)

T表示图中各三角形网格的集合:T=T0,T1,T2,…,T11;(3)

E表示各三角形网格的毗邻关系集合,以无序对表示:

T0,T1),(T0,T2),(T0,T11),(T1,T4),　E=((T1,T8),(T2,T3),(T2,T10),(T3,T4),

图3　用无向图表示的三角形网格

之间的毗邻关系

Fig.3　Theadjoiningrelationsbetweenthe

trianglenetsexpressedbyundiagraph

　第3期谢存禧等:STL文件毗邻关系的建立与切片算法研究　35

　　(T3,T7),(T4,T5),(T5,T7),(T5,T8),(T6,T7),(T6,T9),(T6,T10),(T8,T9),(T9,T11),(T10,T11).　　

若用数组表示法来存储该无向图,则该图的邻接矩阵是:

011

00

Garcs=

0000001

110000011000000010000100

001010010000

001000100110000101000000

000000010110

000101100000

001000000010010001100001

001000100001

100000000110.

(5)(4)

式中,元素1代表三角形网格之间具有毗邻关系.邻接矩阵的每一行只有3个元素为1,其余均为0,它是一个对称矩阵.当n很大时,矩阵的存储量将大得惊人.为此引入毗邻向量,即将上述矩阵的每一行中的元素1修改为相应的列号,变成一个3维向量Adj[3],如将第一行

修改为[1,2,11],表示T0号三角形分别与T1、T2和T11号三角形毗邻.同时引入标志flag.flag=1表示该三角形已被切割,flag=0表示还没有被切割.则重构的STL文件表达了三角形网格的信息以及网格之间的毗邻关系,其形式如下:

　　typedefstructtriangle{

V1[3];

V2[3];V3[3];n[3];

Adj[3];//邻接向量flag;}triangle;

2三角形网格的切片

通过建立三角形网格间的毗邻关系,可将散乱无序的网格表示成无向图的数据结构,随

后沿高度方向对该模型进行切片,它的数学本质是以z=ci(i=1,2,…,n)的截平面截交三角形网格,求出与网格棱边的交点,该层所有交点的连线构成一封闭多边形.

2.1　三角形网格与截平面z=ci相交的判别

判别方法涉及网格高度的比较,取三角形网格3个顶点的z坐标值:z1=triangle.V1.z,z2=triangle.V2.z;z3=triangle.V3.z.如图4所示,如果ci≥min(z1,z2,z3)且ci≤max(z1,z2,z3),则表明z=ci与该网格相交.　36华南理工大学学报第28卷　

2.2　三角形网格两条棱边与截平面z=ci相交的判别和交点的求法

显然,截平面不能同时切割到一个三角形的3条棱边,故需判别3条棱边中哪两条边与截平面相交.记mid(z1,z2,z3)为z1,z2,z3中数值居中者,若ci≥mid(z1,z2,z3),则

取它与max(z1,z2,z3)点连接的两条棱边为被切边;若ci≤图4　三角形与截平面相交的判别

4　Distinguishoftheinter_mid(z1,z2,z3),则取它与min(z1,z2,z3)点连接的两条棱Fig.

边为被切边;另一条被切边是连接max(z1,z2,z3)与min(z1,z2,z3)的那条棱边.若三角形被切棱边的顶点坐标为(x1,y1,z1),(x2,y2,z2),则相应的直线方程是

x-x2y-y2z-z2

==.

x1-x2y1-y2z1-z2求得截平面与棱边的交点坐标:

x=y=

ci-z2

(x-x2)+x2,

z1-z21

ci-z2

(y-y2)+y2,

z1-z21

sectionsofthetrianglewiththesection

(6)

(7)

z=ci.

2.3　标志的设置

在一次切片中,每一个被处理过的三角形网格均设置标志flag=1,以免被重复查询,导

致网格搜索失败.该次切片完毕后,恢复标志flag=0.

2.4　三角形网格的搜索策略

求出切点后,取下一个三角形网格进行切割,此时需要考虑以下两种情况:1)切点位于棱边的两顶点之间　由于一个三角形有且仅有3个毗邻三角形(见图5),若当前被处理的三角形为A,与其毗邻的三角形中只有两个被截平面切割(另一个三角形与未切割棱边毗邻),而在这两个三角形中,有一个三角形已被访问过(通过标志flag=1识别),因此,只有唯一的一个毗邻三角形待访问.

2)切点与三角形的顶点P重合　若当前被处理的三

图5　网格搜索的两种情况Fig.5　Twosituationsofthe

trianglesearch

角形为B(见图5),则按上述方式找不到下一个待访问的毗邻三角形,因为顶点P为多个三角形共有.此时处理方法如下:取三角形B的两个毗邻网格之任一个(除去已被访问过的那个三

角形),显然它们的整体分别在截平面c2的某一侧,即c2≥min(z1,z2,z3)或c2≤max(z1,z2,z3).若取三角形1,再找其毗邻网格,由于三角形B已经插上标志flag=1,则三角形1的毗邻三角形中只有一个可能与截平面相切.

综合上述两种情况,所设计的三角形网格搜索流程图见图6.

如有网格未考虑或处理,表示另有完整轮廓.一般的模型都比立方体复杂,可能存在空腔和分叉,模型的切片将含有多组完整轮廓.

　第3期谢存禧等:STL文件毗邻关系的建立与切片算法研究　37

图6　三角形网格搜索流程图

Fig.6　Thesearchflowchartofthetrianglenets

3切片得到的封闭多边形数据结构

通过上述研究,一个三角形网格与截平面相切,得到两个交点,舍弃与上一毗邻三角形

[3]

相同的交点,保留另一个交点,并取该三角形网格的单位法矢,建立双向链表

如下:

　　typedefstructDulNode{

x;y;　　　　　　　　　　　//切点坐标值n;

StructDulNode＊priorStructDulNode＊next}

//三角形网格单位法矢坐标值//指向结点的前趋指针//指向结点的后继指针

,数据结构

　　在双向链表中加入单位法矢量,便于快速成型后对物理模型进行抛光精整,特别是在机器人快速原型系统中,单位法矢与切点坐标值共同确定了机器人末端手臂的位姿及路径.

　38华南理工大学学报第28卷　

4结论

1)STL文件是无序的,对CAD模型的切片,实质是求截平面与三角形网格棱边的交点.

为了使切片得到的数据具有唯一正确的几何意义,需要对STL文件进行整理重构.

2)建立三角形网格之间毗邻关系的概念,并设置标志,可将无序的三角形网格变得明确有序,使得切片能从最初的网格出发,逐步查询搜索下一个网格,并能最终返回出发点.

3)切点为三角形网格的顶点时,为了使搜索查询能继续下去,必须进行判别处理.4)切得的CAD模型的截面轮廓表示成双向链表的形式,快速成型以此信息完成对截面的扫描.参考文献:

[1]　蔡小康.智能化的快速成型切片算法[J].中国机械工程,1997,8(5):49-51.

[2]　DOLENCA,MAKELAI.Slicingproceduresforlayeredmanufacturingtechniques[J].Computer_

aidedDesign,1994,26:119-126.

[3]　严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.

ConstructionoftheAdjoiningRelationshipofSTLFilesand

theStudyonSlicingAlgorithm

XIECun_xi,LIZhong_yang,CHENGXiao_yang

(Dept.ofMechatronicEngineering,SouthChinaUniv.ofTech.,Guangzhou5100,China)

Abstract:BytheanalysisofthestructuresofSTLfilesandbasedonthestructureofundia-graph,theadjoiningrelationshipamongthetrianglesisconstructedbywhichonecansearchforatriangleandsliceeasily.Aslicingalgorithmisstudiedandtheproblemswhich

mayhappenduringtheslicingprocessarediscussed.Somemethodstosolvetheproblemsareproposedtoo.Atlast,aDoubleLinkListisusedtoexpresstheCADmoldafterslic-ing.

Keywords:rapidprototype;STLfile;slicingalgorithm