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     

Effective lattice point counting in rational convex polytopes

This paper discusses algorithms and software for the enumeration of all lattice points inside a rational convex polytope: we describe LattE, a computer package for lattice point enumeration which contains the first implementation of A. Barvinok’s algorithm (Math. Oper. Res. 19 (1994) 769).We report on computational experiments with multiway contingency tables, knapsack type problems, rational polygons, and flow polytopes. We prove that these kinds of symbolic–algebraic ideas surpass the traditional branch-and-bound enumeration and in some instances LattE is the only software capable of counting. Using LattE, we have also computed new formulas of Ehrhart (quasi-)polynomials for interesting families of polytopes (hypersimplices, truncated cubes, etc).We end with a survey of other “algebraic–analytic” algorithms, including a “homogeneous” variation of Barvinok’s algorithm which is very fast when the number of facet-defining inequalities is much smaller compared to the number of vertices.     

Composite Geometric Concepts and Polynomial Predictability

We study the predictability of geometric concepts, in particular those defined by boolean combinations of simple geometric objects. First, we give a negative results, showing that the problem of predicting the class of convex polytopes encoded by listing their vertices is prediction complete for P. Thus, an efficient solution to this prediction problem implies the existence of efficient solutions to all prediction problems whose associated evaluation problems are in P. Assuming the existence of a one-way function that is hard on iterates, there are such prediction problems which do not admit efficient solutions. Thus we show under minimal cryptographic assumptions that the class of convex polytopes encoded by listing their vertices is not predictable. As a side effect, we show that determining membership in the convex hull of a given set of points is complete for P with respect to log space reductions. Next, we establish the predictability of the class consisting of unions of a fixed number of flats by reducing its prediction problem to that of the class of flats, which has previously been shown to be predictable. Finally, we give an Occam algorithm for predicting fixed finite unions of boxes. Both constructive results for flats and boxes hold if the dimension is variable.     

Efficient collision detection using bounding volume hierarchies ofk-DOPs

Collision detection is of paramount importance for many applications in computer graphics and visualization. Typically, the input to a collision detection algorithm is a large number of geometric objects comprising an environment, together with a set of objects moving within the environment. In addition to determining accurately the contacts that occur between pairs of objects, one needs also to do so at real-time rates. Applications such as haptic force feedback can require over 1000 collision queries per second. We develop and analyze a method, based on bounding-volume hierarchies, for efficient collision detection for objects moving within highly complex environments. Our choice of bounding volume is to use a discrete orientation polytope (k-DOP), a convex polytope whose facets are determined by halfspaces whose outward normals come from a small fixed set of k orientations. We compare a variety of methods for constructing hierarchies (BV-trees) of bounding k-DOPs. Further, we propose algorithms for maintaining an effective BV-tree of k-DOPs for moving objects, as they rotate, and for performing fast collision detection using BV-trees of the moving objects and of the environment. Our algorithms have been implemented and tested. We provide experimental evidence showing that our approach yields substantially faster collision detection than previous methods     

Dynamic Sampling and Rendering of Algebraic Point Set Surfaces

Algebraic Point Set Surfaces (APSS) define a smooth surface from a set of points using local moving least‐squares (MLS) fitting of algebraic spheres. In this paper we first revisit the spherical fitting problem and provide a new, more generic solution that includes intuitive parameters for curvature control of the fitted spheres. As a second contribution we present a novel real‐time rendering system of such surfaces using a dynamic up‐sampling strategy combined with a conventional splatting algorithm for high quality rendering. Our approach also includes a new view dependent geometric error tailored to efficient and adaptive up‐sampling of the surface. One of the key features of our system is its high degree of flexibility that enables us to achieve high performance even for highly dynamic data or complex models by exploiting temporal coherence at the primitive level. We also address the issue of efficient spatial search data structures with respect to construction, access and GPU friendliness. Finally, we present an efficient parallel GPU implementation of the algorithms and search structures.     

Interference detection for direct tool path generation from measured data points

One of the main issues of the reverse engineering (RE) is the duplication of an existing physical part whose geometric information is partially or completely unavailable in measured form. In some industrial applications, physical parts are duplicated using three-axis CNC machines and ball-end mills. Many researches studied the problem of direct tool path generation from measured data point. However, up to the present, it appears that there is no reported study on interference detection in paths generated directly from measured data points. Interference detection is a curial problem in direct tool path generation from measured data points. This paper discusses the problem of local and global interference detection for three-axis machining in RE and proposes algorithms for local and global interference detection. With these algorithms, the measured data points captured from a physical part are analyzed and classified according to the shapes of the part. The method has been tested with several industrial parts, and it is shown to be robust and efficient especially for the part with free-form surfaces.     

曲面工件超声检测中碰撞干涉的研究

在超声检测自动探伤过程中,探头可能和工件发生碰撞干涉。根据曲面工件和圆柱形探头碰撞干涉的特点,给出了一种分级碰撞干涉检测方法。首先利用包围盒算法和几何求交算法剔除大量被检对象分离的情况,然后将可能干涉的3维对象正投影到2维平面中,空间碰撞问题就转化为平面碰撞问题,只需计算投影图是否有重叠就可精确判断是否干涉。工程应用表明,该方法能满足超声检测机器人碰撞干涉检测的高效性和精确性要求,该方法也适用于装配和数控加工中复杂曲面和圆柱体之间的碰撞干涉快速检查。     

GEOMPACK — a software package for the generation of meshes using geometric algorithms

We describe the mathematical software package GEOMPACK, which contains standard Fortran 77 routines for the generation of two-dimensional triangular and three-dimensional tetrahedral finite element meshes using efficient geometric algorithms. This package results from our research into mesh generation and geometric algorithms. It contains routines for constructing two- and three-dimensional Delaunay triangulations, decomposing a general polygonal region into simple or convex polygons, constructing the visibility polygon of a simple polygon from a viewpoint, and other geometric algorithms, from which our mesh generation method is built and others can be implemented. Our method generates meshes in polygonal or polyhedral regions specified by their boundary representation and possible interfaces between subregions.     

Continuous Collision Detection for Ellipsoids

We present an accurate and efficient algorithm for continuous collision detection between two moving ellipsoids. We start with a highly optimized implementation of interference testing between two stationary ellipsoids based on an algebraic condition described in terms of the signs of roots of the characteristic equation of two ellipsoids. Then we derive a time-dependent characteristic equation for two moving ellipsoids, which enables us to develop a real-time algorithm for computing the time intervals in which two moving ellipsoids collide. The effectiveness of our approach is demonstrated with several practical examples.     

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.     

IBCD: a fast collision detection algorithm based on image space using OBB

Image‐based collision detection algorithms make efficient use of the graphics rendering hardware and reduce the computational cost of CPU. In this article, a fast collision detection algorithm based on image space is presented, which combines graphics hardware capabilities with a simplified geometric representation (oriented bounding box) in order to rapidly detect collisions between complex objects. The method can deal with arbitrary polyhedra, while preserving the merits of image‐based collision detection algorithms. This is achieved by decomposing the surfaces of an object into a list of convex pieces. High efficiency of the algorithm is obtained by organizing the convex pieces into a binary tree with each node representing a convex piece, and by adopting triangle strip compression. The algorithm has been implemented and compared with related algorithms. Copyright © 2003 John Wiley & Sons, Ltd.     

Curved glide-reflection symmetry detection

We generalize the concept of bilateral reflection symmetry to curved glide-reflection symmetry in 2D euclidean space, such that classic reflection symmetry becomes one of its six special cases. We propose a local feature-based approach for curved glidereflection symmetry detection from real, unsegmented 2D images. Furthermore, we apply curved glide-reflection axis detection for curved reflection surface detection in 3D images. Our method discovers, groups, and connects statistically dominant local glidereflection axes in an Axis-Parameter-Space (APS) without preassumptions on the types of reflection symmetries. Quantitative evaluations and comparisons against state-of-the-art algorithms on a diverse 64-test-image set and 1,125 Swedish leaf-data images show a promising average detection rate of the proposed algorithm at 80 and 40 percent, respectively, and superior performance over existing reflection symmetry detection algorithms. Potential applications in computer vision, particularly biomedical imaging, include saliency detection from unsegmented images and quantification of deviations from normality. We make our 64-test-image set publicly available.     

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

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

