（计算机应用技术专业论文）不规则曲面相交算法的研究与实现.pdf

，。；。h，i 1j 。，_， i ；- ，l 、 、j t h - 一 学位论文数据集 中图分类号 t p 3 0 1 6 学科分类号 5 2 0 6 0 3 0 论文编号 1 0 0 10 2 0 1 1 13 7 2 密级公开 学位授予单位代码 10 0 1o 学位授予单位名称 北京化工大学 作者姓名黄松柏学号 2 0 0 8 0 0 13 7 2 获学位专业名称 计算机应用技术获学位专业代码 0 8 1 2 0 3 国家自然科学基金项 课题来源 研究方向计算机图形学 目北京市教委 论文题目不规则曲面相交算法的研究与实现 关键词 曲面相交，动态0 b b 层次结构，约束三角化，基于交线曲面优化 论文答辩日期 2 0 1 1 年5 月3 1 日t 论文类型应用研究 学位论文评阅及答辩委员会情况 姓名职称工作单位学科专长 指导教师 徐华教授北京石油化工学院三维建模，可视化 评阅人1朱群雄教授北京化工大学控制科学与工程 评阅人2张国英副教授中国矿业大学( 北京)智能系统与模式识别 评阅人3 评阅人4 评阅人5 徽员糊朱群雄教授北京化工大学控制科学与工程 智能检测与自动化装 答辩委员1戴波 教授北京石油化工学院 置 答辩委员2刘建东 教授北京石油化工学院 信息安全 答辩委员3林小竹 教授北京石油化工学院 信号处理与图像识别 牵引供电系统故障检 答辩委员4李夏青 教授北京石油化工学院 测 答辩委员5 征：一 四 论文类型：1 基础研究2 应用研究3 开发研究4 其它 中图分类号在中国图书资料分类法查询。 学科分类号在中华人民共和国国家标准( g b t1 3 7 4 5 9 ) 学科分类与代码中查 询。 论文编号由单位代码和年份及学号的后四位组成。 t l 一 ，1 - j 摘要 不规则曲面相交算法的研究与实现 摘要 曲面相交算法是计算机辅助几何设计中的一个重要研究课题，是 用计算机及其图形工具表示、描述物体形状和设计几何实体，模拟物 体动态处理过程的一门综合技术。算法有各自的应用环境，各有侧重 和优缺点。为使曲面算法的性能满足实际系统的需要，需要在效率和 稳定性上进一步的研究。 本文首先对国内外参数曲面相交和非参数曲面相交研究状况进 行简要介绍。非参数曲面相交区域获得一般采用碰撞检测方法，通过 分析对比常用的包围盒的特点以及已有碰撞检测算法，提出一种高效 快速的基于o b b 动态层次结构碰撞检测算法；其次，相交区域的相 交三角形位置和形态各异，通过分析可能出现所有三角形相交情况， 采用一种高效稳定的交点计算方法。交线构成是曲面相交的重点之 一，运用合理的数据结构获取符合实际相交的交线以及可能出现的孤 立点。在计算出交点和交线后，利用分治三角化算法以三角形为单位 进行三角化。同时由于短交线的存在，三角化后会出现窄小的三角形， 为使曲面重构后三角形较均匀，提出以基于交线平均长度的方法去除 窄小三角形。在曲面被切割后，会出现空洞，使曲面保持封闭性，以 相交的3 d 交线进行三角化，同时为便于相交后曲面的布尔操作，移 动和删除等操作，需将曲面以交线为边界将曲面分块。 通过实验的验证和分析以及在地质矿体可视化应用系统的运用， 北京化丁人学硕i j 学位论文 证明算法在效率和稳定上得到了提高，同时可以运用于地质矿体， c a d 等领域。 关键词：曲面相交，动态o b b 层次结构，约束三角化，基于交线曲 面优化 i i 一 ： 产 a b s t r a c t r e s e a r c ha n di m p l e m e n t a t i o n0 fi r r e g u l a rs u r f a c e i n t e r s e c t i o na l g o r i t h m a b s t r a c t s u r f a c e s u r f a c ei n t e r s e c t i o n ( s s i ) a l g o r i t h mi so n eo fi m p o r t a n t r e s e a r c ht o p i co fc o m p u t e ra i d e dg e o m e t r i cd e s i g n ( c a g d ) ，i ti sa n i n t e g r a t e dt e c h n o l o g yt h a tu s ec o m p u t e ra n dg r a p h i ct o o lt od e s c r i b et h e s h a p eo fo b i je c t ，t od e s i g n t h eg e o m e t r i ce n t i t i e sa n dt os i m u l a t et h e p r o c e s s i n gp r o c e d u r eo fo b l j e c t s d u et ot h ed i f r e r e n ta p p l i c a t i o no ft h e a l g o l l i t h m ，e a c hh a st h e i ro w np o i n t st o f o c u s i no r d e rt om e e tt h e p e r f - o m a n c en e e d so fa c t u a la p p l i c a t i o n ，t h i sp a p e rc o n t i n u et ow o r ko n t h ea l g o r i t h me m c i e n c ya n ds t a b i l i t y f i r s t l y ；t h i sp 印e ri n t r o d u c e st h eg e n e r a ls i t u a t i o no fr e c e n td o m e s t i c a n di n t e m a t i o n a lr e s e a r c hr e s u l t so fp a r a m e t r i ca n dn o n - p a r a m e t r i c s u r f a c ei n t e r s e c t i o na l g o r i t h mb r i e f ly c u n i e n t l ya l g o r i t h mu s ec o l l i s i o n d e t e c t i o nt og e tt h ei n t e r s e c t i o na r e a s a r e ra n a l y s i st h ec h a r a c t e r i s t i co f m u s hu s e db o u n d i n gb o x e sa n dp i e v i o u s l yc o l l i s i o nd e t e c t i o na l g o r i t h m s ， u s i n gam o r ee m c i e n c yd y n a m i ch i e r a r c h yc o l l i s i o nd e t e c t i o na l g o r i t h m b a s e do n0 e ；bt og e ti n t e r s e c t i o na r e a s ；t h ep 印e rs u m su pa l lp o s s i b l e t n a n g l ei n t e r s e c t i o ns i m a t i o n sa n da d o p ta ne x c e l l e n tw a y t oc o m p u t et h e i n t e r s e c t i o np o i n t s i n t e r s e c t i o nl i n e sf o m l i n gi so n eo ft h ei m p o r t a n t w o r k so fs s i ，u s et h ed a t as t r u c t u r et og e ta c m a l l yi n t e r s e c t i o nl i n ea n d i 北京化工人学硕i ：学位论文 p o i n t s a r e r t h a t ， u s e d i v i d e c o n q u e rt r i a n g u l a t i o na l g o “t h m t o t r i a n g u l a t e i n t e r s e c t i o n t n a n 9 1 eo n eb y o n e b e c a u s eo ft h ec l o s e i n t e r s e c t i o np o i n t sa n dl i n e s ，t h en a n o w t r i a n 9 1 e w i l l a p p e a r a r e r t r i a n g u l a t i o n ，o p t i m i z et h er e c o n s t m c t e ds u r f a c e sb a s eo nt h ea v e r a g e l e n g t ho fi n t e r s e c t i o nl i n e s t r i a n g u l a t et h e3 d i n t e r s e c t i o n1 i n e s 仔o mt h e s u r f a c eb e e nc u t s e p a r a t et h es u r l a c eu s e si n t e r s e c t i o nl i n ef o rd e l e t e ， m o v ea n db o o l e a no p e r a t i o nc o n v e n i e n c e t h ee x p e r i m e n tr e s u l t s ，a n a l y s i sa n da p p l i c a t i o no fg e o l o g i c a l o r e a n a l y s i ss y s t e mv e r i 矽t h ee f ! f i c i e n c ya n ds t a b i l i t yo fa l g o r i t h m s ，a n dc a n b ea p p l i e dt ol o t so ff i e l d s k e y w o r d s ：s u r f a c e s u r f a c e i n t e r s e c t i o n ，d y n a m i c o b b h i e r a r c h ya l g o r i t h m ， c o n s t r a i n e d t r i a n g u l a t i o n ，0 p t i m i z e ， s u r f a c e 0 p t i m i z eb a s e di ni m e r s e c t i o n1 i n e 1 目录 目录 第一章绪论1 1 1 论文背景及其研究意义1 1 2 国外研究现状2 1 3 国内研究现状3 1 4 曲面相交的应用4 1 5 本文主要工作与创新点5 1 6 本章小结6 第二章曲面相交算法总体设计7 2 1 总体设计7 2 2 算法流程8 2 3 本章小结 9 第三章基于动态o b b 层次结构碰撞检测算法1 1 3 1 碰撞检测的概念1 1 3 2 现有碰撞检测分析1 2 3 3 层次结构包围盒1 3 3 3 1 包围球一1 3 3 3 2 沿坐标轴包围盒1 4 3 3 4 沿坐标轴包围盒1 5 3 3 5 包围盒比较1 5 3 4 动态o b b 层次结构算法1 6 3 4 1o b b 计算理论1 6 3 4 2o b b 碰撞检测l8 3 4 3 相交三角形检测2 0 3 4 4 动态o b b 层次结构算法具体步骤2 l 3 4 5 动态o b b 层次结构算法理论分析2 3 3 4 6 算法设计与实现2 6 3 5 本章小结2 8 v 北京化t 大学顾t ：学位论文 第四章曲面三角形交点计算及重构2 9 4 1 相交三角形计算方法2 9 4 2 异面三角形计算3 0 4 3 共面三角形计算3 3 4 4 三角形交点计算健壮性分析3 5 4 53 d 闭合交线三角化3 6 4 6 曲面交线构成3 8 4 7 三角形曲面重构3 9 4 7 1 三维坐标向二维坐标转换方法4 0 4 7 2 三角形曲面重构方法4 1 4 8 优化三角形4 2 4 9 曲面分块4 5 4 1 0 本章小结4 6 第五章算法应用与分析4 9 5 1 图形可视化4 9 5 2 曲面相交算法应用实例4 9 5 3 地质矿体中复杂曲面分析5 2 5 3 1 应用环境简介5 2 5 3 2 复杂曲面相交分析5 3 5 3 3 应用于地质矿体5 4 5 4 本章小结5 5 第六章结论和展望5 7 6 1 结论5 7 6 2 展望5 7 参考文献5 9 致谢 。6 3 研究成果及发表的学术论文6 5 目录 作者和导师简介。6 7 北京化t 人学硕i ：学位论文 v i i i - 厂 c o n t e n t s co n t e n t s c h a p t e r li n t r o d u c t i o n 。1 1 1r e s e a r c hb a c k 孕0 u n da j l ds i g n i f i c a n c eo fm e s i s 1 1 2i n t e m a “o n a lr e s e a r c hs t a t u s 2 1 3d o m e s t i cr e s e a l hs t a t u s 3 1 4a p p l i c a t i o no fs u i f a c e s u r f a c ei n t e r s e c t i o n 4 1 5m a i nr e s e a r c hc o n t e n t s 5 】6r e v i e w 6 c h a p t e r 2o v e r a ud e s i g no fs u r f a c ei n t e r s e c t i o na i g o r i t h m 7 2 10 v e r a l ld e s i 盟o fa l g o r i t h m 7 2 2a l g o r i t h n lf l o wd i a 铲锄：8 2 3r e v i e w 9 c h a p t e r 3d y n a m i ch i e r a r c h ya l g o r i t h m b a s e do no b b 。1 1 3 1t h ec o n c 印to f c o l l i s i o nd e t e c t i o n 1 1 3 2t h ee x i s tc o l l i s i o nd e t e c t i o na l g o 曲t ma 1 1 a l y s i s 1 2 3 3h i e r a r c h yb o u n d i n gb o x 13 3 3 1s p h e r e 13 3 3 2a a b b 1 4 3 3 4o b b 15 3 3 5c o m p a r i s o no f b o u n d i n gb o x 15 3 4d y i l 锄i c1 1 i e r a r c h ya l g o r i m m 1 6 3 4 1o b b c o m p u t a t i o nt h e o r y 1 6 3 4 2o b bc o n i s i o nd e t e c t i o n 18 3 4 3t r i a n g l ei n t e r s e c t i o nt e s t 2 0 3 4 4s t e p so f o b bk e r a r e h ya l g o r i m m 2 l 3 4 5t h e o r e t i c a la n a l y s i so fo b bh i e r a r c h ya l g o r i t l l i n 2 3 3 4 6 甜g o r i t h md e s i 盟a n di i l l p l e m e n t a t i o n 2 6 3 5r e v i e w 2 8 北京化工人学硕卜学位论文 c h a p t e r 4t r i a n g l ei n t e r s e c t i o nc a l c u l a t i o na n d s u r f a c er e c o n s t l l j c t i o n 2 9 4 1t r i a n g l ei n t e r s e c t i o nc a l c u l a t i o n 2 9 4 2u n c o p l a n a rt a j l 9 1 ec a l c u l a t i o n 3 0 4 3c o p l a j l a rt r i a n 百ec a l c u l a t i o n 3 3 4 4r o b u s t n e s so ft h et r i a n g l ei n t e r s e c t i o nc a l c u l a t i o n 3 5 4 53 df o 肌s u r f - a c ei n t e r s e c t i o nl i n e 3 6 4 63 dc l o s el i n et r i a n g u l a t i o n 3 8 4 7r e c o n s t n l c ts u r f a c e 3 9 4 7 13 dc o o r d i n a t e st o2 dc o o r d i n a t e st r a n s f o 肌a t i o nm e t h o d 4 0 4 7 2l e m o do fs u r f a c er e c o n s t m c t 4 1 4 8r e c o n s t l l l c t s u r f a c eo p t i m i z e 4 2 4 9s o r ts u a c e 4 5 4 1or e v i e w 4 6 c h a p t e r5a p p l i c a t i o na n da n a l y s i so fa l g o r i t h m s 4 9 5 1g r a p hv i s u a l i z a t i o n 4 9 5 2a p p l i c a t i o ns u r l a c ei n t e r s e c t i o na l g o r i t h m 4 9 5 3c o m p l e xs u r f a c ea 1 1 a l y s i so fg e o l o g i c a lo r e 5 2 5 3 1a p p l i c a t i o ne n v i r o 彻 1 e 1 1 t 5 2 5 3 2a n a l y s i so fc o m p l e xs u r f a c ei n t e r s e c t i o n 5 3 5 3 3u s e di ng e o l o 百c a lo r e 5 4 5 4r e v i e w 5 5 c h a p t e r6c o n c l u s i o na n dp r o s p e c t 。5 7 6 1c o n c l u s i o n 5 7 6 2p r o s p e c t 5 7 “ r e f b r e n c e 。5 9 气 t h a n k s。6 3 r e s e a r c hr e s u l ta n dp u b l i s ht h e s i s 。6 5 x c o n t e n t s a u t h o ra n d1 u t o r sp r o f i l e 。6 7 北京化工人学硕一l ：学位论文 ， 第一章绪论 1 1 论文背景及其研究意义 第一章绪论 计算机已经对社会发展，科技进步和人类生活和学习产生深远的影响，同时 也已经成为快速、经济地生成图形图像的强大工具。计算机图形学发展至今已 有4 0 多年的历史，其中2 0 世纪8 0 年代到9 0 年代是计算机图形学蓬勃发展的 黄金时期。随着计算机图形硬件和软件快速发展，可以看到计算机图形学已经应 用于多种领域，如图形和精细艺术、工程、商务、工业、医药、政府、娱乐、广 告、教学、培训和家庭等各个方面的应用。 曲面相交( s u 渤c e s u 渤c ei n t e r s e c t i o n ，s s i ) 算法是计算机辅助几何设计 ( c o m p u t e ra i d e dg e o m e t r i cd e s i 印，c a g d ) 中的一个重要的研究课题，是用计算 机及其图形工具表示、描述物体形状和设计几何实体，模拟物体动态处理过程的 一门综合技术。其理论和应用技术在最近十几年已经取得了巨大的进步，应用于 多个领域，如地理信息系统、科学计算可视化、地质建模、虚拟现实、曲面造型、 实体造型、机器人运动规划、工程机械、计算机视觉等领域有着广泛的应用。按 s s i 算法处理的对象不同可以分为参数曲面相交算法和非参数曲面相交算法。到 目前为止，具体的s s i 算法可以分为：几何分割法、代数迭代法、跟踪法、网格 法、解析法和三角法【l 之】。每种方法有其适用范围和优缺点，由于算法有各自的 应用环境，各有侧重，都没有解决好精度和速度问题。其中参数曲面相交的研究 开始与6 0 年代，由于产业的推动，研究成果丰富，如基于n u i s 曲面【3 j ，基 于b 6 z i e r 曲面【4 。5 1 的参数曲面相交算法等，同时也成功地应用于很多的商业化软 件中，如3 d m a x 、m a y a 、c a t i a 、i 也i n o c e r o s 等。非参数曲面，即不规则曲面， 主要的具有拓扑结构的由简单几何面片( 如三角形、四边形等) 构成的网格曲面， 一般来自采集来的数据，这类曲面千变万化，一般不能由简单数学关系进行表达， 可以表示形状复杂的真实曲面。在三维地质模型、虚拟现实等领域中，基于三角 形的不规则曲面相交算法的研究已经相当活跃，法国地理处理i m i n ot c ：玎a i n 软件 就集成了不规则曲面相交算法。 现有的曲面相交算法，各有侧重，适用的范围也各不相同，在算法的效率， 稳定性以及功能上都需要进行进一步的研究。曲面算法应用广泛，随着计算机软 件和硬件的发展和变化以及新的实际应用环境的需要，现有的算法表现出了一定 的局限性。s s i 算法国外研究已经非常成熟和先进，商业化软件和设备已经占据 了国内绝大部分市场，广泛应用于建筑设计、工业、军事、地理地质、艺术、医 学等领域，国内研究已经处于劣势地位，没有应用广泛技术成熟的软件产品，故 深入研究具有积极意义。 北京化t 大学硕l ：学位论文 本论文研究内容来源于国家自然科学基金项目虚拟水文地质环境中基于拓 扑变换的三维动态可视化建模研究和北京市教委科技发展计划项目地下水三 维动态模拟与可视化研究。文章围绕如何提高算法的效率，稳定性和准确性以 及功能通用性的要求，首先研究现有的基于包围盒碰撞算法的技术上，提出新的 高效碰撞检测算法获得相交区域；然后利用设计的数据结构稳定计算相交三角形 的交点以避免浮点数比较，构成与逻辑情况一致的交线；最后重构相交区域的三 角形，三角化3 d 闭合交线，优化相交重构的区域，同时以交线为边界将曲面分 块。 1 2 国外研究现状 s s i 算法应用广泛，国外的论文专著、专利、商业化软件和设备已经非常丰 富。曲面相交，以获得交线是主要目的，或以获取交线便于其他操作为目的，如 复杂物体设计的表现、计算机动画、数控加工、曲面裁剪和布尔运算等操作。在 计算机中，曲面表现方式多样，其中最主要应用最广泛的曲面相交算法包括参数 曲面和非参数曲面： 参数曲面还包括隐式曲面，都可以精确表示曲面形态，同时因为参数曲面的 控制点可以由用户控制和输入，可以方便的使用交互式方式进行参数化设计。在 计算机图形学中，参数曲面的形式最灵活。参数曲面仍然使用欧几罩德空间 的坐标系表示，没有完全消除与特定坐标系的依赖关系。参数曲面相交算法包括： 参数曲面与参数曲面相交，参数曲面与隐式曲面相交以及隐式曲面与隐式曲面相 交。1 9 6 5 年，s o u t h 和k e l l y 在双三次曲面片等高线上使用网格计算相交i 6 | 。1 9 8 4 年，s e d e r b e r g 和o w e n 等采用将隐式曲面方程转化为代数方程，然后用求解代 数方程的方法进行相交计算【。1 9 9 1 年，d i n e s hm a n o c h a 和j o h ef c a n n y 提出 了投影方法由高维参数曲面转化为低维曲面来计算相交结果【8 】。1 9 9 7 年n w c h o 和n k 鼬m 等提出了基于遗传算法的曲面相交算法( s u f f a c ei n t e r s e c t i o n w i t hg e n e t i ca l g o r i t l l i l l ，s i g a ) ，优点在于可以保证s i g a 以较高的概率和效率 获得所有的交线【9 1 。1 9 9 9 年，x i u z iy e 和t a k a s h im a e k a w a 计算曲面相交时的常 见的问题几何属性【l o 】。2 0 0 8 年，k h k o 和n m p a t r i k a l a h s 针对曲面相交时边 界错误提出了新的方法来减少这些问题【l 。对于应用较多的b 6 z i e r 曲面，均匀b 样条曲面和非均匀b 样条曲面，l 觚e 和r i e s e i l f e l d l l 2 j ，c o h e i l 和l ) ，c h e 【乃j ，m a z i z 和r e d a b a 【1 4 j 从不同的方向做出了研究和改进。 非参数曲面则是由简单的基本几何面片组成的曲面，如三角形网格曲面，四 边形网格曲面，六边形网格曲面等，其中四边形网格曲面和六边形网格曲面都可 以转换成三角形网格曲面进行处理。基本几何面片数学表达式简单，便于计算机 2 、 ， 第一章绪论 存储，处理和绘制。一个不规则的三角形网格曲面m e s h 可以通过一个二元组来 表示( 曲面有以个点，个三角形) ：m e s h = ( v ，t ) ，其中v = v i ) ，i = 0 ，l ，2 ，咒1 ) ， t = t i ，i - o ，1 ，2 ，1 ) 。对于曲面相交算法，三角形顶点的排序并不重要，可以 是服从传统的右手定则，也可以是左手定则，依据实际应用而定。“n d e nb e c k 等发表的t r i c u t ，使用r a p i d 、啊a n g l e 三角化库和带有很多图形图像处理的 数据结构、算法和可视化工具的开源的v t k 对不规则曲面的处理，开发方便高 效，算法功能较单一，不能提供更多的实际需要的功能，执行效率有限 1 5 】。p e i z o n g l e e 等提出了基于四叉树的快速不规则曲面相交算法，效率低且相交的时问复杂 度呈线性增加【1 6 】。s n m u t h u k n s h n a n 等提出三维网格曲面的相交的有限元分析 方法【1 7 】。l a n q u e t i n s 等提出针对细分网格曲面布尔操作的速度和准确性进行了 改进【1 8 】。s h l o 等首先为网格曲面建立邻接表，通过判断三角面片的包围盒相 交性来排除不相交三角面片，获取交线段集合后，根据邻接表来实现交线排序， 获得交线【i 乒引j 。 国外曲面相交研究起步早，技术先进，已经广泛应用虚拟现实，工业，艺术， 航空航天，机械等领域。 1 3 国内研究现状 国内对曲面相交算法研究相对较晚，由于开发几何造型及数控加工系统等的 要求，2 0 世纪7 0 年代对曲面相交问题也进行了大量的研究。 参数曲面相交问题研究现状分析。北京航空航天大学的朱心雄在7 0 年代完 成了用代数法及对分法进行曲面相交的软件包【2 2 1 。由于三角b e z i e r 曲面具有可 分割性，可以通过近曲面点、边界点跨越等过程，可以由一个初始交点跟踪跨越 多曲面的交线，再以交线对三角网格进行划分，分割裁剪曲面【2 3 1 。黄金贵等提 出了一种基于微分方程的跟踪算法。该算法采用基于交线微分形式的跟踪公式， 解决了相交中难于处理的分支问题。和已有跟踪法相比，该算法稳定性更强，效 率更高，而且适用于任意参数曲面及解析曲面。陈丽萍等针对目前常用的b e z i e r 曲面分割法相交难以同时满足高精度和高速度要求的问题，提出了一种快速跟踪 相交的算法，算法具有高效、高精度的优点【2 4 】。1 9 8 4 年席平根据b 娩i e r 作图定 理，用对曲面进行分割的办法来获取曲面与曲面之间的交点和交线，同时讨论了 相交区间的判别，精度控制以及交点排序问题，实现了任意参数曲面相交和拼合 【2 5 1 ，余工f 生在1 9 9 9 年提出了新的参数曲面与隐式曲面的求交算法，把参数曲面 的表达式代入到隐式曲面的方程中获取参数方程，抽取参数域的等值线，再向参 数曲面上映射获取曲面之间的交线【26 ，曾祥林对于包含奇异点的交线作出了进 一步的研究，如果包含奇异点则打断该交线，然后再按照它们的逻辑拓扑结构排 北京化t 大学硕f ：学位论义 序，保持拓扑的一致性【27 i 。唐敏等将人工智能算法应用到曲面相交算法中，将 退火遗传算法和跟踪法结合，充分利用遗传算法的内在并行性和全局搜索性，以 及跟踪法的局部快速收敛性，可以可靠的交线及其拓扑结构【2 8 2 9 1 。 在非参数曲面相交研究现状分析。郑红军等利用曲面网格模型的拓扑关系计 算交线【3 0 1 。花卫华等以t r i c u t 为基础对算法的部分细节进行了改进，提高效 率【3 1 。3 2 】。周海通过将对细分曲面的求交转换成为控制网格的求交，再经过三角 形的交线连接获取曲面的交线【3 3 1 。唐良红为解决了几何相交的不稳定性问题， 从计算精度入手，分析交线计算不精确的原因，建立起具有不同几何意义的精度 之问的内在关系【3 4 1 。朱良峰在地质断层中应用了三角网曲面的切割算法，切割 后根据断层的断距对交线进行调整【35 1 。兰向荣【3 6 】由于地质断层三维可视化构模 等需要，对曲面相交算法采用的碰撞检测算法，同时改进了三角形相交算法和三 角形包含测试方法，可以解决复杂地质体的交、并、差等布尔操作。 1 4 曲面相交的应用 随着科学技术的不断发展，曲面相交技术已经应用到现代化的各个领域，推 动各行业新的技术革命。这罩主要介绍曲面相交在工业、地质矿体、医学、艺术 等领域的应用，虽然这只是众多领域中的小部分，但我们还是可以看到它的重要 性和广阔的应用前景。 s s i 应用于工业。在工业中，曲面造型非常重要，由于需要造型的对象复杂， 设计要求高。航空工业中的波音公司，就在7 0 年代中期为生产波形7 4 7 飞机使 用了c a d 系统。后来，将该技术拓展到最新的其他型号的飞机设计中，如机体 外表面，机翼的设计。国外拥有很多软件功能强大几何造型系统，如法国c a t i a ， 美国的c a d 开发环境和设计工具。在汽车工业中，流畅的外形和出色的性能是 极其重要的。2 0 世纪6 0 年代，法国的雷诺汽车公司的设计专家b 6 z i e r ，发明了 以他的名字命名的b 6 z i e r 曲面，并以其为基础，发展了一套自由曲线曲面的设 计制造系统，应用到汽车的造型中，取得了巨大成功。 s s i 在地质矿体中应用。地质问题以成为贯穿与数字城市，地下工程，水电 工程，环境工程，资源开发的个基础性问题。三维地质模拟是解决地质问题的 关键技术。在地质领域中，断层是最常见的地质现象之一，它损坏了地质结构的 连续性，改变了原始的地质格局。在石油、煤炭、金属矿产、地下水等方面，在 开采之前都必须进行储量的探测和分析。这些都需要s s i 算法进行曲面的切割、 分析和模拟。 s s i 应用于医学。虚拟手术是集医学、计算机图形学、计算机视觉、机器人 等诸多学科为一体的新型交叉研究领域，可以帮助医生在手术之前对患者手术方 4 第一章绪论 案进行仿真模拟，保证手术可靠性，用虚拟的手术刀进行手术，手术刀与人体的 切割就需要s s i 算法。通过模拟，可以减少医生的失误，帮助医生制定合理的手 术方案，使医生远离感染和放射线的损伤，而且还可以通过机器人进行远程干预。 s s i 应用于艺术。在计算机图形学发展的这个时代，细分曲面是在娱乐艺术 领域应用最多的技术。现在，几乎所有的3 d 造型设计和动画的制作都用到了细 分曲面。细分曲面可以多层次的表现人物的细节，给人带来真实的视觉享受。 p i x a r 的众多影片都采用了该技术，如果非常成功的虫虫特工队、海底总动 员和超人特工队。 1 5 本文主要工作与创新点 本文的曲面相交算法是以不规则的曲面相交为研究对象，采用碰撞检测算法 获得相交区域，然后在对相交区域进行交点计算和交线构成，最后对相交区域的 三角形进行重构和优化。 主要研究内容： ( 1 ) 分析比较常用的层次结构碰撞算法的特点，包括包围球，轴向包围盒， 方向包围盒，离散轴向包围盒。在曲面相交算法中相交区域的检测对整个算法的 效率影响较大，因此需要改进碰撞检测的效率。本文中根据相交曲面的具体特征， 动态的进行碰撞检测，以获取相交区域。 ( 2 ) 相交区域的三角形的相交关系多种多样，如何对每种相交情况的三角形 都能准确的计算交点对后续的处理非常重要。空间三角形相交关系复杂，通过分 析所有可能出现的空间三角形相交的情形，将所有的处理方法统一、分类处理， 降低算法的复杂度，增加程序的可维护性，提高算法的稳定性。 ( 3 ) 按照已有的交线串联方法，如果遇到歧义点算法将不知道串联将向那个 分支串联。本文研究既能够满足实际处理需要，又能够真实还原实际的逻辑情况 的交线计算方法。其结果在曲面处理后进行曲面分块、布尔操作等非常重要。 ( 4 ) 在实际应用中需要对闭合的3 d 交线进行三角化，以封闭被切割的曲面。 已有常见的3 d 闭合交线的三角化方法将闭合交线投影到坐标面，再使用2 d 的 三角化算法或其他方法进行三角化，不能处理空间扭曲的闭合交线。提出一种新 三角化3 d 闭合交线的方法来处理扭曲3 d 交线。 ( 5 ) 对曲面的相交区域三角化会存在大量的形状细长的三角形，这些三角形 破坏原曲面三角形的均匀性，同时也需要大量空间存储这些三角形，如果这些三 角再次进行相交检测，会累积产生更加细长、接近直线的三角形。提出一种基于 交线平均长度的方法对相交区域的三角形进行优化。 主要创新点： 北京化丁人学硕i j 学位论文 ( 1 ) 针对曲面结构复杂，相交区域的分布离散，曲面数据量大，提出了基于 o b b 的动态层次结构碰撞检测算法，使碰撞检测能够根据曲面的相交区域