𝔖 Scriptorium
✦   LIBER   ✦

πŸ“

Numerical Methods for Linear Complementarity Problems in Physics-Based Animation (Synthesis Lectures on Computer Graphics and Animation)

✍ Scribed by Sarah Niebe, Kenny Erleben


Publisher
Morgan & Claypool
Tongue
English
Leaves
161
Category
Library

⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis


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].

✦ Table of Contents


Introduction
Understanding The Problem
First-Order Optimality is a Linear Complementarity Problem
Nonsmooth Root Search Reformulations
The Boxed Linear Complementarity Problem
Other Reformulations
The Problem in n-Dimensions
1D BLCP to 4D LCP
The Boxed Linear Complementarity Problem in Higher Dimensions
BLCP and the QP formulation
Converting BLCP to LCP
Nonsmooth reformulations of BLCP
Examples from Physics-Based Animation
Fluid-Solid Wall Boundary Conditions
Free-Flowing Granular Matter
Density Correction
Joint Limits in Inverse Kinematics
Contact Force Examples
Numerical Methods
Pivoting Methods
Direct Methods for Small-Sized Problems
Incremental Pivoting ``Baraff Style''
Projection or Sweeping Methods
Splitting Methods
Using a Quadratic Programming Problem
The Blocked Gauss-Seidel Method
The Projected Gauss-Seidel Subspace Minimization Method
The Nonsmooth Nonlinear Conjugate Gradient Method
The Interior Point Method
Newton Methods
The Minimum Map Newton Method
The Fischer-Newton Method
Penalized Fischer-Newton Method
Tips, Tricks and Implementation Hacks
Guide for Software and Selecting Methods
Overview of Numerical Properties of Methods Covered
Existing Practice on Mapping Models to Methods
Existing Software Solutions
Future of LCPs in Computer Graphics
Basic Calculus
Order Notation
What Is a Limit?
The Small- o Notation
The Big- O notation
Lipschitz Functions
Derivatives
First-Order Optimality Conditions
Convergence, Performance and Robustness Experiments
Num4LCP
Using Num4LCP
Bibliography
Authors' Biographies


πŸ“œ SIMILAR VOLUMES


Introductory Tiling Theory for Computer
✍ Craig Kaplan πŸ“‚ Library πŸ“… 2009 πŸ› Morgan and Claypool Publishers 🌐 English

Tiling theory is an elegant branch of mathematics that has applications in several areas of computer science. The most immediate application area is graphics, where tiling theory has been used in the contexts of texture generation, sampling theory, remeshing, and of course the generation of decorati

Lectures on Numerical Methods for Non-Li
✍ R. Glowinski πŸ“‚ Library πŸ“… 1980 πŸ› Springer / Tata Institute of Foundation Research 🌐 English

Many mechanics and physics problems have variational formulations making them appropriate for numerical treatment by finite element techniques and efficient iterative methods. This book describes the mathematical background and reviews the techniques for solving problems, including those that requir

Practical Global Illumination with Irrad
✍ Jaroslav Krivanek, Pascal Gautron πŸ“‚ Library πŸ“… 2009 πŸ› Morgan & Claypool 🌐 English

Irradiance caching is a ray tracing-based technique for computing global illumination on diffuse surfaces. Specifically, it addresses the computation of indirect illumination bouncing off one diffuse object onto another. The sole purpose of irradiance caching is to make this computation reasonably f

Finite Element Method Simulation of 3D D
✍ Eftychios Sifakis, Jernej Barbič πŸ“‚ Library πŸ› Morgan & Claypool Publishers 🌐 English

<span>This book serves as a practical guide to simulation of 3D deformable solids using the Finite Element Method (FEM). It reviews a number of topics related to the theory and implementation of FEM approaches: measures of deformation, constitutive laws of nonlinear materials, tetrahedral discretiza

Efficient Quadrature Rules for Illuminat
✍ Ricardo Marques, Christian Bouville, LuΓ­s Paulo Santos πŸ“‚ Library πŸ› Morgan & Claypool Publishers 🌐 English

<span>Rendering photorealistic images is a costly process which can take up to several days in the case of high quality images. In most cases, the task of sampling the incident radiance function to evaluate the illumination integral is responsible for an important share of the computation time. Ther