一种应用于离散时间碰撞检测的加速算法

第１４卷第３期　２Ｏｌ５年３月　软件导刊　Ｓｏｆｔｗａｒｅ　Ｇｕｉｄｅ　Ｖｏ１．１４Ｎｏ．３　Ｍａｒ．２０１５　一种应用于离散时间碰撞检测的加速算法　赵静　，叶军涛　（１．国家知识产权局专利局专利审查协作广东中心，广东广州５１０５３５；２．中国科学院自动化研究所，北京１００１９０）　摘　要：在布料仿真中，离散时间碰撞检测（Ｄｉｓｃｒｅｔｅ　Ｃｏｌｌｉｓｉｏｎ　Ｄｅｔｅｃｔｉｏｎ，ＤＣＤ）中的邻接三角形对与非邻接三角形对　之间的相交检测在实际执行中存在大量的重复边一面（Ｅｄｇｅ－Ｆａｃｅ，Ｅ＿Ｆ）检测。通过引入“边一面代表三角形”的概念，　可以剔除非邻接对之间约５Ｏ　的重复Ｅ－Ｆ检测；通过定义“边一面孤立集”，可以建立起邻接对之间需要实际执行的　边一面检测。在网格拓扑结构不变的情形下，上述过程可以在数据的预处理阶段提前完成，从而实现ＤＣＤ加速。　关键词：布料仿真；碰撞检测；边一面代表三角形；边一面孤立集；加速算法　ＤＯＩ：１０．１１９０７／ｒｊｄｋ．１４３９４２　中图分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１６７２－７８００（２０１５）００３—００４９—０３　０　引言　在当前布料仿真过程中，模型之间的碰撞检测方法可　以分为连续时间碰撞检测Ｅｌ－ｚ］（Ｃｏｎｔｉｎｕｏｕｓ　Ｃｏｌｌｉｓｉｏｎ　Ｄｅｔｅｃ－　ｔｉｏｎ，ＣＣＤ）和离散时间碰撞检测Ｉｓ－４］（Ｄｉｓｃｒｅｔｅ　Ｃｏｌｌｉｓｉｏｎ　Ｄｅ—　ｔｅｃｔｉｏｎ，ＤＣＤ）两种。在以基本单元为三角形的多边形网　格模拟布料的场景中，ＣＣＤ归结为三角形对（Ｆａｃｅ—Ｆａｃｅ，　Ｆ＿Ｆ）之间的６次顶点一面（Ｖｅｒｔｅｘ－Ｆａｃｅ，Ｖ－Ｆ）检测和９次　边一边（Ｅｄｇｅ－Ｅｄｇｅ，Ｅ—Ｅ）检测；ＤＣＤ的Ｆ－Ｆ检测可归结为　状态；而非邻接对可以同时出现在不同网格的三角形之间　和相同网格的不相邻的三角形之间。　Ｍｏｌｌｅｒ＿ｇ　提出了一种快速判断两个三角形是否相交　的方法，Ｔｒｏｐｐ等＿１。。也给出了一种执行速度更快的算法，　这两种算法都不需要进行特征元之间的相交检测，能够快　速判断两个三角形是否相交。然而，布料仿真中的碰撞检　测不仅要判断出两个三角形是否相交，还需要确定交点位　置　，因此布料仿真中的碰撞检测必须通过执行基本的特　征元检测来实现，即进行Ｅ—Ｆ检测。　在当前算法中，采用ＢＶＨ技术可以剔除明显不会发　生碰撞的非邻接对　，因此可以实现非邻接对之间的加　速，从而建立起“潜在碰撞”的非邻接对，进入特征元检测　阶段；而对于邻接对，ＢＶＨ技术无法使用，为保证不遗漏，　所有邻接对均需要进入特征元检测检测阶段。在特征元　检测阶段，每一次Ｆ－Ｆ检测均需要执行６次Ｅ—Ｆ检测。　６次边一面（Ｅｄｇｅ—Ｆａｃｅ，Ｅ—Ｆ）检测。　碰撞检测加速算法大多应用于碰撞检测前的碰撞剔　除检测　，主要采用层次包围体　（Ｂｏｕｎｄｉｎｇ　Ｖｏｌｕｍｅ　Ｈｉ－　ｅｒａｒｃｈｙ，ＢＶＨ）技术来剔除明显不会发生的Ｆ－Ｆ检测，从　而降低算法的时间复杂度。针对ＣＣＤ过程，Ｔａｎｇ＿７　和　Ｃｕｒｔｉｓ等　提出了相应的加速算法，用于提高ＣＣＤ过程　的重复特征元检测效率。　ＤＣＤ过程的时间复杂度虽然相比ＣＣＤ较低，但现有　ＤＣＤ算法在Ｆ－Ｆ检测阶段同样存在大量的重复特征元检　２　ＤＣＤ特征元检测阶段存在的问题　虽然在一次的Ｆ－Ｆ检测当中执行所有６次Ｅ－Ｆ　检测都是有意义的，但当在两个由许多三角形组成的网格　之间执行ＤＣＤ时，如果每次Ｆ—Ｆ检测检测都执行６次Ｅ—　Ｆ检测，就会出现重复或者无意义的检测。前者会同时出　现在非邻接对和邻接对的Ｆ—Ｆ检测过程中，而后者则是邻　接对的Ｆ—Ｆ检测过程的特殊现象。　２．１　非邻接对中重复特征元检测的出现　测，如何剔除这些重复检测对ＤＣＤ加速十分重要。　１　ＤＣＤ研究现状　ＤＣＤ中的Ｆ－Ｆ检测是判断某一时刻静止的两个三角　形是否相交。如果两个三角形相邻，即存在共享的边或者　顶点，则称之为邻接对；否则，称为非邻接对。ＤＣＤ过程　图１描述了非邻接对之间产生重复特征元检测的原　包括邻接对和非邻接对之间的相交检测。邻接对只会出　现在同一网格中的相邻三角形之间，即网格出现了自相交　基金项目：国家自然科学基金项目（６１０７０１０５）　因。边ｅ和Ｅ分别由三角形ｔ。、ｔ　和　、Ｔ　共享。ｔ。同时　和丁０、Ｔ１相交，丁１同时和ｔ。、ｔ　相交。在对非邻接对（ｔ。，　作者简介：赵静（１９８５一），男，湖北黄冈人，硕士，国家知识产权局专利局专利审查协作广东中心专利审查员，研究方向为计算机图形　学与应用；叶军涛（１９７２一），男，博士，中国科学院自动化研究所副研究员、硕士生导师，研究方向为计算机图形学、虚拟现　实技术、科学计算。