基于图像空间的复杂模型碰撞检测算法

提出一种使用图形硬件用于复杂模型间的快速的碰撞检测算法.算法是基于CULLIDE的执行GPU可见性查询来减少物体模型间没有邻近特征的子集,描述了一个分类方案计算物体潜在碰撞集和碰撞自由子集,提高了裁减的性能.为了减少CPU的负载,利用GPU的可编程性,在GPU上进行精确的物体相交计算.     

Efficient and Reliable Self‐Collision Culling Using Unprojected Normal Cones

We present an efficient and accurate algorithm for self‐collision detection in deformable models. Our approach can perform discrete and continuous collision queries on triangulated meshes. We present a simple and linear time algorithm to perform the normal cone test using the unprojected 3D vertices, which reduces to a sequence point‐plane classification tests. Moreover, we present a hierarchical traversal scheme that can significantly reduce the number of normal cone tests and the memory overhead using front‐based normal cone culling. The overall algorithm can reliably detect all (self) collisions in models composed of hundreds of thousands of triangles. We observe considerable performance improvement over prior continuous collision detection algorithms.     

TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds

http://gamma.cs.unc.edu/BSC/ We present a realtime and reliable continuous collision detection (CCD) algorithm between triangulated models that exploits the floating point hardware capability of current CPUs and GPUs. Our formulation is based on Bernstein Sign Classification that takes advantage of the geometry properties of Bernstein basis and Bézier curves to perform Boolean collision queries. We derive tight numerical error bounds on the computations and employ those bounds to design an accurate algorithm using finite‐precision arithmetic. Compared with prior floatingpoint CCD algorithms, our approach eliminates all the false negatives and 90–95% of the false positives. We integrated our algorithm (TightCCD) with physically‐based simulation system and observe speedups in collision queries of 5–15X compared with prior reliable CCD algorithms. Furthermore, we demonstrate its benefits in terms of improving the performance or robustness of cloth simulation systems.     

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.     

Partitioning and Handling Massive Models for Interactive Collision Detection

We describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the "regions of interest" within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off-line, pre-processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub-graphs to check the corresponding geometry for proximity and pre-fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding-volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real-time on such a model. In terms of model complexity and application to large models, we have improved the performance of interactive collision detection and proximity computation algorithms by an order of magnitude.     

基于两级非渗透滤波的连续碰撞检测算法*

为提高高精度模型在物理仿真中的碰撞检测效率,提出了一种基于两级非渗透滤波的连续碰撞检测算法,对无碰撞可能性的基本图元对进行快速剔除。首先,通过给基本图元增加额外的层次包围盒,对没有发生重叠的基本图元对进行第一级滤除。其次,采用代数滤波器对通过第一级滤除的基本图元对进行低层滤除。实验结果表明,本文的方法不仅可以有效地检测出碰撞信息,而且可以在物体发生大幅度形变时发挥较好的滤波特性。     

一种基于分离包围盒的快速碰撞检测算法

提出了一种基于分离包围盒(SBVs)的快速碰撞检测方法.SBVs的空间形态和位置由两个模型的最优分离平面所决定,这使得它不仅可以快速检测出分离模型,而且在模型相交的情况下能够有效地缩小精确检测的范围.为了能够快速计算SBVs,设计并验证了一种基于SVM的近似计算SBVs方法.最后将SBV和图形硬件的计算优势结合起来,以实现复杂模型相交区的穿刺查询.实验结果表明,基于SBVs的碰撞检测算法能够高效、平衡地处理无拓扑模型的分离、碰撞,尤其是穿刺等复杂情况.     

Adjacency-based culling for continuous collision detection

We present an efficient approach to reduce the number of elementary tests for continuous collision detection between rigid and deformable models. Our algorithm exploits connectivity information and uses the adjacency relationships between triangles to perform hierarchical culling. This can be combined with table-based lookups to eliminate duplicate elementary tests. In practice, our approach can reduce the number of elementary tests by two orders of magnitude. We demonstrate the performance of our algorithm on various challenging rigid body and deformable simulations.     

基于AABB树的聚变堆形变部件碰撞检测算法

针对工程设计中形变部件的限元模型的碰撞检测问题,提出了一种基于AABB树的快速碰撞检测算法.对于需要分析的有限元,对几何表面进行三角化,随后建立AABB包围盒,并采用优化的AABB树算法进行空间划分;利用AABB树与包围盒排除不相交图形,采用Devillers算法测试三角形相交,并利用并行方式加快计算.实验结果表明,本算法有效提高了碰撞检测的效率,适用于复杂有限元模型的碰撞检测.     

