基于优化Snake模型的变形物体碰撞检测算法研究

doi:10.16182/j.issn1004731x.joss.201801008

摘要/Abstract

摘要： 针对现有碰撞检测算法难以解决变形物体碰撞的实时性和逼真性问题,提出一种基于可变形物体的改进碰撞检测算法。该算法在K-dops(K-discrete orientation polytopes)包围盒基础上使用Snake模型应用于包围盒更新过程中,使用改进的Pso(Particle swarm optimization)算法对Snake模型进行边界优化。在优化过程中依据碰撞部位的内凹特性,在Snake模型控制点簇与中心点构成的多直线上,采用改进的粒子选取方式和多种群粒子优化算法思想构成多直线群体。实验结果表明,改进后的碰撞检测算法可以快速准确的模拟物体轮廓,简化了包围盒更新过程,提高了碰撞检测效率。

关键词: 碰撞检测, K-dops包围盒, 多直线群体, Pso算法, Snake模型

Abstract: In view of the existing collision detection algorithm which is difficult to solve the collision of real-time and reality, an improved algorithm of collision detection was propsed based on deformable objects. The algorithm based on K-DOPs bounding box applied to update process used the improved PSO algorithm to optimize the Snake model boundary. The concave in collision region, the control point clusters and the center formed multi-linear swarm with the improved selection method and the ulti PSO algorithm. Experimental results show that the improved collision detection algorithm can accurate simulate object contour, simplify the bounding box to improve the efficiency of collision detection.

Key words: detection, (K-dops) bounding box, multi-linear swarm, particle swarm optimization algorithm, snake model

中图分类号:

TP391.9

李照, 靳雁霞, 秦志鹏, 任超. 基于优化Snake模型的变形物体碰撞检测算法研究[J]. 系统仿真学报, 2018, 30(1): 62-68.

Li Zhao, Jin Yanxia, Qin Zhipeng, Ren Chao. Collision Detection Algorithm of Deformable Object Based on Snake Model Optimization[J]. Journal of System Simulation, 2018, 30(1): 62-68.

参考文献

[1] Du Peng, Tang Min, Tong RuoFeng. Fast Continuous Collision Culling with Deforming Non-collinear Filters[J]. Computer Animation&Virtual Worlds (S1546-427X), 2012, 23(3): 375-383.
[2] 付跃文, 梁加红, 李猛, 等. 基于多智能体粒子群的快速碰撞检测算法研究[J]. 系统仿真学报, 2013, 25(8): 1876-1880.Fu Yuewen, Liang Jiahong, Li Meng, et al. Research on Fast Collision Detection Using Multi-Agent Particle Swarm Optimization[J]. Journal of System Simulation, 2013, 25(8): 1876-1880.
[3] 黄欣, 杨文珍, 吴新丽, 等. 双触点虚拟织物触觉交互[J]. 系统仿真学报, 2014, 26(09): 1997-2008.Huang Xin, Yang Wenzen, Wu Xinli, et al. Virtual Fabric Haptic Rendering with Double Haptic Interactive Points[J]. Journal of System Simulation, 2014, 26(9): 1997-2008.
[4] 李文辉, 王天柱, 王祎, 等. 基于粒子群面向可变形物体的随机碰撞检测算法[J]. 系统仿真学报, 2006, 18(8): 2206-2209.Li Wenhui, Wang Tianzhu, Wang Wei, et al. Stochastic Collison Detection Between Deformable Models Using Particle Swarm Optimization Algorithm[J]. Journal of System Simulation, 2006, 18(8): 2206-2209.
[5] 李艳波, 印桂生, 张菁. 基于Snake模型的碰撞检测算法研究[J]. 计算机应用研究, 2009, 26(3): 855-857.Li Yanbo, Yin Guisheng, Zhang Jing. Research on collision detection methods based on snake[J]. Application Research of Computers, 2009, 26(3): 855-857.
[6] Li Yunqi.Collision Detection Algorithm for Deformable Objects[J]. Journal of Jilin University (S1671-5489), 2012, 30(3): 285-293.
[7] Christer Ericson.实时碰撞检测算法技术[M]. 刘天慧译. 北京: 清华大学出版社, 2010: 81. Christer Ericson. Real-time collision detection algorithm [M]. translation by Liu TianHui. Beijing: Tsinghua university press, 2010: 81.
[8] 陆睿, 刘卉. 基于完全二叉树BVH的自碰撞检测算法[J]. 计算机应用与软件, 2012, 29(12): 282-285. Lu Rui, Liu Hui. A Self-collision detection algorithm based on BVH of complete binary tree[J]. Computer Applications and software, 2012, 29(12): 282-285.
[9] 周旻曦, 刘永学, 李满春, 等. 多目标珊瑚岛礁地貌遥感信息提取方法——以西沙永乐环礁为例[J]. 地理研究, 2015, 34(4): 677-690. Zhou Minxi, Liu Yongxue, Li Manchun, et al. Geomorphologic information extraction for multi- objective coral islands from remotely sensed imagery: A case study for Yongle Atoll, South China Sea[J]. Geographical Research, 2015, 34(4): 677-690.
[10] 王科俊, 郭庆昌. 基于粒子群优化算法和改进的Snake模型的图像分割算法[J]. 智能系统学报, 2007, 2(1): 53-58. Wang Kejun, Guo Qingchang. Image segmentation algorithm based on th PSO and improved Snake model [J]. CAAI Transactions on Intelligent Systems, 2007, 2(1): 53-58.
[11] 钱建生, 厉丹. 基于PSO优化改进的Snake模型煤矿环境目标检测[J]. 煤炭学报, 2011, 36(11): 1949-1954. Qian Jiansheng, Li Dan. Snake model based on PSO optimization for coal mine enviroment object detection [J]. Journal of China Coal Cociety, 2011, 36(11): 1949-1954.
[12] Shi Y, Eberhart R.Fuzzy Adaptive Particle Swarm optimizer[C]//Proceedings of IEEE International Conference on Evolutionary Computation. Korea: IEEE Service Center, 2001: 1045-1048.
[13] 王根, 张建伟, 陈允杰, 等. 一种各向异性GVF模型的心脏左心室MR图像分割模型[J]. 计算机辅助设计与图形图像学报, 2010, 22(11): 1887-1891. Wang Gen, Zhang Jianwei, Chen Yunjie, et al. An Anisotropic GVF Model for the MR Image Segmentation of Left Ventricle[J]. Journal of Computer Aided Design and Computer Grapghics, 2010, 22(11): 1887-1891.
[14] 孙劲光, 吴素红. 基于分类遍历的碰撞检测优化算法[J]. 计算机应用, 2015, 35(1): 194-197. Sun Jinguang, Wu Sugong. Collision detection optimization algorithm based on classified traversal [J]. Journal of Computer Applications, 2015, 35(1): 194-197.