自适应细分及优化编码八叉树碰撞检测算法

摘要/Abstract

摘要：

摘要：基于自适应三角网格划分和优化编码八叉树结构，在机器人虚拟手术训练系统中提出一种新的碰撞检测方法.采用该方法实现的八叉树结构占用存储空间小，且在具有良好的拓扑结构下又能保证实时性要求.八叉树结构中采用物体三角面片AABB包围盒平均边长的3倍设置八叉树空间单元大小，与已有文献采用包围球半径来设置八叉树空间单元大小相比，设置的单元大小合理有效，速度更快.最后根据三角形与最优单元大小相关性，通过自适应三角网格细分，利用三角形中心距离方法检测单元空间中三角形碰撞.实验仿真数据验证了该方法的实时性和有效性.

关键词: 机器人手术训练系统, 八叉树结构, 碰撞检测, 编码, 三角形细分

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

中图分类号:

TP 242

鲍义东1,2，吴冬梅1. 自适应细分及优化编码八叉树碰撞检测算法[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1114-1122.

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.

参考文献

［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]	张晏合, 臧月进, 陈渤, 徐铭晟. 基于解耦表征变分自编码机的雷达目标识别算法[J]. 空天防御, 2022, 5(2): 87-93.
[2]	金丽洁, 武亚涛. 基于双CNN的雷达信号调制类型识别方法[J]. 空天防御, 2022, 5(1): 66-70.
[3]	梁培基. 大脑如何进行神经信息编码与处理？[J]. 上海交通大学学报, 2021, 55(Sup.1): 12-13.
[4]	袁铭, 刘群, 孙海超, 谭洪胜. 基于变分推断和元路径分解的异质网络表示方法[J]. 上海交通大学学报, 2021, 55(5): 586-597.
[5]	胡锦昊, 王明昊, 夏天扬, 王悦行, 杜海静, 徐传刚. 基于HSV色彩空间的红外与可见光图像融合方法[J]. 空天防御, 2021, 4(4): 87-94.
[6]	姜宇迪, 胡晖, 殷跃红. 基于无监督迁移学习的电梯制动器剩余寿命预测[J]. 上海交通大学学报, 2021, 55(11): 1408-1416.
[7]	朱宏伟, 陆志强. 考虑人力资源排班的资源受限项目调度问题建模与优化[J]. 上海交通大学学报, 2020, 54(6): 624-635.
[8]	马斌彬，马红占，褚学宁，李玉鹏. 基于稀疏自编码神经网络的产品再设计模块识别方法[J]. 上海交通大学学报, 2019, 53(7): 838-843.
[9]	吴长征1，岳义1,2，韦宝琛1，刘殿富3. 双臂机器人自碰撞检测及其运动规划[J]. 上海交通大学学报（自然版）, 2018, 52(1): 45-53.
[10]	刘琼霄1，陈昂杨2，丛慧2，丁良辉2，杨峰2，钱良2. 无线网络编码随机优先级检测调度算法[J]. 上海交通大学学报（自然版）, 2017, 51(5): 603-.
[11]	秦利国a，何潇a,b，周东华a,b. 一种基于鲁棒残差生成器的故障估计方法[J]. 上海交通大学学报（自然版）, 2015, 49(06): 768-774.
[12]	耿烜1，孙作雷1，刘锋1，何迪2. 基于块对角化的最小均方误差矢量预编码[J]. 上海交通大学学报（自然版）, 2014, 48(10): 1410-1414.
[13]	苏锦海，栾欣，郭义喜，赵红涛. 一种适用于量子密钥分配网络的组密钥协商方案[J]. 上海交通大学学报（自然版）, 2014, 48(10): 1498-1502.
[14]	黄太安, 宋峥嵘, 喻龙, 张小钢, 蒋小华, 王佳, 徐庚, 尹宝瑞. VPRM材料编码在海洋石油工程建造中的深化应用[J]. 海洋工程装备与技术, 2014, 1(1): 91-94.
[15]	杜继永1, 2，张凤鸣1，惠晓滨1，李永宾1. 改进型连续粒子群算法求解重叠联盟生成问题[J]. 上海交通大学学报（自然版）, 2013, 47(12): 1918-1923.