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

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

任意多面体的四面体剖分算法

该文提出一种将任意多面体剖分为四面体的算法,该算法首先依据顶点凸凹性算法判定多面体顶点的凸凹性性质,再寻找符合剖分条件的凸顶点,将该凸顶点的凸空间从原多面体中剖分出去,得到一个新的多面体,剖分出来的凸空间再分为多个四面体;再重复对新的多面体进行剖分,直到剖分完毕。该算法的平均时间复杂度为O(N+M),其中N为多面体的凸顶点数目,M为多面体的凹顶点数目。     

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

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

任意多面体的剖分算法及应用

本文提出了一种将任意多面体剖分为四面体的算法，给出了算法理论基础的证明、算法具体实现步骤及所用数据结构。该算法首先根据多面体类型，查找出符合剖分要求的多面体一个面与一个顶点，构成一个简单多面体，将原多面体剖分为该简单多面体和一个新的多面体，再 对新的多面体重复剖分，直到多面体全部剖分为简单多面体。每个简单多面体进一步剖分为四面体。最后，文章讨论了该算法在机器人碰撞检测中的应用。     

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

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

基于成功回路的凹多面体的剖分算法

提出了一种对任意凹多面体不添加顶点的凸剖分方法,该算法首先把凹多面体抽象为无向图,无向图的顶点为多面体的顶点,边为多面体的棱和对角棱,权值为棱或对角棱的长度,然后根据普利姆算法构造最小生成树的思想来构造一个成功回路,利用该回路对多面体进行剖分。重复执行此过程,直到剖分后的所有多面体都是非凹的。该算法能够对多面体进行不添加顶点的剖分,同时可以对任意凹多面体多面体进行剖分,包括含有空洞的凹多面体。     

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

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

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

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

凸多面体快速碰撞检测的投影分离算法

为了有效地提高凸面体之间的碰撞检测效率,提出一种凸多面体快速碰撞检测的投影分离算法.该算法通过判断2个凸多面体在中心线上的正投影不相交,或者分别构造它们的准投影分离面集合,并从这2个集合中找到一个投影分离面,来判断2个凸多面体分离;否则,判断为相交.对于2个准投影分离面集合,依次交替地判断它们的每一个面是投影分离面还是相交面,以加快2个凸多面体相交检测.计算复杂度分析和数值实验表明:该算法平均检测效率高于其他检测算法.     

基于图像的快速碰撞检测算法

基于图像的碰撞检测算法是一类较新的碰撞检测方法，它有效地利用图形硬件的加速功能，以减轻CPU的负担，文中提出一种基于图像的快速碰撞检测算法，该算法在继承一般基于图像的碰撞检测算法优点的同时，不但能处理任意形状的多面体，而且具有更高效率，该算法主要采用对物体表面进行自动凸分解，将凸分解结果合理的组织成层次二叉树结构，以及绘制加速等技术，与相关算法的实验比较说明，该算法在性能上有较大的提高。     

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.     

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

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

A discrete methodology for controlling the sign of curvature and torsion for NURBS

This paper develops a discrete methodology for approximating the so-called convex domain of a NURBS curve, namely the domain in the ambient space, where a user-specified control point is free to move so that the curvature and torsion retains its sign along the NURBS parametric domain of definition. The methodology provides a monotonic sequence of convex polyhedra, converging from the interior to the convex domain. If the latter is non-empty, a simple algorithm is proposed, that yields a sequence of polytopes converging uniformly to the restriction of the convex domain to any user-specified bounding box. The algorithm is illustrated for a pair of planar and a spatial Bézier configuration.     

判定凸多边形可碰撞的最优算法

设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的.     

求两个相交凸多边形并的凸包及交的算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段,利用凸壳顶点有序性,分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q,求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性,使算法的时间复杂度达到最小。     

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     

Maximum Entropy Coordinates for Arbitrary Polytopes

Barycentric coordinates can be used to express any point inside a triangle as a unique convex combination of the triangle's vertices, and they provide a convenient way to linearly interpolate data that is given at the vertices of a triangle. In recent years, the ideas of barycentric coordinates and barycentric interpolation have been extended to arbitrary polygons in the plane and general polytopes in higher dimensions, which in turn has led to novel solutions in applications like mesh parameterization, image warping, and mesh deformation. In this paper we introduce a new generalization of barycentric coordinates that stems from the maximum entropy principle. The coordinates are guaranteed to be positive inside any planar polygon, can be evaluated efficiently by solving a convex optimization problem with Newton's method, and experimental evidence indicates that they are smooth inside the domain. Moreover, the construction of these coordinates can be extended to arbitrary polyhedra and higher‐dimensional polytopes.     

寻求简单多边形凸壳的线性时间算法

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选，使剩余顶点的角的大小排成递增序，然后用Graham扫描方法删去非凸壳顶点，最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的 凹点，最后得到凸壳顶点序列。这两种算法简单，易于实现，时间复杂性都是O（n)。     

Probing a scene of nonconvex polyhedra

We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that \(\tfrac{{10}}{3}n\left( {m + k} \right) - 2m - 3k\) probes are sufficient to compute the exact shapes of the polyhedra.