毕业设计（论文）-骨科三维有限元生物力学分析中网格生成的研究与实现.doc

摘要 骨科三维有限元生物力学分析中网格生成的研究与实现 全套图纸加扣 3012250582 随着信息技术在医学领域逐渐深入和广泛的应用，骨科三维有限元生物力学 分析已成为骨科医学研究中的一种不可或缺的科研方法。通过网格生成将处理对 象离散化是运用有限元法求解生物力学问题的一个必要的前期处理环节，而网格 生成的效率和质量会直接影响到求解问题所用的时间和分析结果的精确度。所以， 研究网格生成方法，对于提高骨科三维有限元生物力学分析的效率和精确度，都 具有重要的现实意义。 本文提出了一种全新的、高效的、自适应的可用于骨科三维有限元生物力学 分析的网格生成方法，并详细阐述了其实现过程。在传统的骨科三维有限元生物 力学分析中，通常利用 MIMICS 等软件将整个骨骼模型剖分，然后再手动划分骨 质的厚度（即在模型中区分出骨质和骨髓，为二者赋予不同的物理特性） ，操作 繁琐费时。在本文所述方法中，利用基于顶点的三维模型缩放算法，将 STL 文件 描述的原始骨骼 3D 模型进行小距离缩放，形成一个双层嵌套结构；然后利用开 源软件 TetGen 对上述结构进行四面体剖分，得到一个双层网格模型；最后，自 主设计程序，将内层网格删除，生成一个有一定厚度的、可用于有限元分析的三 维网格模型。本文所述的网格生成方法，具有算法简单、实现高效、满足自适应 性等优势，同时也存在可能导致面片自交等不足。 本文的整体组织安排如下： 第一章介绍了本课题的研究意义、有限元分析方法及有限元网格生成的国内 外研究状况。 第二章介绍了 STL 文件的格式及本课题在实现过程中用到的第三方工具。 第三章给出了本课题的整体设计，重点介绍了基于顶点偏移的模型缩放算法。 第四章详细介绍了本课题的具体实现。 第五章讨论了本课题实现的时空复杂度以及优缺点。 关键字：有限元分析，网格生成，模型缩放 Abstract The Research and Implementation of Mesh Generation in Three - dimensional Finite Element Biomechanics Analysis of Orthopedics As information technology gradually in-depth and extensive application in the medical field, the three-dimensional finite element biomechanical analysis of orthopaedic has become an indispensable research method in orthopedic medicine research.The discretization of the object to be processed by mesh generation is a necessary pre-processing process to solve the biomechanical problem by using the finite element method. The efficiency and quality of the mesh generation will directly affect the time of solving the problem and the correctness of the solution. Therefore, the study of mesh generation method is of great significance for improving the efficiency and accuracy of three-dimensional finite element biomechanical analysis of orthopedics. This paper presents a new, efficient and adaptive method of mesh generation that can be used in three-dimensional finite element biomechanical analysis of orthopaedic, and elaborates its implementation process in detail. In the traditional three-dimensional finite element biomechanical analysis of orthopedics, the entire skeletal model was usually divided by software such as MIMICS, and then the thickness of the sclerotin was manually divided(ie, distinguish the sclerotin and bone marrow in the model, and endow the different physical properties for both),and the operation was cumbersome and time-consuming. In the method described in this article, using the model scaling algorithm based on vertex, we scale the original skeleton 3D model described by the STL file by a small distance,forming a double nested model;Then, the structure is quadrilateral segmented by open source software TetGen , we get a two-layer grid model.Finally,we remove the inner layer mesh by the program designed oueselves to generate a three-dimensional mesh model that has a certain thickness and can be sued in three-dimensional finite element analysis.The mesh generation method described in this paper has the advantages of simple algorithm, high efficiency and high adaptability, however there are some problems such as may lead to self-intersection. The organization of this paper is as follows: The first chapter introduces the research significance of this subject, the finite element analysis method and the domestic and foreign research status of finite element mesh generation. Chapter 2 introduces the format of the STL file and the third-party tools used in the implementation of this project. In the third chapter, the allover design of the subject is given, and the model scaling algorithm based on vertex offset is introduced emphatically. The fourth chapter details the concrete realization of this subject. Chapter 5 discusses the time complexity, spatial complexity and advantages and disadvantages of this subject. Keywords：finite element analysis,grid generation, model zoom 吉林大学 计算机科学与技术学院 毕业论文 5 目目 录录 第 1 章 绪论 .7 1.1 课题的提出及研究意义 .7 1.2 有限元分析简介 .8 1.3 国内外研究状况 .8 1.3.1 国外状况.8 1.3.2 国内状况.10 1.3.3 总结与展望.11 第 2 章 STL 文件及课题所用工具介绍.12 2.1 STL 文件 .12 2.1.1 ASCII 格式 .12 2.1.2 二进制格式.13 2.1.3 顶点排布顺序与法向量方向.14 2.1.4 STL 文件的面片颜色 .15 2.1.5 STL 文件的其它特性 .16 2.2 OPENGL .16 2.3 TETGEN.17 2.4 TETVIEW.17 第 3 章 整体设计 .18 3.1 基本步骤 .18 3.2 基于顶点偏移的模型缩放方法 .19 3.2.1 命名与约定.19 3.2.2 研究现状.20 3.2.3 简单的法向量算术平均存在的问题.22 3.2.4 卫星面片法向量的加权和方法.23 3.2.5 偏移向量的具体解法.25 3.2.6 特殊情况处理.27 吉林大学 计算机科学与技术学院 毕业论文 6 第 4 章 编程实现 .30 4.1 模型缩放 .30 4.1.1 主要数据结构.30 4.1.2 算法流程.32 4.1.3 关键步骤和重要子算法.34 4.1.4 成果展示.42 4.2 模型剖分 .43 4.2.1 基本过程.43 4.2.2 成果展示.44 4.3 模型挖空 .44 4.3.1 基本过程.44 4.3.2 成果展示.47 第 5 章 分析与评价 .48 5.1 时空复杂度.48 5.1.1 时间复杂度.48 5.1.2 空间复杂度.49 5.2 优缺点分析.50 参考文献 .52 致 谢 .55 吉林大学 计算机科学与技术学院 毕业论文 7 第第 1 1 章章 绪论绪论 1.1.1 1 课题的提出及研究意义课题的提出及研究意义 随着骨科医学和信息技术的不断交叉融合，有限元分析在骨科医学中的应用 越来越深入和广泛。但与此同时，在国内，骨科三维有限元生物力学分析方面存 在以下两个明显不足： 1.所用的建模和分析软件绝大部分为国外软件且为付费软件，比如 SYNGO、MIMICS、MSCNASTRAN、ANSYS、ABAQUS、MARC、ALGOR 等； 2.建模与分析相分离。现阶段，在我国进行骨科三维有限元生物力学分析的 一般步骤是：先将 CT 分层扫描数据等用于建模的原始数据导入 SYNGO、MIMICS 等建模软件进行 3D 建模和网格生成，然后将建立好的模型导 入 ANSYS、ABAOUS 等有限元分析软件进行分析求解1。这其中，有时需要手 工进行骨质划分（特别是由于骨质疏松或其它原因导致 CT 灰度值不可用时） ，整 个操作过程复杂、耗时，容易出错。 以上两点不足，直接增加了软件的使用难度和骨科医学中科学研究的成本。 另一方面，三维有限元建模和分析软件在我国拥有的市场空间巨大，许许多 多的大中型骨科医院、医疗科研机构都对相关软件具有强烈、长期的需求。可以 说，自主开发一款高效实用的、建模分析一体化的骨科有限元分析软件，对于提 高我国现阶段软件开发能力、骨科医疗水平，都具有重大的科研价值和重要的现 实意义。 网格生成作为有限元分析前期处理过程中的重要环节，直接决定着建模的效 率和后期分析的准确度，是有限元分析能否高效、准确实施的关键因素。本课题 以网格生成为切入点，探索与生成了一种全新的适用于骨科三维有限元生物力学 分析的网格模型，为开发出一套功能完备、便于操作、适用于骨科生物力学研究 的有限元建模和分析软件进行了有益的探索，提供了一定的理论基础、实践经验 和技术支持。 吉林大学 计算机科学与技术学院 毕业论文 8 1.21.2 有限元分析简介有限元分析简介 有限元分析(finite element analysis, FEA)是一种准确高效、应用广泛数值计 算方法，它的指导思想是离散化、转化思想和近似替代。从数学的角度看，是将 难以求解的微分方程转化为便于求解（特别是便于计算机求解）的代数方程组并 求得近似结果的计算方法。从几何的角度来看，就是将现实中连续、质密的物理 实体划分成有限个小单元（即有限元） “堆砌”成的几何体，在二维空间下，这 些小单元通常是三角形或四边形，在三维空间下，这些小单元通常是四面体或六 面体。这些单元之间的相互连接及力的传递仅仅通过有限的几个连接点来完成。 只要将真实物体的物理特性赋予这些单元，同时设定好边界条件及荷载的大小和 方向，通过矩阵运算，就能够模拟出真实物体在任意一点处的应力分布。现在， 有限元分析方法已经广泛应用于机械制造、航空航天、生物力学等领域。1972 年， Brekelmans，Poort 和 Slooff2等人首次将有限元分析方法引入骨科领域，当时的 网格生成采用的还是纯手工划分的方法。 1.31.3 国内外研究状况国内外研究状况 1.3.11.3.1 国外状况国外状况 国外关于有限元网格生成的研究开始于上世纪 70 年代。1971 年， Zienkiewicz ，Owen 和 Phillips3提出了最早的网格自动生成算法映射法。 1973 年， Buell 和 Bush4从节点生成和元素生成两个方面探讨了有限元网格生成 的方案，从此，该领域的研究在西方开始蓬勃发展。1980 年，Thacker5提出了一 种新的网格生成方法基于栅格法，该方法取得的一个革命性成果是能够产生 非结构性的四边形网格，所以可以实现对复杂几何图形的网格剖分。虽然该方法 在边界适应性方面表现良好，但在生成边界网格上表现欠佳。1981 年，R.Haber 提出了基于离散形式的超限映射网格划分方法，这是对传统映射法的一种改进， 使得生成网格的质量有了很大程度的提高。1983 年，yerry 和 Shephard6等对栅格 法进行了进一步改进，提出了有限四/八叉树法，用来进行四面体网格生成。同 年，Bykat7提出了一种将一个复杂的几何区域划分成几个简单的子区域的自动化 算法，为实现复杂区域上的网格自动生成提供了可能。 吉林大学 计算机科学与技术学院 毕业论文 9 伴随着实际问题中计算需求的不断提高和计算机几何理论及数值模拟技术的 发展，从上世纪 80 中后期开始，在现实需求的驱动下，网格剖分的研究领域逐 渐由二维空间向三维空间转移。1984 年，Wrdenweber8给出了拓扑分解法，顾 名思义，就是将一个结构复杂的空间几何体根据其拓扑结构分解为若干个结构简 单的子几何体，然后对每个子几何体分别进行剖分的方法，基于该方法，提出了 一种六面体网格剖分算法。1984 年，Yerry 和 Shephard9将他们在 1983 年提出的 四/八叉树法推广到三维空间，提供了一种新的将三维模型进行四面体或六面体 自动剖分的方法。1985 年，Cavendish 提出了在四面体网格自动生成领域非常著 名的 Delaunay 三角剖分算法，该方法至今仍被广泛使用。1988 年，Ho-Le 10总 结了之前的各种有限元网格生成方法，使得有限元网格自动生成技术在西方的发 展更加体系化。 从上世纪 90 年代开始，各种网格生成算法呈现出突飞猛进的发展态势。随 着计算机存储、计算性能的大幅度提升，这一时期的专家学者将研究的目光聚集 在四边形和六面体网格的自动生成上。1991 年，Zhu 和 Zienkiewicz11提出了波 前推进法(Advancing Front Method,简称 AFM)，该方法一经提出，就得到了广泛 的应用。同年，Lo 在波前推进法的基础上进行了改进，他采用网格的体积与边的 平方和的比率来判定四面体网格的质量，以保证生成的四面体尽可能均匀。通过 这种方式，生成的四面体网格的质量得到了大幅度提高。1999 年，Owen12再次 在推进波前法的基础上进行了卓有成效的创新，他先运用波前推进法对三维几何 体进行三角形剖分和四面体剖分，然后再将两个剖分结果合并，从而间接实现了 三维空间几何体的四边形和六面体网格自动生成。 最近十年，经过大批专家学者的不懈努力，基本上实现了三角形、四边形和 四面体这三种网格在复杂模型上的自动剖分。于是，人们很自然地将研究的焦点 转向了复杂三维空间几何体的六面体自动剖分。在复杂几何体的六面体网格自动 生成领域，专家学者所面临的技术瓶颈主要有：（1）如何保证不同尺寸的网格 之间的相互兼容；（2）对于边界区域，如何保证生成的网格具有优良的质量； （3）对于复杂区域，如何实现自动分解。面对这些问题，该领域的专家学者提 出了一些解决的思路和方法。1995-1997 年，Armstrong，Price，McKeag，Li13-15 等人提出了中轴面法，该方法充分应用了“化整为零，各个击破”的思想，先求 出待剖分几何体的中轴面，然后以该中轴面为参照，将三维模型分解为相对简单 的子区域，然后以子区域为基本单位进行六面体网格剖分，最后再将剖分好的子 吉林大学 计算机科学与技术学院 毕业论文 10 区域拼装成原来的三维空间几何体。该方法因在复杂三维模型六面体自动剖分方 面表现良好而被广泛应用。与中轴面法类似，1999 年， Sheffer，Etzion,，Rappoport16等提出了内嵌 Voronoi 图方法，该方法先通过 Voronoi 图将原始三维几何模型分解成多个互斥的子模型，通过扫描法等传统方 法对子模型进行六面体网格自动剖分，最后将完成剖分的子模型逆向拼装，从而 实现整个三维几何体的自动网格生成。2000 年，Li 和 Cheng17等对传统映射法进 行改进，提出了一种模式模块方法，可以生成六面体分级网格，在一定长度上改 善了映射法的生成效果。与“先做前期处理，在进行网格剖分”的做法相对应， 另外一些学者采用直接划分的办法对复杂几何体进行剖分。1999 年， Liu，Uicker，Gadh18等人提出了双几何拓扑约束方法，即将扫描法和映射法加 以改造和结合，无需前期处理，直接生成六面体网格。 有限元网格自动生成技术在西方国家医学领域中的应用，最早可追溯到上世 纪 90 年代。1995 年，Bendjaballah，Shirazi-Adl 和 Zukor19等人将网格生成和有 限元分析应用于对人类膝关节的生物力学研究。1998 年，Viceconti，Bellingeri 和 Cristofolini20等人评估比较了五种用于网格化人体股骨的网格自动生成技术。文 章指出，每种情况都值得认真研究，并且在特定情况下都可能是最佳方法。 1.3.21.3.2 国内状况国内状况 国内关于有限元网格生成的研究起步较晚，开始于上世纪 80 年代。1981 年， 岑章志,郁吉仁,王勗成21等将网格生成应用于大型三通结构的三维有限元分析。 1989 年，杨名生,王冬22等介绍了可全自动剖分任意形状空间几何体的有限元网 格生成法。2009 年，杨晓东，申长雨，李倩23等人提出了一种结构自适应有限 元分析中的高质量网格生成方案。 而直到 21 世纪，国内才有将有限元分析技术应用于骨科生物力学研究的报 道。2004 年，黄启今, 刘国权, 马远征24等提出了基于 CT 图像重建腰椎活动 节段三维有限元模型的方法。2007 年，傅栋, 靳安民25等探讨了应用 CT 断层图 像快速构建人体骨骼有限元几何模型的方法。2010 年刘清华26讨论了对人体足 踝进行三维有限元建模和分析的方法。 另外，对于骨科三维有限元模型的建立，国内都是直接利用 ANSYS 等相关 软件进行建模，相关专家学者将更多的目光聚集在如何通过改进操作流程和实验 吉林大学 计算机科学与技术学院 毕业论文 11 方法来利用现有工具建立更加精确的分析模型和得到更精确可靠的分析结果，而 很少有人从学术和研究角度关注和探索通过改进模型的网格剖分方法本身来获得 更加满意的实验效果。截至目前，国内主流科学刊物和新闻媒体上，未见关于骨 科三维有限元生物力学分析中网格生成方法的学术探讨和相关报道。 1.3.31.3.3 总结与展望总结与展望 随着信息技术和计算科学的发展，近年来，国内外的有限元网格生成研究不 断扩展和深入，进入快速、多元化发展阶段27。从研究领域来看,从二维空间转 换变到三维曲面和三维实体。从网格生成方式来看，由原来的四面体网格自动生 成转变为六面体网格自动生成。从研究方法来看，从单一网格生成方法转向多种 传统方法的改进与融合。同时，近年来，由传统网格生成衍生出的许多分支领域， 如结构化网格生成、自适应网格生成、各向异性网格生成、贴体坐标网格生成等， 也都取得了长足的发展。 从国内外对比情况来看，国内关于有限元网格生成方面的研究起步较晚，技 术水平也同国外存在一定差距，特别是在骨科医学领域，未见与骨科三维有限元 生物力学分析中网格生成方法直接相关的研究和报道。 吉林大学 计算机科学与技术学院 毕业论文 12 第第 2 2 章章 STLSTL 文件及课题所用工具介绍文件及课题所用工具介绍 2.12.1 STLSTL 文件文件 STL(STereoLithography, 立体光刻)是一种文件格式，由 3D Systems 公司发明， 最初用于立体光刻计算机辅助设计软件。目前，STL 有多种的英文翻译，如“标 准曲面细分语言(Standard Tessellation Language)” 、 “立体光刻语言 (STereolithography Language)” 、 “标准三角语言(Standard Triangle Language)”等。 STL 文件被广泛应用于计算机辅助设计、快速成型和 3D 打印等领域。简单来说， STL 文件是用来描述三维立体模型的。STL 文件描述的立体模型，是由一个个小 的三角形面片拼凑成的封闭曲面，STL 文件主要就是用来描述这些面片在三维直 角坐标系下的位置信息的。显然，将每个面片的空间位置描述清楚了，也就刻画 出了三维立体模型的形状。STL 文件有 ASCII 码和二进制两种格式，下面分别对 这两种格式加以详细说明。 2.1.12.1.1 ASCIIASCII 格式格式 ASCII 格式即常见的文本格式，数据以 ASCII 码的形式保存，这种形式的文 件可以用记事本等文本编辑软件直接打开查看。STL 文件有固定的开头和结尾， 格式分别如下： 1.开头 solid 文件名 例如：solid a cat 其中 solid 是固定字符串，所有 ASCII 文件都必须以该字符串开头。 2.结尾 endsolid 文件名 其中，endsolid 也是固定字符串，而文件名可以和文件开头中 solid 后的文件 名不同。 吉林大学 计算机科学与技术学院 毕业论文 13 在开头和结尾中间，是对构成三维模型的各个三角形面片在三维坐标系下的 位置信息的描述，每个三角形面片都由固定的 7 行来描述，形式如下 facet normal ni nj nk outer loop vertex v1x v1y v1z vertex v2x v2y v2z vertex v3x v3y v3z endloop endfacet 其中，第一行的前两个单词、第二行、第六行和第七行都是固定字符串。第 一行中，ni ,nj, nk描述了三角形面片的法向量信息，第三、四、五行描述了三角形 面片三个顶点的位置信息。还有一点需要说明的是，n 和 v 都是用科学计数法表 示的小数，且书写规则如下： 1.若底数是正数，前面的+要省略； 2.底数的小数点后统一保留六个数字； 3.指数部分至少两位数字，即使是 0 也要写成 00 的形式，并且，指数前必须 标出正负号； 4.底数和指数之间由小写英文字母 e 连接。 例如：-2.168000e-01，127.361892e+00，都是合法的格式。 还有一点需要特别指出，许多文献中提到，三角形面片的顶点数据必须是正 数，但实践证明，负数也是被允许的。 ASCII 格式的好处是可读性强，缺点是文件体积过大，而一般情况下，一个 STL 模型包含成千上万乃至十万百万个三角形面片，这使得 ASCII 形式的 STL 文 件往往需要占用较大的存储空间，在这种情形下，二进制形式的 STL 文件应运而 生。 2.1.22.1.2 二进制格式二进制格式 二进制格式的 STL 文件将三角形面片的位置和法向量信息以二进制形式存储， 所以占用空间小，也因此被更加广泛地应用。 如果通过内容来划分二进制 STL 文件的字节的话，一个二进制的 STL 文件 吉林大学 计算机科学与技术学院 毕业论文 14 的总字节数可以表示为 总字节数=80+4+50N，其中，N 是三角形面片的总数。 二进制 STL 文件最开头的 80 个字节是标头(Header)，用于记录文件的来源 （如一个网站的网址信息）等附加信息，由于这些信息通常和文件描述的三维模 型没有直接关系，因此往往被忽略。但有一点需要注意，为了与 ASCII 格式相区 分，标准的二进制格式文件不会以“solid”开头。接下来 4 个字节以无符号整数 的形式记录了该文件包含的三角形面片总数。接下来的字节全部用来描述三角形 面片的位置和法向量信息，每个面片固定用 50 个字节。如果从前到后将这 50 个 字节编号 0-49 的话，50 个字节的信息分配如下： 0-11：法向量在三个方向上的坐标值，其中， 0-3x 轴方向的坐标值； 4-7y 轴方向的坐标值； 8-11z 轴方向的坐标值； 12-23：面片的第一个顶点的坐标，其中， 12-15顶点的 x 轴坐标值； 16-19顶点的 y 轴坐标值； 20-23顶点的 z 轴坐标值； 第 24-35 字节，第 36-47 字节分别面片的第二、第三个顶点的坐标信息，格 式与第一个顶点相同。 48-49：描述面片的附加属性（如颜色）信息，在标准文件中被置为 0。 2.1.32.1.3 顶点排布顺序与法向量方向顶点排布顺序与法向量方向 STL 文件的顶点排布顺序和法向量的方向满足右手定则，即按照 STL 文件的 描述顺序，依次设三个顶点为 P1，P2，P3，法向量为 n，于是，令 a=P2-P1(2-1) b=P3-P1 (2-2) 则法向量 n=ab(2-3) 吉林大学 计算机科学与技术学院 毕业论文 15 若从坐标运算的角度考虑，设 (2-4) 1 =(1,1,1) 2 =(2,2,2) 3 = (3,3,3) 则 (2-5) = (2 1) (3 1) 转化成三阶行列式，即 =| 2 12 12 1 3 13 13 1| =( (2 1)(3 1) (2 1)(3 1) (2 1)(3 1) (2 1)(3 1) (2 1)(3 1) (2 1)(3 1) (2-6) 从几何关系的角度来看，如图，伸出右手，四指由向量 a 转向向量 b，则大 拇指所指的方向即为法向量的方向。 图 2-1 右手规则示意图 2.1.42.1.4 STLSTL 文件的面片颜色文件的面片颜色 ASCII 格式的 STL 文件不携带面片的颜色信息，而在二进制形式的 STL 文件 中，可以加上面片的颜色信息，但对于信息的添加位置及解读方式，没有形成统 一的标准，而是由各种支持 STL 文件格式的商用软件自行定义。目前，有两种较 为常用的表示颜色信息的方式。 1.用属性字节表示 VisCAM 和 SolidView 软件用描述每个三角形面片的 50 个字节中的最后两个 存放 15bit 的 RGB 色码，用以标记该面片的颜色，具体规则如下 0-4bit：蓝色强度 5-9bit：绿色强度 10-14bit：红色强度 15bit：颜色信息是否有效，1 表示有效，0 表示无效。 吉林大学 计算机科学与技术学院 毕业论文 16 2.在标头中加入颜色信息 Materialise Magics 软件在 80 字节的标头中加入颜色信息。在该软件输出的 STL 文件中，如果要使用颜色信息，会在标头某处加入“COLOR=”这样的固定 字符串，其后跟 4 字节的颜色信息，其中前三字节表示 RGB 色码，最后一个字 节用来标识透明度（取值 0-255） 。另外，每个三角形面片的颜色还允许另行指定， 方法和规则同 1。 2.1.52.1.5 STLSTL 文件的其它特性文件的其它特性 除了上面提到的右手规则特性之外，标准 STL 文件还有如下特性： 1.无单位：STL 文件的顶点坐标不带单位，即 STL 文件的计量单位是任意的。 2.无序性：STL 文件对三角形面片的描述是无序排列的，即它并不反应三角 形面片之间的拓扑关系。 3.封闭性：STL 所描述的三维模型一定是封闭实体。 4.共顶点：任意两个邻接的三角形面片必须有且只有两个公共顶点，绝不会 出现一个三角形的顶点落在与它邻接的三角形的边上的情况。 5.单位法向量：在标准 STL 文件中，三角形面片的法向量必须是单位向量， 即向量的模为 1。 6.外法向量：三角形面片的法向量永远指向模型的外部。 7.充满规则：STL 文件中的三角形面片不交叉，不重叠，但同时也不存在空 隙，即相互邻接地铺满模型的表面。 8.欧拉公式：STL 文件描述的模型的顶点数 V、边数 E、面片数 F 必须满足 欧拉公式，即：V-E+F=2。 STL 文件的这些特性非常重要，本课题的实现正是在充分利用这些特性的基 础上完成的。 2.22.2 OPenGLOPenGL OpenGL（Open Graphics Library，开放式图形库）是一个开源的、跨编程语 言和平台的图形编程接口，广泛应用于计算机辅助设计、游戏开发、科学可视化 吉林大学 计算机科学与技术学院 毕业论文 17 程序和虚拟现实等领域。OPenGL 最初由 SGI 公司开发，现在由包括 Apple、Dell、 、Intel、IBM 等在内的多家公司共同维护。OPenGL 提供了丰富的 图形编程接口，通过这些 API，可以轻松实现三维图像的显示、渲染、平移、旋 转、缩放等功能。本课题研究的中间结果，就是通过 VC+结合 OPenGL 开发的 MFC 应用程序来显示的。 2.32.3 TetGenTetGen TetGen 是由现就职于德国计算数学与科学计算维尔斯特拉斯应用分析和随机指 数研究所(WIAS)的华人斯杭(Hang Si)编写的开源、跨平台软件。该软件可以实现 对任意三维实体的四面体网格剖分，所产生的四面体满足 Delaunay 三角剖分准则 和 Voronoi 划分。TetGen 支持.stl、.mesh、.off 和.ply 等多种文件格式，同时， TetGen 提供了丰富的命令来实现网格细化、重建、自适应等功能，同时尽可能满 足用户的需求。另外，TetGen 还具有检验面片自交等辅助功能。本课题中，对模 型的具体剖分，就是通过 TetGen 实现的。遗憾的是，目前 TetGen 只支持 ASCII 码形式的 STL 文件，所以，在本课题的实验中，需要将输出 STL 文件写成 ASCII 码的形式。 2.42.4 TetViewTetView TetView 是由斯杭用 C+语言，结合 OPenGL 库开发的与 TetView 配套使用 的软件，支持多种文件格式，主要用来显示和查看 TetGen 的剖分结果。TetView 提供了图像的显示、平移、旋转、缩放等基本功能，还能够对图形进行切片，用 以查看模型内部的剖分情形。 吉林大学 计算机科学与技术学院 毕业论文 18 第第 3 3 章章 整体设计整体设计 3.13.1 基本步骤基本步骤 STL 模型本身不具有厚度，无法直接进行有限元分析，而如果直接将整个模 型剖分，就又走回需要手动进行骨质划分的老路。本文提出了一种创新性的方法， 通过对原始 STL 骨骼模型进行缩放剖分挖空处理，直接生成具有一定厚 度、中空、可直接用于骨科三维有限元生物力学分析的网格模型。本文所采用的 网格生成方法大体上可以分为以下三步： 1.模型缩放 有一点需要解释清楚，这里的缩放指的是在三维物理空间中将模型放大或缩 小，与视图级别的图像缩放有着本质不同。 传统的图像缩放就是将图像等比地放大或缩小，图像上的所有点行动一致， 都是向四周发散（放大时）或向中心集中（缩小时） 。而三维模型的缩放是利用 表面偏移(surface offset)技术，将构成模型的所有三角形面片向外或向内（即与法 向量同向或反向）偏移一定距离，最终达到将模型在三维物理空间中放大或缩小 的目的。如果与原模型一起考虑，就是形成一个具有包含结构的双层模型。下面 两幅图通过对一个三维轮胎放大的俯视视角观察，清晰地展示出视图级别上的缩 放和三维立体空间中缩放的区别。 图 3-1 视图级别上的缩放 图 3-2 三维空间中的缩放 吉林大学 计算机科学与技术学院 毕业论文 19 上图中，实线是放大前的模型，虚线是放大后的模型。图 1 是视图级别上的放大 （俯视图） ，图 2 是三维物理空间中的放大。 本课题基于 STL 文件，采用基于顶点偏移和法向量加权和的三维模型缩放算 法，通过移动顶点的方式来达到将 STL 文件描述的三维立体模型外扩或内缩一段 较小的距离的目的，这样做将产生一个双层嵌套的、中间有一小段厚度的中空三 维模型，为后面的网格剖分工作做好准备。这是本文所述方法中最为关键的一步， 也是本文论述的重点和本课题的主要成果。 2.模型剖分 该步骤在上一步产生的双层 STL 模型的基础上，利用开源软件 TetGen 对模型进 行四面体网格剖分。通过使用-Y 参数，可以保证模型的双层表面不被破坏，对模 型的两层分别进行剖分，通过使用-A 参数，可以在剖分的输出文件中通过一个标 识字段对两层网格加以区分，为下一步的挖空操作提供了辨别依据。 3.模型挖空 该步骤中，通过自主设计程序，读取上一步网格剖分的输出文件，通过对标识字 段的判断，过滤掉内层网格，将外层网格信息写入新的文件，该新文件就是本课 题研究的最终成果一个具有一定厚度，可直接用于有限元生物力学分析的三 维网格模型。 3.23.2 基于顶点偏移的模型缩放方法基于顶点偏移的模型缩放方法 3.2.13.2.1 命名与约定命名与约定 为更加清晰和方便地介绍该算法，这里事先进行下列命名与约定。 对模型 M，命名它的顶点结合为 V，边集合为 E，面集合为 F。按照 STL 文 件的描述顺序，将一个三角形面片的三个顶点顺次命名为 P1、P2、P3。这里，提 出三个新的概念中心顶点、卫星面片和卫星顶点。对于任意顶点 v，定义该 顶点的卫星面片集合和卫星顶点集合如下： St_F(v)=f|fF,v 是 f 的顶点 St_V(v)=v|v是 St_F(v)中某面片的顶点，且 vv 吉林大学 计算机科学与技术学院 毕业论文 20 相应地，将顶点 v 称为中心顶点。 直观地来看，下图中，对于中心顶点 P 而言，周围所有的顶点都是 P 的卫星 顶点，而图中所有的面片都是 P 的卫星面片。 图 3-3 中心顶点、卫星面片、卫星顶点示意图 如上图所示，在 STL 文件正确的前提下，对于任意中心顶点，它的卫星面片 都具备以下三个特征： 1.卫星面片数 n 都满足，这是显然的。 3 2.将所有卫星面片中中心顶点所在的内角加起来，和恰好为 360，即卫星 面片以中心顶点为中心，恰好围成一个圆周。 3.若某中心顶点共有 n 个卫星面片，则它一定有 n 个不同的卫星顶点，每个 卫星顶点在卫星面片中出现且仅出现两次，即每个卫星顶点都恰好被两个邻接的 卫星面片所共享。 上述三个特征，是本文所述算法的重要设计依据。 3.2.23.2.2 研究现状研究现状 关于三维模型的表面偏移，目前国内未见相关报道。在国外，一些专家学者 提出了几种不同的缩放方法。2004 年，Kim，Lee 和 Yang28等人提出一种利用卫 星面片的法向量来进行模型缩放的方法，该方法与本课题所述的方法有相似之处， 但最大的不同在于，Kim 等人是将一个顶点沿卫星面片的法向量向多个方向移动， 即由一个顶点产生多个顶点，而本课题中，只是将顶点沿一个方向移动，不会有 额外的顶点产生。 2005 年，Chen，Wang 和 Rosen29等人提出一种基于点(point 吉林大学 计算机科学与技术学院 毕业论文 21