Substructuring permits parallelization of physics simulation on multi-core CPUs. We present a new substructuring approach for solving stiff multibody systems containing both bilateral and unilateral constraints. Our approach is based on non-overlapping domain decomposition with the Schur complement method, which we extend to systems involving contact formulated as a mixed bounds linear complementarity problem. At each time step, we alternate between solving the subsystem and interface constraint impulses, which leads to the identification of the active constraints. By using the active constraints to compute the effective mass of subsystems within the interface solve, we obtain an exact solution. We demonstrate that our simulations have preferable behavior compared to standard iterative solvers and substructuring techniques based on the exchange of forces at interface bodies. We observe considerable speedups for structured simulations where a user-defined partitioning can be applied, and moderate speedups for unstructured simulations, such as piles of bodies. In the latter case, we propose an automatic partitioning strategy based on the degree of bodies in the constraint graph. Because our method makes use of direct solvers, we are able to achieve interactive and real-time frame rates for a number of challenging scenarios involving large mass ratios, redundant constraints, and ill-conditioned systems.

This paper focuses on the stable and efficient simulation of articulated rigid body systems for real-time applications. Specifically, we focus on the use of geometric stiffness which can dramatically increase simulation stability. We examine several numerical problems with the inclusion of geometric stiffness in the equations of motion, as proposed by previous work, and address these issues by introducing a novel method for efficiently building the linear system. This offers improved tractability and numerical efficiency. Furthermore, geometric stiffness tends to significantly dissipate kinetic energy. We propose an adaptive damping scheme, inspired by the geometric stiffness, that uses a stability criterion based on the numerical integrator to determine the amount of non-constitutive damping required to stabilize the simulation. With this approach, not only is the dynamical behavior better preserved, but the simulation remains stable for mass ratios of 1,000,000-to-1 at time steps up to 0.1 s. We present a number of challenging scenarios to demonstrate that our method improves efficiency, and that it increases stability by orders of magnitude compared to previous work.

We present a method for the simulation of compliant, articulated structures using a plausible approximate model that focuses on modeling endpoint interaction. We approximate the structure's behavior about a reference configuration, resulting in a first order reduced compliant system, or FORK (-1) S. Several levels of approximation are available depending on which parts and surfaces we would like to have interactive contact forces, allowing various levels of detail to be selected. Our approach is fast and computation of the full structure's state may be parallelized. Furthermore, we present a method for reducing error by combining multiple FORK (-1)S models at different linearization points, through twist blending and matrix interpolation. Our approach is suitable for stiff, articulate grippers, such as those used in robotic simulation, or physics-based characters under static proportional derivative control. We demonstrate that simulations with our method can deal with kinematic chains and loops with non-uniform stiffness across joints, and that it produces plausible effects due to stiffness, damping, and inertia.

We present a method for the simulation of compliant, articulated structures using a plausible approximate model that focuses on modeling endpoint interaction. We approximate the structure's behavior about a reference configuration, resulting in a first order reduced compliant system, or FORK-1S. Several levels of approximation are available depending on which parts and surfaces we would like to have interactive contact forces, allowing various levels of detail to be selected. Our approach is fast and computation of the full structure's state may be parallelized. Our approach is suitable for stiff, articulate grippers, such as those used in robotic simulation, or physics based characters under static proportional derivative control. We demonstrate that simulations with our method can deal with kinematic chains and loops with non-uniform stiffness across joints, and that it produces plausible effects due to stiffness, damping, and inertia.

No abstract available.

Generation of a three-dimensional model from an unorganized set of points is an active area of research in computer graphics. Alpha shapes can be employed to construct a surface which most closely reflects the object described by the points. However, no /spl alpha/-shape, for any value of /spl alpha/, can properly detail discontinuous regions of a model. We introduce herein two methods of improving the results of reconstruction using /spl alpha/-shapes: density-scaling, which modulates the value of a depending on the density of points in a region; and anisotropic shaping, which modulates the form of the /spl alpha/-ball based on point normals. We give experimental results that show the successes and limitations of our method.

No abstract available.

Consider the problem of quantifying the quality of a multifinger grasp. The "traditional" grasp quality measures, which are based on inscribing a sphere in the set of wrenches which a grasp can resist, suffer from being dependent on the coordinate system of the object being grasped. In fact, we show that by changing the coordinate system, one can make these measures arbitrarily small. In this paper we generalize these measures in a natural way, and propose a new measure which is invariant under rigid motions of the object coordinate system. It is based on a certain class of ellipsoids which captures the changes in wrench space that occur.

Considers the problem of grasping an unknown polygonal flat object using a parallel jaw gripper. The authors propose to equip a standard gripper with several light-beam sensors (close to each jaw) and describe a reactive grasping algorithm. This is done by probing the object to locate a good grasp position, and then grasping, without moving the object significantly. The goal is to do as little motion as possible to find a grasp. This algorithm can be viewed in, a competitive framework, where the authors' algorithm is competing against any algorithm which already knows the object.>