1 项目背景
随着计算机软硬件技术的飞速发展，碰撞检测已经成为计算机图形学和虚拟现实的一个基本问题，广泛应用于CAD/CAM、计算机动画、飞机和汽车驾驶模拟（Flight and vehicle simulators）、机器人、路径和运动规划（Path and motion planning）、装配（Assembly）、虚拟制造（Virtual manufacturing）、物理仿真模拟、电脑游戏等领域。
图 1. 虚拟驾驶
图 2. 物理仿真模拟 图 3. 虚拟制造
过去，3D动态物体之间的碰撞检测一直是计算机图形学应用和虚拟仿真开发障碍和技术瓶颈。在本项目中，我们将利用M2M算法模型（Marco to Micro Model）设计的碰撞检测算法，结合简易的物理引擎来模拟3D物体碰撞，最终制作成一款3D太空桌球游戏。基于M2M的碰撞检测算法是一种空间分解的碰撞检测方法，它源于我们在研究中提出一种层次数据结构——M2M数据结构。相比于其他基于空间分解的数据结构,这个数据结构具有并行性、动态性等一些优势，在解决多操作问题的时候，可以大大提高处理效率，特别适合未来计算机将要处的越来越复杂的实际问题。使用M2M碰撞检测算法，我们不用再花费巨额费用采购大型工作站。
2 国内外研究状况
近十年来，研究者提出了各种解决方案。从解决方法上看，碰撞检测大致可分为空间分解法和包围盒法。空间分解法是把整个包含所有物体的空间分解成若干个子空间，再通判断这些物体是否占据相同的子空间排除一部分不会相交的物体，对于其子空间相交的物体作进一步的判断处理。空间分解的实现方法有八叉树等。包围盒法是用一个或多个容易计算的多面体包围空间里的每一个物体，再通过判断这些多面体是否相交排除一部分不会相交的物体，对于其包围盒相交的物体作进一步的判断处理。常见的包围盒有AABB包围盒、OBB包围盒、k-DOP包围盒等。为了进一步精确的包围物体，各种树结构如BSP树、K-D树、八叉树等也被应用到对包围盒的分解当中。
图4.计算机游戏 图5.三维动画
3 系统架构图
图6 系统架构图
图7 游戏效果图 图8 游戏界面图
