Graceful Degradation of Collision Handling in Physically Based Animation

Interactive simulation is made possible in many applications by simplifying or culling the finer details that would make real-time performance impossible. This paper examines detail simplification in the specific problem of collision handling for rigid body animation. We present an automated method for calculating consistent collision response at different levels of detail. The mechanism works closely with a system which uses a pre-computed hierarchical volume model for collision detection.     

基于碰撞响应的三维空间多刚体实时运动仿真

该文将计算机科学与理论力学相结合，以刚性球体为例介绍了多刚体物理运动仿真的步骤和方法。首先论述了单个及多个刚体的运动仿真步骤以及应用叠加原理计算合力及合力矩的方法。然后，针对刚体运动中的不同碰撞响应类型：碰撞接触与临时接触，提出分别建立不同的碰撞响应力学模型，前者采用动量及动量矩定理建立响应模型，后者通过分析刚体的受力和运动状态建立相应的动力学模型。最后，详细讨论了刚性球体的碰撞仿真，包括它的碰撞测定、碰撞响应模型的建立及求解等，实现了三维空间中刚性球体实时、精确、快速的运动仿真，为以后多刚体大规模仿真奠定基础。     

A modular haptic rendering algorithm for stable and transparent 6-DOF manipulation

This paper presents a modular algorithm for six-degree-of-freedom (6-DOF) haptic rendering. The algorithm is aimed to provide transparent manipulation of rigid models with a high polygon count. On the one hand, enabling a stable display is simplified by exploiting the concept of virtual coupling and employing passive implicit integration methods for the simulation of the virtual tool. On the other hand, transparency is enhanced by maximizing the update rate of the simulation of the virtual tool, and thereby the coupling impedance, and allowing for stable simulation with small mass values. The combination of a linearized contact model that frees the simulation from the computational bottleneck of collision detection, with penalty-based collision response well suited for fixed time-stepping, guarantees that the motion of the virtual tool is simulated at the same high rate as the synthesis of feedback force and torque. Moreover, sensation-preserving multiresolution collision detection ensures a fast update of the linearized contact model in complex contact scenarios, and a novel contact clustering technique alleviates possible instability problems induced by penalty-based collision response.     

船桥碰撞简化动力分析方法:简化动力模型

为促进碰撞有限元分析技术在桥梁设计工程中的应用,提出2种可用于船桥碰撞动力分析和进行船桥碰撞动力设计的简化力学模型,即简化强迫振动模型和简化碰撞模型.基于碰撞数值模拟技术获得这2种模型中简化冲击力和简化船首非线性接触刚度.建议3种简化冲击力的数学模型,即简化的半波正弦载荷、修正半波正弦载荷及多段线载荷.建立3 000 ...     

Pseudo-interference stiffness estimation, a highly efficient numerical method for force evaluation in contact problems

This paper presents a novel method, Pseudo-Interference Stiffness Estimation (PISE), for evaluating the contact compliance and the contact load in the contacting elastic solids. The PISE method is based on the evaluation of the geometric overlap of two assumedly rigid bodies and estimation of the contact force based on this artificial overlap area (or volume). In this paper, an example of the dynamic simulation of two disk collision problem is solved both by PISE method and finite element contact model. The contact force and velocity changes during impact from both methods are shown to be in good agreement. However, PISE method is, computationally, orders of magnitude (about 3000 times in our numerical simulations) faster than finite element contact analysis. The proposed method will be of practical use in contact force approximation of contacting bodies, such as meshing of spur gear teeth, cam analysis and synthesis, robotic grabbing, and numerous other applications.     

Distant Collision Response in Rigid Body Simulations

We use a finite element model to predict the vibration response of objects in a rigid body simulation, such that rigid objects are augmented to provide a plausible elastic collision response between distant objects due to vibration. We start with a generalized eigenvalue decomposition of the elastic model to precompute a response to an impact at any point on an elastic object with fixed boundary conditions. Then, given a collision between objects, we generate an approximate response impulse to distribute to other objects already in contact with the colliding bodies. This can lead to distant impacts causing an object to slip, or a delicate stack of objects to fall. We also use a geodesic distance based spatial attenuation approximation for travelling waves in objects to respond to an impact at one contact with an impulse at other locations. This response ultimately allows a long distance relationship between contacts, both across a single object being struck, but also traversing the contact graph of a larger collection of objects. We qualitatively validate our approach with a ground truth simulation, and demonstrate a number of scenarios where a long distance relationship between contacts is valuable.     

