A new dynamics algorithm for articulated solid animation is presented. Applied to large scenes, it provides enhancements of computational efficiency and accuracy control with respect to previous solutions. It allows us to perform interactive animations which could be only computed off-line using previous methods.
The efficiency results from managing two sets of constraints associated with the kinematic graph, and proceeding in two steps. First, the acyclic constraints are solved in linear time. An iterative process then reduces the closed loop errors while maintaining the acyclic constraints. This allows the user to efficiently trade-off accuracy for computation time. The iterations are driven using a conjugate gradient algorithm, allowing the full use of matrix sparsity. We analyze the complexity, and investigate practical efficiency compared with other approaches. In contrast with previous research, we present a single method which is computationally efficient for acyclic bodies as well as for mesh-like bodies.
The accuracy control is provided by the iterative improvement performed by the algorithm, and also from the existence of two constraint priority levels induced by the method. Used in conjunction with a robust integration scheme, this new algorithm allows the interactive animation of scenes containing a few thousand geometric constraints including closed loops.
articulated solids, dynamics, constraints, iterative solution
François Faure
Institut für Computergrafik, Technische Universität Wien
francois@cg.tuwien.ac.at
http://www.cg.tuwien.ac.at/~francois/Public/Work/index.html