（计算机应用技术专业论文）点到三角形网格体的带符号距离计算.pdf

摘要 摘要 计算空间任一点到多面体的有符号距离在众多领域部有应用，如在虚拟现实，机器 人运动规划，碰撞检测等方面部有应用。经常通过计算物体问的最近距离来避免运动过 程中的干涉和碰撞，而求解点到多面体的最近有符号距离则足解决这类问题的关键。 本文针对三角形网格表示的物体之i 、日j 的关系，把角度权伪法矢量应用于点到三角形 网格体的带符号距离计算中，并进一步讨论了物体与物体之间距离的计算。 首先，对于封闭，光滑表面的物体来况，其表面的法向量可以用柬判别一个点是在 物体内部还是在外部。但是用三角形网格表示的物体在其顶点和边处不连续，因此不具 有法向量，只能定义一些伪法矢量，文中，我们证明角度权的伪法矢量和从表面上的最 近点到任意点之间的向量的点积的符号可以用来j i , j l 析点在多面体内部还是在外部。计算 点到网格的有符号距离的符号通常就山这个内- 夕r 信息米表示。并把此理论结果应用于 点到三角形网格体的有符号距离计算中。从而把点到光滑表面物体的内外测试推广到三 角形网格表示的物体上。我们采用动态球搜索技术来计算点到网格的带符号距离，此算 法能够快速获得一个含多面体最近体元素在内的侯选面片集，而且一般情况下该侯选集 都足够小，再计算点到侯选面片集之间的距离，可以避免传统方法中需要频繁的计算点 到当f j 订层的最近距离。 其次，进一步研究了物体到物体之间距离的快速计算，采用层次扫掠球来进行快速 的距离查询，并建立基于层次扫掠球的混合层次，具有可变的紧密度，提高算法的灵活 性。为了进一步提高算法效率，引入相对误差，并且限制报告距离与实际距离之间的误 差为一个用户定义的数。通过使用相对误差，准确距离计算和碰撞检测成为同一个问题 的两个极端情况，当用户定义相对误差为零时，则算法作准确距离计算，当定义相对误 差为1 0 0 时，若返回值为零，说明两物体发生碰撞。 关键词：距离计算，伪法矢量，网格，多面体，扫掠球量 江南人学顺f ：学位论文 a b s t r a c t c o m p u t i n g t h es i g n e dd i s t a n c eo fa na r b i t r a r yp o i n tt op o l y h e d r o nh a sb e e nu s e di nm a n y a r e a ，s u c ha sv i r t u a lr e a l i t y ，r o b o t i c sp a t hp l a n n i n ga n dc o l l i s i o nd e t e c t i o n i tw a su s e dt o a v o i dc o l l i d i n ga n di n t e r s e c t i o nd u r i n gm o v e m e n t s oc o m p u t i n gt h em i n i m u ms i g n e dd i s t a n c e i st h ek e yo ft h i sp r o b l e m c o n s i d e r i n gt h er e l a t i o n s h i po fo b j e c t sr e p r e s e n t e dw i t ht r i a n g l em e s h ，w ec o m p u t et h e s i g n e dd i s t a n c eo fap o i n tt o3 do b j e c t su s i n gt h ea n g l ew e i g h t e dp s e u d o n o r m a l a n dd i s c u s s t h ea l g o r i t h mo fc o m p u t i n gt h ed i s t a n c eb e t w e e nt w oo b j e c t s f i r s t l yf o ro b j e c t sw i t hc l o s e d ，s m o o t h ，a n do r i e n t a b l es u r f a c e s ，t h es u r f a c en o r m a li sa n i m p o r t a n tt o o lf o rd e t e r m i n i n gw h e t h e rag i v e np o i n ti s i n s i d eo rn o t h o w e v e r ，a no b j e c t r e p r e s e n t e da st r i a n g l em e s hi s n o tas m o o t hs u r f a c ea n d ，h e n c e ，d o e sn o th a v en o r m a l s d e f i n e de v e r y w h e r eo nt h es u r f a c e ( i e ，t h es u r f a c ei sd i s c o n t i n u o u sa te d g e sa n dv e r t i c e s ) i n t h i sp a p e r ，w ep r o v et h a tt h ea n g l ew e i g h t e dp s e u d o n o r m a lh a st h ei m p o r t a n tp r o p e r t yt h a ti t a l l o w su st od i s c r i m i n a t eb e t w e e np o i n t st h a ta r ei n s i d ea n dp o i n t st h a to u t s i d eam e s h t h e a l g o r i t h mu s e sd y n a m i cs p h e r es e a r c h i n gt e c h n o l o g yw h i c ht a k e st h eg i v e np o i n ta ss p h e r e c e n t e r ap o t e n t i a lf a c e ts e tc a nb ef o u n dq u i c k l ya n da c c u r a t e l ya n dt h i ss e ti sc o m p a c t e n o u g h t oa c c e l e r a t et h ed i s t a n c ec a l c u l a t i o ng r e a t l y c o m p a r e dw i t ht h eh i e r a r c h i c a l p r e s e n t a t i o na p p r o a c h ，t h i sa l g o r i t h ma v o i d sf r e q u e n t l yc a l c u l a t i n gt h ed i s t a n c eb e t w e e nt h e p o i n ta n dh i e r a r c h i c a ls t r u c t u r e w ea l s od i s c u s st h ea l g o r i t h mo fc o m p u t i n gt h ed i s t a n c eb e t w e e nt w oo b j e c t s a n d i n t r o d u c e saf a m i l yo fb o u n d i n gv o l u m e sc a l l e ds w e p ts p h e r ev o l u m e s ，f u r t h e r m o r e ，w eb u i l d h y b r i dh i e r a r c h i e su s i n gt h o s ev o l u m e s a n dt h ee f f i c i e n c yc a nb ef u r t h e ri m p r o v e db y a c c e p t i n gar e l a t i v ee r r o ri nt h er e t u r n e dr e s u l t w el i m i tt h ee r r o rb e t w e e nt h er e p o r t e d d i s t a n c ea n dt h ee x a c td i s t a n c et ob eau s e rs p e c i f i e df r a c t i o no ft h ee x a c td i s t a n c e ；b yu s i n ga r e l a t i v ee r r o r ，e x a c td i s t a n c ec o m p u t a t i o na n dc o l l i s i o nd e t e c t i o nb e c o m et w oe x t r e m e so ft h e s a m ep r o b l e m w h e nt h eu s e r s p e c i f i e s z e r or e l a t i v ee r r o r ，w ec o m p u t et h ee x a c t d i s t a n c e c o n v e r s e l y ，w h e nt h ea c c e p t a b l er e l a t i v ee r r o ra p p r o a c h e so n eh u n d r e dp e r c e n t ，t h e o b j e c t si n t e r s e c t k e yw o r d s ：d i s t a n c ec a l c u l a t i o n ，p s e u d o n o r m a l ，m e s h ，p o l y h e d r o n ，s w e p ts p h e r ev o l u m e s i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 查五垒日期：6 - 7 年7 月形日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：扯导师签辄丞牲 日期： d 7 年弓月形日 第一帝绪论 1 1 引言 第一章绪论 在计算机图形学中，三维复杂物体的几何表示方法大体上可以分为两类：面 ( s u r f a c e ) 表示和体( v o u m e ) 表示。体表示方法描述了物体的表面特征和内部特征，其 中内部特征描述了模型的有关物理属性。但是这种表示方法占用空间较大，不利于计算 机表示和处理，并且与之相关联的许多技术( 诸如分类、真实感绘制等) 尚未成熟。面表 示方法描述了模型的表面特征，大大减少了内存的占用肇。在很多实际应用中，并不需 要物体内部特征，因此面表示方法是目前比较通用的一种模型表示方法。 面表示方法有多种，如样条曲面表示方法，三角形网格表示方法等。目前，三角形 网格表示是一种最流行、最重要、且得到最广泛支持的一种表示方法。因为计算机图形 学中许多技术都可以产生物体的三角形网格表示，比如使用从扫描仪获取的数据来建立 原来对象的三维几何模型，采用移动立方体方法从体数据抽取物体的等值面等，这些模 型都是用三角形网格表示。另外，很多软硬件都支持以三角形网格表示的数据。虽然在 不同的软硬件实现中都有自己不| 一j 的数掘格式，但本质上都是基于这种表示结构进行分 析、操作和绘制的，i 女r i 辐射度计算、有限元分析以及碰撞检测等。基于曲面表示的系 统在进行处理前一般也都是先转化成这种表示，在各种硬件加速卡中通常也是这样实现 的。因此，三角形网格表示是计算机图形学中最基本的一种模型表示方法。 对于用三角形网格表示的3 d 物体，当处理这样的3 d 物体时，两物体之问的关系非 常重要，尤其是需要知道两个物体足否相交或者给定的路径是否与物体相碰撞。在虚拟 现实，机器人路径规划，数控加工等领域，常通过计算物体间的最近距离来避免运动过 程中的干涉与碰撞，而求解点到多面体的最近有符号距离是解决这类问题的基础。 计算空间点到多面体的最近有符号距离的关键在于如何减少搜索最近体元素的计 算量，一旦确定了最近体元素，则距离的计算就变成简单的问题。目前对这类问题的求 解主要有以下几类算法：一是基于g i l b e r t 算法的多面体分解算法，此算法给出了计 算复杂度为d ) 的求点到任意凸体最近距离的方法，因此这类算法的共同点就是首先通 过各种方法将任意凸多面体分解为一系列凸体的并，然后再利用g i l b e r t 算法进行求 解，但非凸多面体分解算法通常的计算复杂度为d 伽2 ) ，且不能保证正确处理任意复杂 的情况。另一类算法是建立空间物体的层次结构，从而快速搜索到最近的体元素的算法， 如利用空间八叉树剖分技术的层次表示方法，层次包围盒技术瞳1 ，以及利用不同半径的 球面来逼近原多面体表面的层次表示技术。 等各种层次表示方法。但是在实际应用中， 我们发现这类层次表示方法对分离的物体或者在某一个方向上尺寸较大的物体较为有 汀l 再人等：坝j j 学位论文 效，能够快速排除一些不相关的体元素，而对许多一般情况，特别是需要频繁计算距离 的情况，这种层次表示技术的加速效果是不够的，还有一类是近似的方法，如将空问进 行均匀剖分，然后通过计算空f h j 格了距离来近似其精确距离，或者用插值技术通过一些 已知数据插值出任意点的距离值。一! 。 在本文中，我们在研究两物体之i 口j 的距离查询算法的基础上，研究点到多面体的带 符号距离算法，对于光滑，封闭的物体来说，其表面的法矢量可以用来判断点在多面体 内部还是在外部，而计算点到网格的有符号距离的符号通常就由这个内- 夕 信息束表示。 但是对于用三角形网格表示的3 d 物体，由于在其顶点和边处，不连续，因此只能定义 一些伪法矢量，目的已经提出很多种伪法矢量，有不同的属性，本文的工作是在分析和 比较各种伪法矢量的基础上，证明角度权伪法矢量具有我们所需要的属性，并且把它应 用于点到三角形网格体的带符号距离计算中。并进一步研究了物体到物体之间距离的快 速计算方法。 1 2 国内外研究现状 在机器人学方面，最小距离查询广泛用于机器人路径规划，路径修改，和避碰中； 在计算机图形学方面，最小距离计算在物理仿真，模型原形方面起着重要作用。下面简 要分析目前已提出的各种模型之i h j 的最d , t j i 离查询算法。 1 2 1 多面体模型间的最小距离 c h i n m l 和e d e l s b r u n n e r 口1 提出时问复杂度为o ( 1 0 9 n ) 的两凸多面体之间的最小距离 算法。d o k i n 吲采用不同的方法得到同样的结果，并且把他的算法扩展到任意多面体 1 凸多面体模型 l i n c a n d y 哺1 算法的主要思想就足寻找两个多面体之i 口j 的一对距离最近的特征，称为 最近对。当多面体运动时，该算法跟踪并更新最近特征对。这里的特征对指的是多面体 上的一个顶点，边或面，特征对的距离指两个特征上距离最近两点的距离。该算法利用 一个事实，即当物体沿一个路径移动时，最近特征对不经常发生改变。该算法通过对多 面体做预处理，可保证最近特征对或者不变，或学在一个可预知的常量时| h j 内更新相邻 的特征对，算法首先从两个多面体上各选一个候选特征，检测最近点是否在这对候选特 征上，因为多i 丽体设为【几1 的，该项检测只需涉及与相邻特征的比较。如果检测失败，就 根据一定规则选取相邻的特征对作为新的候选特征对，重新榆测，通过一些简单的预处 理，可保证缚个特征的相邻特征个数恒定，因而可在预知的常量时问范围内更新相邻的 特征对。当检测失败时，该算还保证所选的特征对比原特征对更短，因而是收敛的，通 常情况下，即物体的运动变化不大时，算法可在一次或几次检测后找到最近特征对。在 最坏的情况下，算法的检测次数为两多面体之间的全部特征对数。 2 第一章绪论 物体a 和b 之间的距离定义为最短欧氏距离d 舳：d 柚2 毫瞄l p q 判断一对特征对是否是最近特征对的算法：即判断两个特征对是否包含最近特征点。算 法在预处理过程中首先计算好每个特征的v o r o n o i 区域。假设两个物体a 和b 上的待检测 特征对为f a ，f b ，特征点的检测主要检n u f a 上任意p 点足否落在f b 的v o r o n o i 区域中，f b 上任意q 点是否落在f a 的v o r o n o i 区域中，若检测成功，则说明f a s f t l f b 是a , w b 之间的最近 特征对，否则，则根据相应的规则更新特征对重新检测。找到最近特征对以后，检测特 征对之间的距离。 g i i b e r t 采用两个凸多面体的m i n k o w s k id i f f e r e n c e 来计算两物体l 、日j 的最小距离， c h u n g 田1 增加一个有效的m i n k o w s k id i f f e r e n c e 更新方法来进行两凸多面体的碰撞检测。 2 一般的多面体模型 q u i n l a n u 们提出计算两个非凸多面体问的最短距离的有效方法。通过采用层次包围 球技术对模型部分进行剪枝来实现。以深度优先的方式遍历到模型的叶子节点，并建立 最小上层距离来进行剪枝，允许近似结果来加速收敛，时间复杂度为l o g ( n 1 ，n 是场景 中的多边形个数。当要求精确距离时，则时白j 复杂度不冉是l o g ( n 1 。 1 2 2 参数模型间的最小距离 对于点p ，面s 上的最近点就是下面公式中的根： ( 唧) f k 塑o u 熹) 2 。 这个方程可以进一步转换为： s - p ) 。言 2 ， s - p ) 面o s o 1 凸曲面之间的最小距离 l i m a i e m n 提出了查询点到参数曲线和曲面以及他们之间的最近距离的算法，他的 算法通过重复查询曲面上的最近点从而收敛于局部最小距离，b a r a f f n 胡使用两严格凸曲 面l 白j 的最近点对末创建见证点( w i t n e s s e s ) 。并通过数值方法更新最近点对。 2 凹曲面之间的最小距离 s n y d e r n 砌提出了参数曲面问的全局最小距离方法，它使用间隔的方法来查询最小距 汀南人学埘if ：学位论史 离，可以避免检查所有距离的极值。 1 2 3 碰撞检测 当最小距离值为零时，可以步0 断两物体发生碰撞，从而把碰撞检测问题和距离计算 联系起来。该类算法通过寻找和f 艮踪两个多面体之1 8 j 的最近点来计算他们之间的距离， 当距离小于或等于零时，两者就发生了碰撞。比较著名的算法有l i n _ c a n d y 算法阳1 和 e n h a h c e d g j k 算法引。两种算法借鉴了时空连续性和几何连续性的原理来加速算法，当 物体运动速度不是很快时，前后两帧物体的移动距离和形状变化不是很大，可以利用上 一帧的物体位置和形状来加速算法。 1 3 应用领域 1 距离场计算： 距离场是一个标量场，它反映了空间中任意一点到一个给定物体表面的最短距离， 这个距离可以是有符号的，从而可以表征该点足位于物体之外还是物体之内，这样4 e t x , - t 于任一封闭曲面sc r 3 ，可以定义空间中任意一点pe r 3 的有符号距离场值 厂( p ) = d i s t ( p ，5 ) ，一般而言，l - 丁以没定该点位于物体之外是场值为正，位于物体之内 时常之为负，显然厂( p ) = 0 就表示了物体的表面s ，将物体表示为距离场形式可以大大 的简化物体间的自i 尔运算，点相对物体位置的判断等操作。本文中的算法可以应用于距 离场计算中。 2 虚拟环境下的碰撞检测： 在虚拟环境中，由于用户与物体的移动，物体之i 日j 经常会发生碰撞，为了保持虚拟 环境的真实性，需要及时预测到这些碰撞的发生，碰撞检测的方法有三种，层次包围盒 方法，距离跟踪法，和空i n j 音l j 分法。 其中的距离跟踪法就是通过计算两物体| 、日j 的最小距离来判断是否碰撞的。该类算法 通过寻找和跟踪两个多面体之间的最近点来计算他们之间的距离，当距离小于或等于零 时，两者就发生了碰撞。比较著名的算法有h i n c a n d y 算法聃3 * n e n h a n c e d g j k 算法n 制。 两种算法借鉴了时空连续性和几何连续性的原理来加速算法，当物体运动速度不是很快 时，前后两帧物体的移动距离和形状变化不足很大，可以利用上一帧的物体位置和形状 来加速算法。 ( 1 ) l i n 算法candy l i n _ c a n d y 算法的主要思想就足寻找两个多面体之间的一对距离最近的特征，称为 最近对。当多面体运动时，该算法跟踪并更新最近特征对。这罩的特征对指的足多面体 上的一个顶点，边或面，特征对的距离指两个特征上距离最近两点的距离。该算法利用 4 第一审绪论 一个事实，即当物体沿一个路径移动时，最近特征对不经常发生改变。该算法通过对多 面体做预处理，可保证最近特征对或者不变，或者在一个可预知的常量时间内更新相邻 的特征对。找到最近特征对以后，检测特征对之间的距离，若大于零则说明物体不相交， 否则相交。 ( 2 ) e n h a n c e dg j k 算法 e n h a n c e dg j k 算法足在g j k 算法上改进而成。g j k 算法足一个跟踪计算两凸多面体 间的最短距离的算法，与l i n c a n n y 算法不同的是g j k 不是直接对两凸多面体进行搜索和 跟踪，而是在他们的明氏距离多面体参数空问中搜索跟踪执行，它具有线性时间复杂度。 当物体a , u b 在空问中移动时，它们上边的最近点对a 干l l b 也跟着更新位置，实时检测 其问的距离，若距离大于或等于零，则它们相交，否则不相交。距离计算在碰撞检测中 有两个作用：决定调用静态检测的时间，实时向用户报告模型之间的距离。距离计算实 质上就是判断两个模型中距离最近的两点，然后计算它们之间的距离。距离计算算法分 为两种：静态算法和动态算法 典型的静态算法足d o b k i n k i r k p a t r i c k 算法。它在线性时间内对模型进行预处理， 建立d o b k i n _ k i r k p a t r i c k 层次数据结构，距离计算的复杂度就降低为0 ( 1 0 9 n l o g m ) 。处 理动态距离计算的一般方法是将时问离散化，根据模型当前的位置和方向计算距离。如 果时间间隔足够小，那么两个模型的最近特征( 顶点、边或者面) 可能就在上次最近特征 的附近( 假设是凸多面体) 。利用这种运动连续性就可以跟踪模型的最近特征的方法取代 静态距离计算。最早出现的跟踪算法是l i n _ c a n n y 算法，它从上次得到的最近特征对丌 始，沿多面体表面移动，直到找到最近特征。显然这种算法依赖于相邻两次最近特征距 离，即模型的相干性。如果相干性高，那么算法的效率较高；相反相干性越低，算法效 率就越低，在最坏情况下，算法需要执行o ( n 2 ) 步爿能找到最近特征。这足第一类跟踪 算法：基于特征的递增算法。第二类跟踪算法足基于层次数据结构的层次算法。其中提 出一种层次算法( h _ w a l k ) ，是建立在d o b k i n k i r k p a t r i c k 层次数据结构基础上的，能够 根据需要在不同层次上寻找最近特征，这样即使在相干性较低时也能保证算法的效率比 较高。从上次得到的一对最近特征开始执行两步搜索。首先在开始层次中移动固定的步 长s ，如果在这个过程中找不到最近特征，那么两个模型中同时降低一层，直到找到某 一层中的最近距离或者到达最低层；然后从最低层向上移动，当到达最上层时就得到两 个模型的最近特征。 1 4 本文所做工作 本文主要工作是建立在前人对物体到物体之间的距离计算的研究基础之上的，本人 所做工作主要如下：首先研究了目自仃已经提出的各种距离查询方法，重点研究点到多面 体的带符号距离算法，对于光滑，封闭的物体来说，其表面的法向量可以用来判断点在 多面体内部还是在外部，但是对于用三角形网格表示的3 d 物体，由于在其顶点和边处， 5 江雨人学坝i ? 号：1 1 ；z 论丈 不连续，因此只能定义- - j ：f ：p , 伪法矢量，目前已经提出很多种伪法矢量，有不同的属性， 本文的工作足在分析和比较各种伪法矢量的基础上，证明角度权伪法矢量具有我们所需 要的属性，为了证明这个结果的应用，我们把它应用于三角形网格的有符号距离计算中， 所有的无符号距离算法都是要找f , j x 寸于任意点p 网格上的最近点c ，找到了最近点c 后，用向量p c 与角度权的伪法矢量作点积，就可以计算出符号。除了证明角度权伪 法矢量和从表面上的最近点到任意点之i b j 的向量的点积的符号可以用来判断点在多面 体内部还足在外部外。我们还采用动态球搜索技术计算点到三角形网格表示的物体之问 的最近距离，此算法能够快速获得一个含多面体最近体元素在内的侯选面片集，而且一 般情况下该侯选集都足够小，再计算点到侯选面片集之f h j 的距离，不像层次结构表示方 法脚惦- 1 ，需要频繁计算点到当自，j 层的最近距离，因此算法适合距离场构造，运动物体间 的干涉检查等需要频繁计算点到多面体距离的领域。实验结果表明符号计算的时m 耗费 是很小的，从而把点到光滑表而物体的内外测试推广到三角形网格表示的物体上。 并进一步研究了物体到物体i u j 的最小距离计算，文中，我们采用层次扫掠球来进行 快速的距离查询。层次包围盒节点中的节点属于三种不同的扫掠球量。分别是点扫掠球 量( 相应于一个球) ，线段扫掠球量( 通过用一个球的球心扫过一个任意方向的线段获 得的复杂一点的量：两端为球形的圆柱体) 和矩形扫掠球量( 通过用一个球的球心扫过 任意方向的矩形获得的量：边和角是圆形的立方体) ，见p o p n7 。，并建立基于层次扫掠 球的混合层次，它具有可变的紧密度，能够提高算法的灵活性。同时采用有效而准确的 算法计算这些包围盒量之间的距离。 为了进一步提高算法效率，我们引入相对误差，并且限制报告距离与实际距离之间 的误差为一个用户定义的数。通过使用相对误差，准确距离计算和碰撞检测刚成为同一 个问题的两个极端情况，当用户定义相对误差为零时，则算法作准确距离计算，当定义 相对误差为l o o , 1 ，若返刚值为零，说明两物体发生碰撞。 1 5 本文组织结构 本文共分五章，各章的内容和组织如下： 第一章 绪论。介绍了课题的研究背景和意义，分析国内外的研究动态和水平，应用 领域、以及文章主要研究的内容。 第二章 系统回顾以前的各种距离计算算法。 详细介绍了a a b b ，o b b ，包闸球，离散方向多面体的基本概念，计算方法，优缺点， 并且介绍了层次包围体树的概念，构造方法，和包围体树的划分方法。在此基础上介绍 了一个有效的距离计算框架：l u b _ t r e e 框架，它可以应用于参数表示和多边形表示的 物体的距离计算中，分析其在不同情况下的性能，并把它应用于多面体问的距离计算中。 第三章研究了点到三角形网格表示的物体的带符号距离的计算方法。 对于封闭，光滑表面的物体来说，其表面的法向量可以用来判别一个点是在物体内 6 弼一币绪论 部还是在外部。但是用三角形网格表示的物体在其顶点和边处不连续，因此不具有法向 量，只能定义一些伪法矢量，文中，我们证明角度权的伪法矢量和从表面上的最近点到 任意点之间的向量的点积的符号可以用来判断点在多面体内部还足在外部。从而可以用 来确定距离符号。并采用动态球搜索技术末搜索最近体元素，能够快速获得一个含多面 体最近体元素在内的侯选面片集，而且一般情况下该侯选集都足够小，再计算点到侯选 面片集之问的距离，从而可以避免传统方法中需要频繁的计算点到当前层的最近距离。 搜索效率高于传统的层次结构表示方法。 第四章研究了物体到物体之问的最近距离的计算。 采用层次扫掠球来进行快速的距离查询，层次包围盒节点中的节点属于三种不同的 扫掠球量。分别是点扫掠球量( 相应于一个球) ，线段扫掠球量( 通过用一个球的球心 扫过一个任意方向的线段获得的复杂一点的量：两端为球形的圆柱体) 和矩形扫掠球量 ( 通过用一个球的球心扫过任意方向的矩形获得的量：边和角是圆形的立方体) ，并建 立基于层次扫掠球的混合层次，它只有可变的紧密度，能够提高算法的灵活性 第五章结论与未来工作。 对全文的工作进行总结，并介绍今后需要进一步做的工作。 7 江南人学顺 ：学位论文 2 1 引言 第二章距离计算问题的方法与分析 距离计算广泛用于实时地避碰，实时地路径修改和最优路径规划中，本章主要介绍 各种距离计算方法，重点介绍了包围盒的概念和包闸盒树的计算方法，并分析比较各种 包围盒的性能。在此基础上研究了l u b t r e e 框架，对其算法进行详尽的说明，并分析 该算法在不同情况下的性能。同时把此框架应用于多面体之问的最小距离查询中。 2 2e n h a n c e dg j k 算法 e n h a n c e d6 j k 算法是在g j k 算法上改进而成。g j k 算法是一个跟踪计算两凸多面体问 的最短距离的算法，与l i n _ c a n n y 算法不同的是g j k 不是直接对两凸多面体进行搜索和跟 踪，而足在他们的明氏距离多面体参数空间中搜索跟踪执行，它具有线性时间复杂度； e n h a n c e dg j k 算法将原6 j k 算法的时问复杂度改进为近乎常量级，达到与l i nc a n n y 算法 的同等水平。 定义两物体a * i j b 之i b j 的最近距离d ( a ，b ) 为它们的m i n k o w s k i 和： d ( a ，b ) = f i v ( a b ) l i ( 2 1 ) 其中定义u ( c ) 为c 中最接近原点的点，v ( c ) c 且卜( c ) i j = m i n 钏石i l ：x c ) 显然，对于a * i j b 中的最近点a a ，b b ，则a _ b = u ( a - b ) ，最近点a ，b 也称为物体a , 币n b 的见证点( w i t n e s s p o i n t s ) ，它们不一定是唯一的。当物体a , 币h b 在空间中移动时，它 们上边的最近点对a 和b 也跟着更新位置，实时检测其问的距离。 如何快速的寻找到见证点算法的关键问题，传统的g j k 算法对所有的顶点进行遍历， 导致时间耗费大，增加了时间复杂度，e n h a n c e dg j k 采用了“爬山法”迭代算法求解， 使时问复杂度大大降低，基本呈线性，大大减少了运算时问。 2 3 建立空间物体的层次结构 包围盒层次法是碰撞检测算法和距离计算中广泛使用的一种方法，它曾经在计算机 图形学的许多应用领域( 如光线跟踪等) 中得到深入的研究。其基本思想是用体积略大 而几何特性简誓的包围盒末近似地描述复杂的几何射象，进而通过构造树状层次结构可 以越来越逼近对象的几何模型，直到几乎完全获得对象的几何特性，在对物体进行距离 计算时，假设两物体问的距离为d ，初始化d 等于无穷大，先求两物体的包围盒间的距离 8 第，：章距离计算n d 题的方法j 分析 d 。，若距离小于d ，贝l j d = d 从根节点了1 ：始以深度优先方式遍历两棵树，若两节点之洲 距离大于或者等于d ，则说明从这个节点丌始下面的节点距离都足大于或者等于d ，囚此 剪技，能够快速排除一些小相关的体元素，从而可以减少大量的计算。由于求包闸盒的 之间的距离比求物体的要简单，若距离小于d 则只需对距离小于d 的包围盒的部分进行进 一步的距离测试，从而加速了算法。假设物体a 和b 要进行距离检测，则首先建立他们 的包围盒树。包围盒树中，根节点为每个物体的包围盒，叶节点_ ! 1 1 0 为构成物体的基本几 何元素( 如三角片) ，而中问节点则为对应于各级子部分的包围盒。包围盒层次法距离 检测算法的核心就足通过有效的遍历这两棵树，以确定在当前位置下，对象a 的某些部 分是否与对象b 的某些部分距离最近，从而进一步对该距离最近的两郝分进行精确的距 离计算。下面介绍包围盒的基本概念和各种层次包n 习盒的计算方法。 2 3 1 包围盒的基本概念 包闸盒技术足在1 9 7 6 年由c l a r k 提出的m 1 ，基本思想足用一个简单的几何形体( 即 包f f ；l 盒) 将虚拟场景中复杂的几何物体住，通过构造树状层次结构可以越来越逼近真 实的物体。 包围盒虽然是我们虚拟出的实体，但必须是有效的l 卜则实体。一个有效的正则实体 必须是形状与位置和方向无关的刚性实体；必须外部封闭内部连同，没有悬边和悬点； 必须维数一定占有有限的空自j ；有明显的边界能区分出内部区域和外部区域。除此之外 简单性和紧密性足衡量包围盒优劣的两个标准。就简单性 而言包围盒的几何特性应该比被包围的物体简单尽量较少见用存储空间，而且对于此类 包幽之f h j 的求交运算算法的复杂性也应该棚对容易。包围盒的紧密性决定包闸体逼近物 体的程度，包围盒包l 土i 物体越紧密，越能减少需要运算的概率。紧密性町以用包凼盒与 物体之间的h a u s d o r f f 距离来衡最。 固定点集之间的l l a u s e d o r f f 足巨离的定义：给定两个有限点集 a = ( a l ，a 2 ，a p ) ，b = ( b l ，b 2 ，b q ) 。定义h a u s e d o r f f 距离为h ( a ，b ) = m a x ( h ( a ，b ) ，h ( b ，a ) ) ，其中h ( a ，b ) = m a x 晒刘口一圳，l l a 一圳是a ，b 中点的泛数。函数 4 t = d t 卫 一一 h ( a ，b ) 称为由a 到b 的有向t t a u s b d o r f f 距离。即a 中某个点p 足a 中的点与b 中的点 距离最大的那个点。也就足说p 是a 对b 的最人失配点。h ( b ，a ) 为b 中点到a 的最大距 离。对于包围盒的紧密性我们用r 来表示，b 代表物体。g 是包i 土l 盒，b 和g 之问的 h a u s d o r f f 距离为： f = m ax 嘧d i s f ( 6 ，g ) 用d 来表示包阿盒与物体之i b j 的最人距离，则 d=maxd i s t ( g ，h ) g ，h g g ， 通过求包围盒和物体之i i j j 的h a u s e d o r f f 距离我们就可以衡量出包围盒的紧密性。 1 a a b b 沿坐柄；轴的包围盒a a b b ( a x i s - a l i g n e db o u n d i n gb o x e s ) ，一个物体的a a b b 被定 9 江南人学彤! i j 学化论文 义为包含该物体，且边平行于坐标轴的最小六而体( 见图2 1 ) 。构造时根据物体的形 状和状念取得坐标x ，y ，z 方向上的最大最小值就能确定包围盒最高和最低的边界点。 对于给定的物体，它的a a b b 仪需六个标帚描述，即组成物体基本几何元素的顶点的x 、y 、 z 坐标的最大和最小值。 劁2 1a a b b 包i 羽盒 a a b b 包幽盒的边界总足j 坐标轴平行，它的平面与其相应的坐标平面柏平行。一个 a a b b 包凼盒通常可以用其阳i 个坐标轴的投影的最大最小值来表示，还町以用物体中 心点和三个方向上的跨度来表示。 包凼盒a a b b lf ( m i n x l ，m i n y l ，m if i z l ) ，( m a x x l ，m a x y l ，m a x z l ) ； 包围盒a a b b 2 ( x o ，y o ，z o ) ，( 1 e n g t h ，w i d t h ，h e i g h t ) ) ； 构造a a b b 树足基j 。 a a b b 的二叉树，按照白顶向下的方法细分构造而成的。将物体 的a a b b 做为根节点，在每一次细分过程中，下一节点将上一子节点沿所需的剖分面将物 体分为两部分，将1 了 的原始儿何元素分别归属到这两部分，依次剖分，直到于i 王一个叶 节点只包含物体的一个基本儿何元素为止。具有n 个几何元素的a a b b 树包含有n - 1 个非 叶子节点和n 个叶子1 了点。 2 o b b o b b ( o r i e n t e db o u n d i n gb o x ) 方向包凼盒足由g o t t s c h a l k 等于1 9 9 6 年提出的。一 个给定对象的o b b 被定义为包含该对象且相对于坐标轴方向任意的最小的长方体。o b b 最 大特点是它的方向的任意性，这使得它可以根扼被包嗣埘象的形状特点尽呵能紧密地包 围对象，o b b 的构造稍微复杂一些，关键在于包m 盒最佳方向的确定，最佳方向必须保 证在该方向上包幽盒的尺寸最小。g o t t s c h a l k 等提出的一种计算三角网格体的o b b 包闸 盒的方法来建物体的o b b 包围盒，具体步骤如下： ( 1 ) 首先把所有多于三条边的多边形分割成三角片，累计凸壳卜所有顶点的坐标 向量获取甲均向量m 。 设第j 个三角形的顶点矢量为p ，珂，- ，包围盒包围的三角i f i i 片数为n 。 包围盒的中心位置为：朋= 去毫g + q + ，) ( 2 ) 由- t - 均向昂计算出队方差矩阵 1 0 ( 2 2 ) 矿 ，2 鼻 第一二章距离计算问题的方法j 分析 协方差矩阵元素：c 业一去耄仁瓦+ 万瓦+ i i ) 1s ，七s3( 2 3 ) 其中p = p 一肌，g = q 一m ，r 一，一优，c j k 是3 3 的协方差矩阵中的元素 ( 3 ) 求出协方差矩阵c 的特征向量，确定o b b 包围盒局部坐标的三个轴向。由于协 方差矩阵c 是对称矩阵，其三个特征向量相互正交。将这三个特征向量单位化后，没定 它们为凸块o b b 包围盒的局部坐标的三个轴向( d o , d 1 ，d2 ) 。 ( 4 ) 将凸壳的所有顶点分别向三个轴向d 0d 1 ，d 2 ) 投影。在三个轴向上的最大最小 投影距离差定为o b b 包围盒的大小 u o = m a x ( i h o j c c t ( d o ，v 1 ) ) ； u 1 = m a x ( 1 h o j c c t ( d 1 ，v 1 ) ) ； u 2 = m a x ( p r o je c t ( d 二，矿) ) ； w o = m i n ( i h - o je c t ( d o v 1 ) ) ： w 1 = n f i n ( 1 h - o j e c t ( d 1 , v 1 ) ) ； w 二= n f i n ( p r o j e c t ( d ：，v 1 ) ) ： ( 5 ) 计算包围盒的中心。 c p ，z t e ，。( 0 w o d o + 丢( “1 + w 1 ) d 1 + 吾( “2 + w 2 ) d 2 ( 2 4 ) 如果物体是凹的，利用这种方法求o b b 包围盒有个缺陷就是位于物体内部的点会 对包围盒的方向产生很大的影响，会使向量偏向内部点密度大的方向。所以解决此问题 的一个办法就是先求出物体的凸壳去除内部点的影响。平面点集或空间点集的凸壳的构 造算法主要有c b r a d f o r db a r b e r 提出的快速凸壳求法引，c h a n d 和k a p u r 提出的 卷包裹法，格雷厄姆法，p r e p a r a t a 和h o n g 提出的分治法，周培德的z 3 1 与z 3 - 3 法等 2 0 】 即使求得凸壳，o b b 包围盒的方向还会受到凸壳上顶点的分布影响，向量会偏向点 分布比较密集的方向。为了解决这个问题g o t t s c h a l k 等提出一种均匀面积密度采样法心1 。 存储一个o b b 需要l5 个标量( 表示方向的3 个基底向量共9 个标量和表示范围的6 个标 量) 。o b b 树的构造也采用自顶向下的方法。首先将包围盒的最氏轴用一个垂直于该轴 的平面来剖分，剖分的位置选为包围盒中所有顶点的均值位置。然后根据多边形的中点 在平面的哪一边来对包围盒中的多边形进行分类，采用此方法对包围盒进行剖分，直到 不能再分为止，作为o b b 树的叶结点。构造o b b 树的时i 、日j 为：若采凸包方法为0 ( n 1 9 2 n ) ， 若不采用凸包方法为0 ( n l g n ) 。 3 包围球 包围球类似于a a b b ，也是简单性好紧密性差的一类包围盒，包围球被定义为包含该 对象的最小的球体。包围球的球心可以用物体顶点坐标的最大值和最小值的一半来确 江南人学坝i j 学位论文 定。设物体顶点坐标最大最小值分别为：( x 。，y m a xz 。) ，( x