基于启发式搜索分离向量的凸多面体碰撞检测

碰撞检测是计算机模拟物理过程的基础，在计算机图形学、CAD／CAM、虚拟现实和机器人等领域有着广泛的应用．该文给出了一个新的用于凸多面体碰撞检测的算法——HP-jump．HP-jump建立了一个有效的碰撞检测模型用于报告物体的碰撞，同时提供了一个快速的启发式的策略用于搜索两个凸多面体的分离向量．该算法是利用凸多面体的层次表示来搜索支撑顶点对，用平衡二叉树来记录球面凸多边形的顶点，同时还利用了时间、空间相关性，这些都加速了算法的执行．该文的最后给出了HP-jump与GJK，I-COLLIDE算法的比较．     

物体变形的广义形态变换方法

将广义形态变换理论用于非刚体运动的描述和内插，通过对非刚体的凸剖分把非刚体的运动分解为非刚体的变形与子凸集的旋转，提出物体近似骨架的概念；通过近似骨架实现子凸集匹配，实现了任意非同拓扑结构(包括有孔及凹多面体)物体的变形．广义形态变换具有基于体元的变形方法和基于边界形状的变形方法的优点，同时克服了它们的缺点．实验表明，该方法变形物体边界光滑、定位精度高、计算速度快，可应用于CAD、虚拟现实和生物医学工程。     

基于混合人工鱼群算法的凸多面体碰撞检测研究

提出了一种基于最短距离计算的凸多面体碰撞检测算法。该算法利用凸多面体三维空间顶点坐标的凸包表示凸多面体,将两个凸多面体间碰撞检测问题归结为一个带约束条件的非线性规划问题,采用混合人工鱼群算法对该问题进行求解,寻优过程前期利用人工鱼群算法快速找到全局极值的邻域,后期切换到模式搜索法,准确找到全局极值。实验表明,无论在计算精度还是在计算速度方面,混合人工鱼群算法比惩罚函数法和遗传算法有更加明显的优势,能够满足碰撞检测的实时性和精确性的要求。     

重建小凸多面物体面形的新方法

为实现小凸多面物体面形快速重建,提出了基于投影轮廓的新方法。首先处理被测小凸多面物体各平行旋转角度下纵投影轮廓图像,得到对应轮廓序列集及横截面切片投影长度曲线集,然后由该曲线集得到所有疑似被测物体表平面的索引,将该索引对照各轮廓序列进行筛选,最后经计算得到被测物体的各表平面参数,完成面形重建。实验表明,该方法能够精确恢复被测小凸多面物体面形,与现有方法相比具有设备精简、速度快等特点,适用于针对小凸多面体工件的工程应用。     

求解整数线性规划问题的定界阻止算法的改进*

在现有求解整数线性规划问题的定界阻止算法的基础上提出了一种改进。该算法通过目标函数超平面截线性规划松弛问题的有效约束锥而形成一个单纯形;然后,引入一串平行片来切割该单纯形产生更低维的凸多面体;最后,在片上的这些凸多面体上执行阻止搜寻程序。由于单纯形和片上凸多面体的极顶点可以直接通过公式计算,且变量在片上凸多面体上的取值区间更窄,改进的定界阻止算法既方便又高效,这得到了一些经典算例和随机产生的算例的验证。     

基于非线性规划理论的凸多面体最小平移距离算法

凸多面体的最小平移距离问题一直以来都成为计算机图形学的一个研究热点.目前已有的距离算法在稳定性、可实现性、精确度和实现效率这几方面或多或少都存在一定的缺陷.为此,从最小平移距离定义出发,引入广义分离平面概念,提出一种用非线性规划求解距离问题的新算法.算法先定义一对最优广义分离平面以确定凸多面体最小平移距离;然后,将最优广义分离平面对的搜索问题等效变换为非线性规划问题;最后,用非线性优化工具软件对非线性规划问题进行求解,从而确定最小平移距离.实验结果表明：该算法能提供一个准确的距离值和实现向量,其性能优于其他同类算法;迭代次数与多面体的顶点数呈线性关系.此外,该算法只需提供顶点信息即可实现,求解过程中避免了死循环,故实现简单、可靠.因此,此算法是一种快速而有效的距离算法.     

机械加工过程仿真中运动物体的碰撞检测

本文提出了一种表达实体的八叉树层次球状模型和基于这种模型的运动物体之间的碰撞检测算法。机械加工过程的图形仿真对ＮＣ程序的检验是十分有用的，因为编程者或加工操作者能够很方便地看到加工的效果。由于在加工过程中，刀具和工件等都是运动物体，而要从图形上直接目测运动物体之间的碰撞情况是十分困难的。所以，本文提出了一种表示运动物体的模型及相应的碰撞检测算法。一个物体可用一个八叉树层次球模型来表示，其运动可以用节点的外接球的球心的运动来表示，它是时间的函数。通过求解满足碰撞条件的方程，我们可以得到两运动物体碰撞时间和位置。本文最后对碰撞检测算法的特性进行了分析。     

