基于混合包围体的openmp并行化碰撞检测算法

《基于混合包围体的openmp并行化碰撞检测算法》由会员分享，可在线阅读，更多相关《基于混合包围体的openmp并行化碰撞检测算法（5页珍藏版）》请在金锄头文库上搜索。

1、赵伟等：基于混合包围体的O p e n M P 并行化碰撞检测算法 基于混合包围体的O p e n M P 并行化碰撞检测算法牛 赵伟1 , 2 谭喜璞2 李文挥1 1 ( 吉林大学计算机科学与技术学院吉林省长春1 3 0 0 1 2 ) 2 ( 长春工业大学计算机科学与工程学院吉林省长春1 3 0 0 1 2 ) 摘要针对交互式系统争碰撞检测实时性精确性的要求，提出了一种共享存锗系统的并行碰撞检测算法利用A A B B 包囤 盒较好的紧密性和包围球计算简单的优点采构建物体的；盼包围体层次( S - A A B B ) ，快速排除不相交的物体阻加速算法，利用 O p c 吐。并行模型来并行遍历

2、混合包围体层次，进一步加速碰撞检测算法实验结果表明，与现有的经典的I - C O L L I D E 0 等算法 相比，谊算法在效率、精确性方面具有明显优势，能够满足交互式复杂虚拟环境的实时性和精确性的要求 关键宇碰撞检测；：融釜包围体层次；并行化：O p e n , n , P a r a l l e lC o l l i s i o nD e t e c t i o nA l g o r i t h mB a s e dO HM i x e dB V Ha n dO p e n M P Z h a oW e i l 甜T A NR m 矿L IW e n h u i l ( 铂珏c 窖eo

3、 f c o p I 舸s c i 血T c c j 锄，i 。薯y 恤U n i v e n i t y , C l u m g c h u n1 3 0 0 1 2 ，C h i 盈) 2 ( S c h o o lo f C c 衄p l 船S c i e n c e E n g i n e e r i n g , C l 业g c h u aU n i v e r s i t yo f T e c h n o l o g y , C h a n g c h t m1 3 0 0 1 2 C h i a a ) + C o r r 味q x m c l m ga u t h o r P

4、h a ：1 3 0 8 6 8 4 6 5 8 8 0 4 3 1 - 8 5 5 5 6 6 8 8 。E - m a i l ：脚t 2 0 5 1 6 3 c o r n A b s t r a c tC o n c e r n i n gt h er e q u i r e m e n t so fr e a l - t m ea n da c c u r a t ec o l l i s i o nd e t e c t i o ni ni n t e r a c t i v et o , s t e m , W Cp r o p o 辩as h a 面m e m o r y p

5、a r a l l e lc o l l i s i o nd e t e c t i o na l g o r i t h m F i r s tW e ：m c o r p o r a t et h em e r i t so fb o t hA A B Bb o u n d i n gb o xe n db o u n d i n gs p h e r e st Oc m L s t m c ta h y b r i db o u n d i n gr e p r e s e n t a t i o no fa r b i t r a r yn o n - c o n v e xp o

6、l y h c d r 翟( S - A A B B ) f o ra t t a i n i n gs p d , a n dt h e n 璐eO p e n M Pp a r a l l e l p r o g r a m m i n gm o d e lt ot r a v e r s a lt h eb u i l th y l x i db o u n d i n gv o l u m eh i e r a r c h y , S Of u r t h e ra c c e l e r a t et h ec o l l i s i o nd e t e c t i o na l

7、g o r i t h m A t l a s t , e x p e r i m e n t sr e s u l t sh a v es h o w nt h a t a l g o r i t h mi sa d v a n t a g e o u so v e ro t h e rc u r r e n tt y p i c a lc o L l i s i o nd e t e c t o n 飘l c h 越I - C O L L I D E 碡铲以i 辈e 伍c i e n c ya n d 翻穗c y 8 0 鞠您嚣您t h eR a l - t i m e 托da c c m

8、 - a t e 甲由啪选i nc o m p l e xi n t e r a c t i v ev i r t u a jc n v i r o n m e n t K e yw o r d sc o l l i s i o nd e t e c t i o n ；h y b r i db 咖d i n gv o l u m eh i e r a r c h y ；, p a r a l l e l i s m ；O p e n M P 1弓l 言 碰撞检测作为计算机图形学、虚拟现实等领域中的一个 经典问题多年来一直受到较多的关注由于虚拟环境的几 何复杂性的增加，碰撞检测往往成为虚拟环境中

9、的一个瓶颈 碰撞检弱算法大体上可分为两类：空间分解法和层次包圉盒 方法尤其是层次包围盘，已经作为公认的比较好的碰撞检 测手段被广泛应用主要包围盒有：沿坐标轴的包围盒 ( A A B B ) ，包匡球( S p h e r e ) ，汾任意方向包围盒O B B 等，每 种包围盒都有其优缺点 随着并行机的高速发展，并行碰撞检测在计算几何和机 器人控制等领域得到了广泛的应用f 2 J 文献【2 】提出了同等大小 体素构成模型的并行处理算法但对于过于简单或是结构复 杂的模墅较难处理文献【3 】提出了一种基于I V I P ! 的并行碰撞 检测算法，虽然算法效率得到了一定的提高，但是物体的八 叉树表示相

