碰撞检测问题是计算机仿真、CAD、机器人中的一个基本问题,主要用于提高虚拟场景的真实感或进行机器人的路径规划等。不同的碰撞检测基于不同的应用,因此提供的信息也不同。有的应用需要碰撞检测算法给出两物体沿各自运动路径运动过程中是否发生碰撞,有的应用则需要碰撞检测算法不仅给出两物体运动过程中是否碰撞,还需要提供距离信息,即两物体发生碰撞时它们之间的最短穿刺距离,或者两个在运动路径上没有碰撞的物体,它们之间的最短分离距离。目前已有很多种碰撞检测方法,但主要分为两大类:一类是离散的碰撞检测,如基于计算几何的方法、基于分离平面的方法、基于图形硬件的方法等;一类是连续碰撞检测,如扫描卷方法、基于对偶和Minkowski和的方法、代数方法等。离散的碰撞检测方法是对两运动物体在时间轴上采样,在每个采样时刻判断两静态物体是否碰撞。在离散的碰撞检测方法中,如果物体运动速度很快或者物体很小,有可能会检测不到取样时间间隔之内发生的碰撞;缩短采样的时间间隔可以提高精度,但是会降低效率。连续碰撞检测的方法对物体的运动过程进行建模,构造出一条连续的路径,基于路径判断物体间的碰撞情况。本文提出了两个算法,一个是研究利用代数方法进行连续的碰撞检测,对两个运动的复合圆锥体进行碰撞检测,另外一个是用几何方法计算两个运动的复合圆锥体的最近距离并进行碰撞检测。代数方法的求解过程是把两个物体静止时的碰撞条件表达成一个代数条件,然后通过对物体的运动进行建模,将物体的运动表示成关于时间的函数,根据静止时碰撞的代数条件和运动函数将两个运动物体的碰撞条件表示成关于时间的代数条件,通过求解这个代数条件得到两个运动物体的碰撞时间。代数法可以给出碰撞点的位置信息和发生碰撞的时间等,但是当两物体不发生碰撞时无法给出最近距离信息,也就是在这一段路径下两物体何时距离最近。计算两个物体之间的最近距离在很多领域里有重要的应用,如机器人技术,CAD/CAM,计算机图形学等。在机器人路径规划中,计算相互作用力和补偿函数都需要距离信息。在计算机图形学中,距离信息对于碰撞检测和动态仿真也是非常重要的。已经有很多方法来计算两个多面体之间的距离,对于一般形状的物体,这些方法是用多个多面体来近似模拟,多面体数量很多时就需要很多存储空间,而且难以满足实时的要求。有一些方法是直接考虑两个曲面是否相交,如果相交,则它们之间的距离为零。也有文章直接计算曲面的最近距离[2][3],他们利用了这样一个几何性质:两个曲面上距离最近的两个点,它们的法线方向互相平行,这可以称为几何方法,这些方法最后都需要解一个高次方程或方程组,因而只能求静止的两个曲面的距离,对于运动情况则采用采样的方法,这可能会引起误差。在这篇文章中我们提出了一种用几何的方法计算两个运动的复合圆锥体的最近距离的方法,把最近距离看作随时间变化的连续函数,当圆锥体运动的路径已知时,该方法不仅可以计算每个时刻两圆锥体的距离,还可以计算出它们在整个运动过程中的最近距离。本文主要研究内容有:利用有理运动表示物体在三维空间中的运动;通过对控制点处的动力学镜像进行插值计算得到物体的运动方程:提出两个复合圆锥体在有理运动下的碰撞条件:提出直接利用碰撞的代数条件进行碰撞检测的算法并对求出的交点进行可用性检验:利用多项式的Bemstein形式进行求解;利用距离公式将两个复合圆锥体在三维空间的距离转化成3个多项式距离函数,计算这3个多项式函数的最小值,得到发生碰撞的情况中,两个运动复合圆锥体的最近穿刺距离和未发生碰撞情况中,两物体在运动过程中的最近分离距离。