（计算机应用技术专业论文）虚拟牙齿矫正系统中牙齿移动路径规划研究.pdf

论文题目：虚拟牙齿矫正系统中牙齿移动路径规划研究 专业：计算机应用技术 硕士生：王增波 指导教师：李占利 摘要 ( 签名) 皇堕丝 ( 签名) 歪量查 牙齿移动路径规划是开发虚拟牙齿矫正系统非常重要的一部分，如何规划牙齿移动 的路径是一个很复杂的问题，不仅要寻求一条无碰撞的最短路径，而且还要求该路径尽 可能平滑并满足一定的安全性。本文在分析了隐形牙套矫正技术及目前各种路径规划方 法优缺点的基础上，选择遗传算法解决虚拟牙齿矫正系统下的牙齿移动路径规划问题。 本文通过分析牙齿移动路径规划问题的特点，对所采用的遗传算法的各个环节进行 了细致的分析，包括问题的定义、染色体的表示和编码、适应度函数的设计以及遗传操 作算子的设计和算法参数的分析和选取。 首先，开发出存储牙颌模型的s t l 格式文件的装载模块，采用哈希表法对牙颌模型 进行拓扑结构的重建，并在o p e n g l 环境下实现牙颌模型的渲染和三维可视，采用三维 射线拾取技术和三维交互标记扩展分割方法实现牙颁模型的快速分割，最终得到供移动 路径规划所需的已分离的牙齿模型。 然后，在把牙齿模型移动过程离散化成一系列的路径点的基础上，建立移动路径规 划的数学模型，并采用对距离长度和基于碰撞检测的碰撞强度“加权和”的形式求得综合 反映各子目标要求的单一适应度函数，将多目标问题转化为可利用单目标遗传算法求解 的等效问题，并选择赌轮选择法、单点交叉和简单变异等遗传操作算子对牙齿移动路径 进行求解。 最后，把通过遗传算法求得的结果解码为每颗牙齿移动的路径点信息，并根据这些 信息在虚拟牙齿矫正系统中建立牙齿矫正过程的移动路径，依照该移动路径插值生成牙 齿移动过程的动画序列，最终实现整个矫正过程的可视化。 关键词i 虚拟牙齿矫正；s t l 文件；路径规划；碰撞检测；遗传算法； 研究类型：应用研究 s u b i e e t：as t u d yo fp a t hp l a n n i n gf o rt o o t hm o v e m e n ti nv i r t u a l o r t h o d o n t i c st r e a t m e n ts y s t e r n s p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：w a n gz e n g b 。( s i g n a t u r e ) 堡豳：! ! 竺生 i n s t r u c t o r ：l iz h a n l i a b s t r a c t ( s i g n a t u r e ) c ；z 觚k p a t hp l a n n i n gf o rt o o t hm o v e m e n ti sa v e r yi m p o r t a n tp a r ti nt h ev i r t u a lo r t h o d o n t i c s t r e a t m e n ts y s t e m h o wt od e s i g nt h ep a t ho ft o o t hm o v c m c l l t ，w h i c hn o to n l yg u a r a n t e e sa c o l l i s i o n - f r e e p a t hw i t hm i n i n l u l nt r a v e l i n g d i s t a n c eb u ta l s or e q u i r e ss m o o t h n e s sa n d c l e a r a n c e ，i sav e r yc o m p l i c a t e dp r o b l e ma n di sa l s ow h a tt h ep a p e rc o n c e n t r a t e so n t h u s ，a l l a p p r o a c hf o rt h ep a t hp l a n n i n gb a s e do nt h eg e n e t i ca l g o r i t h mi sp r o p o s e di nt h ep a p e r , b y a n a l y z i n gt h ei n v i s i b l ea l i g n e rt e c h n o l o g ya n dt h em e r i ta n ds h o r t c o m i n go fv a r i o u sp a t h p l a n n i n gm e t h o d s i na c c o r d a n c ew i t ht h ec h a r a c t e r i s t i co fp a t hp l a n n i n gp r o b l e m , e a c hc o m p o n e n to ft h e a l g o r i t h m sa r ea n a l y z e dc a r e f u l l y , i n c l u d i n gi s s u ed e f i n i t i o n , c h r o m o s o m er e p r e s e n t a t i o n , p a t h e v a l u a t i o n , g e n e t i co p e r a t o r sd e s i g na n dg ap a r a m e t e r ss e l e c t i o n f i r s t l y ，t h el o a d i n gm o d e li sd e v e l o p e do nt h eb a s i so f a n a l y z i n gt h ep r o p e r t yo f t h es t l f i l e t h eh a s ht a b l em e t h o df o rt h er e c o n s t r u c t i o no fd e n t o g n a t h i cm o d e l sf r o ms t lf i l e si s p r e s e n t e d , a n dt h er e n d e r i n ga n dt h r e e - d i m e n s i o n a lv i s u a l i z a t i o no fd e n m lm o d e la i ea l l i m p l e m e n t e di no p e n o le n v i r o n m e n t t h e naf a s t3 dm e s hs e g m e n t a t i o nm e t h o du s i n g i n t e r a c t i v em a r k e r sa n dt h r e s h o l df o rd e n t o g n a t h i cm o d e l ss e g m e n t a t i o ni sa l s op r o p o s e d , a n d a p p l i e di n t h et e e t hs e g m e n t a t i o n w ec 锄g e tt h es e g m e n t e dd e n t i t i o nm o d e l s w h i c hp a v et h e w a y f o rt h et o o t hm o v e m e n tp a t hp l a n n i n g s e c o n d l y ，t h em o v i n gp r o c e s so f t e e t hm o d e lc a nb ec h a n g e dt oas e r i e so f p a t hp o i n t , a c c o r d i n gt ow h i c ht h em a t h e m a t i c a lm o d e lo fp a t hp l a n n i n gi se s t a b l i s h e d w ec o n v e r tt h e m u l t i - o b j e c t i v ep r o b l e mi n t o t h es i n g l e o b j e c t i v ep r o b l e me x p r e s s e db yt h em e a no f e v a l u a t i n gt h ef i n e n e s sf u n c t i o no f w e i g h ts l i mo f d i s t a n c el e n g t ha n dc o l l i s i o ns t r e n g t h a n d t h ep a t ho f t o o t hm o v e m e n ti sc o m p u t e db yu s i n gr o u l e t t ew h e e ls e l e c t i o no p e r a t o r , o n e - p o i n t c r o s s o v e ro p e r a t o ra n ds i m p l em u t a t i o no p e r a t o r f i n a l l y , t h em o v i n gp a t hp o i n ti n f o r m a t i o nf o re v e r yt o o t hi so b t a i n e db yd e c o d i n gt h e r e s u l t sf r o mg e n e t i ca l g o r i t h m , a n da c c o r d i n gt ot h eg i v e ni n f o r m a t i o nt h ew h o l ep a t hf o r t e e t hi si m p l e m e n t e di nt h ev i r t u a lo r t h o d o n t i c sr c a t m c n ts y s t e m a n dt h e nw ea d o p t i n t e r p o l a t i o nm e t h o dt oa c h i e v ee a c he e lo fa n i m a t i o ns e q u e n c ed u r i n gt h ep r o c e s so ft o o t h m o v e m e n t , a n da c h i e v et h ev i s u a l i z a t i o no f t h ee n t i r eo r t h o d o n t i c st r e a t m e n t k e y w o r d s ：v i r t u a lo r t h o d o n t i c st r e a t m e n t s t lf i l e p a t hp l a n n i n g c o l l i s i o n d e t e c t i o n ( g a ) g e n e t i ca l g o r i t h m t h e s i s ：a p p l i c a t i o nr e s e a r c h 要错技夫擎 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：a 影靓波日期：? 妒7 莎z 矽 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：多叫咯戚指导教师签名：季占禾f ? 唧年多月2 扩日 i 绪论 1 绪论 1 1 选题背景及研究意义 进入二十一世纪，全球的科技得到了飞速的发展，人们的物质和精神生活水平都得 到极大的提高，在工作、交际、生活各个方面，越来越多的人对自身的外表越来越重视， 不断地追求外在形象的完美，使得近年来整形美容业得到飞速发展。牙齿是人类品尝食 物、展现形象的工具，有一付健康美白的牙齿是大多数人的梦想，牙齿直接影响个人的 仪容和生活质量，一副整齐洁白的牙齿，自然令人的外表更加出众。很多人或多或少有 一些牙齿方面的问题，较常见的牙齿问题包括牙齿拥挤、稀疏、哨牙和暴牙等i l j 。他们 的牙列不齐不但严重影响到他们的形象，还经常性地给社交生活和工作带来不必要的麻 烦，不仅如此，牙齿正畸者龋病、牙龈和牙周疾病的发病率也比较高；严重者还有颞下 颌关节的问题，并发头疼等其他症状，致使身体健康受到干扰，生活质量下降。很多人 也知道接受牙齿矫正才能重造一剐整齐的牙齿，但一般的金属矫正器治疗法，由于形状 突出、易于造成口腔磨损、影响美观、影响正常饮食、难清洗等缺点使很多成年人敬而 远之，多数用于儿童牙齿矫正【2 j 。 在美国，凭借极为先进的牙齿矫正技术，身体健康的4 0 岁以下成年人都有机会通过 漂白、镶饰、牙填充及矫正等手段，让自己拥有灿烂的笑容。据悉，在美国和加拿大， 每年都有上1 0 0 万1 8 岁以上的成年人在接受牙齿矫正治疗。中国目前的成人牙齿矫正治 疗已经变得越来越普遍。 在传统牙齿治疗中，治疗设备需要反复调整以达到正确矫正牙齿移动轨迹。这种治 疗方法通常周期较长，代价昂贵，同时对病人也是一种折磨。因此长期以来，对计算机 应用于牙齿科学，发展一种计算机辅助模拟矫正系统是一个重要目标例。 近些年来，随着计算机技术的不断发展，特别是计算机图像处理技术、虚拟现实技 术( v i r t u a lr e a l 蚵t e c h n o l o g y ) 和现代医学的飞速发展与交叉融合、相互渗透使得医学仿 真系统的研究与设计已成为计算机应用的一大热点。计算机技术越来越多地应用于现代 医疗领域，一些新的技术诸如c a s ( c o m p u t e ra s s i s t e ds u r g e r y ) ，c i s ( c o m p u t e ri n t e g r a t e d s u r g e r y ) ，i c s ( i m a g eg u i d e ds u r g e r y ) 也越来越多的应用到外科学方面。采用计算机图形 学与数据可视化技术，利用计算机图像处理和分析方法，选择数学模型对三维数据进行 人体器官几何重建，进而在计算机上模拟出病灶部位的三维结构，并且使得依据三维数 据建立的模型具有实际物体的物理性质，最后利用v r ( v m u a lr e a l i t y ) 手段虚拟手术的逼 真场景就是所谓的虚拟手术f 、，j n i 】a ls u r g e r y ) 。 通过这种虚拟手术方案能够利用图像数据帮助医生合理、定量地制定手术方案，进 西安科技大学硕士学位论文 行实际手术之前检验评价各种手术方法，还可以反复训练外科医生做各种复杂的手术操 作而不受实验人体数量的限制，使医生能够在计算机建立的虚拟的环境中设计手术过 程，进刀的部位、角度等【2 】。对于选择最佳手术途径、减少手术损伤、减少对临近组织 损害、提高肿瘤定位精度、执行复杂外科手术和提高成功率等具有十分重要的意义。 由于金属矫正器治疗存在着诸多的不足，近年新兴了一种新型的用于错颌畸形矫正 的虚拟手术技术隐形牙套矫治技术，图1 1 和图1 2 就是隐形牙套的外观和佩戴效 果，该技术可进行牙列间隙、拥挤、扭转等多种错颌畸形的矫治，相对目前最常用的固 定矫治技术，它具有以下优点： 美观：其隐形的特点，使牙齿的矫正过程几乎在旁人毫无察觉之中完成，解决了很 多患者尤其是成人对矫正牙齿时的美观顾虑。 舒适：患者使用时异物感觉较小，对口腔粘膜的刺激也较小。 方便：可自行摘戴；同时省去了就诊时医生调整矫治器的时间，节约您的宝贵时间。 清洁：口腔卫生易于维护，不必担心牙龈炎、牙齿脱矿、变色等问题。 个性化及可预见：可以在治疗前用电脑可视化模拟整个治疗过程中牙颌的变化，更 好地选择个性化的矫正方案。 图1 1 隐形牙套外观图1 2 佩戴效果 对于正畸医师而言，采用隐形矫治技术还可以大大减少调整矫治器的工作量，将更 多的精力用于矫治方案的设计，可以接诊更多的需矫正的病人。同时采用牙颌数字模型 还可以大大方便复杂错颌畸形病例的远程专家会诊，共享医疗资源。它主要有以下六个 方面的特色： ( 1 ) 该方法针对每个患者的个体特征进行矫正过程设计和矫正器的个性化制造，而非 简单地选择相对接近患者情况的标准矫正器进行矫正，因而具有更好的针对性和适应 性； ( 2 ) 用于放入口腔内的矫正器材料为目前已成功地用于牙齿保持器制造的材料，即通 过相关认证的高分子材料，对口腔内粘膜的伤害也大大减小，从而使病人的不适感觉大 大减轻； ( 3 ) 使用的高分子材料具有较小的弹性模量，同时作用于牙齿的面积大增加，从而使 2 1 绪论 牙齿和牙骨的受力状态更柔合并便于控制，并使牙齿能整体移动，更易于获得合生物力 学要求的应力分布，患者感到舒适； ( 4 ) 矫正过程医生只需在计算机自动设计阶段，根据计算机辅助设计的结果进行确认 和参数调整，而不需要进行手工调整矫正器，减轻了医生的工作负担，同时也降低了医 生手工操作的熟练程序对治疗过程的影响，一般来说患者只需门诊治疗数次，矫正器的 更换可由患者自己完成，这样不但大量节省了医生和患者的时间，也大大节省了患者的 费用； ( 5 ) 由于矫正器为透明材料制造，在治疗过程中几乎不会影响患者的形象，特别适用 于成年人的牙颌畸形矫正。 。 本文利用v c + + 和o p e n g l 开发平台，研制出一套基于隐形矫治技术的虚拟牙齿矫 正系统。通过对患者牙齿的三维牙颌数字模型进行三维重构、牙齿分割和路径规划，进 而模拟牙齿的矫正过程来设计整个治疗计划 4 1 ，为患者量身定做设计不同时期所需的牙 套，最后根据路径规划的结果由快速成型制造系统制造出透明的弹性塑料牙套。患者只 需按指示不同时期佩戴不同的牙套就可以达到预期效果。由于牙套采用的是透明弹性塑 料，所以完全不影响患者的形象。患者还可以在治疗前就看到虚拟的治疗过程，预先了 解矫正结果。除了能“隐形”，电脑设计的透明牙套还能控制矫正时间。在特定的治疗阶 段里，只有特定的牙齿被移动，从而使矫正效率提高。 牙齿移动的路径规划是该虚拟牙齿矫正系统中的关键部分，所以本文所进行的研究 具有很重要的意义。 1 2 路径规划技术研究的现状及论文的主要工作 1 2 1 路径规划技术研究的现状 路径规划技术是依据某一个或某一些优化准则( 如工作代价最小、行走路线最短等) ， 在其工作环境中找出一条从起点到终点的能避开障碍物的最优或近似最优的路径。路径 规划技术被广泛应用到机器人控制技术研究之中，也成为机器人控制技术研究中的一个 重要问题。随着计算机技术和人工智能技术的飞速发展，移动机器人在生产制造、医疗、 服务、勘探开发和运输等方面得到了广泛的应用，由于对实现机器人自主确定安全和便 捷的行动路线的实时性、精确性和安全性等方面的要求，移动机器人的路径规划技术自 然成为移动机器人研究领域中的一项重要的研究内容。路径规划问题实质上是一个有约 束的优化问题，研究人员为寻求高效的解决方案提出了许多方法。 基于环境模型的规划方法根据掌握环境信息的完整程度可以细分为环境信息完全 己知的全局路径规划和环境信息完全未知或部分未知的局部路径规划。 5 1 具体从其环境 模型和障碍物的状态来分析，可以从以下5 种情况来考虑： 3 西安科技大学硕士学位论文 ( 1 ) 已知环境下的静态障碍物其环境中障碍物的形状、大小和位置对规划系统都是 精确己知的，其障碍物是静止不动的。 ( 2 ) 已知环境下的动态障碍物其环境中障碍物的形态、大小对规划系统都是精确已 知的，但其位置是动态的。 ( 3 ) 已知环境下的静态障碍物对机器人系统而言，环境事先是未知的或部分未知的， 其障碍物的形状和大小是未知的，但其障碍物是静止不动的。 ( 4 ) 已知环境下的动态障碍物对机器人系统而言，环境事先是未知的或部分未知。 ( 5 ) 其障碍物的形状和大小是未知的，同时其位置是动态的。 由于环境模型是已知的，全局路径规划的设计标准是尽量使规划的效果达到最优。 在此领域已经有了许多成熟的方法，包括可视图法、切线图法、v o r o n o i 图法、拓扑法、 惩罚函数法、栅格法等。前4 种方法都是采用基于图论的思想，将目标、机器人及其工 作空间用一个连接图表示，如此一来，路径规划问题就转化为在图上寻找一条从起始节 点到目标节点的路线。惩罚函数法将路径规划这个有约束的问题( 受到障碍物的限制) 转化为一个无约束最优化问题，再求解就可得出解答。栅格法用网格描述机器人的工作 环境，根据栅格的可信度值可确定出障碍物的分布，此时通过避障规划就可得到无碰路 径。 作为当前规划研究的热点问题，局部路径规划得至0 了深入细致的研究。对环境信息 完全未知的情况，机器人没有任何先验信息，因此规划是以提高机器人的避障能力为主， 而效果作为其次。g o e i n gs 等【6 】提出了增量式的d l i t e 算法，该方法利用启发式策略搜 索一条从目标点指向机器人当前位置的路径，并在机器人向目标运动过程中根据局部环 境的更新信息来实时重规划路径，由此得出一条最优路径。在环境部分未知时的规划方 法主要有人工势场法、模糊逻辑算法、遗传算法、人工神经网络、模拟退火算法、蚁群 优化算法、粒子群算法和启发式搜索方法等。前4 种方法相对应用较广，后几种则是近 年来才比较流行，其中启发式方法的研究取得了较大进展。启发式方法的最初代表是a 算法，而其新发展是d 和f o c u s s e dd 这两种由s t e n t za 提出的增量式图搜索算法( 又 称作d y n a l l l i ca 算法) 的产生。d 算法可以理解为动态的d i j k s t r a ( 最短路径) 算法， 而f o c u s s e dd 算法则利用了a 算法的主要优点即使用启发式估价函数，两种方法都能 根据机器人在移动中探测到的新的环境信息快速地修正和重规划出最优路径，减少了局 部规划的时间，对于在线的实时路径规划有很好的效果。此外，还出现了一些基于a 的改进算法，它们一般都是通过修改a 算法中的估价函数和图搜索方向而实现的，可 以较大地提高路径规划的速度，具有一定的复杂环境自适应能力。随着移动机器人应用 范围的扩大，对于规划技术的要求也越来越高，单个规划方法有时不能很好地解决某些 规划问题，所以新的发展趋向于将多种方法相结合。 环境信息完全未知或部分未知，通过传感器在线地对机器人的工作环境进行探测， 4 1 绪论 以获取障碍物的位置、形状和尺寸等信息的局部路径规划，又称动态或在线路径规划。 局部路径规划和全局路径规划并没有本质区别。很多适用于全局路径规划的方法经过改 进都可以用于局部路径规划；而适用于局部路径规划的方法都可以适用于全局路径规 划。 一般而言解决静态路径规划问题较常用的有两种途径：一种是拓扑法，另一种是几 何法。在二维平面空间中，几何法将组成空间表示为一系列递归方式不同精度的网格， 根据不同的精度要求，由粗而精，逐级搜索路径。另一种是拓扑法，根据环境和运动物 体的几何特点，将组成空间划分成若干拓扑特征一致的子区域，并依据彼此的连通性建 立一个拓扑网，在该图中搜索一条拓扑路径，进而得到几何路径。目前常用到的路径规 划方法如人工势场法、栅格法等，计算的实时性很强，便于机器人的动力学优化控制和 实时路径规划，但却保证不了能够寻求到全局最优的路径。 近年来有很多学者运用人工智能的一些方法来解决路径规划的问题，取得了一定的 效果。比如神经网络法，遗传算法等等。但是常规的神经网络算法、遗传算法本身也存 在着一些缺陷，如局部寻优能力差、遗传算法的早熟现象等问题就很突出，严重影响路 径规划的计算效率和可靠性。为提高路径规划问题的求解质量和求解效率，在利用神经 网络算法、遗传算法进行路径规划的基础上，引入模拟退火算法，既能抑制遗传算法的早 熟现象，又克服了其局部寻优能力较差的缺点，形成一种新的路径规划算法来解决机器 人路径规划问题。 由于在牙齿移动路径规划问题领域还没有专门性的算法，本文将借鉴广泛应用于移 动机器路径规划领域的遗传算法来解决牙齿移动过程的路径规划问题。 1 2 2 论文的主要工作 我们进行牙齿移动路径规划的数据源是一种c a d 数据交换格式s t l 文件，先简单 介绍s t l 文件的特点，由于s t l 文件未保存三角面片间的拓扑关系，因此为了表示三 角面片之间的拓扑关系，采用哈希表法建立一个包括面片之间拓扑关系的数据结构，并 利用o p e n g l 技术对三维模型进行实时渲染，通过鼠标对三维数字模型的拾取实现获得 分割所需的信息，研制出交互标记扩展分割方法实现牙齿与牙龈、牙齿与牙齿之间的分 割，最终得到单颗牙齿的数据信息，建立起移动路径规划的数字模型，在选择适当的遗 传操作算子的基础上用遗传算法实现牙齿移动路径的规划，最终按照规划解生成牙齿矫 正过程的动画。具体的工作主要有以下五个方面： ( 1 ) 设计s t l 文件的调用模块，能够从二进制和纯文本两种格式的s t l 文件里提取 三角面片信息，并建立合理的数据结构对三角面片问的拓扑信息进行重构，最终在计算 机屏幕上用o p e n g l 技术重现三维牙颌模型，并能实现对模型任意地缩放和任意角度的 观察。 5 西安科技大学项士学位论文 ( 2 ) 利用交互拾取算法，实现鼠标对三维牙颌模型的交互式操作，采用高效的分割算 法对牙齿进行分割，并设计单齿运动的数据存储结构，存储单齿运动的状态参数。 ( 3 ) 通过交互式操作获取牙颌模型的各项关键数据参数，采用合理的数学模型生成理 想牙弓曲线，辅助生成符合生物医学和口腔正畸学的理想牙列。 ( 4 ) 设计高效的碰撞检测算法，引入到牙齿移动的路径规划过程中，用于精确验证运 动设计结果的合理性和可行性。 ( 5 ) 选择适当的遗传参数对牙齿移动路径进行规划，并记录牙齿移动的运动参数，插 值生成牙齿移动过程的动画序列，最终实现整个矫正过程的可视化。 1 3 论文的结构 本文首先介绍了选题前景及研究意义，路径规划技术的现状，以及这个课题所需作 的主要工作。 在第二章中介绍了如何在以s t l 数据文件格式存储的牙颌模型的基础上，建立牙颌 模型的拓扑结构，并设计出交互标记扩展分割方法，实现了牙颁模型的快速分割，最终 成功建立了移动路径规划所需的牙齿模型，并通过层次包围盒技术实现了路径规划过程 中的碰撞检测。 在第三章中我们把牙齿移动路径规划问题按照遗传法原理建立了数学模型，并针对 该数学模型设计了基于遗传算法的搜索方法，对遗传算法中的各个组成部分，特别是对 选择策略，杂交策略，变异策略通过实验的方式选择了适当的参数实现牙齿移动路径规 划，并分析了各项参数对路径规划性能的影响。 在第四章中介绍了虚拟牙齿矫正系统的系统功能，并在该系统上实现了牙齿移动路 径规划的仿真。 在第五章中对自己研究的主要内容和研究成果进行了总结，以及提出一些需要改善 的地方和对后续的工作进行了展望。 6 2 牙齿移动路径规划的技术基础 2 牙齿移动路径规划的技术基础 我们要在三维环境下仿真牙齿矫正过程，必须充分利用三维图形学的一些理论技术 开发出针对性的算法，包括牙颌模型的重建、牙颌数字信息的获取、牙颌模型的分割以 及牙齿间的碰撞检测等功能模块的实现算法，这样才能为后续的工作铺平道路。因此在 这一章里，我们对这些功能的算法设计及实现进行详细阐述。 2 1 数字化模型的获取 牙颌模型的测量和分析在口腔正畸的诊断和治疗方案的设计中具有十分重要的作 用。以往的研究和临床医疗中主要是以石膏模型作为保存牙颌信息资料的载体，以手工 的方法进行测量。随着正畸学科的发展，石膏模型在保存和测量方面的缺陷已使其很难 为正畸医师提供快速准确的测量数据和进行可视化的治疗预测。计算机技术和三维重建 技术的快速发展使得牙颌模型的数字化三维重建成为可能，现在常用的技术手段为采用 点，线激光表面扫描设备或接触式三坐标测量仪等【7 - 9 1 。 ( t ) 接触式方法 接触式方法通过探针或触头与被测实体发生接触以获取实体的表面数据，由于测量 过程中需要和被测物接触，因此无法获取测头触及表面的数据，如内腔结构和牙领上牙 齿间的狭窄缝隙等；此外受机械结构的限制，该方法测量速度较慢。 ( 2 ) 激光扫描法 根据激光光源的特点和性质，激光扫描法可分为点激光扫描、线激光扫描和区域激 光扫描。激光扫描利用三角测距原理获取实体表面数据，扫描速度快。但对十外形复杂 的实体，如牙颌模型，为获取完整的表面数据，需要从不同方向进行多次扫描，并对不 同方向的扫描数据进行配准，配准过程会造成一定的精度损失。 但由于牙颌模型本身的不规则性和复杂性，采用以上几种技术手段很难同时解决精 度、完整获取模型信息、效率与过程自动化等问题。 ( 3 ) 层析方法 层析方法的具体过程为：首先将牙颌模型放置在深色液态树脂类材料中，并保证树 脂类材料完全填充进牙颌模型上的精细结构中，没有气泡和空隙，然后在一定条件下使 树脂类材料固化，再将固化后的树脂与牙颌模型一起以预定的层厚逐层切削并扫描切削 断面，最后将扫描所得的切削断面图像通过诸如m i m i e s ( t 七利时m a t e r i a l i s t 公司产品) 等软件重构成三维几何模型，使之可以用于后序的计算机处理( 系统流程如图2 1 所示) 。 7 西安科技大学硕士学位论文 图2 1 层析法系统流程 层析扫描方法的优点在于，扫描过程在专用设备上完成，并易于实现过程的自动化， 并在大规模工业应用时可以获得较高的效率；层析过程中每层获取的图像为平面图像， 因而不会出现牙颌模型形状极为复杂的部分难以获取数据或数据靠多次扫描数据组合 而导致精度损失的问题；采用该数字技术模型的精度由切削加工精度的层片叠加重构的 精度决定，而这两项技术目前已非常成熟，其精度要优于基于多次空间扫描结果叠加重 构的精度。 由于本系统对牙颌模型的精确度要求较高，故采用层析方法获取的数字化模型作为 研究对象，该类模型通常都是以s t l 文件格式进行存储的。这种s t l 数字模型文件只 是保存了模型的三角面片的顶点坐标和法向量，没有保存三角面片之间的任何邻接关 系，并且牙齿和牙龈部分是一个整体，我们研究的牙齿移动路径规划的对象是牙齿间的 移动，因此就有必要在建立模型的拓扑信息的基础上把牙齿从牙颌模型中分割出来。 本章后面的四节首先通过s t l 文件重建牙颌模型的拓扑结构，然后在此基础上设计 一种快速的分割算法分割出每一颗的牙齿，最终建立起用于路径规划的牙齿模型，并对 路径规划过程中的碰撞检测技术的实现进行详细阐述。 2 2 模型的拓扑结构重建 2 2 1s t l 文件格式简介与分析 本系统所采用的s t l ( s t c r e ol i t h o g r a p h y ) 格式文件是一种用三角形表达实体表面数 据的数据交换文件，在逆向工程中是三维测量设备数据输出的主要文件格式。s t l 格式 文件用三角网格面表示具有复杂拓扑和外形的几何模型，在快速成型、图形真实感显示、 有限元分析和逆向工程等方面已得到广泛应用。然而，s t l 格式文件只是无序地列出几 何体表面的三角形的几何信息，无法由s t l 文件直接知道不同三角形之间的连接关系， 因此在进行网格分割和区域划分时，如何找到这些三角形的相邻信息，以及三角形所包 含的顶点和边的信息，建立点、边和面的拓扑信息是进行网格分割和区域划分的前提。 同时，s t l 格式文件数据重复很多，每个顶点几乎被重用6 次，所以有必要建立s t l 格式文件的拓扑结构，把相同的几何元素( 顶点和边) 存储为一个元素，从而可以大大节 省模型的存储空间。所以在无序三角形基础上建立其连接关系，即拓扑信息是很有必要 8 2 牙齿移动路径规划的技术基础 的。归纳一下，建立拓扑信息可以带来如下四个好处： f 1 ) 可0 a 节省模型的存储空间，因为相同的几何元素( 顶点和边) 可以存储为一个节 点。 ( 2 ) 可以进行实体模型的合法性检查和进行模型修正。由曲面实体生成的s t l 文件 可能包含有不合法的三角形，导致空洞、裂缝、重叠、交叉等问题。在一些应用中，对 s t l 进行合法性检查和模型修正是必要的。而完成该任务的前提是建立起三角形之间的 拓扑信息。 ( 3 ) 可0 a 方便地对实体模型进行分析。例如，一旦建立了拓扑信息，实体就表示为完 整的多面体，可以很容易地生成实体的截面形状，可以很容易地计算出实体的体积和表 面积等参数。 ( 4 ) 可以方便地实现三维网的分割和区域划分。建立了面片之间的拓扑关系后，就能 按要求进行快速查找，对分割算法和区域划分的提供了很好的支持。 如果不考虑算法的速度，构造s t l 实体的拓扑关系并不难实现，主要就是一个查找 过程。但是对于复杂的自由曲面实体，所生成的s t l 文件非常庞大，有可能包含几万个 三角形，普通的牙颌模型就有5 万多个三角形，这时算法的速度显得非常迫切。这就需 要一个建立s t l 格式实体拓扑信息的快速算法，对于一个包含几万个三角形的s t l 文 件，在普通的微机上只需几秒种完成。 s t l 格式文件的内容就是记录模型中每个三角形的几何信息，包括三角形所在平面 的法矢和它所包含的3 个顶点的坐标。在具体表示上，它又分为a s c i i 码和二进制两种 格式。 a s c i i 码格式逐行给出三角面片的几何信息。每一行以一个或两个关键字开头，关 键字的排列顺序以及关键后面的数据内容如下： s o l i d f a c e t n o r m a l o u t e rl o o p v e r t e x v e r t e x v e r t e x e n d l o o p e n d f a c e t f a c e tn o r m a l 9 西安科技大学硕士学位论文 e n d s o l i d 二进制格式的s t l 文件是用固定的字节数来给出三角面片的几何信息。文件的起始 8 0 字节是文件头，可以放入任何文字信息。紧随着的4 字节整数用来描述实体的三角面 片个数。后面的内容就是逐个给出每个三角面片的几何信息。每个三角面片占用固定的 5 0 字节：3 个4 字节浮点数用来描述三角面片的法矢量，3 个4 字节浮点数用来描述第 1 个顶点的坐标，3 个4 字节浮点数用来描述第2 个顶点的坐标，3 个4 字节浮点数用来 描述第3 个顶点的坐标，每个三角面片的最后2 字节用来描述三角面片的属性信息( 暂 时没有用) 。如表2 1 所示： 表2 1s t l 文件二进制格式 2 2 2 拓扑重建算法 s t l 格式实体的拓扑重建主要包含两方面工作：一是重复顶点的合并，也就是将 s t l 文件中重复列出的顶点在实体模型中只表示成一个顶点；二是邻接关系建立，也就 是通过某一个面片能够的找到与其相邻接的面片，从而建立三角面片之间的毗邻关系。 s t l 格式文件的拓扑重建过程具体来说是从s t l 文件中依次读取三角形，查找并 去除重复的顶点，建立一个包含所有不重复顶点的点表( 存储顶点坐标等) ，同时建立包 含所有三角形的面表( 存储顶点的索引) 。点表记录每个顶点的坐标信息，同时点表中的 每个顶点记录它所属于的多个三角形在面表中的编号( 由于进行了顶点的合并，每个顶 点可能有多个引用面) 。面表记录它所包含的3 个顶点在点表中的编号、法向量信息以 及邻接的面片的编号。其中每个面记录指向三个顶点的指针，即建立了由面获得包含点 的拓扑信息。每一个点记录与之连接的面，即建立了由点获得引用面的拓扑信息。其他 的拓扑信息都是可以根据这两种拓扑信息建立起来。因此，这里的主要工作就是点的合 并，点表和面表的建立，数据结构和合并算法的设计就相当重要了，如果数据结构和合 并算法设计不好就会导致程序的效率低下。 构造s t l 格式文件的拓扑关系关键在于去除重复的顶点，而这个过程可以归结为顶 点的查找过程。如何快速查找到重复的顶点并把它去除，直接关系到拓扑重建的效率。 文献【l o 】中对改进的直接法、平衡二叉树法和哈希表法三种方法进行对比，实现顶点的查 找去除并构建s t l 格式文件的拓扑结构，通过实例对上述3 种方法的性能进行了比较。 通过对以上三种方法的效率比较，确定用哈希表法作为拓扑重建的算法。在算法设 l o 2 牙齿移动路径规划的技术基础 计过程中，设计三个表：第一个是顶点哈希表，它实质上就是一个查找表，通过特定的 数学公式的计算得到顶点坐标对应的哈希地址，当该地址与表中的地址发生冲突时，通 过从冲突链表中的查找，能够快速地判断出该顶点是否已经存在；第二个是点表，它是 一个无重复顶点的存储表，未发生哈希地址冲突或发生哈希地址冲突但在冲突链表中查 找不到的顶点将被加入到该点表；第三个是面表，它是存储所有三角面片点信息的索引 表，存储面片法向量、三顶点索引和邻接面片索引三类信息。存储结构如图2 2 一图2 4 所示。 邻接面片 ， - 、 点坐标- 4 面索引1磔l 2 l 。 ii 图2 2 顶点哈希表( 查找表)图2 3 点表( 无重复的顶点表) 邻接面片 ， _ 、 法冉量点素引- 4 面索引l面索引2 i 面囊引， i 图2 4 面表( 面信息表) 拓扑结构建立过程( 面片与各表的关系如图2 5 所示) ： ( 1 ) 读入一个面片。 ( 2 ) 先算出三个点的哈希地址。 ( 3 ) 在顶点哈希表中查找，若未找到表示是一个新点，转到( 4 ) ；若找到表示是一个旧 点，转到( 5 ) 。 ( 4 ) 把新点加入到点表中( 点坐标和邻接面片索引号) ，且把新点的索引号加入到哈 西安科技大学硕士学位论文 希表中，转到( 6 ) 。 ( 5 ) 若是一个旧点时，把当前面片的索引号加入到点表中该顶点的邻接面片链中，转到 ( 6 ) ( 6 ) 不管是新旧点都把法向量、三顶点在点表中的索引号加入面表，同时对邻接面片 的邻接面片链中加入该面片的索引。 ( 7 ) 转到( 1 ) 直到所有面片都读完为止。 r 点坐标哈希地址，丁新点点表( 加坐标、邻接面索引) 一个面片 法向量面表( 直接存储) l 旧点+ 点表( 加邻接面索引) l - 面索引卜面表f 索引号即为面片在s t l 文件中的顺序号) 图2 5 拓扑结构建立过程 2 3 模型信息获取的理论方法 该模型是一个三维数字模型，基本图形元素是三角面片，在o p e n o l 环境下如何通 过鼠标实现模型信息的获取是进行后续一切工作的前提。在这一节，我们通过研究三角 形面片与射线相交理论，实现对三角面片信息的拾取，然后就能采用交互方式实现牙颌 模型的分割，建立起移动路径规划所需的模型。 2 3 1 面片拾取理论 在许多情况下计算机图形处理系统不仅要绘制图形，而且要允许操作者能够通过输 入设备( 通常是鼠标) 操纵屏幕上的物体( 标识、移动和修改) 。有时还需要获取物体上点 的空间坐标或测量物体的几何特性如距离、角度、半径等，这些操作都需要以拾取作为 实现的基础。特别是在3 d 交互图形应用程序中，常常要用鼠标去选择图形对象，其实 现的机制基于鼠标拾取算法。本系统是一种交互式的三维仿真诊断软件，需要通过鼠标 的拾取来实现牙颌模型的多角度显示、数据测量、模型分割、牙列重排等功能，所以精 确快速的拾取是非常重要的。 这里所谓的拾取操作指当我们在屏幕上用鼠标点击某个图元时应用程序能返回该 图元的一个标志和某些相关信息。有了这些信息就表示我们有了对该图元的控制权，实 现你所需要的功能。 三维图形库o p e n g l 提供了一种拾取模式，在该模式下能够使用鼠标拾取三角面片， 但系统采用的牙颌模型数据量巨大，通常包含几万个面片，o p e n g l 拾取模式操作时间 长，交互过程中时间延迟严重，无法满足实时拾取的要求。因此，我们开发出一种快速 的射线拾取法，实现对三角面片信息的快速拾取。 2 牙齿移动路径规划的技术基础 拾取算法的思想很简单：得到鼠标点击处的屏幕坐标，通过投影矩阵和观察矩阵把 该坐标转换为通过视点和鼠标点击点的一条射入场景的光线，该光线如果与场景模型的 三角形相交，则获取该相交三角形的信息。本文讲述的方法除可以得到三角形的一个索 引号以外还可以得到相交点的重心坐标。 从数学角度来看，我们只要得到射线的方向矢量和射线的出射点，我们就具备了判 断射线与空间一个三角面是否相交的条件，根据拾取操作的处理顺序，首先通过坐标变 换得到射线矢量，然后求解射线矢量与三角形图元是否相交以及它们的交点和到交点的 距离。 2 3 2 射线矢量的获取 二维屏幕坐标的原点在屏幕左上角，而在o p c n g l 环境中，采用右手坐标系，屏幕 是x o y 平面，平面的原点位于屏幕中心，z 轴垂直屏幕向外。因此，首先对二维屏幕坐 标进行归一化处理，即将其原点移到屏幕的中心，并且使屏幕的四个角的坐标依次为 ( 1 ，1 ) ，( 】，d , o ，一0 , ( - i ，一1 ) 。因此进行如下公式所示的坐标变换，其中w 是屏幕宽度，h 是 屏幕高度： hi | x l w i 驯2 2 l y