Lecture07-Introduction to Geometry几何

Lecture07-Introduction to Geometry几何

显式的（explicit）几何表示方法：点云（point cloud）、多边形网格（polygon mesh）、细分（subdivision）…

隐式的（implicit）表示方法：等值面（level set）、代数曲面（algebraic surface）…

Implicit Surface 隐式的曲面

形如 $f(x,y,z)=0$ 的形式给出。

找到哪些点在面上通常是困难的，但是判断一个点在哪里是比较简单的！

CSG-Constructive Solid Geometry（Implicit）构造刚体几何图形

集合运算跟逻辑运算是对应的，所以就可以用集合的交并补差这些运算，来处理图形。

Blending Distance Functions 融合距离函数

对于几何，不去描述表面，而是描述点到表面的最近距离。

假设想要求出上图中，$A\to B$ 的中间的运动状态，如果直接混合（blend），会得到（黑-灰-白）的三块，并不具有运动的信息。如果反过来，对横轴上每个点求SDF（Signed Distance Function），然后混合两个SDF，得到$blend(SDF(A),SDF(B))$。

Level Set Method 水平集方法

有了混合的距离函数，如何再恢复表面呢？把SDF=0的地方找出来，如果函数是隐式的，那就类似光栅化那样采样，然后用插值的方法求出等值面。

Fractal 分形

复杂的情况~在渲染的时候可能会引起强烈的走样。

Explicit Representation 显式的表示

找到哪些点在面上会变简单（比如参数方程的表示，只要跑遍所有参数的取值，也必须跑遍），但是判断一个点在哪里变难了！

所有点直接给出/通过参数坐标给出，比如课件上给了个 $\mathbb{R}^2\to \mathbb {R^3}$ 的映射，把平面上的图形映射成马鞍面，又比如前面的轮胎面$(2-\sqrt{x^2+y^2})^2+z^2-1=0$，也可以改写成显示的 $z=\pm \sqrt{1-(2-\sqrt{x^2+y^2})^2}$。

接着就开始说极坐标表示点，上面提到的轮胎面还可以表示成 $f(u,v)=((2+\cos u)\cos v,(2+\cos u)\sin v,\sin u)$，但是我们会发现，这样子的表示，就不太好判断一个点在内部还是外部了。

（补充）

Point Cloud 点云

用一系列的点 $(x,y,z)$ 表示，可以很容易表示各种几何图形，对于数据集比较大（比如一个3D空间的扫描）的情况非常有用，并且经常可以转化成多边形网格的表示。

Polygon Mesh 多边形网格

存储点和多边形
很容易做处理、模拟、自适应采样
更加复杂的数据结构
在图形学里更经常用的表示方法

Splines 样条曲线

样条（spline）：一条连续的曲线，经过一系列给定的控制点，并且满足一定的连续性。

Cubic Hermite Interpolation 三次Hermite插值

Nearest Neighbor Interpolation：$x$ 处选取最近的 $x_i$ 的函数值，函数不连续。
Linear Interpolation：线性插值，函数连续，导数不连续。
Cubic Hermite Interpolation（三次厄尔米特插值）：可以让导数连续！

Power Basis 幂基

幂基（power basis）：$\mathcal {P}^d=[1,u,u^2,\dots,u^d]$，（注：这里幂基应当是一个行向量）很明显幂基在 $\R $ 上是线性无关的。

然后对于一个 $\R [u]$ 中的元素，可以写成幂基的形式： $x(u)=\sum_{i=0}^ d c_i u^i=\mathcal {C\cdot P}^d$。

Useful Properties of a Basis 基的一些有用性质

这部分在课件里放在贝塞尔曲线，但我感觉提上来比较好。

Convex Hull property 凸包性质

凸包性质指的是：所有曲线上的点都落在控制点的凸包内。
贝塞尔曲线具有这种性质。
基满足凸包性质，若：
- 基函数的和为1，即： $\sum b_i (u)=1(\forall u\in \Omega)$
- 基函数非负：$b_i (u)\geq 0 (\forall u\in \Omega,i=0,\dots,n)$

Invariance 不变性

这里特指：对曲线做某个变换=对控制点做变换，再绘制曲线

即：

贝塞尔曲线对仿射变换具有不变性，但对透视变换不具有不变性，即：

