An Efficient, Error-Bounded Approximation Algorithm for Simulating Quasi-Statics of Complex Linkages

Stephane Redon and Ming C. Lin
Department of Computer Science
University of North Carolina at Chapel Hill


Abstract

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.



Citation (download BibTex)
Stephane Redon and Ming C. Lin.
An Efficient, Error-Bounded Approximation Algorithm for Simulating Quasi-Statics of Complex Linkages.
In Proceedings of ACM Symposium on Solid and Physical Modeling, 2005.

Download PDF [5.3 MBytes]


Overview

 This paper introduces an algorithm for automatic simplification of the quasi-statics of articulated bodies (in the quasi-statics case, the articulated bodies velocities are zero at all times). Based on a user-defined maximum error threshold, the algorithm determines a set of joints which contribute most to the articulated body acceleration, and culls away the other joints (implicitly assuming that their acceleration is zero). This algorithm is linear in the number of processed joints. This allows for a significant speed-up when the required precision is low, or when the forces applied to the articulated body have a localized effect only, as demonstrated by our benchmarks.

The figure above shows an example of the progressive simplification of the articulated body motion when the user-defined error threshold varies: (a) shows a close-up view of the model; (b) shows the initial and final positions of the linkage, and the force applied to the last link of the chain; (c)-(e) compare the simulation results of the simplification algorithm to those of a linear-time algorithm, for varying degrees of precision, with both the view of the chain and a close-up of the end position.

Please refer to the paper for more details about the algorithm, benchmarks and analyses.

An extension of this algorithm to the general, dynamics case is available in our SIGGRAPH 2005 paper Adaptive Dynamics of Articulated Bodies.



Links

Authors pages:
      Stephane Redon
      Ming C. Lin

ACM Symposium on Solid and Physical Modeling
      Homepage

Generalization
       Adaptive dynamics of articulated bodies (extension to the dynamics case)

 

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Last revision : June 6, 2004