凸多面体碰撞检测的棱线投影分离算法EI北大核心CSCD

针对凸多面体碰撞检测问题,以直线投影法为基础对分离面投影法进行改进,提出一种采用棱线投影分离的凸多面体实时精确碰撞检测算法.首先分析了凸多面体各种相对位置关系并提出了投影分离线的概念,针对凸多面体的各种分离情况证明投影分离线的存在;其次选取凸多面体相向面上的棱集构造准投影分离线,通过沿着准投影分离线方向投影可将3D凸多面体碰撞检测降维为2D凸多边形的碰撞检测问题;最后将分离投影的思想延用至为2D凸多边形的碰撞检测,再次将2D问题降维为1D问题.算法分析和实验结果表明,该算法对于凸多面体碰撞检测具有较高的响应速度和检测精度.     

凸多面体碰撞检测的棱线投影分离算法

针对凸多面体碰撞检测问题,以直线投影法为基础对分离面投影法进行改进,提出一种采用棱线投影分离的凸多面体实时精确碰撞检测算法.首先分析了凸多面体各种相对位置关系并提出了投影分离线的概念,针对凸多面体的各种分离情况证明投影分离线的存在;其次选取凸多面体相向面上的棱集构造准投影分离线,通过沿着准投影分离线方向投影可将3D凸多面体碰撞检测降维为2D凸多边形的碰撞检测问题;最后将分离投影的思想延用至为2D凸多边形的碰撞检测,再次将2D问题降维为1D问题.算法分析和实验结果表明,该算法对于凸多面体碰撞检测具有较高的响应速度和检测精度.     

判断两个凸多面体是否相交的一个快速算法

在机器人路径规划中,碰撞检测算法占有十分重要的地位.在智能机器人仿真系统中,碰撞检测耗用的时间在整个路径规划过程所用时间中占有相当大的比例.于是,如何进一步提高碰撞检测的速度在智能机器人路径规划系统中就起到了非常关键的作用.而碰撞检测问题最终转化为判断三维空间中两个凸多面体是否相交的问题.就这一问题,给出了一种新的算法,其思想是取一个从一个凸多面体指向另一个多面体的向量,根据两个多面体中的面与这一向量的相对位置关系来寻找相交的平面.即有两个多面体的交点位于这一平面,若能找到一个相交平面则可以断定两个多面体     

基于Minkowski和的多面体快速碰撞检测算法

为了进一步提高碰撞检测的实时性,提出一种基于Minkowski和的多面体快速碰撞检测算法.该算法以Minkowski和为工具,无需精确计算两个多面体之间的最短距离,首先通过构造两个多面体的Minkowski和,将多面体碰撞检测问题转化为判断原点是否在该Minkowski和内,然后运用射线和求交计算将三维空间问题转化为二维平面问题,再通过判断原点是否在平面多边形内来检测多面体是否发生碰撞,进而提高了碰撞检测的实时性和可靠性.在Visual C#环境下,利用OpenGL图形库搭建一个路径规划仿真系统.实验结果表明,该算法平均检测效率明显高于传统算法,并且有效降低了存储空间和时间复杂度.     

基于层次包围盒的混合碰撞检测算法

针对碰撞检测算法实时性较差的缺点,本文提出基于AABB包围盒与OBB包围盒相结合的混合碰撞检测算法,首先由对象投影来判断是否相交,检测出不可能相交对象;然后对可能相交的对象投影反向构建AABB包围盒,快速地测试对象;再用OBB包围盒进行精确地检测,以实现虚拟环境对象间高效的碰撞检测。本文还针对传统的基元相交测试效率不高的缺点进行了一定的改进。实验结果表明,与另外两种算法对比,该方法在相同环境前提下能够有效的提高碰撞检测的效率。     

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

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

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

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

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

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

用于特征点配准的快速聚类凸集投影算法

提出一种用于特征点配准的快速聚类凸集投影算法. 该算法首先将模板点集和目标点集的配准问题通过聚类转化为相应类集合的配准问题，降低了算法的计算量；进而采用基于二次规划的凸集投影来求解类配准问题，避免了序贯凸集投影算法由于交替行列投影而引起的积累误差. 仿真表明，相对于现有的特征点配准算法，本文算法的配准精度和计算量均有所改善.     

基于并行的快速碰撞检测算法的研究

为了提高检测速度,提出了一种基于并行的快速碰撞检测算法,该算法首先将任意多面体的剖分为多个四面体,然后对四面体进行并行碰撞检测,并通过建立包围盒树进一步提高算法的效率,并行算法采用基于MPI库方式来实现.结果表明,该算法显著提高检测速度并具备较高精度.     

On the construction and display of a polytopal mesh for the N-dimensional hypercube and (N + 1) simplex