\[x(u)=\mathcal{P}^3 \beta_{Z} \cdot p \\ \Leftrightarrow \\ T\cdot x(u)=\mathcal{P}^3 \beta_{Z} \cdot (T\cdot p) \]

这条性质感觉得通过Bernstein多项式来写？（不知道有没有更直接的方法，直接乘矩阵肯定是不能交换的）

Local Support 局部支撑

改变一个控制点，不会改变整个曲线。

Some Differential Geometry 一些微分几何

一条曲线在某方向的切线可以写成 $t(u)=\frac{\partial x}{\partial u}|_u$，对于一个曲面则可以写$t_u(u,v)=\frac{\partial x}{\partial u}|_{u,v}$ 和 $t_v(u,v)=\frac{\partial x}{\partial v}|_{u,v}$，综合起来，可以写出曲面的单位法向量：

\[\vec n =\frac{\vec t_u\times \vec t_v}{||\vec t_u\times \vec t_v||} \]

当然也有一些退化情况（比如 $||t_u \times t_v||=0$ 或者 $\partial x/\partial u=0$ 的情况。

好了说了这么多，其实不知道他这页PPT放了有什么意义…

Specifying a Curve 特定曲线

给了一些希望有的限制，如何确定三次幂基的系数（这句话有点绕，其实就是确定一个三次曲线的系数）？

即：已知 $x(u_0)=x_0,x(u_1)=x_1, x'(u_0)=d_0,x'(u_1)=d_1$，如何确定三次函数 $x(u)=c_0+c_1u+c_2 u^2 +c_3 u^3$？

好，首先：