10、当费时，算法进程问通讯需要花费一定的时间 s q 即卅一b y 她t h e N a t l o e a l N S c i e n c e F e e n d a g m o f t k i a t u t w l a G f f t n t N O ，3 l 驼N 0 毋明3 田寡自嚣科学基金疆日) 俸蠢篙夯，篮伟( 1 9 6 7 年- - ) ，男。奢棒蜜长謇市，髯士嚣教授。焉研充生导筇。主要研究方匀为曩擒霹素雏。虚报毳客技本番l 曩謇囊( 1 ，钇年一) 女投族两膏 睿巩义市囊士研究生主要研拜方向为教据库系统，丘投现实技术等，李文肆【1 9 白年一) 男青韩省长春市霹士教授，士生寻师

11、主要研究方向为计算机圈形学与 虚拟现实技术等 5 9 中国计算机辅助设计与图形学2 0 0 8 纪念全国首届C A D C G 学术会议3 0 周年 文献【4 】提出了一种基于流水线的并行碰撞检测算法，虽然算 法效率有很大提高，但任务进程数P 对算法性能有很大影响， 难以找到最佳值。 与以上方法不同，作者提出了基于混合包围体的O w n M P 并行化碰撞检测算法采用分治策略为每个任意形状的物体 建立平衡二叉树，然后并行遍历包围盒树，这样极大提高碰 撞检测速度，并具有通用性能可以在单处理机和多处理机上 运行。 2 理论基础 2 1 混合包围盒层次 在粗略相交检测阶段，本文采用了包围球和包围盒树

12、来 加速算法包围球具有简单，且旋转平移后易于更新的特点， 缺点就是紧密性差，需要检测相交的包围盒对数多，而A A B B 包围盒与包围球相比，它对物体包围更加紧密，构造和相交 测试较简单。因此，我们利用A A B B 包围盒与包围球各自的 优点提出了混合包围体层次( S A A B B ) ，本文采用S A A B B 混合包围体树进行粗略阶段的相交检测 2 2 混合模型中不同类型包围盒的相交检测 设A A B B 包围盒内点的坐标为( x , y ，z ) ，其边长为H ，中 心坐标为( ，写，乙) ，则A A B B 包围盒的约柬方程为： 伍J ，z ) I o 毛y ，z o 时，口=

13、9 ；当K o 且五如时， e = 石一p ； 当如且五 o 时，口= 呻； 当K o 且五如时， e = 石+ 舻； 因此，仅器比较争d b t 和I z o f 即可得到两包围盒的相交情 况；若良如f | z o l ，则A A B B 包围盒和包围球相交；否则不 相交 - 6 0 3 算法描述及实现 3 1 混合包围体层次的构建 对于一个给定的基本几何元素集，混合包围体层次的构 建分为如下4 个步骤 ( 1 ) 采用文献 5 】中的方法来为物体的每个基本元素构建 小包围球，我们称之为基本球( u n d e r l y i n gs p h e r e ) 主要有两 个用途：文有助于快速

14、划分包围体，b 在进行精确的相交测 试前，它可用于预检测 ( 2 ) 建立根节点就是要建立整个物体的A A B B 包围盒、 整个物体的包围球和物体中所有多边形的基本球 ( 3 ) 利用与局部坐标轴垂直的平面，将上述包围体划分 成两个子包围体以形成根节点的两个子节点子节点具有和 根节点一样的三个特征：A A B B 包围盒、包围球和节点中所 有多边形的基本球 为使得左、右子包围体中的多边形个数大致相等，保证 混合包围盒体树的平衡，采用了一个惩罚函数( p ) 定义如 下： 厂( p ) = l 矗，一一，I + 工一 ( 4 ) 其中P 为分割面，啊，一，心分别为左包围体内、右包 围体内和横跨

15、基本球的个数丑是以的一个影响系数 ( 4 ) 对第( 3 ) 步中得到的两个子节点分别递归地执行上 述包围体的分割过程得到最终的混合包围盒树 图l 是根据上述算法步骤构建的平衡二叉树，每个节点 中第一行的两个数字表示包含在对应节点中的基本球数目 ( 等于相应多边形个数) 和对应节点的包围球的半径；第二行 的三个数字表示的是对应节点的A A B B 包围盒的宽度、高度、 深度。 图1 混合包围体层次的表示 3 2 混合包围体层次的遍历 物体A 和B 的混合包围体层次构建完成，我们就可以通 过遍历它们的平衡树来进行它们之间的碰撞检测，在此，我 们引入任务树的概念1 4 将遍历两个物体的平衡包围盒树的过 程定义成一棵任务树的遍历利用任务树，混合包围体层次 的广度遍历过程的算法如下 赵伟等：基于混合包围体的O p e n m 并行化碰撞检测算法 输入：两物体A B 输出：碰撞检测的结果T R U E ：相交，F A L S E ：不相交 b o o lW F S - T r a v e 传a l ( R A R B ) 建立凡B 两物体的混合包围盒树R A ，K B ； L I V E S E T = R a t i o T h r e s h o l d (