CS3621 密歇根理工大学计算机几何学入门课程笔记-下

[TOC]
密歇根理工大学计算机几何学入门课程笔记第二部分, 主要介绍贝塞尔曲线, B 样条曲线的由来/定义/性质/计算等相关内容以及插值/拟合的应用.

Dr. C.-K. Shene
Department of Computer Science
Michigan Technological University

Unit 5: Bézier Curves

Chapter 1. An Introduction

用户对曲线设计的要求

• Intuitive 可读性:
  We expect that every step and every algorithm will have an intuitive and geometric interpretation.
• Flexible 易控性:
  The system should provide the users with more control for designing and editing the shape of a curve. The way of creating and editing a curve should be easy, intuitive and geometric rather than by manipulating equations.
• Unified Approach 描述统一性:
  The way of representing, creating and editing different types of curves (e.g., lines, conic sections and cubic curves) must be the same. That is, it does not require different techniques for manipulating different curves (i.e., conics and cubics).
• Invariant 平移/旋转/仿射不变性:
  The represented curve will not change its geometry under geometric transformations such as translation, rotation and affine transformations.
• Efficiency and Numerically Stability 经济性:
  A user of a curve design system may not care about the beauty of the underlying geometry; but, he/she expects the system to deliver the curve he/she wants fast and accurately. Moreover, a large amount of computations will not "distort" the shape of the curve (i.e., numerical stability).

Bézier curves 等 Spline 曲线优点

• 用控制点看出整体趋势
  A user layouts a set of control points for the system to come up with a curve that more or less follows the trend of the set of control points.
• 不需要公式, 移动控制点/操纵一些参数
  A user can change the positions of some control points and some other characteristics for modifying the shape of the curve. No equation is required, because the equation of a curve is usually not stored.
• 可以在不改变原有曲线的基础上添加控制点
  If necessary, a user can add control points and other vital information without changing the shape of the curve. In this way, a user has more freedom of editing a curve because adding control points and other information increases the degree of freedom of the curve.
• 可切割
  A user can even break a curve into two pieces for "micro" editing and then join them back into one piece.
• 数值计算上稳定
  There are very geometric, intuitive and numerically stable algorithms for finding points on the curve without knowing the equation of the curve.
• 方便计算曲面
  Once you know curves, the surface counterpart is a few steps away. More precisely, the transition from curve to surface will not cause much difficulty, since what you learn for curves applies directly to surfaces.

分为 polynomial parametric forms 以及 rational parametric form. Rational Bézier curves and Non-Uniform Rational B-splines 可以表达封闭曲线. 所有贝塞尔-样条曲线的关系如下:

Chapter 2. Construction of Bézier Curves 构造

数学描述

control points：$n+1$ points $P_0, P_1, P_2, … P_n$ in space.
Bézier basis functions or Bernstein polynomials:

$$
\mathbf{C}(u)=\sum_{i=0}^{n} B_{n, i}(u) P_{i}
$$

各项系数:

$$
B_{n, i}(u)=\frac{n !}{i !(n-i) !} u^{i}(1-u)^{n-i}
$$

重要特性

1. $n+1$ 个控制点曲线阶数为 $n$.
   The degree of a Bézier curve defined by $n+1$ control points is $n$.
2. 曲线过起终点.
   $C(u)$ passes through $P_0$ and $P_n$.
3. Non-negativity 所有项非负
4. Partition of Unity 所有项和为 1, 因此可以理解贝塞尔曲线求解表达式如下:
   to compute $C(u)$, one takes the weight $B_{n,i}(u)$ for control point $P_i$ and sum them together.
5. Convex Hull Property 曲线一定是在所有控制外轮廓以内为凸
   
6. Variation Diminishing Property 略过.
   
7. Affine Invariance 仿射不变性

自变量定义域线性变换

$u \in [a,b] $ 转换成 $[0,1]$.

$$
\underline{u}=\frac{u-a}{b-a}
$$

Chapter 3. Moving Control Points 更改

移动一个控制点会改变整个曲线形状.
$P_k$ 点移动矢量 $\textbf{v}$: $P_0, P_1. …, P_{k+\textbf{v}}, …, P_n$
曲线方程变为:

$$
\begin{aligned}
\mathbf{D}(u) &=\sum_{i=0}^{k-1} B_{n, i}(u) P_{i}+B_{n, k}(u)\left(P_{k}+\mathbf{v}\right)+\sum_{i=k+1}^{n} B_{n, i}(u) P_{i} \
&=\sum_{i=0}^{n} B_{n, i}(u) P_{i}+B_{n, k}(u) \mathbf{v} \
&=\mathbf{C}(u)+B_{n, k}(u) \mathbf{v}
\end{aligned}
$$

示意图:

Chapter 4. De Casteljau’s Algorithm: Finding a Point on a Bézier Curve 求解

本质上是一个动态规划算法.
需要求解 $n$ 阶下 $u$ 对应值, 求解 $n-1$ 阶下 $u$ 与 $1-u$ 对应值.
伪代码(低效版, 未加查找表)如下:

Input: array P[0:n] of n+1 points and real number u in [0,1]
Output: point on curve, C(u)
Working: point array Q[0:n]

for i := 0 to n do
    Q[i] := P[i]; // save input
for k := 1 to n do
    for i := 0 to n - k do
        Q[i] := (1 - u)Q[i] + u Q[i + 1];
return Q[0];

或者是采用递归的形式

function deCasteljau(i,j)
begin
    if i = 0 then
        return P0,j
    else
        return (1-u)* deCasteljau(i-1,j) + u* deCasteljau(i-1,j+1)
