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

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

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