International audience

Abstract One of the major challenges in physically based modelling is making simulations efficient. Adaptive models provide an essential solution to these efficiency goals. These models are able to self‐adapt in space and time, attempting to provide the best possible compromise between accuracy and speed. This survey reviews the adaptive solutions proposed so far in computer graphics. Models are classified according to the strategy they use for adaptation, from time‐stepping and freezing techniques to geometric adaptivity in the form of structured grids, meshes and particles. Applications range from fluids, through deformable bodies, to articulated solids.

Molecular interactions typically have a high dynamic range (HDR), combining short-range stiff repulsive effects with long-range, soft attractive and repulsive terms. As a result, faithful haptic rendering of such molecular interactions is both important and difficult, in particular in applications where the precise perception of molecular forces is necessary (e.g. in molecular docking simulations). Traditionally, teleoperation coupling using constant gain control schemes have limited applications since they are unable to transmit to users low attractive forces without truncating repulsive ones. Furthermore, constant scaling displacement induces either instability or time-consuming experiments (displacements are slow), which deteriorates the ease of manipulation. In this paper, we describe a variable gain haptic coupling method specifically designed to render high dynamic range (molecular) forces. The proposed method is evaluated by user tests on an experiment involving two water molecules. We observe that variable force amplification is widely appreciated, whereas variable displacement scaling is appropriated only for users familiar with haptic manipulation. A complex experiment on a HIV molecule is carried out using this variable gain system. Advantages and limitations of this approach are discussed.

In this paper, a new tool dedicated to the analysis and the conception of molecules is presented. It is composed of an adaptive simulation software and a haptic device used to interact with molecules while feeling either the forces applied by the environment or the internal forces. The adaptive articulated body algorithm allows fast simulations of complex flexible molecules. To handle the coupling with the force feedback device, two different control schemes designed for nanoscale applications and providing high transparency rendering are proposed and compared.

Abstract We propose a method for view‐dependent simplification of articulated‐body dynamics, which enables an automatic trade‐off between visual precision and computational efficiency. We begin by discussing the problem of simplifying the simulation based on visual criteria, and show that it raises a number of challenging questions. We then focus on articulated‐body dynamics simulation, and propose a semi‐predictive approach which relies on a combination of exact, a priori error metrics computations, and visibility estimations. We suggest several variants of semi‐predictive metrics based on hierarchical data structures and the use of graphics hardware, and discuss their relative merits in terms of computational efficiency and precision. Finally, we present several benchmarks and demonstrate how our view‐dependent articulated‐body dynamics method allows an animator (or a physics engine) to finely tune the visual quality and obtain potentially significant speed‐ups during interactive or off‐line simulations. Copyright © 2008 John Wiley & Sons, Ltd.

We present a novel motion planning algorithm that efficiently generates physics-based samples in a kinematically and dynamically constrained space of a highly articulated chain. Similar to prior kinodynamic planning methods, the sampled nodes in our roadmaps are generated based on dynamic simulation. Moreover, we bias these samples by using constraint forces designed to avoid collisions while moving toward the goal configuration. We adaptively reduce the complexity of the state space by determining a subset of joints that contribute most towards the motion and only simulate these joints. Based on these configurations, we compute a valid path that satisfies non-penetration, kinematic, and dynamics constraints. Our approach can be easily combined with a variety of motion planning algorithms including probabilistic roadmaps (PRMs) and rapidly-exploring random trees (RRTs) and applied to articulated robots with hundreds of joints. We demonstrate the performance of our algorithm on several challenging benchmarks

