接触检测在非连续变形分析方法计算流程中耗时占比最高。提出一种高效的基于体素网格划分的接触粗检测算法。该算法将符合特定条件的复杂块体剖到网格中，有效减少预检测获得的块体对数。本文的算法已整合到非连续变形分析程序中，经过经典算例测试，该算法相比现有算法优势明显。
程晓龙
,
程章焱
,
肖俊
,
张龙
,
王颖
. 基于体素网格划分的二维DDA接触粗检测优化算法[J]. 中国科学院大学学报, 2023
, 40(4)
: 540
-546
.
DOI: 10.7523/j.ucas.2021.0071
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.
[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.
