基于OpenGL的STL文件剖分及填充显示技术研究

２００８年第１期　铸造设备研究　２００８年　２月　ＲＥＳＥＡＲＣＨ　ＳＴＵＤＩＥＳ　ＯＮ　ＦＯＵＮＤＲＹ　ＥＱＵＩＰＭＥＮＴ　Ｆｅｂ．２００８№１　・研究生论文・　基于ＯｐｅｎＧＬ的ＳＴＬ文件剖分及填充显示技术研究　牛晓峰　，侯华　，徐宏　，毛红奎　（１．中北大学电子与计算机科学技术学院，山西太原０３００５１；２．中北大学材料科学与工程学院，山西太原　诤０３００５１）　摘要：ＳＴＬ文件格式是快速成形领域中描述三维实体模型的标准文件格式。本文基于ＯｐｅｎＧＬ技术，对　ＳＴＬ文件分割过程中ＳＴＬ文件分割算法、截面轮廓线的提取算法、利用ＯｐｅｎＧＬ的镶嵌技术实现截面填充显示　和三角化算法的关键问题进行了详细的论述。　关键词：快速成型；ｓＴＬ模型；ＯｐｅｎＧＬ；三角４１５；分割　中图分类号：ＴＰ３９１　文献标识码：Ａ　文章编号：１００４—６１７８（２００８）０１—００２２—０４　Ｒｅｓｅａｒｃｈ　ｏｎ　ＳＴＬ　Ｄｉｖｉｄｉｎｇ　Ｍｏｄｅｌ　Ｄｉｓｐｌａｙ　Ｔｅｃｈｎｉｑｕｅ　Ｂａｓｅｄ　ｏｎ　ＯｐｅｎＧＬ　ＮＩＵ　Ｘｉａｏ－ｆ￣ｇ，，ＨＯＵＵｌｌａｆｉ２　ＸＵ　Ｈｏｌ　，ＭＡＯ　Ｈｏｎｇ－ｋｕｉｚ　（１．Ｃｏｌｌｅｇｅ　ｏｆＥｌｅｃｔｒｏｎ　ａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎｏｒｔｈ　Ｕｎｉｖｅｒｓ　ｏｆＣｈｉｎｔ￣Ｔａｉｙｕａｎ　Ｓｈａｎｘｉ　０３００５１，Ｃｈｉｎｔｇ　２．Ｃ０　Ｍａｔｅｒｉａｌ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈ　Ｕｎｉｖｅｒｓ　ｏｆＣｈｉｎａ，Ｔａｉｙｕａｎ　Ｓｈａｎｘｉ　０３００５１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：ＳＴＬ　ｆｉｌｅ　ｉｓ　ｔｈｅ　ｓｔａｎｄａｒｄ　ｆｉｌｅ　ｆｏｒｍａｔ　ｏｆ　Ｒａｐｉｄ　Ｐｒｏｔｏｔｙｐｅ．Ａ　ｓｏｌｉｄ　ｄｉｖｉｄｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ＳＴＬ　ｆｉｌｅ　ｆｏｒｍａｔ　ｉｓ　ｂｒｏｕｇｈｔ　ｆｏｒｗａｒｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ｔｈｅ　ｋｅｙ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｄｉｖｉｄｉｎｇ　ＳＴＬ　ｆｉｌｅ，ｉｎｃｌｕｄｉｎｇ　ｄｉｖｉｄｉｎｇ　ＳＴＬ　ｆｉｌｅ，ｃｒｅａｔｉｎｇ　ｃｒｏｓｓ－ｓｅｃｔｉｏｎ　ｐｒｏｆｉｌｅ，ｐｒｏｃｅｓｓｉｎｇ　ｔｈｅ　ｔｒｉａｎｇｌｅ　ｆａｃｅｔ　ｄｉｖｉｄｅｄ　ａｎｄ　ｔｒｉａｎｇｕｌａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｒｏｓｓ—ｓｅｃｔｉｏｎ　ｐｒｏｆｉｌｅ　ａｎｄ　ＳＯ　ｏｎ　ａｙｅ　ｄｉｓｃｕｓｓｅｄ．　Ｋｅｙｗｏｒｄｓ：ｒａｐｉｄ　ｐｒｏｔｏｔｙｐｉｎｇ，ＳＴＬ　ｍｏｄｅｌ，ｏｐｅｎＧＬ，ｔｒｉａｎｇｕｌａｔｉｏｎ，ｄｉｖｉｄｉｎｇ　快速成型技术是一种新型的先进制造技术，是　并能在网络环境下以客户／月艮务器模式工作。是专业图　通过逐层的填加材料来制造零件。ＳＴＬ文件格式已　形处理、科学计算等高端应用领域的标准图形库。　经成为快速成形领域中的描述三维实体模型的标　准文件格式。ＳＴＬ文件是通过对ＣＡＤ实体模型或曲　Ｉ　ＳｒＩ＇Ｌ文件分割基本思路　面模型进行表面三角化离散得到的，相当于一种全　从本质上讲，对ＳＴＬ文件进行分割，就是用一　由小三角形面片所构成的多面体模型。从几何上　个平面交割ＳＴＬ模型。计算该平面与ＳＴＬ模型中三　看，它是用众多三角形小平面来形成三维形体的表　角形面片的相交情况。交割后ＳＴＬ文件变为二个独　面，每个三角形面片用三个顶点表示。ＳＴＬ文件能够　立的ＳＴＬ文件，此时的ＳＴＬ文件均缺少一个表面，　正确描述三维模型，必须遵守一定的规范。共顶点　是不完整的ＳＴＬ文件。故还要计算一系列封闭的截　规则：每相邻的２个三角形只能共享２个顶点即一　面的轮廓线，并把缺少的表面补上，形成完整的　个三角形的顶点不能落在相邻的任何一个三角形　ＳＴＬ。补全不完整ＳＴＬ文件有两种方法。一种方法是　的边上。取向规则：对于每个小三角形平面的法向　采用ＯｐｅｎＧＬ中的镶嵌技术，该法只适用一次分割；　量必须由内部指向外部，小三角形三个排列顶点的　另外一种是对截面轮廓进行三角化处理。并把三角　顺序同法向量符合右手法则。　化的结果加到分割后生成的两个新的ＳＴＬ文件中　本文基于ＯｐｅｎＧＬ技术．实现ＳＴＬ文件剖分及填　去，此法可进行多次分割。　充显示。ＯｐｅｎＧＬ是Ｏｐｅｎ　Ｇｒａｐｈｉｃｓ　Ｌｉｂｒａｒｙ（开放性图　形库）的缩写，是一套三维图形处理库，也是该领域的　２　ＳＴＬ文件分割　工业标准。ＯｐｅｎＧＬ被设计成于硬件。于窗口　２．１．三角形面片和平面的关系　系统的，在运行各种操作系统的各种计算机上都可用，　平面交割ＳＴＬ模型后，把一个ＳＴＬ文件一分为　二，三角形面片和平面的关系有以下六种。第一种如　收稿日期：２００７—１　１－２１　图１，是三角形面片和平面不相交的情况；第二种如图　作者简介：牛晓峰（１９８２一），男，硕士生，主要研究方向：计算机应用　计算机图形学。　２是三角形面片的—个顶点在平面上。另两个顶点在　基金项目：中北大学院基金（２００８１６）　平面的同一侧的情况；第三种如图３。是三角形面片的　维普资讯 http://www.cqvip.com

