Article

Free access

The virtual erector set: dynamic simulation with linear recursive constraint propagation

Authors:

Peter Schröder,

David ZeltzerAuthors Info & Claims

I3D '90: Proceedings of the 1990 symposium on Interactive 3D graphics

Pages 23 - 31

https://doi.org/10.1145/91385.91403

Published: 01 February 1990 Publication History

Abstract

We have implemented an algorithm for rigid body dynamics which unifies the advantages of linear recursive algorithms with the advantages of earlier linear algebra based constraint force approaches. No restriction is placed on the joints between links. The algorithm is numerically robust and can deal with arbitrary trees of bodies, including kinematic loops. Motion as well as force constraints on the dynamic behavior of any member of the linkage can be added easily. Through the use of spatial algebra notation---including our extension to account for spatial position---the mathematical expressions are simplified and more efficient to execute. The algorithm has been implemented on workstation class machines and performs at interactive speeds.

References

[1]

[1] ARMSTRONG, W. W. Recursive solution to the equations of motion of an n-link manipulator. In Proc. 5th World Congress Theory Mach. Mechanisms (1979), vol. 2, pp. 1243-1346.

[2]

[2] ARMSTRONG, W. W., AND GREEN, M. W. The dynamics of articulated rigid bodies for purposes of animation. Visual Computer (1985), 231-240.

[3]

[3] BALL, R. S. A Treatise on the Theory of Screws. Cambridge University Press, 1900.

[4]

[4] BARZEL, R., AND BARR, A. H. Controlling rigid bodies with dynamic constraints. In Course Notes: Developments in Physically Based Modelling. ACM Siggraph, 1988, ch. E.

[5]

[5] BARZEL, R., AND BARR, A. H. A modeling system based on dynamic constraints. Computer Graphics 22, 4 (August 1988), 179-188.

Digital Library

[6]

[6] BRETT, C., PIEPER, S., AND ZELTZER, D. Putting it all together: An integrated package for viewing and editing 3d microworlds. In Proc. 4th Usenix Computer Graphics Workshop (October 1987), pp. 3-12.

[7]

[7] FEATHERSTONE, R. The calculation of robot dynamics using articulated body inertias. The Intl. J. of Robotics Research 2, 1 (Spring 1983), 13-30.

[8]

[8] FEATHERSTONE, R. Robot Dynamics Algorithms. Kluwer Academic Publishers, 1987.

Digital Library

[9]

[9] GEAR, C. W. Numerical Initial Value Problems in Ordinary Differential Equations. Prentice-Hall, 1971.

Digital Library

[10]

[10] HAHN, J. K. Realistic animation of rigid bodies. In Proceedings SIGGRAPH (1988), pp. 299-308.

Digital Library

[11]

[11] HINDMARSH, A. C. Odepack, a systemized collection of ode solvers. In Scientific Computing, R. S. S. et. al., Ed. North-Holland, 1983, pp. 55-64.

[12]

[12] HOLLERBACH, J. M. A recursive lagrangian formulation for manipulator dynamics and a comparative study of dynamics formulation complexity. IEEE Trans. Syst. Man Cybern. 10, 11 (1980), 730-736.

[13]

[13] ISAACS, P. M., AND COHEN, M. F. Controlling dynamic simulation with kinematic constraints, behavior functions, and inverse dynamics. In Proceedings SIGGRAPH (1987), pp. 215-224.

Digital Library

[14]

[14] ISAACS, P. M., AND COHEN, M. F. Mixed methods for complex kinematic constraints in dynamic figure animation. The Visual Computer 4, 6 (1988), 296-305.

[15]

[15] LATHROP, R. H. Constrained (closed-loop) robot simulation by local constraint propagation. In Robotics and Automation (1986), IEEE Council on Robotics and Automation, pp. 689-694.

[16]

