依赖表面提取的二次空间分解碰撞检测方法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (5): 156-159.

• 图形、图像、模式识别 • 上一篇下一篇

依赖表面提取的二次空间分解碰撞检测方法

王娟¹，赖思渝²，李明东¹

1.西华师范大学计算机学院，四川南充 637002
2.川北医学院医学影像学系，四川南充 637000

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-02-11 发布日期:2011-02-11

Twice space division collision detection method based on surface extraction

WANG Juan¹，LAI Siyu²，LI Mingdong¹

1.School of Computer Science，China West Normal University，Nanchong，Sichuan 637002，China
2.Department of Medical Imaging，North Sichuan Medical College，Nanchong，Sichuan 637000，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-02-11 Published:2011-02-11

摘要/Abstract

摘要： 为了提高空间分解碰撞检测算法的性能，提出了一种基于表面提取的二次空间分解碰撞检测算法。该算法在预处理阶段首先建立碰撞检测体的三维模型，进行第一次空间剖分，利用表面提取方法抽取包含碰撞体表面的单元格，使得参与碰撞检测的三角面片大幅减少。在检测阶段进行第二次剖分，通过计算待检物体包围盒树深度与给定值μ的大小关系，生成称作Adjacent的数据结构，采用遍历跟踪的策略记录遍历过程，当拓扑结构发生变化时根据遍历跟踪表的记录调整遍历方案可缩短遍历路径，节省运算时间，进一步提高算法性能。实验通过与Rapid、I-Collide算法的比较表明，提出的算法提高了检测效率。

关键词: 碰撞检测, 空间剖分, 表面提取, 遍历跟踪, 邻接表

Abstract: In order to improve the division performance of collision detection algorithm，the twice space division collision detection algorithm is proposed based on surface extraction.Three-dimensional model of body is established in the pre-processing stage.The first space subdivision is performed and surface extraction method is used to pick up collision cell that contains body surface which makes the triangle number of collision detection substantially reduced.In second stage（Detection stage），by means of calculating the value between the to be detected object’s depth of bounding box tree and the given μ，the data structure named as Adjacent is generated just because of the traversal track strategy.When topology is changed according to the records of traversal tracking table，traversal project can shorten the traversal path and save computing time.Comparison with the Rapid、I-Collide method shows that the proposed algorithm improves the detection performance.

Key words: Collision detection, space division, surface extraction, traversal track, adjacent table

王娟¹，赖思渝²，李明东¹. 依赖表面提取的二次空间分解碰撞检测方法[J]. 计算机工程与应用, 2011, 47(5): 156-159.

WANG Juan¹，LAI Siyu²，LI Mingdong¹. Twice space division collision detection method based on surface extraction[J]. Computer Engineering and Applications, 2011, 47(5): 156-159.

[1]	杜豪，杨岩，张成杰. 虚拟现实技术在柔性上肢康复机器人中的应用[J]. 计算机工程与应用, 2020, 56(24): 260-265.
[2]	张功森，郭翌，李永哲，裴曦，徐榭，周解平. 结合增强现实的医用加速器碰撞检测方法[J]. 计算机工程与应用, 2020, 56(17): 197-202.
[3]	吴其凡1，张劲1，刘凯1，汤炜2，田卫东2. 下颌骨拼接与导板设计的力反馈虚拟手术研究[J]. 计算机工程与应用, 2019, 55(5): 226-231.
[4]	刘满禄1，2，李铭浩2，敖天翔2，赵皓1，2. 危险环境消防侦察机器人视轴规划算法研究[J]. 计算机工程与应用, 2018, 54(23): 217-222.
[5]	孙敬荣1，2，卢新明1，2. 基于混合包围盒与三角形相交的碰撞检测优化算法[J]. 计算机工程与应用, 2018, 54(19): 198-203.
[6]	郑星星，谢明鸿，张亚运. 基于空间划分和线性规划的快速碰撞检测算法[J]. 计算机工程与应用, 2017, 53(23): 236-240.
[7]	靳雁霞，任超，李照，程思岳，王贺，韩慧妍. 融合智能算法的变形体碰撞检测算法研究[J]. 计算机工程与应用, 2017, 53(19): 130-135.
[8]	王发麟，郭宇，廖文和，黄少华. 基于距离场和扫掠剪除算法的线缆碰撞检测技术[J]. 计算机工程与应用, 2017, 53(10): 27-34.
[9]	孙劲光1，吴素红2. 基于空间分割与椭球包围盒的碰撞检测算法[J]. 计算机工程与应用, 2016, 52(4): 217-222.
[10]	沈学利，王瑞新. 基于改进粒子群的快速碰撞检测算法研究[J]. 计算机工程与应用, 2016, 52(22): 49-54.
[11]	董晓芬1，2，张伟1，庞明勇1，2. 空间剖分树形查找结构的效率分析[J]. 计算机工程与应用, 2016, 52(15): 73-78.
[12]	谭睿璞1，赵伟2. 一种快速的可变形物体的碰撞检测算法[J]. 计算机工程与应用, 2014, 50(9): 170-175.
[13]	张国飚，张华，刘满禄，余慧. 基于空间剖分的碰撞检测算法研究[J]. 计算机工程与应用, 2014, 50(7): 46-49.
[14]	王立文，李洪帅. 机场消防车辆模拟器的视景系统研究[J]. 计算机工程与应用, 2012, 48(7): 238-241.
[15]	姜晓路1，2，刘渊2. 一种新的基于混合层次包围盒的碰撞检测算法[J]. 计算机工程与应用, 2012, 48(6): 143-145.

依赖表面提取的二次空间分解碰撞检测方法

Twice space division collision detection method based on surface extraction

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics