A Novel Algorithm for Collision Detection Based on Octree of Adaptive Subdivision and Encoding

Abstract

Abstract:

Abstract： A novel algorithm for collision detection in robot operation training system based on octree of adaptive subdivision and encoding algorithm was proposed in this paper. Using this method, this structure can not only guarantee the real-time, and has the good topology. This octree structure adopts three times of the average triangle of the axis aligned bounding box to set the cell size. It is reasonable and effective compared with the radius of sphere. Based on the triangle size and the optimal cell size, by using the adaptive triangular mesh subdivision and the centroid distance, the collision in the space was detected. The experimental simulation data verify the realtime and effectiveness of the method.

Key words: robot operation training system； octree structure； collision detection； encoding； triangle subdivision

CLC Number:

TP 242

BAO Yidong1, 2,WU Dongmei1. A Novel Algorithm for Collision Detection Based on Octree of Adaptive Subdivision and Encoding[J]. Journal of Shanghai Jiaotong University, 2015, 49(08): 1114-1122.

References

［1］Avril Q, Gouranton V, Arnaldi B. Dynamic adaptation of broad phase collision detection algorithms ［C］∥ IEEE International Symposium on Virtual Reality Innovation. Singapore：IEEE Computer Society Publishing, 2011：4147.

［2］Zhao W, Li L. A new KDOPs collision detection algorithms improved by GA ［C］∥ 1th International Conference on Wireless Communications and Applications. Sanya: Springer Verlag Publishing，2012：5868.

［3］王晓荣，王萌，李春贵. 基于AABB包围盒的碰撞检测算法的研究［J］. 计算机工程与科学，2010，32(4)： 5961.

WANG Xiaorong, WANG Meng, LI Chungui. Research of collision detection algorithms based on AABB ［J］. Computer Engineering & Science，2010，32(4)：5961.

［4］甘建红，彭强，戴培东,等. 基于 OBB 层次结构碰撞检测的改进算法［J］. 系统仿真学报，2011，32(10)： 21692173.

GAN Jianhong, PENG Qiang, DAI Peidong, et al. Improved collision detection algorithm Based on oriented bounding box ［J］. Journal of System Simulation，2011，32(10)：21692173.

［5］Anderson M, Ronan B, Daniel T. Efficient collision detection with in deforming spherical sliding contact ［J］. IEEE Transactions on Visualization and Computer Graphics，2007，13(3)：518529.

［6］Spillmann J, Becker M, Teschner M. Efficient updates of bounding sphere hierarchies for geometrically deformable models ［J］. Journal of Visual Communication and Image Representation，2007，18(2)：101108.

［7］Luque R, Comba J, Freitas C. Broadphase collision detection using semiadjusting BSPtrees ［C］∥Symposium on Interactive 3D Graphics and Games.Washington: Association for Computing Machinery Publishing，2005：179186.

［8］郭小明，崔建明，刘琼瑢,等. 虚拟视觉的Mesh方法与包围球方法研究［J］. 软件导报，2010，9(6)：2123.

GUO Xiaoming, CUI Jianming, LIU Qiongrong, et al. Study of Mesh and sphere bounding volumes method in virtual visual ［J］. Software Guide，2010，9(6)：2123.

［9］蒋健勋，方志刚，徐洁,等. 基于SphereOBB的改进碰撞检测算法及其应用［J］. 计算机工程与应用，2011，47(17)：172174.

JIANG Jianxun, FANG Zhigang, XU Jie, et al. Improved collision detection based on dual SphereOBB bounding volume hierarchy and its application ［J］. Computer Engineering and Applications，2011，47(17)：172174.

［10］秦铨，赵春江，肖伯祥，等. 基于AABBOBB盒的玉米叶片碰撞检测［J］. 农机化研究，2012(1)： 177180.

QIN Quan, ZHAO Chunjiang, XIAO Boxiang, et al. Collision detection for maize leaves based on AABBOBB bounding Volumes ［J］. Journal of Agricultural Mechanization Research， 2012(1)：177180.

［11］崔云飞, 苏凡囤, 王海涛，等. 基于八叉树精确划分型值点的碰撞检测算法［J］. 微型机与应用, 2013， 32(20)：8083.

CUI Yunfei, SU Fantun, WANG Haitao, et al. The algorithm of collision detection based on octrees of data points ［J］. Microcomputer & Its Applications， 2013，32(20)：8083.

［12］李山，赵伟，李菲. 一种基于八叉树与流水线技术的快速碰撞检测算法［J］. 计算机与现代化, 2011， 185(1)：2025.

LI Shan, ZHAO Wei, LI Fei. An algorithm of rapid collision detection based on octree and pipeline ［J］. Computer and Modernization，2011，185(1)：2025.

［13］Naylor B F. Interactive solid geometry via partitioning trees ［C］∥In Graphics Interface. Toronto: Canadian Information Processing Publishing, 1992：1118.

［14］Bentley J L, Friedman J H. Data structures for range searching ［J］. Computing surveys，1979，11(4)：397409.

［15］Wong T H, Leach G, Zambetta F. Virtual subdivision for GPU based collision detection of deformable objects using a uniform grid ［J］. Visual Computer，2012, 28：829838.

［16］Fan W S, Wang B, Paul J C, et al. An octreebased proxy for collision detection in largescale particle systems ［J］. Science ChinaInformation Sciences，2013，56(1)：110.

［17］Fujimotoa K, Kimuraa N, Moriyaa T. Method for fast detecting the intersection of a plane and a cube in an octree structure to find point sets within a convex region Intelligent Robots and Computer Vision ［C］∥ Algorithms and Techniques, Burlingame. Burlingame：SPIE Publishing，2012：110.

