多核加速的并行碰撞检测

针对复杂场景中碰撞检测算法无法满足实时性要求的问题,通过分析影响碰撞检测算法并行度的主要因素,提出一种基于数据分块思想的并行碰撞检测算法.在初始化阶段,将场景数据从空间角度进行分块;在碰撞检测阶段,由每个处理器处理一块数据以实现包围盒并行更新,同时利用静态和动态相结合的任务分配策略实现碰撞检测的并行化.在16核和24核处理器模式下与已有算法进行对比实验的结果证明,文中算法能够提升碰撞检测速度,同时具有很好的兼容性.     

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

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

图形硬件加速的柔性物体连续碰撞检测

给出了一种图形硬件加速的柔性物体连续碰撞检测算法,可以实时检测复杂柔性物体场景中所有物体间碰撞和自碰撞.算法将柔性物体的碰撞检测过程进行流式分解,映射到图形硬件上并行执行,同时使用了并行流式登记算法,在图形硬件上高效实现了变长数据结构.该算法已经使用OpenCL在AMD Radeon HD 5870图形硬件上实现.针对一组各具特色的柔性物体仿真场景进行测试,对比CPU(Intel Q6600@2 4GHz)上的单线程优化实现,可以获得9 2～11 4倍的计算加速.     

基于GPU加速的多物体碰撞检测方法

为了在虚拟环境中更加真实地模拟现实环境中物体的运动,需要在仿真系统中加入碰撞检测模块。现有的碰撞检测算法虽然能够快速检测两个物体是否相交,但在物体数量非常多的场景中,因需要对物体两两进行判断,所以仍无法达到较高的检测速度。利用GPU并行计算的特性,在GPU上增加一个预先剔除的过程,大幅度地快速排除不相交的物体,提高了检测的速度。     

一种快速的可变形物体的碰撞检测算法

为实现虚拟环境中可变形物体与刚体间实时的碰撞检测,提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重,对可变形物体建立Sphere和AABB混合包围盒层次树,对刚体建立Sphere和OBB混合包围盒层次树;每个物体的混合包围盒层次树又分成上层、中层和下层,每层使用不同的包围盒;在碰撞检测遍历时,上层使用Sphere和Sphere相交检测快速排除不相交物体,在中层使用Sphere和OBB的相交检测进一步排除物体相交的可能性,在下层使用AABB和OBB的相交检测较精确地确定物体是否相交;采用多线程技术,在多核设备上实现并行碰撞检测算法。实验结果表明,与经典的AABB算法相比较,该算法在效率方面具有明显优势,能够满足可变形物体与刚体的碰撞检测要求。     

基于视线碰撞检测算法的研究

碰撞检测能增强场景漫游中的真实感,在Vega中由于对自定义的运动模型根本起不到实质的作用,因此本文提出了基于视线的碰撞检测算法。借助简化的OBB包围盒来简化碰撞的模型,以提高碰撞检测的效率。经实验验证。该检测方法简单、精确,检测速度快。能够满足大范围场景中实时交互的要求。     

基于层次包围盒的碰撞检测算法研究

比较基于包围盒的碰撞检测算法中的包围球法、轴向包围盒法、方向包围盒法、离散方向多面体法、固定方向凸包(FDH),分析结果表明:包围盒的简单性和其包裹对象的紧密性是一对矛盾,如何更好的兼顾简单性和紧密性成为关键.     

一种优化的可变形物体碰撞检测算法

对可变形物体的碰撞检测提出了一种优化的加速算法。算法在Sean Curtis[1]等人提出的特征三角形检测算法的基础上,增加了点和边的基本元素动态分配,并且用多叉树代替二叉树,提高了碰撞检测的效率。新算法可以应用于所有以三角形为基本单位的模型,能够显著地减少基本元素对的检测,并且可以和传统的层次包围盒法结合使用。用提出的优化加速算法对连续碰撞检测中的球-布模型和人体模特-服装模型进行了检测,实验表明,改进的算法相比原算法减少了元素检测的对数,缩短了检测时间,性能提升非常明显。     