凸多面体连续碰撞检测的运动轨迹分离轴算法

针对凸体间的连续碰撞检测,在距离算法(Gilbert-Johnson-Keerthi distance algorithm,GJK)基础上,提出一种采用运动轨迹分离轴计算的线性连续碰撞检测算法.该算法首先采用支撑点和投影技术,剔除必定不发生碰撞的物体,以加速碰撞检测的速度;然后,对可能发生碰撞的物体,计算2个凸体的Minkowski差集,所形成的凸包与运动路径执行GJK分离轴算法,实现在整个时间区间内一次性完成碰撞检测任务;最后,采用几何方法以及超平面与射线求解方式计算射线与凸体边界近交点,确定出第一次发生碰撞位置,并调整运动物体位置,完成碰撞响应过程.该算法不需要构造扫掠体,连续检测过程中不需要凸体间的求交计算.将文中算法应用于物体方向包围盒的连续碰撞检测,算法分析和实验结果表明,该算法对包围盒的连续碰撞检测具有较高检测精度和响应速度.     

基于凸分解与OBB层次结构的碰撞检测方法

目前的碰撞检测方法大部分是基于简单的包围盒方法和简单的搜索算法的,这种算法精确度低且效率不高。基于凸分解与OBB层次结构的碰撞检测方法是对传统碰撞检测算法的一种改进,该方法继承了传统碰撞检测算法的优点,同时又对传统算法进行了必要的改进。实验证明,利用物体表面凸分解的方法解决了传统碰撞检测算法不能测试非凸物体相交的问题,拓宽了碰撞检测算法的应用范围;根据物体前后碰撞点的相关性,运用加速搜索提高了碰撞检测效率,降低了算法复杂度。     

一个直接计算多面体之间距离的快速算法

在机器人离线编程及仿真系统中，如何快速确定多面体之间的距离对无碰路径规划，细微运动规划和装配运动规划都有十分重要的意义，本文介绍了通用的机器人离线编程及仿真系统ＨＯＬＰＳＳ中计算多面体之间距离的一个有效算法。该方法通过直接计算凸多面体部分棱边之间的距离来确定多面体之间的距离，并利用Ｊ０函数来判别空间直线段与凸多面体是否有交。     

Incremental algorithms for collision detection between polygonalmodels

Fast and accurate collision detection between general polygonal models is a fundamental problem in physically based and geometric modeling, robotics, animation, and computer-simulated environments. Most earlier collision detection algorithms are either restricted to a class of models (such as convex polytopes) or are not fast enough for practical applications. The authors present an incremental algorithm for collision detection between general polygonal models in dynamic environments. The algorithm combines a hierarchical representation with incremental computation to rapidly detect collisions. It makes use of coherence between successive instances to efficiently determine the number of object features interacting. For each pair of objects, it tracks the closest features between them on their respective convex hulls. It detects the objects' penetration using pseudo internal Voronoi cells and constructs the penetration region, thus identifying the regions of contact on the convex hulls. The features associated with these regions are represented in a precomputed hierarchy. The algorithm uses a coherence based approach to quickly traverse the precomputed hierarchy and check for possible collisions between the features. They highlight its performance on different applications     

Proximity Queries Between Convex Objects: An Interior Point Approach for Implicit Surfaces

This paper presents a general method for exact distance computation between convex objects represented as intersections of implicit surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make intermittent contact, such as in dynamic simulations and in haptic interactions. They can also be used in the narrow phase of hierarchical collision detection. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem. We use an interior point method to solve the optimization problem and demonstrate that, for general convex objects represented as implicit surfaces, interior point approaches are globally convergent, and fast in practice. Further, they provide polynomial-time guarantees for implicit surface objects when the implicit surfaces have self-concordant barrier functions. We use a primal-dual interior point algorithm that solves the Karush-Kuhn-Tucker (KKT) conditions obtained from the convex programming formulation. For the case of polyhedra and quadrics, we establish a theoretical time complexity of O(n^1.5), where n is the number of constraints. We present implementation results for example implicit surface objects, including polyhedra, quadrics, and generalizations of quadrics such as superquadrics and hyperquadrics, as well as intersections of these surfaces. We demonstrate that in practice, the algorithm takes time linear in the number of constraints, and that distance computation rates of about 1 kHz can be achieved. We also extend the approach to proximity queries between deforming convex objects. Finally, we show that continuous collision detection for linearly translating objects can be performed by solving two related convex optimization problems. For polyhedra and quadrics, we establish that the computational complexity of this problem is also O(n^1.5).     

基于空间划分和线性规划的快速碰撞检测算法

为提高在复杂环境下多物体碰撞检测的速度,提出基于空间划分和线性规划的快速碰撞检测算法。该算法首先用均匀网格法来确定处于同一单元格内的对象,然后利用线性规划的方法对处于同一单元格内的对象进行精确测试,并实时得到碰撞检测的结果。实验结果表明,与传统的碰撞检测算法相比,该算法可以缩短计算时间,提高了碰撞检测的效率。     

