面向快速原型制造的数据模型简化处理
面向快速原型制造的数据模型简化处理
罗建春,高诚辉,彭育辉
(1.中铁西南科学研究院有限公司,四川成都 611731;2.福州大学机械工程与自动化学院,福建福州 350002)
摘要:随着坐标测量设备的发展,获取包含被测物体更多细节的海量数据已非常方便,但复杂且冗余的数据模型既对计算机的存储容量、处理速度、绘制速度、传输效率等都提出了很高的要求,又在一定程度上影响了制造企业响应市场的快速性。本文对快速原型数据模型进行了简化处理研究。首先,依据网格简化的特点,提出了一种快速重建STL模型拓扑信息的新算法;然后,在总结三角形折叠型简化算法简化过程的基础上,提出了一种改进的基于三角形折叠的模型简化算法;最后,通过自行开发的数据模型简化处理系统实现了该算法,并进行了大量的示例验证。实验结果表明,本文提出的简化算法能够很好地简化光滑平坦区域,同时对曲率变化较大的局部区域的简化效果也比较明显。
关键词:快速原型制造;网格简化;三角形折叠;模型简化系统
中图分类号:TH164 文献标识码:A 文章编号:
1
2
2
Simplification of the datum model based on rapid prototype manufacture
LUO Jianchun1,GAO Chenghui2,PENG Yuhui2
(1 China Railway Southwest Research Institute Co.,Ltd.,Chengdu 611731,China;
2 School of Mechanical Engineering and Automation,Fuzhou University,Fuzhou Fujian,China)
Abstract: With the development of the coordinate measuring equipment, it is very convenient to obtain the mass data that contains more details of the object to be tested. However, the redundant and complicated models require huge capability of the memory, faster processing, and faster drawing and higher transferring efficiency; also, the manufacture enterprises can’t response the market as soon as possible. This thesis is dedicated to datum model simplification in rapid prototype manufacture. Firstly, a novel arithmetic was proposed to rebuild topological structure about STL model based on the feature of mesh simplification, and then we survey some existed model simplification algorithms. On the basis of our research work, we present an improved algorithm for simplifying triangle mesh models, which is based on collapse operation for triangles in meshes. Last, we developed a simplification system based on our algorithm and gave lots of demonstration. Results from our system show that the algorithm provided in our paper can simplify the smooth and plain area better, and make huge achievement in the area of the small curvature.
Key words: rapid prototype manufacture; mesh simplification; triangular collapse; model simplification system
0 引言
快速原型制造技术的发展,不仅满足了消费者日趋主体化、个性化和多样化的需求,而且还使得产品设计、制造的周期大大缩短,提高了产品设计、制造的一次成品率,降低了产品开发成本,从而给制造业带来了根本性的变化。然而,随着三维测量设备在测量效率、精度等方面的突破,目前应用于快速原型制造的网格数据模型越来越精细、越来越复杂,这些复杂的模型动辄就
产生数以万计的三角形面片。如此复杂的模型对
计算机的存储容量、处理速度、绘制速度、传输效率等都提出了很高的要求。同时也在一定程度上影响了制造企业响应市场的快速性,如:过度精细的模型增加了快速原型机的数据处理时间。更有甚者,由于计算机的内存容量有限,当STL数据模型文件太大时,计算机无法全部将STL文件一次读入计算机内存,使得后期不能正常切片。因此我们有必要对快速原型制造中的数据模型进行简化处理,即用一些相对简单的数据模型
来替代原始数据模型。本文在研究过程中,首先对原始模型数据文件中的三角面片之间的拓扑关系进行了快速重建,接着根据快速原型制造模型数据自身的特点,对传统三角形折叠简化算法进行了深入研究,针对算法中的误差矩阵计算、新点位置确定和折叠误差函数定义等几个关键问题进行了改进。最后,开发了面向快速原型制造数据模型简化处理系统,该系统能够有效地简化快速原型制造中复杂的数据模型。
1 快速重建STL拓扑信息
STL是一种离散的实体表面三角面片模型,目前各种通用造型系统,如:UG、Pro/E、Solid Edge以及SolidWorks等都能产生并输出这种实体模型。该模型记录了将实体表面离散处理后得到的所有三角面片信息,描述了每一个三角面片的顶点坐标及其法向矢量。然而,一个三角面片在计算机中的存储是随机的、杂乱的,各三角形之间缺乏明显的拓扑关系,所以STL文件只是表达了物体表面的数值信息。在实际应用中需要重新构造STL三角面片之间的拓扑关系,即邻接关系[1](包括面片的邻接面、顶点的邻接面/邻接顶点等)。 1.1 数据结构
网格模型简化算法的实现需要考虑顶点(Vertex)和三角面(Face)的几何信息以及两者之间显式的拓扑关系,它们相互之间的访问和遍历在算法实现中是必要的,并且要求以下几种主要的拓扑访问能够快速实现:
(1)已知三角面,获取它的三个顶点; (2)已知三角面,获取与它相邻的所有三角面;
(3)已知顶点,获取以它为顶点的所有三角面的集合;
(4)已知顶点,获取与它相连接的所有顶点;
在网格模型简化的过程中,由于退化几何元素的不断删除和新生成几何元素的不断出现,网格模型的拓扑关系始终在变化,并且需要同步更新。但是,对几何元素相关信息的大多数更新操作通常需要分别对不同的几何元素进行搜索,而网格模型中各种几何元素均具有相当大的数量级。因此,不同的几何元素须分别用不同的存储结构进行存储,同时在各自的结构中保存相互之
间的拓扑联系。由于拓扑关系重建和网格简化在
面的存储结构中进行查询的次数较少,所以选择简单的双向链表作为面的存储结构。顶点的存储结构和面的存储结构同步创建,但需要进行查询的次数很多,宜选用查询效率较高的平衡二叉查找树作为其存储结构。
2.2 建立顶点归并和邻接关系
在确定三角面各构成顶点之间的邻接关系时,具体的操作情况可分为以下三类:
(1)如果当前三角面的三个顶点均是新顶点,或者其中的两个顶点是第一次出现,则可以分别将其中的两个顶点作为余下的那个顶点的邻接点进行记录。
(2)如果当前三角面中仅有一个顶点是首次出现,则仅仅将两个重复的顶点作为新顶点的邻接点进行添加。
(3)如果当前三角面的三个顶点都已经在顶点的存储结构中被记录过,则需要分别在各顶点的邻接点堆栈中搜索是否已存在另外两个顶点,并根据重复的情况确定是否添加它们作为自己的邻接点。
图1 重建STL拓扑信息流程图
在顶点的归并过程中,每读取一个三角面,可以建立一个新的三角面的记录,在该记录中用顶点的索引代替顶点的坐标信息。这样,从文件中每读取一个三角面,既可以为这个面和它的构成顶点建立自己的记录(如果该顶点未在顶点的存储结构中记录),也能够同时建立这三个构成顶点之间以及这些顶点和当前的三角面之间的拓扑邻接关系。而后续读取的三角面除了向面和顶点的存储结构中添加新的记录外,也对已记录
顶点的邻接顶点信息和邻接面信息进行完善。在完成STL文件中所有三角面的读取之后,不仅可以建立顶点的存储结构和顶点的完整拓扑关系(顶点的邻接面、邻接顶点等),也建立了面的存储结构以及每个面与其构成顶点之间的联系,在此基础上,对面的拓扑关系进行完善。重建STL模型拓扑信息的流程图如图1所示。
2 数据模型简化算法
依据快速原型制造加工过程中对数据模型的要求,在研究和比较现有的各种网格简化算法 [2-5]
的基础上,本文提出了一种改进的基于三角形折叠的面向快速原型制造数据模型简化算法。 2.1 基于三角形折叠网格简化算法描述[3]
(1)对原始网格中的每个三角形,计算其误差矩阵。
(2)对原始网格中的每个三角形,通过误差矩阵计算折叠后生成的新顶点的位置和折叠误差。
(3)按折叠误差从小到大排列三角形。 (4)从三角形序列中取出折叠误差最小的三角形执行折叠操作,更新所有相关信息。
(5)若三角形序列为空或误差已达到用户要求,则简化操作结束;否则,执行(4)。 2.2 基于三角形折叠的数据模型简化算法改进
传统算法中,每个三角形折叠后产生的折叠误差都是通过误差矩阵来确定的。在求误差矩阵时,必须先求得折叠后新顶点的位置,而新顶点位置的求得必须先知道误差矩阵中各元素的值,因此,误差矩阵具有不确定性。本文在前人算法的基础上进行了改进,改进的内容包括误差矩阵的修正、新点位置的确定、控制函数的定义和折叠误差的确定。
(1)误差矩阵的修改。对要进行折叠操作三角形的三个顶点所有相关三角形的误差矩阵相加,将得到的误差矩阵作为该三角形的误差矩阵,从而解决了原有算法中误差矩阵不确定这一问题。
(2)新点位置的确定。根据三维实体模型的表面特征,本文在新点位置确定的过程中,分两种情况计算折叠后新点的位置:①当表面是平面时,新点的位置为折叠三角形的中心;②当表面是曲面时,采用基于点到平面距离平方和最小的二次误差度量方法求取新点位置。
(3)控制函数的定义。本文改进传统单一的简化标准,采用包含折叠前后相关三角形转动的二面角、折叠三角形的面积、折叠三角形的纵横比等三个分项的控制函数作为简化优先的主要依据。
(4)折叠误差的确定。控制函数仅表示当前三角形折叠前后的变化特征,而不能表达该区域简化的历史情况,为了从总体上有效控制简化后网格与原始网格的差异,本文定义了一个全局误差,用来引导模型化简。
3 数据模型简化处理系统的设计
3.1 系统总体框图
基于改进的三角形折叠简化算法,设计了一个面向快速原型制造数据模型简化处理系统。该系统的总框图如图2所示。
图2 面向RP数据模型简化处理系统总体框图
3.2 数据结构设计
快速原型制造数据模型的数据量较大,非常有必要通过优化数据结构[6]来提高数据存取效率,从而进一步提高简化速度。考虑到顺序结构具有最优的存取效率,因此,在程序中尽可能地使用顺序结构来存储顶点和三角形序列。对于系统中大量的排序过程,选取了堆排序。一方面堆排序是运行效率最高的排序算法之一,另一方面由于堆排序中的堆是一棵完全二叉树,因而易于用静态数组表示,再者,通过交换堆顶和当前堆
的最后一个元素,无须改动数据结构就可以实现将己折叠的元素排除在继续折叠的元素之外。 3.3 简化过程的实现
本文简化过程的实现主要是控制简化的进行,包括设置简化参数、调整待排序三角形队列、修改各三角形误差函数等等,简化过程的具体的步骤如下:
(1)遍历所有三角形,为三角形面片信息赋初值;
(2)计算所有面的折叠误差函数值; (3)误差函数值建堆;
(4)利用堆排序建一折叠优先队列; (5)设置简化参数(面片数或简化率); (6)While(面片数>设置值)
{ 取堆顶元素heaptop; If (flag==0)
{ 折叠heaptop三角形;
更新邻接三角形拓扑结构; 计算三角形新点、误差函数值,并置flag为1;
面片数减4;}
取堆中的下一元素;
If(所有三角形的flag==1)break; }
(7)If (面片数≤设置值) 退出; Else 转(2)。 3.4 三角形折叠操作的实现
三角形折叠操作的过程主要是对被折叠三角形及其相关三角形区域进行简化后的修改。其修改内容包括:将折叠三角形以一个新点代之,将此三角形及其共边三角形标记为消失,其共点三角形标记为冻结并修改顶点序号,与其共点三角形具有点相关和面相关的三角形集合也都发生了改变,并作相应的增减。
3.5 数据模型简化处理系统的界面设计
本数据模型简化处理系统是基于OpenGL和MFC[7]开发设计的,主界面如图3所示。主界面包括菜单区、工具栏图标区、状态栏区和图形显示区。菜单区包括了文件、操作和帮助三项下拉菜单。文件下拉菜单中包括打开模型、关闭文件、保存模型、保存文件和退出;操作下拉菜单包括模型和绘制模式两项,其中模型分为原始模型和简化模型,绘制模型分为线框图和实体图;帮助下拉菜单中仅有相关信息这一项(列出
该系统的版权信息)。工具栏图标区给出了打开
模型文件、保存简化模型、简化模型的快捷图标以及显示模型各种效果的选项,包括缩放、旋转、平移、显示/隐藏坐标轴、激活/取消旋转惯量等等。图形显示区是绘制快速原型数据模型的区域。状态栏区标明了当前系统进行的状态以及显示简化前后三角面片的数目。
图3 模型简化处理系统界面
4 试验结果与分析
(1)如图4所示,小熊模型中原模型(a)共有23031个顶点,45853个三角面片。通过简化处理系统简化后,模型(b)保留了20%的面片、模型(c)保留了10%、模型(d)保留了1%。从图中可以看出模型(b)、(c)基本保持了原始模型的细节特征,而模型(d)眼睛、嘴巴、胸前等部位已丢失部分细节特征。另外,传统算法获得的底部平面网格模型汇聚于一点,造成大量狭长三角形的产生,而本文设计的模型简化算法避免了这一弊端,生成的三角面片大小、分布均匀,从而为快速原型制造提供了优质的网格模型。
(a) (b) (c) (d)
图4 小熊模型
(2)如图5所示,小猪模型中原模型(a)共有23358个顶点,46712个三角面片。通过简化处理系统简化后,模型(b)保留了10%的面片、
模型(c)保留了5%。从图中可以看出模型(b)、(c)很好地保持了原始模型的细节特征。
(a) (b) (c)
图5 小猪模型
(3)如图6所示,气门摇臂模型中原模型(a)共有1704个顶点,3408个三角面片。通过简化处理系统简化后,模型(b)保留了30%的面片、模型(c)保留了20%、模型(d)保留了10%。从图中可以看出模型(b)基本保持了原始模型的细节特征,模型(c)在圆柱、孔等部位发生了微小的变化,尤其是中间大圆柱和右边圆柱之间的一部分曲面相对(a)和(b)已变得更加的尖锐,而模型(d)孔等部位已丢失部分细节特征,已变成了类四方体空洞。
(a) (b)
(c) (d)
图6 气门摇臂模型
(4)与传统的三角形折叠型简化算法相比,
面向快速原型制造简化算法在简化操作时间和简化误差方面具有显著的优势(见表1)。
表1 简化算法实验结果对比
5 结语
(1)本文通过快速重建STL拓扑信息,在传统算法的基础上提出了一种改进的基于三角
形折叠的简化算法,并将其应用于快速原型制造数据模型的简化处理。验证结果证明,该简化算法能够很好地简化光滑平坦区域,同时对曲率变化较大的局部区域的简化效果也比较明显。
(2)快速原型制造技术中数据模型的简化仅仅是三维网格模型简化的一个应用方向。随着网络技术的发展,RPM技术在网络远程设计制造系统中的应用越来越广泛,同时对模型网格简化算法的要求越来越高,因此实时性更强的动态简化方法将是未来远程RPM数据模型简化研究的一个方向。
参考文献
[1] 张必强,刑源,阮雪榆.面向网格简化的STL拓扑
信息快速重建算法.上海交通大学学报,2004年1月第38卷第一期
[2] Garland, M., Heckbert, P.S. Surface simplification
using quadric error metric. In: Proceedings of the SIGGRAPH’97. 1997. 209-216
[3] 周昆,潘志庚,石教英.基于三角形折叠的网格
算法.计算机学报,1998, 21( 6): 506-513 [4] Li, Gui-qing, Li, Xian-min, Li, Hua. Mesh
simplification based subdivision. In: Pan, Yun-he,
ed. Proceedings of the 2nd International Conference on Computer-Aided Industrial Design and Conceptual Design (CAID & CD’99). Bangkok: International Academic Publishers, 1999. 351-355 [5] 费广正,吴恩华.基于递进网格的多层次模型编
辑.计算机学报,2000,23(9): 953-959
[6] 徐孝凯.数据结构实用教程(第二版).清华大学
出版社,2006
[7] 郭兆荣,李菁,王彦.Visual C++ OpenGL应用程序
开发.人民邮电出版社,2006. 作者简介:罗建春,硕士,工程师,主要从事数字化设计、隧道施工机械化与设备研究。 E-mail: [email protected]
身份证号码:[***********] 工作单位:中铁西南科学研究院有限公司
联系地址:四川省成都市高新西区双柏东二街188号 邮政编码:611731 联系电话:[1**********]