基于双视角与半透明颜色叠加的碰撞检测算法
|
摘要
为了在复杂机械产品装配仿真过程中快速进行碰撞检测,提出一种基于双视角与半透明颜色叠加的碰撞检测算法。该算法通过多维显示投影将3D空间中的碰撞检测问题转化为平面像素点的参数判定问题,弥补了传统图像类碰撞检测算法只能识别是否发生碰撞而不能预先求距的不足。算法分为遮挡对象判定、碰撞面遍历和像素求距3个阶段。首先利用半透明颜色叠加算法快速剔除无碰撞可能性的零部件,判定出潜在的遮挡对象;然后利用像素深度值查找潜在的碰撞面对;最后基于横向视角识别可移动的像素点个数,基于像素个数计算碰撞距离。通过实验与分析表明,该算法能够满足虚拟装配系统中碰撞检测的速度要求。
To carry out collision detection quickly in complex mechanical product assembly simulation process,a collision detection algorithm based on double view and translucent color overlay was proposed.Through the multi-dimensional display projection,the collision detection problem in 3 Dspace of this algorithm was transformed into the traversal problem of planar pixels,which made up the shortcoming that most image-space collision detection algorithms could only judge whether the collision occurred,but could not find the distance.The algorithm was divided into three stages:block object determination,collision traversal and pixel traversal.The semi-transparent color overlay algorithm was used to quickly remove the parts without collision probability,and the potential occlusion object was determined;the potential collision surface was calculated by pixel depth value;the number of moving pixels was identified based on the horizontal perspective and the collision distance based on the number of pixels was calculated.Through the experiments and analysis,the algorithm can meet the speed requirement of collision detection in virtual assembly system.
To carry out collision detection quickly in complex mechanical product assembly simulation process,a collision detection algorithm based on double view and translucent color overlay was proposed.Through the multi-dimensional display projection,the collision detection problem in 3 Dspace of this algorithm was transformed into the traversal problem of planar pixels,which made up the shortcoming that most image-space collision detection algorithms could only judge whether the collision occurred,but could not find the distance.The algorithm was divided into three stages:block object determination,collision traversal and pixel traversal.The semi-transparent color overlay algorithm was used to quickly remove the parts without collision probability,and the potential occlusion object was determined;the potential collision surface was calculated by pixel depth value;the number of moving pixels was identified based on the horizontal perspective and the collision distance based on the number of pixels was calculated.Through the experiments and analysis,the algorithm can meet the speed requirement of collision detection in virtual assembly system.
引文
[1]PAN Renyu,SUN Changle,XIONG Wei,et al.Survey and prospect of collision detection based on virtual assembly environment[J].Computer Science,2016(S2):136-139(in Chinese).[潘仁宇,孙长乐,熊伟,等.虚拟装配环境中碰撞检测算法的研究综述与展望[J].计算机科学,2016(S2):136-139.]
[2]WANG Yi.Research on key technology of collision detection in virtual reality[D].Changchun:Jilin University,2009(in Chinese).[王祎.虚拟现实中碰撞检测关键技术研究[D].长春:吉林大学,2009.]
[3]CHANG J W,WANG W,KIM M S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design,2010,42(1):50-57.
[4]XIE Qianru,GENG Guohua.Fast collision detection method in virtual surgery[J].Journal of Computer Applications,2012,32(3):719-721(in Chinese).[谢倩茹,耿国华.虚拟手术中的快速碰撞检测算法[J].计算机应用,2012,32(3):719-721.]
[5]TANG Yong,YANG Sisi,LU Mengya,et al.Collision detection for cloth based on adaptive enclosing ellipsoids[J].Journal of Computer-Aided Design&Computer Graphics,2013,25(10):1589-1596(in Chinese).[唐勇,杨偲偲,吕梦雅,等.自适应椭球包围盒改进织物碰撞检测方法[J].计算机辅助设计与图形学学报,2013,25(10):1589-1596.]
[6]SHAO Xiaodong,GAO Wei,LIU Huanling.New collision detection algorithm based on adaptive tese lines[J].Computer Integrated Manufacturing Systems,2013,19(12):3147-3154(in Chinese).[邵晓东,高巍,刘焕玲.基于自适应检测线的碰撞检测算法[J].计算机集成制造系统,2013,19(12):3147-3154.]
[7]GOVINDARAJU N K,REDON S,LIN M C,et al.CUL-LIDE:interactive collision detection between complex models in large environments using graphics hardware[C]//Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware.Geneva,Switzerland:Eurographics Association,2003:25-32.
[8]WANG Ji,ZHAI Zhengjun,CAI Xiaobin.Real-time collision detection based on sphere depth texture[J].Journal of System Simulation,2007,19(11):2503-2506(in Chinese).[王季,翟正军,蔡小斌.基于球深度纹理的实时碰撞检测算法[J].系统仿真学报,2007,19(11):2503-2506.]
[9]ZHOU Yang,XU Qing,XIAO Yonghui.Research on collision detection algorithm based on Z_buffer[J].Computer Engineering,2007,33(12):214-216(in Chinese).[周杨,徐青,肖勇辉.基于Z_buffer值的碰撞检测算法研究[J].计算机工程,2007,33(12):214-216.]
[10]TANG Min,MANOCHA D,LIN Jiang,et al.Collisionstreams:fast GPU-based collision detection for deformable models[C]//Proceedings of Symposium on Interactive 3DGraphics and Games.New York,N.Y.,USA:ACM,2011:63-70.
[11]NICOLIN G,WILKE D N,KOK S.Collision detection of convex polyhedra on the NVIDIA GPU architecture for the discrete element method[J].Applied Mathematics and Computation,2015,267(15):810-829.
[12]LIU Liangping,LIU Zhen,FANG Hao,et al.GPU-based fluid collision detection method with surface of there-dimensional scenes[J].Journal of System Simulation,2015,27(10):2439-2445,2452(in Chinese).[刘良平,刘箴,方昊,等.基于GPU的三维场景表面流体碰撞检测方法研究[J].系统仿真学报,2015,27(10):2439-2445,2452.]
[13]KIM D,HEO J P,HUH J,et al.HPCCD:hybrid parallel continuous collision detection using CPUs and GPUs[J].Computer Graphics Forum,2009,28(7):1791-1800.
[14]YU Haijun,MA Chunyong,ZHANG Tao,et al.Fast collision detection algorithm based on image space[J].Journal of Computer Applications,2013,33(2):530-533(in Chinese).[于海军,马纯永,张涛,等.基于图像空间的快速碰撞检测算法[J].计算机应用,2013,33(2):530-533.]
[15]OSharp.Popularity of console games[EB/OL].[2017-06-12].http://bbs.a9vg.com/thread-3549729-1-1.html,2016-04-05/2016-04-05(in Chinese).[OSharp.主机游戏普及[EB/OL].[2017-06-12].http://bbs.a9vg.com/thread-3549729-1-1.html,2016-04-05/2016-04-05.]
[16]XU Wenpeng,WANG Yukun,LIU Yonghe.The foundations of computer graphics(OpenGL)[M].Beijing:Tsinghua University Press,2014:213-232(in Chinese).[徐文鹏,王玉琨,刘永和.计算机图形学基础(OpenGL版)[M].北京:清华大学出版社,2014:213-232.]
[17]ZOU Yisheng,DING Guofu,ZHOU Xiaoli,et al.Collision detection algorithm based on image space[J].Journal of System Simulation,2011,23(5):944-949(in Chinese).[邹益胜,丁国富,周晓莉,等.一种基于图像空间的碰撞检测算法[J].系统仿真学报,2011,23(5):944-949.]
[2]WANG Yi.Research on key technology of collision detection in virtual reality[D].Changchun:Jilin University,2009(in Chinese).[王祎.虚拟现实中碰撞检测关键技术研究[D].长春:吉林大学,2009.]
[3]CHANG J W,WANG W,KIM M S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design,2010,42(1):50-57.
[4]XIE Qianru,GENG Guohua.Fast collision detection method in virtual surgery[J].Journal of Computer Applications,2012,32(3):719-721(in Chinese).[谢倩茹,耿国华.虚拟手术中的快速碰撞检测算法[J].计算机应用,2012,32(3):719-721.]
[5]TANG Yong,YANG Sisi,LU Mengya,et al.Collision detection for cloth based on adaptive enclosing ellipsoids[J].Journal of Computer-Aided Design&Computer Graphics,2013,25(10):1589-1596(in Chinese).[唐勇,杨偲偲,吕梦雅,等.自适应椭球包围盒改进织物碰撞检测方法[J].计算机辅助设计与图形学学报,2013,25(10):1589-1596.]
[6]SHAO Xiaodong,GAO Wei,LIU Huanling.New collision detection algorithm based on adaptive tese lines[J].Computer Integrated Manufacturing Systems,2013,19(12):3147-3154(in Chinese).[邵晓东,高巍,刘焕玲.基于自适应检测线的碰撞检测算法[J].计算机集成制造系统,2013,19(12):3147-3154.]
[7]GOVINDARAJU N K,REDON S,LIN M C,et al.CUL-LIDE:interactive collision detection between complex models in large environments using graphics hardware[C]//Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware.Geneva,Switzerland:Eurographics Association,2003:25-32.
[8]WANG Ji,ZHAI Zhengjun,CAI Xiaobin.Real-time collision detection based on sphere depth texture[J].Journal of System Simulation,2007,19(11):2503-2506(in Chinese).[王季,翟正军,蔡小斌.基于球深度纹理的实时碰撞检测算法[J].系统仿真学报,2007,19(11):2503-2506.]
[9]ZHOU Yang,XU Qing,XIAO Yonghui.Research on collision detection algorithm based on Z_buffer[J].Computer Engineering,2007,33(12):214-216(in Chinese).[周杨,徐青,肖勇辉.基于Z_buffer值的碰撞检测算法研究[J].计算机工程,2007,33(12):214-216.]
[10]TANG Min,MANOCHA D,LIN Jiang,et al.Collisionstreams:fast GPU-based collision detection for deformable models[C]//Proceedings of Symposium on Interactive 3DGraphics and Games.New York,N.Y.,USA:ACM,2011:63-70.
[11]NICOLIN G,WILKE D N,KOK S.Collision detection of convex polyhedra on the NVIDIA GPU architecture for the discrete element method[J].Applied Mathematics and Computation,2015,267(15):810-829.
[12]LIU Liangping,LIU Zhen,FANG Hao,et al.GPU-based fluid collision detection method with surface of there-dimensional scenes[J].Journal of System Simulation,2015,27(10):2439-2445,2452(in Chinese).[刘良平,刘箴,方昊,等.基于GPU的三维场景表面流体碰撞检测方法研究[J].系统仿真学报,2015,27(10):2439-2445,2452.]
[13]KIM D,HEO J P,HUH J,et al.HPCCD:hybrid parallel continuous collision detection using CPUs and GPUs[J].Computer Graphics Forum,2009,28(7):1791-1800.
[14]YU Haijun,MA Chunyong,ZHANG Tao,et al.Fast collision detection algorithm based on image space[J].Journal of Computer Applications,2013,33(2):530-533(in Chinese).[于海军,马纯永,张涛,等.基于图像空间的快速碰撞检测算法[J].计算机应用,2013,33(2):530-533.]
[15]OSharp.Popularity of console games[EB/OL].[2017-06-12].http://bbs.a9vg.com/thread-3549729-1-1.html,2016-04-05/2016-04-05(in Chinese).[OSharp.主机游戏普及[EB/OL].[2017-06-12].http://bbs.a9vg.com/thread-3549729-1-1.html,2016-04-05/2016-04-05.]
[16]XU Wenpeng,WANG Yukun,LIU Yonghe.The foundations of computer graphics(OpenGL)[M].Beijing:Tsinghua University Press,2014:213-232(in Chinese).[徐文鹏,王玉琨,刘永和.计算机图形学基础(OpenGL版)[M].北京:清华大学出版社,2014:213-232.]
[17]ZOU Yisheng,DING Guofu,ZHOU Xiaoli,et al.Collision detection algorithm based on image space[J].Journal of System Simulation,2011,23(5):944-949(in Chinese).[邹益胜,丁国富,周晓莉,等.一种基于图像空间的碰撞检测算法[J].系统仿真学报,2011,23(5):944-949.]