end

计算示意图:

Chapter 5. Derivatives of a Bézier Curve 求导

1 阶求导过程

$$
\begin{aligned}
&\frac{\mathrm{d}}{\mathrm{d} u} B_{n, i}(u)=B_{n, i}^{\prime}(u)=n\left(B_{n-1, i-1}(u)-B_{n-1, i}(u)\right) \
&\frac{\mathrm{d}}{\mathrm{d} u} \mathbf{C}(u)=\mathbf{C}^{\prime}(u)=\sum_{i=0}^{n-1} B_{n-1, i}(u)\left{n\left(P_{i+1}-P_{i}\right)\right} \
&\mathbf{C}^{\prime}(u)=\sum_{i=0}^{n-1} B_{n-1, i}(u) \mathbf{Q}_{i}
\end{aligned}
$$

hodograph: $n(P_n - P_{n-1})$

$$
\begin{aligned}
\mathbf{C}^{\prime}(u) &=\sum_{i=0}^{n-1} B_{n-1, i}(u)\left{n\left(P_{i+1}-P_{i}\right)\right} \
&=n\left[\left(\sum_{i=0}^{n-1} B_{n, i}(u) P_{i+1}\right)-\left(\sum_{i=0}^{n-1} B_{n, i}(u) P_{i}\right)\right]
\end{aligned}
$$

$$
\mathbf{C}^{\prime}(u)=n\left(\mathbf{C}{1}(u)-\mathbf{C}{2}(u)\right)
$$

由此可见 1 阶导是 $n-1$ 阶的两个贝塞尔曲线之差.
当 $u=0,u=1$ 时即始终点 $ C’(0) = n (P_1 - P_0) \quad C’(1) = n (P_n - P_{n-1})$, 可以看出第一个与最后一个控制点处的 polyline leg 为贝塞尔曲线的切线.

连续性

两条贝塞尔曲线连接
$C(u):m + 1$ control points $P_0, P_1, P_2, …, P_m$
$D(u):n + 1$ control points $Q_0, Q_1, Q_2, …, Q_n$

• $C^0$连续
  $P_m=Q_0$
• $G^1$连续
  $P_{m-1},P_m(Q_0),Q_1$共线
• $C^1$连续

$$
\mathbf{C}^{\prime}(1)=m\left(\mathbf{P}{m}-\mathbf{P}{m-1}\right)=\mathbf{D}^{\prime}(0)=n\left(\mathbf{Q}{1}-\mathbf{Q}{0}\right)
$$

例如 $ P_1 - P_0 = P_n - P_{n-1} $

$k$ 阶导

$$
\begin{aligned}
\mathbf{C}^{[k]}(u) &=n(n-1)(n-2) \cdots(n-k+1) \sum_{i=0}^{n-k} B_{n-k, i}(u)\left(\mathbf{D}{i+1}^{k-1}-\mathbf{D}{i}^{k-1}\right) \
&=n(n-1)(n-2) \cdots(n-k+1) \sum_{i=0}^{n-k} B_{n-k, i}(u) \mathbf{D}_{i}^{k}
\end{aligned}
$$

Chapter 6. Subdividing a Bézier Curve 分割

分割贝塞尔曲线: 在 $u$ 处, 分割为两条仍为 $n$ 阶的贝塞尔曲线, 整体形状不变. 求分割后的两条贝塞尔曲线控制点.

观察三角算法可以看出用上三角边与下三角边都可以求出最终的表达式, 两条边上的点即为分割后的控制点. 示意图如下:

Chapter 7. Degree Elevation of a Bézier Curve 拼接

实际应用: 连接高低阶贝塞尔曲线时, 需要在不改变低阶形状的前提下增加控制点提高其阶数.
Suppose we have a Bézier curve of degree $n$ defined by $n + 1$ control points $P_0, P_1, P_2, …, P_n$, 增加到 $n + 2$ control points $Q_0, Q_1, Q_2, …, Q_{n+1}$.
始终点必须保持不变: $Q_0 = P_0 \quad Q_{n+1} = P_n$
可得新控制点的求解公式, 即 $Q_i$ divides the segment $P_{i-1}P_i$ in a ratio of $1 - i/(n+1):i/(n+1)$. 几何上看 corner-cutting effect, 切割掉低阶的 polyline leg 的角.

$$
\mathbf{Q}{i}=\frac{i}{n+1} \mathbf{P}{i-1}+\left(1-\frac{i}{n+1}\right) \mathbf{P}_{i} \quad 1 \leq i \leq n
$$

Unit 6: B-spline Curves

Chapter 1. Motivation

贝塞尔曲线的缺陷, 调整形状->增加控制点->增加阶数, 增加复杂度, 同时动 1 个控制点整个曲线随之变化.
调整思路用低阶贝塞尔曲线拼接->低阶曲线分割为多段贝塞尔曲线->B 样条曲线, 以切割自变量 $u$ 为 knots 来构造多段曲线实现连续性.
knots 控制曲线示意图:

Chapter 2. B-spline Basis Functions

Definition

knots: a set of $m + 1$ non-decreasing numbers, $u_0 <= u_1 <= u_2 <= … <= u_m$.
knot vector: $\textbf{U}$.
$i$-th knot span: half-open interval $[u_i, u_{i+1})$, some knot spans may not exist.
$u_i$ is a multiple knot of multiplicity $k$: $u_i(k)$.
simple knot: not a multiple knot.
uniform(non-uniform): knots are equally spaced.
degree: $p$
满足公式: $m = n + p + 1$
B-spline basis functions: Cox-de Boor recursion formula

$$
\begin{aligned}
&N_{i, 0}(u)= \begin{cases}1 & \text { if } u_{i} \leq u<u_{i+1} \
0 & \text { otherwise }\end{cases} \
&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)
\end{aligned}
$$

求解示意图(依旧是动态规划思想, 基公式已经是动态规划的表达式了):

knot 作用域

由于 $p=0$ 的 step function 决定了不同 knot span 与不同 $p$ 的不同节点的作用域关系.
正向:
Basis function $N_{i,p}(u)$ is non-zero on $[u_i, u_{i+p+1})$. Or, equivalently, $N_{i,p}(u)$ is non-zero on $p+1$ knot spans $[u_i, u_{i+1}), [u_{i+1}, u_{i+2}), …, [u_{i+p}, u_{i+p+1})$.
如图 $p=3$:

逆向:
On any knot span $[u_i, u_{i+1})$, at most $p+1$ degree $p$ basis functions are non-zero, namely: $N_{i-p,p}(u), N_{i-p+1,p}(u), N_{i-p+2,p}(u), …, N_{i-1,p}(u)$ and $N_{i,p}(u)$
如图:

Meaning of the Coefficients?

上述的作用域影响只是 0-1 式的, 具体到影响大小的话, 用在 knot span 中的线性长度占比来描述.

具体地: If $u$ is in this interval, then $u_{i+p+1} - u$ is the distance from $u$ to the right end of this interval, $u_{i+p+1} - u_{i+1}$ is the length of the interval, and $(u_{i+p+1} - u) / (u_{i+p+1} - u_{i+1})$ is the ratio of these two distances and its value is in the range of 0 and 1. Therefore, $N_{i,p}(u)$ is a linear combination of $N_{i,p-1}(u)$ and $N_{i+1,p-1}(u)$ with two coefficients, both linear in $u$, in the range of 0 and 1.

Important Properties

1. 多项式描述
   $N_{i,p}(u)$ is a degree $p$ polynomial in $u$.
2. 非负性
   For all $i$, $p$ and $u$, $N_{i,p}(u)$ is non-negative
3. Local Support
   上述正向性质
4. 作用域
   上述逆向性质
5. 合一性(自造词)
   Partition of Unity – The sum of all non-zero degree $p$ basis functions on span $[u_i, u_{i+1})$ is 1:
6. 满足 $m = n + p + 1$
7. 在 knot 处连续的多段多项式曲线
8. 重复 knot 处的连续性
   At a knot of multiplicity $k$, basis function $N_{i,p}(u)$ is $C^{p-k}$ continuous.

The Impact of Multiple Knots

1. Each knot of multiplicity $k$ reduces at most $k-1$ basis functions’ non-zero domain. —> 影响作用域
2. At each internal knot of multiplicity $k$, the number of non-zero basis functions is at most $p - k + 1$, where $p$ is the degree of the basis functions.

Chapter 3. B-spline Curves

定义:
Given $n + 1$ control points $P_0, P_1, …, P_n$ and a knot vector $\textbf{U} = { u_0, u_1, …, u_m }$, the B-spline curve of degree $p$ defined by these control points and knot vector $\textbf{U}$ is

$$
\mathbf{C}(u)=\sum_{i=0}^{n} N_{i, p}(u) \mathbf{P}_{i}
$$

clamped B-spline curves: tangent to the first and the last legs at the first and last control points.
close B-spline curves(open B-spline curves): a closed loop.

Wrapping Knots 封闭图形

制造封闭的 B 样条曲线过程：

1. Add a new control point $P_{n+1} = P_0$. Therefore, the number of control points is $n+2$.
2. Find an appropriate knot sequence of $n+1$ knots $u_0, u_1, …, u_n$. These knots are not necessarily uniform.
3. Add $p+2$ knots and wrap around the first $p+2$ knots: $u_{n+1} = u_0, u_{n+2} = u_1, …, u_{n+p} = u_{p-1}, u_{n+p+1} = u_p, u_{n+p+2} = u_{p+1}$ as shown in the following diagram. In this way, we have $n+p+2 = (n+1) + p + 1$ knots.
4. The open B-spline curve $C(u)$ of degree p defined on the above constructed $n+1$ control points and $n+p+2$ knots is a closed curve with $C^{p-1}$ continuity at the joining point $C(u_0) = C(u_{n+1})$. Note that the domain of this closed curve is $[u_0, u_{n+1}]$.
   

Important Properties

1. B-spline curve $C(u)$ is a piecewise curve with each component a curve of degree $p$.
   每个 knot span 都是 degree 为 $p$ 的多项式曲线, 因此可以用较低的次数拟合复杂的曲线. 通常多项式次数越低拟合效果越好, 如下图, 次数从 7->5->3.

   

2. Equality $m = n + p + 1$ must be satisfied.

3. Clamped B-spline curve $C(u)$ passes through the two end control points $P_0$ and $P_n$. 经过始终点.

4. Strong Convex Hull Property: A B-spline curve is contained in the convex hull of its control polyline. More specifically, if $u$ is in knot span $[u_i,u_{i+1})$, then $C(u)$ is in the convex hull of control points $P_{i-p}, P_{i-p+1}, …, P_i$.

5. Local Modification Scheme: changing the position of control point $P_i$ only affects the curve $C(u)$ on interval $[u_i, u_{i+p+1}$). Moreover, if fine-tuning curve shape is required, one can insert more knots (and therefore more control points) so that the affected area could be restricted to a very narrow region. 修改一部分控制点不会影响所有段曲线, 并且可以通过增加控制点影响部分曲线形状.

6. $C(u)$ is $C^{p-k}$ continuous at a knot of multiplicity $k$.

7. Variation Diminishing Property: If the curve is in a plane (resp., space), this means no straight line (resp., plane) intersects a B-spline curve more times than it intersects the curve’s control polyline.

8. Bézier Curves Are Special Cases of B-spline Curves.
   If $n = p$ (i.e., the degree of a B-spline curve is equal to $n$, the number of control points minus 1), and there are $2(p + 1) = 2(n + 1)$ knots with $p + 1$ of them clamped at each end, this B-spline curve reduces to a Bézier curve.

9. Affine Invariance: once the transformed control points are obtained the transformed B-spline curve is the one defined by these new points. Therefore, we do not have to transform the curve. 仿射不变性

Computing the Coefficients

如果按照定义方程直接计算系数, 许多中间量会被计算多次, 改进的算法如下(主要的思想是不计算那些为 0 的项)：

Moving Control Points 更改

移动某一控制点, 在其影响范围内的曲线会向点位移的方向位移, 位移量依照点而定.
Let control point $P_i$ be moved to a new position $P_i + \textbf{v}$.

$$
\begin{aligned}
\mathbf{D}(u) &=\sum_{k=0}^{i-1} N_{k, p}(u) \mathbf{P}{k}+N{i, p}(u)\left(\mathbf{P}{i}+\mathbf{v}\right)+\sum{k=i+1}^{n} N_{k, p}(u) \mathbf{P}{k} \
&=\sum{k=0}^{n} N_{k, p}(u) \mathbf{P}{k}+N{i, p}(u) \mathbf{v} \
&=\mathbf{C}(u)+N_{i, p}(u) \mathbf{v}
\end{aligned}
$$

Some Useful Consequences from the Strong Convex Hull Property

1. Force a curve segment to become a line segment: let $p+1$ adjacent control points be collinear.—>制作B样条曲线中直线部分的方法.
   
2. Force a B-spline curve to pass a control point: let $p$ adjacent control points be identical.
3. Force a B-spline curve to be tangent to a leg of control polyline: let $P_{i-p}, P_{i-p+1} = P_{i-p+2} = …. = P_{i-1} = P_i$ and $P_{i+1}$ be collinear.
   

Modifying Knots

Modifying the shape of B-spline curve by changing knots is usually unsatisfactory and difficult to achieve the desired goal.

Derivatives of a B-spline Curve

Derivative of a B-spline curve is another B-spline curve of degree $p - 1$ on the original knot vector with a new set of $n$ control points $Q_0, Q_1, …, Q_{n-1}$. Remove the first and the last knots, $N_{i+1,p-1}(u)$ evaluated on the original knot sequence is equal to $N_{i,p-1}(u)$ on the new one.

$$
\begin{aligned}
&\mathbf{Q}{i}=\frac{p}{u{i+p+1}-u_{i+1}}\left(\mathbf{P}{i+1}-\mathbf{P}{i}\right) \
&\frac{\mathrm{d}}{\mathrm{d} u} \mathbf{C}(u)=\mathbf{C}^{\prime}(u)=\sum_{i=0}^{n-1} N_{i, p-1}(u) \mathbf{Q}_{i}
\end{aligned}
$$

Chapter 4. Important Algorithms for B-spline Curves(Knot Insertion) 插点

The meaning of knot insertion is adding a new knot into the existing knot vector without changing the shape of the curve. 插点可以不改变形状.

Inserting a Single Knot

计算思路是把要插入的节点找到在节点向量中的位置, 改变作用域内所有的原节点, 作用域外的节点保持不变即可. 改变的方程如下:

$$
\begin{aligned}
&\mathbf{Q}{i}=\left(1-a{i}\right) \mathbf{P}{i-1}+a{i} \mathbf{P}{i} \
&a{i}=\frac{t-u_{i}}{u_{i+p}-u_{i}} \quad \text { for } k-p+1 \leq i \leq k
\end{aligned}
$$

详细解释:
To insert a new knot $t$, we first find the knot span $[u_k, u_{k+1})$ that contains $t$. With $k$ available, $p$ new control points $Q_{k-p+1}, …, Q_k$ are computed with the above formula. Finally, the original control polyline between $P_{k-p}$ and $P_k $is replaced with the new polyline defined by $P_{k-p}, Q_{k-p+1}, Q_{k-p+2}, …, Q_{k-1}, Q_k$ and $P_k$. Note that after inserting a new knot, the knot vector becomes $u_0, u_1, …, u_k, t, u_{k+1}, …, u_m$.
图解

Inserting a Knot Multiple Times

公式:
If a new knot $t$ is inserted to knot span $[u_k, u_{k+1})$ $h$ times, the coefficients $a_i,h$ can be computed as follows:

$$
a_{i, h}=\frac{t-u_{i}}{u_{i+p-(h-1)}-u_{i}}
$$

图解:

if $t$ is inserted $h$ times at a knots $u_k$ of multiplicity $s$, where $s = 0$ means $t$ is inserted in the middle of that knot span and $s > 0$ means $t$ is inserted at a knot $u_k$ of multiplicity $s$, one can

1. write down the first set of $p+1$ affected control points as the 0-th column;
   ignore the last s control points (i.e., $P_{k-s+1} $to $P_k$);
2. compute the first column, the second column, … and the $h_{th}$ column;
3. the new set of control points are those surrounded by the blue polygon

伪代码:

De Boor’s Algorithm

利用了上面插入同一个节点多次的原理:

if a knot $u$ is inserted repeatedly so that its multiplicity is $p$, the last generated new control point is the point on the curve that corresponds to $u$.

为什么?

After inserting $u$ multiple times, making its multiplicity $p$, the triangular computation scheme yields one point. Because the given B-spline curve must pass this new point, it is the point on the curve corresponding to $u$.

伪代码:

De Casteljau’s 是 de Boor’s Algorithms 的特例.

Subdividing a B-spline Curve

切割 B 样条曲线在 $u$ 处, 前后两段插入控制点实现每段的 $p,n$ 与切割前一致. 参考 $u$ 处插入节点过程, 图解过程如下:

这里需要注意的一点是, 理论上在 $u$ 处切割直观上理解就是现在 $u$ 处插入节点, 然后向前/向后在作用域范围内插入必要的控制点.
但讲义强调 Note that this order is important!!!, 先判断作用域范围, 然后从作用域范围外向 $u$ 处求解.

Subdividing a B-spline Curve into Bézier Curve Segments

只需要把切割的 $u$ 选为 konts 上的 $u$ 值即可. Why?

Since the given B-spline curve is subdivided at its knots, each curve segment has no internal knots.
Moreover, the subdivision process makes the internal knots to have multiplicity $p+1$, and the curve segment is “clamped” at the first and last control points of each curve segment.

但是不要切割成贝塞尔曲线比较好. 原因是切割为 B 样条曲线依旧可以在切割点处维持 $C^{p-k}$ 连续性, 切割成贝塞尔曲线就需要花功夫维持了.

Unit 7: NURBS Curves 非均匀有理 B 样条曲线

Chapter 1. Motivation and Definition

解决 polynomial B Spilne 无法描述圆等封闭曲线的问题.

描述公式:
齐次坐标系下

$$
\mathbf{C}^{w}(u)=\sum_{i=0}^{n} N_{i, p}(u) \mathbf{P}{i}^{w}=\sum{i=0}^{n} N_{i, p}(u)\left[\begin{array}{c}
w_{i} x_{i} \
w_{i} y_{i} \
w_{i} z_{i} \
w_{i}
\end{array}\right]=\left[\begin{array}{c}
\sum_{i=0}^{n} N_{i, p}(u)\left(w_{i} x_{i}\right) \
\sum_{i=0}^{n} N_{i, p}(u)\left(w_{i} y_{i}\right) \
\sum_{i=0}^{n} N_{i, p}(u)\left(w_{i} z_{i}\right) \
\sum_{i=0}^{n} N_{i, p}(u) w_{i}
\end{array}\right]
$$

第四维转换为 1

$$
\mathbf{C}(u)=\left[\begin{array}{c}
\frac{\sum_{i=0}^{n} N_{i, p}(u)\left(w_{i} x_{i}\right)}{\sum_{i=0}^{n} N_{i, p}(u) w_{i}} \
\frac{\sum_{i=0}^{n} N_{i, p}(u)\left(w_{i} y_{i}\right)}{\sum_{i=0}^{n} N_{i, p}(u) w_{i}} \
\frac{\sum_{i=0}^{n} N_{i, p}(u)\left(w_{i} z_{i}\right)}{\sum_{i=0}^{n} N_{i, p}(u) w_{i}} \
1
\end{array}\right]=\sum_{i=0}^{n} \frac{N_{i, p}(u) w_{i}}{\sum_{j=0}^{n} N_{j, p}(u) w_{j}}\left[\begin{array}{c}
x_{i} \
y_{i} \
z_{i} \
1
\end{array}\right]
$$

重新转换为笛卡尔坐标系下

$$
\mathbf{C}(u)=\frac{1}{\sum_{i=0}^{n} N_{i, p}(u) w_{i}} \sum_{i=0}^{n} N_{i, p}(u) w_{i} \mathbf{P}_{i}
$$

定义:
NURBS curve of degree $p$ defined by control points $P_0, P_1, …, P_n$, knot vector $\textbf{U} = { u_0, u_1, …, u_m }$, and weights $w_0, w_1, .., w_n$

$$
\mathrm{C}(u)=\sum_{i=0}^{n} R_{i, p}(u) \mathbf{P}{i} \quad R{i, p}(u)=\frac{N_{i, p}(u) w_{i}}{\sum_{j=0}^{n} N_{j, p}(u) w_{j}}
$$

观察定义容易推出:

1. If all weights are equal to 1, a NURBS curve reduces to a B-spline curve.
2. NURBS Curves are Rational. 分子分母均为 $p$ 阶多项式.

关于 $w$, 一般为正, 为 0 时代表 disabled 的 knot 影响 infinite control points 形式的插值, 为负讲义未具体讲.

Non-Uniform Rational B-Splines: generalize B-splines to rational curves using homogeneous coordinates. A NURBS curve in the three-dimensional space is merely the projection of a B-spline curve in four-dimensional space.

Chapter 2. Important Properties

Important Properties of NURBS Basis Functions

在 B 样条曲线基函数特点的基础上有 2 条特有的特点.

1. $R_{i,p}(u)$ is a degree $p$ rational function in $u$.
2. If $w_i = c$ for all $i$, where $c$ is a non-zero constant, $R_{i,p}(u) = N_{i,p}(u)$.

Important Properties of NURBS Curves

基本上与 B 样条曲线一致

Chapter 3. Modifying Weights

Increasing (resp., decreasing) the value of weight $w_i$ pulls (resp., pushes) the curve toward (resp., away from) control point $P_i$. When the value of wi becomes infinity, the curve passes through control point $P_i$ and when $w_i$ is zero, control point $P_i$ has no impact on the curve.
相关的数学证明还是参考讲义吧, 很繁琐但是不复杂.

Chapter 4. Important Algorithms for B-spline and NURBS Curves

Knot Insertion

分为 3 步:

1. converting the given NURBS curve in 3D to a B-spline curve in 4D.
2. performing knot insertion to this four dimensional B-spline curve.
3. projecting the new set of control points back to 3D to form the the new set of control points for the given NURBS curve.

Rational Bézier Curves

贝塞尔函数转换为 rational 格式.

Rational Bézier Curves: Conic Sections 圆锥曲线

The rational Bézier curve defined by three non-collinear control points $P_0$, $P_1$ and $P_2$ and weights $1, w , 1$ is a hyperbola, a parabola or an ellipse if $w$ is greater than, equal to, or less than 1.
推导过程见官网.

Circular Arcs and Circles

这部分感觉比较实用, 稍微解释一下.
三点确定一个圆, 2阶.
如下图:

$$
\begin{aligned}
&|\mathrm{MX}|=|\mathrm{OX}|-|\mathrm{OM}|=r-r \sin (a)=r(1-\sin (a)) \
&\left|\mathrm{M P}{1}\right|=\left|\mathrm{OP}{1}\right|-|\mathrm{OM}|=\frac{r}{\sin (a)}-r \sin (a)=\frac{r\left(1-\sin ^{2}(a)\right)}{\sin (a)} \
&\frac{w}{1+w}=\frac{|\mathrm{MX}|}{\left|\mathrm{MP}_{1}\right|}=\frac{\sin (a)}{1+\sin (a)}
\end{aligned}
$$

如图所示, 三点只得到一段圆弧, 得到整圆的话需要将几段圆弧拼接起来.

可以用三段等腰三角形导出的圆弧/四段等腰直角三角形导出的圆弧拼接而成.
控制点一目了然, knots 前者选择 $[0, 0, 0, 1/3, 1/3, 2/3, 2/3, 1, 1, 1]$, 后者选择 $[0, 0, 0, 1/4, 1/4, 1/2, 1/2, 3/4, 3/4, 1, 1, 1]$.
前/后 3 个 knot 满足 clamped 原则, 中间 1/3 是均等三段, 重复 2 次是强制经过中间的某些控制点.

Unit 8: Surfaces

略过.

Unit 9: Interpolation and Approximation 插值与拟合

Chapter 1. Parameter Selection and Knot Vector Generation

Parameter Selection Overview

问题描述: 给定点寻找合适的 parameter vector 与 knots vector 穿过所有点得到每段曲线的表达式.
if the data points are $D_0, …, D_n$, then $n+1$ parameters $t_0, …, t_n$ in the domain of the curve must be found so that data point $D_k$ corresponds to parameter $t_k$ for $k$ between 0 and $n$. This means that if $C(u)$ is a curve that passes through all data points in the given order, then we have $D_k = C(t_k)$ for all $0 <= k <= n$.
方法有: Uniformly Spaced Method, Chord Length Method, Centripetal Method.
knots: Knot Vector Generation.

The Uniformly Spaced Method

$\textbf{t}$ 的选择如下:

$$
\begin{aligned}
t_{0} &=0 \
t_{i} &=\frac{i}{n} \quad \text { for } 1 \leq i \leq n-1 \
t_{n} &=1
\end{aligned}
$$

$n+1$ points divide the interval $[0,1]$ into $n$ subintervals evenly, each of which must be of length $1/n$, the division points are $0, 1/n, 2/n, 3/n, …, (n-1)/n 1$.
自变量定义域归一化:

$$
\begin{aligned}
&t_{0}=a \
&t_{i}=a+i \frac{b-a}{n} \quad \text { for } 1 \leq i \leq n-1 \
&t_{n}=b
\end{aligned}
$$

特点: 简单, 但是遇到插值点分布没那么均匀的情况会出现 big bulges, sharp peaks and loops, 如下图.

The Chord Length Method

用点距比例分配 domian: if the domain is subdivided according to the distribution of the chord lengths, the parameters will be an approximation of the arc-length parameterization.
公式如下:

$$
\begin{aligned}
L &=\sum_{i=1}^{n}\left|\mathbf{D}{i}-\mathbf{D}{i-1}\right| \quad L_{k}=\frac{\sum_{i=1}^{k}\left|\mathbf{D}{i}-\mathbf{D}{i-1}\right|}{L} \
t_{0} &=0 \
t_{k} &=\frac{1}{L}\left(\sum_{i=1}^{k}\left|\mathbf{D}{i}-\mathbf{D}{i-1}\right|\right) \
t_{n} &=1
\end{aligned}
$$

问题: 有时候较长的段会变现的不必要地摇摆.
Sometimes, a longer chord may cause its curve segment to have a bulge bigger than necessary.

数学证明: polynomial curves cannot be parameterized to have unit speed (i.e., arc-length parameterization), the chord length can only be an approximation.

The Centripetal Method

解决 Chord Length Method中的长距离点间曲线不稳定的问题, 将点距做 <1 的幂运算.