［18］Zou C M, Tang Z Y. The collision detection algorithm based on the combination of twodimensional and dynamic octree ［C］∥ International Conference on Environmental Science and Information Application Technology. Wuhan: IEEE Computer Society Publishing，2009：470473.

［19］Bandi S, Thalmann D. An adaptive spatial subdivision of the object space for fast collision detection of animated rigid bodies ［J］. Computer Graphics Forum，1995，14(3)：259270.

［20］Teschner M, Heidelberger B, Mueller M, et al. Optimized spatial hashing for collision detection of deformable objects ［C］∥ 8th Workshop on Vision, Modeling, and Visualization. Munich：CGL Publishing，2003：4754.

［21］Pabst S, Koch A, Strasser W. Fast and scalable CPU/GPU collision detection for rigid and deformable surfaces ［J］. Comput Graph，2010，29(6)：16051612.

［22］Fan W S, Wang B, Paul J C, et al. A hierarchical grid based framework for fast collision detection ［J］. Comput Graph，2011，30(5)：14511459.

［23］Eitz M. Hierarchical spatial hashing for realtime collision detection ［C］∥ IEEE International Conference on Shape Modeling and Applications. Lyon：Institute of Electrical and Electronic Engineering Computer Society Publishing，2007： 6168.

［24］Princeton Shape Benchmark. Princeton shape benchmark and analysis group ［EB/OL］. (20140303). http:∥shape.cs.princeton.edu/benchmark/.

[1]	WEN Yani, YAN Guozheng, WANG Zhiwu, JIANG Pingping, XUE Rongrong, WANG Yiyun. Design and Optimization of Three-Dimensional Receiving Coils for Intestinal Robots [J]. Journal of Shanghai Jiaotong University, 2020, 54(11): 1117-1123.
[2]	JING Xiaolong, HU Yuan, GUO Weizhong. High-Accuracy Calibration of Hand-Eye Matrix of Line-Structured Laser Sensor: Multiple Coordinates Transformation [J]. Journal of Shanghai Jiaotong University, 2020, 54(6): 607-614.
[3]	ZHANG Jianjun, WU Zhonghua, LIU Qunpo, WANG Hongqi, LIU Weidong. Bilateral Adaptive Impedance Control Scheme in Master-Slave Manipulator Teleoperation System [J]. Journal of Shanghai Jiaotong University, 2020, 54(6): 615-623.
[4]	ZHANG Tie, XIAO Meng, ZOU Yanbiao, XIAO Jiadong. Curved-Surface Constant Force Tracking Based on Fuzzy Iterative Method [J]. Journal of Shanghai Jiao Tong University, 2020, 54(4): 344-351.
[5]	GAO Jinyang, YAN Guozheng, SHI Yunbo, LIU Jun. Optimization of a Powering Coil Onboard a Dime-Size Inchworm-Like Robot for Exploring the Intestine [J]. Journal of Shanghai Jiaotong University, 2020, 54(2): 152-159.
[6]	PU Pengxian,YAN Guozheng,WANG Zhiwu,HAN Ding. Design and Experiment of Expanding Mechanism and Power Receiving Coil for Micro Intestinal Robot [J]. Journal of Shanghai Jiaotong University, 2019, 53(10): 1143-1150.
[7]	LU Shan,WANG Zhiwu,YAN Guozheng,ZHOU Zerun. Design and Experimental Verification of a Novel Puborectalis-Like Artificial Anal Sphincter [J]. Journal of Shanghai Jiaotong University, 2019, 53(10): 1151-1158.
[8]	ZHANG Jianjun,LIU Weidong,LI Le,CHENG Ruifeng,ZHENG Haifeng. Adaptive Impedance Control for Underwater Manipulator Intelligent Grasping in Unknown Environment [J]. Journal of Shanghai Jiaotong University, 2019, 53(3): 341-347.
[9]	SU Cheng,YE Jianan,LI Wei,DING Wangcai,ZHAO Zhigang. Analysis of Dynamic Workspace for Under-Constrained Coordinate Suspending System with Multi-Robots [J]. Journal of Shanghai Jiaotong University, 2019, 53(2): 225-231.
[10]	HU Bing,YANG Ming,GUO Lindong,WANG Chunxiang,WANG Bing. Global Localization for Intelligent Vehicles Using Ground SURF [J]. Journal of Shanghai Jiaotong University, 2019, 53(2): 203-208.
[11]	WU Wenhan,YANG Ming,WANG Bing,WANG Chunxiang. Pallet Detection Based on Contour Matching for Warehouse Robots [J]. Journal of Shanghai Jiaotong University, 2019, 53(2): 197-202.
[12]	YUAN Weia,b,YANG Minga,b,DENG Liuyuana,b,WANG Chunxiangc,WANG Binga,b. A Fast Method to Build Elevation Terrain Grid Map Using V-Disparity [J]. Journal of Shanghai Jiaotong University, 2018, 52(1): 1-6.
[13]	WANG Jiangbei,FANG Yeyang,TONG Xin,ZHANG Shuai,FEI Yanqiong. Design and Locomotion Properties of a Multi-Airbag Bionic Soft Robot [J]. Journal of Shanghai Jiaotong University, 2018, 52(1): 20-25.
[14]	SHEN Yue1,JIANG Zhihua2,YAN Guozheng1,KE Quan1,WANG Yongbing1. Optimization and Realization of Wireless Capsule Robot [J]. Journal of Shanghai Jiaotong University, 2018, 52(1): 39-44.
[15]	ZHAO Guoqia,b,YANG Minga,b,WANG Binga,b,WANG Chunxiangc. Mobile Robot Seamless Localization Based on Smart Device in Indoor and Outdoor Environments [J]. Journal of Shanghai Jiaotong University, 2018, 52(1): 13-19.