[16] LOTSTEDT, P. Mechanical systems of rigid bodies subject to unilateral constraints. SIAM J. Appl. Math. 42 (1982), 281-296.

Digital Library

[17]

[17] LOTSTEDT, P. Numerical simulation of time-dependent contact and friction problems in rigid body mechanics. SIAM J. Sci. Stat. Comput. 5, 2 (June 1984), 370-393.

[18]

[18] LUH, J. Y. S., WALKER, M. W., AND PAUL, R. P. C. On-line computational scheme for mechanical manipulators. Trans. ASME, J. Dyn. Sys. Measurement Contr. 102, 2 (1980), 69-76.

[19]

[19] MCKENNA, M. A dynamic model of locomotion for computer animation. Master's thesis, Massachusetts Institute of Technology, 1990.

[20]

[20] MOORE, M., AND WILHELMS, J. Collision detection and response for computer animation. In Proceedings SIGGRAPH (1988), pp. 289-298.

Digital Library

[21]

[21] ORIN, D. E., AND ET AL., Kinematic and kinetic analysis of open-chain linkages utilizing newton-euler methods. Math. Biosci. 43 (1979), 107-130.

[22]

[22] PAIGE, C. C., AND SAUNDERS, M. A. Lsqr: An algorithm for sparse linear equations and sparse least squares. ACM Trans. on Math. Software 8, 1 (March 1982), 43-71.

Digital Library

[23]

[23] SHOEMAKE, K. Animating rotation with quaternion curves. Computer Graphics 19, 3 (July 1985), 245-254.

Digital Library

[24]

[24] SHOEMAKE, K. Quaternion calculus for animation. In Course Notes: Math for Siggraph. ACM Siggraph, 1989, pp. 187-205.

[25]

[25] WALKER, M. W., AND ORIN, D. E. Efficient dynamic computer simulation of robotic mechanisms. In Proc. Joint Automatic Contr. Conf. (June 1981), pp. paper WP-2B.

[26]

[26] WILHELMS, J. Dynamic experiences. In Making Them Move: Mechanics, Control and Animation of Articulated Figures, D. Zeltzer, N. Badler, and B. Barsky, Eds. Morgan Kaufman, 1990. in preparation.

Digital Library

[27]

[27] WILHELMS, J., AND BARSKY, B. Using dynamics analysis to animate articulated bodies such as humans and robots. In Graphics Interface (1985), pp. 97-115.

Digital Library

[28]

[28] WITKIN, A., GLEICHER, M., AND WELCH, W. Interactive dynamics. In these proceedings (1990).

Digital Library

[29]

[29] WITKIN, A., AND KASS, M. Spacetime constraints. In Proceedings SIGGRAPH (1988), pp. 159-168.

Digital Library

[30]

[30] ZELTZER, D., PIEPER, S., AND STURMAN, D. J. An integrated graphical simulation platform. In Proc. Graphics Interface (1989), pp. 266-274.

Cited By

McKenna MZeltzer D(2019)Dynamic simulation of autonomous legged locomotionACM SIGGRAPH Computer Graphics10.1145/97880.9788224:4(29-38)Online publication date: 27-Jun-2019
https://dl.acm.org/doi/10.1145/97880.97882
Tomcin RSibbing DKobbelt L(2014)Efficient enforcement of hard articulation constraints in the presence of closed loops and contactsComputer Graphics Forum10.1111/cgf.1232233:2(235-244)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1111/cgf.12322
Weinstein RTeran JFedkiw R(2006)Dynamic Simulation of Articulated Rigid Bodies with Contact and CollisionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2006.4812:3(365-374)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1109/TVCG.2006.48
Show More Cited By

Index Terms

The virtual erector set: dynamic simulation with linear recursive constraint propagation

Recommendations

The virtual erector set: dynamic simulation with linear recursive constraint propagation

