由浅入深地理解样条曲线
本文简要介绍计算机图图形学中的常用的各个样条曲线,同时梳理他们的之间的关系。
前言
在阅读本文之前,请先静下心来,一步一步理解公式,不要因公式复杂而望而却步。如果慢慢理解,它其实也挺简单。
对于下列形式的公式说明: \[ \begin{equation} P(t) = \sum_{i=0}^{n}P_iB_{i}(t) \end{equation} \] 上述公式表示 \(P_t\) 是通过将多个点乘以一个函数 \(B_i(t)\)相加求得,这个公式的可以理解成曲线上的每个点 \(P_t\) 是 n 维线性空间中的点,\(B_i(t)\) 是线性空间中的基函数。
n 维线性空间不是指笛卡尔坐标系下的 n 维,而是线性代数上的维度,如果对这个概念不是很清楚,可以查阅相关书籍,当然,上述的这个理解方式也可以忽略。
贝塞尔曲线(Bézier curve)
定义
\[ \begin{split} P(t) &= \sum_{i=0}^{n}P_i \cdot B_{i,n}(t),t \in [0,1] \\ B_{i,n}(t) &= C_n^it^i(1-t)^{n-i}=\frac{n!}{i!(n-i)!}t^i(1-t)^{n-i},i \in[0,1,\cdot\cdot\cdot,n] \end{split} \] ### 理解
参数说明
\(t\)
参数 \(t\) 是隐函数 \(P(t)\) 的参数,它的值域是 [0,1],在计算机中,通过将 \(t\) 从 0 递增到 1,来生成贝塞尔曲线上的点,因此 \(t\) 的步长越短,其生成的曲线越光滑
\(P_i\)
\(P_i\) 是由用户给定的控制点,下标 \(i\) 代表点的顺序
\(C_n^i\)
\(C_n^i\) 称为二项式系数。
二项式展开定义如下: \[ \begin{split} (a+b)^n = \sum_i^n C_n^i a^{n-i} b^i \end{split} = \sum_i^n \frac{n!}{i!(n-i)!}\cdot a^{n-i} \cdot b^i \]
\(B_{i,n}(t)\)
这个叫做贝塞尔曲线的基函数,它的计算公式见上面的公式。\(\sum_i^n B_{i,n}(t)\) 是二项式 \((t+(1-t))^n\) 的展开公式。
\(i\) 代表点的序号,从 0 开始;\(n\) 叫次数(degree)。
如果点的数量为 p,则 \(n\) 与 \(p\) 的关系为 \(n=p-1\)。
其它说明
- 一条贝塞尔曲线是由多个控制点共同决定的,n(次数)决定了生成一条曲线需要使用多少个控制点。
- 复杂形状通常要将多条贝塞尔曲线拼接在一起表达。
线性贝塞尔曲线
线性曲线的次数为1,其所需要的控制点为 2 个,假设为 \(P_0,P_1\) \[ \begin{split} P(t) &= \sum_{i=0}^{n}P_iB_{i,n}(t)=P_0 B_{0,1}(t)+P_1 B_{1,1}(t) \\ \therefore P_t &= P_0 \cdot \frac{1!}{0!(1-0)!}t^0(1-t)^{1-0}+ P_1 \cdot \frac{1!}{1!(1-1)!}t^1(1-t)^{1-1} \\ & 又 \because 0! = 1 \\ \therefore P_t &= P_0 \cdot (1-t)+P1\cdot t = P_0+t\cdot(P_1-P_0) \end{split} \]
异形曲线
为了能够表达复杂的异形曲线,我们将多条贝塞尔曲线连接在一起,在连接处保证其几何连续,这样就形成了一条复杂的贝塞尔曲线了。
性质
各项系数之和为1 这个很好理解,因为系数 \(\sum_i^n B_{i,n}(t)\) 是二项式 \((t+(1-t))^n\) 的展开,所以其值始终为 1
对称性 第 \(i\) 项系数和倒数第 \(i\) 项系数(即 \(n-i\) 项)相同
递归性 递归性指其系数满足下式: \[ B{i,n}(t) = (1-t)B_{i,n-1}(t)+tB_{i-1,n-1}(t),i \in [0,1,\cdot\cdot\cdot,n] \]
凸包性质 贝塞尔曲线始终会在包含了所有控制点的最小凸多边形中,不是按照控制点的顺序围成的最小多边形。这点大家一定注意。
这一点的是很关键的,也就是说可以通过控制点的凸包来限制规划曲线的范围,在路径规划是很需要的一个性质。
端点性质 第一个控制点和最后一个控制点,恰好是曲线的起始点和终点。这一点可以套用二项式展开来理解,t=1或者0的时候,相乘二项式的系数,除了初始点或者末尾点,其余的都是0。
一阶导数性质
B样条曲线(B-Spline)
贝塞尔曲线有很多优点,但也有几个不足之处:
(1)一旦确定了特征多边形的顶点数,就决定了曲线的阶数。当数据点的数量太多时,计算量急剧增加。
(2)由于光滑性很高,反而导致拼接比较复杂。
(3)无法做局部修改,这是一个很大的局限性,牵一发而动全身。
1972年,在贝塞尔提出他的方法十年后,Gordon和Riesenfeld等人又提出了B样条方法,在保留了贝塞尔方法的全部优点的同时,克服了以上三大缺点。
B样条曲线有如下性质:
- 可以指定阶次
- 移动控制点仅仅改变曲线的部分形状,而不是整体
定义
b 样条曲线有很多种定义方式,相对简单的表达是 de Boor-Cox 递归公式,其定义如下:
$$ \[\begin{split} P(t) &= \sum_{i=0}^{n}P_i \cdot N_{i,k}(t),t \in [t_{k-1},t_{n+1}] \\ N_{i,1}(t) &= \left\{ \begin{array}{left} 1 \ ,t_i<t<t_{i+1} \\ 0 \ ,Otherwise \end{array} \right. ,注意,N_{i,1}(t) 中的 1 代表阶\\ N_{i,k}(t) &=\frac{t-t_i}{t_{i+k-1}-t_i}\cdot N_{i,k-1}(t)+\frac{t_{i+k}-t}{t_{i+k}-t_{i+1}}\cdot N_{i+1,k-1}(t) \\ & 同时约定: \frac{0}{0} = 0 \end{split}\]$$
理解
参数
\(P(t)\)
曲线上的点
t
隐式方程的参数,与贝塞尔曲线的 t 相同
\(P(i)\)
用户给定的控制点
n
控制点数组中下标的最大值,其值等于控制点的总数减 1
i
每一个控制点的下标
k
代表 b 样条曲线的阶数。
阶数的表达的意义是:
- b 样条必须有 k 个基函数才有意义
- 每个基函数的定义域跨越了 k 个区间
特别注意,上面的表达式中用的是阶,而在有的文章里面,是用次来表示的,阶与次都是同一个概念,只是它们的值不一样,阶(order)=次(degree)+1。
为什么会出现阶和次两种表达方式呢?
在图形学中,有两个很著名的教授,一个叫 G Farin,一个叫 Les Piegl,他们分别是 Computer Aided Geometric Design 和 Computer Aided Design 杂志的主编。这两位主编分别写了一本书,G Farin 叫 k 阶 b 样条曲线,Les Piegl 叫 k 次 b 样条曲线。
这两个概念大家都在用,所以就导致了这种不同名称的定义。
\(N_{i,k}(t)\)
表示第 \(i\) 个 \(k\) 阶(order)B样条基函数。它是由节点向量(knot vector)唯一决定的。
特别注意,上面的分段函数是 \(N_{i,1}(t)\)
通过 \(N_{i,k}(t)\) 的公式,我们可以作如下推导: \[ \begin{split} N_{i,k}(t) &=\frac{t-t_i}{t_{i+k-1}-t_i}\cdot N_{i,k-1}(t)+\frac{t_{i+k}-t}{t_{i+k}-t_{i+1}}\cdot N_{i+1,k-1}(t) \\ &= \frac{t-t_i}{t_{i+(k-1)}-t_i}\cdot N_{i,k-1}(t) + \frac{t_{(i+1)+(k-1)}-t}{t_{(i+1)+(k-1)}-t_{i+1}}\cdot N_{i+1,k-1}(t) \end{split} \] 通过上式,可以知 \(N_{i,k}(t)\) 其实是 \(N_{i,k-1}(t)\) 在区间 \([t_i,t_{i+k-1}]\) 上的插值加上 \(N_{i+1,k-1}(t)\) 在区间 \([t_{i+1},t_{i+1+k-1}]\) 上的插值。
更通俗地讲就是,第 i 个 k 阶基函数是第 i 和 i+1 个 k-1 阶基函数的线性插值。
节点向量
设 T 是 m+ 1 个非递减数的集合,\(t_0 <= t_1 <= t_2<= ... <= t_m\)。\(t_i\)称为节点(knots), 集合 T 称为节点向量(knot vector), 半开区间 \([t_i,t_{i+1}]\) 是第 i 个节点区间(knot span)
节点向量本质就是一组非减的实数序列,一般取 [0,1]。
看到此处,可能会很疑惑,为什么需要定义节点向量,节点向量有什么作用呢?后文将会一一道来。
重复度
在节点向量(节点数组)中,如果某一个节点连续出现 m 次,则称该节点的重复度为 m。
示例
为了方便理解 b样条曲线,我们先计算一些低阶曲线。
第 0 个 1 阶基函数 \(N_{0,1}(i=0,k=1)\)
当 \(t_i<t<t_{i+1}\) 时,即 \(t_i\) 在区间 \([t_0,t1]\) 上时,有:
\[ \begin{equation} N_{0,1}(t) = \left\{ \begin{array}{left} 1 \ ,t_0<t<t_{1} \\ 0 \ ,Otherwise \end{array} \right. \end{equation} \]
第 1 个 1 阶基函数 \(N_{1,1}(i=1,k=1)\) \[ \begin{equation} N_{1,1}(t) = \left\{ \begin{array}{left} 1 \ ,t_1<t<t_{2} \\ 0 \ ,Otherwise \end{array} \right. \end{equation} \]
第 0 个 2 阶基函数 \(N_{0,2}(i=0,k=2)\) \[ \begin{split} N_{0,2}(t) = \frac{t-t_0}{t_1-t_0}\cdot N_{0,1}(t) + \frac{t_2-t}{t_2-t_1}\cdot N_{0,1}(t) \end{split} \]
节点向量的作用
首先抛出一个定义,节点向量是对 \(t\) 定义域的一个划分。
因为节点向量是是分段的,基函数在仅在某些段上有值,所以公式 \(P(t) = \sum_{i=0}^{n}P_i \cdot N_{i,k}(t)\) 中实际参与组合的点并不是全部(实际上只有 k 个,文会详细解释)。
因此,节点区间通过控制基函数是否为 0,来确定计算 b 样条曲线上的点时,采用哪些控制点。
在生成曲线的时候,将 t 从小到大变化,从而得到曲线上的一系列点,它的详细步骤如下:
- 根据 t,确定 t 所在的节点区间 \(T_i\)
- 通过迭代公式,求出每个点在该区间(\(T_i\))上的基函数
- 将每个基函数与对应的控制点相乘取和,得到曲线上实际的点
节点向量的取值
上文讲到节点向量是一组非减实数序列,从插值公式中可以知道,向量中的每个节点大小不会影响结果,影响结果的是两个节点的步长。
因此,节点向量可以是任意实数序列。
那么步长怎么确定呢?
节点向量的步长取值
上面一节讲到,b 样条上每个点只与节点向量的步长有关,因此,根据设置不同的步长,b 样条就会产生不同的效果。
如果节点向量没有任何特别的结构,那么产生的曲线不会与控制折线(polyline)的第一边(leg)和最后一边(leg)接触,如下面图所示。
这种类型的B-样条曲线称为开(open )b 样条曲线。
我们可能想强制曲线使得它分别与第一个控制点和最后一个控制点的第一边和最后一边相切,像贝塞尔曲线那样。为了做到这些,第一个节点和最后一个节点必须是重复度为 \(k(代表阶数)\)。这就产生了所谓的 clamped b 样条曲线。参见下图。
通过重复某些节点和控制点,产生的曲线会是闭(closed)曲线。 这种情况,产生的曲线的开始和结尾连接在一起形成了一个闭环如下图所示。
节点的个数确定
从公式定义中,可以得知,第 i 个 k 阶 b 样条曲线的基函数等于第 i 个 k-1 阶基函数和第 i+1 个 k-1 阶基函数的线性插值。它们的关系可以用下图来表示。
从上图中,我们可以看到,如果要求第 0 个 5 阶 b 样条函数基函数,则需要 5 个 1 阶基函数,需要 6 个节点。由此,可以得到如下结论: \[ 结点数量(KnotsCount) = 控制点数量(PointCount)+阶数k(order) \]
有效定义区间
上面在解释 k 这个符号的时候,提到了 k 阶的概念。
一个 k 阶 b 样条,它必须有 k 个基函数才有意义,所以,一个 b 样条曲线的有效定义区间必须包含 k 个 基函数定义。
从公式 \[ \begin{split} P(t) = \sum_{i=0}^{n}P_i \cdot N_{i,k}(t),t \in [t_{k-1},t_{n+1}] \end{split} \] 可以看出,曲线上的点是通过每个点乘以其基函数然后进行相加,从3.6节的计算图中我们可以看到,每个点的基函数的计算仅使用了有限个区间,比如 \(N_{0,2}(t)\) 使用的区间为 \([t_0,t_2)\)。
因此,我们可以将一个高阶基函数用 1 阶基函数来表示: \[ \begin{split} N_{i,k}(t) &= \sum_{i}^{i+k-1}C_i(t) \cdot N_{i,1}(t), \ t \in [t_i,t_{i+k}) \\ C_{i}(t) &-一阶基函数系数 \end{split} \]
从上式可以看出,k 阶基函数跨越了 \((i+k)-i = k\) 个区间。
假设一个 4 阶 b 样条有 5 个控制点,其基函数的区间可以用下图来表示:
从图中我们发现,仅在 \([t_3,t_5]\) 区间上存在 4 个基函数,所以仅在该区间上,b 样条曲线才有定义。
推而广之,我们就得到,一个有 (n+1) 个控制点的 k 阶 b 样条曲线的有效定义区间为 \([t_{k-1},t_{n+1}]\)。
b 样条本质
b 样条曲线的本质是由多个 k-1 次多项式组合而成,这些分段曲线之间 k-2 次连续。
假设一个 4 阶 b 样条有 5 个控制点,任意点公式可以写成: \[ \begin{split} P(t) = N_{0,k}(t)P_0+N_{1,k}(t)P_1+N_{2,k}(t)P_2+N_{3,k}(t)P_3+N_{4,k}(t)P_4 \end{split} \] 由于是 4 阶 5 点,所以有 9 个节点,8 个节点区间,因此可以画出基函数的有效区间图如下:
所以,可以得到下列分段函数
区间序号 | 定义域 | 公式 | 有效性 |
---|---|---|---|
1 | \([t_0,t_1)\) | \(P(t) = N_{0,k}(t)P_0\) | 无效 |
2 | \([t_1,t_2)\) | \(P(t) = N_{0,k}(t)P_0+N_{1,k}(t)P_1\) | 无效 |
3 | \([t_2,t_3)\) | \(P(t) = N_{0,k}(t)P_0+N_{1,k}(t)P_1+N_{2,k}(t)P_2\) | 无效 |
4 | \([t_3,t_4)\) | \(P(t) = N_{0,k}(t)P_0+N_{1,k}(t)P_1+N_{2,k}(t)P_2+N_{3,k}(t)P_3\) | 有效 |
5 | \([t_4,t_5)\) | \(P(t) = N_{1,k}(t)P_1+N_{2,k}(t)P_2+N_{3,k}(t)P_3+N_{4,k}(t)P_4\) | 有效 |
6 | \([t_5,t_6)\) | \(P(t) = N_{3,k}(t)P_3+N_{4,k}(t)P_4\) | 无效 |
7 | \([t_6,t_7)\) | \(P(t) = N_{3,k}(t)P_3+N_{4,k}(t)P_4\) | 无效 |
8 | \([t_7,t_8)\) | \(P(t) = N_{4,k}(t)P_4\) | 无效 |
从表中可以看出,5个控制点的 4 阶 b样条曲线仅在第 4 和 5 个节点区间上生成曲线。
性质
非负性
\(N_{i,k}(t)\) 是非负的
局部支持性
- 区间 \([t_i,t_i+1]\) 上的曲线仅至多由 k 个控制
\(P_j,j \in [i-k+1,...,i]\) 决定
\(P_i\) 只影响在区间 \([t_i,t_i+k)\) 上的曲线。
归一性
区间 \([t_{k-1},t_{n+1}]\) 上的所有 k 阶分段非零基函数的和为 1 \[ \sum_i^n N_{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}\cdot N_{i,k-1}(t)+\frac{k-1}{t_{i+k}-t_{i+1}} \cdot N_{i+1,k-1}(t) \] 为什么分子是 k-1 呢?
因为 k 阶基函数是一个 k-1 次函数,在对其求导的时,其次数作为导数的系数,所以是 k-1
连续性
\(P(t)\) 在每一个重复度为 r 的节点上具有 \(C^{k-1+r}\) 的连续性
\(C^{k-1+r}\) 表示具有 \(k-1+r\) 次(degree)连续。C 是 Continue 的首字母。
凸包性
一个 b 样条曲线被包围在其控制顶点的凸包内部。更精确地,对区间 $[t_i,t_{i+1}],k-1 i n $ 上的任何 t,\(P(t)\) 都在控制点 \(P_{i-k+1},...,P_i\) 的凸包内部。
分段多项式性质
在任何一个由相邻结点确定的节点区间(knot span)上,\(P(t)\) 是一个关于 t 的次数不超过 k 的多项式。
变差缩减性(Variation Diminishing Property)
任何曲一条直线与 B 样条曲线的交点数量不会超过该直线与 B 样条曲线的控制多边形的交点的数量。
几何不变性
曲线的形状和相对于控制点的位置不取决于坐标系的选择。
仿射不变性
将仿射变换作用于等式两边,等式依然成立 \[ A[P(t)]= \sum_i^nA[P_i]N_{i,k}(t),t \in [t_{k-1},t_{n+1}] \]
直线保持性
如果控制多边形退货成为一条直线,那么 B 样条曲线依然在这条直线上。
分类
根据起起终点是否重合,可分为:
开曲线
起终点不重合的曲线
闭曲线
起终点重合的曲线
根据节点向量的分布,又可为分为:
- 均匀 b 样条曲线
- 非均匀 b 样条曲线
- 分段 Bezier 曲线
- 非均匀无理 b 样条曲线
均匀(uniform) b 样条曲线
当节点成等差数列均匀排列时,这样形成的 b 样条曲线就叫均匀 b 样条曲线。
例如:\(\vec{T} = [0,1,2,3,4,5,6,7]\)
均匀 b 样条曲线有一个非常重要的特点,先上图:
均匀 b 样条曲线的起点位于 B 点垂直于AC两个点连线的 1/3 处,方向为 \(\vec{AC}\),终点位于 D 点垂直于 CE 两个点连线的 1/3,方向为 \(\vec{CE}\)。
均匀 b 样条的一个特点是:
均匀 b 样条曲线一定通过非端点垂直于它前后两个点连线的 1/3 处,且其方向与前后两个点的连线相切。
准均匀(quasi-uniform) b 样条曲线
k 阶准均匀 b 样条曲线有以下特点:
- 它的起终点分别为控制点的起终点
- 起始节点与终止节点都有 k 个重复度
小提示:
如果想让 b 样条曲线经过起终点,可以让起始节点都具有 k 个重复度
分段 Bezier 曲线
当 b 样条曲线具有如下特点时,它就是分段 Bezier 曲线:
- 起终节点具有 k 个重复度
- 所有其它节点具有 k-1 个重复度
曲线包含线段
如果需要在样条曲线中包含一条线段,只需要指定 k(阶数) 个控制顶点共线。
如果要保证插入的直线在控制点范围内是一条直线,还必须保证线段的首尾点分别具有 1 个重复度。
左图是仅 3 个点共线,右图是 3 个点共线且共线的首尾点重复 1 次。
曲线经过控制点
通过均匀 b 样条的特点可以知,如果 3 个点相同(这种重复3次的点,叫做 3 重点),则曲线经过该点。
因为 3 个点相同,所以它们的连线与垂线都位于这个点上。
曲线与某直线L相切
如果希望某段曲线与某直线 L 相切,需满足以下条件:
- \(P_i,P_{i+1},P_{i+2}\) 都在直线上
- \(t_{i+3}\) 重复度小于 2
因此,如果想要曲线与两个控制点的连线相切,可以通过添加一个相同的控制点,将两个点变成 3 个点,因为有一个点是重复的,所以 3 个点必然在一条直线上,这样就达到了曲线与直线相切的条件了。
闭曲线
构件闭曲线的方式有很多种,此处只介绍一种简单的方法:重复起始节点法。
假设我们想要构建一个由 n+1 个控制点 \([P_0,P1,...,P_n]\) 定义的 k 次闭 B 样条曲线 \(C_t\)。构建过程如下:
- 增加一个新控制点 \(P_{n+1}=P_0\),因此控制点的数目是 \(n+2\)。
- 按开曲线方式,增加 n+k+1 个节点 \([t_0,t_1,...,t_{n+k}]\)。这些节点可以不需要是均匀的。
- 将前 p-1 节点复制到节点序列末尾,最终结果为:\(t_0,t_1,...,t_n+k,t_0,t_1,...,t_{k-1}]\)
通过对比开闭曲线,我们可以得到如下规律:
开曲线:节点数量=控制点数量+阶数
闭曲线:节点数量=控制点数量+2x阶数
小提示:在 Microstation 软件中,生成闭曲线时不需要在末尾增加第一个点
非均匀有理B样条曲线(NURBS)
Order(阶数)
NURBS曲线的 order 定义了影响曲线上任何给定点附近的控制点的数量。
这条曲线用比 order 小 1 次的多项式表示。 因此,order 为 2 时表示线性曲线,order 为 3 时表示二次曲线。
控制点的个数必须大于或等于曲线的 order。
在实践中,三次曲线是最常用的曲线。 五阶和六阶曲线有时是有用的,特别是对于获得连续的高阶导数,但高阶曲线实际上从未使用过,因为它们会导致内部数值问题,往往需要大量的计算时间。
Control Point 与 Knot
这两个概念与 b 样条的概念是一样的
Weight
nurbs 还有一个特殊的参数权重(weight),权重范围是 [0,100],正常权重是 1,值越大,控制点对曲线影响越在,越靠近点,值为 0 值,控制点对曲线没有影响,相当于没有这个控制点。
Bézier、B-Spline、NURBS 区别
Bezier 曲线中的每个控制点都会影响整个曲线的形状,而B样条中的控制点只会影响整个曲线的一部分,显然 B样条提供了更多的灵活性
Bezier和B样条都是多项式参数曲线,不能表示一些基本的曲线,比如圆,所以引入了 NURBS,即非均匀有理B样条来解决这个问题
Bezier 曲线只是 B样条的一个特例而已,而 B样条又是 NURBS 的一个特例,它们的关系可以图示为:
MSBsplineCurve(Microstation中的对象)
它是一条非均匀有理B样条曲线,简称(NURBS)。
MSBsplineCurve is a "Non uniform, rational Bspline curve".
Pole and knot counts
曲线类型 | 关系 |
---|---|
Open curve (非闭合曲线) | knots = poles + order |
Closed (periodc) curve (闭合线) | knots = poles + 2 * order - 1 |
B样条曲线上的参数化位置
有两种方法来确定 B 样条曲线的位置,分别是通过 Fraction 和 Knot 点。
Convention | start value | end value | remarks |
---|---|---|---|
Fraction position | 一直是 0.0 | 一直是 1.0 | 这个值不是沿曲线线性变化的。如果想要获取等分点,需要先通过FractionAtSignedDistance
获取 Fraction,然后再通过 Fraction 去获取点。 |
Knot postion | 第一个激活的 Knot | 最后一个激活的 Knot | “激活”的意思是除去(order-1)开头和结尾的Knot后剩余的中间 Knot |
The word Fraction or Knot in a method name indicates how the arguments for that method are interpreted.
通过控制点的 b 样条曲线
Microstation 中可以通过控制点创建 b 样条曲线,这个实现目前没有找到相关资料,今后发现了之后再更新本节。
源代码
本文使用的一些代码示例(基于 Microstation 平台)位于ArticleSourceCode-Bspline 中。
参考
计算机图形学 13 和 14 - B 样条曲线-bilibili (建议先看完)