层次八叉的三维模型并行碰撞检测
|
摘要
针对复杂虚拟场景中碰撞检测效率低、精度差等问题,基于层次八叉包围盒的构建,提出多线程并行碰撞检测算法。构建三维网格模型的层次八叉包围盒,采用多线程并行的算法实现多层次包围盒的并行碰撞检测,基于动态任务分配策略,在保证负载均衡度的前提下提高检测速度和检测精度。相关实验结果表明了该算法的有效性。
To deal with the problem of low efficiency and low precision of the collision detection in the virtual environments,based on the construction of hierarchical octree bounding box,a multi-thread parallel collision detection algorithm was proposed.The hierarchical octree bounding-box of 3D mesh model was constructed,and parallel collision detection was realized using multithread parallel algorithm.Based on the dynamic task allocation strategy,the detection speed and detection precision were improved on the premise of guaranteeing load balancing.The results of the experiment demonstrate the effectiveness of the proposed algorithm.
To deal with the problem of low efficiency and low precision of the collision detection in the virtual environments,based on the construction of hierarchical octree bounding box,a multi-thread parallel collision detection algorithm was proposed.The hierarchical octree bounding-box of 3D mesh model was constructed,and parallel collision detection was realized using multithread parallel algorithm.Based on the dynamic task allocation strategy,the detection speed and detection precision were improved on the premise of guaranteeing load balancing.The results of the experiment demonstrate the effectiveness of the proposed algorithm.
引文
[1]ZHANG Zhi,ZOU Shengtao,LI Jiatong,et al.A collision detection algorithm between convex polyhedrons based on projection of edges[J].Journal of Computer-Aided Design and Computer Graphics,2015,27(8):1407-1415(in Chinese).[张智,邹盛涛,李佳桐,等.凸多面体碰撞检测的棱线投影分离算法[J].计算机辅助设计与图形学学报,2015,27(8):1407-1415.]
[2]Feito FR,Ogayar CJ,Segura RJ,et al.Fast and accurate evaluation of regularized Boolean operations on triangulated solids[J].Computer-Aided Design,2013,45(3):705-716.
[3]Carsten Burstedde,Lucas C Wilcox,Omar Ghattas.p4est:Scalable algorithms for parallel adaptive mesh refinement on forests of octrees[J].SIAM Journal on Scientific Computing,2015,33(3):1103-1133.
[4]Schwesinger U,Siegwart R,Furgale P.Fast collision detection through bounding volume hierarchies in workspace-time space for sampling-based motion planners[C]//Robotics and Automation.IEEE,2015:63-68.
[5]Zhu S,Jin X,Jin L.An octree-based grouping recoding RFID anti-collision algorithm[C]//IEEE International Conference on Software Engineering and Service Science,2015:758-761.
[6]Camata JJ,Aveleda AA,Coutinho ALGA. Measuring performance of a parallel octree-based finite element mesh generator on SDumont machine[C]//CARLA Latin America High Performance Computing Conference.2015.
[7]Aguilera A,Melero FJ,Feito FR.Out-of-core real-time haptic interaction on very large models[J].Computer-Aided Design,2016,77(C):98-106.
[8]Qian C,Lin W,Chen J,et al.Point cloud trajectory planning based on Octree and K-dimensional tree algorithm[C]//Chinese Association of Automation.IEEE,2016:213-218.
[9]Albin Hermansson.View-dependent collision detection and response using octrees[D].Karlskrona:Blekinge Institute of Technology,2016.
[10]Wang Pengshuai,Liu Yang,Guo Yuxiao,et al.O-CNN:Octree-based convolutional neural networks for 3Dshape analysis[J].ACM Transactions on Graphics(SIGGRAPH),2017,36(4):72:1-72:11.
[11]PAN Hai’ou,DAI Jun,CHEN Lin,et al.Multi-robot parallel dynamic bounding volume hierarchy tree collision detection algorithm[J].Journal of Computer-Aided Design and Computer Graphics,2014,26(11):1948-1956(in Chinese).[潘海鸿,戴骏,陈琳,等.多机器人并行动态包围体层次树碰撞检测算法[J].计算机辅助设计与图形学学报,2014,26(11):1948-1956.]
[12]Fei Y,Song Y,Sun G.Closest distance searching by GPUbased massive parallel computation[C]//Cyber Technology in Automation,Control,and Intelligent Systems.IEEE,2015:2036-2039.
[2]Feito FR,Ogayar CJ,Segura RJ,et al.Fast and accurate evaluation of regularized Boolean operations on triangulated solids[J].Computer-Aided Design,2013,45(3):705-716.
[3]Carsten Burstedde,Lucas C Wilcox,Omar Ghattas.p4est:Scalable algorithms for parallel adaptive mesh refinement on forests of octrees[J].SIAM Journal on Scientific Computing,2015,33(3):1103-1133.
[4]Schwesinger U,Siegwart R,Furgale P.Fast collision detection through bounding volume hierarchies in workspace-time space for sampling-based motion planners[C]//Robotics and Automation.IEEE,2015:63-68.
[5]Zhu S,Jin X,Jin L.An octree-based grouping recoding RFID anti-collision algorithm[C]//IEEE International Conference on Software Engineering and Service Science,2015:758-761.
[6]Camata JJ,Aveleda AA,Coutinho ALGA. Measuring performance of a parallel octree-based finite element mesh generator on SDumont machine[C]//CARLA Latin America High Performance Computing Conference.2015.
[7]Aguilera A,Melero FJ,Feito FR.Out-of-core real-time haptic interaction on very large models[J].Computer-Aided Design,2016,77(C):98-106.
[8]Qian C,Lin W,Chen J,et al.Point cloud trajectory planning based on Octree and K-dimensional tree algorithm[C]//Chinese Association of Automation.IEEE,2016:213-218.
[9]Albin Hermansson.View-dependent collision detection and response using octrees[D].Karlskrona:Blekinge Institute of Technology,2016.
[10]Wang Pengshuai,Liu Yang,Guo Yuxiao,et al.O-CNN:Octree-based convolutional neural networks for 3Dshape analysis[J].ACM Transactions on Graphics(SIGGRAPH),2017,36(4):72:1-72:11.
[11]PAN Hai’ou,DAI Jun,CHEN Lin,et al.Multi-robot parallel dynamic bounding volume hierarchy tree collision detection algorithm[J].Journal of Computer-Aided Design and Computer Graphics,2014,26(11):1948-1956(in Chinese).[潘海鸿,戴骏,陈琳,等.多机器人并行动态包围体层次树碰撞检测算法[J].计算机辅助设计与图形学学报,2014,26(11):1948-1956.]
[12]Fei Y,Song Y,Sun G.Closest distance searching by GPUbased massive parallel computation[C]//Cyber Technology in Automation,Control,and Intelligent Systems.IEEE,2015:2036-2039.