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]	LIUYongfei. Simulation Analysis of a Subsea Hydraulic Control System Based on SimulationX [J]. Ocean Engineering Equipment and Technology, 2022, 9(1): 1-7.
[2]	WANGJuan, ZHENG Maoyao, ZHANGZiliang, SONGGuangxing, ZHANGLei. Precision Control Technology for Large Semi-Submersible Platforms [J]. Ocean Engineering Equipment and Technology, 2022, 9(1): 21-26.
[3]	WANGJuan, YANG Mingwang, ZHENG Maoyao, LIULingyun, ZHAOLijun. Application of High Strength Steelin Construction of Large Semi-Submersible Platforms [J]. Ocean Engineering Equipment and Technology, 2022, 9(1): 27-31.
[4]	LIU Hao , ZHANGNing , WANG Huoping , ZHU Liyun , ZHANG Yu . A Method for Improving the Motion Performance of Steel Catenary Riser by Adding Inertia Bodies to the Sagbend Section #br# [J]. Ocean Engineering Equipment and Technology, 2022, 9(1): 37-45.
[5]	YIN Yankun, YI Difei. Engineering Criticality Assessment of Key Joint for Hull Structure of Semi-Submersible Floating Production Unit [J]. Ocean Engineering Equipment and Technology, 2022, 9(1): 52-57.
[6]	LUO Ruiqiao. Application of Down hole Throttle Technology in High Temperature Gas Fields in Eastern South China Sea [J]. Ocean Engineering Equipment and Technology, 2022, 9(1): 58-66.
[7]	MA Qunsheng (马群圣), CEN Xingxing (岑星星), YUAN Junyi (袁骏毅), HOU Xumin (侯旭敏). Word Embedding Bootstrapped Deep Active Learning Method to Information Extraction on Chinese Electronic Medical Record [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 494-502.
[8]	ZHANG Shengfa (张胜发), TANG Na (唐纳), SHEN Guofeng (沈国峰), WANG Han (王悍), QIAO Shan (乔杉). Universal Software Architecture of Magnetic Resonance-Guided Focused Ultrasound Surgery System and Experimental Study [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 471-481.
[9]	KONG Xiangqiang (孔祥强), MENG Xiangxi (孟祥熙), LI Jianbo (李见波), SHANG Yanping (尚燕平), CUI Fulin (崔福林) . Comparative Study on Two-Stage Absorption Refrigeration Systems with Different Working Pairs [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 155-162.
[10]	ZHUANG Weimin (庄蔚敏), WANG Pengyue (王鹏跃), AO Wenhong (熬文宏), CHEN Gang (陈刚) . Experiment and Simulation of Impact Response of Woven CFRP Laminates with Different Stacking Angles [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 218-230.
[11]	ZHOU Xuhui (周旭辉), ZHANG Wenguang (张文光), XIE Jie (谢颉). Effects of Micro-Milling and Laser Engraving on Processing Quality and Implantation Mechanics of PEG-Dexamethasone Coated Neural Probe [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 1-9.
[12]	HUANG Ningning (黄宁宁), MA Yixin (马艺馨), ZHANG Mingzhu (张明珠), GE Hao (葛浩), WU Huawei (吴华伟). Finite Element Modeling of Human Thorax Based on MRI Images for EIT Image Reconstruction [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 33-39.
[13]	WANG Xianjin, GAO Xu, YU Kuigang . Fixture Locating Modelling and Optimization Research of Aluminum Alloy Sidewall in a High-Speed Train Body [J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 706-713.
[14]	QIAO Xing, MA Dan, YAO Xuliang, FENG Baolin. Stability and Numerical Analysis of a Standby System [J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 769-778.
[15]	WU Jin, MIN Yu, YANG Xiaodie, MA Simin . Micro-Expression Recognition Algorithm Based on Information Entropy Feature [J]. Journal of Shanghai Jiao Tong University(Science), 2020, 25(5): 589-599.