Anmerkungen:
Part of: Synthesis digital library of engineering and computer science. - Includes bibliographical references (pages 145-150). - Compendex. INSPEC. Google scholar. Google book search. - Title from PDF title page (viewed on February 22, 2015)
Includes bibliographical references (pages 145-150)
Part of: Synthesis digital library of engineering and computer science
1. Introduction -- 1.1 Understanding the problem -- 1.1.1 First-order optimality is a linear complementarity problem -- 1.1.2 Nonsmooth root search reformulations -- 1.1.3 The boxed linear complementarity problem -- 1.1.4 Other reformulations -- 1.2 The problem in n-dimensions -- 1.2.1 1D BLCP to 4D LCP -- 1.2.2 The boxed linear complementarity problem in higher dimensions -- 1.2.3 BLCP and the QP formulation -- 1.2.4 Converting BLCP to LCP -- 1.2.5 Nonsmooth reformulations of BLCP -- 1.3 Examples from physics-based animation -- 1.3.1 Fluid-solid wall boundary conditions -- 1.3.2 Free-flowing granular matter -- 1.3.3 Density correction -- 1.3.4 Joint limits in inverse kinematics -- 1.3.5 Contact force examples --
System requirements: Adobe Acrobat Reader
Mode of access: World Wide Web
Beschreibung:
Linear complementarity problems (LCPs) have for many years been used in physics-based animation to model contact forces between rigid bodies in contact. More recently, LCPs have found their way into the realm of fluid dynamics. Here, LCPs are used to model boundary conditions with fluid-wall contacts. LCPs have also started to appear in deformable models and granular simulations. There is an increasing need for numerical methods to solve the resulting LCPs with all these new applications. This book provides a numerical foundation for such methods, especially suited for use in computer graphics. This book is mainly intended for a researcher/Ph.D. student/post-doc/professor who wants to study the algorithms and do more work/research in this area. Programmers might have to invest some time brushing up on math skills, for this we refer to Appendices A and B. The reader should be familiar with linear algebra and differential calculus. We provide pseudo code for all the numerical methods, which should be comprehensible by any computer scientist with rudimentary programming skills. The reader can find an online supplementary code repository, containing Matlab implementations of many of the core methods covered in these notes, as well as a few Python implementations [Erleben, 2011]
1. Introduction -- 1.1 Understanding the problem -- 1.1.1 First-order optimality is a linear complementarity problem -- 1.1.2 Nonsmooth root search reformulations -- 1.1.3 The boxed linear complementarity problem -- 1.1.4 Other reformulations -- 1.2 The problem in n-dimensions -- 1.2.1 1D BLCP to 4D LCP -- 1.2.2 The boxed linear complementarity problem in higher dimensions -- 1.2.3 BLCP and the QP formulation -- 1.2.4 Converting BLCP to LCP -- 1.2.5 Nonsmooth reformulations of BLCP -- 1.3 Examples from physics-based animation -- 1.3.1 Fluid-solid wall boundary conditions -- 1.3.2 Free-flowing granular matter -- 1.3.3 Density correction -- 1.3.4 Joint limits in inverse kinematics -- 1.3.5 Contact force examples --
2. Numerical methods -- 2.1 Pivoting methods -- 2.1.1 Direct methods for small-sized problems -- 2.1.2 Incremental pivoting "Baraff style" -- 2.2 Projection or sweeping methods -- 2.2.1 Splitting methods -- 2.2.2 Using a quadratic programming problem -- 2.2.3 The blocked Gauss-Seidel method -- 2.2.4 Staggering -- 2.2.5 The projected Gauss-Seidel subspace minimization method -- 2.2.6 The nonsmooth nonlinear conjugate gradient method -- 2.3 The interior point method -- 2.4 Newton methods -- 2.4.1 The minimum map Newton method -- 2.4.2 The Fischer-Newton method -- 2.4.3 Penalized Fischer-Newton method -- 2.4.4 Tips, tricks and implementation hacks --
3. Guide for software and selecting methods -- 3.1 Overview of numerical properties of methods covered -- 3.2 Existing practice on mapping models to methods -- 3.2.1 Existing software solutions -- 3.3 Future of LCPs in computer graphics --
A. Basic calculus -- Order notation -- What is a limit? -- The small-o notation -- The big-o notation -- Lipschitz functions -- Derivatives -- B. First-order optimality conditions -- C. Convergence, performance and robustness experiments -- D. Num4LCP -- Using Num4LCP -- Bibliography -- Authors' biographies