刚体在软体对象环境中的碰撞检测的研究

刚体在软体对象环境中的碰撞检测在虚拟现实的研究领域具有很大的普遍性 ,但以往的研究较少 .文中给出了一种基于固定方向凸包 (FDH)包围盒树的碰撞检测方法 ,并着重论述了利用线性规划的思想以解决刚体自由运动后包围盒树的更新以及通过一种自底向上的方法解决软体对象变形后包围盒树的更新 .实验表明 ,该方法不仅能较好地解决刚体间的碰撞检测 ,而且能有效地解决刚体与软体间的碰撞检测     

Fast Collision Detection Algorithms with Applications to Particle Flow

In this paper, we present efficient algorithms for collision detection of arbitrarily shaped rigid moving objects in a variety of interactive as well as non-interactive environments. The algorithms primarily consist of two stages. The first stage involves finding candidate objects for possible collisions. The second stage involves detecting exact (within a prespecified tolerance) collision between these candidates. The primary data structure used in the algorithms is an octree. In the first stage, we build an octree for the enclosure containing the objects, which is used to detect possible collisions. Assuming spatial/temporal coherence i.e., that the particles move slowly or that the time sampling is fast enough, the average time complexity of this stage can be shown to be O(n) (excluding the time complexity for a one time octree construction), where n is the number of particles. In the second stage, we build a surface-octree for each object. If the objects are convex and assuming coherence, the expected time complexity to detect precise (within a prespecified tolerance) collision for each pair is a constant (excluding the time complexity for a one time surface-octree construction). Therefore, the overall expected time complexity for convex object collision detection is linear with respect to n. For the concave objects, complexity analysis is nontrivial to perform and instead we provide a very practical (almost linear time) algorithm. We apply our algorithms to particle flow simulations by simulating flow density conditions often arising in granular flows.     

基于拓扑层次图的碰撞检测算法

为了提高虚拟环境中碰撞检测的实时性和精确性,提出了一种基于拓扑层次图的碰撞检测方法。利用拓扑结构的连接关系将模型分割成凸集;然后利用凸集较强的适应性和OBB紧密性好的优点构造包围盒的拓扑层次图,提高了剔除不相交包围盒的效率,减少了检测时间;利用智能搜索算法——改进的A*算法搜索潜在碰撞集(PCS),进一步提高相交检测的速度和准确性。实验表明,该算法具有较高的速度和精度,能够满足复杂虚拟环境碰撞检测实时性和精确性的要求。     

基于凸壳的高密度点集物碰撞检测算法

提出了一种基于凸壳的高密度点集物碰撞检测算法。根据高密度点集物紧密性好的特点,设计了一种快速的凸壳算法;当极值比较不能确定待检测点集物未碰撞时,用该算法计算待检测点集物的凸壳,并对凸壳进行求交运算,若不相交,两点集物未发生碰撞,否则在两凸壳的交集区域中寻找碰撞点集。算法简单、高效、可靠,在教育、国防、艺术等方面具有一定应用价值。     

A Recursive Algorithm for On-line Clustering Obstacles Cluttered in Dynamic Environments

In some applications of industrial robots, the robot manipulator must traverse a pre-specified Cartesian path with its hand tip while links of the robot safely move among obstacles cluttered in the robot's scene (environment). In order to reduce the costs of collision detection, one approach is to reduce the number of collision checks by enclosing a few real obstacles with a larger (artificial) bounding volume (a cluster), e.g., by their convex hull [4, 14], without cutting the specified path.In this paper, we propose a recursive algorithm composed of four procedures to tackle the problem of clustering convex polygons cluttered around a specified path in a dynamic environment. A key fact observed is that the number k of clusters is actually determined by the specified path not by any criterion used in clustering. Based on this fact, an initial set of k clusters could be rapidly generated. Then, the initial set of clusters and its number is further refined for satisfying the minimum Euclidean distance criterion imposed in clustering. Compared to the heuristic algorithm in [14], complexity of the proposed algorithm is reduced by one order with respect to the number n of obstacles. Simulation are performed in both static and dynamic environments, which show that the recursive algorithm is very efficient and acquires less number k of clusters.     

基于距离场和扫掠剪除算法的线缆碰撞检测技术

针对线缆具有柔性可变形特性而引起线缆碰撞检测难的问题,提出了基于距离场和扫掠剪除算法的线缆碰撞检测方法。基于距离场的碰撞检测方法主要用于检测线缆与线缆、线缆与结构件之间的碰撞：首先通过建立线缆体廓包围球,完成线缆多细节层次球面调和的表达;然后生成三维距离场映射,获取线缆或结构件表面法向量和穿刺深度等碰撞反馈信息。基于扫掠剪除算法的碰撞检测方法主要用于检测线缆的自碰撞：先构建线缆分段数学模型,然后通过线缆离散点扫掠剪除完成线缆自碰撞检测。最后对算法进行了验证,算法具有较好的准确性和快速性,可以满足工程实际的要求。