By considering the analytical properties of polytopes it is possible to design a general data structure, a polytopal mesh, to represent such N-dimensional objects. Further investigation of the N-dimensional hypercube leads to the construction of a ternary code for representing the hypercube and the interconnection between levels of the polytopal mesh. This technique has been extended to other convex polytopes and specific examples of the N-dimensional cross polytope and simplex are given. Various projection techniques are used to display the convex polytopes on a two dimensional viewport.     

On the necessity of the invariance conditions for reach control on polytopes

We study the Reach Control Problem (RCP) to make the solutions of an affine system defined on a polytopic state space reach and exit a prescribed facet of the polytope in finite time without first leaving the polytope. So-called invariance conditions are used to prevent solutions from leaving the polytope through facets which are not designated as the exit facet. These conditions are known to be necessary for solvability of the RCP on polytopes by continuous state feedback. We study whether the invariance conditions are also necessary for solvability of the RCP on polytopes by open-loop controls. We show by way of a counterexample that surprisingly the answer is negative. We identify a suitable class of polytopes for which the invariance conditions remain necessary conditions.     

A Linear Algorithm for Collision Detection of 3-Dimensional Convex Polytopes

Given two disjoint 3-dimensional convex polytopes P and Q and a straight direction along Which P moves in translation, this paper presents a linear algorithm for determining Whether P collides with Q, and the possible collision positions on P and Q. This result is achieved by using the hierarchicat representation of polytopes, of which the preprocessing time is linear with space.     

Mathematical modeling of the interaction of non-oriented convex polytopes

An ??-function for two non-oriented convex polytopes is set up. The ??-function can be used to construct a mathematical model of packing optimization problem for non-oriented polytopes. An example of an ??-function for two non-oriented parallelepipeds is given.     

Two Approaches to Modeling and Solving the Packing Problem for Convex Polytopes

We consider the problem of packing convex polytopes in a cuboid of minimum volume. To describe analytically the non-overlapping constraints for convex polytopes that allow continuous translations and rotations, we use phi-functions and quasi-phi-functions. We provide an exact mathematical model in the form of an NLP-problem and analyze its characteristics. Based on the general solution strategy, we propose two approaches that take into account peculiarities of phi-functions and quasi-phi-functions. Computational results to compare the efficiency of our approaches are given with respect to both the value of the objective function and runtime.     

Set-theoretic approach to uncertain dynamical systems using convex polytopes

A set-theoretic approach to uncertain dynamical systems by using convex polytopes is treated. In some points, this approach is superior to the one using ellipsoids, though it also has some disadvantages. First, some fundamental operations are discussed, such as addition, intersection, and the linear transformation of convex polytopes. The results are applied to the analysis of reachable sets for discrete-time linear dynamical systems and also to the state estimation.     

Geometrically Exact Simulation of Inextensible Ribbon

Narrow, inextensible, and naturally flat ribbons have some special and interesting phenomena under isometric deformations. Although a ribbon has a shape between rod and shell, directly applying the geometric representation designed for them imposes a challenge to faithfully reproduce interesting behaviors. We thus parameterize the ribbon surface as a developable ruled surface along its centerline and represent it using a framed centerline curve. Then the elastic and kinetic energy of the ribbon surface can be equivalently yet compactly described by the framed centerline curve only. To avoid numerical singularity when develop ability is violated, a finite Taylor series approximation to the potential energy is adopted. Under the observation that the off‐centerline part of ribbon contributes little dynamic effect, the kinetic energy is simplified with respect to the centerline velocity only. For efficiency, each time step is separated into two stages: dynamically evolving the centerline, and then quasi‐statically updating the ruling. We validate the method with qualitative analysis and ribbon specific phenomena comparisons with real‐world scenarios. A set of comparisons to rod and shell model is also provided to demonstrate the advantages of our method.     

Convex-set-based fuzzy clustering

Prototype-based methods are commonly used in cluster analysis and the results may be highly dependent on the prototype used. We propose a two-level fuzzy clustering method that involves adaptively expanding and merging convex polytopes, where the convex polytopes are considered as a “flexible” prototype. Therefore, the dependency on the use of a specified prototype can be eliminated. Also, the proposed method makes it possible to effectively represent an arbitrarily distributed data set without a priori knowledge of the number of clusters in the data set. In the first level of our proposed method, each cluster is represented by a convex polytope which is described by its set of vertices. Specifically, nonlinear membership functions are utilized to determine whether an input pattern creates a new cluster or whether an existing cluster should be modified. In the second level, the expandable clusters that are selected by an intercluster distance measure are merged to improve clustering efficiency and to reduce the order dependency of the incoming input patterns. Several experimental results are given to show the validity of our method