Quadratic Contact Energy Model for Multi‐impact Simulation

Simultaneous multi‐impact simulation is a challenging problem that frequently arises in physically‐based modeling of rigid bodies. There are several physical criteria that should be satisfied for rigid body collision handling, but existing methods generally fail to meet one or more of them. In order to capture the inner process of potential energy variation, which is the physical foundation of collisions in a multi‐impact system, we present a novel quadratic contact energy model for rigid body simulation. By constructing quadratic energy functions with respect to the impulses, post‐impact reactions of rigid bodies can be computed efficiently. Our model can satisfy the physical criteria and can simulate various natural phenomena including the wave effect. Also, our model can be easily combined with Linear Complementary Problem (LCP) and can provide feasible results with any restitution coefficient. In practice, our model can solve the simultaneous multi‐impact problem efficiently and robustly, and we highlight its performance on different benchmarks.     

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.     

Interactive continuous collision detection for non-convex polyhedra

We present a highly interactive, continuous collision detection algorithm for rigid, general polyhedra. Given initial and final configurations of a moving polyhedral model, our algorithm creates a continuous motion with constant translational and angular velocities, thereby interpolating the initial and final configurations of the model. Then, our algorithm reports whether the model under the interpolated motion collides with other rigid polyhedral models in environments, and if it does, the algorithm reports its first time of contact (TOC) with the environment as well as its associated contact features at TOC. Our algorithm is a generalization of conservative advancement [19] to general polyhedra. In this approach, we calculate the motion bound of a moving polyhedral model and estimate the TOC based on this bound, and advance the model by the current TOC estimate. We iterate this process until the inter-distance between the moving model and the other objects in the environments is below a user-defined distance threshold. We pose the problem of calculating the motion bound as a linear programming problem and provide an efficient, novel solution based on the simplex method. Moreover, we also provide a hierarchical advancement technique based on a bounding volume traversal tree to generalize the conservative advancement for non-convex models. Our algorithm is relatively simple to implement and has very small computational overhead of merely performing discrete collision detection multiple times. We extensively benchmarked our algorithm in different scenarios, and in comparison to other known continuous collision detection algorithms, the performance improvement ranges by a factor of 1.4～45.5 depending on benchmarking scenarios. Moreover, our algorithm can perform CCD at 120～15460 frames per second on a 3.6 GHz Pentium 4 PC for complex models consisting of 10K～70K triangles.     

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.     

A fast impulsive contact suite for rigid body simulation

A suite of algorithms is presented for contact resolution in rigid body simulation under the Coulomb friction model: Given a set of rigid bodies with many contacts among them, resolve dynamic contacts (collisions) and static (persistent) contacts. The suite consists of four algorithms: 1) partial sequential collision resolution, 2) final resolution of collisions through the solution of a single convex QP (positive semidefinite quadratic program), 3) resolution of static contacts through the solution of a single convex QP, 4) freezing of "stationary" bodies. This suite can generate realistic-looking results for simple examples yet, for the first time, can also tractably resolve contacts for a simulation as large as 1,000 cubes in an "hourglass". Freezing speeds up this simulation by more than 25 times. Thanks to excellent commercial QP technology, the contact resolution suite is simple to implement and can be "plugged into" any simulation algorithm to provide fast and realistic-looking animations of rigid bodies.     

基于约束的刚体碰撞响应仿真研究与应用

为了解决虚拟场景中刚体碰撞与穿透问题,采用了一种基于约束的碰撞响应方法。根据刚体之间的穿透深度和在碰撞点处的相对速度,判定不同的碰撞状态。通过将多刚体碰撞和多点碰撞分割为单个碰撞,以刚体在碰撞点相对速度法向分量构建法向约束,切向分量构建切向摩擦约束。根据不同的碰撞状态以及牛顿恢复系数碰撞模型求取法向误差,并以碰撞点相对速度切向分量作为切向摩擦误差。结合约束与误差,得到碰撞的约束方程,联合刚体的动力学方程,迭代求解,计算碰撞之后刚体的速度,更新刚体的坐标与姿态,并计算刚体顶点在世界坐标系中的坐标。在虚拟矿山场景中进行了应用,仿真效果较好。     

Combining deformable- and rigid-body mechanics simulation

