虚拟装配中碰撞检测的研究

1、第7卷第6期2007年3月 167121819(2007 621057205科学技术与工程Science Technol ogy and EngineeringVol . 7No . 6M ar . 20072007Sci . Tech . Engng .虚拟装配中碰撞检测的研究杨萍谢慧清3(兰州理工大学机电学院, 兰州730050摘要主要针对虚拟装配中的碰撞干涉检测, , 装配关系函数, 面向对象的基于包围盒的碰撞检测算法, , 提出的方法能很好地满足系统的实时性和交互性要求, 。关键词虚拟装配装配关系中图法分类号 , 当两个物体接触或当虚拟手与物体接触时, 需要利用碰撞检测算法对这两个物体

2、之间的接触情况进行检测。合理的碰撞检测需要选择合适的碰撞检测算法1, 2例如圆柱在模型表达的时候其实是多棱柱, 所以轴孔配合的时候, 有时会发生干涉碰撞; 这时, 就需要依据零件的装配约束关系确定干涉运动量, 剔除干涉之后, 进行最后的虚拟装配操作。因此, 本文主要解决了以下3个方面的问题:确定零部件的装配关系, 基于本试验选择合适的碰撞检测算法和干涉剔除方法。; 并且, 由于虚拟手的造型和许多三维物体采用的是多面体造型的方式来表达, 精确的碰撞检测需要在面片的层次上才能实现。也就是说, 精确地判断两者之间是否发生了碰撞, 需要检测两者的面片是否发生了碰撞(在实际的操作中一般选用三角面片 。特

3、别是存1总体设计在此虚拟装配系统中, 首先要确定装配关系, 形成装配函数对, 并利用接口技术用VC +对装配关系函数进行编程, 然后封装。利用选取的两种碰撞检测算法, 对有装配关系的两零部件进行碰撞检测; 若发生干涉, 则根据装配关系进行干涉剔除, 剔出干涉之后重新进行虚拟装配; 若没有干涉, 则直接进行装配, 最后虚拟装配完成, 具体的设计流程如图1。在很多的零部件时, 若直接进行碰撞检测则显得非常复杂, 系统的计算量大, 对操作的实时反应性差。这时, 需要在零部件导入系统的同时, 对零部件之间的装配关系进行确定, 减少碰撞检测的对数, 从而使系统计算量大大减少, 提高系统的实时性。为了进一

4、步提高系统的反应性能, 选择最合适的碰撞检测算法非常重要。算法既不能过于复杂, 又要满足系统的要求。本文提出了结合两种算法(AABB s 法和K 2DOPs 法 的碰撞检测算法。但是, 现实中不存在的干涉碰撞, 在虚拟装配中反而存在, 这是由于模型的三角面片仅是一种近似。2006年11月14日收到2确定零部件的装配关系函数根据现实装配中具体的装配关系和装配序列,第一作者简介:杨萍, 女, 黑龙江人, 博士, 教授, 研究方向:机器人, 虚拟制造系统。3通信作者简介:谢慧清, 男, 山东莱芜人, 硕士研究生, 研究方向:虚拟装配系统研究。E 2mail:benben 22001 。可以得到虚拟装

5、配操作系统中的各个零部件之间的装配关系, 从而形成装配函数对。根据装配关系可以降低系统的计算量, 提高系统的反应能力 。根 1058科学技术与工程表1装配函数表零件W 1W 1W 2W 3W 4W 5W 6W 7W 2W 3W 4W 5W 6W 77卷W n01100110010100010001001000110100110000111010110n1111表1中W i (i =1, , 7 代表单个零部件, 1代表有装配关系, 0代表无装配关系。从表1就可以很清楚的知道各零部件之间是否存在装配关系。若无装配关系则不需进行碰撞检测; 若有装配关系则需要进行碰撞检测; 若存在干涉情况, 则需根

6、据两零部件之间的位置运动量关系, 对此段区域内的干涉碰撞进行剔除, 使装配过程正常进行。在开始进行虚拟操作之前可以利VC +的程序填入具体的数图1装配流程据, 从而可以简化虚拟装配的复杂程度。通过建立装配函数表, 我们排除了不需进行碰撞检测的零部件, 节省了大量的时间, 加快了系统的反应速度。这不论是从加快产品的生产进程, 还是对于整个系统的快速化设计都起了关键的作用。VC +的程序如下:case i =1, 2, 3n i =1f or j =1t o j =n thenif dij =1then col our =red if dij =0then col our =0i =2i =n 程

7、序与i =1相同据零部件的装配关系首先确定两物体之间是否存在装配关系, 事实上有的零部件之间不存在装配关系, 则不需要进行干涉检验。对于有装配关系的零部件, 确定装配关系, 使之生成两两的装配函数对; 之后, 再根据装配函数利用VC +进行编程, 最终利用接口用于系统的碰撞检测之中。这样, 在具体的虚拟操作过程, 如果两物体有装配关系, 系统会出现提示。如轴孔配合时, 当抓取的轴与孔靠近时, 会出现相应的基准线; 这时, 就可以根据基准线进行装配。不过这种方法适用于系统有若干个零部件, 若本身零部件很少, 则不需要进行确定装配关系。现假设这里有n 个零件, 表1中W i (i =1, ,n 代

8、表单个零部件, 这些零部件之间形成的装配函3基于包围盒的碰撞检测在确定了装配函数表之后, 对存在装配关系的数对如表1所示。零部件就需要进行碰撞检测了。而虚拟环境自身的复杂性和实时性也对碰撞检测提出了更高的要求。目前, 对于碰撞检测的研究主要集中于碰撞检测算法的设计、选择与优化。包围盒方法用于碰撞6期杨萍, 等:虚拟装配中碰撞检测的研究1059检测主要是为了提高碰撞检测的速度, 通过对两个对象的包围盒层次间的相交测试, 尽可能早地排除所有不可能相交的基本几何元素对; 即如果两个结点的包围盒不相交, 那么它们的后代结点的所有包围盒一定不相交, 而它们所包围的对象也一定不相交, 从而不需要对这些后代

9、结点进行相交测试。通过包围盒间的相交测试, 快速排除不相交的几何元素对, 以减少相交测试的次数。适当的层次包围盒方法可以大大减少参与相交测试的包围盒的数目, 从而能有效提高碰撞检测的速度。, 4AABB 法的问题是它对于中心M 没有精确的计算方法, 一般采用近似的求平均值的方法, 但是这种方法有一个问题, 就是点的分布对M 影响很大, 如图2所示, 其中M 假设为理想的中心点 。M =m +m qipi =0+j =0(1 (2, 不适合软体变形的复杂环境。OBB 法紧密性好, 但由于OBB 的方向任意性, 使得OBB 间的相交测试复杂。凸包是包裹对象最紧密的包围盒, 但相交测试最复杂。K 2

10、DOPs 其实是介于AABB s 和凸包之间的包围盒, 它的突出特点是只要合理地选取平行平面对的个数和方向, 就可以在碰撞检测的简单性和包裹物体的紧密性之间灵活取舍, 即紧密性要优于AABB s, 而相交测试的复杂度要小于OBB s 。综上所有的碰撞检测算法, 本文提出了基于本系统的有效的碰撞检测算法。第一步碰撞检测选用AABB s 法, 这样可以迅速的完成零部件之间的相交测试。对大多数零件作粗略的碰撞检测, 快速排除相距较远的、未发生碰撞的物体。第二步选用K 2DOPs 法, 进行更加精确的碰撞检测。3. 1AABB 包围盒法的应用p S (P i -M 校正后中心M 和半径R m in 的

11、计算公式如下:(1 式中m 和q 分别为划分后密叶结点和非密叶结点的数目, 这样采用调整后的正方体包围盒进行快速的碰撞检测。采用简单的碰撞检测机制, 利用静态和动态轴一致包围盒AABB , 对大多数零件作粗略的碰撞检测, 快速排除了相距较远的、未发生碰撞的物体。3. 2K 2DO Ps 的精确碰撞检测方法K 2DOPs 法提出了根据景物的实际形状, 选取若干组不同方向的平行平面对, 包括一个景物或一组景物的层次包围盒技术。这些平行平面对组成一个凸体, 称之为平行2K 面体。将这一思想应用于碰撞检测, 就是用超过3对的平行平面对来逼近对象, 所有的平行平面对都是由方向相反的两个法向量所定义的半空

12、间相交得到的, 而这些平行平面对的法向量是固定不变的。在实际应用中, 可以合理地选择法向量的方向, 以简化平行平面对的计算。当K 足够大时, K 2DOP 就发展为物体的凸包。对于平面图形而言, 凸包是包围一组控制点的凸多边形的边界; 对于立体图形而言, 凸包是用面片连接各顶点的多面体的包络。所以, 凸包包裹对象最紧, 只要合理地选取K 的大小以及平行平面对的方 向, 就可以在碰撞检测的简单性和包裹物体的紧密性之间取得较好的折衷, 同时又能满足了系统的一个给定对象的AABB 被定义为包含该对象且平行于坐标轴的最小正六面体。一般情况下, 在一个虚拟场景中, 已发生碰撞的物体个数和即将发生碰撞的物

13、体个数远小于存在的物体个数。由于AABB 有构造简便、易于确定重叠状况等特点, 因而可以用未建立层次结构的AABB 剔除相距较远的或未发生碰撞的物体对。在检测出碰撞物体后, 再建立层次结构进行进一步碰撞检测。正方体包围盒只有两个参数:中心M 和半径R 要求。设S A 、S B 分别为结点V A 、V B 所对应的基本几何元素的子集, b (S A 、b (S B 分别为它们的K 2DOP 包围盒, 为空集, K 2DOP 之间的相交测试如图3所示 。图4碰撞检测算法时还要对实际发生干涉的区域, 根据零部件之间的K 2相交测试几何约束配合关系, 对此段区域内的干涉碰撞进行剔除, 使装配过程正常进

14、行。干涉剔除的原理思想就是要调整两零件之间的位置姿态, 计算装配位置运动量, 根据装配位置运动量完成零件的最终装配。其具体的算法过程如下:设有装配关系的两物体N , M 在世界坐标系中的坐标分别为(n x , n y , n z , (m x , m y , m z , 方位分别为(n A , n B , n C , (m A , m B , m C ; 物体M 当前的步长表示为p =(p x , p y , p z , p A , p B , p C , 即外界控制物体M 的运动增量, 则基于相对位置的干涉剔除算法的步骤如下:1 对物体M 的位置进行坐标变换, 即将物体Mif b (S A

15、b (S B if S A 是叶结点then if S B 是叶结点then f or S A 中的基本几何元素t Athenfor S B 中的基本几何元素t B进行基本几何元素对t A 、t B 之间的相交测试elsefor S B 的每一个子结点S b进行K 2DOPs 之间的相交测试TraverseTrees (S b , S A elsefor S A 的每一个子结点S a进行K 2DOPs 对之间的相交测试TraverseTrees (S B , S a Return同时为了加快手、物体与物体之间的碰撞检测, 可以让所有有装配关系的对象之间进行并行的基于包围盒的碰撞检测。每个对象都

16、采用相同的算法; 同时, 并行的、与虚拟场景中的其它物体进行碰撞检测。其时间由原来的f t =t a +t b +t c +t d +变为现在的f t =max |t a , t b , t c , t d , , 这样可以大大缩短碰撞检测的时间, 满足虚拟装配系统的实时性要求, 具体的碰撞检测算法如图4。的位置变换到物体N 的局部坐标系中去, 变换后位置设为c ; 将物体N 的坐标和方位的值代入式(1 中得到坐标的变换矩阵, 经变换矩阵得到物体M 在物体N 的局部坐标系中的坐标(c x , c y , c z ; 在物体N 的局部坐标系中, 物体M 的方位角(c A , c B , c C

17、=(m A -n A , m B -n B , m C -n C , 令 c =(c x , c y , c z , c A , c B , c C 。2 判断位置c 与位置a 的约束项的接近程度,对应位置a 处约束项, 计算约束项的差的平方均值,4干涉剔除由于模型的面片表示法在虚拟装配时会产生均值设为f:令 d = c - a , 令 e =(a sx ×d x , a sy ×d y , a sz ×d z , a s A ×d A , a s B ×d B , a sC ×d C , 则f = e × e /(a sx

18、 +a sy +a sz +a s A +a s B +a sC 。若f 的值小于预设的阈值干涉碰撞, 因此, 基于虚拟装配的碰撞检测不仅要能实时、精确地判断虚拟物体间是否发生碰撞, 同时, 则认为物体M 的位置就是装配干涉的初始位置, 即在下一步(帧 进入基于相对位置的干涉剔除 过程, 即直接从3 开始执行, 否则物体M 停止移动。3 确定装配运动量, 令q =(z sx ×p x , z sy ×p y , z sz包围盒法的结合使用, 以及最后的干涉剔除, 经过试验论证可以提高系统碰撞检测的效率, 可以很大的缩短整个虚拟操作的时间。不过, 在实际的实验之中, 还存在各

19、部分之间不能很好的兼容, 造成整个系统的效率降低, 在以后的工作要加以完善。参考文献1刘江省, 姚英学, 李建广, 等. ×p z , z s A ×p A , z s B ×p B , z sC ×p C , 即为非约束项的变化量; 令y =(v sx ×p x , v sy ×p y , v sz ×p z , v s A ×p A , v s B ×p B , v sC ×p C , 即为约束项的变化, y 在x 方向上的投影的长度为j =|y |×cos (y , x , 则j

20、 × h 为约束项的实际变化量, 由此得装配物体位置变化量为j × h +q 。4 干涉剔除过程的结束, ,. , ; :1747, , , . .将其与装配的最终. 2 同理, 当, ( , 2005; 18(1 :71763, , 丑武胜, 等. 快速计算虚拟物体之间精确接触位置的算法. 北京航空航天大学学报, 2005; 31(7 :7998044申玉斌, 蔡勇, 华才健. 虚拟环境中的碰撞检测技术的研究与, , 则装配过程结束, ; 当j <0时, 判断当前位置与装配的初始位置的位置关系, 若物体M 脱离装配干涉区域, 则装配过程结束。应用. 交通与计算机,

21、2005; 23(1 :74785吴彦鹏, 张建民, 伍贤和, 等. 一种面向虚拟装配的分层碰撞检测方法研究. 2003; (6 :1031055结语本文提出的虚拟装配中关于建立装配关系, 两Research of Collisi on D etecti on i n V i rtua l A sse m blyY ANG Ping, X I E Hui 2qing(SchoolMechanical and Electrical, Lanzhou University of Technol ogy . Lanzhou 730050, P . R. China AbstractThe interference with detecti on in the virtual asse mbly collisi on as well as re moving the interference is mainly is ai m ed at