Voxel-based meshing collision detection accelerating algorithm for DDA2D

doi:10.7523/j.ucas.2021.0071

Abstract

Abstract: Contact detection takes the most time in the calculation process of discontinuous deformation analysis method. Contact detection consists of two steps:contact coarse detection and contact precise detection; contact coarse detection searches all possible block pairs in the calculation space; the contact precise detection determines the specific contact position for the block pairs from the contact coarse detection results for subsequent mechanical treatment. In this paper, an efficient contact coarse detection algorithm based on voxel meshing is proposed. The algorithm divides the complex blocks that meet the specific conditions into sub grids, which effectively reduces the number of generated pre-detected blocks. The algorithm has been integrated into the discontinuous deformation analysis program and tested by classical examples. The results show that the proposed algorithm has obvious advantages over the existing algorithms.

Key words: voxel-based meshing, 2D-DDA, contact coarse detection

CLC Number:

TP391.9

CHENG Xiaolong, CHENG Zhangyan, XIAO Jun, ZHANG Long, WANG Ying. Voxel-based meshing collision detection accelerating algorithm for DDA2D[J]. Journal of University of Chinese Academy of Sciences, 2023, 40(4): 540-546.

References

[1] SHI G H. Discontinuous deformation analysis:a new numerical model for the statics and dynamics of block system[D]. Berkeley:Department of Civil, University of California, 1988.
[2] Zhang R, Liu X G, Wei J J. Collision detection based on OBB simplified modeling[J]. Journal of Physics:Conference Series, 2019, 1213(4):042079(6pp). DOI:10.1088/1742-6596/1213/4/042079.
[3] Munjiza A, Andrews K R F. NBS contact detection algorithm for bodies of similar size[J]. International Journal for Numerical Methods in Engineering, 1998, 43(1):131-149. DOI:10.1002/(SICI)1097-0207(19980915)43:1<131::AID-NME447>3.0.CO;2-S.
[4] Perkins E, Williams J R. A fast contact detection algorithm insensitive to object sizes[J]. Engineering Computations, 2001, 18(1/2):48-62. DOI:10.1108/02644400110365770.
[5] 王晓荣, 王萌, 李春贵. 基于AABB包围盒的碰撞检测算法的研究[J]. 计算机工程与科学, 2010, 32(4):59-61. DOI:10.3969/j.issn.1007-130X.2010.04.017.
[6] 王太勇,王国锋. 基于HV分割的精确碰撞检测在虚拟设计中的应用[J]. 机械设计, 2001, 18(12):12-14. DOI:10.3969/j.issn.1001-2354.2001.12.005.
[7] Wu W, Zhu H H, Zhuang X Y, et al. A multi-shell cover algorithm for contact detection in the three dimensional discontinuous deformation analysis[J]. Theoretical and Applied Fracture Mechanics, 2014, 72:136-149. DOI:10.1016/j.tafmec.2014.03.004.
[8] Wang X, Wu W, Zhu H H, et al. Contact detection between polygonal blocks based on a novel multi-cover system for discontinuous deformation analysis[J]. Computers and Geotechnics, 2019, 111:56-65. DOI:10.1016/j.compgeo.2019.03.004.
[9] 王振文,徐华. 复杂场景中基于拓扑空间网格的碰撞检测算法[J].计算机系统应用, 2017, 26(12):116-123. DOI:10.15888/j.cnki.csa.006031.
[10] Echegaray G, Borro D. A methodology for optimal voxel size computation in collision detection algorithms for virtual reality[J]. Virtual Reality, 2012, 16(3):205-213. DOI:10.1007/s10055-011-0199-5.
[11] Wang H Y, Liu S G. A collision detection algorithm using AABB and octree space division[J]. Advanced Materials Research, 2014, 3326(1983):2389-2392. DOI:10.4028/www.scientific.net/AMR.989-994.2389.
[12] Melero F J, Aguilera Á, Feito F R. Fast collision detection between high resolution polygonal models[J]. Computers & Graphics, 2019, 83:97-106. DOI:10.1016/j.cag.2019.07.006.
[13] Frisken S F, Perry R N. Simple and efficient traversal methods for quadtrees and octrees[J]. Journal of Graphics Tools,2002,7(3):1-11. DOI:10.1080/10867651.2002.10487560.
[14] Heo Y J, Kim D, Lee W, et al. Collision detection for industrial collaborative robots:a deep learning approach[J]. IEEE Robotics and Automation Letters, 2019, 4(2):740-746. DOI:10.1109/LRA.2019.2893400.
[15] 朱二喜, 徐敏, 何援军. 一种利用Delaunay三角剖分的碰撞检测算法[J]. 图学学报, 2015, 36(4):516-520. DOI:10.3969/j.issn.2095-302X.2015.04.004.