$$
\begin{aligned}
&L=\sum_{i=1}^{n}\left|\mathbf{D}{i}-\mathbf{D}{i-1}\right|^{a} \
&L_{k}=\frac{\sum_{i=1}^{k}\left|\mathbf{D}{i}-\mathbf{D}{i-1}\right|^{a}}{L}
\end{aligned}
$$

$a$ 通常取值 0.5.

对比：

有些情况还是Uniformly Spaced Method表现更好

Knot Vector Generation

一般为 clamped, 以下均基于 clamped.

1. uniformly spaced

$$
\begin{aligned}
u_{0} &=u_{1}=\cdots=u_{p}=0 \
u_{j+p} &=\frac{j}{n-p+1} \quad \text { for } j=1,2, \ldots, n-p \
u_{m-p} &=u_{m-p+1}=\cdots=u_{m}=1
\end{aligned}
$$

This method is not recommended because, if it is used with the chord length method for global interpolation, the system of linear equations would be singular.
2. “average” the parameters only in affected area

$$
\begin{aligned}
u_{0} &=u_{1}=\cdots=u_{p}=0 \
u_{j+p} &=\frac{1}{p} \sum_{i=j}^{j+p-1} t_{i} \quad \text { for } j=1,2, \ldots, n-p \
u_{m-p} &=u_{m-p+1}=\cdots=u_{m}=1
\end{aligned}
$$

The Universal Method

先求 uniformly spaced Knot Vector, 然后求 degree $p$ 时基函数的最大值点为参数点.
特点:

1. 大概率与 Uniformly Spaced Method 一致
2. 求解最大值可以用采样/搜索(例如 Golden Section Search)的方式节省效率.
3. affine invariant, the transformed interpolating B-spline curve can be obtained by transforming the data points. Uniformly Spaced Method 也有仿射不变性, 但是 Chord Length Method/Centripetal Method 则没有这个性质.

Parameters and Knot Vectors for Surfaces

略过.

Chapters 2. Solving Systems of Linear Equations

数学基础补充. LU 分解求解线性方程组.

$$
\begin{array}{rl}
& \mathbf{B}=\mathbf{A} \cdot \mathbf{X} \
& \mathbf{B}=\left[\begin{array}{cccc}
b_{11} & b_{12} & \cdots & b_{1 h} \
b_{21} & b_{22} & \cdots & b_{2 h} \
\vdots & & \ddots & \vdots \
b_{n 1} & b_{n 2} & \cdots & b_{n h}
\end{array}\right]{n \times h} \
& \mathbf{A}=\left[\begin{array}{ccccc}
a{11} & a_{12} & \cdots & a_{1 n} \
a_{21} & a_{22} & \cdots & a_{2 n} \
\vdots & & \ddots & \vdots \
a_{n 1} & a_{n 2} & \cdots & a_{n n}
\end{array}\right]{n \times n}
\end{array} \
\mathbf{X}=\left[\begin{array}{cccc}
x{11} & x_{12} & \cdots & x_{1 h} \
x_{21} & x_{22} & \cdots & x_{2 h} \
\vdots & & \ddots & \vdots \
x_{n 1} & x_{n 2} & \cdots & x_{n h}
\end{array}\right]_{n \times h}
$$

1. LU Decomposition
   $\textbf{A} = \textbf{L}\cdot\textbf{U}$

$$
\mathrm{L}=\left[\begin{array}{ccccc}
l_{11} & 0 & 0 & \cdots & 0 \
l_{21} & l_{22} & 0 & & 0 \
\vdots & & & \ddots & \vdots \
l_{n 1} & l_{n 2} & l_{n 3} & \cdots & l_{n n}
\end{array}\right] \quad \mathrm{U}=\left[\begin{array}{ccccc}
u_{11} & u_{12} & u_{13} & \cdots & u_{1 n} \
0 & u_{22} & u_{23} & & u_{2 n} \
0 & 0 & u_{33} & & u_{3 n} \
\vdots & & & \ddots & \vdots \
0 & 0 & 0 & \cdots & u_{n n}
\end{array}\right]
$$

2. Forward Substitution
   $\textbf{B} = \textbf{L}\cdot(\textbf{U}\cdot\textbf{X})=\textbf{L}\cdot\textbf{Y}$
   即求解 $\textbf{B} = \textbf{L}\cdot\textbf{Y}$

$$
\begin{aligned}
&\left[\begin{array}{cccc}
b_{11} & b_{12} & \cdots & b_{1 h} \
b_{21} & b_{22} & \cdots & b_{2 h} \
\vdots & & \ddots & \vdots \
b_{n 1} & b_{n 2} & \cdots & b_{n h}
\end{array}\right]=\left[\begin{array}{ccccc}
l_{11} & 0 & 0 & \cdots & 0 \
l_{21} & l_{22} & 0 & & 0 \
\vdots & & & \ddots & \vdots \
l_{n 1} & l_{n 2} & l_{n 3} & \cdots & l_{n n}
\end{array}\right] \cdot\left[\begin{array}{cccc}
y_{11} & y_{12} & \cdots & y_{1 h} \
y_{21} & y_{22} & \cdots & y_{2 h} \
\vdots & & \ddots & \vdots \
y_{n 1} & y_{n 2} & \cdots & y_{n h}
\end{array}\right]\
&\left[\begin{array}{c}
b_{1} \
b_{2} \
\vdots \
b_{n}
\end{array}\right]=\left[\begin{array}{ccccc}
l_{11} & 0 & 0 & \cdots & 0 \
l_{21} & l_{22} & 0 & & 0 \
\vdots & & & \ddots & \vdots \
l_{n 1} & l_{n 2} & l_{n 3} & \cdots & l_{n n}
\end{array}\right] \cdot\left[\begin{array}{c}
y_{1} \
y_{2} \
\vdots \
y_{n}
\end{array}\right]\
&b_{1}=l_{11} y_{1}\
&b_{2}=l_{21} y_{1}+l_{22} y_{2}\
&\text { : } \quad\
&b_{n}=l_{n 1} y_{1}+l_{n 2} y_{2}+l_{n 3} y_{3}+\cdots+l_{n n} y_{n}
\end{aligned}
$$

