Bezier曲线和曲面
基本知识
- 图形学中产生真实感的图像的步骤：设定场景，通过渲染方程产生具有真实感的图像。因此引入几何造型设计场景；
- 物体的表示方式：显式，隐式，参数（我们应该找到以t的多项式表达的参数形式）。
Bézier曲线
Bernstein多项式：伯恩斯坦多项式(Bernstein polynomial)是逼近连续函数的一系列多项式：记其中$B_{(i,n)} (t)$是第$i$个$n$阶Bernstein多项式：
$$
B_{(i,n)} (t)=C_n^i t^i (1-t)(n-i)=\frac {n!}{i!(n-i)!}t^i(1-t)^{n-i}(i=0,1,…,n)
$$Bernstein多项式的性质：
- 若$t\in(0,1)且i=1,2,…,n-1$时，$B_{i,n} (t)>0$，若$t=0或1$，则$B_{i,n} (t)=0$；
- 若$i=0$，则$B_{(i,n)} (0)=1$，若$i\ne0$，则$B_{(i,n)} (0)=1$；
- 若$i\ne n$，则$B_{(i,n)} (1)=$0，若$i=n$，则$B_{(i,n)}=1$；
- Unity: $\displaystyle\sum_{i=0}^nB_{i,n}(t)\equiv1,t\in(0,1)$ ；
- Symmetry: $B_{i,n} (1-t)=B_{n-i,n} (t)$；
- Recursion: $B_{i,n} (t)=(1-t) B_{i,n-1}(t)+tB_{i-1,n-1} (t)$，即$n$阶Bernsten多项式是$n-1$阶Bernsten多项式的线性组合；
- Derivation：$B_{i,n}’(t) =n[B_{i-1,n-1)} (t)-B_{i,n-1}(t)]$；
- Maximum: $\frac in$；
- Integral: $\int_0^1B_{i,n} (t)dt=\frac 1{n+1}$
- Degree raising formula:
- $(1-t)B_{i,n}(t)=(1-\frac i{n+1})B_{i,n+}$；
- $tB_{i,n}(t)=\frac {i+1}{n+1}B_{i+1,n+1}(t)$；
- $B_{i,n}(t)=(1-\frac i{n+1})B_{i,n+1}(t)+\frac {i+1}{n+1}B_{i+1,n+1}(t)$。
连接向量表达曲线的方法。定义，给定控制顶点${P_i}$，曲线可以被定义为
$$
P(t)=\sum_{t=0}^nP_iB_{i,n}(t),t\in[0,1]
$$
且一条Bézier曲线一定是第一次Bézier曲线的包络（或者说具备闭包性质）。Bézier曲线的性质：
- 端点：$P(0)=P_0，P(1)=P_n$；
- 切向量$P’ (0)=n(P_1-P_0 )，P’ (1)=n(P_n-P_{n-1})$，即起点和终点处的切向量方向与控制多边形第一个和最后一个边的方向一致
- 二阶导数公式：$P’’(t)=n(n-1)\displaystyle\sum_{i=0}^{n-2}(P_{i+2}-2P_{i+1}+P_i)B_{i,n-2}(t)$；
- k阶差分形式：$P^k(t)=\frac {n!}{(n-k)!}\displaystyle\sum_{i=0}^{n-k}\triangle^kP_iB_{i,n-k}(t), t\in[0,1]$；
- 对称性：存在一点使得曲线保留曲线的形状，但方向相反；
- 凸包性，曲线在控制曲线的凸包内；
- 几何不变性：不随坐标系变化。
De Casteljau算法：由于
$$
P(t)=\displaystyle\sum_{t=0}^nP_i B_{i,n} (t)\
=\displaystyle\sum_{t=0}^nP_i[(1-t)B_{i,n-1}(t)+tB_{i-1,n-1} (t)]\
=\displaystyle\sum_{t=0}^n[(1-t) P_i+tP_{i+1}]B_{i,n-1} (t)
$$
故可以得到其递推公式
$$
P^k=\begin{cases} P_i, k=0\
(1-t)P_i^{k-1}+tP_{i+1}^{k-z} , k=1,2,…,n;i=0,1,…,n-k
\end{cases}
$$
即可得到所求点。几何连续性：算术连续性在实际运用中存在一些困难和与常识的错误，故引入几何连续性：两个分别由控制点$P_i(i=0,1,…,n)，Q_j(j=0,1,…,n)$定义的两个Bézier曲线，两条曲线共享端点，且$a_i=P_i-P_(i-1),b_j=Q_j-Q_(j-1)$，则称之为一阶几何连续（共线）（二阶要求曲率一样）；
升阶公式；
$$
P_i^*=\frac i{n+1}P_{i-1}+(1-\frac i {n+1})P_i,(i=0,1,…,n+1)
$$Bezier曲面：矩形域Bézier曲面（定义暂略）与三角域的转换（数学推导暂略）
B样条曲线曲面（B-spline）
动机源于Runge-Kutta现象：高阶多项式很容易产生不稳定抖动。故以分段低阶连续连接，这就是样条——分段低阶多项式。
B样条内容：样条函数插值（解三对角方程），给定区间划分（与插值计算类似）和割点去搭建的所有样条函数组成了一个线性空间，线性空间基函数叫做B样条基函数；可以像Bezier曲线使用Bernsterin基函数一样，B样条曲线使用B样条基函数。
B样条曲线及其性质：
- 公式：$P(t)=\sum {i=0}^nP_iN{i,k}(t),t\in[0,1]$
- $P_i(i=0,1,…,n)$是控制点；
- $N_{i,k}(t)(i=0,1,…n)$是第$i$个$k$阶B样条基函数；
- 注意的是，B样条基函数是由节点向量唯一决定的分段$k$阶多项式，节点向量是由一组非递减的实数序列：$t_0,t_1,…,t_{k-1},t_k,…,t_n,t_n,t_{n+1},…,t_{n+k-1},t{n+k}$;
- 和Bézier曲线相比，B样条动一点曲线只改变部分，而Bézier一变全变。
B样条基函数定义
- de boor-cox递归函数：
$$
N_{i,1}(t)=\begin{cases}
1,t_i<x<t_{i+1}\\
0,Otherwise
\end{cases}
$$
- de boor-cox递归函数：
$$
N_{i,k}(t)=\frac {t-t_i}{t_{i+k}-t_i}N_{i,k-1}(t)+\frac{t_{i+k}-t}{t_{i+k}-t_i+1}N_{i+1,k-1}(t)
$$
其性质为:
非负性：$N_{i,k}(t)=\begin{cases}\ge0,t\in[t_i,t_{i+k}]\\=0,otherwise\end{cases}$;
归一性：$\displaystyle\sum_{i=0}^nN_{i,k}(t)=1,t\in(t_{k-1},t_{n+1})$;
求导公式：
$$
N_{i,k}’(t)=\frac {k-1}{t_{i+k-1}-t_i}N_{i,k-1}(t)+\frac {k-1}{t_{i+k}-t_{i+1}.}N_{i+1,k-1}(t)
$$
这里有个点是为了防止公式渲染失败局部支撑性：$N_{i,k} (t)$是$[t_i,t_{i+k} ]$上的分段非零多项式。
均匀B样条：节点为等差数列均匀排布节点分布对应的是均匀B样条基函数。
准均匀B样条：均匀B样条不同，准均匀B样条的起始节点和终止节点都具有k的重复度，其并不具有Bézier曲线的端点性质，即均匀B样条起点和重点并不等于第一个和最后一个控制点，但是准均匀B样条具备端点性质。
分段Bézier曲线，起始和终止节点都具有k的重复度，其他节点都具有$k-1$的重复度，这样的所有曲线都是Bézier曲线，其不同曲线段相对独立，移动控制点只会影响所在的Bézier曲线段，其关于Bézier曲线的算法都可以同样地适用于分段Bézier曲线。但是其需要更多的参数和变量来控制——即更多的控制点和更多的节点。
非均匀B样条（重点讨论）：
定义：在满足一般B样条的条件下，起始节点和终止节点的重复度均小于$k$，且其他节点的重复度均小于$k-1$；
性质：
局部性：区间上的曲线仅有至多$k$个控制点决定，而修改控制点$P_i$仅改变对应区间$(t_i,t_{i+k})$的曲线；
连续性：$P(t)$在重复的结点$r$有$C^{k-1-r}$连续；
凸包性：非均匀B样条被包含在控制多边形的凸包内。特别的，若$t$是不同节点段$(t_i,t_{i+1}),k-1\le i \le n$，那么$P(t)$在控制点$P_{i-k+1},…,P_i$所围成的闭包内；
分段多项式性质：任何一个相邻节点确定的区间上，$P(t)$为一个关于$t$的次数不超过$k$的多项式；
导数公式:$P’(t)=\sum_{i=0}^n P_i N’{i,k}(t)\\=(k-1)\sum{i=0}^n(\frac{-P_{i-1}+P_i}{t_{i+k-1}-t_i})N_{i,k-1}(t),t\in[t_{k-1},t_{n+1}]$
几何不变性：曲线形状和位置相对于控制点的位置而不是坐标系；
变差缩减性：任何一个直线与B样条曲线的交点数目不会超过该直线与该B样条曲线的控制多边形的交点数目；
仿射不变性：由于
$$
A[P(t)]=\displaystyle\sum_{i=0}^nA[P_i]N_{i,k}(t),t\in[t_{k-1},t_{n+1}]
$$
故仿射变换后依旧成立；直线保持性：若控制多边形退化为一条直线，则B样条曲线依然在这条直线上；
灵活性：可以构造出线段，尖点，切线等。
De boor算法——计算B样条曲线的一点，使用直线段进行割角并不断递归，最终在一定深度后可得到曲线上的某一点（可以理解为数分的闭区间套定理）；
节点插入：在不改变一个B样条的几何形状和阶的条件下增加一个新的节点，以此来增加B样条曲线的可控程度。而在插入新的节点向量后，基函数也会改变，故需要求新的控制顶点，因此有了下述算法
Boehm给出的算法公式：
$$
\begin{cases}
P_j^1=P_j,j=0,1,…,i-k+1，\\
P_j^1=(1-\beta_j)P_{j-1}+\beta_jP_j,j=i-k+2,…,i-r，\\
P_j^1=P_{j-1},j=i-r+1,…,n+1，
\end{cases}
$$
$$
\beta=\frac {t-t_j}{t_{j+k-1}-t_j}
$$简略来说就是$0$到$i-k+1$和$i-r+1$到$n+1$不变，而对中间部分进行改变，$r$为新插入节点在节点序列中的重复度。
B样条曲面的数学定义：给定两个节点向量处于$U$和$V$两参数轴有：
$$
U=[u_0,u_1,…,u_{m+p}],V=[v_0,v_1,…,v_{n+q}]
$$
则$p\times q$的B样条曲面被定义为：
$$
P(u,v)=\displaystyle\sum_{i=0}^m\displaystyle\sum_{j=0}^nP_{ij}N_{i,p}(u)N_{j,q}(v)
$$
其中： $P_{ij}$是B样条曲面的控制网格（特征网格）
$N_{i,p}(u)$和$N_{j,q}(v)$是B样条的分别对于$p$和$q$的的基础函数，并且对于任意方向，都可以有Boor- Cox公式计算得到。
由于B样条曲线和Bezier曲线不能精确表示除了抛物线外的圆锥曲线，因此有了下述的曲线/曲面。
非均匀有理B样条：NURBS
其优点为：
- 更一般更精确的方法来表达对曲线曲面的设计；
- 提供通用的数学形式表示标准的解析曲面/曲线和自由曲线/曲面；
- 存在稳定快速的数值计算方法；
- 针对非有理和有理的Bézier曲线/曲面均可以看成NURBS的一种特殊形式；
其缺点为：
- 其存储空间较大；
- 若权重不合适，则会产生畸变；
- 不适合曲线重叠。
定义：NURBS是由分段有理B样条多项式基函数所定义的曲线，其函数为：
$$
P(t)=\frac {\displaystyle\sum_{i=0}^n\omega_iP_iN_{i,k}(t)}{\displaystyle\sum_{i=0}^n\omega_iN_{i,k}(t)}=\displaystyle\sum_{i=0}^nP_iR_{i,k}(t)
$$
其中：
$$
R_{i,k}(t)=\frac{\omega_iN_{i,k}(t)}{\displaystyle\sum_{i=0}^n\omega_iN_{i,k}(t)}
$$曲线性质
仍然具有B样条的性质：
- 局部支撑性：$R_{i,k}(t)=0,t\notin[t_i,t_{i+k}]$
- 归一性：$\displaystyle\sum_{i=0}^nR_{i,k}(u)=1$
- 可微性：若t不是结点，则$P(t)$在结点中间无限可微，否则则只在$C-k+r$阶连续
- 若$\omega_i=0$，则$R_{i,k}(t)=0$；
- 若$\omega_i=+\infty$，则$R_{i,k}=1$；
NURBS曲线有一些和B样条曲线相似的几何性质：
- 局部支持性；
- 变差缩减性；
- 凸包性；
- 仿射不变性；
- 可微性；
- 若控制点的权重为0，则该点不会影响曲线；
- 若$\omega_i\rightarrow+\infty$且$t\in[t_i,t_{i+k}]$，则$P(t)=P_i$；
- Non-rational/rational Bezier curves and nonrational B-Spline curves are special cases of NURBS curve.
通过齐次坐标表达控制点——即在这个向量末尾增加一维：
$$
P_i^ω=(ω_i x_i,ω_i y_i,ω_i z_i,ω_i),（i=0,1,…,n)
$$
其中$\omega_i$为权重，若$P(t)$关于$ω_i$是线性关系，则可以改变图形的形状。$\omega_i$其越大越靠近控制点，越小越远离控制点；圆锥曲线的表示方式：
$$
P(t)=\frac {(1-t^2)\omega_0P_0+2t(1-t)\omega_1P_1+t^2\omega_2P_2}{(1-t)^2\omega_0+2t(1-t)\omega_1+t^2\omega_2}
$$
注意其形状因子：
$$
C_{sf}=\frac {\omega_1^2}{\omega_0 \omega_2}
$$
其值为$1$则抛物线，大于$1$双曲线，$C_{sf}\in(0,1)$则为椭圆，为$04退化为两条直线，当趋近与正无穷时为直线。修改NURBS曲线：
修改方法：
修改权重：增/减控制点的权重，曲线则会被表现为往远处推/往近处拉；假设我们想要让在曲线上的点$S$发生相对于控制点$P_i$位移距离$d$，则新的权重$\omega^*$有如下公式：
$$
\omega^i=\omega_i[1+\frac{d}{R_{i,k}(t)(P_i)S-d}]
$$修改控制点：则会改变整个曲线的形状；
几何约束下的形状修改；其修改描述为计算新的控制点是的曲线上的点$S$变为指定点$T$，假设曲线等式如下：
$$
P_t=\displaystyle\sum_{i=0}^nP_iR_{i,k}(t),t_{k-1}\leq t \leq t_{n+1}
$$
其中：
$$
R_{i,k}(t)=\frac{\omega_iN_{i,k}(t)}{\displaystyle\sum_{i=0}^n\omega_iN_{i,k}(t)}
$$
带约束的优化方法：
假设前$m-1$个点已经修改，给予其微小形变$ε_i=(\epsilon_i^x,\epsilon_i^y,\epsilon_i^z)^T$。
然后使用优化方法对修改量计算，则约束为$\widetilde P(t)=\sum_{i=0}^{l-1}P_iR_{i,k}(t)+\sum_{i=l}^{l+m-1}(P_i+\epsilon_i)R_{i,k}(t)+\sum_{i=l+m}^{n}P_iR_{i,k}(t)\\=\sum_{i=0}^{n}P_iR_{i,k}(t)+ \sum_{i=l}^{l+m-1}\epsilon_iR_{i,k}$ ；
其中$t_{k-1}\leq t \leq t_{n+1};$
然后令$Min=\displaystyle\sum_{i=l}^{l+m-1}||\epsilon_i||^2$
使用拉格朗日函数有$L=\displaystyle\sum_{i=l}^{l+m-1}||\epsilon_i||^2+\lambda(T- \widetilde P(t_s))$
然后我们可以得到下面的方程组
$$
\begin{cases}
T=S+\displaystyle\sum_{i=l}^{l+m-1}\epsilon_iR_{i,k}(t_s),\\
\epsilon_i=\frac \lambda2R_{i,k}(t_s),i=l,l+1,…,l+m-1
\end{cases}
$$
可以解得$\epsilon_i=\frac {R_{i,k}(t_s)}{\displaystyle\sum_{i=l}^{l+m-1}R_{j,k}^2(t_s)},i=l,l+1,…,l+m-1$若只有唯一的控制点被允许修改：$\epsilon=\frac{T-S}{R_{i,k}(t_s)}$
我们也可以使用最小能量法对形状进行修改：
曲面的限制能量
$$
E(p)=\int k^2ds=\int_0^1(\frac {|P’\times P’’|}{|P’|})^2dt\rightarrow E(p)=\int|P’’|^2dt
$$薄板曲面能量
$$
E(P)=\iint(P_{uu}^2+2P_{uv}^2+P_{vv}^2)dudv
$$
NURBS曲面:
- 定义方式：
$$
P(u,v)=
\frac {\displaystyle\sum_{i=0}^{m}\displaystyle\sum_{j=0}^{n}\omega_{ij}P_{ij}N_{i,p}(u)N_{j,q}(v)}
{\displaystyle\sum_{i=0}^{m}\displaystyle\sum_{j=0}^{n}\omega_{ij}N_{i,p}(u)N_{j,q}(v)}
=\displaystyle\sum_{i=0}^{m}\displaystyle\sum_{j=0}^{n}P_{ij}R_{i,p,j,q}(u,v),u,b\in[0,1]
$$
其中：
$$
R_{i,p,j,q}(u,v)=\frac {\omega_{ij}N_{i,p}(u)N_{i,q}(v)}{\displaystyle\sum_{r=0}^{m}\displaystyle\sum_{s=0}^{n}\omega_{rs}P_{ij}N_{r,p}(u)N_{s,q}(v)}
$$
且四个角的权重$\omega_{00}，\omega_{m0}，\omega_{0n}，\omega_{mn}$均为正数，其他权重均为非负数。
性质（和B样条曲面具有类似）
- 局部支撑性；
- 局部归一;
- 可微：
- 在$U$方向有$C-p+r+l$阶连续可微；
- 在$V$方向有$C-q+r+1$阶连续可微；
- 局部极值：若$p,q>1$，则存在局部极大值。
- 定义方式：
网格（Mesh）
- 网格的描述：一系列的三角形面片$F$和一系列的顶点$V$，而$F$中的每个面片是$V$中的序列组（即$F$由$V$中的元素表示）；
- 表示原因：
- 因为图形学中需要一个统一的表示方式；
- 且视觉精度和处理速度需要在可接受的范围内；
- 再有由于图形硬件的快速发展，能快速的并行光栅化（rasterize）和三角网格的渲染（render）。
- 数据来源：文件I/O、程序建模、建模软件、3D扫描仪、照片重构或以上的技术组合；
- 两大类的模型：
- 基于实体的（实际加工过程），
- 基于表面的（无实体，只考虑表面，但易显示）。
- 网格化（Tessellation）：
- 二维网格化——多边形表示为多种不同形式并且需要分割成更易于处理的图元的过程。例如多边形分割为三角形称之为三角化（方法多样）。
- 基本的网格化算法：给定多边形，检验其任意两个顶点之间的线段是否与该多边形的边相交或者部分重叠，若相交则不能用来分割，若不相交则分割（不怎么好）。
- 割耳法：找到一个多边形，查看所有具有顶点序列$i,i+1,i+2(mod\space n)$的三角形，检查线段$i,i+2$是否与任意边相交。若是，则三角形$i+1$构成一个ear，割之，然后检验$i$和$i+2$的三角形是不是构成ear，直至遍历所有的顶点
- T型顶点：当相交表面的边缘部分重合，但是不完全共点是出现（理论可行，但是精度过高很难实现）。
- 简化需要的基础数学知识：
- 拓扑结构：指多边形网格的连接结构；
- 亏格（通俗的说一个模型上面的孔洞数目）：面片、边或顶点的局部拓扑，指相邻元素的局部连接关系。
- 2D流形（manifold）：若局部拓扑处处等价于一个圆盘，则为一个二维流形；在三角形网格流形拓扑中，恰好仅有两个三角形共用一条边，每个三角形分别与三个相邻的三角形共用一条共边。
- 带边界的二维流形：确保边界的边有且仅有一个三角形。（注：这些定义和拓扑学中的定义只是类似，但是拓扑学的定义则更为严谨）
- 单纯复形：由顶点集合担单形非空子集构成，$0$单形为点，$1$单形为边，$2$单形面，后续可数学归纳。
- 简化（simplification）：用一个相对简单的，但保持足够几何细节的网格模型近似表示。
- 目的：主要是为了减少几何上的冗余，减小模型大小，提高运行性能；
- 方法：采样，自适应细分，剔除，顶点合并（sampling, adaptive subdivision, decimation, vertex merging）。
- 采样（sampling）：通过选取模型表面上的点，简单的对模型进行几何采样，在编程存在困难和复杂，且对高频特征难以精确采样。通常在没有尖角的光滑表面上取得最好的效果。
- 自适应细分（adaptive subdivision）：通过寻找一个可以递归细分逼近最初模型的基网格，该算法在基模型易于获取的情况下较为适用；虽然其能够保持模型表面的拓扑细节，但对模型的大规模简化能力不足。
- 细分：给定一个原始网格，通过网格加细产生更光滑的效果。步骤主要为两步，
- 第一部细化阶段，创建新顶点与之前的顶点相连，产生新的更小的三角形（三角形形式多样）；
- 第二步为平滑阶段，计算新顶点的位置（计算方式可以由不同的插值方式生成）。
- 方案为
- loop细分：基于三角网格的细分方案，它更新每个已有的顶点，并对每条边创建一个新的顶点,然后每个三角形被分割成四个新三角形，$4n$步后生成$4n$个三角形。
- $\sqrt3$细分，他在每个三角形的中间加一个点，从而得到三个新的三角形，而为了更加均匀分布三角形，每个原始三角形的边都被翻转，使之连接两个相邻顶点的中间顶点而不是两个已经存在的旧顶点（注意这个边翻转）。
- 去除（Decimation）：迭代去掉网格的顶点或面片，并三角化每次去除后留下的空间，适用于处理共面多边形这种冗余的几何。
- 顶点合并（vertex merging）；将模型的两个或多个顶点合并为一个顶点，简单且易于编程，但是需要采用多个技术来确定合并点和合并次序（边坍塌算法）。
- 层次细节简化技术
- 应用：简化采样密集的多面体网格，激光扫描测距系统扫描真实三维物体，三维场景的存储/传输/绘制；
- 定义：指的是在不影响画面视觉效果的条件下，通过逐次简化景物的表面细节来减少场景的几何复杂性，从而提高绘制算法的效率。近处精细远处粗糙之间插值保证光滑；
- 方法有顶点删除，边压缩，面片压缩等。
- 长方体滤波算法，给定一多面体，记$K$为其拓扑，假设$M$已经三角化：
- 首先建立$M$的长方形包围盒，将其空间均匀剖分成一系列的小长方体子空间；
- 然后采用各长方体子控件对景物定点进行聚类合并，位于同一长方体空间的顶点被归于同一类；
- 最后属于同一类的顶点被合并为一代表点。
- 而这些代表顶点为与暗多面体所示景物的重新采样。
- 基于与暗多面体的K结构和这些采样点和重新产生以多面体，其保持了一定的层次细节模型。其多面体包围盒剖分生成的子空间越小，则层次模型越逼近原多面体。（会丢失部分高频细节）
- 顶点删除法：设法减少景物表面的采样点数目。删除不重要的顶点及其有关的所有面片，然后对删除后的空洞进行局部三角剖分。
- 渐进的网格简化技术：任一网格$M$均可表示为一个粗网格以及逐步细化的网格$M_i$的变化，一张网格定义为一个序偶$（K,V）$其中$K$为$M$的顶点，边，面的邻接关系（$K$为不包含点集的所有子集，仅包含了构造网络$M$所有面、边、顶点的子集）。$V$为顶点位置的向量集，表达$M$在$\R^3$的形状。同时引入拓扑实现：将顶点$i$看成$\R^m$的基向量，则定义$\R^m$的几何$|K|$的拓扑实现为$|K|=⋃_{s∈K}|s|$，其中$s$为$K$的一个单形，$|S|$为$s$在$\R^m$空间中顶点的凸包。
- 边收缩的合并原则：
- 相邻点+距离小于一定值；
- 二次误差度量。