This paper introduces a novel algorithm for haptic interaction with an adaptive simulation of articulated-body dynamics. Our algorithm has a multi-threaded structure, which allows us to separate the force feedback computation from the adaptive dynamics simulation. The algorithm we propose for force feedback computation has a logarithmic complexity in the number of degrees of freedom in the articulated body. We have implemented our approach and tested it on a 3.0GHz dual processor Xeon PC. The preliminary benchmarks presented here demonstrate that our multi-threaded approach, as well as the logarithmic complexity of the force feedback computation, allow us to interact in a stable way with large articulated bodies that have complex dynamics (such as articulated-body models of proteins). Whatever the update rate of the adaptive simulation loop, the force feedback computation is performed in a few tens of microseconds.

We present a fast continuous collision detection (CCD) algorithm for articulated models using Taylor models and temporal culling. Our algorithm is a generalization of conservative advancement (CA) from convex models [Mirtich 1996] to articulated models with non-convex links. Given the initial and final configurations of a moving articulated model, our algorithm creates a continuous motion with constant translational and rotational velocities for each link, and checks for interferences between the articulated model under continuous motion and other models in the environment and for self-collisions. If collisions occur, our algorithm reports the first time of contact (TOC) as well as collision witness features . We have implemented our CCD algorithm and applied it to several challenging scenarios including locomotion generation, articulated-body dynamics and character motion planning. Our algorithm can perform CCDs including self-collision detection for articulated models consisting of many links and tens of thousands of triangles in 1.22 ms on average running on a 3.6 GHz Pentium 4 PC. This is an improvement on the performance of prior algorithms of more than an order of magnitude.

This paper describes a generalization of the god-object method for haptic interaction between rigid bodies. Our approach separates the computation of the motion of the six degree-of-freedom god-object from the computation of the force applied to the user. The motion of the god-object is computed using continuous collision detection and constraint-based quasi-statics, which enables high-quality haptic interaction between contacting rigid bodies. The force applied to the user is computed using a novel constraint-based quasi-static approach, which allows us to suppress force artifacts typically found in previous methods. The constraint-based force applied to the user, which handles any number of simultaneous contact points, is computed within a few microseconds, while the update of the configuration of the rigid god-object is performed within a few milliseconds for rigid bodies containing up to tens of thousands of triangles. Our approach has been successfully tested on complex benchmarks. Our results show that the separation into asynchronous processes allows us to satisfy the different update rates required by the haptic and visual displays. Force shading and textures can be added and enlarge the range of haptic perception of a virtual environment. This paper is an extension of [1].

This paper describes a generalization of the god-object method for haptic interaction between rigid bodies. Our approach separates the computation of the motion of the six degree-of-freedom god-object from the computation of the force applied to the user. The motion of the god-object is computed using continuous collision detection and constraint-based quasi-statics, which enables high-quality haptic interaction between contacting rigid bodies. The force applied to the user is computed using a novel constraint-based quasi-static approach, which allows us to suppress force artifacts typically found in previous methods. Our approach has been implemented on a 3.2 GHz Xeon bi-processor and has been successfully tested on complex benchmarks. Our results show that the separation into asynchronous processes allows us to satisfy the different update rates required by the haptic and the visual displays. The constraint-based force applied to the user, which handles any number of simultaneous contact points, is typically computed within a few microseconds, while the update of the configuration of the rigid god-object is performed within a few milliseconds for rigid bodies containing up to tens of thousands of triangles.

Proximity query is an integral part of any motion planning algorithm and takes up the majority of planning time. Due to performance issues, most existing planners perform queries at fixed sampled configurations, sometimes resulting in missed collisions. Moreover, randomly determining collision-free configurations makes it difficult to obtain samples close to, or on, the surface of C-obstacles in the configuration space. In this paper, we present an efficient and practical local planning method in contact space which uses “continuous collision detection” (CCD). We show how, using the precise contact information provided by a CCD algorithm, a randomized planner can be enhanced by efficiently sampling the contact space, as well as by constraining the sampling when the roadmap is expanded. We have included our contact-space planning methods in a freely available state-of-the-art planning library - the Stanford MPK library. We have been able to observe that in complex scenarios involving cluttered and narrow passages, which are typically difficult for randomized planners, the enhanced planner offers up to 70 times performance improvement when our contact-space sampling and constrained sampling methods are enabled.

