基于体素网格划分的二维DDA接触粗检测优化算法

doi:10.7523/j.ucas.2021.0071

中国科学院大学学报 ›› 2023, Vol. 40 ›› Issue (4): 540-546.DOI: 10.7523/j.ucas.2021.0071

• 电子信息与计算机科学 • 上一篇下一篇

基于体素网格划分的二维DDA接触粗检测优化算法

程晓龙, 程章焱, 肖俊, 张龙, 王颖

中国科学院大学人工智能学院, 北京 100049

收稿日期:2021-06-25 修回日期:2021-10-28 发布日期:2023-07-07
通讯作者: 肖俊,E-mail:xiaojun@ucas.ac.cn
基金资助:
中国科学院战略性先导科技专项（A类）（XDA23090304）、中国博士后科学基金（2019M650816）、国家自然科学基金（U2003109）、中国科学院青年创新促进会优秀会员项目（Y201935）和中央高校基本科研业务费专项资助

Voxel-based meshing collision detection accelerating algorithm for DDA2D

CHENG Xiaolong, CHENG Zhangyan, XIAO Jun, ZHANG Long, WANG Ying

School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing 100049, China

Received:2021-06-25 Revised:2021-10-28 Published:2023-07-07

摘要/Abstract

摘要： 接触检测在非连续变形分析方法计算流程中耗时占比最高。提出一种高效的基于体素网格划分的接触粗检测算法。该算法将符合特定条件的复杂块体剖到网格中，有效减少预检测获得的块体对数。本文的算法已整合到非连续变形分析程序中，经过经典算例测试，该算法相比现有算法优势明显。

关键词: 体素网格划分, 二维DDA, 接触粗检测

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

中图分类号:

TP391.9

程晓龙, 程章焱, 肖俊, 张龙, 王颖. 基于体素网格划分的二维DDA接触粗检测优化算法[J]. 中国科学院大学学报, 2023, 40(4): 540-546.

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.

参考文献

[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.

基于体素网格划分的二维DDA接触粗检测优化算法

Voxel-based meshing collision detection accelerating algorithm for DDA2D

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	赵明浩, 周以国. 相控阵天线波束形成联合优化算法研究^*[J]. 中国科学院大学学报, 0, (): 0-.
[2]	王贺, 卜智勇, 谭冲. 基于核相关滤波视觉检测的多旋翼无人机对地目标跟踪与逼近[J]. 中国科学院大学学报, 2022, 39(2): 217-223.
[3]	杨善强, 李华旺, 常亮, 高才栋, 虞业泺. 一种基于RPC的组态化卫星模拟器故障注入方法[J]. 中国科学院大学学报, 2021, 38(3): 402-408.
[4]	沈振涯, 肖俊, 王颖, 隋红建. 裂隙岩体块体几何识别研究[J]. 中国科学院大学学报, 2012, 29(1): 81-87.
[5]	陈兆兵, 郭劲, 王兵, 韩旭东. 摆镜式IRST反射镜支架结构设计与优化[J]. 中国科学院大学学报, 2011, 28(2): 155-160.
[6]	崔明路, 王治强, 刘薇. 一种星地量子密钥通信仿真平台[J]. 中国科学院大学学报, 2011, 28(2): 241-245.
[7]	王兆其. 虚拟人合成研究综述[J]. 中国科学院大学学报, 2000, 17(2): 89-98.