一种快速的基于并行的碰撞检测算法

提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树,通过遍历每两棵包围盒树形成对一任务树的遍历,采用并行算法中的流水线技术,利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术,因而能运行于单处理机和多处理机上。     

Collision Detection for Deformable Objects

Interactive environments for dynamically deforming objects play an important role in surgery simulation and entertainment technology. These environments require fast deformable models and very efficient collision handling techniques. While collision detection for rigid bodies is well investigated, collision detection for deformable objects introduces additional challenging problems. This paper focuses on these aspects and summarizes recent research in the area of deformable collision detection. Various approaches based on bounding volume hierarchies, distance fields and spatial partitioning are discussed. In addition, image‐space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.     

虚拟环境中的软体碰撞检测技术综述

介绍软体碰撞检测中主要的层次包围盒方法、空间分割、随机方法、距离场和图像空间方法,从碰撞检测的计算效率与准确性的角度,分析这些算法的优势和不足,指出研究的关键点和难点。     

Deformable Objects Collision Handling with Fast Convergence

We present a stable and efficient simulator for deformable objects with collisions and contacts. For stability, an optimization derived from the implicit time integrator is solved in each timestep under the inequality constraints coming from collisions. To achieve fast convergence, we extend the MPRGP based solver from handling box constraints only to handling general linear constraints and prove its convergence. This generalization introduces a cost of solving dense linear systems in each step, but these systems can be reduced into diagonal ones for efficiency without affecting the general stability via pruning redundant collisions. Our solver is an order of magnitude faster, especially for elastic objects under large deformation compared with iterative constraint anticipation method (ICA), a typical method for stability. The efficiency, robustness and stability are further verified by our results.     

kDet: Parallel Constant Time Collision Detection for Polygonal Objects

We define a novel geometric predicate and a class of objects that enables us to prove a linear bound on the number of intersecting polygon pairs for colliding 3D objects in that class. Our predicate is relevant both in theory and in practice: it is easy to check and it needs to consider only the geometric properties of the individual objects – it does not depend on the configuration of a given pair of objects. In addition, it characterizes a practically relevant class of objects: we checked our predicate on a large database of real‐world 3D objects and the results show that it holds for all but the most pathological ones. Our proof is constructive in that it is the basis for a novel collision detection algorithm that realizes this linear complexity also in practice. Additionally, we present a parallelization of this algorithm with a worst‐case running time that is independent of the number of polygons. Our algorithm is very well suited not only for rigid but also for deformable and even topology‐changing objects, because it does not require any complex data structures or pre‐processing. We have implemented our algorithm on the GPU and the results show that it is able to find in real‐time all colliding polygons for pairs of deformable objects consisting of more than 200k triangles, including self‐collisions.     

ICCD: Interactive Continuous Collision Detection between Deformable Models Using Connectivity-Based Culling

We present an interactive algorithm for continuous collision detection between deformable models. We introduce multiple techniques to improve the culling efficiency and the overall performance of continuous collision detection. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh as part of self-collision tests. Second, we introduce the concept of “procedural representative triangles” to remove all redundant elementary tests between nonadjacent triangles. Finally, we exploit the mesh connectivity and introduce the concept of “orphan sets” to eliminate redundant elementary tests between adjacent triangle primitives. In practice, we can reduce the number of elementary tests by two orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior collision detection algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations, and breaking objects.     

虚拟现实中手与虚拟物体碰撞检测的一种算法

在虚拟现实技术中，人与虚拟空间物体的碰撞检测是非常重要的研究课题之一。由于空间物体结构的复杂性和碰撞响应的多样性，故找出一种通用检测算法是极为困难的。该文针对飞机机舱内的可操纵物体：开关，按钮，油门杆，停车杆等，实现了一种实时精确的碰撞检测算法。