Efficient conservative visibility culling using theprioritized-layered projection algorithm

We propose a novel conservative visibility culling technique based on the Prioritized-Layered Projection (PLP) algorithm. PLP is a time-critical rendering technique that computes, for a given viewpoint, a partially correct image by rendering only a subset of the geometric primitives, those that PLP determines to be most likely visible. Our new algorithm builds on PLP and provides an efficient way of finding the remaining visible primitives. We do this by adding a second phase to PLP which uses image-space techniques for determining the visibility status of the remaining geometry. Another contribution of our work is to show how to efficiently implement such image-space visibility queries using currently available OpenGL hardware and extensions. We report on the implementation of our techniques on several graphics architectures, analyze their complexity, and discuss a possible hardware extension that has the potential to further increase performance     

A fast algebraic non-penetration filter for continuous collision detection

Continuous collision detection is a key technique to meet non-penetration requirements in many applications. Even though it is possible to perform efficient culling operations in the broad stage of a continuous collision detection algorithm, such as bounding volume hierarchies, a huge number of potentially colliding triangles still survive and go to the succeeding narrow stage. This heavily burdens the elementary collision tests in a collision detection algorithm and affects the performance of the entire pipeline, especially for fast moving or deforming objects. This paper presents a low-cost filtering algorithm using algebraic analysis techniques. It can significantly reduce the number of elementary collision tests that occur in the narrow stage. We analyze the root existence during the time interval [0, 1] for a standard cubic equation defining an elementary collision test. We demonstrate the efficiency of the algebraic filter in our experiments. Cubic-solvers augmented by our filtering algorithm are able to achieve up to 99% filtering ratios and more than 10 ×  performance improvement against the standard cubic-solver without any filters.     

Efficient Image‐Based Proximity Queries with Object‐Space Precision

We present an efficient algorithm for object‐space proximity queries between multiple deformable triangular meshes. Our approach uses the rasterization capabilities of the GPU to produce an image‐space representation of the vertices. Using this image‐space representation, inter‐object vertex‐triangle distances and closest points lying under a user‐defined threshold are computed in parallel by conservative rasterization of bounding primitives and sorted using atomic operations. We additionally introduce a similar technique to detect penetrating vertices. We show how mechanisms of modern GPUs such as mipmapping, Early‐Z and Early‐Stencil culling can optimize the performance of our method. Our algorithm is able to compute dense proximity information for complex scenes made of more than a hundred thousand triangles in real time, outperforming a CPU implementation based on bounding volume hierarchies by more than an order of magnitude.     

gProximity: Hierarchical GPU‐based Operations for Collision and Distance Queries

We present novel parallel algorithms for collision detection and separation distance computation for rigid and deformable models that exploit the computational capabilities of many‐core GPUs. Our approach uses thread and data parallelism to perform fast hierarchy construction, updating, and traversal using tight‐fitting bounding volumes such as oriented bounding boxes (OBB) and rectangular swept spheres (RSS). We also describe efficient algorithms to compute a linear bounding volume hierarchy (LBVH) and update them using refitting methods. Moreover, we show that tight‐fitting bounding volume hierarchies offer improved performance on GPU‐like throughput architectures. We use our algorithms to perform discrete and continuous collision detection including self‐collisions, as well as separation distance computation between non‐overlapping models. In practice, our approach (gProximity) can perform these queries in a few milliseconds on a PC with NVIDIA GTX 285 card on models composed of tens or hundreds of thousands of triangles used in cloth simulation, surgical simulation, virtual prototyping and N‐body simulation. Moreover, we observe more than an order of magnitude performance improvement over prior GPU‐based algorithms.     

Interactive collision detection for deformable models using streaming AABBs

We present an interactive and accurate collision detection algorithm for deformable, polygonal objects based on the streaming computational model. Our algorithm can detect all possible pairwise primitive-level intersections between two severely deforming models at highly interactive rates. In our streaming computational model, we consider a set of axis aligned bounding boxes (AABBs) that bound each of the given deformable objects as an input stream and perform massively-parallel pairwise, overlapping tests onto the incoming streams. As a result, we are able to prevent performance stalls in the streaming pipeline that can be caused by expensive indexing mechanism required by bounding volume hierarchy-based streaming algorithms. At runtime, as the underlying models deform over time, we employ a novel, streaming algorithm to update the geometric changes in the AABB streams. Moreover, in order to get only the computed result (i.e., collision results between AABBs) without reading back the entire output streams, we propose a streaming en/decoding strategy that can be performed in a hierarchical fashion. After determining overlapped AABBs, we perform a primitive-level (e.g., triangle) intersection checking on a serial computational model such as CPUs. We implemented the entire pipeline of our algorithm using off-the-shelf graphics processors (GPUs), such as nVIDIA GeForce 7800 GTX, for streaming computations, and Intel Dual Core 3.4G processors for serial computations. We benchmarked our algorithm with different models of varying complexities, ranging from 15K up to 50K triangles, under various deformation motions, and the timings were obtained as 30 approximately 100 FPS depending on the complexity of models and their relative configurations. Finally, we made comparisons with a well-known GPU-based collision detection algorithm, CULLIDE [4] and observed about three times performance improvement over the earlier approach. We also made comparisons with a SW-based AABB culling algorithm [2] and observed about two times improvement.     