We have implemented an algorithm for rigid body dynamics which unifies the advantages of linear recursive algorithms with the advantages of earlier linear algebra based constraint force approaches. No restriction is placed on the joints between links. ...
Dynamic simulation of nonpenetrating rigid bodies
Impulse-based dynamic simulation in linear time
CASA 2007

This paper describes an impulse-based dynamic simulation method for articulated bodies which has a linear time complexity. Existing linear-time methods are either based on a reduced-coordinate formulation or on Lagrange multipliers. The impulse-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

I3D '90: Proceedings of the 1990 symposium on Interactive 3D graphics

February 1990

271 pages

ISBN:0897913515

DOI:10.1145/91385

Chairman:
Michael J. Zyda
Naval Postgraduate School, Monterey, CA

ACM SIGGRAPH Computer Graphics Volume 24, Issue 2
Mar. 1990
241 pages
ISSN:0097-8930
DOI:10.1145/91394
Editor:
Richard J. Beach
Xerox PARC, Palo Alto, CA
Issue’s Table of Contents

Copyright © 1990 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 148 of 485 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
667
Total Downloads

Downloads (Last 12 months)158
Downloads (Last 6 weeks)9

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

McKenna MZeltzer D(2019)Dynamic simulation of autonomous legged locomotionACM SIGGRAPH Computer Graphics10.1145/97880.9788224:4(29-38)Online publication date: 27-Jun-2019
https://dl.acm.org/doi/10.1145/97880.97882
Tomcin RSibbing DKobbelt L(2014)Efficient enforcement of hard articulation constraints in the presence of closed loops and contactsComputer Graphics Forum10.1111/cgf.1232233:2(235-244)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1111/cgf.12322
Weinstein RTeran JFedkiw R(2006)Dynamic Simulation of Articulated Rigid Bodies with Contact and CollisionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2006.4812:3(365-374)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1109/TVCG.2006.48
Lee DBae HTae Kim CLee DJung DLee NLee KBaek NWon Lee JWoo Ryu KHahn J(2001)Reproducing works of CalderThe Journal of Visualization and Computer Animation10.1002/vis.24712:2(81-91)Online publication date: 11-Jun-2001
https://doi.org/10.1002/vis.247
Kijimam RHirose M(1996)Representative Spherical Plane Method and Comsposition of Object Manipulation MethodsProceedings of the 1996 Virtual Reality Annual International Symposium (VRAIS 96)10.5555/832290.836031Online publication date: 30-Mar-1996
https://dl.acm.org/doi/10.5555/832290.836031
Kijima RHirose M(1996)Representative spherical plane method and composition of object manipulation methodsProceedings of the IEEE 1996 Virtual Reality Annual International Symposium10.1109/VRAIS.1996.490528(195-202)Online publication date: 1996
https://doi.org/10.1109/VRAIS.1996.490528
Zeltzer D(1992)Human figure modeling for virtual environment applications[1992] Proceedings IEEE International Workshop on Robot and Human Communication10.1109/ROMAN.1992.253925(117-122)Online publication date: 1992
https://doi.org/10.1109/ROMAN.1992.253925
Rijpkema HGirard M(1991)Computer animation of knowledge-based human graspingACM SIGGRAPH Computer Graphics10.1145/127719.12275425:4(339-348)Online publication date: 1-Jul-1991
https://dl.acm.org/doi/10.1145/127719.122754
Rijpkema HGirard MThomas J(1991)Computer animation of knowledge-based human graspingProceedings of the 18th annual conference on Computer graphics and interactive techniques10.1145/122718.122754(339-348)Online publication date: 1-Jul-1991
https://dl.acm.org/doi/10.1145/122718.122754
McKenna MZeltzer DBaskett F(1990)Dynamic simulation of autonomous legged locomotionProceedings of the 17th annual conference on Computer graphics and interactive techniques10.1145/97879.97882(29-38)Online publication date: 1-Sep-1990
https://dl.acm.org/doi/10.1145/97879.97882
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents