图形学笔记(五) 空间图形的几何表示(加工中)

空间图形的几何表示

曲线

什么是埃尔米特曲线？

**埃尔米特曲线(Hermit)**是一种插值曲线，也是样条曲线家族中最好理解的一种曲线。

Hermit曲线给定曲线两个端点的位置矢量$P_0$P0​、$P_1$P1​和切线矢量$T_0$T0​、$T_1$T1​，通过插值获得曲线在定义域[0,1]上的三次参数方程：

我们设目标参数方程为$P(t)=at^3+bt^2+ct+d$P(t)=at3+bt2+ct+d，则有$P'(t)=3at^2+2bt+c$P′(t)=3at2+2bt+c，将0和1代入t易得：
$\left \{ \begin{array}{c} \ P(0)&=&d\\\ P(1)&=&a+b+c+d\\\ P'(0)&=&c\\\ P'(1)&=&3a+2b+c \end{array}\right.\tag{14}$⎩⎪⎪⎨⎪⎪⎧​ P(0) P(1) P′(0) P′(1)​====​da+b+c+dc3a+2b+c​(14)
现在我们设$h_0=P(0),h_1=P(1),h_2=P'(0),h_3=P'(1)$h0​=P(0),h1​=P(1),h2​=P′(0),h3​=P′(1)，则有：
$\begin{bmatrix} h_0\\h_1\\h_2\\h_3 \end{bmatrix}=\begin{bmatrix} 0&0&0&1\\1&1&1&1\\0&0&1&0\\3&2&1&0 \end{bmatrix}\begin{bmatrix} a\\b\\c\\d \end{bmatrix}\\\Rightarrow\begin{bmatrix} a\\b\\c\\d \end{bmatrix}=\begin{bmatrix} 2&-2&1&1\\-3&3&-2&-1\\0&0&1&0\\1&0&0&0 \end{bmatrix}\begin{bmatrix} h_0\\h_1\\h_2\\h_3 \end{bmatrix}$⎣⎢⎢⎡​h0​h1​h2​h3​​⎦⎥⎥⎤​=⎣⎢⎢⎡​0103​0102​0111​1100​⎦⎥⎥⎤​⎣⎢⎢⎡​abcd​⎦⎥⎥⎤​⇒⎣⎢⎢⎡​abcd​⎦⎥⎥⎤​=⎣⎢⎢⎡​2−301​−2300​1−210​1−100​⎦⎥⎥⎤​⎣⎢⎢⎡​h0​h1​h2​h3​​⎦⎥⎥⎤​
我们将参数方程$P(t)=at^3+bt^2+ct+d$P(t)=at3+bt2+ct+d写成矩阵形式：
$P(t)=\begin{bmatrix} a&b&c&d \end{bmatrix}\begin{bmatrix} t^3\\t^2\\t\\1 \end{bmatrix}$P(t)=[a​b​c​d​]⎣⎢⎢⎡​t3t2t1​⎦⎥⎥⎤​
将列向量abcd的表达式转置，代入上式，得到：
$P(t)=\begin{bmatrix} h_0&h_1&h_2&h_3 \end{bmatrix}\begin{bmatrix} 2&-3&0&1\\-2&3&0&0\\1&-2&1&0\\1&-1&0&0 \end{bmatrix}\begin{bmatrix} t^3\\t^2\\t\\1 \end{bmatrix}$P(t)=[h0​​h1​​h2​​h3​​]⎣⎢⎢⎡​2−211​−33−2−1​0010​1000​⎦⎥⎥⎤​⎣⎢⎢⎡​t3t2t1​⎦⎥⎥⎤​
将后两项乘起来可以得到：

$P(t)=\sum_{i=0}^3h_iH_i(t)\\$P(t)=i=0∑3​hi​Hi​(t)
其中$h_1=P(0)=P_0$h1​=P(0)=P0​，$h_2=P(1)=P_1$h2​=P(1)=P1​，$h_3=P'(0)=T_0$h3​=P′(0)=T0​，0$h_4=P'(1)=T_1$h4​=P′(1)=T1​。

什么是贝塞尔曲线？

贝塞尔曲线也是参数格式的曲线，n阶贝塞尔曲线是n次参数方程，其原理图如下：

贝塞尔曲线完全由其控制点决定其形状，n个控制点对应着n-1阶的贝塞尔曲线，并且可以通过递归的方式来绘制。贝塞尔曲线是典型的递归法曲线。

一阶贝塞尔曲线就是对两个控制点进行线性插值，其参数方程为：
$B_1(t)=P_0+(P_1-P_0)t=(1-t)P_0+tP_1,t\in[0,1]$B1​(t)=P0​+(P1​−P0​)t=(1−t)P0​+tP1​,t∈[0,1]
二阶贝塞尔曲线由三个控制点组成，假设三个控制点依次为P₀、P₁、P₂，先分别对P₀P₁和P₁P₂两段进行线性插值得到两个新控制点P₀’、P₁’，将二阶贝塞尔曲线降为一阶：
$P'_0=(1-t)P_0+tP_1\\ P'_1=(1-t)P_1+tP_2$P0′​=(1−t)P0​+tP1​P1′​=(1−t)P1​+tP2​
然后再对P₀’P₁’求线性插值：
$B_2(t)=(1-t)P'_0+tP'_1=(1-t)^2P_0+2t(1-t)P_1+t^2P_2$B2​(t)=(1−t)P0′​+tP1′​=(1−t)2P0​+2t(1−t)P1​+t2P2​
三阶贝塞尔曲线由四个控制点组成，假设四个控制点依次为P₀、P₁、P₂、P₃，先分别对P₀P₁、P₁P₂和P₂P₃三段求线性插值得到三个新控制点P₀’、P₁’、P₂’，将三阶贝塞尔曲线降为二阶：
$P'_0=(1-t)P_0+tP_1\\ P'_1=(1-t)P_1+tP_2\\ P'_2=(1-t)P_2+tP_3$P0′​=(1−t)P0​+tP1​P1′​=(1−t)P1​+tP2​P2′​=(1−t)P2​+tP3​
然后再利用新控制点求二阶贝塞尔曲线：
$P''_0=(1-t)P'_0+tP'_1\\ P''_1=(1-t)P'_1+tP'_2$P0′′​=(1−t)P0′​+tP1′​P1′′​=(1−t)P1′​+tP2′​
最后对P₀’‘和P₁’'进行线性插值：
$B_3(t)=(1-t)P''_0+tP''_1=(1-t)^3P_0+3t(1-t)^2P_1+3t^2(1-t)P_2+t^3P_3$B3​(t)=(1−t)P0′′​+tP1′′​=(1−t)3P0​+3t(1−t)2P1​+3t2(1−t)P2​+t3P3​
不难发现，n阶贝塞尔曲线展开式系数是n阶二项式展开系数，可以得到n阶贝塞尔曲线的通项公式：
$B_n(t)=\sum_{i=0}^n\frac{n!}{i!(n-i)!}t^i(1-t)^{n-i}P_i,\ t\in[0,1]$Bn​(t)=i=0∑n​i!(n−i)!n!​ti(1−t)n−iPi​, t∈[0,1]
其中，n阶贝塞尔曲线的第i项系数B_i,n(t)又被记作Bernstein基函数。
$B_{i,n}(t)=\frac{n!}{i!(n-i)!}t^i(1-t)^{n-1}\\ B_n(t)=B_{i,n}(t)P_i,\ t\in[0,1]$Bi,n​(t)=i!(n−i)!n!​ti(1−t)n−1Bn​(t)=Bi,n​(t)Pi​, t∈[0,1]
对n阶贝塞尔曲线进行求导可得：
$B'_n(t)=\sum_{i=0}^{n-1}B_{i,n-1}(t)[n(P_{i+1}-P_i)],\ t\in[0,1]$Bn′​(t)=i=0∑n−1​Bi,n−1​(t)[n(Pi+1​−Pi​)], t∈[0,1]
经观察，n阶贝塞尔曲线的导数显然是n-1阶贝塞尔曲线，其控制点为原曲线控制点的组合。

贝塞尔曲线具有端点性质：第一个控制点和最后一个控制点恰好是曲线的起点和重点。

贝塞尔曲线具有凸包性质：贝塞尔曲线始终位于包含了所有控制点的最小凸多边形中。注意，不是按控制点顺序围成的凸多边形。

贝塞尔曲线具有端点导数性质：贝塞尔曲线在P₀和P_n处的斜率分别等于直线P₀P₁和直线P_n-1P_n的斜率，即贝塞尔曲线端点的一阶导数仅同其相邻的一条边向量有关，与更远的各边无关。推广的，贝塞尔曲线端点的r阶导数仅同其相邻的r条边向量有关，与更远的各边无关。

贝塞尔曲线最大的问题在于，高阶贝塞尔曲线的路径不够直观，很难让美术人员利用贝塞尔曲线进行设计。但我们注意到，由于贝塞尔曲线具有端点性质和端点导数性质，二阶和三阶贝塞尔曲线的形状相对直观。所以在实际使用中我们会讨论到将多个贝塞尔曲线尤其是二、三阶贝塞尔曲线拼接成直观曲线的算法。

如何拼接贝塞尔曲线？

我们先聊聊什么是连续性。

在讨论曲线连续性时，我们经常见到Cⁿ连续和Gⁿ连续的说法。如果不同曲线都用参数方程来描述，那么在连接点处n阶导数连续，就被称为Cⁿ连续。在图形学中，一般最高只要求C²连续，因为更高阶的连续已经超出了人眼视觉能识别的层次。但Cⁿ连续有一个致命的缺陷，那就是连续性会随参数的选取而变化，这使得Cⁿ连续不具备普适性，不能用于广泛的学术交流。

为了避免这个缺陷，人们引入了几何连续性和自然参数方程，定义曲线的弧长s作为自然参数，这样任何参数方程都可以转换为自然参数方程，在连接点处自然参数方程的n阶导数连续，就称为Gⁿ连续。在图形学中，一般最高也只要求G²连续。

考察G⁰，G¹，G²连续的几何意义。G⁰就是满足位置连续，即两曲线端点重合。G¹满足两曲线在端点上具有相同的切线方向。G²满足曲线在端点上具有相同的自然参数二阶导失，也就是对一般参数方程具有相同的曲率矢量。

曲率矢量的求法：
$k=\frac{r'(t)\times r''(t)}{|r'(t)|^3}$k=∣r′(t)∣3r′(t)×r′′(t)​
设两条贝塞尔曲线P和Q的参数方程P(t)和Q(t)，它们的控制点序列分别是P₀、P₁……P_n和Q₀、Q₁……Q_m，则满足C⁰和G⁰的连接条件是P(1)=G(0)，即P_n=Q₀。满足G¹的连接条件是P_n-1、P_n=Q₀、Q₁这三点共线且顺序排列。在满足G¹连接的基础上，如果**|P_n-1P_n|=|Q₀Q₁|**，则满足C¹连接。

根据端点导数性质，C²和G²的达成与P_n-2和Q₂有关。记a_i=P_i-P_i-1，b_i=Q_i-Q_i-1，则对曲线P和Q的端点求其曲率，也就是曲率矢量的模，得：
$K_P(1)=\frac{(n-1)|a_{n-1}\times a_n|}{n|a_n|^3}\\ K_Q(0)=\frac{(m-1)|b_1\times b_2|}{m|b_1|^3}$KP​(1)=n∣an​∣3(n−1)∣an−1​×an​∣​KQ​(0)=m∣b1​∣3(m−1)∣b1​×b2​∣​
将P_n-1、P_n=Q₀、Q₁所在的公切线记为直线l，a_n-1与a_n之间的夹角记为θ，b₁与b₂之间的夹角记为φ，P_n-2到l的距离记为h₁，Q₂到l的距离记为h₂。根据几何关系可知：
$|a_{n-1}\times a_n|= |a_{n-1}|\times|a_n|\times\sin\theta =|a_{n-1}|\times|a_n|\times\frac{h_1}{|a_{n-1}|}=|a_n|h_1\\ |b_1\times b_2|= |b_1|\times|b_2|\times\sin\theta =|b_1|\times|b_2|\times\frac{h_2}{|b_1|}=|b_1|h_2\\$∣an−1​×an​∣=∣an−1​∣×∣an​∣×sinθ=∣an−1​∣×∣an​∣×∣an−1​∣h1​​=∣an​∣h1​∣b1​×b2​∣=∣b1​∣×∣b2​∣×sinθ=∣b1​∣×∣b2​∣×∣b1​∣h2​​=∣b1​∣h2​

过端点P_n=Q₀作公切线l的垂线v，过端点P_n-2和Q₂分别作l的平行线交v于点A、B。连接AP_n-1、BQ₁，过点P_n-1作线端AP_n-1的垂线CP_n-1交v于C，过点Q₁作线端BQ₁的垂线DQ₁交v于D。记C到l的距离为g₁，D到l的距离为g₂。

在直角三角形ACP_n-1和直角三角形BDQ₁中，有：
$a_n^2=h_1g_1\\ b_1^2=h_2g_2$an2​=h1​g1​b12​=h2​g2​
于是将曲率变形为：
$K_P(1)=\frac{n-1}{n}\frac{|a_n|h_1}{|a_n|^3}=\frac{n-1}{n}\frac1{g_1}\\ K_Q(0)=\frac{m-1}{m}\frac{|b_1|h_2}{|b_1|^3}=\frac{m-1}{m}\frac1{g_2}$KP​(1)=nn−1​∣an​∣3∣an​∣h1​​=nn−1​g1​1​KQ​(0)=mm−1​∣b1​∣3∣b1​∣h2​​=mm−1​g2​1​
满足G²的条件是K_Q(0)=βK_P(1)，此时：
$\beta=\frac{n(m-1)}{m(n-1)}\frac{g_1}{g_2}$β=m(n−1)n(m−1)​g2​g1​​
满足C²的条件是β=1且两曲线具有公共的切平面，要满足β=1即：
$g_1=\frac{m(n-1)}{n(m-1)}g_2$g1​=n(m−1)m(n−1)​g2​
在特殊条件下，若m=n，则满足β=1的条件是g₁=g₂。

要满足两曲线具有公共切平面，则点P_n-2、P_n-1、P_n=Q₀、Q₁、Q₂五点必须共面，并且点P_n-2和点Q₂应位于另三个顶点所在公切线的同侧。

如何获得匀速贝塞尔曲线？

我们已经得到了贝塞尔曲线的参数方程，但显然，如果将参数t作为时间变量，将物体沿曲线运动，我们很难得到一个匀速的运动效果。事实上，在靠近控制点处运动的较慢，而在曲线中段则运行的较快。同时，我们也很难在贝塞尔曲线的拼接处获得良好的平滑速度。

我们可以先求得B(t)相对于t的速度公式，我们先将t看作时间变量，在单个方向上对t求导就可以得到
$v(t)=\sqrt{B_x'(t)^2+B_y'(t)^2+B_z'(t)^2}$v(t)=Bx′​(t)2+By′​(t)2+Bz′​(t)2​
现在我们以二阶贝塞尔曲线为例，记$B_x'(t)^2+B_y'(t)^2+B_z'(t)^2 = At^2+Bt+C$Bx′​(t)2+By′​(t)2+Bz′​(t)2=At2+Bt+C，将左式展开：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …
注意到，A为完全平方式，我们设$\alpha = 2P_0-4P_1+2P_2$α=2P0​−4P1​+2P2​，则$A=\alpha_x^2+\alpha_y^2+\alpha_x^2$A=αx2​+αy2​+αx2​。同理我们记$\beta=2P_0-2P_1$β=2P0​−2P1​，则有$C=\beta_x^2+\beta_y^2+\beta_z^2$C=βx2​+βy2​+βz2​，$B=-2(\alpha_x\beta_x+\alpha_z\beta_y+\alpha_z\beta_z)$B=−2(αx​βx​+αz​βy​+αz​βz​)。经整理得：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …
写成向量形式即：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …
根据这个公式得出贝塞尔曲线得长度公式$L(t)$L(t)：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …
显然，整条曲线的长度为L(1)，我们求变量t的函数$T(t)$T(t)，使得$L(T(t))=L(1)*t$L(T(t))=L(1)∗t，则$T(t)=L^{-1}[L(1)*t]$T(t)=L−1[L(1)∗t]。由于对L(t)求逆函数几乎不可能，在这里我们利用L(t)的导数v(t)，使用牛顿切线法求出离散的近似解：
$T_{n+1}=T_n+\frac{\Delta L}{v(T_n)}$Tn+1​=Tn​+v(Tn​)ΔL​
其中$\Delta L$ΔL是每次前进的长度，如果按$t\in [0,1]$t∈[0,1]来计算前进的长度则：
$\Delta L = L(1)\times t -T_n$ΔL=L(1)×t−Tn​
有了上面的经验，我们再来求三阶贝塞尔曲线的$T_n$Tn​，记$B_x'(t)^2+B_y'(t)^2+B_z'(t)^2 = At^4+Bt^3+Ct^2+Dt+E$Bx′​(t)2+By′​(t)2+Bz′​(t)2=At4+Bt3+Ct2+Dt+E，将左式展开得：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …
观察到，A和E为完全平方式，我们取$\alpha=3P_0-9P_1+9P_2-3P_3$α=3P0​−9P1​+9P2​−3P3​，则$A=\alpha_x^2+\alpha_y^2+\alpha_z^2$A=αx2​+αy2​+αz2​。取$\beta=3P_0-3P_1$β=3P0​−3P1​，则$E=\beta_x^2+\beta_y^2+\beta_z^2$E=βx2​+βy2​+βz2​。注意到，D是β的倍数，我们取$\gamma=3P_0-6P_1+3P_2$γ=3P0​−6P1​+3P2​，有$D=-4(\beta_x\gamma_x+\beta_y\gamma_y+\beta_z\gamma_z)$D=−4(βx​γx​+βy​γy​+βz​γz​)。类似的，又得到$B=-4(\alpha_x\gamma_x+\alpha_y\gamma_y+\alpha_z\gamma_z)$B=−4(αx​γx​+αy​γy​+αz​γz​)。

C的推导过程比较繁琐，但核心思路如下：设$a=m_3-m_2,b=m_2-m_1,c=m_1-m_0$a=m3​−m2​,b=m2​−m1​,c=m1​−m0​，将C配方得到与a、b、c、a+b、b+c、a+b+c有关得表达式，然后展开得到$C=18[2b^2+3c^2+ac-6bc]$C=18[2b2+3c2+ac−6bc]，易得：
$C=\sum_m^{m\in \{x,y,z\}}4\gamma_m^2+2\alpha_m\beta_m$C=m∑m∈{x,y,z}​4γm2​+2αm​βm​
最后整理整个公式：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …
写成向量形式即：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …

什么是B样条曲线？

仅修改贝塞尔曲线的一个控制点，也会影响到整个曲线的形状。为了弥补这个缺陷，deBoor发明了B样条曲线，B样条曲线基于deBoor-Cox递推公式实现。

B样条曲线本质上是对多段短贝塞尔曲线的连续拼接。

n段p次B样条曲线由n+1个控制点P₀、P₁……P_n练成的n段的控制折线，和一个m维节点向量U={u₀,u₁,……,u_m}组成。

其中u_i为节点(pnots)，m个节点将完整的B样条曲线划分成了m-1个曲线段，每个曲线段都定义在一个节点区间上。对p次的B样条曲线来说，这m-1个曲线段都是p次的贝塞尔曲线。

如果u_i=u_i+1=……=u_i+k-1，那么u_i节点被称为一个重复度(multiplicity)为k的多重节点，$1<k\le p$1<k≤p，节点的重复度也被称为度数。否则如果一个节点只出现一次，那么这就是一个简单节点。如果u₁-u₀=u₂-u₁=……=u_m-u_m-1，即节点等距，则称节点向量为均匀的，称B样条曲线为均匀B样条曲线，否则称节点向量为非均匀的，称B样条曲线为非均匀B样条曲线。

p次B样条曲线要求满足m=n+p+1，显然，不同于贝塞尔曲线，B样条曲线的次数与控制点的数量无关。贝塞尔曲线中的t取值范围是[0,1]，而B样条曲线中的u取值范围可能比[0,1]更小。

B样条曲线和贝塞尔曲线的核心差别是，B样条曲线用B样条基函数替代Bernstein基函数，B样条曲线的公式为：
$C(u)=\sum_{i=0}^nN_{i,p}(u)P_i$C(u)=i=0∑n​Ni,p​(u)Pi​
其中N_i,p(u)是第i个p次B样条基函数，也叫调和函数，或者p次规范B样条基函数。这个函数使用deBoor-Cox递推公式，其定义如下：
$N_{i,0}(u)=\left \{ \begin{array}{c} 1&u_i\le u<u_{i+1}\\0&otherwise \end{array}\right.\\ N_{i,p}(u)\frac{u-u_i}{u_{i+p}-u_i}N_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u)$Ni,0​(u)={10​ui​≤u<ui+1​otherwise​Ni,p​(u)ui+p​−ui​u−ui​​Ni,p−1​(u)+ui+p+1​−ui+1​ui+p+1​−u​Ni+1,p−1​(u)

注：在该递推公式中认为0÷0=0。

可见，B样条基函数的形态主要受u_i的取值影响。以U={0,0.25,0.5,0.75,1}的2段2次B样条曲线为例直观的感受B样条基函数的形象：

可以归纳得出，基函数N_i,p(u)在区间[u_i,u_i+p+1)上非零。反过来，在区间[u_i,u_i+1)上，共有p+1个p次基函数非零，分别是：N_i-p,p(u)，N_i-p+1,p(u)，N_i-p+2,p(N)……N_i-1,p(u)和N_i,p(u)。

当计算N_i,p(u)时，它在区间[u_i,u_i+p+1)上非零。在deBoor-Cox递推公式中，N_i,p(u)被拆解为一个N_i,p-1(u)项和一个N_i+1,p-1(u)项，前者在[u_i.,u_i+p)上非零，如果u∈[u_i.,u_i+p)，那么$\frac{u-u_i}{u_{i+p}-u_i}$ui+p​−ui​u−ui​​恰好是u和这个区间左端的距离与这个区间长度的比；同理，后者在[u_i+1,u_i+p+1)上非零，如果u∈[u_i+1,u_i+p+1)，那么$\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}$ui+p+1​−ui+1​ui+p+1​−u​恰好是u和这个区间右端的距离与这个区间长度的比。如图所示：

B样条线的形状与节点的度数直接关联，两种具有特殊度数格式的B样条曲线如下：

• 均匀B样条曲线

  节点成等差数列均匀分布。

• 准均匀B样条曲线

  在均匀B样条曲线的基础上，两端节点的度数为p+1，中间节点的度数为p。

一般的B样条曲线称为开B样条曲线，即曲线不会与控制折线的第一边和最后一边接触，对于开B样条曲线，其定义域为[u_p,u_m-p]。可见，均匀B样条曲线就是一种特殊的开B样条曲线。

强制第一个节点和最后一个节点的重复度为p+1，那么产生的曲线就会分别与第一边和最后一边相切，这样的曲线被称为clamped-B样条曲线。可见，准均匀B样条曲线就是一种特殊的clamped-B样条曲线。

通过重复节点和控制点，可以使产生的曲线形成闭环，称为闭B样条曲线。生成闭B样条曲线的方法有两种：

• Wrapping控制点

  设计一个m+1个节点的节点序列U={$u_0=0,u_1=\frac1m,u_2=\frac2m,...u_{m-1}=\frac{m-1}m,u_m=1$u0​=0,u1​=m1​,u2​=m2​,...um−1​=mm−1​,um​=1}，对曲线的头p个和尾p个控制点，令$P_0=P_{n-p+1}$P0​=Pn−p+1​,$P_1=P{n-p+2}$P1​=Pn−p+2,…,$P{p-2}=P_{n-1}$Pp−2=Pn−1​,$P_{p-1}=P_n$Pp−1​=Pn​。曲线的定义域为[$u_p,u_{n-p}$up​,un−p​]，且在连接点C($u_p$up​)=C($u_{n-p}$un−p​)上保证C^p-1连续性。

• Wrapping节点

  设计n+1个控制点，并使$P_n=P_0$Pn​=P0​。先找到具有n个节点的单调节点序列U，在U基础上增加p+1个节点，并使$u_{n+1}=u_0,u_{n+2}=u_1,...,u_{n+p}=u_{p-1},u_{n+p+1}=u_p$un+1​=u0​,un+2​=u1​,...,un+p​=up−1​,un+p+1​=up​，这样得到一个定义域为[$u_0,u_{n+1}$u0​,un+1​]的闭曲线，在连接点C($u_0$u0​)=C($u_{n+1}$un+1​)上保证C^p-1连续性。

曲线是如何被光栅化的？

曲线是通过被细分成许多段直线进行光栅化的，所以我们必须先了解平面上直线的光栅化。

设直线的斜率为k，当$k=0,k=\pm1,k=\pm\infty$k=0,k=±1,k=±∞时，直线的光栅化方法显而易见。所以我们只考虑在$0\lt|k|\lt1$0<∣k∣<1的情况下直线的光栅化算法，这样也可以类比推出在$1<|k|<\infty$1<∣k∣<∞下的算法。

DDA算法是最简单的直线光栅化算法，它的核心思路在于步进和通过舍入选择像素。

当$0\lt|k|\lt1$0<∣k∣<1时，选择对x进行步进，即$x_{i+1}=x_i\pm1$xi+1​=xi​±1，则$y_{i+1}=y_i+k$yi+1​=yi​+k。相对的，当$1<|k|<\infty$1<∣k∣<∞时，选择对y进行步进，即$y_{i+1}=y_i\pm1$yi+1​=yi​±1，$x_{i+1}=x_i\pm\frac1k$xi+1​=xi​±k1​。最后选择对$x_{i+1}$xi+1​和$y_{i+1}$yi+1​进行舍入后的像素点进行光栅化。

中点画线法是经典的直线光栅化算法。它相比于DDA的进步在于巧妙的避免了浮点运算，有效提升了渲染效率。

直线的一般式方程为$F(x,y)=0$F(x,y)=0，这条直线将平面分为三个区域：直线上方的点、直线下方的点以及直线上的点。其中，对于直线上方的点，$F(x,y)>0$F(x,y)>0；直线下方的点，$F(x,y)<0$F(x,y)<0；直线上的点，$F(x,y)=0$F(x,y)=0。

中点画线法也使用步进思想，但它在每次移动时，根据中点误差项判断而非舍入来决定是在水平/竖直方向上移动一个像素，还是在斜方向上移动一个像素。

在上图中，像素点$P(x_i,y_i)$P(xi​,yi​)已经被选中，接下来直线既穿过了像素点又$P_d$Pd​穿过了像素点$P_u$Pu​，我们应当在这两个像素中选择一个进行绘制。我们考察直线与线段$P_dP_u$Pd​Pu​的交点$Q$Q，如果它更靠近$P_d$Pd​则绘制$P_d$Pd​，否则绘制$P_u$Pu​。

于是我们将$P_u$Pu​与$P_d$Pd​的中点$M$M纳入考量，将$M$M点坐标代入方程$F(x_i,y_i)$F(xi​,yi​)，即，如果结果小于0，则$M$M在$Q$Q下方，取$P_u$Pu​，如果结果大于0，则$M$M在$Q$Q上方，取$P_d$Pd​。如果恰等于0，则两者皆可。

我们记$d_i=F(x_i+1,y_i+0.5)$di​=F(xi​+1,yi​+0.5)，当然，每次移动都代入方程来计算$d_i$di​是合理的，但并不高效。我们试图通过找到递推公式$d_{i+1}=d_i+\Delta d$di+1​=di​+Δd来减少代入方程带来的计算。
$d_i=F(x_i+1,y_i+0.5)=A(x_i+1)+B(y_i+0.5)+C$di​=F(xi​+1,yi​+0.5)=A(xi​+1)+B(yi​+0.5)+C
当$d_i<0$di​<0时，取$P_u$Pu​，即右上方的像素，则
$d_{i+1}=F(x_i+2,y_i+1.5)=A(x_i+2)+B(y_i+1.5)+C=d_i+A+B$di+1​=F(xi​+2,yi​+1.5)=A(xi​+2)+B(yi​+1.5)+C=di​+A+B
当$d_i \ge 0$di​≥0时，取$P_d$Pd​，即右方的像素，则
$d_{i+1}=F(x_i+2,y_i+0.5)=A(x_i+2)+B(y_i+0.5)+C=d_i+A$di+1​=F(xi​+2,yi​+0.5)=A(xi​+2)+B(yi​+0.5)+C=di​+A
总结可得：
$d_{i+1}= \left \{ \begin{array}{c} d_i+A+B&d<0\\d_i+A&d\ge 0 \end{array}\right.\ \ \ \ \ \ \ \ \ \ ,d_0=A+0.5B$di+1​={di​+A+Bdi​+A​d<0d≥0​          ,d0​=A+0.5B

由于d只关心符号，所以可以使用2d代替d来避免浮点运算，进一步提升性能。

Bresenham算法与中点画线法实际上是同一算法，只是对算法的解释不同，在此不多赘述。

在光栅化曲线时，只需要将曲线参数方程映射到像素坐标系下，对不同的参数取值将曲线细分成多条线段，在线端上应用直线光栅化算法即可。

曲面

什么是贝塞尔曲面？

我们先复习贝塞尔曲线的定义：
$B_n(t)=\sum_{i=0}^nB_{i,n}(t)P_i,\ t\in[0,1]$Bn​(t)=i=0∑n​Bi,n​(t)Pi​, t∈[0,1]
其中$B_{i,n}(t)$Bi,n​(t)是Bernstein基函数：
$B_{i,n}(u)=\frac{n!}{i!(n-i)!}u^i(1-u)^{n-1}$Bi,n​(u)=i!(n−i)!n!​ui(1−u)n−1

贝塞尔曲面本质上就是先对每一行做贝塞尔曲线，然后将这些贝塞尔曲线的结果作为列贝塞尔曲线的控制点。

我们用两个参数u、v代替t，分别在两个方向上描述贝塞尔曲面的形状，相对应的，我们需要n×m个控制点控制整个曲面，记控制点为$P_{ij},i\in n,j\in m$Pij​,i∈n,j∈m。

在上图中，$q_i (u)$qi​(u)由每行的m个控制点控制，是一条m-1阶的贝塞尔曲线。即：
$q_i(u)=\sum_{j=0}^mB_{j,n}(u)P_{ij}$qi​(u)=j=0∑m​Bj,n​(u)Pij​
紧接着，这n条贝塞尔曲线$q_i (u)$qi​(u)在$u=u_0$u=u0​上取得了n个点，将这n个点作为v方向上的贝塞尔曲线的控制点得到整个贝塞尔曲面的方程：
$P(u,v)=\sum_{i=0}^nB_{i,n}(v)q_i(u)\\ P(u,v)=\sum_{i=0}^n\ [B_{i,n}(v)\sum_{j=0}^mB_{j,n}(u)P_{ij}]$P(u,v)=i=0∑n​Bi,n​(v)qi​(u)P(u,v)=i=0∑n​ [Bi,n​(v)j=0∑m​Bj,n​(u)Pij​]
显然，贝塞尔曲面的定义域是参数范围[0,1]×[0,1]。

什么是B样条曲面？

B样条曲面的思路和贝塞尔曲面一致，我们也用两个参数u、v代替t，使用n×m个控制点，则相对的，我们需要节点矢量U={u₀,u₁,…,u_n+p}和V={v₀,v₁,…v_m+q}，他们分别由n+p+1和m+q+1个节点组成，它们的要求和B样条曲线中一致。

只需将贝塞尔曲面中的Bernstein基函数改为B样条基函数就可以得到B样条曲面的定义，在此我们先复习一下B样条基函数的deBoor-Cox递推公式：
$N_{i,0}(u)=\left \{ \begin{array}{c} 1&u_i\le u<u_{i+1}\\0&otherwise \end{array}\right.\\ N_{i,p}(u)\frac{u-u_i}{u_{i+p}-u_i}N_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u)$Ni,0​(u)={10​ui​≤u<ui+1​otherwise​Ni,p​(u)ui+p​−ui​u−ui​​Ni,p−1​(u)+ui+p+1​−ui+1​ui+p+1​−u​Ni+1,p−1​(u)
用B样条基函数替换Bernstein基函数：
$P(u,v)=P(u,v)=\sum_{i=0}^n\ [N_{i,n}(v)\sum_{j=0}^mN_{j,n}(u)P_{ij}]$P(u,v)=P(u,v)=i=0∑n​ [Ni,n​(v)j=0∑m​Nj,n​(u)Pij​]
显然，B样条曲面的定义域是参数范围[u_p,u_n+1]×[v_q,v_q+1]。

什么是Nurbs曲面？

Nurbs是非均匀有理B样条的缩写，B样条曲面是Nurbs曲面的一种特例。Nurbs建模(也被称为曲面建模)是工业3D建模的一个重要方式，另一种更常见的建模方式则是多边形建模。

Nurbs相比一般B样条曲面的改进在于，通过调整曲面中控制点的权，来产生更好的平滑性。我们记$W_{ij}$Wij​为控制点$P_{ij}$Pij​的权值，除此之外的定义都与B样条曲线相同。

下面直接给出Nurbs曲面的参数方程：
$S(u,v)=\frac {\sum_{i=0}^n\sum_{j=0}^mN_{i,p}(u)N_{j,q}(v)W_{ij}P_{ij} } {\sum_{i=0}^n\sum_{j=0}^mN_{i,p}(u)N_{j,q}(v)W_{ij}}$S(u,v)=∑i=0n​∑j=0m​Ni,p​(u)Nj,q​(v)Wij​∑i=0n​∑j=0m​Ni,p​(u)Nj,q​(v)Wij​Pij​​
其中$N_{i,p}(u)$Ni,p​(u)是B样条基函数。

显然，Nurbs曲面的定义域也是参数范围[u_p,u_n+1]×[v_q,v_q+1]。

曲面如何进行渲染？

由于曲面是矢量图形，我们采用和曲线一样的渲染思路，在参数空间上以任意精细度对参数点进行采样，将采样结果组成四边形或三角形，然后就可以以多边形的方式对其进行渲染。

对于更高级的渲染方案，可以通过在距离摄像机近处密集采样，距离摄像机远除粗略采样，来提升渲染性能。

多边形

多变形是如何被光栅化的？

什么是消隐算法？

如何进行多边形的三角形化？