从上往下可以推出所有的 $y_i$

$$
y_{i}=\frac{1}{l_{i i}}\left[b_{i}-\sum_{k=1}^{i-1} l_{i, k} y_{k}\right]
$$

3. Backward Substitution
   即求解 $\textbf{X}=\textbf{L}\cdot\textbf{Y}$

$$
\begin{aligned}
&\left[\begin{array}{c}
y_{1} \
y_{2} \
\vdots \
y_{n}
\end{array}\right]=\left[\begin{array}{ccccc}
u_{11} & u_{12} & u_{13} & \cdots & u_{1 n} \
0 & u_{22} & u_{23} & & u_{2 n} \
0 & 0 & u_{33} & & u_{3 n} \
\vdots & & & \ddots & \vdots \
0 & 0 & 0 & \cdots & u_{n n}
\end{array}\right] \cdot\left[\begin{array}{c}
x_{1} \
x_{2} \
\vdots \
x_{n}
\end{array}\right]\
&y_{1}=u_{11} x_{1}+u_{12} x_{2}+u_{13} x_{3}+\cdots+u_{1 n} x_{n}\
&y_{2}=\quad u_{22} x_{2}+u_{23} x_{3}+\quad+u_{2 n} x_{n}\
&y_{n}=\quad u_{n n} x_{n}\
&x_{i}=\frac{1}{u_{i i}}\left[y_{i}-\sum_{k=i+1}^{n} u_{i, k} x_{k}\right]
\end{aligned}
$$

Chapter 3. Curve Global Interpolation

问题定义:
Given a set of $n+1$ data points, $D_0, D_2, …, D_n$ and a degree $p$, find a B-spline curve of degree $p$ defined by $n+1$ control points that passes all data points in the given order.

parameter 有四种选择方法: uniform, chord length, centripetal, universal.

Global Method

选定 parameter 后, 使用矩阵求解的方式求得所有的控制点坐标.

$$
\mathbf{D}{k}=\mathbf{C}\left(t{k}\right)=\sum_{i=0}^{n} N_{i, p}\left(t_{k}\right) \mathbf{P}_{i} \quad \text { for } 0 \leq k \leq n
$$

$$
\begin{aligned}
&\mathbf{N} =\left[\begin{array}{ccccc}
N_{0, p}\left(t_{0}\right) & N_{1, p}\left(t_{0}\right) & N_{2, p}\left(t_{0}\right) & \cdots & N_{n, p}\left(t_{0}\right) \
N_{0, p}\left(t_{1}\right) & N_{1, p}\left(t_{1}\right) & N_{2, p}\left(t_{1}\right) & \cdots & N_{n, p}\left(t_{1}\right) \
\vdots & & & \ddots & \vdots \
N_{0, p}\left(t_{n}\right) & N_{1, p}\left(t_{n}\right) & N_{2, p}\left(t_{n}\right) & \cdots & N_{n, p}\left(t_{n}\right)
\end{array}\right] \
& \mathbf{D}=\left[\begin{array}{ccccc}
d_{01} & d_{02} & d_{03} & \cdots & d_{0 s} \
d_{11} & d_{12} & d_{13} & \cdots & d_{1 s} \
\vdots & & & \ddots & \vdots \
d_{n 1} & d_{n 2} & d_{n 3} & \cdots & d_{n s}
\end{array}\right] \qquad \mathbf{P}=\left[\begin{array}{ccccc}
p_{01} & p_{02} & p_{03} & \cdots & p_{0 s} \
p_{11} & p_{12} & p_{13} & \cdots & p_{1 s} \
\vdots & & & \ddots & \vdots \
p_{n 1} & p_{n 2} & p_{n 3} & \cdots & p_{n s}
\end{array}\right]
\end{aligned}
$$

化成一般形式求解 $s$ 个如下方程($s$ 为坐标维度):

$$
\mathrm{d}^{i}=\mathrm{N} \cdot \mathrm{p}^{i}
$$

The Impact of Parameters and Knots

uniform/universal 能更好地应对长距离, chord length 能更好地缓解 cusp, centripetal 是前两者的折衷.

The Impact of Degree

degree 越高, 曲线自由度越高越容易 cusp, 尤其是在 uniform 方法.

Chapter4. Curve Global Approximation

问题定义:
Given a set of $n+1$ data points, $D_0, D_1, …, D_n$, a degree $p$, and a number $h$, where $n > h >= p >= 1$, find a B-spline curve of degree $p$ defined by $h+1$ control points that satisfies the following conditions:

1. this curve contains the first and last data points.
2. this curve approximates the data polygon in the sense of least square.

后面的讲义用到了最小二乘法求解, 其中 error distance 是 $ |D_k - C(t_k)|$ 即 parameter vector 处的误差. 整个推导过程非常值得学习一遍, 推荐随着讲义推导一遍. 本文不再复制粘贴.

Chapter 5. Surface Interpolation

略过.

Chapter 6. Surface Approximation

略过.