We present an interface between a deformable-body mechanics model and a rigid-body mechanics model. What is novel with our approach is that the physical representation in both the models is the same, which ensures behavioral correctness and allows great flexibility. We use a mass–spring representation extended with the concept of volume, and thus contact and collision. All physical interaction occurs between the mass elements only; thus there is no need for the explicit handling of interaction between rigid and deformable bodies or between rigid and rigid bodies. This also means that bodies can be partially rigid and partially deformable. It is also possible to change dynamically whether part of a body should be rigid or not. We present a demonstration example and possible applications in conceptual design engineering, geometric modeling, as well as computer animation.     

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.     

一种基于可能碰撞集的碰撞检测方法

为了提高虚拟环境中碰撞检测的实时性和有效性,提出了一种基于可能碰撞集的碰撞检测方法.该方法首先通过预测环境中刚体在当前帧和下一帧之间的可能运动轨迹来构建一个各边与世界坐标系各坐标轴平行,且包围该运动轨迹的包围盒;然后利用空间平铺技术来快速检测与某一平铺单元同时相交的轨迹包围盒,即可得到当前帧的可能碰撞集;接着对可能碰撞集中的刚体对进行最早碰撞时间tmin的求解,并根据tmin进行排序;最后只对具有最小tmin值的刚体对进行碰撞检测.仿真试验结果表明,与目前已有的碰撞检测算法相比,该方法简单、快速,不仅可以有效解决多个刚体环境中碰撞发生的次序问题,同时,该方法还能保证碰撞检测的完整性和唯一性.另外,理论和实践也证明了该方法的正确性和有效性.     

一种快速计算三维空间中物体碰撞接触面的方法

介绍了一种利用三维空间中物体运动的时空相关性 ,以碰撞检测取得的两物体碰撞三角面为计算域 ,快速寻找凸多面体发生碰撞时接触面的方法。该方法利用特征点来描述接触面 ;根据接触面的拓扑结构计算碰撞三角面间的点 -面、边 -边的最小距离 ,从而快速确定碰撞位置、接触面特征点及接触面的法线 ,并简要叙述了点 -面、边 -边接触的计算流程。该方法通过缩小接触面的计算范围 ,简化接触面法线 ,提高了碰撞测定的实时性。通过实际应用 ,证明了该方法的可行性 ,适用于三维游戏制作、虚拟现实中的物理仿真等各项应用研究。     

Fast continuous collision detection and handling for desktop virtual prototyping

This paper presents an overview of our recent work on continuous collision detection methods and constraints handling for rigid polyhedral objects. We demonstrate that continuous collision detection algorithms are practical in interactive dynamics simulation of complex polyhedral rigid bodies and show how continuous collision detection and efficient constraint-based dynamics algorithms allow us to perform various virtual prototyping tasks intuitively, precisely and robustly on commodity desktop computers. Especially, we present two applications of our system to actual industrial cases. We note that both tasks are performed with a simple 2D mouse on a high-end computer.     

Interactive simulation of solid rigid bodies

The article describes the implementation of an interactive system for simulating rigid bodies with contact and friction. The system can simulate moderately complex mechanical systems at interactive rates (20-30 Hz on low end Silicon Graphics workstations). New objects and user specified constraints can be added into the simulation environment on the fly. The system uses analytical methods to compute contact forces, as opposed to the penalty methods common in other interactive systems. Currently, the system's weakest feature is that it can fail to detect high speed collisions. Objects that move at high speeds (relative to the step size of the simulation) are subject to a form of aliasing and may tunnel through other objects without causing a collision. Other simplifications of the system involve approximating collision times and locations by interpolation methods, and periodic error correction adjustments of geometric tolerances. It is difficult to try to quantify the error incurred by a given approximation or tradeoff. Some of the design choices will likely curtail the system's use for highly predictive applications. However, they do not seriously affect simulating the basic dynamics of a mechanism like a feeder. In general, the system performs with sufficient accuracy and realism to be considered a viable interactive simulation environment     

Hierarchical spherical distance fields for collision detection

The problem of collision detection between objects is fundamental in many different communities including CAD, robotics, computer graphics, and computational geometry. This article presents a fast collision detection technique for all types of rigid bodies, demonstrated using polygon soups. We present two algorithms for computing a discrete spherical distance field of models. For compactly storing the distance field, we use a subsampling filter bank.