２００８年第１期　一牛晓峰，等：基于ＯｐｅｎＧＬ的ｓＴＬ文件剖分及填充显示技术研究　铸造设备研究　个顶点在平面上，另两个顶点在平面的两侧的情　况；第四种如图４，是三角形面片的两个顶点在平面上　的情况；第五种如图５，是三角形面片的三个顶点在平　面上的情况；第六种如图６，是三角形面片的三个顶点　均不在平面上，面片有两条边和平面相交的情况。　ｆｌｏａｔ　ＳＴＬＶｅｒｔｅｘ３ｆ３［３］；，／三角形面片顶点３　ｓｔｒｕｃｔ　ｏｎｅｆａｃｅ＊ｆｏｒｗａｒｄ；／／指向前—个三角形面片　ｓｔｒｕｃｔｏｎｅｆａｃｅ＊ｎｅｘｔ；　ｂｏｏｌ　ｆａｃｅ＿／／指向下—个三角形面片　ａｓｋ；　／／三角形面片的访问标志　／／三角形面片顺序号　ｉｎｔ　ｎｕｎ；　ｉｎｔ　ｎｅｘｔｎｕｍ［３］；　＿／／相邻三角形面片邻边的　图１　三角形面片和平　图２三角形面片的一个顶　面不相交　点在平面上，另两个　顶点在平面的同一侧　图３三角形面片的一个　顶点在平面上．另两　图４三角形面片的两　个顶点在平面　两侧　个顶点在平面上　／　＼、　＞　√　图５三角形面片的三个顶　图６三角形面片的三个　点在平面上　顶点均不在平面上，面片　有两条边和平面相交　２．２分割算法　分割就是用一个特定平面将一个空间物体分　块。实际上是平面与空间物体的求交过程。首先使　用结构体双向链表来存储三角形面片的数据信息。　有利于插人和删除运算，数据结构体如下：　ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ｏｎｅｆａｃｅ　｛　ｆｌｏａｔ　ＳＴＬＮｏｒｍａｌ３ｆ［３］；，／三角形面片的法向量　ｆｌｏａｔ　ＳＴＬＶｅｒｔｅｘ３ｆｌ［３］；／／三角形面片顶点１　ｆｌｏａｔ　ＳＴＬＶｅｒｔｅｘ３ｆ２［３］；／／三角形面片顶点２　权值及邻接面片的共享　｜｜迦青号　ｌＦａｃｅ；　具体的分割算法如下：　１）读人一个铸件的三维实体ＳＴＬ文件，保存到　相应结构体双向链表ｓｏｕｒｃｅ＿ｆａｃｅ中。并用计算机显　示出待分割的实体。　２）建立两个新的结构体双向链表ｌｅｆｔ＿ｆａｃｅ和　ｉｒｇｈｔ　ｆａｃｅ，分别用于保存位于切割平面之左、之右的　三角形面片。　３）根据切割要求，选一个坐标值为ｍ的平面（ｘ　平面，Ｙ平面或Ｚ平面）作为切割面。　４）读出保存在结构体双向链表ｓｏｕｒｃｅ＿ｆａｃｅ中的　第一个三角形面片的信息。　５）分割平面　６）找保存在结构体双向链表ｓｏｕｒｃｅ＿ｆａｃｅ中的下　一个三角形面片的信息，若找得到则返回第五步，　找不到则结束。　２．３分割平面　在交割中需要判断三角形面片和切割平面的　关系，如果三角形面片和切割平面的关系为第一　种，第二种或第四种，则根据三角形面片和切割平　面的相对位置（在切割平面的右边还是左边），把三　角形面片复制后放人新的结构体双向链表ｌｅｆｔ＿ｆａｃｅ　或ｒｉｇｈｔ＿ｆａｃｅ中：如果这个三角形面片和切割平面　的关系为第五种。则把三角形面片复制两份后分别　放人新的结构体双向链表ｌｅｆｔ＿ｆａｃｅ和ｒｉｇｈｔ＿ｆａｃｅ中。　如果这个三角形面片和切割平面的关系为第三　种，则把三角形面片Ａ沿切割平面分成　。Ｃ两个三　角形面片，并根据　，Ｃ和切割平面的相对位置，把三　角形面片　和三角形面片ｃ复制后分别放人新的结　构体双向链表ｌｅｆｔ＿ｆａｃｅ或ｒｉｇｈｔ＿ｆａｃｅ中（图７）。　如果这个三角形面片和切割平面的关系为第　六种，则把三角形面片Ａ分成　，Ｃ。Ｄ三个三角形　面片，并根据　，Ｃ，Ｄ和切割平面的相对位置，把三　角形面片　，三角形面片Ｃ和三角形面片Ｄ复制后　分别放人新的结构体双向链表ｌｅｆｔ＿ｆａｃｅ或ｒｉｇｈｔ＿ｆａｃｅ　中（图８）。　３不完整ＳＴＬ的处理方法　维普资讯 http://www.cqvip.com Ｆｅｂ．２０ｏ８№ｌ　铸造设备研究　２００８年第１期　／　Ａ　’‘｝ｃｕｔｌｉｎｅ；　根据ＳＴＬ文件的共顶点规则，每一个三角形面　＼／　／　片只能由三个邻接的三角形。由此建立的三角形面　片邻接关系［　］如图９所示。　三角形面片１　相邻三角形面片０Ｈ相邻三角形酣１　Ｈ相邻三角形酣２　三角形面片２　相邻三角形面片０卜＿叫相邻三角形面片１　ｌ　ｒｌ相邻三角形面片２　／　图７当三角形面片的一个顶点在平面上。另两个顶点　在平面的两侧时的分割情况　／　Ａ　－．　－＼　√　／　●　、　’、　．　＼．　图８当三角形面片的三个顶点均不在平面上。　面片有两条边和平面相交时的分割情况　３．１镶嵌技术　使用结构体双向链表来存储截面轮廓线中每　一条线段的数据信息，数据结构体如下：　ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ｃｕｔｌｉｎｅ　｛　…　…　ｌｆｏａｔ　ＳＴＬＶｅｒｔｅｘ３ｆＡ［３］；　／／线段顶点１　ｌｆｏａｔ　ＳＴＬＶｅｒｔｅｘ３ｆＢ［３］；　／／线段顶点２　切割平面相交的交线是截面轮廓线，通过三角　形面片的邻接关系表，形成了一个三角形之间的有　向加权图。其中权值为邻接面片的共享边的序号。　其具体算法如下所示：　１）从所有的三角形面片中找到一个在切割范　围之内的三角形面片。　２）从这个三角形面片出发，搜索其相邻的三个　邻接三角形。并通过权值得到与邻接三角形面片之　间的共享边。　３）￣ｌＪ断这条边是否在切割范围之内，如果是则　计算出交点坐标，同时设置三角形访问标志　ｆａｃｅ—ａｓｋ＝ｔｒｕｅ。这样依次追踪，直到回到第一个被访　问的三角形面片，得到一条有向封闭的轮廓线。　４）重复上述过程，直到所有轮廓线计算完毕。　为了使ＯｐｅｎＧＬ的速度尽可能快，所有的几何　图元都必须是凸的，但ＯｐｅｎＧＬ工具函数库包含了　一些函数，可以自动把凹多边形分解为更小的．处　理效率更高的ＯｐｅｎＧＬ图元。这种对多边形进行分　解的过程叫做镶嵌。　‘　镶嵌是通过镶嵌器来发挥作用的，以下是镶嵌　器的使用步骤［　］：　１）创建镶嵌器对象。　２）设置镶嵌器的状态和回调函数。　３）开始一多边形。　４）开始一条轮廓线。　５）向镶嵌器对象输入指定这条轮廓线的顶点。　６）结束这条轮廓线。　７）如果还有更多的轮廓线，回到步骤４。　８）结束这个多边形。　／／仓０建镶嵌器对象　ｐＴｅｓｓ＝ｇｌｕＮｅｗＴｅｓｓ（）；　／／设置镶嵌器的状态和回调函数　ｇｌｕＴｅｓｓＣａｌｌｂａｃｋ（ｐＴｅｓｓ，ＧＬＵ＿ＴＥＳＳ＿ＢＥＧＩＮ，　（ｖｏｉｄ（ｓｔｄｃａｌｌ　）（））ｇｌＢｅｇｉｎ）；　ｇｌｕＴｅｓｓＣａｌｌｂａｃｋ（ｐＴｅｓｓ，ＧＬＵ＿ＴＥＳＳ＿ＥＮＤ，　（ｖｏｉｄ（ｓｔｄｃａｌｌ　）（））ｇｌＥｎｄ）；　维普资讯 http://www.cqvip.com ２００８年第１期　牛晓峰，等：基于ＯｐｅｎＧＬ的ＳＴＬ文件剖分及填充显示技术研究　ｇｌｕＴｅｓｓＣａｌｌｂａｃｋ（ｐＴｅｓｓ，ＧＬＵ＿ＴＥＳＳ—ＶＥＲＴＥＸ，　（ｖｏｉｄ（ｓｔｄｃａｌｌ　）（））ｇｌＶｅｒ　ｔｅｘ３ｄｖ）；　３）判断当前多边形其余　Ｌ１１Ｌｋ２或Ｌ１２Ｌｋ２相交，若是，转　／／如何计算填充和开放区域　ｇｌｕＴｅｓｓＰｒｏｐｅｒｔｙ（ｐＴｅｓｓ，ＧＬＵ＿ＴＥＳＳ＿ＷＩＮＤ　ＩＮＧ＿ＲＵＬＥ，ＧＩ　Ｕ＿ＴＥＳＳ＿ＷＩＮＤ　ＩＮＧ＿ＯＤＤ）；　／／开始多边形　ｇｌｕＴｅｓｓＢｅｇｉｎＰｏｌｙｇｏｎ（ｐＴｅｓｓ，ＮＵＬＬ）；　／／第一条轮廓线　ｇｌｕＴｅｓｓＢｅｇｉｎＣｏｎｔｏｕｒ（ｐＴｅｓｓ）；　ｆｏｒ（ｉ＝０；ｉ＜第一条轮廓线上点的个数；ｉ＋＋）　ｇｌｕＴｅｓｓＶｅｒｔｅｘ（ｐＴｅｓｓ．轮廓线上第ｉ个点的信　息，轮廓线上第ｉ个点的信息）；　ｇｌｕＴｅｓｓＥｎｄＣｏｎｔｏｕｒ（ｐＴｅｓｓ）；　／／第二条轮廓线　ｇｌｕＴｅｓｓＢｅｇｉｎＣｏｎｔｏｕｒ（ｐＴｅｓｓ）；　ｆｏｒ（ｉ＝Ｏ；ｉ＜第二条轮廓线上点的个数；ｉ＋＋）　ｇｌｕＴｅｓｓＶｅｒｔｅｘ（ｐＴｅｓｓ．轮廓线上第ｉ个点的信　息，轮廓线上第．ｉ个点的信息）；　ｇｌｕＴｅｓｓＥｎｄＣｏｎｔｏｕｒ（ｐＴｅｓｓ）；　／／绘制其它所有的轮廓线　／／完成这个多边形的所有操作　ｇｌｕＴｅｓｓＥｎｄＰｏｌｙｇｏｎ（ｐＴｅｓｓ）；　／／不再需要镶嵌器对象　ｇｌｕＤｅｌｅｔｅＴｅｓｓ（ｐＴｅｓｓ）；　ｇｌｕＴｅｓｓＰｒｏｐｅｒｔｙ（ｐＴｅｓｓ，ＧＬＵ＿ＴＥＳＳ＿ＷＩＮＤ　ＩＮＧＲＵＬＥ，ＧＬＵＴＥＳＳＷＩＮＤＩＮＧ＿—＿＿ＯＤＤ）中的　ＧＬＵ＿ＴＥＳＳ＿ＷＩＮＤＩＮＧ＿ＯＤＤ表示多边形内部奇数　条轮廓线所包围的区域内的所有的点都是填充的。　３．２三角化处理　为准备对分割后的ＳＴＬ文件再进行多次分割，　故对截面轮廓进行三角化处理．并把三角化的结果　加到分割后生成的两个新的ＳＴＬ文件中去：　使用Ｄｅｌａｕｎａｙ三角剖分法，其具有简洁，通　用等特点。规定沿面上任一条边前进时，其左侧　定义为图形区域，右侧定义为非图形区域，￣０９１，　环按逆时针走向，而内环按顺时针走向。具体算　法如下［’Ｊ：　令该多边形的边数为Ⅳ．第Ｋ条边的起点序号　为Ｌｋ１．终点序号为Ｌｋ２　１）若Ⅳ＝３，则该多边形本身是一个三角形，剖　分结束；否则令Ｋ＝Ｉ，转入（１）。　２）令Ｋ＝Ｋ＋Ｉ，若Ｌｋ２不在有向线段Ｌ１１一＞　１２　之左，转入（２），否则转入（３）。　（４）。　４）保存节点Ｌｋ２至候选节点　转入（５），否则转入（２）。　５）从候选节点列表中求出与　成的外接圆最小的节点Ｌ０２．则：　Ｌ０２必然构成一个有效的Ｄｅｌａｕｎａ　当前多边形作如下修正：　①若线段Ｌ１１Ｌ０２及Ｌ１１Ｌ０２　形的边界线段．则令Ｎ＝Ｎ＋Ｉ．Ｌｎ　Ｌ１２＝Ｌ０２，转入（１）。　②若线段Ｌ１１　Ｌ０２（或Ｌ１２ＬＯ　的第ｍ条边，而线段Ｌ１２Ｌ０２（或上　多边形的边，则令Ｌ１１＝Ｌ０２（或　Ｌｎｌ，Ｌｍ２＝Ｌｎ２，Ｎ＝Ｎ－１，转入（１）。　③若线段Ｌ１　１Ｌ０２和Ｌ１２Ｌ０２　形的第ｍ边和第　边．则将线段　第　边从当前多边形中删除，Ｎ＝Ａ　ｌＯ为ＳＴＬ文件。　ａ）完整的ＳＴＬ文件　ｂ）　图１０应用实例　４结论　本文通过判断三角形面片和　关系实现了ＳＴＬ文件的分割．在卒｝　件时采用了两种方法．一种是采，Ｆ　嵌技术．该法只适用一次分割；另　轮廓进行三角化处理，并把三角　后生成的两个新的ＳＴＬ文件中去　分割　参考文献：　［１］赵吉宾，刘伟军，王越超．基于ＳＴＬ文　［Ｊ］．机械科学与技术，２００５，２４（２）：１３１　『２］Ｒｉｃｈａｒｄ　Ｓ　Ｗｒｉｇｈｔ．ＯｐｅｎＧＬ超级宝典（　民邮电出版社．２００５．　［３］丁永祥，夏巨谌，王英，等．任意多边珏　『Ｊ］．计算机学报，２００４，ｌ７（４）：２７０～２７１