# num3ric/Comp559-Notes

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
628 lines (587 sloc) 27.6 KB
 \documentclass{article} \usepackage{amsmath,amssymb,amsthm, graphicx, float, subfig, hyperref} \begin{document} \renewcommand{\arraystretch}{1.9} \centerline{\sc \large Particle \& Collision Simulation} \centerline{Course Notes from Fundamentals of Computer Animation Comp559 with Paul Kry.} \section{Mathematical background} \subsection{Multivariate/Vector Calculus Basics} First of all, we consider a real-valued multivariate function $f$ defined as follows: $f:\mathbb{R}^n \longrightarrow \mathbb{R}$. This function, which we can call a scalar field, maps $n$ independent variables to one real-valued dependent variable. We say it is real-valued because elements in its range belong to $\mathbb{R}$, and multivariate (or of a vector variable'') because elements in its domain belong to $\mathbb{R}^n$. Here is one example: $f(\mathbf{x}) = f(x_1, x_2, \dots, x_n) = \sum_{i=1}^n x_i$ Now consider the vector-valued multivariate function $\mathbf{f}:\mathbb{R}^n \longrightarrow \mathbb{R}^m$. This function which maps $n$ independent variables to a vector of $m$ dimensions. $\mathbf{f}(\mathbf{x}) = \begin{bmatrix} f_1(\mathbf{x}) \\ f_2(\mathbf{x}) \\ \vdots \\ f_m(\mathbf{x}) \end{bmatrix} = \begin{bmatrix} f_1(x_1, x_2, \dots, x_n) \\ f_2(x_1, x_2, \dots, x_n) \\ \vdots \\ f_m(x_1, x_2, \dots, x_n) \end{bmatrix}$ This type of function is typically called a vector field, most commonly when $n=m=3$. By the end of this section, our hope is that you will understand this statement: \textit{The Hessian of a scalar field is the Jacobian of its gradient while the Laplacian of a scalar field is the divergence of its gradient.''} \subsection{Functions defined over scalar fields} For simplicity, we will assume in the following sections that $m=n$. Furthermore, we will be using the \textit{numerator-layout notation}. \footnote{\url{http://en.wikipedia.org/wiki/Matrix\_calculus\#Layout\_conventions}} \subsubsection{Gradient} What is the gradient of $f$? It is the derivative of a scalar field; essentially a derivative in higher dimensions. We first treat the nabla symbol $\nabla$ as if it was a row-vector differential operator: $\nabla = \begin{bmatrix} \dfrac{\partial }{\partial x_1} & \dfrac{\partial }{\partial x_2} & \hdots & \dfrac{\partial }{\partial x_n} \end{bmatrix}$ Therefore, the gradient of $\nabla f$ is a vector of its partial derivatives: $\nabla f = \begin{bmatrix} \dfrac{\partial f}{\partial x_1} & \dfrac{\partial f}{\partial x_2} & \hdots & \dfrac{\partial f}{\partial x_n} \end{bmatrix}$ Applied over the whole domain of $f$, it yields a vector field where the vectors point in the direction of the greatest rate of increase of the scalar field. As such we can view $\nabla : (\mathbb{R}^n \rightarrow \mathbb{R}) \longrightarrow (\mathbb{R}^n \rightarrow \mathbb{R}^n)$ since it transforms a scalar field into a vector field. %TODO: FIELD NOTATION IS SKETCHY. C^k functions maybe? See wikipedia laplacian %article. \subsubsection{Hessian} The Hessian $\nabla \otimes \nabla f$ or $H(f)$ of a function $f: \mathbb{R}^n \longrightarrow \mathbb{R}$ is the square matrix of its second partial derivatives.\footnote{$\nabla \otimes \nabla$ is a non-standard notation. The Hessian is usually denoted $\nabla^2 f$ but I find this very confusing since it would be indistinguishable from the Laplacian.} $\nabla \otimes \nabla f = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1\,\partial x_n} \\ \frac{\partial^2 f}{\partial x_2\,\partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & & \frac{\partial^2 f}{\partial x_2\,\partial x_n} \\ \vdots & & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n\,\partial x_1} & \frac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}$ While the gradient mapped a scalar field to a vector field, the Hessian maps a scalar field to a a matrix field'': $\nabla \otimes \nabla : (\mathbb{R}^n \rightarrow \mathbb{R}) \longrightarrow (\mathbb{R}^n \rightarrow \mathbb{R}^{n^2})$. Just like a second derivative, the matrix associated to a point in the scalar field describes the local curvature of the field at that point. We can derive the Hessian by taking the outer product of $\nabla$ and the gradient of $f$. Using only two dimensions, we have: $\nabla \otimes \nabla f = (\nabla)^T \nabla{f} = \begin{bmatrix} \dfrac{\partial }{\partial x_1} \\ \dfrac{\partial }{\partial x_2} \end{bmatrix} \cdot \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1} & \dfrac{\partial f_1}{\partial x_2} \end{bmatrix} = \begin{bmatrix} \dfrac{\partial^2 f_1}{\partial^2 x_1} & \dfrac{\partial^2 f_1}{\partial x_1 \partial x_2} \\ \dfrac{\partial^2 f_1}{\partial x_2 \partial x_1} & \dfrac{\partial^2 f_1}{\partial^2 x_2^2} \end{bmatrix}$ \subsubsection{Laplacian} The Laplacian $\nabla \cdot \nabla f$ of a function $f: \mathbb{R}^n \longrightarrow \mathbb{R}$ is the sum of all its unmixed'' second partial derivatives: $\nabla \cdot \nabla f = \sum_{i=1}^n \frac {\partial^2 f}{\partial x^2_i}$ You can also view it as the trace of the Hessian matrix. As opposed to the Hessian, the Laplacian is the inner product/dot product of $\nabla$ and the gradient of $f$. $\nabla \cdot \nabla f = \nabla (\nabla{f})^T = \begin{bmatrix} \dfrac{\partial }{\partial x_1} & \dfrac{\partial }{\partial x_2} \end{bmatrix} \cdot \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1} \\ \dfrac{\partial f_1}{\partial x_2} \end{bmatrix} = \dfrac{\partial }{\partial x_1} \dfrac{\partial f_1}{\partial x_1} + \dfrac{\partial f_1}{\partial x_2} \dfrac{\partial f_1}{\partial x_2} = \dfrac{\partial^2 f_1}{\partial^2 x_1} + \dfrac{\partial^2 f_1}{\partial^2 x_2^2}$ It is a different kind of second derivative of a scalar field. Most noticeably, it maps a scalar field to a scalar field. In general terms, it measures the rate at which the average value of $f$ over spheres centered at a point $p$, deviates from $f(p)$ as the radius of the sphere grows. \subsection{Functions defined over vector fields} \subsubsection{Jacobian} The Jacobian $J(\mathbf{f})$ of a function $\mathbf{f}: \mathbb{R}^n \longrightarrow \mathbb{R}^n$ is a matrix of its partial derivatives. It is the generalization of the gradient for vector-valued function. $J(\mathbf{f})= \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1} & \dfrac{\partial f_1}{\partial x_2} & \cdots & \dfrac{\partial f_1}{\partial x_n} \\ \dfrac{\partial f_2}{\partial x_1} & \dfrac{\partial f_2}{\partial x_2} & & \dfrac{\partial f_2}{\partial x_n} \\ \vdots & & \ddots & \vdots \\ \dfrac{\partial f_n}{\partial x_1} & \dfrac{\partial f_n}{\partial x_2} & \cdots & \dfrac{\partial f_n}{\partial x_n} \end{bmatrix} = \begin{bmatrix} \nabla f_1 \\ \nabla f_2 \\ \hdots \\ \nabla f_n \end{bmatrix}$ Notice that each column of $J$ is the gradient of $\mathbf{f}$: $J_{(i, :)} = \nabla f_i(x)$. It maps a vector field to a matrix field''. \subsubsection{Divergence} The divergence $\nabla \cdot \mathbf{f}$ of a function $\mathbf{f}: \mathbb{R}^n \longrightarrow \mathbb{R}^n$ is the sum of the partial derivatives of the vector. \begin{align*} \nabla \cdot \mathbf{f} &= \begin{bmatrix} \dfrac{\partial }{\partial x_1} & \dfrac{\partial }{\partial x_2} & \hdots \dfrac{\partial }{\partial x_n} \end{bmatrix} \cdot \begin{bmatrix} f_1 \\ f_2 \\ \vdots \\ f_n \end{bmatrix} \\ &= \dfrac{\partial f_1}{\partial x_1} + \dfrac{\partial f_2}{\partial x_2} + \hdots + \dfrac{\partial f_n}{\partial x_n} \end{align*} It maps a vector field to a scalar field. For a given point $p$ in a vector field, it measures the density of the outward flux of the vector field from an infinitesimal region around around $p$. \subsection{Relationships} As you may have guessed, if the Jacobian takes in as a vector field the gradient of a particular scalar field $f$, that Jacobian matrix is identical to the Hessian of $f$. They both reach the same matrix field''. The same principle applies to the divergence: if the divergence is applied to gradient of $f$, it will yield the same scalar field as the Laplacian of $f$. \begin{figure}[H] \centering \includegraphics[width=0.6\textwidth]{img/hessian.png} \caption{Transition from a scalar field, to a vector field, to a matrix field'' using first and second-order derivatives.} \end{figure} \begin{figure}[H] \centering \includegraphics[width=0.6\textwidth]{img/laplacian.png} \caption{Transition from a scalar field, to a vector field, back to a scalar field using first and second-order derivatives.} \end{figure} \subsubsection{Example} `The Jacobian of the force is the Hessian of the energy.'' First, let us define an \underline{energy} function $V : \mathbb{R}^2 \rightarrow \mathbb{R}$ which yields a potential energy value for each point in the space (a scalar field). We also define a \underline{force} function $\mathbf{F} : \mathbb{R}^2 \rightarrow \mathbb{R}^2$ which yields a force vector field. We can obtain the force field by computing the gradient of the energy field. $\mathbf{F} = (\nabla V)^T = \begin{bmatrix} \dfrac{\partial V}{\partial x_1} \\ \dfrac{\partial V}{\partial x_2} \end{bmatrix} = \begin{bmatrix} F_1 \\ F_2 \end{bmatrix}$ Now the Hessian of the energy: $H(V) = \begin{bmatrix} \dfrac{\partial^2 V}{\partial^2 x_1} & \dfrac{\partial^2 V}{\partial x_1 \partial x_2} \\ \dfrac{\partial^2 V}{\partial x_1 \partial x_2} & \dfrac{\partial^2 V}{\partial^2 x_2} \end{bmatrix}$ The Jacobian of the force: $J(\mathbf{F}) = \begin{bmatrix} \dfrac{\partial F_1}{\partial x_1} & \dfrac{\partial F_1}{\partial x_2} \\ \dfrac{\partial F_2}{\partial x_1} & \dfrac{\partial F_2}{\partial x_2} \end{bmatrix} = \begin{bmatrix} \dfrac{\partial}{\partial x_1} \dfrac{\partial V}{\partial x_1} & \dfrac{\partial}{\partial x_2} \dfrac{\partial V}{\partial x_1} \\ \dfrac{\partial}{\partial x_1} \dfrac{\partial V}{\partial x_2} & \dfrac{\partial}{\partial x_2} \dfrac{\partial V}{\partial x_2} \end{bmatrix} = \begin{bmatrix} \dfrac{\partial^2 V}{\partial^2 x_1} & \dfrac{\partial^2 V}{\partial x_1 \partial x_2} \\ \dfrac{\partial^2 V}{\partial x_1 \partial x_2} & \dfrac{\partial^2 V}{\partial^2 x_2} \end{bmatrix} = H(V)$ \subsection{Chain rule} Recall the definition of the chain rule for functions of a single variable. Let $z=f(x)$ and $x=u(t)$ so that $z = (f \circ x)(t)$. $\frac{dz}{dx} = f'(x) \cdot x'(t) = \frac{df}{dx} \cdot \frac{dx}{dt}$ Equivalently using a different notation, we have: $Dz = D(f \circ x)(t) = D(f(x))D(x(t))$ Now we consider the chain rule in the context of multivariate functions. For simplicity, we shall use only two dimensions. \subsubsection{Case 1} Let $z=f(x)$ and $x=u(\mathbf{t})=u(s, t)$ so that $z = (f \circ x)(s,t)$. \begin{align*} \begin{bmatrix} \dfrac{\partial z}{\partial s} & \dfrac{\partial z}{\partial t} \end{bmatrix} &= \begin{bmatrix} \dfrac{df}{dx} \dfrac{\partial x}{\partial s} & \dfrac{df}{dx} \dfrac{\partial x}{\partial t} \end{bmatrix} \\ &= \dfrac{df}{dx} \nabla x \\ \end{align*} So we have, $Dz = D(f \circ x)(\mathbf{t}) = D(f(x)) D(x(\mathbf{t}))$. \subsubsection{Case 2} Let $z= f(\mathbf{x}) =f(x_1, x_2)$ where $x_1=u(t)$ and $x_2=v(t)$. \begin{align*} \dfrac{dz}{dt} &= \dfrac{\partial f}{\partial x_1} \dfrac{ d x_1}{dt} + \dfrac{\partial f}{\partial x_2} \dfrac{ d x_2}{dt} \\ &= \begin{bmatrix} \dfrac{\partial f}{\partial x_1} & \dfrac{\partial f}{\partial x_2} \end{bmatrix} \cdot \begin{bmatrix} \dfrac{d x_1}{dt} \\ \dfrac{d x_2}{dt} \end{bmatrix} \\ &= \nabla f \dfrac{d\mathbf{x}}{dt} \\ \end{align*} So we have, $Dz = D(f \circ \mathbf{x})(t) = D(f(\mathbf{x}))D(\mathbf{x}(t))$. \subsubsection{Case 3} Let $z= f(\mathbf{x}) = f(x_1, x_2)$ where $x_1=u(\mathbf{t})=u(s, t)$ and $x_2= v(\mathbf{t}) = v(s, t)$. \begin{align*} \begin{bmatrix} \dfrac{\partial z}{\partial s} & \dfrac{\partial z}{\partial t} \end{bmatrix} &= \begin{bmatrix} \dfrac{\partial f}{\partial x_1} \dfrac{\partial x_1}{\partial s} + \dfrac{\partial f}{\partial x_2} \dfrac{\partial x_2}{\partial s} & \dfrac{\partial f}{\partial x_1} \dfrac{\partial x_1}{\partial t} + \dfrac{\partial f}{\partial x_2} \dfrac{\partial x_2}{\partial t} \end{bmatrix} \\ &= \begin{bmatrix} \dfrac{\partial f}{\partial x_1} & \dfrac{\partial f}{\partial x_2} \end{bmatrix} \cdot \begin{bmatrix} \dfrac{\partial x_1}{\partial s} & \dfrac{\partial x_1}{\partial t} \\ \dfrac{\partial x_2}{\partial s} & \dfrac{\partial x_2}{\partial t} \\ \end{bmatrix} \\ &= \nabla f \cdot J(\mathbf{x}) \end{align*} So we have, $Dz = D(f \circ \mathbf{x})(\mathbf{t}) = D(f(\mathbf{x}))D(\mathbf{x}(\mathbf{t}))$. \subsubsection{Case 4} At last, let's consider the case of a vector-valued function $\mathbf{z} = \mathbf{f}(\mathbf{x}) = \mathbf{f}(x_1, x_2)$ where $x_1=u(\mathbf{t})=u(s, t)$ and $x_2= v(\mathbf{t}) = v(s, t)$. $\mathbf{z} = \begin{bmatrix} f_1(\mathbf{x}) \\ f_2(\mathbf{x}) \end{bmatrix}$ \begin{align*} \begin{bmatrix} \dfrac{\partial f_1}{\partial s} & \dfrac{\partial f_1}{\partial t} \\ \dfrac{\partial f_2}{\partial s} & \dfrac{\partial f_2}{\partial t} \end{bmatrix} &= \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1} & \dfrac{\partial f_1}{\partial x_2} \\ \dfrac{\partial f_2}{\partial x_1} & \dfrac{\partial f_2}{\partial x_2} \end{bmatrix} \cdot \begin{bmatrix} \dfrac{\partial x_1}{\partial s} & \dfrac{\partial x_1}{\partial t} \\ \dfrac{\partial x_2}{\partial s} & \dfrac{\partial x_2}{\partial t} \\ \end{bmatrix} \\ &= J(\mathbf{f}) \cdot J(\mathbf{x}) \end{align*} So we have, $D\mathbf{z} = D(\mathbf{f} \circ \mathbf{x})(\mathbf{t}) = D(\mathbf{f}(\mathbf{x}))D(\mathbf{x}(\mathbf{t}))$. \subsubsection{Summary} Using the \textit{numerator-layout notation}, we found that the chain rule can be generalized to multivariate functions. The only difference between the cases is how the differential operator is applied. \begin{itemize} \item The derivative of a scalar by a scalar $D(f(x))$ produces a scalar. \item The derivative of a vector by a scalar $D(\mathbf{f}(x))$ produces a column vector. \item The derivative of a scalar by a vector $D(f(\mathbf{x}))$ produces a row vector. \item The derivative of a vector by a vector $D(\mathbf{f}(\mathbf{x}))$ produces a jacobian matrix. \end{itemize} \subsection{Taylor expansion} The taylor serie of an infinitely differentiable function $f$ at $x=a$ is given by: $f(x) = \sum_{k=0}^{+\infty} \frac{f^{(k)}(a)}{k!}(x-a)^k$ A finite number of terms can be used as an approximation function of $f$ around $a$. For a k-differentiable function, Taylor's theorem states that: \begin{align*} f(x) &= f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \cdots \\ &\qquad {} +\frac{f^{(k)}(a)}{k!}(x-a)^k + h_k(x)(x-a)^k \\ f(x) &= P_k(x) + h_k(x)(x-a)^k \\ f(x) &= P_k(x) + R_k(x) \end{align*} where $lim_{x\to a}h_k(x)=0$. \newline The remainder term $R_k(x) = h_k(x)(x-a)^k = o(|x-a|^k), x \longrightarrow a$ represents the approximation error. Thus, say we have a function $x(t+h)$. We then can approximate it around $t$ using its Taylor expansion: \begin{align*} x(t+h) &= x(t) + x'(t)((t+h)-t) + \frac{x''(h)}{2!}((t+h)-t)^2 + \cdots \\ &\qquad {} +\frac{x^{(k)}(h)}{k!}((t+h)-t)^k + h_k(t)((t+h)-t)^k \\ x(t+h) &= x(t) + h x'(t) + \frac{h^2}{2!}x''(h)+ \cdots + \frac{h^k}{k!}x^{(k)}(h) + h^k h_k(t) \end{align*} We will later use this expansion as a position update formula ($x$ will be the position and $h<1$ the timestep). \subsection{Taylor expansion for multivariate or vector functions} Very often in our computations, we will use vector/matrix-form values --- position, velocity and acceleration are all vectors. Hence, we can try to derive an Taylor expansion approximation of second-order for a vector function. \begin{align} y=f(\mathbf{x}+\Delta\mathbf{x})\approx f(\mathbf{x}) + J(\mathbf{x})\Delta \mathbf{x} +\frac{1}{2} \Delta\mathbf{x}^\mathrm{T} H(\mathbf{x}) \Delta\mathbf{x} \end{align} \section{Particle simulation} In physically based animation, particles can be divided into two main groups: \begin{itemize} \item Non-interacting particles such as dust, sparks, snow, rain, \ldots \item Interacting particles such as cloth, cables, elastic solids, dluids, \ldots \end{itemize} \subsection{Introductory example} Say we have snow blown by a simple wind force function $f(x, t)$ which depends on both time and position: $\dot{x} = f(x, t)$ In solving an ODE such as this one, we might have a boundary value problem where knowing the starting point $x_0$ and the ending point $x_n$, we look for $x(t)$. This is usually hard to compute and can have many possible solutions (i.e. cycles). We could also have an initial value problem: we know $x_0$ (and $\dot{x_0}$), and we want to compute $x(t)$. This method is generally faster. \begin{align*} \mathbf{x} = \begin{bmatrix} x \\ y \end{bmatrix}&, \quad \mathbf{\dot{x}} = \begin{bmatrix} \dot{x} \\ \dot{y} \end{bmatrix} = \begin{bmatrix} 1 \\ -3y \end{bmatrix}, \quad \mathbf{x} \in \mathbb{R} \\ \dot{x} = 1,\quad \dot{y} = -3y \quad &\Rightarrow \quad x(t) = c_1+t, \quad y(t) = c_2 e^{-3 x} \\ \mathbf{x_0} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \quad &\Rightarrow \quad x(t) = t, \quad y(t) = e^{-3 x} \end{align*} However, computing the exact formula for a particle path would generally be unrealistic. The only viable approach is to approximate the ODE solution by discretizing time. The particle path $x(t)$ will then describe a discrete sequence of displacements --- hopefully small enough so that they remain unnoticeable. Correct appearance and expected behavior are our primary concerns. \subsection{Forward Euler} Using the forward euler approximation method, we discretize time and find solution at each time steps \$0