Design and analysis of articulated mechanical structures, commonly referred to as linkages, is an integral part of any CAD/CAM system. The most common approaches formulate the problem as purely geometric in nature, though dynamics or quasi-statics of linkages should also be considered. Existing optimal algorithms that compute forward dynamics or quasi-statics of linkages have a linear runtime dependence on the number of joints in the linkage. When forces are applied to a linkage, these techniques need to compute the accelerations of all the joints and can become impractical for rapid prototyping of highly complex linkages with a large number of joints.We introduce a novel algorithm that enables adaptive refinement of the forward quasi-statics simulation of complex linkages. This algorithm can cull away joints whose contribution to the overall linkage motion is below a given user-defined threshold, thus limiting the computation of the joint accelerations and forces to those that contribute most to the overall motion. It also allows a natural trade-off between the precision of the resulting simulation and the time required to compute it. We have implemented our algorithm and tested its performance on complex benchmarks consisting of up to 50,000 joints. We demonstrate that in some cases our algorithm is able to achieve up to two orders of magnitude of performance improvement, while providing a high-precision, error-bounded approximation of the quasi-statics of the simulated linkage.

Forward dynamics is central to physically-based simulation and control of articulated bodies. We present an adaptive algorithm for computing forward dynamics of articulated bodies: using novel motion error metrics, our algorithm can automatically simplify the dynamics of a multi-body system, based on the desired number of degrees of freedom and the location of external forces and active joint forces. We demonstrate this method in plausible animation of articulated bodies, including a large-scale simulation of 200 animated humanoids and multi-body dynamics systems with many degrees of freedom. The graceful simplification allows us to achieve up to two orders of magnitude performance improvement in several complex benchmarks.

Most of well-known approaches for rigid body simulations are formulated in the contact-space. Due to Gauss' principle of least constraints, the frictionless dynamics problems are formulated in a motion-space. While the two formulations are mathematically equivalent, they are not computationally equivalent. The motion-space formulation is better conditioned, always sparse, needs less memory, and avoids some unnecessary computations. A preliminary experimental comparison suggests that an algorithm operating in the motion-space takes advantage of sparsity to perform increasingly better than a contact-space algorithm as the average number of contact points per object increases.

A few years ago, Vanecek (1994) suggested to apply a variant of back-face culling to speed-up collision detection between polyhedral objects. However, Vanecek's method is linear in the number of faces in the object, which is unpractical for large models. This paper suggests to add some geometrical information to hierarchies of bounding volumes, typically used in collision detection, and perform conservative back-face culling at the bounding-volume level in constant time. The method described in this paper can be applied to complement any kind of bounding-volumes hierarchy and allows a trade-off between memory and speed. Preliminary experimental results suggest that the method allows a significant speed-up, especially in close proximity situations.

This paper introduces a fast continuous collision detection technique for polyhedral rigid bodies. As opposed to most collision detection techniques, the computation of the first contact time between two objects is inherently part of the algorithm. The method can thus robustly prevent objects interpenetrations or collisions misses, even when objects are thin or have large velocities. The method is valid for general objects (polygon soups), handles multiple moving objects and acyclic articulated bodies, and is efficient in low and high coherency situations. Moreover, the method can be used to speed up existent continuous collision detection methods for parametric or implicit rigid surfaces. The collision detection algorithms have been successfully coupled to a real-time dynamics simulator. Various experiments are conducted that show the method's ability to produce high-quality interaction (precise objects positioning for example) between models up to tens of thousands of triangles, which couldn't have been performed with previous continuous methods. Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Animation - Virtual Reality

This paper describes a new collision detection algorithm designed for interactive manipulation in virtual environments. Making some assumptions on object motion, the collision time between two objects can be computed by solving a polynomial equation whose degree is equal to or smaller than three.