Improved algorithms for linear complementarity problems arising from collision response

D. Baraff, Dynamic simulation of non-penetrating rigid bodies, Ph.D. thesis, Cornell University, 1992. D. Baraff, Fast contact force computation for nonpenetrating rigid bodies, in: SIGGRAPH’94 Conference Proceedings, Annual Conference Series, ACM SIGGRAPH, Orlando, FL, USA, 1994, pp. 23–34. Terzopoulos, 1988, Physically-based models with rigid and deformable components, IEEE Comput. Graphics, 8, 41, 10.1109/38.20317 D. Baraff, A. Witkin, Large steps in cloth simulation, in: M. Cohen (Ed.), SIGGRAPH’98 Conference Proceedings, Annual Conference Series, ACM SIGGRAPH, Orlando, FL, USA, 1998, pp. 43–54. M. Desbrun, M.-P. Gascuel, Animating soft substances with implicit surfaces, in: SIGGRAPH’95 Conference Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, CA, USA, 1995, pp. 287–290. M. Desbrun, P. Schröder, A. Barr, Interactive animation of structured deformable objects, in: Graphics Interface’99, Kingston, Canada, 1999, http://www.multires.caltech.edu/pubs/GI99.pdf. Eberhardt, 1999, A particle system approach to knitted textiles, Comput. Graphics, 23, 599, 10.1016/S0097-8493(99)00077-1 M. Lin, S. Gottschalk, Collision detection between geometric models: a survey, in: Proceedings of IMA Conference on Mathematics of Surfaces, 1998, ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/cms.pdf. Pang, 1996, Complementarity formulations and existence of solutions of dynamic multi-rigid-body contact problems with Coulomb friction, Math. Program., 73, 199, 10.1007/BF02592103 Buck, 1998, Interactive rigid body manipulation with obstacle contacts, J. Visual. Comput. Animation, 9, 243, 10.1002/(SICI)1099-1778(1998100)9:4<243::AID-VIS189>3.0.CO;2-5 Chang, 1981, Polynomially bounded ellipsoid algorithms for convex quadratic programmings, Nonlinear Program., 4, 439 C.E. Lemke, On complementarity pivot theory, in: G.B. Dantzig, J.A.F. Veinott (Eds.), Mathematics of the Decision Sciences, American Mathematical Society, 1968, pp. 95–114. R. Cottle, J. Pang, R. Stone, The Linear Complementarity Problem, Academic Press, New York, 1992. J. Bochnak, M. Coste, M.-F. Roy, Géométrie Algébrique Réelle, Ergebnisse der Mathematik, Vol. 12, Springer, Berlin, 1987. A. Dolzmann, T. Sturm, Redlog User Manual, FMI, Universität Passau, Passau, Germany, 1999, http://www.fmi.uni-passau.de/ redlog/. Loos, 1993, Applying linear quantifier elimination, Comput. J., 5, 450, 10.1093/comjnl/36.5.450 V. Weispfenning, Quantifier elimination for real algebra—the cubic case, in: Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation (ISSAC’94), Association for Computing Machinery, Oxford, 1994, pp. 258–263.