基于空间数据结构的快速碰撞检测算法

第２８卷第４期　２００７年１２月　长春工业大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈａｎｇｃｈｕｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｏｎｏｌｏｇｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）Ｖｏ１．２８，Ｎｏ．４　Ｄｅｃ．２００７　基于空间数据结构的快速碰撞检测算法　韩文君　，　赵（Ｉ．长春工业大学计算机科学与工程学院，吉林长春伟　１３００１２）　１３００１２；２．吉林大学计算机科学与技术学院，吉林长春摘　要：在已有的预留碰撞算法基础上，提出了一种以空间数据结构管理为核心，用简化的几　何模型表示（０ＢＢ层次树）结合起来实现复杂物体间的实时碰撞检测算法，主要采用包围盒的　方法对检测物体进行包围，然后对包围盒所形成的体进行结构索引，遍历体索引输出检测结　果，这样在少量增加存储空间的前提下，可以提高碰撞检测的速度。　关键词：碰撞检测；空间数据结构；包围盒　中图分类号：ＴＰ３９１．９　文献标识码：Ａ　文章编号：１００６—２９３９（２００７）０４—０４１５－０６　Ａ　ｆａｓｔ　ｃｏｉ　ｌ　ｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｓｐａｃｅ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ　ＨＡＮ　Ｗｅｎ—ｊｕｎ　．　ＺＨＡＯ　Ｗｅｉ　＇　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈａｎｇｃｈｕｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｃｈｕｎ　１３００１２，Ｃｈｉｎａ；　２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ　１３００１２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｂａｓｉｎｇ　ｏｎ　ｔｈｅ　ｐｒｅ—ｒｅｓｅｒｖａｔｉｏｎ　ａｒｉｔｈｍｅｔｉｃ，ａ　ｒｅａｌ—ｔｉｍｅ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｓｐａｃｅ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ　ｍａｎａｇｅｍｅｎｔ　ａｓ　ｃｏｒｅ　ｉｓ　ｐｕｔ　ｆｏｒｗａｒｄ，ｗｈｅｒｅ　ｔｈｅ　ｓｉｍｐｌｉｆｉｅｄ　ｇｅｏｍｅｔｒｙ　ｍｏｄｅｌｓ（ＯＢＢ　ｌａｙｅｒ　ｔｒｅｅ）ａｒｅ　ｃｏｍｂｉｎｅｄ　ｔｏ　ｒｅａｌｉｚｅ　ｔｈｅ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｍｏｎｇ　ｔｈｅ　ｃｏｍｐｌｅｘ　ｏｂｊｅｃｔｓ．Ｔｈｅ　ｅｎｃｉｒｃｌｅ　ｂｏｘ　ｍｅｔｈｏｄ　ｉｓ　ａｐｐｌｉｅｄ　ｔｏ　ｓｕｒｒｏｕｎｄ　ｔｈｅ　ｄｅｔｅｃｔｅｄ　ｏｂｊ　ｅｃｔｓ，ａｎｄ　ｔｈｅｎ　ｔｈｅ　ｅｎｃｉｒｃｌｅｄ　ｂｏｄｙ　ｉｓ　ｉｎｄｅｘｅｄ．Ａｆｔｅｒ　ｔｈｅ　ｏｖｅｒ　ａｌｌ　ｓｅａｒｃｈｉｎｇ，ｔｈｅ　ｒｅｓｕｌｔ　ｉｓ　ｏｕｔｐｕｔ　ｔｏ　ｉｎｃｒｅａｓｅ　ｔｈｅ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｎｇ　ｓｐｅｅｄ　ｕｎｄｅｒ　ｔｈｅ　ｐｒｅ—ｃｏｎｄｉｔｉｏｎ　ｏｆ　ｉｎｃｒｅａｓｉｎｇ　ｔｈｅ　ｓｔｏｒａｇｅ　ｓｐａｃｅ　ｌｅｓｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ；ｓｐａｃｅ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ；ｅｎｃｉｒｃｌｅ　ｂｏｘ．　０　引　言　虚拟现实（ＶＲ）技术的主要目标之一是允许　用户以尽可能自然的方式与虚拟世界直接交互，　因此，ＶＲ系统的用户希望虚拟物体给人的感觉　是“物理存在”。但由于在真提高虚拟环境的真实　性、增强虚拟环境的沉实的物体运动中，任意两个　物体不会相互贯穿，因而在运动过程中，精确的碰　器人和虚拟现实等领域中的一个经典问题，多年　来一直受到较多的关注［２］。已有许多研究者对碰　撞检测问题及其应用进行了深入广泛的研究，提　出了许多有效的检测方法，形成了一些较为成熟　的技术。文献［３］采用层次包围盒技术加速多面　体场景的碰撞检测，它的基本思想是用体积稍大　且特性简单的几何体（包围盒）来近似地代替复杂　的几何对象，并通过构造树状层次结构逐渐逼近　对象的几何特性，从而提高碰撞检测的效率。为　了提高碰撞检测的实时性和降低算法的复杂性，　撞检测对浸感起着至关重要的作用Ｅ¨。　碰撞问题作为计算几何、计算机动画、仿真机　收稿日期：２００７—０４—０６　基金项目：国家自然科学基金资助项目（６０５７３１８２，６９８８３００４）　作者简介：韩文君（１９８３一），女，汉族，吉林长春人，长春工业大学硕士研究生，主要从事人工智能方向研究．＊联系人：赵　伟　（１９６７一），男，汉族，吉林长春人，长春工业大学副教授，吉林大学博士研究生，主要从事人工智能、多Ａｇｅｎｔ系统、软件自　动化与程序分析研究，Ｅ—ｍａｉｌ：ｐｒｉｎｃｅｌ２０５＠１６３．ｃｏｍ．　维普资讯 http://www.cqvip.com ４１６　长春工业大学学报（自然科学版）　第２８卷　文献［４１提出了基于凸多面体剖分的并行碰撞检　测算法。文献［５］对包围盒方法进行了一系列的　理论研究，证明了该方法可以使碰撞检测的算法　是否满足下列逻辑表达式：　Ｌ一［Ｐ　（￡　）Ｎ　Ｐｚ（￡　）Ｎ…ｎ　Ｐ　（￡　）］Ｖ　［Ｓ　（　）Ｎ　Ｓｚ（￡　）Ｎ…ｎ　Ｓ　（￡　）］一　复杂度大大降低。文献［６］则提出了两个有效的　碰撞检测算法：其一用来处理三角剖分过的物体　表面；另一算法则用来处理多面体环境的碰撞检　测。由于任一物体表面均可表示成一系列三角面　片，因而该碰撞检测算法具有普遍性，但这一算法　如果表达式成立，则不发生碰撞，否则发生碰　撞。　１．２　空间数据结构碰撞检测算法　对于一个体的拓扑关系的数据结构包括体、　面、环、边、点等元素。要对这些基本元素进行索　的缺点是当场景物为一复杂的雕塑曲面时，对表　面的三角部分可能产生大量的三角片，这会大大　影响算法的效率，为此，文献［７］提出了基于参数　曲面的集合碰撞检测算法。采用层次八叉树结　构，文献［８］提出了一个基于三角形的快速碰撞检　测算法，并把它应用于人体动画和衣服动画中。　文中提出了一种基于物体空间数据结构的快　速碰撞检测算法。首先，采用包围盒的方法对检　测物体进行包围（只进行包围，不进行检测）。其　次，对包围盒所形成的体进行结构索引，遍历体　索引输出检测结果。算法的整体框架如图１所　示。　物体模型输入　返回检测结果　实体凸分解　检测几何特征索引值　得到凸体集合　是否发生变化，以确　——ｒ一　土　定包围盒是否相交　建构层次　遍历物体　凸体二叉树　对的层次树　为层次树中的每　针对每个包围　个凸体结点生成　盒的几何特征　ＯＢＢ包围盒　进行索引　图１基于空间数据结构检测算法的整体框架　１碰撞检测与空间碰撞理论　１．１碰撞检测定义　假设三维空间中有Ｎ个运动模型，随着时间　改变位置和状态。从计算几何的角度可以这样定　义碰撞检测。　定义１　设３Ｄ空间中有Ｎ个运动模型，构　成集合Ｍ一｛Ｍ　，Ｍ２，…，　｝，运动前Ｎ　Ｍ　一　，　ｚ—１　（ｔｊ）为随时间变化的运动模型Ｍｆ在时刻ｔ，的　位置，Ｓ　（￡，）为随时间变化模型的状态。碰撞检　测则是判断当ｔ＝ｔ。，ｔ　”，ｔ　（ｍ为检测碰撞的有　效时间）时，运动模型集Ｍ中元素Ｍ　，Ｍ２，…，　引，如果体的构成复杂，那么索引起来将是非常耗　时的事情，所以这里采用了包围盒的思想。文中　采用了方向包围盒ＯＢＢ（Ｏｒｉｅｎｔｅｄ　Ｂｏｕｎｄｉｎｇ　Ｂｏ—　ｘｅｓ）。　１．２．１　ＯＢＢ包围盒的计算　利用一次矩（均值）和二次矩（协方差矩阵）统　计量来计算包围盒的位置和方向。设第ｉ个三角　形的顶点矢量为Ｐ　，ｑ　和ｒ　，包围盒包围的三角　面片数为　。　包围盒的中心位置为：　１　ｎ　一　∑（　＋ｑ　＋　协方差矩阵元素：　ｃ　一　∑（　ｉ　ｉ＋　＋　）　其中，Ｐ　一Ｐ　－－，ｕ，ｑ　—ｑ　—　，　一，』一　，均为Ｒ。　中的一个向量。　利用数值的方法解出协方差矩阵的特征向量　并单位化，由于Ｃ是一个实对称矩阵，所以矩阵Ｃ　的特征向量相互垂直，可以作为包围盒的方向轴。　把将要包围的几何体的顶点向方向轴上投影，找　出各方向轴的投影区间，各投影区间的长度就是　所求包围盒的相应尺寸。　１．２．２　ＯＢＢ包围盒的相交测试方法　凸块ＯＢＢ包围盒之间的相交检测方法采用　了Ｇｏｔｔｓｃｈａｌｋ等基于分离轴定理提出的相交检　测方法。　分离轴的重叠判断方法如图２所示。　图中，Ａ和Ｂ为两个ＯＢＢ包围盒，向量Ｄ为　Ａ中心点至Ｂ中心点的距离矢量。单位向量ＳＡ　为１５个分离轴之一。两个投影区间中点之距离　长度为ｌ　Ｄ・ＳＡ　ｌ。Ｐ＾和ＩＤ日分别为Ａ，Ｂ在ＳＡ上　的投影区间半径。于是，可以得出投影区间处于　分离状态的充分必要条件为：　Ｉ　Ｄ・ＳＡ　Ｉ＞ｐ＾＋Ｐ日　维普资讯 http://www.cqvip.com 第４期　韩文君，等：基于空间数据结构的快速碰撞检测算法　４１７　即　＞Ｏ，其中　一ｌＤ・ＳＡｌ一（ｐａ＋ｐＢ）。　图２　ＯＢＢ包围盒的相交测试　这里　的绝对值为在分离轴ＳＡ上的投影区　间重叠部分的长度或为投影区间分离间隙的长　度。令ａ　和ｂ　（　一１，２，３）分别为Ａ，Ｂ的半径，即　分别为Ａ，Ｂ两包围盒长宽高的一半；Ａ　和Ｂ　（　一１，２，３）分别为两包围盒的坐标轴单位向量；　则两包围盒在ＳＡ上的投影区间半径ｌＤｎ和ｌＤｅ可　由式（１）得到。　　。一二　＞　ｌ口　Ａ　・ｓＡ　ｌ　（１）　一＞　ｌ　ｂｉＢ　・ｓＡ　ｌ　当两ＯＢＢ包围盒相交，则它们在１５个分离　轴上的投影区间都是相交的。这时算法将保留在　它们６个包围盒轴上的投影区间重叠长度，即式　（１）中　的绝对值。　２算法的设计思想　２．１体的空间数据结构　空间数据结构如图３所示。　／　＼　Ｆｌ　…　上　上　￡１　八　ｌ　Ｅ２　Ｅ３　Ｅ４　图３空间数据结构　此空间数据结构共包含４个结点：体结点、面　结点、边结点和顶点结点。结点之间通过结构指　针相互联系。　２．１．１　体结点　体是三维几何元素，是由封闭表面围成的空　间，也是欧氏空间中非空有界的封闭子集，其边界　是有限面的并集。体结点是各种引用的根结点，　从体结点出发，可以索引到任何其它的结点。　２．１．２　面结点　面是形体上一个有线、非零的区域，它是有环　界定其范围，面有方向性，一般用其外法向量的方　法定义面的正负。　２．１．３边结点　边是一维几何元素，是两个或多个相邻面的　交界，在这里边结点对应几何元素的边。　２．１．４顶点结点　点是实体造型中的最基本元素，自由曲线、曲　面或其它形体均可用有序的点集表示。所以，顶　点结点必须包含顶点的空间三维坐标值。　２．２元素的基本操作　（１）对于基本几何元素，可做到下列操作。　・已知一个体，查找组成体的所有面、边、顶　点；　・已知一个面，一条边或一个顶点，查找它所　属的体；　・已知一个面，顺序查找围成它的所有的边；　・已知一个边，查找交于该边的所有面，查找　该边的邻边，查找该边的两个端点；　・已知一个顶点，查找交于该顶点的所属边、　所属面或所属体。　（２）要想各个几何元素之间查找迅速，必然要　在它们之间建立广泛的联系，这样必然增加存储　空间的占有量。但目前，计算机的内存价格低廉，　容量较大，完全可以满足对存储空间的需求。　（３）空间数据结构法的目的是减少每次求交　检测中所涉及的体的个数。当物体Ａ的几何特　征索引与物体Ｂ的一个结点包围盒发生关系时，　保留所有发生改变的特征索引，并组建一个特征　索引表，存贮特征指针。为获取物体Ａ的几何特　征索引与Ｂ结点包围盒的相交结果，需要读取深　度测试的结果，通过构造一个二维随机函数　ｆ（Ｕ，　），Ｕ　≤Ｕ≤Ｕｍ．　，　≤　≤　…作为生成　子索引的数据，用Ｎ（　，　）表示产生一个均值　，　标准差为　的正态随机函数，产生ｆ（Ｕ，　）的方　法是：　维普资讯 http://www.cqvip.com ４１８　长春工业大学学报（自然科学版）　第２８卷　ｆｆ（Ｕ　ｉ　，Ｖｍｔ　）一ｆｔ—Ｎ（Ｏ，　）　２．３．２建面结点索引　ＫＳＪＦａｃｅ＊ｓｏｌｉｄ；／指向面所属体的指针　Ｉ　ｆ（Ｕ　，Ｖｍ　）一　一Ｎ（Ｏ，　）　Ｉ　ｆ（Ｕ　，Ｖ　）一　一Ｎ（Ｏ，　）　【ｆ（Ｕ　，Ｖｍ　）一　一Ｎ（Ｏ，　）　得出：　２．３．３建边结点索引　ＫＳＪＬｉｎｅ＊ｖｅｘｌ；／边的顶点指针　ＫＳＪＬｉｎｅ＊ｆａｃｅｌ；／边所属面的指针　ＫＳＪＬｉｎｅ＊ｓｏｌｉｄｌ；／边所属体的指针　ｆ厂（　，　）一Ｎ（　，２－１８）　２．３．４建顶点结点指针索引　ｆ厂（　～Ｖｍ）一Ｎ（　）　｛厂（　～Ｖｍ）一Ｎ（　）　Ｊｆ（Ｕｍｉｎ，　）一Ｎ（　）　Ｉ厂　，ＶＴｍｉｎ￣Ｖｍａｘ）一Ｎ（　）　把区域［【，　¨Ｕ　］ｘ［　ｉ　，　］上的随机　函数分成以［（Ｌ厂ｍｉ　＋Ｕｍ　）／２，（　ｉ　＋Ｖｍ　）／２］为　分界点的４个子域上的随机函数。从公式上可以　看出，每分割一次，随机函数的标准差便下降二分　之一，这样产生的厂（Ｕ，　）在局部变化均衡。然　后采用新的几何特征索引，分别与Ｂ层次包围盒　树上的当前结点的两个子索引包围盒进行求交运　算，如此递归计算下去，直到Ｂ层次包围盒树的　叶结点中是三角形。一般地，由于几何特征索引　在求交计算中逐层简化，ＣＵＰ所需绘制的象素个　数也逐步减少，从而可大大加快绘制速度，提高算　法整体效率。　２．３算法实现　输入：两个物体Ａ，Ｂ；　输出：碰撞检测结果（真值为相交，假值为不　交）。　Ｓｐａｅｅ＿Ｓｔｒｕｃｔ（Ａ，Ｂ）ｆ　建立Ａ，Ｂ两物体的方向包围盒，并将此包围盒做为　体结点；　／＊体结点是各种３１用的根结点，从体结点出发，可　以搜索任何其他的结点＊／　Ｉｆ（Ａ，Ｂ为基本几何元素）｛用基本碰撞检测算法进行　检测，并返回结果；　即：ＡＢ＝　未发生碰撞　ＡＢ＝／：　发生碰撞）　Ｅｌｓｅ（　２．３．１建体结点索引　ＫＳＪＳｏｌｉｄ＊ｆａｃｅ／指向面的指针　ＫＳＪＳｏｌｉｄ＊ｄｅｇｅ；／指向边的指针　ＫＳＪＳｏｌｉｄ　ｖｅｘ；／指向点的指针　ＫＳＪＰｏｉｎｔ＊ｓｏｌｉｄ２；／Ａ所属体指针　ＫＳＪＰｏｉｎｔ＊ｄｅｇｅｌ；／点所属边指针　ＫＳＪＰｏｉｎｔ＊ｆａｃｅ２；／Ａ所属面指针　Ｉｆ（结点的初始索引发生变化）｛　说明当前两个结点所对应的ＯＢＢ包围盒相交，即　ＡＢ≠　，继续进一步判断，将包围盒一分为二，其中一部　分包含碰撞点处的区域。产生４个体结点Ｃ、Ｄ、Ｅ、Ｆ。　Ｓｐａｃｅ＿Ｓｔｒｕｃｔ（Ｃ，Ｄ，Ｅ，Ｆ）：　｝　Ｗｈｉｌｅ（当前结点为根结点或叶子结点）　返回Ａ，Ｂ两物体不会发生碰撞，遍历过程终止；　）　）　３性能分析与评价　文中提出的基于空间数据结构的快速碰撞检　测算法是以几何物体的基本拓扑关系为基础，以　简单性及紧密性都很好的方向包围盒（ＯＢＢ）为辅　助的一种快速检测算法，要想各个几何元素之间　查询迅速，必然要在它们之间建立广泛的联系，这　样也必然增加存储空间的占用量，但相对于ＯＢＢ　间的相交测试：需测试１５条可能是分离轴的轴，２　个ＯＢＢ的相交测试最多需要１５次比较运算，６Ｏ　次加减运算，８１次乘法运算和２４次绝对值运算。　本算法的复杂程度大幅度下降，并且能够快速地　检测出碰撞。　我们主要同基于ＯＢＢ包围盒的ＲＡＰＩＤ系　统进行比较，这是由于ＲＡＰＩＤ系统的代码是开　放的，而且它是近年来比较著名的一个碰撞检测　系统，常常被用做衡量碰撞测试算法的一个标准，　故用Ｃ＋＋实现了基于空间数据结构的碰撞检测　算法。　实验的运行环境见表１。　表１实验运行环境　维普资讯 http://www.cqvip.com 第４期　韩文君，等：基于空间数据结构的快速碰撞检测算法　４１９　构造包围盒层次的时间开销见表２。　表２构造包围盒层次的时间开销（单位：ｓ）　表３鑫要　磊　毒嵩　学能比较　当环境中的物体运行５　０００步时，在模型１　空问数据结构算法与ＡＡＢＢ，ＯＢＢ的性能比　较见表３。　１６Ｏ　与模型２中所用时间的实验数据直观比较如图４　所示。　１２Ｏ　曰　譬　嚣　８０　∞＼里鲁暴　４０　∞　∞　∞　∞　∞　０　㈣　。　０　圈基于ＡＡＢＢ包　盒算池　口萆于ＯＢＢ包　盒并浊　圜　于空问数据结构的碰撞检测算法　（ａ）模型１中检测结果的对比　（ｂ）模型２中检测结果的对比　图４　３种算法运行５　０００步实验数据的比较　通过图４实验数据的比较，采用基于空间数　据结构的快速碰撞检测算法后，检测时间得到降　低，显著地提高了碰撞检测的速度。　针对相同场景，本算法和基于ＯＢＢ包围盒的　ＲＡＰＩＤ算法的碰撞检测时间变化率的比较如图　５所示。　１００　５０　；　雕　ｏ　篓一５０　捌　１００　碰撞检测的步数　图５　碰撞检测时间变化率的比较图　图５中，水平轴是碰撞检测的步数，垂直轴是　式中：ｔ　——碰撞过程中记录每一步碰撞检测所　需的时间；　碰撞检测时间的变化率叩：　∞一　一　一　×ｌＯＯ％　运行５　０００步的平均时间。　从图中不难看出，本算法具有基于物体几何　维普资讯 http://www.cqvip.com

