【作者】 赵贵明；

【导师】 屠长河；

【作者基本信息】 山东大学 ， 计算机软件与理论， 2008， 硕士

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

【Abstract】 Collision detection problem is a basic problem in computer simulation, CAD; robotics .It is mainly used to enhance the reality of virtual scene or applied for robot Path planning. Collision Detection algorithms are different for different applications, providing different information. Some applications require collision detection algorithm to give information of whether the collision occurred along their respective moving course of these two objects. Other applications require collision detection algorithm not only to give whether the collision occurred, but also to provide distance information: the shortest puncture distance between these two objects when there is a collision along their moving course and the minimum separation distance between these two objects when there is no collision.Currently, there are many collision detection methods. Usually, they are divided into two major categories: one is discrete collision detection, like algorithms based on computational geometry, based on separation plane, based on graphics hardware etc.; the other is continuous collision detection, such as swept volume algorithm based on duality and Minkowski Sum, and algebraic methods. Discrete Collision Detection Methods of two moving objects use time sampling. In each sampling time we judge whether the two static objects collide. In this kind of method, if the speed of moving objects is very high, or objects are very small, collision during inter zone of two sampling time may be missed. We can improve accuracy through shortening the time sampling interval, but this will reduce efficiency. Continuous Collision Detection methods constructed a continuous path. Based on the path between objects we judge whether these two objects collision. We studies continuous collision detection using algebraic methods.There are two algorithms in this article: one is collision detection of two moving composite cone using algebraic method, another is computing minimum distance of two moving composite cones.In algebraic method a collision condition using algebraic expression of two stationary objects is proposed, and then the movement of objects modeled as a function of time. Based on these former two factors, collision condition between two moving objects is proposed.Algebraic method can give information about collision position and collision time,but when the two object don’t collide with each other,this method can’t return the minimum distance and the time when they are closest.Computing minimum distance of two object is important for many applications,such as robotics, CAD/CAM, computer graphics.In robotic path design,distance information is need in force computing and compensate function.Distance information is important for collision detection and computer simulation. There are many algorithm to compute the distance of polyhedra,to a object with free surface we can also use this method using polyhedra simulate the object,but when the number of polyhedra using to simulating is large,it is difficult to use for realtime application.There are also some method direct detect two surface is collide or not,if so,the distance if zero.There are also some method computing the distance between surfaces,these method use such a geometry character:the direction of nomor on the closest point on two surface are colliner.These method can called geometry method,they all need to solve a equation or equations with a high degree.so they only suit to immobile objects.To moving object a sampling is needed,and this could be all right.This article we propose a method computing minimum distance of two moving compesite cone using algebraic method,we see the distance as a function of time,when the path of cone is determined,this method can return the minimum distance and the time when they are closest.Contents of this paper: use Rational movement as motion of objects in three dimensional space; calculated equations of motion through interpolation of the dynamic image control points of motion trajectory; propose collision detection of two composite cone under rational motion; propose collision detection algorithm of two moving composite cone using direct computation of curves; Bernstein polynomial form of the solution; distance formula is used in collision detection between two composite cone, which is formulated into three polynomials; Bernstein polynomial form of the solution;compute distance information: the shortest puncture distance between these two objects when there is a collision along their moving course and the minimum separation distance between these two objects when there is no collision.更多还原