（计算机应用技术专业论文）计算机辅助隐形牙齿正畸功能实现.pdf

浙江大学硕士学位论文摘要 摘要 牙齿正畸日益流行，在国外，计算机辅助技术在牙齿正畸中的应用从上世纪 9 0 年代就已经开始。但在国内，此类技术与国外还有不少差距。本文实现了计算 机辅助牙齿正畸中的主要功能，这些主要功能贯穿了牙齿正畸的整个流程，可以 说是数字化牙齿正畸中的核心。全文共分六个章节进行阐述。 第一章，介绍了牙齿正畸中的生物学常识，计算机牙齿正畸是一门交叉学科， 需要必要的生物学理论作支撑。还介绍了计算机辅助牙齿正畸在国内外的发展状 况，以及数字化正畸软件的总体流程。 第二章，介绍了计算机辅助牙齿正畸中的变形算法。本文的变形算法是一种 基于旋转不变性拉普拉斯变形算法。针对变形矩阵稀疏性的特点，采用稀疏矩阵 的数据结构进行存储，运用s u p e r l u 进行求解。如果最终结果仍不理想，可以采 用光顺算法进一步调整模型形状。 第三章，介绍了计算机辅助牙齿正畸中的虚拟咬合功能。该功能目的是找出 上、下牙模型正确的咬合位置关系，为后续的正畸提供依据。我们采用了基于迭 代最近点的方法，并采用空间剖分结构和g p u 对虚拟咬合过程进行加速。 第四章，介绍了平面裁剪技术。该技术主要用来剔除导入模型的多余信息， 为牙齿模型的后续处理提供基础。 第五章，介绍了计算机辅助口腔正畸中的诊断功能。该功能的目的是提供方 便友好的交互式界面，方便操作人员，提取牙齿参数信息，为下一步正畸提供依 据。 第六章，总结全文，给出进一步研究的方向。 关键词：隐形正畸，变形，虚拟咬合，诊断 浙江大学硕上学位论文 a b s t r a c t a b s t r a c t o r t h o d o n t i c si sg e t t i n gm o r ea n dm o r ep o p u l a ri n0 1 1 1 d a i l yl i f e 1 1 1 ea p p l i c a t i o no f c o m p u t e ra i d e dd e s i g ni no r t h o d o n t i c ss t a r t e df r o ml a s tc e n t u r y i nt h i st h e s i s ，w eh a v e r e a l i z e dt h em a i nf u n c t i o n si n0 1 1 1 i n v i s i b l eo r t h o d o n t i c s t h e s ef u n c t i o n sa r e i n d i s p e n s a b l ei nt h eo r t h o d o n t i ct r e a t m e n t t h ew h o l et h e s i s i sd i v i d e di n t os i x c h a p t e r s i nc h a p t e ro n e ，a f t e ri n t r o d u c i n gt h eb a s i cb i o l o g i c a lk n o w l e d g eo fo r t h o d o n t i c s ， w ed e s c r i b et h ed e v e l o p m e n to fc o m p u t e r - a i d e do r t h o d o n t i ct e c h n o l o g ya th o m ea n d a b r o a d t h e n ，w ep r e s e n tt h ef r a m e w o r ko fa ni n v i s i b l eo r t h o d o n t i c ss y s t e m i nc h a p t e rt w o ，w ep r e s e n tar o t a t i o ni n v a r i a n tl a p l a c i a nd e f o r m a t i o n b y u t i l i z i n gt h ef e a t u r eo fas p a r s em a t r i x ，w ea d o p ts u p e r l u t os o l v et h el i n e a re q u a t i o n s y s t e m t w os m o o t h i n ga l g o r i t h m sa l eo p t i o n a l l ye m p l o y e dt os m o o t ht h em o d e l i nc h a p t e rt h r e e ，w ei n t r o d u c e0 1 1 1 7v i r t u a lo c c l u s i o nb a s e do nt h ec l a s s i ci t e r a t i v e c l o s e tp o i n ta l g o r i t h m w eu s es p a c es u b d i v i d i o na n dg p ut o i m p r o v et h e p e r f o r m a n c e i nc h a p t e rf o u r , w ei n t r o d u c eap l a n ec l i p p i n ga l g o r i t h mt oc l i pi m p o r t e dm e s h m o d e l i nc h a p t e rf i v e ，i n t r o d u c i n gt h ed i a g n o s i sm o d u l eo fo u ri n v i s i b l eo r t h o d o n t i c s s y s t e m s o m eu e r - f r i e n d l y u s e ri n t e r f a c e sa r ee m p l o y e dt oc a l c u l a t et h et o o t h p a r a m e t e r s i nc h a p t e rs i x ，c o n c l u d i n gt h et h e s i sa n dd i s c u s st h ed i r e c t i o n sf o rf u t u r ew o r k k e y w o r d s ： i n v i s i b l e o r t h o d o n t i c s ，d e f o r m a t i o n ，v i r t u a lo c c l u s i o n , d i a g n o s i s 浙江大学硕士学位论文图目录 图目录 2 1 共边面面关系的建立1 1 2 2 变形算法流程1 2 2 3 拉普拉斯光顺算法流程1 3 2 4 双步光顺算法流程1 4 2 5 变形l ； 牙齿形态。1 5 2 6 交互式选取变形区域1 5 2 7 变形后牙齿形态1 6 2 8 双步光顺前牙齿形态1 6 2 9 双步光顺后牙齿形态1 6 2 1 0 拉普拉斯光顺前牙齿形1 6 2 1 l 拉普拉斯光顺后牙齿形态16 3 1 迭代最近点算法l8 3 2 旋转矩阵算法2 1 3 3 多点对齐算法流程图2 4 3 4 基于图形空间的碰撞检测2 5 3 5 距离图显示2 7 3 6 第一次启动g p u 流程图一3 0 3 7 第二次启动g p u 流程图3 l 3 8 迭代选取最小值3 3 3 9 对齐前上牙、整牙侧扫描面相对位置3 6 3 1 0 对齐前下牙、整牙侧扫面相对位置。3 7 3 1 1 对齐前上、下牙与整牙侧扫描面相对位置3 7 3 1 2 对齐前上牙、整牙侧扫描面交互式选点3 7 3 1 3 对齐前下牙、整牙侧扫描面交互式选点3 8 3 1 4 多点对齐后正视图3 8 3 1 5 多点对齐后左侧视图。3 8 3 1 6 多点对齐后右侧视图3 8 3 17 单遍i c p 后正视图3 8 3 1 8 单遍i c p 后左侧视图。3 8 3 1 9 单遍i c p 后右侧视图3 8 3 2 0 两遍i c p 后正视图3 9 3 2 1 两遍i c p 后左侧视图3 9 3 2 2 两遍i c p 后右侧视图3 9 3 2 3 迭代最近点c p u 执行正视图4 0 3 2 4 优化后g p ui c p 正视图4 0 3 2 5 迭代最近点c p u 执行左侧视图一4 0 i i l 图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图 浙江大学硕士学位论文图目录 3 2 6 优化后g p ui c p 左侧视图4 0 3 2 7 迭代最近点c p u 执行右侧视图4 1 3 2 8 优化后g p ui c p 右侧视图4 1 4 1 裁剪平面与边相交4 4 4 2 裁剪平面与边界边相交4 5 4 3 平面裁剪算法流程4 6 4 4 平面裁剪前牙齿模型4 7 4 5 平面裁剪后牙齿模型4 7 5 1 纵颌曲线生成流程4 9 5 2 贝叶斯分裂法5 0 5 3 诊断模块界面5 2 5 4 牙冠宽界面5 2 5 5 纵颌曲线界面5 3 5 6 牙弓宽界面5 3 5 7 覆合覆盖界面5 4 5 8 视口平移操作。5 4 i v 图图图图图图图图图图图图图图图图 浙江大学硕上学位论文表目录 表目录 表格3 1 色阶实验数据( 单位：s ) 2 6 表格3 2 迭代最近点实验结果数据( 单位：s ) 3 5 表格3 3 实验时间对比表( 单位；m s ) 4 1 v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝姿态堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘鲎有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年月日签字日期：年月日 浙江大学硕上学位论文第l 章绪论 第1 章绪论 1 1 口腔正畸学知识简介 1 3 腔正畸掣l 】作为1 3 腔学的一个分支，通过对畸形牙齿的实际测量，提取牙 齿的相关信息，结合力学、生物学等知识，对牙齿进行矫治，实现牙齿外表美观、 咬合功能改善的目标。 口腔牙齿畸形的原因分为先天原因和后天原因两种。先天原因源于父母的遗 传，后天原因则可能源于后天牙齿护理不周，如乳牙脱落后，恒牙生长期间，不 注意保护，舌头、手指等接触导致牙齿生长变形，或者由于外力的作用对牙齿造 成硬伤，使牙齿错位、损坏，以致脱落等。 口腔畸形的临床表现是多种多样，如牙齿拥挤、牙齿稀疏、双颌前突等。口 腔畸形不但看起来影响面部的美观，而且会造成口腔和消化道的疾病，引发多种 疾病。因此，口腔正畸引起了人们的愈来愈多的重视。 牙齿要经历约2 0 年左右的生长发育才最终完成。牙齿的形态多种多样，总 体上分为切牙、尖牙、磨牙三类。切牙的主要的功能是咬断食物，上、下牙各有 4 颗，共计8 颗。紧挨着切牙的是尖牙，上、下牙共计4 颗，主要功能是撕咬富 有纤维的食物，最靠近里边的形状呈不规则正方形的磨牙，共计8 颗，功能是磨 碎食物。 牙齿移动的生物学原理的研究可分为槽骨可塑性、骨质抗压性、周膜内环境 稳定性、组织改建四个方面。 1 牙槽骨的可塑性 骨组织的可塑性是很大，适应性也很强，牙槽骨是人体骨骼中代谢、改建最 活跃的部分。改建由增生和吸收两个过程构成，二者处于一个动态平衡的状态， 这是正畸治疗的生物学基础。 2 牙骨质的抗压性 相同的外力的作用下，牙槽骨逐渐吸收，而牙骨质仅有少量浅层部分被吸收。 浙江大学硕士学位论文第1 章绪论 原因是牙根表面总是覆盖着一薄层尚未钙化的类牙骨质，其对压力吸收较牙骨质 具有更强的抵抗力，起到对深层牙骨质有保护作用。 3 牙周膜内环境的稳定性 牙周膜的细胞成分包括合成性细胞、吸收性细胞和未分化的间充质细胞等。 在保证牙周正常血液循环、各种细胞成分存在和分化的条件下，经过神经系统的 调节，口腔内各种细胞活性因子活化，参与其组织改建活动。 4 牙齿受力后的组织改建 牙齿受力后的组织改建由牙周膜反应、牙槽骨改建、牙根吸收、牙髓反应和 颞下颌关节改建五个方面构成。 传统口腔矫治方法。方丝弓矫治器是一种多带环矫治器，由a n g l e 在1 9 2 5 年首先提出，当时的方丝弓矫治器是在钉管装置唇弓、带状唇弓矫治器的基础上 发展而来。方丝弓借助其边缘与托槽方型槽沟间的作用而施力，方形矫治弓丝是 该矫治器的一个重要特点，故称之为方丝弓矫治器。后来开发研制的矫治器都是 依据方丝弓矫治器的基本原理，在其基础上从组成材料、附件形式、矫治步骤等 方面有所创新发展。自从上世纪5 0 年代以来，方丝弓矫治器已逐步成为应用最 广泛的固定矫治器。 方丝弓矫治器组成部分：带环、托槽、矫治弓丝、末端管及其他附件。 ( 1 ) 带环：由不锈钢片或合金金属片制成。与牙齿密贴地粘着，具有良好的固定 作用，同时不妨碍咬合，对牙龈无刺激。带环主要由不锈钢片或合金金属片制成， 要求与牙齿密贴地粘着，具有良好的固位作用，并不妨碍咬合，对牙龈无刺激。 可以针对各个牙而个别制作，也可直接选用预制成的不同大小型号的预成带环。 ( 2 ) 托槽：由不锈钢或生物陶瓷复合树脂制成，其中部有容纳弓丝的槽沟。槽沟 宽度及深度分为二类，一类是宽0 4 6 m m ，另一类是宽0 5 6 m m ，制作两种类型的 托槽为配合相应规格的方弓丝所用。托槽的意义在于弓丝借助托槽对牙齿施以各 种类型的矫治力。托槽按照结扎丝沟形态可分为单托槽和双托槽。双托槽弓丝接 触面积大，同时又易于对扭转牙的矫正，因而广泛使用。 ( 3 ) l 矫治弓丝：矫治弓丝弹性好，多由不锈钢丝及钛镍合金丝等制成，若由多根 2 浙江大学硕士学位论文第1 章绪论 细的金属丝编织而成，则具有更好的弹性。 ( 4 l 末端颊面管：末端颊面管多数焊接在带环颊面，作用是使弓丝末端插入管内。 ( 5 l 其他附件：拉钩、舌侧牵引钩等。 1 2 计算机辅助技术在隐形牙齿正畸中的应用 由于传统矫治器存在不美观、舒适度差、根吸收等方面的不足，不少人放弃 了治疗，计算机辅助口腔正畸应运而生。计算机辅助口腔正畸软件首先由美国 a l i g n 公司开发出来，主要技术是计算机模拟矫治过程和批量生产无托槽隐形矫 治器。国内口腔正畸软件的代表是“北京时代天使 公司。目前，国内尚无其它 较知名的“口腔正畸 公司。所以该领域的研究在国内尚属起步阶段。 计算机隐形牙齿正畸技术的主要矫治原理有两个重要组成部分【2 j 。 第一，牙颌模型的数字化技术。它是整个矫治过程的基础，主要包括激光扫 描技术、层析扫描技术、c t 扫描技术。 第二，计算机辅助设计矫治过程。这是数字化口腔正畸流程的核心部分，计 算机辅助正畸牙齿的原始数据是数字化后的牙齿的三维网格模型。刚导入计算机 的模型是只有一些点、面信息。在口腔正畸的过程中，牙齿和牙龈的性质是明显 不一样的，正畸医生对牙齿和牙龈的操作显然也不一样，所以对导入的模型进行 牙齿、牙龈信息的分离。导入进的牙齿模型是一个三维网格模型，它是一个由点、 线、面构成的闭合三维空间区域，由于牙齿、牙龈的分离，会有网格信息丢失， 需要对牙齿、牙龈模型进行修补，即生成三角网格点、面信息。生成方法主要依 据实际牙齿的形态，结合图形学中成型的网格生成算法，修补信息。修补后的牙 齿、牙龈模型可能达不到正畸的要求，需要对模型进行变形和光顺处理。本文采 用旋转不变的拉普拉斯变形方法，对变形后的模型进行光顺处理。正畸主要就是 调整牙齿的实际位置，包括平移和旋转。无论是那种操作，都需要对牙齿个体空 间的运动方向加以确定，即对分离后的每一个牙齿，进行p c a 分析，确定牙齿的 以几何中心点为原点的三维直角坐标系和三个轴方向上的极值，即包围盒。为了 方便旋转操作，本软件为每个牙齿构建一个t r a c k b a l l 。t r a c k b a l l 以该模型的 3 浙江大学硕士学位论文第1 章绪论 几何中心为球心，以p c a 分析中三个主元中的最大值为半径构成的一个球体。 t r a c k b a l l 可以记录模型的旋转、缩放等信息。对牙齿模型经过一番处理之后， 运用已生成的牙齿、牙龈模型计算出分阶段矫治方案，根据矫治方案生成模型， 生成牙套进行矫治。本文重点阐述四个模块：“变形、“虚拟咬合、“平 面裁剪、“诊断 。 一“变形 在口腔正畸中起到了非常重要的作用，其目的是调整牙齿、牙 龈的形态。结合“光顺”算法，可以使牙齿、牙龈形态达到非常好的视觉效果。 实验中，可以通过程序画刷来选定需要变形的口腔区域，也可以用画刷擦除部分 变形区域，程序自动在最终的选定区域内确定要变形的点集。实验证明，该变形 方法快捷有效，通过“光顺”算法的完善，可以达到实际的要求。 二“虚拟咬合 是口腔正畸中非常重要的环节。导入计算机的上、下牙齿 三维网格模型在空间中的位置是相对独立的，矫治牙齿很重要的一个参数就是 上、下牙齿在咬合状态下的数据信息。咬合过程有三方面标准：准确、高效、直 观。本文采用i c p 算法，在保证模型间中心重合的前提下，在源和目标模型上交 互式选取多组对应点，根据每组对应点生成的法相间的夹角，旋转模型，使得上、 下牙齿模型和待对齐的侧扫描面模型粗略重合。i c p 算法保证，只要待对齐模型 间初始位置在一个合理的范围内都能达到一个最优的对齐效果【3 】。在匹配模型的 过程中，采用“空间剖分 对其进行加速，在目标模型上选取与源模型上每一个 顶点相匹配的对应点时，利用数据运算的可并行性，使用g p u 对其进行加速，大 大提高了程序的运行效率。o p e n g l 的渲染模式，使得模型间的位置关系，模型自 身的信息特点直观显示，b c g c o n t r o l b a r 的界面提供了方便快捷的平移，旋转等 交互式操作方式。 三“平面裁剪 模块提供了可交互的一个裁剪平面，剔除扫描进来的牙齿 模型中的多余网格数据，以平面为界限，保留平面侧的牙齿数据，剔除掉另一 侧牙齿模型数据。扫描进来的三维网格模型很可能包含多余的信息，有必要剔除 这部分信息，“平面裁剪 就是利用交互式的裁剪平面，确定裁剪平面与三维网 格模型的交点，通过交点确定出网格模型与平面相交的边界，进而实现多余信息 4 浙江大学硕士学位论文 第1 章绪论 的剔除。该算法可以适应多个不连续区域的模型，利用模型的拓扑关系，线性时 间完成。 四“诊断模块 在口腔正畸当中占有非常重要的地位，其目的是测量出牙 齿模型参数，牙齿模型参数对于精确地口腔正畸有非常重要作用。该模块提供了 牙齿模型的直观的o p e n g l 显示，同时提供了交互式确定牙齿模型上特征点的方 法，进而确定牙齿的各种特征参数。 浙江大学硕士学位论文第l 章绪论 1 3 本章小结 计算机辅助口腔正畸是一项结合了生物学、医学、计算机科学等学科的交叉 技术。在进行数字化正畸的过程中，不能单凭数学关系进行矫治，一定要以医学 和生物学的知识做依据，这样才能真正达到高效、准确辅助正畸的效果。 本章主要介绍了计算机辅助正畸的流程，从原始的导入数据，中间牙齿模型 的处理，一直到最后导出模型。 重点介绍了变形、虚拟咬合、平面裁剪、诊断四部分功能模块。这四部份可 以说是口腔正畸中的核心模块。 变形的对象的牙齿和牙龈，在进行牙齿模型处理的过程中，难免要破坏一些 导入模型的原始信息，同时要根据经验重构一些模型信息，这些丢失的信息和人 为重构的信息势必会使得牙齿和牙龈的形状发生与实际不符的情况。这就是引入 变形算法的必要性，也说明了变形在整个流程的过程中的重要性。本文采用旋转 不变拉普拉斯变形算法，运用稀疏矩阵进行加速运算，达到了保特征、高效的双 重效果。最后，采用光顺算法对牙齿形态进行微调。 虚拟咬合的对象是导入模型的上、下牙模型和参考模型，目的是使上、下牙 模型达到一种正常咬合的状态，以便提取咬合状态下的参数信息。本文采用的基 于i c p 的算法保证了虚拟咬合的准确、高效、直观。特别的，针对i c p 算法中最 费时间的寻找最近匹配点部分，运用g p u 的并行性，采用支持c 语言的c u d a 架构进行加速，在保证对齐效果的前提下，极大地提高了运行效率。 平面裁剪算法的时间复杂度为o ( f a c e n u m ) ，f a c e n u m 为模型面片的数量。 本算法可以适应含有多个不联通区域的模型。 诊断模块运用m f c 框架结合o p e n g l 三维图形渲染，为程序提供了方便友 好的交互式界面操作。 总之，本文为计算机辅助牙齿正畸提出了四个核心功能，为整个数字化正畸 流程的建立奠定了坚实的基础。 6 浙江大学硕士学位论文 第2 章牙齿变形 第2 章牙齿变形 2 1 变形理论背景 对模型的表面编辑操作研究已有很多【3 - 9 ，从交互式控制方式的角度，也已有 较多研列1 5 】【16 】【1 弧1 8 】【1 9 】【2 0 1 。从程序界面角度，模型表面编辑应提供便于操作的交 互式接口【1 0 】【l l 】【1 2 】【1 3 】【1 4 1 。从算法角度，模型表面编辑应保持源模型的表面特征 【2 1 】【2 2 】【2 3 】【2 4 】【2 5 】。多分辨率方法将模型表面特征分解为多个频率带【2 7 1 ，很好地保持 了模型的表面特征。常见的多分辨率方法将模型的表面特征分为两个频率带，基 本的光顺模型和带有细节特征的模型【2 8 】【2 9 1 ，后来的方法不是显式的设置两个频率 带，而是通过保持模型本身的一些差分属性【2 6 】【3 0 1 ，如拉普拉斯差分坐标、三角网 格坐标函数的梯度等来实现模型表面编辑。但上述的多分辨率方法不能很方便的 解决模型的旋转不变性。s h e f f c ra n dk r a e v o y t 3 1 】使用金字塔坐标保证了旋转不变 性，但算法的运行时间为非线性。y a r o nl i p m a n 3 2 】等提出了线性时间复杂度的旋 转不变性算法。 本文采用旋转不变的l a p l a c i a n 算法对源模型进行变换，该方法兼具平移不变 性和旋转不变性的双重优点。 变形的操作对象是三维网格模型，设该模型的表示为( k ，矿) ，其中k 描述了 模型的连通性，v = v l ，1 ，。) 描述了模型几何信息。 首先，算法采用了模型的相对坐标，即拉普拉斯坐标。对输入进来的三维网 格模型中变形区域内的点集构建相对应的差分坐标集合，见公式( 2 1 ) 。点表 示点f 对应的差分坐标，该坐标通常定义为该点笛卡尔坐标减去相邻点坐标和的 平均值。见公式( 2 2 ) 。m 表示与舛目邻的所有点的集合，d ，表示点f 的度。这样 可以构造一个方程组，方程组的左侧为变形区域内所有点的差分坐标构成的集合 ，方程组的右侧由两个部分组成，变形区域内的点集矿，和度数关系矩阵。l 为一个以变形区域内点构成的一个方阵，矩阵的第f 行和第，列代表第i 个点和第 7 浙江大学硕士学位论文第2 章牙1 旨变形 ，个点的相邻关系，如果江，则相应的位置为1 ；如果f ! = 歹并且f 与相邻，则 相应位置为一1 反。这样就可以构造出公式( 2 3 ) 至公式( 2 5 ) 。在公式( 2 4 ) 中，彳为关系矩阵，j 为单位矩阵，d - 1 为d 的逆矩阵。在公式( 2 3 ) 中，如果 将矿替换为y 7 ，y 7 为经过拉普拉斯变换后的点构成的集合，我们认为变形前后点 的差分坐标保持不变，这也是拉普拉斯变形的主要的思想。由于和已知，这 样就可以求出y ，即最终要求的点的集合。可以证明为以一1 阶的矩阵，所以只 要固定其中一个点变化后的位置就可以求出唯一一个变换后点集。在给出多个点 变化位置的情况下，最小化公式( 2 6 ) ，就可以得到保证平移不变性的点集。 a = 点公式( 2 1 ) 磊- - - - v i = o a , ) y v j 公式( 2 2 ) j 毛m a = l v = ，一d 一1 彳 d = a i a g ( a , ，以) e ( v 7 ) = i i 巧- 4 ，1 1 2 + i i 巧一1 1 2 i = li = m 公式( 2 3 ) 公式( 2 4 ) 公式( 2 5 ) 公式( 2 6 ) 在公式( 2 6 ) 中，4 为变形前点的差分坐标的集合，彰为变形后点的差分坐 标集合。t 定义见公式( 2 7 ) 。l g i 和为在变换前后保持固定的点。如果要保证 平移、旋转的不变性，可以证明，只要在谚前乘以一个旋转变换i 。经证明t 是 关于v 的函数，可写作z ( y 7 ) 。求解变换后的点集y ，则要最小化公式( 2 8 ) 。 其中，z ( y ) 是y 7 的线性函数。具体形式见公式( 2 9 ) 。乃中的变量只有7 个，可 以将其中的变量其写成列向量的形式( s ，曩，) r ，其中f 1 2 3 ) ，求解( 5 ，h ，t ，) r 需要最小化公式( 2 1 0 ) ，公式( 2 1 0 ) 中a ，定义如公式( 2 1 1 ) ，b i 定义见公式 ( 2 1 2 ) 。在公式( 2 1 1 ) 和公式( 2 1 2 ) 中，m 表示顶点f 邻域中的点集，七表示 顶点f 和与其相邻点的集合中的元素。( s ，h ，t ，) r 即t 可表示成矿7 的函数，见公式 ( 2 1 3 ) 。结合公式( 2 8 ) 和公式( 2 1 3 ) 可以求出最终的变形后点集y 7 。 8 浙江大学硕士学位论文 一= i ，f 聊，l ，删 以 e ( y ，) = i it ( v 7 ) 4 - 4 ，1 1 2 + i lv ，一“川2 = 陲 is i 霉- - t 色 l 一也 l0 a i ( s , ，忽，) r 一6 f1 1 2 目吲刈m ( s i , h i ，) 7 = ( 4 t 4 ) 卅g o , 9 第2 章牙齿变形 公式 公式 ( 2 7 ) ( 2 8 ) 公式( 2 9 ) 公式( 2 1 0 ) 习，后u m 公式q j 。 公式( 2 1 2 ) 公式( 2 1 3 ) 、， 乞如1 吃叫j o _ 魄so山s 啊o o 1 o l 0 0 飞k o k o叱一 o ，b o 叫 咋 一 浙江大学硕士学位论文第2 章牙齿变形 2 1 1 变形算法在计算机辅助隐形牙齿正畸中的应用 计算机辅助正畸过程中，对牙齿的变形操作必不可少。计算机导入的是由扫 描设备扫描得到的三维网格模型。受扫描精度和扫描范围的限制，导入的模型难 免有些失真，特别是经过分离牙齿、牙龈信息之后，局部形状多数会造成与实际 牙齿、牙龈形态不符合现象。通过交互式的变形操作，使牙齿恢复到正常牙齿形 态是非常必要的。 导入的牙齿模型信息只具有一些点、面信息，需要对其进行拓扑重构。 半边结构是表示三维网格模型的常用方法，该结构中含有对应的点、边、面 信息，通过遍历该结构构成的集合可以很方便地访问网格中的每一组的点、边、 面信息。本算法采用另外一种数据结构。该数据结构主要包含两个类，t o p o l o g y 和p o s 。t o p o l o g y 类的主要作用构建点与面间的拓扑关系，p o s 类主要提供了一 些拓扑遍历操作。 t o p o l o g y 先构造共点的面面关系。遍历模型的所有三角面片的所有顶点，如 果第一次遍历该点所在的面，则令该面作为共该点的首面，对于后来遍历到的共 该点的所有面，依次作为第二、第三、第刀个面。在构建了共点面面关系的 基础上，再构建共边面面关系。首先，遍历当前模型的所有面，对每一面的三条 边进行压栈操作。其次，遍历该栈中的每一条边。最后，取每一条边中的一个顶 点，遍历共该顶点的所有面，如果当前面中的其余两个顶点有一个为当前边的另 外一个顶点，则将该面加入共该边的链表，同时标记该边，表示已经处理过。如 图2 1 。 p o s 主要提供了一些拓扑遍历操作。可看作是遍历三角网格时的“位置 信 息，包含一组点、边、面，通过该结构可以沿边界遍历，按任意条件访问局部拓 扑结构。此外该类还定义了判断点面是否为流形，面法向是否正确等功能。 整个变形算法流程分为以下几个部分。 一通过交互式操作选定变形区域，在变形区域范围内选定h a n d l e 点范围，注 意h a n d l e 点一定要在整个变形区域的内部。对所选的变形区域内的所有点、面加 以标识。对h a n d l e 点范围加以特殊标识。在整个变形操作的过程中，变形区域的 1 0 浙江大学硕士学位论文 第2 章牙齿变形 图2 1 共边面面关系的建立 点分为三类。h a n d l e 点、a n c h o r 点、f r e e 点。h a n d l e 点变形后的位置由交互式 拖动确定，h a n d l e 点集为整个变形区域的真子集。变形区域边界的点构成a n c h o r ， a n c h o r 点变形前后位置不变。变形区域内，h a n d l e 点和a n c h o r 点之间的所有点 构成f r e e 点，这部分点的最终位置由变形计算得出。根据实际的需要对a n c h o r 点的边界圈数进行适当的增减。本算法对选取的变形区域边界进行三至四圈的扩 充，将最后外围的四圈点作为最终的a n c h o r 点集。将变形区域所有点，h a n d l e 点，a n c h o r 分别保存。 二变形操作的预计算。因为对变形区域内的点来讲，点与点间的处于相邻关 系的毕竟是少数，所以在构造关系矩阵l 时，会造成很多元素所在位置为零。这 样的矩阵运算会带来不必要的开销。我们采用系数矩阵存储数据，在该数据结构 中，主要有三个参数：1 矩阵非零元素构成的一维数组。2 行首非零元素在一 维数组中的索引。3 与一维数组相对应的每个非零元素所在的列索引。首先，计 算变形区域内每一顶点的拉普拉斯坐标。遍历当前变形区域内的每一顶点，遍历 共该点的每一个面，清空面上每一点的访问标识位。设置当前顶点标志位。其次， 遍历共该点的每一面，如果该面上的顶点未被访问过，则设置该点的访问标识， 累加计算拉普拉斯坐标。再次，计算矩阵。设置矩阵的维数，行为3 宰( 所有顶点 数+ a n c h o r 点数+ h a n d l e 点数) 。乘以3 的目的是同时运算x 、y 、z 三个坐标。将点 浙江大学硕士学位论文 第2 章牙齿变形 分三类添加到矩阵三中，第一类，变形区域内所有点，按照计算所得的拉普拉斯 坐标逐行填入系数矩阵中。第二类，h a n d l e 点，该点对应的位置填入1 。第三类， a n c h o r 点，该点对应位置填入l 。最后，将得到的矩阵调用s u p e r l u 计算。s u p e r l u 【3 3 1 是用来计算形如a x = b 稀疏线性方程组。s u p e r l u 分为三个类型的库，串行、并 行、分布式。串行s u p e r l u 库主要适用串行方式单处理器形式的程式。并行s u p e r l u 库主要适用于多处理器下的情况。分布式s u p e r l u 适用于大规模的分布式处理器 情况下的矩阵方程求解。s u p e r l u 总体思想采用高斯消去法求解。求解过程分为 两步。1 三角化操作。将待求解的矩阵a 进行如下分解：a = l u = p r d r a d c p c ，其 中a = l u = p r d r a d c p c 中，p ，、p c 互为转置，d ，、d c 对角矩阵。2 求解过程用 d c r e a r e和 ) 设置矩阵a 和b 。用c o m p c o ! m a t r i x ( ) d c r e a t e d e n s em a t r i x ( s e t _ d e f a u l t _ o p t i o n s 0 设置缺省的输入选项参数。用s g s t m ) 对矩阵a 进行l u 分解。 三根据交互式确定h a n d l e 点的最终位置，求解最终点的坐标。整个流程如 图2 2 所示。 ”交互式操作选定变形区域 一i 一 “ 一”、。一”+ 一i 一 图2 2 变形算法流程 1 2 浙江大学硕士学位论文第2 章牙齿变形 2 1 2 光顺算法在计算机辅助隐形牙齿正畸中的应用 变形后的牙齿可能在局部有一些不符合实际牙齿状态的情况。光顺算法可以 很好的解决变形后牙齿形态的问题。经典的光顺算法有拉普拉斯光顺法t 3 4 ，双边 滤波算法【3 5 1 ，双步滤波【3 6 1 算法。 本文采用了基于拉普拉斯的算法和基于双步滤波算法的两种光顺方法。 拉普拉斯光顺算法流程如下。根据预先设定的算法迭代次数，进行循环遍历， 在每一步的遍历过程中，先对所有点的参数进行初始化。再遍历每一个点，遍历 共该点的所有面，累加该面中的三个点的坐标到当前点，同时累加计数。在遍历 了所有的点之后，用当前点的坐标除以累加器的次数即是当前点本次遍历的新坐 标值。算法流程如图2 3 所示。 图2 3 拉普拉斯光顺算法流程 双步滤波：第一步，对三角面片的法向量进行光滑操作。第二步，根据法线 光顺结果对顶点位置进行更新以逼近法线结果。该光顺方法在去噪和保特征方面 都有较大的优势。本文采用的双步滤波算法流程如图2 4 所示。 1 3 浙江大学硕士学位论文第2 章牙齿变形 图2 4 双步光顺算法流程 1 4 浙丈学硕学位论立 第2 章牙* 变形 2 2 本章小结 在计算机辅助牙齿正畸中，变形是保证处理后牙齿保持正常形态的必要条 件。本文采用的基于旋转不变的拉普拉斯变形方法，在实现的过程中，针对牙齿 这一特定的三维模型，提供了交互式选取变形区域，h a n d l e 点区域，程序自动增 加a n c h o r 点的圈数，计算的过程中采用了稀疏矩阵，提高了运算效率，节省了 存储空间，调用s u p e r l u 求解最终的方程组。为了弥补变形后效果的一些不足， 提供了拉普拉斯光顺和双步光顺的算法，用户可根据实际情况进行选择，牙齿需 要调整的形卷很小时，可选择拉普拉斯光顺，如果需要调整的程度稍大，则可选 择两步光顺它是一种保特征的光顺方法。 本实验数据是在l a t e lc o r e 2d u oe 7 4 0 0 ，w i n d o w s 73 2 位操作系统上运行。界 面框架由b c g c o n t r o l b a r 搭建，运用o p e n g l 进行三维模型渲染。程序的 整个运行结果如图2 5 - 图2 l l 。观察图25 和图2 7 ，可以看出变形后牙齿的表面 形态更加光滑。图2 8 和图2 9 显示采用双步光顾前后牙齿表面形状的变化，变 形前牙齿表面突起很明显，变形后，突起明显退化，牙齿表面趋于平滑。图21 0 和图2 1 1 显示了采用拉普拉斯光顺后的效果图，因为图2l o 的突起并不十分明 显，适合采用拉普拉斯光顺方法。光顺后表面趋于平滑。通过实验证明， 本文变形算法和光顺算法非常有效，满足口腔牙齿形态调整的实际要求。 图2 5 变形前牙齿形恋闰2 6 交互式选取变形区域 浙江大学碗学位论女第2 章牙齿变* 盯即 “一 一 ， 1 l 一二一 圈2 7 变形后牙齿形态图2 , 8 取步光顺前牙齿形态 r 1 田贾1 。一羔一。三 一盏 圈2 9 双步光顺后牙齿形态图21 0 拉普拉斯光顾前牙齿形 图21 1 拉营拉斯光顺君牙齿形态 浙江大学硕士学位论文第3 章虚拟咬合 第3 章虚拟咬合 3 1 虚拟咬合技术概述 虚拟咬合关键是对齐上、下颌模型。对三维模型的对齐方法的研究，主要分 为两种【3 刀。一种是高精度的对齐方法，它依赖对模型特征的提取；一种是低精度 的对齐方法，它只是依赖模型的部分点、面元素。迭代最近点算法是一种广泛流 行的低精度对齐方法。该算法主要是在待匹配的模型的元素集中，如点集间做迭 代逼近，直到符合精度要求。 虚拟咬合的最终结果需要有一个直观的显示，常采用碰撞检测技术，从实践 角度，碰撞检测技术分为全局和局部。局部碰撞检测又分为基于图形空间和基于 图像空间。基于图形空间的算法准确度高，可以很精确的表示模型间的碰撞检测 程度。 3 1 1i c p 算法概述 i c p 全称i t e r a t i v ec l o s e s tp o i n t ，即迭代最近点算法。它是一种迭代逼近的对 齐方法，在每一步的迭代过程中都涉及了很多影响迭代效果的因烈3 8 1 ，现将这些 因素归纳总结。 第一种因素，点集选择。在源模型和目标模型上选取点集，分以下五种：1 同时在源和目标模型上随机采样；2 同时在源和目标模型上采样点，运用匹配点 间的夹角筛选匹配点对；3 对所选点对加以常量权重；4 剔除点对中的边缘点 对和点对间距离大于阈值的点对；5 剔除到另一个模型对应三角面片的距离大于 阈值的顶点。 第二种因素，点对匹配。对选择来的两组点集进行匹配，分以下五种：1 寻 找模型间距离最近的点匹配；2 从源模型上每一个点，沿该点法向，与目标模型 的交点，在交点所在的三角形中寻找匹配点：3 从目标模型的角度，投影源模型 上的点到目标模型来查找匹配点；4 投影源模型上的点到目标模型，在目标模型 浙江大学硕士学位论文第3 章虚拟咬合 上查找距离该点最近的匹配点；5 根据其它特征，如点之间的法相夹角、颜色等 匹配。 第三种因素，点对加权。对点对加权，一方面可以剔除权重小于给定阈值的 点对；另一方面，该权重参与旋转矩阵和平移矩阵的运算，进而影响最终匹配效 果。大体上有四种方法：1 常值权重；2 根据距离的远近加权，距离越远权值 越小，反之，则越大；3 根据法相夹角加权，法相夹角越小权值越大，反之，越 小；4 点到对应点所在平面的距离加权，距离越小，权值越大；反之，越小。 第四种因素，点对剔除。剔除一些匹配点对，特别是边界轮廓线上的匹配点， 有时可以提高最终的匹配效果。总的来讲，有5 种常用的剔除算法：1 剔除相距 大于一定距离的点对；2 剔除匹配程度最差的1 0 的点对；3 剔除点对距离偏 差大于标准偏差一定倍数( 如2 5 ) 的点对；4 剔除点对距离偏差值相对于相邻点对 偏差过大的点对。5 剔除边界轮廓点。 第五种因素，误差计算方法。误差计算方法的不同直接影响到最终匹配的精 确程度和匹配的速率。大体有三种方法：1 加权求和所有匹配点对距离差值的平 方；2 对点对距离和颜色同时加权求和：3 加权求和点到匹配三角形的距离。 算法总体流程如图3 1 。 图3 1 迭代最近点算法 下面讨论算法收敛性。设集合p 第七次迭代表示为忍和集合】，( 排序后的集 浙江大学硕士学位论文第3 章虚拟咬合 合x ) 第k 次迭代表示为砭，在第k 次迭代，最小二乘距离以定义见公式( 3 1 ) 。 其中，p 为集合p 中点的数目。p 啦为第k 次迭代中集合尸中的第f 个点，y 耻为 第k 次迭代中集合y 中的第f 个点。在应用转换矩阵之后，模型间的最d , - 乘距离 见公式( 3 2 ) 。很容易看出e k 巩，因为e k 是经过转换后的点距离，一定比转换前 具有更接近的距离。在进行第k + 1