（通信与信息系统专业论文）三角形网格自适应技术研究.pdf

西南科技大学硕士研究生学位论文第1 页 摘要 几何信息模型是实现多学科协同仿真的基础。s t l 模型( 一种三角形物面网格 模型) 具有数据结构简单并且与三维c a d 系统无关的优点，已经成为多学科仿真 采用的主要几何信息模型之一。 现有商业c a d 系统生成的s t l 模型，主要考虑形状逼近的精度，而非考虑三角 形的形态和密度，故亟需基于曲率与压力梯度的三角形网格的自适应技术，以满 足多学科协同数值仿真对物面网格的需求。虽然该技术一直是国外的研究热点， 但到目前为止，国内在这方面全面的、系统的研究未见文献报道，为此，本文展 开以下研究： ( 1 ) 提出基于曲率与压力梯度的三角形网格自适应思想，并采用基于三变量四 次b 6 z i e r 曲面块实现三角形网格的几何重建，确保自适应前后网格几何精度保持一 致。 ( 2 ) 研究三角形物面网格的几何与拓扑关系重建的方法，建立相应的几何重建 和拓扑信息恢复算法。 ( 3 ) 提出基于长度优先的细分( 简化) 边的搜索方法，以利用边分割、边消去 法和边转换成熟技术，得到边长都接近目标边长的网格单元。 ( 4 ) 提出局部动态的参数化技术，将整个网格模型分解为多个可重叠的区域， 既避免3 d 几何结构映射到参数化平面时可能产生的严重几何变形，又将三角形网 格的自适应简化为二维优化问题，确保自适应三角形网格的精度与效率。 ( 5 ) 丌发了基于s t l 的三角形表面网格重构系统r e m e s h 2 0 0 8 软件，多个工程 实例论证了上述研究的有效性和实用性。 本文提出的算法还可以应用到以下领域：计算机图形学、可视化计算、虚拟 现实建模等领域中，解决网格数量和渲染的速度及质量问的优化技术难题。 关键词：自适应网格优化三角形多学科协同仿真 西南科技大学硕士研究生学位论文 第1 i 页 a b s t r a c t g e o m e t r i cm o d e li st h eb a s e m e n to fm u l t i d i s c i p l i n a r yc o l l a b o r a t i v es i m u l a t i o n ， a n ds t lm o d e l ( at r i a n g u l a rs u r f a c em e s h ) h a sb e c o m eo n eo fm a i ng e o m e t r i cm o d e l s u s e db ym u l t i d i s c i p l i n a r yc o l l a b o r a t i v es i m u l a t i o n ，b e c a u s eo fi t ss i m p l ed a t as t r u c t u r e a n di n d e p e n d e n c eo fc a d s y s t e m t h es t lm o d e lg e n e r a t e db yc a d s y s t e mu s u a l l yr e f l e c t st h er e g u l a rs a m p l i n go f t h eu n d e r l i n gp a r a m e r t r i cd o m a i ni n s t e a do fc a dm o d e l sf e a t u r e s ，t h e r e f o r et h e a d a p t i v er e m e s h i n gd r i v e db yc u r v a t u r eo rp r e s s u r ei sn e e d e df o rm u l t i d i s c i p l i n a r y c o l l a b o r a t i v es i m u l a t i o n a l t h o u g ha d a p t i v er e m e s h i n gi st h em a i nr e s e a r c ht o p i c so f o v e r s e a sc o m p u t e rg r a p h i c s ，t h et h e s i so fd o m e s t i cr e s e a r c h e rh a sn o tb e e ns e e nf o r m u l t i d i s c i p l i n a r yc o l l a b o r a t i v es i m u l a t i o n a sar e s u l t ，t h em a i nr e s e a r c h e si nt h i sp a p e r a r ea sf o l l o w s ： ( 1 ) ar e m e s h i n gm o t h e dd r i v e db yc u r v a t u r ea n dp r e s s u r eg r a d i e n t si sp r o p o s e d a n dt r i a n g u l a rc u b i cb 6 z i e rp a t c h e sa r ee m p l o y e dt or e c o n s t r u c tag 1 - c o n t i n u o u s s u r f a c e ，f o re n s u r i n gf i d e l i t yo ft h en e wm e s ht ot h eg e o m e t r yo ft h eo r i g i n a lm e s h ( 2 ) at o p o l o g i c a la n dg e o m e t r i cr e c o n s t r u c t i o nm e t h o da n di t sa l g o r i t h ma r e p r e s e n t e df o rt r i a n g u l a rm e s h ( 3 ) am o t h e do fs e e k i n ge d g eb a s e do nl e n g t hp r i o r i t yf o rs u b d i v i s i o na n d s i m p l i f i e dm e s hi sp r o p o s e dt og a i nn e wm e s h ，e a c he d g el e n g t ho fw h i c ha p p r o a c h st h e t a r g e tl e n g t ha f t e rp e r f o r m a t i o no fe d g e f l i p ，e d g e - c o l l a p s ea n de d g e - s p l i t ( 4 ) ad y n a m i cp a t c h w i s ep a r a m e t e r i z a t i o ni sd e s c r i b e dt op e r f o r ml o c a l m o d i f i c a t i o n si nm e s h e so p t i m i z a t i o n t h em e s hi sd i v i d e di n t oo v e r l a p p i n gp a t c h e s ， t h e r e f o r et h ef r e e d o mt oc h o o s et h es h a p ea n ds i z eo ft h ep a t c h e sc a nc o n s i d e r a b l y r e d u c et h ee r r o r ( d i s t o r t i o n ) c a u s e db ym a p p i n ga3 dm e s hw i t ha na r b i t r a r yg e n u sa n d h o l e st ot h e2 dp a r a m e t r i cd o m a i n ，a n dt h er e m e s h i n gm o d e li sf i d e l i t yt ot h eo r i g i n a l m e ha th i l g he f f i c i e n c y ( 5 ) at r i a n g u l a rs u r f a c er e m e s h i n gs o f t w a r en a m e dr e m e s h 2 0 0 8i sd e v e l o p e d t h ea l g o r i t h m sp r e s e n t e di nt h i sp a p e rh a v eb e e nv e r i f i e db yp r a c t i c a lc a s e s ，w h i c hh a v e s h o w e dt h a tt h e ya r eu s e f u l t h ea l g o r i t h m si nt h i sp a p e rc a na l s ob ea p p l i e di nm a n yo t h e rf i e l d ss u c ha s c o m p u t e rg r a p h i c s & i m a g e ，v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ，v i r t u a lr e a l i z a t i o ne t c s ， 西南科技大学硕士研究生学位论文第1 i i 页 w h e r et h e i rf o c u si so nt h et r a d e o f fb e t w e e nt h ev i s u a lq u a l i t yo ft h er e s u l t ，t h es p e e do f t h er e m e s h i n go p e r a t i o n ，a n dt h eo p t i m i z a t i o no ft h en u m b e ro fp o l y g o n si no r d e rt o a c h i e v ei n t e r a c t i v er e n d e r i n gs p e e d s k e yw o r d s ：a d a p t i v e ；m e s h - o p t i m i z a t i o n ；t r i a n g u l a r ；m u l t i d i s c i p l i n a r y c o l l a b o r a t i v es i m u l a t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得西南科技大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：l 参氓7同期：p 。瓴b 。，7 关于论文使用和授权的说明 本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 签名： 翩虢影咨慨 j 专i o 西南科技大学硕士研究生学位论文第1 页 1绪论 1 1研究背景 多学科协同仿真技术是一种新型的集成化产品设计与丌发手段贯穿于 复杂产品设计、试制、生产和评估的全生命周期中。其主要应用在飞机、汽 车、铁路机车车辆、轮船等大型复杂产品的开发过程中，在一些发达国家，如 美国、德国、同本等已经开始比较广泛地应用，包括制造业、工程机械、航 空航天、造船、机械电子、国防工业、通用机械等许多领域，相关技术的研 究工作也正在进一步深入开展。典型应用为波音公司采用产品全数字 化定义制作出波音7 7 7 整机虚拟样机，减少设计更改费用9 4 ，制造周期缩 短了5 0 。 在我国，多学科协同仿真的虚拟样机技术正在引起重视。在航天、航空、 汽车、铁路机车等行业，针对一些复杂产品的丌发，己开展了虚拟样机技术 的研究工作。国家“十一五”、“8 6 3 ”计划自动化领域现代集成制造系统主题 和国家制造业信息化工程领导小组对虚拟样机技术也非常重视，对虚拟技术 的多项有关课题进行了资助。 但目f j 仍然缺乏普遍适用的支持产品设计全过程的数字化产品开发系统， 尚未发现支持虚拟样机协同仿真的工具与环境。实施虚拟样机协同仿真的关 键就是如何开发出可信度高的虚拟样机，如何等效简化实际工况进行虚拟仿 真与试验，并在设计阶段就能完全预测评价产品的各项性能。由于虚拟样机 技术是不同领域仿真模型( c a d 、c f d 、c s d 等) 的有效集成与协同工作。 因此，实现虚拟样机协同设计与仿真的核心是如何对这些模型进行一致和有 效地描述、组织、管理和协同运行。重点研究对象是复杂产品多学科统一几 何信息建模技术、设计仿真过程协同管理技术、设计仿真数据管理技术、应 用工具集成及数据映射技术、协同平台通用基础组件集、设计仿真数据可视 化技术、数据安全管理技术、开放式软件架构技术等。 而面向多学科统一几何信息模型建模正是协同仿真得以实现的关键，能 否建立正确的几何信息模型，将直接影响仿真系统能否成功丌发。几何信息 模型建模的重要相关技术一网格自适应技术正是本文研究的重点。 西南科技大学硕士研究生学位论文第2 页 1 2 几何信息模型建模研究现状及需求 121 几何信息模型建模研究现状 c a d 技术是三维几何模型构建最重要的手段之，许多图形图像和动画 制作的软件也常常借助于c a d 进行三维建模，并能为建模附着材质，为场 景添加灯光，渲染出逼真的三维场景从而是设计者更好的表现自己的产品， 提高设计效率和成功率。 c a d 通常通过一系列的小面片来表示曲面，个比较复杂的曲面可能由 几百个小面片构成。从c a d 系统输出的模型可以保存为标准文件格式如 i g e s ( i n i t i a l g r a p h i c se x c h a n g es p e c i f i c a t i o n 基本图形交换规范) 、d x f ( d r a w i n ge x c h a n g e f o r m g 图形交换文件) 等，把c a d 中的文件输出成标准文 件格式后，鉴于c a d 造型内核并非使用同样的数学函数表达同一类型曲面、 判断曲面间无缝连接的精度也不尽相同，造成读入不同c a d 系统输出的实 体或表面模型文件时，将出现缝隙、搭接、起皱( 如图1 - 1 ) 所示，在进行 诸如c f d 和c s d 应用前处理之前必须对模型进行修补，难度大且费时 g - i o 。 而近些年柬，三角形网格模型在各种需要三维模型描述的领域中( 如有 限元分析、铸件凝固模拟、医学成像系统、反求工程等) 也都获得了具体的 应用该模型具有数据结构简单并h 与三维c a d 系统无关的优点，已经成 为连接c a d 和数值仿真的桥梁。如文献【1 1 】、 1 5 】和【1 7 】直接从c a d 输出的 三角形网格模型( s t l 模型) 生成有限元网格：文献 1 4 】利用s t l 模型进行铸 件的凝固进程模拟。因此对几何信息模型建模的研究将重点反映在三角形网 格模型的建立上，对i 角彤网格自适应技术的研究有着强烈的需求。 舅习 a ) 起皱b ) 裂缝 图卜1c a d 造型精度误差问题 f i g1 1 e rr o ro fc a dc a s t 西南科技大学硕士研究生学位论文第3 页 1 2 2三角形网格自适应技术的需求 对几何信息模型建模的三角形网格自适应研究需求范围非常广泛，其应 用需求主要有以下5 个方面： 计算机辅助几何设计( c a g d ) 的需要 n u r b s 和多边形网格是表示复杂三维模型的两种主要方法1 3 6 】。复杂形 体的造型是c a g d 中的关键问题。如何方便、有效地设计、编辑和修改表 达三维实体的几何模型，一直是科学家研究的重要课题f 25 | 。三角网格模型是 三维空间中由一系列相互连接的平面三角片组成的一种曲面离散逼近表达形 式，它在计算机图形学及c a g d 等领域得到了广泛应用。正确地建立三角网 格模型，对网格的后续处理具有重要意义。 逆向工程的需要 利用现有的三维重构软件或c a d 软件包进行曲面重构，要求操作人员 具备较强的专业知识和丰富的实践经验，而且工作量大、耗费时间多【2 9 】；并 且随着c a d 模型复杂程度的增加，商用c a d 软件将其转化为s t l 模型时可 能出现诸如因截断误差而导致的面片间的间隙、法矢错误等缺陷。这就使得 r p 制作者需要花费大量的时间和精力用在检验s t l 模型的正确性或修正其 错误上【32 1 。而直接从r e 测量数据经滤波平滑、拼接及重采样处理后，再利 用三角剖分算法直接输出s t l 模型，可以减少建模的时间和错误【2 3 】；此外， 测量数据点云经数据预处理后，通过插值或逼近的方法生成经向曲线，通过 空间曲线与平面的求交算法可直接获得r p 切层轮廓数据【32 1 。这样即可绕开 目前r e 技术的“瓶颈 一一三维散乱数据的复杂曲面重构与c a d 造型 有限元分析的需要 计算流体力学( c o m p u t a t i o n a lf l u i dd y n a m i c s ，简称为c f d ) 是以计算机 为工具，利用离散化网格技术和数值计算方法求解流体运动方程，从而揭示 流动机理和流动规律的科学。 对c f d 研究面临的问题是对计算空间的剖分，即在整个计算空间中生成 计算所必须的网格点分布，再进行有限元分析。在计算时采用的网格种类和 采用的网格生成方法对整个计算的最后结果精度有重要影响【5 1 。据文献介绍， 复杂外形流场表面描述及表面网格生成一般要占整个计算任务时间的7 0 8 0 嘣7 】。可见数值网格生成长期以来一直是计算流体力学的重要内容也是瓶 颈部分，网格质量直接影响数值计算的准确性。 近来复杂流场描述的研究一般借助于c a d 系统环境来降低这项工作的 复杂度。c a d 生成的s t l 模型可以直接划分为有限元单元网格3 9 】【4 0 1 ，进行 西南科技大学硕士研究生学位论文第4 页 原型的有限元分析，针对薄弱环节需要对其s t l 模型直接进行重建，以快速 制作出满足设计要求的计算原型网格。 3 d 视角技术的需要 目前3 d 游戏，3 d 电影等已经发展成为新兴的朝阳产业，带来巨大的商 业价值。而3 d 游戏的速度和视角效果一直是一对矛盾。高仿真的三维模型， 由于其数据信息的巨大，必将影响其模型数据流在网络上的传输速度。目前， 根据不同的视角环境的需要，对模型网格进行适当的简化和细化两种相异的 操作，达到网络三维游戏的速度和视角效果的最佳效果。 在3 d 电影中，三维动画是电影制作的核心技术，如何在三维模型上实 时地模拟各种运动，产生具有真实感的特技效果，是其中的一个难点。利用 三维自由变形d f f d ( d i r i c h l e tf r e e f o r md e f o r m a t i o n ) 和刚体运动模拟的混合 技术，同时，通过交叉的运动控制点模拟功能区之间运动的相互影响使得这 一难点得以解决。 虚拟现实技术的需要 目前虚拟现实技术应用十分广泛。医学上，虚拟手术的实现大大提高医 生对大型高难度手术的成功率。在日常生活中，网上购物将实现虚拟三维试 衣，虚拟试用等技术，提高人们的生活质量。工业上，虚拟实时监控，虚拟 装配等都己得到广泛应用，这些应用的基础正是对几何信息模型的三角形网 格自适应优化技术的研究结果。 1 3 本文和选题意义 1 3 1三角形网格自适应研究现状 十年来，国外已经提出了许多网格重整r e m e s h i n g 算法。其中的一类算 法【2 3 】【2 9 】【3 1 1 使用细分技术，将3 d 网格模型进行分区单独处理。该技术虽可 以获得满意的结果，但对分区后形成的区域结构非常敏感，并且顶点采样难 以控制。 最近提出了基于初始网格的全局参数化r e m e s h i n g 算法”厶5 4 j ，首先根据 参数化域进行采样。再将新生成的三角形“映射 回3 d 空间，改善原来的 网格模型。全局参数化r e m e s h i n g 方法的主要缺点是重构的网格质量对使用 的参数化因子十分敏感。将3 d 几何结构映射到参数化平面可能导致几何结 构与几何信息严重变形，因而无法将3 d 几何结构表示清楚，使几何特征丢 失。即使参数化将3 d 几何结构在尺寸上的变形降低到最小，但依然不能消 西南科技大学硕士研究生学位论文第5 页 除对几何特征所带来的误差。而且，全局参数化r e m e s h i n g 方法通常需求解 大量方程( 有时是非线性方程) ，故效率低。最近用m u l t i r e s o l u t i o n a l 方法1 5 5 j 加快了大型网格的求解速度。但当处理极大规模的网格时或具有严重等周变 形( 如袜子形状区域s o c k s h a p e dr e g i o n s ) 网格，数值计算精度将成为问题， 此时全局参数化r e m e s h i n g 方法几乎无法执行，除非使用多尺度或参数域的 精确算法式。除非使用多尺度或参数域的精确算法式。选择全局参数化网格 重构方法的主要原因是可直接在网格表面进行一系列的局部修改，即所谓的 网格自适应过程，也是本文的主要研究目的。 目前，国内网格重建也展丌了相关研究，如文献【6 4 提出一种基于网格 简化的三角网格参数化方法，该方法通过构建并参数化边界三角网格来自动 完成复杂三角网格边界的参数化，然后通过一系列局部计算完成网格内部点 的参数化。采用该方法得到的参数值可较好地反映三角网格的特性。但对于 数字化过程中采样率低、采样点分布离散性很大的三角网格，如果边界三角 网格展丌后是一个非凸多边形，则算法可能失效。又如文献【6 5 从模型中保 留的几何细节出发，提出一种自适应的三角网格简化算法，该算法首先比较 顶点与其相邻点之间的欧氏距离是否超过预先设定的简化尺度，删除小于该 尺度的相邻点，再对删除造成的空洞作局部三角剖分。但此算法未解决细节 度过大时局部三角剖分不萨确的问题。 据此提出本文的自适应网格重构思想。 1 3 2 研究内容确定 考虑到目前国外对三维模型的三角形网格自适应技术已经开展了一段时 间，并且在很多领域都得到了成功的应用，而国内类似的研究还很少见相关 报道，所以本文提出基于s t l 模型的三角形网格自适应优化软件系统，以统 一不同学科应用的前置数据处理过程，为多学科协同设计应用打下基础。基 于s t l 模型的三角形自适应网格优化软件系统的组织结构如图1 2 所示，由 以下1 0 个部分组成。 s t l 模型读入程序与数据输出程序，主要完成读入s t l 文件，并将处理 后的数据以s t l 文件格式或中间工程文件格式输出。 人机交互及显示程序，主要完成系统与操作者间的交流，并提供可视化 的操作过程，使操作者能够充分了解s t l 模型的外形、结构，便于设定s t l 模型处理参数。 面片整理程序，用s t l 模型的拓扑重建方法将读入的s t l 文件数据按 西南科技大学硕士研究生学位论文第6 页 照系统内部的数据结构进行存储，对模型进行几何压缩，减少三维数据的存 储空间和提高模型的传输速度。 s t l 模型拓扑分割程序，完成对s t l 模型的拓扑分割操作，用于s t l 模型的网格数据重组，形成新的s t l 模型。 s t l 模型细化程序，根据不同应用背景，计算s t l 模型加密特征驱动信 息，得到曲面三角形细化的标准，增加模型不同部位的网格细化程度。对c f d 应用而言就是根据压力梯度对狭长三角形的边进行剖分，提高计算网格的质 量。 s t l 模型简化程序，根据不同应用背景，在保证模型的特征形状不变的 基础上，对s t l 模型进行边融合，减少模型的三角形总体数量，对于三维游 戏应用来说，就是对于场景为远景的模型进行模型精简计算，得到大体轮廓 信息即可，有利于提高模型的网络传输速度。对于直接由扫描点云重构的网 格来说，一般数据量太大，有几十到几百力- 顶点构成的三角形，直接应用肯 定不行，所以就要对其三角形进行简化。 s t l 模型的三角形形态优化程序，用最小角最大化原则，对共边三角形 形态进行计算，得到更优形态的三角形。 s t l 模型顶点位置重构程序，在三角形网格进行完，细化，简化，形态 优化等操作后，对于局部三角形态可能得到优化，但对于整体而言，需要根 据三角形的相邻拓扑结构信息，移动模型顶点在曲面上的位置，得到更优的 三角形结构。 s t l 模型顶点法矢重计算程序，顶点的法矢非常重要，不仅反映顶点的 法矢方向，同时反映物面模型的曲面曲率特征信息，为判断模型的几何特征 信息提高重要依据。因此对网格进行重建后，由于顶点位置移动及相邻三角 形拓扑信息已经改变，其顶点法矢已经不存在，应对其法矢方向进行重计算。 例如在c f d 应用中，边界层贴体三棱柱网格的推进方向就是其顶点的法矢方 向，直接影响有限元分析的计算精度。 西南科技大学硕士研究生学位论文第7 页 图卜2基于s t l 三角形网格自适应软件系统组织结构 fig 1 2s t r u c t u r eo fm e s ha d a p t a tiv es o f ts y s t e m 1 3 3选题意义 针对基于s t l 的几何信息模型三角形网格自适应优化技术展开研究具有 以下意义。 计算机辅助几何设计( c a g d ) 的需要，弥3 # f c a d 软件不能够直接对s t l 模型进行再设计的缺陷 目前流行的c a d 软件，如p r o e 、u g 、i d e a s 、s o l i de d g e 等都只提供 了从c a d 模型转换到s t l 模型的功能，而不具有将s t l 模型转化为c a d 模型或直接对s t l 模型进行再设计的功能【4 4 】【45 1 。s t l 模型再设计软件使得 原型的再设计工作，不仅能通过对其c a d 模型的再设计加以完成，而且能 通过对其s t l 模型及其切层轮廓的再设计得以完成，便于r p & m 的实施。 针对r e 技术，满足生成高质量的物面网格的需求 通常曲面可以用两种方法生成，一种是由一系列有序的面片构成( 如 c a d 系统生成的) ，另一种是以离散的方式构成( 如r e 系统，三维扫描生 成) 。三维扫描仪获得的初始数据都是些离散顶点的三维坐标，首先对这些顶 西南科技大学硕士研究生学位论文第8 页 点进行处理，构造其问的拓扑连接关系，生成网格或参数曲面。而生成的初 始三角形面片因子数量巨大( 如生物医学图形数据可以达到几百力) ，有必 要使用三角形网格自适应优化将其数量降到一定的范围内，使之既能保持几 何近似的精确度，又能满足网格的质量要求， 针对有限元计算，对计算网格进行在设计，提高满足计算要求的网格 质量 由于三维空间复杂模型描述的复杂性，最初描述如实测流场的边界离散 点以人工方式，要对流场进行计算首先要处理这些点，耗时十分巨大，目前 复杂流场描述的研究一般借助于c a d 系统环境来降低这项工作的复杂度。 二维空间网格生成算法相对比较成熟，但是随着c f d 问题的复杂化，简单二 维算法的应用受到了很大的限制，人们把注意力转移到了复杂模型的网格生 成算法上。针对c a d 模型不能直接用于计算网格的情况，对c a d 模型进行 网格优化，快速生成计算网格，将大幅提高整个计算任务的效率。 针对生成高质量的虚拟现实，三维游戏模型的需要 目前，具有真实感的三维模型动画有着广泛的应用领域，可以用来制作 虚拟现实环境中的各种虚拟模型；可以用来制作和传输网络媒体，如虚拟播 音员、可视电话、远程网络会议等。另外，在电影制作、游戏娱乐等方面都有 着很好的应用前景。运用自适应优化技术正是这些应用得以实现的基础。 综上所述，本文对三角形网格自适应优化的关键技术开展研究是十分有 意义的。 1 4课题来源 国家高技术研究发展计划( 8 6 3 计划) 面向大型飞机机翼的非线性结构 气动力耦合优化关键技术研究( 2 0 0 7 a a 0 4 2 1 2 9 ) 。 1 5本文的章节安排 鉴于以上研究工作，本文的章节安排如下： 第一章绪论 第二章三角形物面网格的几何拓扑关系重建研究 第三章三角形网格自适应方法研究 第四章三角形网格的细化简化方法 西南科技大学硕士研究生学位论文第9 页 第五章三角形网格单元的优化方法研究 第六章基于s t l 模型网格重建软件显示平台设计 第七章结论 西南科技大学硕士研究生学位论文第1 0 页 2三角形物面网格的几何拓扑关系重建研究 基于三角形物面网格重建三维模型外形的几何曲面信息，对提升物面网 格重整质量至关重要。商业c a d 系统直接生成的三角形物面网格模型( 如 s t l 模型) 后，建模过程中的c 1 连续曲面块的精确数学表达已不存在；即使 有曲面块的精确数学表达式，在气动力使飞行器外形产生较大变形时，该数 学表达式也将失效，此时，通过重划分离散的三角面片是产生变形模型的唯 选择。网格重划分方法有：边分割( e d g e s p l i t ) 、边转换( e d g e f l i p ) 、边 消去法( e d g e c o l l a p s e ) 和顶点移动( v e r t e xr e l o c a t i o n ) | ，其中边分割将产生 新的顶点，而顶点移动则需要找寻顶点的新位置，因此，通过邻接三角形重 建物面网格所表达的几何信息( 即获得相应的光滑曲面) 是计算新的顶点坐 标的基础。 三角形物面网格模型( 如s t l 模型) 一般由散乱、无序存储的三角形组 成，没有直接体现三角形问的拓扑关系。为此，本章在分析归纳三角形物面 网格性质的基础上，研究其几何与拓扑关系重建的方法，提出相应的重建算 法和拓扑信息检索算法，为有限元分析网格生成技术实现奠定理论基础。 2 1 相关概念 2 。1 。1s t l 模型 s t l 模型是以s t l 文件格式纪录的三维欧式空间( r 3 ) 中的形体模型， 是目前最流行的一种三角形物面网格模型。近些年来，s t l 模型在各种需要 三维模型描述的领域中( 如有限元分析、铸件凝固模拟、医学成像系统、反 求工程等) 也都获得了具体的应用。由此可见，s t ，模型有着越来越广阔的 应用前景，对s t l 模型的再设计要求也越来越强烈。 2 。1 1 1s t l 文件 s t l 文件格式是1 9 8 7 年由美国3 ds y s t e m 公司提出的c a d 系统与r p 系统间的数据交换格式，最初是在s l a ( s t e r e o l i t h o g r a p h y ) 技术中得到应用， 但因为其在数据处理上比较简单，而且与c a d 系统无关，所以很快发展为 快速成型制造领域中c a d 系统与快速成型机之间数据交换的事实标准1 4 列 【5 7 】。s t l 文件的存储格式分为两种：二进制文件和a s c i i 文件。采用二进制 表达的s t l 文件的数据量比用a s c i i 格式的数据量要小得多，所以目前大多 西南科技大学硕士研究生学位论文第1 1 页 数s t l 文件都采用二进制格式。 s t l 文件的满足以下3 个准则。 右手法则 三角面片的法矢是一个单位向量，法矢的方向和它的三个顶点的排列顺 序符合右手法则，如图2 1 所示，1 ，。、v ：和v ，为三角面片的顶点，则其法矢： 品：芒兰当 ( 2 1 ) l v 鸬籼z v ，i 顶点和边法则相邻的两个三角面片只能共享两个顶点，即一个三角面 片与其相邻的三角面片有且只有一条公共边。 取值规则三角面片的顶点坐标值必须是正数，零和负数是错误的。 图2 - 1法矢方向与顶点的关系 f i g 2 1 r e i a t i o nb e t w e e nv e r t e xa n dn o r m a 2 1 1 2s t l 模型的性质 一般s t l 模型是通过对形体的c a d 模型进行表面三角化离散处理获得 的，是形体的一种近似表达方法。在制造业中，s t l 模型是表示零件的一种 方法，它通过三角面片逼近零件的表面，每个三角面片采用一个法矢和三个 顶点坐标来定义，三角面片的法矢是一个单位向量，指向实体的外部，因此 将s t l 模型记作 n t ：yz( 2 。2 ) ， 式中z 表示组成s t l 模型丁的第f 个三角面片，刀表示组成s t l 模型的三角 面片总数。 由于零件表面都是有界闭集，因此本文中所指的s t l 模型必然表示的是 三维欧氏空间中的正则形体，于是 ( 1 ) s t l 模型所有的三角面片，将三维欧氏空间分隔为两个互不连通 的三维子空间，即s t l 模型的内部和外部； ( 2 ) 除去组成s t l 模型的任意一个三角面片上的任何一点，s t l 模型 西南科技大学硕士研究生学位论文第1 2 页 的内部和外部将成为连通的三维子空间； ( 3 ) s t l 模型的任意一个三角面片的法矢指向s t l 模型的外部。 若将s t l 模型的顶点数记为n ( v ) ，边的总数为n ( e ) ，三角面片总数为n ( t ) ， 则 3 n ( t ) = 2 n ( e ) ( 2 - 3 ) n ( v ) + 刀( r ) 一胛( p ) = 2 ( 2 4 ) 与目前常用的实体表示方法( 如，构造的实体几何表示( c s g ) 和边界 表示( b r e p ) 等) 相比，s t l 模型存在以下缺陷。 难以将实体的s t l 模型还原成c a d 模型。s t l 模型是针对快速原型 本身提出来的，为了处理的方便，它只包含了模型的表面信息，而建模过程 中的一些重要信息都被忽略掉了，因此s t l 模型的转换是一个很难可逆的过 程。 s t l 模型含有大量的冗余信息。由公式( 2 - 3 ) 和公式( 2 - 4 ) 可知， s t l 模型顶点数约为三角面片个数的一半，边数为三角形个数的1 5 倍，可 见在s t l 模型存在大量的冗余信息。 s t l 模型是对c a d 模型表示的平面与曲面的逼近，因而s t l 模型对 实体的表达精度较低z 。 组成s t l 模型的三角面片信息是散乱、无序的，难以直接从s t l 模 型获取实体的几何拓扑信息。 2 1 2三角形网格模型的相关概念 定义1 ( 拓扑重建) 将从散乱、无序存储的三角形中获取其拓扑信息的过程称为三角形网格 模型的拓扑重建。 定义2 ( 三角形网格边的角度) 设z 和z 为三角形网格模型r 的两共边的三角形， 角为z 和r 共有边e 的夹角，记作晓，其计算式如下： 见= a r c c o s ( n , ，) 式中m 和，分别为z 和z 的法矢。 定义3 ( 特征边) 则z 和i 法矢的二面 ( 2 - 5 ) 飞行器几何外形由多块光滑区域( 其切平面能精确数学定义) 及其交线 ( c 1 连续信息丢失) 组成，本文将r 上表示这些交线的边称为特征边，丁上 所有特征边组成的集合记作p 脚”，将组成特征边的网格顶点称为特征顶点。 西南科技大学硕士研究生学位论文第13 页 在特征边处飞行器的几何外形不满足c 连续，即特征边的角度相对较 大，故可通过边的角度是否大于设定角度阀值( 记作酽“) 提取丁的特征边， 沪一般取2 0 度。 定义4 ( 特征环) 由s t l 模型的性质可知，将p 倒”中的特征边首尾交线相连后，必然形 成的一条或多条空间封闭折线，将这种空间封闭折线称为特征环。将特征环 组成的集合记作肠印励”。 定义5 ( 壳域) 给定由网格模型丁中三角形组成的集合丁；，若r ：满足以下性质： 丁：具有连通性，即丁；上的任意两点都可用r ；表面上的一条路径连接 起来；丁；的表面不能自相交；丁：的三角形的法矢定义了丁：表示的几何 表面的内侧和外侧。r j 表示的几何表面是有界的。 则称丁；为壳域，记作r ”，将丁的壳域组成的集合称为s h e l l 7 。 定义6 ( 壳域边界) 设丁，丁为某壳域r ，的三角形，若f ，至少有一边在丁咖f ，丁中没有共享 三角形，则该边为壳域的边界边，丁，。为壳域的边界三角形；壳域的边界边 的顶点为壳域的边界点。 定义7 ( 壳域拾取) 壳域拾取是指从三角形网格模型中得到组成各个壳域的三角形集合的过 程。 定义8 ( 径向搜索) 将得到丁中共享某壳域边界点且不属于该壳域的三角形的过程称为壳域 的径向搜索。如图2 2 所示，互和瓦组成壳域执行一次径向搜索后，得到三 角形疋、瓦、五、弓、瓦、互。、互。、互：、五与正。 定义9 ( 几何重构) 将从物面网格模型中得到三角形单元所表达曲面计算模型的过程称为三 角形网格模型的几何重建。 西南科技大学硕士研究生学位论文第1 4 页 图2 - 2径向搜索示意图 f i g 2 - 2d i a g r a mo f r a d i a is e a r c h 2 2三角形物面网格的几何拓扑重建算法 在许多实际应用中，由于模型曲面很复杂，所以对复杂曲面网格的处理， 一般先要对其进行分割操作。例如在有限元计算应用中，在针对复杂模型进 行c f d 计算网格优化时，由于流场对模型整体作用区域不同，在强作用区域 要求对网格进行加密、稀疏等任意操作。因此需要将s t l 模型分割为若干子 壳域区域再进行局部设计。这种分割要求即具有智能性，又具有良好的人工 交付性。为此本章提出基于s t l 模型特征信息的径向搜索、壳域拾取等算法 达到三角形网格模型拓扑重建之要求。 2 2 1三角形网格模型的拓扑重建 2 2 1 1三角形网格模型的拓扑重建现状 目l i 成熟的方法是引入三角形的信息和顶点与边信息共同表示网格模 型，以恢复三角形间的拓扑信息。 ( 1 ) 顶点表用于存放三角形网格模型各个顶点的三个坐标分量，在装载 s t l 模型时，要把相同的顶点进行归并，一方面可以节省内存，另一方面可 以加快数据处理的速度，如在对s t l 模型进行平移、旋转和缩放等操作不再 需要对模型中所有三角形的顶点分别进行处理，而只要对顶点表中的数据进 行处理即可，从而使运算量大大减少。 ( 2 ) 三角形表用于存放三角形网格模型中所有三角形的信息，包含有其 三个顶点在顶点表中的位置索引及其法矢信息。 西南科技大学硕士研究生学位论文第1 5 页 ( 3 ) 边表用于存放三角形网格模型的所有边的信息。边的信息包含有该 边的两个端点在顶点表中的位置索引和共享该边的2 个三角形在面片表中的 位置索引。 2 2 1 2 三角形网格模型拓扑重建的数据结构 如图2 3 所示n o r m a l 为三角形法矢；i s b o u n d a r y 表示是否为边界三角形； c o o r d i n a t e 为顶点坐标值；b p t m a r k 表示是否为边界点；l i n k m a r k 为索引共边 三角形的标志，u s e d t i m e 表示被访问的次数( 详见后续算法) 。 即引入三角形网格模型表、三角形表、边表和顶点表共同表示多个网格 模型的信息。通过每个三角形网格模型表索引到该模型的三角形表；每个三 角形表内不记录三角面片顶点的坐标值，提供3 个到3 个顶点在顶点表中的 索引；顶点表用于存放模型各个顶点的三个坐标分量。边表提供2 个指向共 享该边的三角形在三角形表中的索引，还提供2 个指向该边的2 端点在顶点 表中位置的索引。 优点是在己知某一模型的某一三角形的情况下，能够直接索引到该三角 形的3 条边和3 个顶点，再通过这3 条边和3 个顶点索引到与其共边共点的 三角形，便于实现三角形的顶点、边和面片间几何拓扑信息的直接访问，并 减少点冗余数据。如图2 2 所示，互通过3 条边可以索引到乃、五和瓦，互通 过3 个顶点可以索引到疋、e 、正、五、瓦、乃、正和瓦。如此，就可以把 所有这些杂乱的三角形有机地结合在一起，为三角形网格的自适应操作奠定 基础。 西南科技大学硕士研究生学位论文第1 6 页 图2 - 3数据结构示意图 f i g 2 - 3d i a g r a mo fd a t as t r u c t u r e 2 2 2三角形网格模型的径向搜索 2 2 2 1 问题的提出 在处理三角形网格的操作中，常常需要从一个三角形z 出发，检索到另 一三角形丁，的连通路径，其步骤为：首先，从z 开始执行径向搜索直到遇到l ， 得到壳域t s h e l i , t r ；然后从丁，开始执行径向搜索直到遇到z ，得到r 删l 2 j ；丁删 巧 与t 删l 巧的交集即为所求的连通路径。 因此，径向搜索是处理三角形网格的基本操作之一。 2 2 2 2 径向搜索方法 设z 妇盯( z 曲训可由一个三角形组成) 为网格模型丁的某一壳域，z 咖的 径向搜索方法如下： 得到z 曲洲的边界点集合1 ，6 0 删咧，若z 咖仅由一个三角形组成，该三角 形3 顶点组成v b o u n d a r y ； 得到共享v b o u n d a r y 中边界点的三角形集合丁蚴8 ，将丁砌8 中z 删没有 的元素加入z 咖； 更新v b o u n d a r y ，得到z 咖新的边界点集合，幻俐叫。 西南科技大学硕士研究生学位论文第17 页 2