HPCCD: Hybrid Parallel Continuous Collision Detection using CPUs and GPUs

We present a novel, hybrid parallel continuous collision detection (HPCCD) method that exploits the availability of multi‐core CPU and GPU architectures. HPCCD is based on a bounding volume hierarchy (BVH) and selectively performs lazy reconstructions. Our method works with a wide variety of deforming models and supports self‐collision detection. HPCCD takes advantage of hybrid multi‐core architectures – using the general‐purpose CPUs to perform the BVH traversal and culling while GPUs are used to perform elementary tests that reduce to solving cubic equations. We propose a novel task decomposition method that leads to a lock‐free parallel algorithm in the main loop of our BVH‐based collision detection to create a highly scalable algorithm. By exploiting the availability of hybrid, multi‐core CPU and GPU architectures, our proposed method achieves more than an order of magnitude improvement in performance using four CPU‐cores and two GPUs, compared to using a single CPU‐core. This improvement results in an interactive performance, up to 148 fps, for various deforming benchmarks consisting of tens or hundreds of thousand triangles.     

Accurate and Fast Proximity Queries Between Polyhedra Using Convex Surface Decomposition

The need to perform fast and accurate proximity queries arises frequently in physically-based modeling, simulation, animation, real-time interaction within a virtual environment, and game dynamics. The set of proximity queries include intersection detection, tolerance verification, exact and approximate minimum distance computation, and (disjoint) contact determination. Specialized data structures and algorithms have often been designed to perform each type of query separately. We present a unified approach to perform any of these queries seamlessly for general, rigid polyhedral objects with boundary representations which are orientable 2-manifolds. The proposed method involves a hierarchical data structure built upon a surface decomposition of the models. Furthermore, the incremental query algorithm takes advantage of coherence between successive frames. It has been applied to complex benchmarks and compares very favorably with earlier algorithms and systems.     

Segment Tracing Using Local Lipschitz Bounds

We introduce Segment Tracing, a new algorithm that accelerates the classical Sphere Tracing method for computing the intersection between a ray and an implicit surface. Our approach consists in computing the Lipschitz bound locally over a segment to improve the marching step computation and accelerate the overall process. We describe the computation of the Lipschitz bound for different operators and primitives. We demonstrate that our algorithm significantly reduces the number of field function queries compared to previous methods, without the need for additional accelerating data-structures. Our method can be applied to a vast variety of implicit models ranging from hierarchical procedural objects built from complex primitives, to simulation-generated implicit surfaces created from many particles.     

AD-Frustum: adaptive frustum tracing for interactive sound propagation

We present an interactive algorithm to compute sound propagation paths for transmission, specular reflection and edge diffraction in complex scenes. Our formulation uses an adaptive frustum representation that is automatically sub-divided to accurately compute intersections with the scene primitives. We describe a simple and fast algorithm to approximate the visible surface for each frustum and generate new frusta based on specular reflection and edge diffraction. Our approach is applicable to all triangulated models and we demonstrate its performance on architectural and outdoor models with tens or hundreds of thousands of triangles and moving objects. In practice, our algorithm can perform geometric sound propagation in complex scenes at 4-20 frames per second on a multi-core PC.     

面向移动终端的三维模型简化与碰撞检测方法研究

移动终端三维场景的绘制与漫游由于其庞大的模型数据量和复杂的外观形态使得实现清晰的场景快速绘制十分困难。为了加快模型的绘制,提出了一种面向移动终端的三维模型的简化与碰撞检测方法,以优化绘制过程。该方法通过二次测量误差半边折叠算法来简化三维模型,并利用八叉树技术对不能显示在屏幕中的场景进行剔除,从而实现三维场景的快速读取、组织和绘制。针对移动设备的屏幕尺寸以及计算能力等限制,实现了适用于移动平台的碰撞检测算法,减少了计算量。实验结果表明,该方法能有效地简化模型,并提高绘制效率,同时减少碰撞检测的计算时间,因而可应用于三维场景的快速逼真绘制。