# Mathematical Background --- ## Dot Product $ \begin{align*}a\cdot b &= b\cdot a=\Vert a \Vert \Vert b \Vert\cos \phi =a^Tb=b^Ta\\ \phi &= \cos^{-1}(\frac{a\cdot b}{\Vert a \Vert \Vert b \Vert}) \\ a\cdot(b+c) &=a\cdot b+a\cdot c \\ (ka)\cdot b &=a\cdot(kb)=k(a\cdot b) \\ \end{align*}$ **Application**: Projection of $b$ onto $a$ ([tutorial](https://matthew-brett.github.io/teaching/vector_projection.html)) $\begin{align*} \Vert proj_{a}b \Vert &= \Vert b \Vert \cos \phi = \frac{a\cdot b}{\Vert a \Vert} \\ proj_{a}b &= \Vert proj_{a}b \Vert \frac{a}{\Vert a \Vert} = \frac{a\cdot b}{\Vert a \Vert^2} a \end{align*}$ ## Cross Product The magnitude of cross product of two vectors $\mathbf{a\times b}$ corresponds to the area of the parallelogram formed by $\mathbf{a,b}$. $\text{Area} = \Vert\mathbf{a\times b}\Vert$ --- ## Coordinate Frames Any set of 3 vectors $\in \mathbb{R}^3$ (say ${u,v,w}$) such that: $\begin{align*}\Vert u\Vert&=\Vert v\Vert=\Vert w\Vert = 1 \\ u\cdot v &= v\cdot w = u\cdot w = 0 \\ w &= u\times v \\ p &= (p\cdot u)u+(p\cdot v)v + (p\cdot w)w \end{align*}$ Construct a **coordinate frame** (i.e. a basis) **from 1 vector**: 1) normalize $w$, 2) choose any vector $t$ that's not collinear with $w$ to cross-multiply with $w$ to get $u$, 3) Get $v$ as $u\times v$ $\begin{align*} w = \frac{a}{\Vert a \Vert}, \; u=\frac{t\times w}{\Vert t\times w\Vert}, \; v=w\times v \end{align*}$ Construct a **coordinate frame** (i.e. a basis) **from 2 vectors**: - Goal: Given a vector $a$ (e.g. ***viewing direction***), construct an ***orthonormal basis*** - Need a 2nd vector $b$ (e.g. ***camera up direction***). Problem: $a,b$ are neither orthogonal nor unit-norm $\begin{align*} w = \frac{a}{\Vert a \Vert}, \; u=\frac{b\times w}{\Vert b\times w\Vert}, \; v=w\times v \end{align*}$ ## Matrix **Matrix multiplication** ([wiki](https://en.wikipedia.org/wiki/Matrix_multiplication)): Associative, distributive, but **NOT commutative** $\begin{align*}A(B+C)=AB+AC; \;\; (A+B)C=AC+BC\end{align*}$ **Identity** & **Transpose** $\begin{align*}AA^{-1} &=A^{-1}A=I_{n} ;\;\; (AB)^{-1}=B^{-1}A^{-1}\\ I_3 &= \begin{bmatrix}1&0&0\\0&1&0\\1&0&1\end{bmatrix} \end{align*}$ Dot product as matrix multiplication $a\cdot b=a^Tb=(a_1b_1+a_2b_x+a_3b_3)$ Cross product as matrix mult (***skew-symmetric matrix*** (aka dual matrix)): $\begin{align*} a\times b = [a]b= \begin{bmatrix}0&-a_3&a_2\\a_3&0&-a_1\\-a_2&a_1&0\end{bmatrix} \begin{bmatrix}b_1\\b_2\\b_3\end{bmatrix} \end{align*}$ --- ## Line and Plane Checkout this awesome [post on nagwa](https://www.nagwa.com/en/explainers/373101390857/). ![[Pasted image 20221228103323.png]] Lets first review how we define a line: $\begin{align*} \text{General form: } &Ax+By+C=0\\\\ \text{Two-point form: } & A(x-x_0)+B(y-y_0)=0\\ &\text{where } (x_0,y_0), (x,y) \text{ are 2 given points on the line}\\\\ \text{Vector form: } &\mathbf{n}\cdot(\mathbf{r-r_0})=0\;\equiv\; \mathbf{n\cdot r}=\mathbf{n\cdot r_0}\\ &\text{where }\mathbf{n}=\begin{bmatrix}A\\B\end{bmatrix}, \mathbf{r_0}=\begin{bmatrix}x_0\\y_0\end{bmatrix}, \mathbf{r}=\begin{bmatrix}x\\y\end{bmatrix}\\ \end{align*}$ Note that by the property of dot product, the normal vector $\mathbf{n}$ is perpendicular to the line. The geometric intuition of the vector form is that <mark style="background: #FFF3A3A6;">we can define a hyperplane with one point and a normal vector</mark>. When generalizing to a plane in 3D, $\mathbf{n}$ is perpendicular to the plane: $\begin{align*} \text{General form: } &ax+by+cz+d=0\\\\ \text{Two-point form: } & a(x-x_0)+b(y-y_0)+c(z-z_0)=0\\ &\text{where } (x_0,y_0,z_0), (x,y,z) \text{ are 2 given points on the plane}\\\\ \text{Vector form: } &\mathbf{n}\cdot(\mathbf{r-r_0})=0 \;\equiv\; \mathbf{n\cdot r}=\mathbf{n\cdot r_0}\\\ &\text{where }\mathbf{n}=\begin{bmatrix}a\\b\\c\end{bmatrix}, \mathbf{r_0}=\begin{bmatrix}x_0\\y_0\\z_0\end{bmatrix}, \mathbf{r}=\begin{bmatrix}x\\y\\z\end{bmatrix}\\ \end{align*}$ To recap, we've seen 3 ways of describing a line: 1) general form, 2) two-point form, and 3) vector form. Notice that they are all in the form of '$\text{something}=0, which is formally referred to as the root of an **implicit** line function. In the next section we will introduce the concept of ***implicit line/curve equation***. --- ## Implicit Line/Curve Fundamentals of Computer Graphics, Chapter 2.7 ![[Pasted image 20221227134756.png|500]] ***Implicit curves*** are very useful when we later discuss raytracing and [[7_raytracing#Ray-Object Intersection|ray-sphere intersection]]. The following discussion focuses on implicit curves in 2D. The reason why we refer to them as *implicit* is that the function $f:\mathbb{R}^2\rightarrow\mathbb{R}$ itself doesn't explicitly describe a curve. In fact, when plotted in a 3D space, function $f$ refers to a surface. The curve's equation can be reveal only after solving for $f(x,y)=c$. By convention $c=0$. ### Implicit line equation We've established that the general form line equation is $Ax+By+C=0$. In fact, we can rephrase it as the root to the implicit line function $f(x,y)=Ax+By+C$. Such a way of specifying a line comes with lots of benefits which will be made apparent by the following problems. ![[Pasted image 20221228205512.png]] **Problem1**: What is the normal vector $\mathbf{n}$ to the line $f(x,y)=0$? Assume $(x_0,y_0),(x_1,y_1)$ are two known points on the line $f(x,y)=0$, i.e. $\mathbf{a}=\begin{bmatrix}x_1-x_0\\y_1-y_0\end{bmatrix}$ is parallel to the line. $\begin{align*} \text{Claim: } &\mathbf{n}=\nabla f=\begin{bmatrix}\partial f/\partial x\\\partial f/\partial y\end{bmatrix}=\begin{bmatrix}A\\B\end{bmatrix}\\\\ \text{WTS: } & \mathbf{n\cdot a} =0\\ \text{Proof: }& \begin{cases}Ax_0+By_0+C=0\\Ax_1+By_1+C=0\end{cases} \text{ since } \mathbf{a} \text{ is on the line}\\ \therefore\; &A(x_1-x_0)+B(y_1-y_0)=0\\ \equiv & \begin{bmatrix}A\\B\end{bmatrix}\cdot\begin{bmatrix}x_1-x_0\\y_1-y_0\end{bmatrix}=\mathbf{n\cdot a}=0 \;\;\text{Q.E.D} \end{align*}$ A corollary of this problem is that given two points $(x_0,y_0), (x_1,y_1)$, we can express $A,B,C$: $A=y_0-y_1,\;B=x_1-x_0,\; C= x_0y_1-x_1y_0$ It's easy to verify that the following still hold: - $\begin{bmatrix}A\\B\end{bmatrix}\cdot\begin{bmatrix}x_1-x_0\\y_1-y_0\end{bmatrix}=0$ - $Ax+By+C=0$ **Problem2**: Given arbitrary point $\mathbf{p}$, what's its distance $d$ from the line? We can use a trick for defining $\mathbf{p}$ to make our lives easier (instead of specifying its x,y coordinates explicitly), that is, $\mathbf{p}=\begin{bmatrix}a\\b\end{bmatrix}=\begin{bmatrix}x_0\\y_0\end{bmatrix}+k\begin{bmatrix}A\\B\end{bmatrix}$ where $[x_0\;y_0]^T$ is on the line $f(x,y)=0$. The distance from $\mathbf{p}$ to the line $f(x,y)=0$ is $d=k\Vert\mathbf{n}\Vert=k\sqrt{A^2+B^2}$ by definition. $\begin{align*} \text{Claim: } &d=\frac{f(\mathbf{p})}{\Vert\mathbf{n}\Vert}=\frac{f(a,b)}{\sqrt{A^2+B^2}}\\\\ \text{Proof: } & f(\mathbf{p})=A(x_0+Ak)+B(y_0+Bk)+C\\ &=k(A^2+B^2) + \underset{=0}{\underbrace{Ax_0+By_0+C}}\\ &=d\sqrt{A^2+B^2}\\ \underset{\text{Rearrange}}{\rightarrow} &d=\frac{f(\mathbf{p})}{\sqrt{A^2+B^2}}=\frac{f(a,b)}{\sqrt{A^2+B^2}}\; \text{Q.E.Q} \end{align*}$ A corollary of this problem is that the distance between line $f(\mathbf{p})=D$ and line $f(\mathbf{p})=0$ is proportional to $D$. ### Implicit circle equation Equation of 2D circle, centered at $\mathbf{c}=(c_x,c_y)\in\mathbb{R}^2$ with radius $r\in\mathbb{R}$. - First we express the circle's implicit equation as a function of $\mathbf{p}=(p_x,p_y)\in\mathbb{R}^2$ $f(\mathbf{p})=(\mathbf{p}-\mathbf{c})\cdot(\mathbf{p}-\mathbf{c})-r^2\equiv\|\mathbf{p}-\mathbf{c}\|^2-r^2\equiv\|\mathbf{p}-\mathbf{c}\|-r $ - Then we solve for the root, i.e. $f(\mathbf{p})=0$ to reveal the curve/circle's equation $\|\mathbf{p}-\mathbf{c}\|-r=0$ --- ## Barycentric Coordinates Fundamentals of Computer Graphics, Chapter 2.9.1 ![[Pasted image 20221228210843.png]] Triangle is a fundamental geometric primitive. The ***barycentric coordinates*** provide a convenient way to specify a point $\mathbf{p}$ w.r.t. a triangle $\triangle abc$. Later down the line, this will come in handy for [[7_raytracing#Ray-triangle intersection|ray-triangle intersection]]. Given an 2D triangle with vertices $\mathbf{a,b,c}$, we can set up a coordinate system using two of its edges, i.e. $\{(\textbf{b-a}),(\textbf{c-a})\}$. The point $\textbf{p}$ in said coordinate system can be specified by the coordinate $(\beta,\gamma)$, i.e. $\mathbf{p}=\mathbf{a}+\beta(\mathbf{b-a})+\gamma(\mathbf{c-a})\;\equiv\;\underset{\coloneqq\alpha}{\underbrace{(1-\beta-\gamma)}}\mathbf{a}+\beta\mathbf{b}+\gamma\mathbf{c}$ For better symmetry, we can alternatively define $\mathbf{p}$ as: $\begin{align*} &\mathbf{p}(\alpha,\beta,\gamma)=\alpha\mathbf{a}+\beta\mathbf{b}+\gamma\mathbf{c}\\ &\text{Subject to the constraint: } \alpha+\beta+\gamma=1 \end{align*}$ Such a way of expressing $\mathbf{p}$ has a particularly nice property. That is, point $\mathbf{p}$ is inside $\triangle\mathbf{abc}$ iff $\alpha\in(0,1) \text{ and } \beta\in(0,1) \text{ and } \gamma\in(0,1)$ Note that the above definitions and properties holds for both $\mathbf{p}\in\mathbb{R}^2$ and $\mathbf{p}\in\mathbb{R}^3$. ### Compute barycentric coordinates Given a point $\mathbf{p}\in\mathbb{R}^3=[x_p\;y_p\;z_p]^T$, we need to find its barycentric coordinates $(\beta,\gamma)$ to determine whether it's inside $\triangle\mathbf{abc}$. There are in general 3 ways to accomplish this task. **Method1**: Solve for $\beta,\gamma$ by solving a linear system of equations. We start with the definition of $\mathbf{p}s barycentric coordinates: $\begin{align*} &\mathbf{p-a}=\beta(\mathbf{b-a})+\gamma(\mathbf{c-a})\\ \text{In matrix form: }&\begin{bmatrix} x_b-x_a&x_c-x_a\\y_b-y_a&y_c-y_a \end{bmatrix}\begin{bmatrix}\beta\\\gamma\end{bmatrix}=\begin{bmatrix}x_p-x_a\\y_p-y_a\end{bmatrix} \end{align*}$ **Method2**: Solve for $\beta, \gamma$ geometrically using properties of [[#Implicit line equation]]. $\beta=\frac{f_{a c}(x, y)}{f_{a c}\left(x_b, y_b\right)}=\frac{\left(y_a-y_c\right) x+\left(x_c-x_a\right) y+x_a y_c-x_c y_a}{\left(y_a-y_c\right) x_b+\left(x_c-x_a\right) y_b+x_a y_c-x_c y_a}$ $\gamma$ can be solved for similarly. **Method3**: Use areas of sub-triangles, i.e. $A_a,A_b,A_c$. $\triangle\mathbf{abc}$ has area $A$. $\alpha=A_a/A,\; \beta=A_b/A,\;\gamma=A_c/A$ Recall that cross product has the geometric meaning a area. So in 3D, we have the following formula: $\begin{align*} &\alpha=\frac{\Vert\mathbf{n_a}\Vert}{\Vert\mathbf{n}\Vert},\;\beta=\frac{\Vert\mathbf{n_b}\Vert}{\Vert\mathbf{n}\Vert},\;\gamma=\frac{\Vert\mathbf{n_c}\Vert}{\Vert\mathbf{n}\Vert}\\ \text{Where } &\begin{cases} \mathbf{n}=(\mathbf{b-a})\times(\mathbf{c-a})\sim A\\ \mathbf{n_a}=(\mathbf{c-b})\times(\mathbf{p-b})\sim A_a\\ \mathbf{n_b}=(\mathbf{a-c})\times(\mathbf{p-c})\sim A_b\\ \mathbf{n_c}=(\mathbf{b-a})\times(\mathbf{p-a})\sim A_c\\ \end{cases} \end{align*}$ Note that the above formulation is only valid for $\mathbf{p}\in\triangle\mathbf{abc}$, that is, when $\alpha,\beta,\gamma\in(0,1)$. The reason is that $\Vert\bullet\Vert$ renders areas $A_a,A_b,A_c$ unsigned, when in fact they should be signed (since the result from vector cross product). To solve this problem, we can utilize the property of vector dot product, i.e. $\mathbf{a\cdot b}=\Vert\mathbf{a}\Vert\cdot\Vert\mathbf{b}\Vert\cos\theta$. $\begin{align*} \text{Originally: }&\alpha=\frac{\Vert\mathbf{n_a}\Vert}{\Vert\mathbf{n}\Vert}=\frac{\Vert\mathbf{n}\Vert\Vert\mathbf{n_a}\Vert}{\Vert\mathbf{n}\Vert\Vert\mathbf{n}\Vert}\\ \text{To make } \alpha \text{ signed: }&\alpha=\frac{\Vert\mathbf{n}\Vert\Vert\mathbf{n_a}\Vert}{\Vert\mathbf{n}\Vert\Vert\mathbf{n}\Vert}\cos\theta=\frac{\mathbf{n\cdot n_a}}{\Vert\mathbf{n}\Vert^2}\\ &\text{where }\cos\theta=\begin{cases} 1, &\mathbf{n,n_a} \text{ same direction}\\ -1, &\mathbf{n,n_a} \text{ opposite direction}\end{cases}\\\\ \text{Finally: }& \alpha=\frac{\mathbf{n\cdot n_a}}{\Vert\mathbf{n}\Vert^2},\;\beta=\frac{\mathbf{n\cdot n_b}}{\Vert\mathbf{n}\Vert^2},\gamma=\frac{\mathbf{n\cdot n_c}}{\Vert\mathbf{n}\Vert^2} \end{align*}$ Now we can see $\alpha, \beta, \gamma$ can correctly represent any point $\mathbf{p}$ in the plane spanned by $\triangle\mathbf{abc}$.