（航空宇航制造工程专业论文）面向口腔正畸的仿真技术研究与应用.pdf

r e s e a r c ho no r t h o d o n t i cs i m u l a t i o n t e c h n o l o g y a n dt h e i ra p p l i c a t i o n s a t h e s i si n a e r o n a u t i c a la n da s t r o n a u t i c a ls c i e n c ea n dt e c h n o l o g y b y p e n gy a n i n g a d v i s e d b y p r o f c h e n gx i a o s h e n g s u b m i t t e di 1 1p a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g j a n u a r y , 2 0 1 0 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下， 独立进行研究工作所取得的成果。尽我所知，除文中已经注明 引用的内容外，本学位论文的研究成果不包含任何他人享有著 作权的内容。对本论文所涉及的研究工作做出贡献的其他个人 和集体，均己在文中以明确方式标明。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 毒 南京航空航天大学硕士学位论文 摘要 传统的牙齿矫治方法不仅有难清洁、影响美观等缺点，而且依赖医生的经验，难以预测矫 正的效果。口腔正畸仿真系统通过过程模拟与结果预测，可以有效地改善正畸治疗体验。本文 针对口腔正畸仿真系统在规划正畸方案的过程中的需求，围绕口腔正畸中的咬合分析和咬合仿 真问题的相关算法进行研究。主要研究内容和成果如下： 针对口腔正畸仿真中的快速边界搜索和一环邻域搜索问题，研究了基于半边结构的三角网 格拓扑重建算法。该算法在网格数据的点、边和面的查找搜索方面显示出较好的优势，为碰撞 检测和干涉分析的研究打下基础。 针对咬合问题中的碰撞检测问题，提出了一种基于包围盒的快速碰撞检测算法，该算法在 检测到碰撞后能够返回碰撞模型中相交三角片对的相关信息，并在此基础上求取出了碰撞模型 的交线，显示了干涉区域的边界和形态。 针对咬合分析中干涉位置及干涉深度问题，提出了一种高效、健壮的干涉分析方法。通过 快速划分模型数据，并根据碰撞检测快速判断模型的干涉区域，获取干涉区域内部的顶点信息， 利用k 临近搜索返同的距离信息确定干涉区域内部顶点的干涉深度。最后，结合p a t r i o t 系统与 y a m a h a c h i 咬合器提取的上下颌咬合运动轨迹信息，确定运动轨迹约束。 在上述研究基础上，实现了上下颌虚拟咬合运动仿真，并在口腔正畸仿真系统中成功应用， 取得了良好的效果，达到了预期目标。 关键词：咬合分析，口腔正畸，半边数据结构，碰撞检测，k d 树 c o l l i s i o nm o d e l so fr e l e v a n ti n f o r m a t i o n ，a n dc a l c u l a t ei n t e r s e c t i o nl i n e s ，a n ds h o wt h ee d g ea n dt h e s h a p eo ft h ea r e a a c c o r d i n gt ot h ep r o b l e mo fi n t e r f e r e n c ep o s i t i o na n di n t e r f e r e n c ed e p t hi no c c l u s a la n a l y s i s ， p r o p o s eae f f i c i e n ta n ds t r o n gi n t e r f e r e n c ea n a l y s i sm e t h o d t h r o u g hp a r tt h em o d e ld a t ai n t ot h eg i v e n c o n d i t i o n sa n dj u d g et h ei n t e r f e r e n c ea r e ai nm o d e lb yc o l l i s i o nd e t e c t i o ng e ti n f o r m a t i o na b o u t v e r t i c e si ni n t e r f e r e n c ea r e a a n dt h e n ，r e t u r ni n t e r f e r e n c ed e p t ho ft h ev e r t i c e si na r e ab yk n ns e a r c h f i n a l l y ，c o m b i n i n gw i t ht h ej a wo c c l u s a lt r a j e c t o r yi n f o r m a t i o ne x t r a c t e db yp a t r i o ts y s t e ma n d y a m a h a c h ic o r r e c ta r t i c u l a t o rd e t e r m i n et h et r a j e c t o r yc o n s t r a i n t b a s e do nt h ea b o v er e s e a r c h e s ，r e a l i z e dt h ej a wv i r t u a lo c c l u s a lm o t i o ns i m u l a t i o n ，a n di nt h e o r t h o d o n t i cs i m u l a t i o ns y s t e ms u c c e s s f u la p p l i c a t i o n ，a c h i e v e dg o o de f f e c ta n dt h ee x p e c t e dg o a l k e y w o r d s ：o c c l u s a la n a l y s i s ，o r t h o d o n t i c s ，h a l f - e d g ed a t as t r u c t e , c o l l i s i o nd e t e c t i o n ，k dt r e e 南京航空航天大学硕士学位论文 目录 第一章绪论l 1 1 引言一l 1 2 口腔正畸仿真研究背景一l 1 3 口腔正畸仿真技术的研究内容及发展现状3 1 4 论文主要工作及结构安排4 第二章输入模型数据拓扑重建6 2 1s t l 文件介绍6 2 2 基于半边结构的s t l 文件拓扑重建一7 2 2 1s t l 拓扑重建常用算法7 2 2 2 三角网格拓扑数据表示8 2 2 3 半边拓扑结构快速重建算法。1 0 2 2 4 性能分析。1 3 2 3 小结1 3 第三章碰撞检测技术1 4 3 1 经典层次包围盒1 4 3 1 1 包围球。1 4 3 i 2 沿坐标轴的包围盒。1 5 3 1 3 方向包围盒。1 5 3 1 4 固定方向凸包1 6 3 2 层次包围盒方法的性能分析1 6 3 3 算法预处理1 8 3 3 1 计算o b b 包围盒1 8 3 3 2 构建o b b 树1 8 3 3 3o b b 层次包围盒树的更新2 0 3 4 算法执行过程2 l 3 4 1 遍历层次二叉树。2 1 3 4 2 包围盒间的碰撞检测。2 2 3 5 基本几何元素的相交测试2 4 3 6 算法流程2 6 3 7 小结2 7 第四章干涉分析技术2 8 4 1 干涉区域检索2 8 4 1 1 模型网格数据预处理2 8 4 1 2 判定干涉区域3 l 4 2 基于k n n 搜索计算干涉深度3 3 4 2 1 计算k d 树包围盒3 4 4 2 2 构建k d 树3 5 4 2 2k n n 搜索3 7 i i i 面向口腔正畸的仿真技术研究与应用 i v 学位论文 图表清单 图1 1 固定矫治器。l 图1 2 无托槽隐形矫治器2 图1 3 牙颌模型测量与重构一3 图1 4 论文的研究路线一5 图2 1 翼边数据结构。8 图2 2 半边数据结构。9 图2 3 半边数据结构的层次1 0 图2 4 红黑树示例1 l 图3 1 包围球1 4 图3 2 a a b b 包围盒2 5 图3 3o b b 包围盒1 6 图3 4 固定方向凸包1 6 图3 5 不同包围盒相交测试复杂度比较1 7 图3 6o b b 包围盒的层次结构1 9 图3 7 层次二叉树的遍历2 2 图3 8 分离轴原理2 3 图3 9t i 和t 2 相交示意图2 5 图3 1 0 t 2 投影至百平面2 6 图3 1 1 算法流程图2 7 图4 1 上下颌牙齿咬合干涉2 9 图4 2 区域内一顶点的一环邻域示意图2 9 图4 3 一环临域搜索算法流程图3 0 图4 45 近邻示意图3 3 图4 5 协方差分析前后点集包围盒的比较。3 4 图4 6 空间分割法构建k d 树3 6 图4 7 手与雕塑干涉实验结果3 9 图4 8 手与龙干涉实验结果3 9 图4 9 龙与龙干涉实验结果3 9 图4 1 0 多个单颗牙齿干涉实验结果4 0 图4 1 1 程序执行时间折线图4 0 图5 1 虚拟咬合仿真流程4 2 图5 2 咬合平面4 3 v 一一 面向口腔正畸的仿真技术研究与应用 图5 3y a m a h a c h i 平均值咬合器i 型4 3 图5 4 测量实物的照片4 4 图5 5 坐标系转换4 4 图5 6 下颌中切牙示意图4 5 图5 7 咬合运动轨迹4 6 图5 8 下颌开闭口运动4 7 图5 9 下颌侧移运动4 7 图5 1 0 开闭口运动咬合分析结果4 7 图5 1 l 侧移运动咬合分析结果4 8 图5 1 2 正畸前上颌咬合分析结果4 8 图5 1 3 单颗牙齿平移操作4 9 图5 1 4 单颗牙齿旋转操作4 9 图5 1 5 正畸后上颌咬合分析结果5 0 表2 1 常见拓扑重建方法比较表1 3 表3 1 各类型包围盒大小j 1 7 表4 1 模型数据4 0 南京航空航天大学硕士学位论文 第一章绪论 1 1引言 口腔正畸学( o r t h o d o n t i c s ) 是口腔医学的一个分支学科，它的学科内容是研究错矛椭形 ( m a l o c c l u s i o n ) 的病因机制、诊断分析及其预防和治疗。错种奇形是指儿童在生长发育过程 中，由先天的遗传因素或后天的环境因素，如疾病、口腔不良习惯、替牙异常等导致的牙齿、 颌骨、颅面的畸形，如牙齿排列不齐、上下牙弓间的牙台关系异常、颌骨大小形态位置异常等等。 这些异常机制，是牙量与骨量、牙齿与颌骨、上下牙弓、上下颌骨、颌骨与颅面之间的不协调。 世界卫生组织( w o r l dh e a l t ho r g a n i z a t i o n ) 把错骀畸形定为“牙面异常”( h a n d i c a p p i n gd e n t o f a c i a l a n o m a l y ) 。“牙面异常”不但影响外貌，同时也影响功能【l l 。 1 2 口腔正畸仿真研究背景 近些年来，随着科学技术的不断进步，世界各国人民对医疗卫生都给予了更多的关注，同 时计算机辅助设计技术、图形图像处理技术、虚拟与现实技术和现代医学的飞速发展和交叉融 合、相互渗透使得医学组织的仿真设计和研究已成为计算机应用的一大热点。因此计算机技术 也越来越多地应用在现代医学领域，其中采用计算机图形学与数据可视化技术，利用图形图像 的处理和分析方法，选择合适的数学模型来处理三维数据并进行人体器官的几何建模，进而在 计算机中进行进一步的设计和模拟是研究最多的一种方式。在这种背景下面，针对口腔正畸的 计算机仿真技术也逐步地发展和壮大。 在传统牙齿正畸治疗中，治疗过程需要反复调整以达到正确矫正牙齿移动轨迹。这种治疗 方法治疗周期长，治疗费用较高，同时对病人也是一种折磨。1 7 2 8 年，法国医师f a u c h a r d 发明 了一种简单的固定矫治装置，即在一根平整金属条的适当位置打上小孔，然后将金属条弯成牙 弓形状，每颗牙齿都用穿过小孔的线来同定，从而对牙齿产生矫治力，达到矫治错牙黼形的目 的。固定矫治器是用黏合剂粘固于牙齿上，患者不能自行摘戴，只能由正畸医师用器械来拆装 调整的矫治装置。固定矫治器一般由托槽、带环、弓丝和其他辅助装置等组成，如图1 1 。 图1 i 固定矫治器 固 可前后 器除了 维蔬菜 容易导 齿等口 进度和 大，患 针 矫治技 图象处 有一定 动的力 图1 2 无托槽隐形矫治器 口腔正畸仿真系统是为无托槽隐形矫治技术提供计算机辅助诊断，输出模拟矫正数据的软 件系统。通过对患者牙列的三维光学扫描数据进行三维重构，咬合分析，进而模拟牙齿的矫正 过程来设计整个治疗计划，为患者量身定做设计不同时期所需的牙套，最后根据设计结果由快 速成型制造系统制造出透明的弹性塑料牙套，患者只需按牙科医生指示，不同时期佩戴不同的 牙套就可以达到预期矫正效果【3 1 。与传统的金属矫正相比“隐形”牙齿矫正具有以下优点： 由于牙套采刚的是透明弹性塑料，所以完全不会影响患者的形象：易于摘取，在治疗时患者 可以随时刷牙和使用牙线来保持口腔清洁：由于没有用到金属，它还不会刺激口腔；患者 还可以在治疗前就看到虚拟的治疗过程，预先了解矫正结果；可以预先控制矫正时间。在特 定的治疗阶段里，只有特定的牙齿被移动，从而使矫正效率大大提高。 口腔正畸仿真系统是一个特殊的虚拟现实( v i r t u a lr e a l i t y ) 系统，首先应满足v r 系统的 基本要求，即数据在三维场景中的交互与可视化。同时口腔正畸仿真系统又有其自身特殊的要 求，比如颅颌系统的牙台与咬合问题，使之既要达到一定的物理真实感又要满足实时性的要求就 需要在碰撞检测、干涉分析及上下颌咬合行为定义与约束等问题上进行研究。这些都是口腔正 2 1 3 口腔正畸仿真技术的研究内容及发展现状 口腔正畸仿真技术就是利用计算机对患者牙颌数字模型行进测量分析，完成输入牙齿数字 模型数据拓扑重建、碰撞检测、干涉分析以及咬合运动仿真等工作，通过人机交互完成错颌畸 形的诊断与矫治方案规划。 口腔正畸仿真系统采用的牙齿数字化模型，按模型曲面的不同表示形式可分为两大类：一 类是由众多三角形平面片组成的离散曲面模型；另一类是连续曲面模型。由于离散曲面模型能 够表达复杂拓扑结构，在计算机图形显示、计算机仿真等领域得到了广泛的应用，尤其在医学 三维造型和动画影视行业得到了产业化的发展。h o p p e 4 1 较为系统的研究了稀疏散乱点重构方 法，这种方法可以取得较为稳定、质量较好的拟合模型，但是因采用了全局优化策略，速度较 ，慢。张丽艳【5 1 对h o p p e 等人提出的三角网格模型重建算法进行了改进，进一步提高了算法的效 率，并能够更好地进行有界曲面及带尖锐棱边曲面的重建。 离散模型数据文件一般都不含有模型的拓扑信息，口腔正畸仿真系统在读入文件信息后需 要对文件数据进行拓扑重建，以便于仿真过程中的数据检索与处理。对于拓扑重建技术，国内 外很多学者都进行了广泛的研究，提出了不同的算法。h r d d e k 6 设计了一种新的h a s h 函数去处 理未知特性的数据集，保证能够尽可能提高h a s h 表中存储单元的利用率，使用尽可能简单的 h a s h 函数，同时还要有效的避免冲突的消解，这种方法可以获得较高的处理速度，但内存消耗 较多，参数选择复杂；赵歆波等7 1 人也研究了基于散列的拓扑信息重建算法，这种方法是一种 静态结构，不适合网格的动态修改：崔树标等i s 人提出了三轴分块排序的几何搜索算法；张必 强等【9 1 人提出的顶点归并和边的建立算法，采用点、边、面的数据结构。 ( a )( b ) 图1 3 牙颌模型测量与重构 ( a ) 测量得到的三维点与数据( b ) 重构得到的网格模型 口腔正畸仿真技术中有关碰撞检测、干涉分析以及咬合运动仿真方面的问题，在口腔正畸 医学中被归结为黔与咬合问题分析技术。a t h a n a s i o n 等使用光颌法h o t o c c l u s i o nt e c h n i q u e ) 3 面向口腔正畸的仿真技术研究与应用 去研究咬合接触，将具有光弹性的透明高分子材料制成厚约0 0 2 5 1 m m 的光颌片，在咬合力的 作用下，受力区产生塑性变形，在光颌仪上观察咬合接触的大小、形态、数量、分布；m a n e s s 等【l l 】采用t - s c a n 系统分析咬合接触，该系统由传感器、电缆、计算机等组成，在稍力作用下传 感器基片发生变形，通过分析传感器返回信号的变化，检测咬合接触的分布、咬合力等信息的 三维动态变化。第四军医大学王慧芸等人自主开发了咬合接触计算机图像分析系统【1 2 1 ，采用硅 胶材料记录被测者的牙啥接触情况，通过采集光源照射硅胶后的透视图像信息，分析图像灰度值 和标定牙台间隙，定量的测量咬合接触点的分布和咬合接触距离；王海涛等【1 3 l 利用反射式光纤位 移传感器开发了咬合监测装置。 随着计算机图形学和计算机硬件的飞速发展，虚拟现实技术和口腔医学的结合，推动了牙台 与咬合问题分析相关技术的发展。国外在9 0 年代后期开始了虚拟咬合技术的研究，德国的k o r d a b 1 4 l 等介绍了虚拟咬合的概念和发展，并开发了d e n t c a m 3 0 虚拟咬合仿真系统，可以动态模 拟咬合运动过程；b i s l e r t l 5 】描述了如何将v r 技术应用到虚拟咬合仿真的流程，阐述了咬合运动 分析、碰撞检测等一系列关键技术。日本k a r o l 1 6 等采用纯几何算法抽象了虚拟咬合过程中的 滑动接触过程模型，简化了约束条件，可以动态分析咬合滑动的过程。国内相关的研究才刚刚 起步，仅有北京大学附属口腔医院的李鸿波 1 7 1 等作了相关的研究，他采用c t 扫描重建模型，。 利用k a v o 的超声下颌运动描迹仪记录运动轨迹，建立了虚拟张架取得了一定研究成果。 对于整个口腔正畸仿真系统而言，它是依托于隐形矫治技术发展而来的。从上个世纪9 0 年代后期提出隐形矫治技术以来，国外一些公司就一直从事相关系统的研究开发。1 9 9 8 年，以 i n v i s a l i g n 为注册商标的a l i g n 公司推出了无托槽隐形矫治系统。a l i g n 公司将这项矫治系统从 技术流程到产品输出完全商业化，采用的是研究加工中心与远程医疗相结合的公司运作形式， 使得该项矫治技术获得了巨大的成功，在欧美国家的正畸临床得到了广泛地使用。m o t o h a s h i 【l 8 j 等研制的数字牙颌诊断及治疗系统提供基本的模型测量分析功能，并实现整个矫治过程的仿真。 美国c a n d e t 公司开发的o r t h o c a d ”】系统能够进行多数正畸治疗参数的测量分析、模拟正畸排 牙、预测矫治结果，是现在发展比较成熟的商用口腔正畸仿真系统。 国内对口腔正畸仿真系统的研制稍晚于国外，2 0 0 4 年周沽珉等报道了牙颌模型的三维重构 系统，北京市口腔医院白玉兴【2 0 1 等同时报道了国产无托槽矫治系统的研制进展，2 0 0 5 年，王邦 康【2 l 】报道了国产隐形矫治系统的最新进展。 1 4 论文主要工作及结构安排 本文主要针对s t l 文件的牙齿模型就其正畸仿真过程中的碰撞检测、咬合接触分析以及咬 合行为定义等问题进行了研究。 本论文共分为六章，各章节内容安排如下： 4 南京航空航天大学硕士学位论文 第一章绪论。本章介绍了当前牙齿矫正治疗的背景和发展现状，并阐述了口腔正畸仿真系 统在牙齿矫正治疗中的计算机辅助诊断、治疗方案设计等方面发挥的作用。介绍了论文的主要 研究内容和章= 育安排。 第二章牙齿模型数据结构的建立。描述了s t l 文件的概念、特点和缺陷。介绍了s t l 文 件拓扑重建常用的算法和数据结构。为半边数据结构设计了c + + 语言环境下的类，实现了一种 基于半边结构的s t l 文件拓扑快速重建算法。 第三章基于o b b 的碰撞检测算法。本章介绍了碰撞检测技术常用的层次包围盒技术，并 分析了各种包围盒的性能。提出了一种基于o b b 的碰撞检测方法。论述了基本集合元间的碰 撞检测及其交线的计算方法。 第四章咬合接触分析技术。提出了一种根据区域边界顶点拟合平面，并自动判断干涉区域， 提取干涉区域内部顶点数据和相关信息的方法。通过基于k d 树的k 近邻搜索技术，计算各顶 点的干涉深度并返回给用户可视化信息。 第五章上下颌虚拟咬合仿真。利用p a t r i o t 系统与y a m a h a c h i 咬合器提取上下颌咬合运 动的轨迹信息，实现虚拟咬合仿真。 第六章总结与展望。对本文所做工作进行了总结，分析了本文研究的不足。讨论了今后的 研究方向。 图1 4 论文的研究路线 5 面向口腔正畸的仿真技术研究与应用 第二章输入模型数据拓扑重建 传统的医学计算机辅助诊疗仿真系统的数据获取依赖于医学图像三维重建技术，医学图像 的三维重建就是人体器官的几何形态的三维重建。模型重建的数据来源主要由系列切片图像、 系列c t 图像和系列m r i 扫描图像【2 2 1 。对于口腔正畸仿真系统来说，由于传统口腔正畸治疗已 经发展出了成熟的翻模技术，将患者口内全口牙列进行印模并翻制，获得患者完整的上下颌石 膏模型，所以只要利用三维测量仪对石膏模型进行测量，就可以获得精度较高而且稳定的患者 牙体三维数字模型。因此本文选取s t l 文件格式作为输入数据文件类型。 2 1s t l 文件介绍 s t l 文件格式是一种用三角片表达实体表面数据的数据交换文件，是为快速原型制造 ( r p m ) 服务的文件格式，由美国3 ds y s t e m 公司于1 9 9 8 年制定的一个接口协议。由于s t l 文件格式简单、容易读取和显示，它成为从三维数据测量到c a d 几何造型过程中十分重要的 数据交换文件，同时也是快速原型制造事实上的标准。s t l 模型是一种用许多空间三角形小平 面来逼近原c a d 实体的数据模型，对三维实体的描述具有唯一性，它是多个无续三角形面片 的集合，每个三角形面片由四个数据项表示，即三角形的三个顶点坐标( x ，y ，z ) 和三角形面片 的外法线矢量( 氏，纱，历) ，三个顶点与外法向量符合右手法则，s t l 文件数据结构非常简单，没 有任何的邻接和连接关系。 s t l 文件必须遵循一定的规范才能正确描述三维实体数据模型。这些规范有： ( 1 ) 共顶点规则，每一个三角形面片中必须有两个顶点与其相邻的三角面片共用，即一个三 角面片中的顶点不能落在另一个三角面片的边上。 ( 2 ) 取向规则，由于这些三角面片定义的是三维实体的表面，所以每个三角面片可看作是三 维物体内部与表面的分界面，它的法矢量始终朝外，它与三个顶点连成的矢量方向构成右手法 则。 ( 3 ) 充满规则，三角面片必须充满实体表面，不允许出现缝隙、空洞。 ( 4 ) 取值规则，每个顶点的坐标值必须是非负的，即s t l 实体应该在第一象限( 这一规则并 不必要，设计时可以通过平移将模型移至第一象限来保证) 。 s t l 文件格式规整、结构清晰，但是从实体几何拓扑模型转换成s tl 文件格式时，采用 顶点“分裂”的方式存储，丢失了顶点的邻接拓扑关系，同时还增加了大量的重顶点。根据欧 拉公式可得s t l 文件中三角面片的点、边、面之间的关系： y e + ，一h = 2 ( b p ) ( 2 1 ) 其中v ，e ，f 分别代表三角形的点、边、面的个数；日代表形体表面上的洞：b 表示实体 的个数，p 为穿透形体的孔洞数。 6 南京航空航天大学硕士学位论文 对于一个封闭的，具有二维流形性质且无穿透孔洞的s t l 模型，日为0 ，b 为1 ，p 为0 ； 模型中的每个面由3 条边组成，每条边被两个面所共享。因此它的几何元素之间对应存在如下 等式： e = 3 f 2 ( 2 2 ) 矿一e + f = 2 ( 2 3 ) 将式( 2 2 ) 代入式( 2 3 ) ，就得到s t l 模型中面数与顶点数之间的关系： 矿= e f + 2 = f 2 + 2 ( 2 4 ) 在s t l 文件中所列出的顶点数恰好是面片数的3 倍，由此推出s t l 文件中分裂点 v 。= 6 ( v 一2 ) ，平均分裂点数几乎是原来拓扑点数的6 倍，所以在s t l 拓扑重建中必须采用高 效的算法滤除冗余数据。 2 2 基于半边结构的s t l 文件拓扑重建 如前所述，s t l 文件数据结构非常简单，没有任何的点、边和面的邻接、连接关系。对牙 齿模型进行咬合接触分析时，需要得到模型中点、面的准确信息。进行咬合接触分析的模型的 网格数量一般都计较巨大，大都可以达到十万个以上，因而必须在无序的三角面片的基础上建 立邻近关系，即拓扑重建。拓扑重建对s t l 文件具有以下作用： ( 1 ) 可以在内存中节省模型的存储空间。文件中重复的点、边可以存储在一个结构中。 ( 2 ) 便于进行邻接顶点、边、面的查找。旦拓扑关系建立，整个模型就表现为完整的多面 体，可以容易的进行模型边界和三角面片邻域三角片的搜索。 2 2 1s t l 拓扑重建常用算法 设计并实现一个拓扑重建算法并不难，难的是如何提高算法的效率。一个设计完善的s t l 拓扑结构需要尽可能满足各种后续应用的需求： ( 1 ) 处理、操作大数据量时，依然十分高效、快速； ( 2 ) 具备分析s t l 数据数量的能力，即能够快速的搜索孔洞、间隙和边界； ( 3 ) 能够快速查询每个点的n 邻域信息； ( 4 ) 能够快速查询每个面的相邻面信息； ( 5 ) 通过一条边可以遍历所有其他的边； ( 6 ) 通过一个面可以遍历所有其他的面 目前较常用的方法主要有以下几种： ( 1 ) 直接算法( n a i v ea l g o r i t h m ) 2 3 】：直接算法不采用任何附加的数据结构，逐个将三角面片加 入到实体模型中。当从s t l 文件中读入一个三角面片时，首先检查该三角面片的3 个顶点在已 建立的模型中是否存在，如果己存在，则不建立新的顶点节点；否则建立新的顶点节点。然后 7 并集是所有顶点x 坐标的集合。每一个x 对应一个y 数组，而每一个y 对应一个z 数组。x ， y ，z 数组分别存放顶点的坐标。对于三轴分块算法，其时间复杂度为o ( n 2 ) ( n 为块的大小) 。 三轴分块算法的顶点查询时间于块中顶点数成平方关系，对于数据量巨大的s t l 文件效率不 高。 ( 3 ) 哈希表算法【2 4 l ：哈希表算法用于读取s t l 的平均查找长度约为1 6 6 7 ，故一个顶点的查 找时间与s t l 顶点数无关。哈希表算法的时间复杂度为d ( ) ，当s t l 的顶点数很大( 即n 很 大) 时，哈希表算法的效率将高于三轴分块算法。 2 2 2 三角网格拓扑数据表示 目前采用的拓扑重建的数据结构主要包括：翼边结构、半边结构2 6 1 、四边结构【2 7 1 等。 。 翼边结构是由s t a n f o r d 大学的b a u m g a r t 引入的【2 8 】，它给出了这种基于边的边界表示方法， 并用环来表示边结点的信息。翼边结构可用图2 1 来表示。 8 图2 1 翼边数据结构 南京航空航天大学硕士学位论文 其中c l 、c 2 、c c l 、c c 2 表示四条边，v l 、v 2 表示顶点，f l 、f 2 表示面。翼边数据结构的 结构体设计如下： t y p e d e f s t r u c te d g e v e r t e xv 1 v 2 ； e d g e c 1 , * c 2 , * c c l ，幸c c 2 ； f a c e f 1 ，f 2 ； ) ； 翼边数据结构的边形似一对翅膀，它的名称就由此而来。由于物体的面可能是多连通的( 即 带有孔洞的) ，所以环作为同一面上各个边首尾相接形成的闭合回路，描述了物体面的多连通性 质，一个面具有一个外环( 它的边界) 和可能的多个内环( 孔洞的边界) 。翼边结构存储了边与 顶点，边与面，边与边的邻接关系。在翼边结构中，与边相邻的环有两个。由于翼边没有明确 的正向，因此要确定当前边所在的环与厩比较困难，于是许多研究对翼边结构作了改进。 半边数据结构是翼边结构的一种改进形式。如图2 2 在半边结构中，将一条边一分为二， 其中一条半边属于它一个相邻面的边环，另一条半边属于它另一个相邻面的边环。每条半边仅 储存它的起点指针，这样两条半边能够表示一条边的两个端点，搜索一个面的各端点时，只需 沿着半边顺序即可。一般来讲，半边结构由体( s o l i d ) ，面( f a c e ) ，环( l o o p ) ，半边( h a l t e d g e ) 和顶点( v e r t e x ) 5 个层次的拓扑信息和几何信息组成。如图2 3 所示。 、 半， 边| 1 边， l i 边 l：2 ， 、 图2 2 半边数据结构 体节点构成一个半边数据结构的根节点。通过指向3 个双向链表的指针，体节点给出面、 边和顶点的访问。所有物体被存储到1 个双向链表中，这个表是通过指向该表的后续和前趋物 体的指针来实现的。 面节点表示用半边数据结构表示的多面体的1 个小平面，每一个小平面与1 个环相联系， 每个环表示该小平面的1 条多边形边界曲线。每个面有且只有一个外环( 边界) 。 半边节点表示段中的一条线段。在欧拉实体中，一条线段同时属于相邻的两个面，在半边 结构中，将一条线段看作两条半边，每条半边中记录其起点指针，则两条半边完整地表示一条 边，且每条半边只在个面上。 9 红黑树是二叉搜索树的一种改进。二叉搜索树在最坏的情况下可能会变成一个链表( 当所 有节点按从小到大的顺序依次插入后) 。而红黑树在每一次插入或删除节点之后都会用 o ( 1 0 9 托) 的时间来对树的结构作调整。以保持树的平衡。也就是说，红黑树的查找方法与- - y 搜索树完全一样：插入和删除节点的方法前半部份与二叉搜索树完全一样，而后半部份添加了 一些修改树的结构的操作。图2 4 给出了一棵红黑树的实例，黑色代表黑色结点，白色代表红 色结点。红黑树除了具有二叉搜索树的所有性质外，还有如下性质： ( 1 ) 节点是红色或黑色的。 ( 2 ) 根节点是黑色的。 ( 3 ) 空节点是黑色的。 ( 4 ) 每个红色节点的两个子节点都是黑色( 从每个叶子到根的所有路径上不能有两个连续的 红色节点) 。 1 0 南京航空航天大学硕士学位论文 ( 5 ) 从每个叶子到根的所有路径都包含相同数目的黑色节点。 图2 4 红黑树示例 因为含有n 个内部结点的红黑树的深度至多为2 1 0 9 ( n + 1 ) 2 9 1 ，所以以上的约束条件强制规 定了红黑树的关键属性：从根到叶子最长的可能路径不长于最短的可能路径的两倍，可知这个 树基本是平衡的。因为对树的操作比如插入、删除和查找某个值等都要求与树的高度成比例的 最坏情况时间，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。它可以在 ：o ( 1 0 9 n ) 时间内做查找、插入和删除。若考虑红黑树的动态查找特性，即在查找失败时插入该 结点，这时最坏情况是发生树的形状连续调整，但调整次数不会超过树的深度，故时间复杂性 仍保持为o ( 1 0 9n ) 。因此，红黑树是一种查找效率非常高的树。 2 2 3 2 滤除冗余顶点及拓扑重建 s t l 冗余顶点的滤除算法实际上就是在一组数量巨大的包含有大量重复顶点坐标的点集中 去除掉坐标重复的点。滤除算法的效率取决于构造项点坐标查询序列的效率和在序列中访问指 定顶点的效率。通过顶点滤除算法，最终在原有顶点数量为6 n 的原始数据中得到无重复顶点 且数量为n 的集合。 红黑树节点的结构体设计： s t r u c tr b t r e e s t d ：v e c t o r ：i t e r a t o r i t e r ；手旨向网格中顶点的指针 i n ti n d e x 节点对应顶点在网格中的索引 b o o lo p e r a t o r ( c o n s tr b t r e e & n ) c o n s t ；- 笋0 断顶点大小关系 b o o lo p e m t o 产- - - - ( c o n s tr b t r e e & n ) c o n s t ；笋1 断节点对应的顶点是否相等 冗余点滤除算法伪代码： m y m e s hm e s h ； 面向口腔正畸的仿真技术研究与应用 s t d ：v e c t o r ：i t e r a t o rv _ i t ； s t d ：s e t _ r b t r e e ； s t d ：p a i r s t d ：s e t ：i t e m t o r ，b o o l j p a i r ； w h i l e ( ! s t l 文件结束) 读取三角形强的三个顶点：v l ，v 2 ，v 3 v l ，v 2 ，v 3 对应的索引v e r t e x h a n d l e l ，v e r t e x h a n d l e 2 ，v e r t e x h a n d l e 3 ； i f ( v l 没有在m e s h 的v e r t e xl i s t 中出现过) v i t = v e r t e x _ l i s t p u s h _ b a c k ( v 1 ) 把v l 作为新顶点插入v e r t e x _ l i s t 尾部 新建顶点v 。对应的红黑树中节点的对象： r b t r e e r b _ t r e e ；r b t r e e i t e r = v _ i t ； r b t r e e i n d e x = v e r t e x _ l i s t 1 e n g t h 0 ；顶点链表的长度对应的索引 判断红黑树中是否已经有相同的顶点存在，若没有则把r bt r e e 插入到红黑树中， 否则返同已存在顶点在二叉树集合中对应的索引： j p a i r = _ r b t r e e i n s e r t ( r b _ t r e e ) ； i f l t p a i r s e c o n d t r u e ) v e r t e x h a n d l e l = r bt r e e i n d e x ； e l s e v e r t e x h a n d l e1 = ( r p a i r f i r s 0 i n d e x ； v e r t e x l i s t e r a s e ( v _ i t ) ； 对于v 2 ，v 3 同样处理。 把t r i ( v e r t e x h a n d l e l ，v e r t e x h a n d l e 2 ，v e r t e x h a n d l e 3 ) 添加到m e s h 的t r i l i s t 南京航空航天大学硕士学位论文 2 2 4 性能分析 上述拓扑重建的时间主要消耗在快速排序过程中，采用递归形式的快速排序算法其平均时 间为t ( n ) = k n i n n ，其中k 为常数，n 为顶点的个数。表2 1 是几种拓扑重建方法复杂度比较， 从时间复杂度上看本文数据结构的构建较哈希表算法的效率差一点，但查找效率比哈希表要高 的多( 哈希表的查找时间复杂度为o ( n ) ) ，半边数据结构在顶点和三角面片的查找过程中的时间 复杂度为o ( d ，且在后续的处理中大量用到邻接顶点、邻接三角形的查找。同时占用内存要比 哈希表低的多。因此在排序过程中的时间消耗是值得的。 直接法三轴分块法哈希表法半边结构 时间复杂度 o ( n 2 )o ( n 2 )d ( 以)o ( nl o g n