\[x(u)=c_0+c_1u+c_2 u^2 +c_3 u^3\\ x'(u)=c_1+2 c_2u +3c_3u^2 \]

不妨假设 $u_0=0,u_1=1$，那么有：

\[\left\{ \begin{aligned} x(0)=c_0&=x_0\\ x(1)=c_0+c_1+c_2+c_3&=x_1\\ x'(0)=c_1&=d_0\\ x'(1)=c_1+2c_2+3c_3&=d_1 \end{aligned} \right. \]

写成矩阵，即：

\[\begin{bmatrix} 1&0&0&0\\ 1&1&1&1\\ 0&1&0&0\\ 0&1&2&3 \end{bmatrix} \cdot \begin{bmatrix} c_0\\c_1\\c_2\\c_3 \end{bmatrix} = \begin{bmatrix} x_0\\x_1\\d_0\\d_1 \end{bmatrix} \]

我们把左边的列向量 $c=(c_0,c_1,c_2,c_3)^T$ 叫做系数（coefficient）向量，右边 $h=(x_0,x_1,d_0,d_1)^T$ 一般叫做控制点，以及矩阵记为 $B$ ，那么就是 $B\cdot c=h$，即我们想要的系数 $c=B^{-1}h$，因为逆矩阵更常用，所以不如起个名字叫 $\beta_H=B^{-1}$。（H就是Hermite的首字母， $\beta _H$ 则叫做Hermite基矩阵）

注：Hermite基矩阵：

\[\beta_H=\begin{bmatrix} 1&0&0&0\\ 0&0&1&0\\ -3&3&-2&-1\\ 2&-2&1&1 \end{bmatrix} \]

此时任意一点

\[x(u)=\mathcal{P}^3(u) c=\mathcal{P}^3(u) \cdot \beta_H \cdot h \]

如果控制点发生变化，其实幂基、Hermite基矩阵都不会改变，所以 $\mathcal{P}^3 (u)\cdot \beta_H$ 的结果是固定的！这一部分（最终其实是一个行向量）就叫 Hermite 基函数（因为是关于自变量 $u$ 的函数）

综上所述，三次Hermite插值是这样一个过程：输入端点函数值、导数值，输出一个三次多项式，最终的结果就是Hermite基的带权和（其实就是矩阵乘完的结果啦）！

得到的Hermite基函数（的各个分量）：

Q：为什么不用更高阶的多项式？

A：1、高阶多项式更不稳定，容易摆动。2、希望编辑后，能保持一些局部的性质（局部不要变化太大）3、开销大。

Catmull-Rom 插值

输入一些点，输出C1连续的经过所有插值点的样条。

导数的确定方式： $i$ 处的导数值 $f'(x_i)=\frac{f(x_{i+1})-f(x_{i-1})}{x_{i+1}-x_{i-1}}$，（注：这里的上一个和下一个应该是循环的）

是一种逐段的（piecewise）三次曲线，并且非常容易推广到对 $n$ 维空间的几个点进行插值。

确定了导数之后，剩下的内容其实和三次Hermite插值一样，上面的 $\vec h=[p_1,p_2,\frac{1}{2}(p_2-p_0),\frac{1}{2}(p_3-p_1)]$，那么

\[\begin{aligned} p(u)&=\mathcal{P}^3 (u)\cdot \beta_H \cdot h=\mathcal{P}^3 (u)\cdot \beta_H\cdot M_{CR\to H}\cdot [p_0,p_1,p_2,p_3]^T\\ &=\begin{bmatrix} 1&u&u^2&u^3 \end{bmatrix} \cdot \begin{bmatrix} 1&0&0&0\\ 0&0&1&0\\ -3&3&-2&-1\\ 2&-2&1&1 \end{bmatrix} \cdot \begin{bmatrix} 0&1&0&0\\ 0&0&1&0\\ -\frac{1}{2}&0&\frac{1}{2}&0\\ 0&-\frac{1}{2}&0&\frac{1}{2} \end{bmatrix} \cdot \begin{bmatrix} p_0\\p_1\\p_2\\p_3 \end{bmatrix} \end{aligned} \]

中间两个矩阵的结果就叫 $\beta_{CR}=\beta_H\cdot \beta_{CR\to H}$。

Bézier Curve 贝塞尔曲线

Evaluating Bézier Curves——Matrix Formula 矩阵表示

和之前的Hermite、Catmull-Rom相比，还是改了个切线的定义方式——所有的控制点都是空间中的点，没有切线，而是让左右两个端点处的切线，恰好是连线（虽然这里有个系数 $3$ ，对应着后面的Bernstein多项式的系数）

然后也类似有一个矩阵 $\beta_Z=\beta_H\cdot M_{Z\to H}$，

\[\beta_Z=\begin{bmatrix} 1&0&0&0\\ -3&3&0&0\\ 3&-6&3&0\\ -1&3&-3&1 \end{bmatrix} \]

可以得到一个基函数的图像：

Evaluating Bézier Curves——De Casteljau Algorithm

对于 $n$ 个控制点，和某个时间 $t\in[0,1]$ ，跑 $n-1$ 次循环。假设当前的控制点是 $b_0,\dots,b_k$ ，则取 $b_i'=(1-t)\cdot b_i+t\cdot b_{i+1}$——这一步就是所谓的线性插值（lerp），直到最后只剩下一个点。

Evaluating Bézier Curves——Bernstein Polynomial

贝塞尔曲线迭代 $n$ 次的结果（一个点）为：

\[\vec{b}^n (t)=\sum_{j=0}^n b_j B_j^n(t)=\sum_{j=0}^n \vec{b_j} \binom{n}{j}t^j (1-t)^{n-j} \]

注意， $\vec b,\vec b_j$ 都是某维空间的向量， $B_j^n (t)=\binom{n}{j} t^j (1-t)^{n-j}$ 叫做伯恩斯坦多项式，是标量。

$b_0,\dots b_n$ 是贝塞尔曲线控制点。

那么特别地，对于一个三次贝塞尔曲线，有：

\[b(t)=b_0(1-t)^3 +3b_1 t(1-t)^2+3 b_2 t^2 (1-t)+b_3 t^3 \]

系数 3 就在这里。

Properties of Bézier Curve 贝塞尔曲线的性质

插值端点：$b(0)=b_0,b(1)=b_n$
切线端点：对于3次贝塞尔曲线（4个控制点），$b'(0),b'(1)$恰是切线。
仿射变换不变性：贝塞尔曲线做仿射变换=控制点做仿射变换，再绘制贝塞尔曲线。
凸包性质：绘制的图形一定在控制点构成的凸包内部。
良好的表现：局部控制（加入点时？）

Piecewise Bézier Curves 逐段贝塞尔曲线

普通的贝塞尔曲线有个不好的地方，次数一旦高了，就不好通过控制点控制！

所以就有了逐段贝塞尔曲线——把很多段低阶的贝塞尔曲线，按顺序拼接起来，应用非常广泛（比如Photoshop的钢笔工具，绘制路径，很多矢量图的存储方式也是用这种曲线）

然后就是注意一点差异，我们平常在Photoshop里的钢笔工具是比较规范的，实际上的逐段贝塞尔曲线，可能不是C1连续的：

想象下面两段3阶贝塞尔曲线拼接起来，$C^0$ 连续当且仅当 $a_n =b_0$， $C^1 $连续还需切线连续，这里通常还会要求相等，即 $a_n-a_{n-1}=b_1-b_0$，又因为 $C^0$ 连续有 $a_n=b_0$，所以即 $a_n=b_0=\frac{1}{2}(a_{n-1}+b_1)$。

Bézier Surfaces 贝塞尔曲面

通常是用 $[0,1]^2$ 的参数来刻画曲面的。

Method 1: Separable 1D de Casteljau Algorithm

方法1就是说，对于 $(u,v)$ 分开地用Casteljau算法，可见复杂度之高x

Method 2: Algebraic Evaluation

方法2是代数方法，推广一下上面的Bernstein多项式的写法：

\[b^{n,m}(u,v)=\sum_{i=0}^n \sum_{j=0}^m b_{i,j} B_i^n (u)B_j^m(v) \]

课件上管这玩意叫张量积（Tensor product），给我吓得不轻。

Method 3: Linear Algebra

其实三个方法思路都一样，都是对两个方向进行线性插值。

方法3还是考虑前的形式，$x(u,v)=\mathcal{P}^3(u) \cdot \beta_Z\cdot [p_0,p_1,p_2,p_3]^T$，只不过这里

\[p_i=\mathcal{P}^3 (v)\cdot \beta_Z\cdot [p_{i,0},p_{i,1},p_{i,2},p_{i,3}]^T \]

最后写出来：

\[x(u,v)=\mathcal{P}^3(u)\cdot \beta_Z \cdot \begin{bmatrix} p_{0,0}&p_{0,1}&p_{0,2}&p_{0,3}\\ p_{1,0}&p_{1,1}&p_{1,2}&p_{1,3}\\ p_{2,0}&p_{2,1}&p_{2,2}&p_{2,3}\\ p_{3,0}&p_{3,1}&p_{3,2}&p_{3,3}\\ \end{bmatrix} \cdot \beta_Z^T\cdot \mathcal{P}^3(v)^T \]

Method 4: Bézier Subdivision

方法4和之前的都不太一样！切入点应该是考虑贝塞尔曲线的凸包性质，进一步考虑找到一个合适的中点——即参数 $t=1/2$ 对应的点，把控制点一分为二，连同中间过程的控制点，一起递归地处理，每次范围缩小一半，最后对于很小的地方直接用凸包替代曲线（？）：

\[\begin{aligned} x(u)&=[1,u,u^2,u^3]\beta_z\cdot P,(0\leq u\leq \frac{1}{2})\\ &=[1,\frac{u}{2},\frac{u^2}{4},\frac{u^3}{8}]\cdot \beta_Z\cdot P,(0\leq u\leq 1)\\ &=[1,u,u^2,u^3]\cdot \underbrace{\begin{bmatrix} 1&&&\\ &1/2&&\\ &&1/4&\\ &&&1/8 \end{bmatrix}}_{\color{red}S_1} \cdot \beta_Z\cdot P \\ &=[1,u,u^2,u^3]\cdot (\beta_Z \beta_Z^{-1})S_1\beta_Z P\\ &=[1,u,u^2,u^3]\cdot \beta_Z \underbrace{{\color{red}\cdot(\beta_Z^{-1}S_1\beta_Z)}}_{H_{Z1}}\cdot P\\ &=[1,u,u^2,u^3]\cdot \beta_Z {\color{red} P_1} \end{aligned} \]

这里 $H_{Z1}=\beta_Z^{-1}S_1\beta_Z$ 是一个下三角矩阵。

类似地，另一半也可以写成 $x(u)=[1,u,u^2,u^3]\cdot \beta_Z \cdot P_2$ 的形式，$P_2=H_{Z2}P$。