互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

基于着色算法的并行碰撞检测算法


□ 赵 伟 谭睿璞 杨秋娜 丁文保 李文辉

  (1.吉林大学 计算机科学与技术学院 长春 130012; 2.长春工业大学 计算机科学与工程学
  院 长春 130012; 3.西北工业大学 软件与微电子学院 西安 710072)
  
  摘 要:提出了一种基于着色算法的并行碰撞检测算法,利用AABB包围盒较好的紧密性和包围球计算简单的优点以及并行算法中的分治策略构建物体的混合包围体层次(SAABB);然后采用破对称技术中的典型算法——着色算法,将每棵任务树编码,以产生各不相同的类别,并将不同的类别指派到不同的并行机,在并行机上采用多线程技术执行相同的类别的任务树的遍历,来检测是否有碰撞发生。实验结果表明,与现有的经典的ICOLLIDE等算法相比,该算法在效率、精确性方面具有明显优势,能够满足交互式复杂虚拟环境的实时性和精确性的要求。
  关键词:碰撞检测; 混合包围体层次; 并行技术; 破对称; 着色算法
  中图分类号:TP301.6文献标志码:A
  文章编号:1001-3695(2009)05-1695-05
  
  Parallel collision detection algorithm based on coloring algorithm
  ZHAO Wei1,2 TAN Ruipu2 YANG Qiuna3 DING Wenbao2 LI Wenhui1
  (1.College of Computer Science & Technology Jilin University Changchun 130012 China; 2.School of Computer Science & Engineering Changchun University of Technology Changchun 130012 China; 3.Software & Microelectronics Institute Northwestern Polytechnical University Xi’an 710072 China)
  Abstract:This paper presented a new parallel collision detection algorithm based on coloring algorithm. At first incorporated the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary nonconvex polyhedra (SAABB) for attaining speed balanced especially the SAABB using divideandconquer technologies which were mostly primary technologies in parallel algorithm. Then applied symmetry breakingkcoloring technology which was also important in parallel algorithm in order to reduce different categories and assign them to different processors; also multithread was used in multiprocessor computer. At last experiments results show that the algorithm is advantageous over other current typical collision detection such as ICOLLIDE regarding efficiency and accuracy so can meets the realtime and accurate requirements in complex interactive virtual environment. ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017