４２０　长春工业大学学报（自然科学版）　第２８卷　空间碰撞检测算法所不具备的时间消耗的稳定　性，即对同一复杂度的场景而言，不同步数中的碰　撞检测时间变化不大，这一特点有利于准确预测　碰撞检测时间。　４　结　论　目前，碰撞检测算法正得到越来越多的研究，　应用于越来越多的领域。文中提出了一种基于空　间数据结构的快速碰撞检测算法，以空间数据结　构管理为核心，将图形硬件的计算优势和简单的　几何模型表示结合起来，实现复杂物体间的实时　碰撞检测，并在具体的应用中对该算法进行验证。　实验证明，该算法确实加快了碰撞检测的速度，同　时，通过碰撞检测时间的变化率，再次证明此算法　具有基于物体几何空间碰撞检测算法所不具备的　时间消耗的稳定性。　目前，大部分碰撞检测算法都是针对具体的　应用场合设计的，没有一种算法适用于所有的情　形，且主要集中在静态环境下碰撞检测效率的研　究，而对动态环境下复杂虚拟场景中多虚拟对象　之间的碰撞检测问题，高效率的检测算法还不多。　在以后的工作中，我们将进一步研究空间数据结　构索引，在碰撞检测的简单性和包裹物体的紧密　性之间灵活取舍，减少存储空间的占有量，以建立　面向各类应用的更加实用、灵活统一的基于空间　数据结构的碰撞检测算法。　参考文献：　Ｅ１３魏迎梅，王涌，吴泉源．碰撞检测中的固定方向凸　包包围盒的研究［Ｊ］．软件学报，１９９９，１２：１　２５３—　１　２６３．　Ｅ２３　王志强，洪嘉振，杨　辉．碰撞检测问题研究综述　ＥＪ３．软件学报，１９９９，１０（５）：５４５—５５１．　Ｅ３］Ｈａｈｎ　Ｊ　Ｋ．Ｒｅａｌｉｓｔｉｃ　ａｎｉｍａｔｉｏｎ　ｏｆ　ｒｉｇｉｄ　ｂｏｄｉｅｓＥＪ］．　ＡＣＭ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ，１９８８，２２（４）：２９９—３０８．　Ｅ４］金文华，饶上荣，唐卫清，等．基于顶点可见性的凹　多边形快速凸分解算法ＥＪ］．计算机研究与发展，　１９９９，３６（１２）：１　４５５－１　４６０．　Ｅ５］Ｓｕｒｉ　Ｓ，Ｈｕｂｂａｒｄ　Ｐ　Ｍ，Ｈｕｇｈｅｓ　Ｊ．Ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃ—　ｔｉｏｎ　ｉｎ　ａｓｐｅｃｔ　ａｎｄ　ｓｃａｌｅ　ｂｏｕｒｄｅｄ　ｐｏｌｙｈｅｄｒａ［Ｊ］．　Ｐｒｏｃ．９ｔｈ　ＡＣＭ—ＳＩＡＭ　Ｓｙｍｐｏｓ．Ｄｉｓｃｒｅｔｅ　Ａｌｇｏ—　ｒｉｔｈｍｓ，１９９８，６（３）：２９１－３０２．　Ｉ－６］　Ｍｏｏｒｅ　Ｍ，Ｗｉｌｈｅｌｍｓ　Ｊ．Ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｎｄ　ｒｅ—　ｓｐｏｎｓｅ　ｆｏｒ　ｃｏｍｐｕｔｅｒ　ａｎｉｍａｔｉｏｎＦＪ］．ＡＣＭ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ，１９８８，２２（４）：２８９－２９８．　－Ｉ７］　Ｂａｒａｆｆ　Ｄ．Ｉｎｔｅｒａｃｔｉｖｅ　ｓｉｍｕｌａｔｉｏｎ　ｏｆ　ｓｏｌｉｄ　ｒｉｇｉｄ　ｂｏｄｉｅｓ　［Ｊ］．ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，　１９９５，１５（３）：６３－７５．　Ｅ８］　Ｙａｎｇ　Ｙ，Ｔｈａｌｍａｎｎ　Ｎ．Ａｎ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｃｌｏｔｈ　ａｎｉｍａｔｉｏｎ　ｗｉｔｈ　ｈｕｍａｎ　ｂｏｄｙ［Ｊ］．Ｆｉｒｓｔ　Ｐａｃｉｆｉｃ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎ，１９９３，１４（２）：２３７—２５１．