A convex optimization approach for clone detection in wireless sensor networks

When deployed unattended in hostile environments, static and mobile Wireless Sensor Networks (WSNs) are vulnerable to node capture and cloning attacks, where an adversary physically compromises network nodes and extracts all information known to them, including the assigned cryptographic material and the internal states of network protocols. The obtained knowledge is used to disrupt the network by deploying and controlling copies of captured nodes (clones). Recently, a variety of novel clone detection methods have been developed, using concepts such as birthday paradox, sequential detection or random encounters in mobile environments. At present there is no framework to evaluate an individual detection method based on the WSN performance under attack or to compare and choose a method appropriate for a given application. In this paper, we develop an optimization framework for choosing the parameters of a detection method so that the cost of clone detection is minimized. We show that every detection method can be characterized in terms of four costs, namely, the impact of leaving undetected cloned nodes in the network, the cost of revoking nodes falsely identified as compromised, and the costs of communication and storage. A convex combination of these costs defines the cost of clone detection, which is then minimized with respect to the parameters of the detection method. Using this framework, we analyze existing clone detection algorithms and provide efficient methods for obtaining optimal detection parameters.     

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

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

基于角度搜索和距离判定的边缘检测算法

在离散数据处理中,边缘检测算法的应用非常广泛。针对当前边缘检测算法存在的问题,如数据量的大小、数据的几何特性、密度的集中程度、距离跨度等,提出了一种基于角度搜索和距离判定的边缘检测算法,详细考虑了边界的多情况、凹边形和凸边形的几何特性。首先建立四个点的边界凸壳,然后采用角度判断的方法进行凸壳内缩,最后进行距离判断的二次内缩检验。该方法简洁、高效、便于理解与实现,并且可以针对各种情况的离散数据。采用乐山市城区的商业圈聚类分析数据进行测试,该离散数据体现了高密度、低密度、数据量大、距离跨度大等特点,通过实验证明了该算法边界检测效果较好,异常数据小,能够准确甄别出边界区域数据。同时也证明了该算法的通用性、简洁性和高效性。     

From images to rooms

In this paper we start from a set of images obtained by the robot that is moving around in an environment. We present a method to automatically group the images into groups that correspond to convex subspaces in the environment which are related to the human concept of rooms. Pairwise similarities between the images are computed using local features extracted from the images and geometric constraints. The images with the proposed similarity measure can be seen as a graph or in a way as a base level dense topological map. From this low level representation the images are grouped using a graph-clustering technique which effectively finds convex spaces in the environment. The method is tested and evaluated on challenging data sets acquired in real home environments. The resulting higher level maps are compared with the maps humans made based on the same data.     

Planar Shape Detection and Regularization in Tandem

We present a method for planar shape detection and regularization from raw point sets. The geometric modelling and processing of man‐made environments from measurement data often relies upon robust detection of planar primitive shapes. In addition, the detection and reinforcement of regularities between planar parts is a means to increase resilience to missing or defect‐laden data as well as to reduce the complexity of models and algorithms down the modelling pipeline. The main novelty behind our method is to perform detection and regularization in tandem. We first sample a sparse set of seeds uniformly on the input point set, and then perform in parallel shape detection through region growing, interleaved with regularization through detection and reinforcement of regular relationships (coplanar, parallel and orthogonal). In addition to addressing the end goal of regularization, such reinforcement also improves data fitting and provides guidance for clustering small parts into larger planar parts. We evaluate our approach against a wide range of inputs and under four criteria: geometric fidelity, coverage, regularity and running times. Our approach compares well with available implementations such as the efficient random sample consensus–based approach proposed by Schnabel and co‐authors in 2007.