Question

Curve

想要建立曲线，可以使用多项式函数，平滑柔顺。

这种方式有个严重的问题：曲线是一个函数，每个 X 值只对应一个 Y 值；曲线不能到处乱绕，只能左右伸展。

要解决这个问题，最简单的方法，就是分别处理 X 轴与 Y 轴。用一个多项式专门处理 X 座标，用另一个多项式专门处理 Y 座标。

例如
x(t) = 1 + 2t¹ + 3t² - t³
y(t) = 2 - t¹ + t² - t³

t 代入-0.1，得到一个座标(x(-0.1), y(-0.1)) = (0.831, 2.111)
t 代入   0，得到一个座标(x(0)   , y(0)   ) = (1, 2)
t 代入 0.1，得到一个座标(x(0.1) , y(0.1) ) = (1.229, 1.909)

这个手法叫做“参数式 Parametric Equation”，t 就是参数。高中数学、微积分、线性代数课程都有提到，既基础又常见，不是什麽艰深晦涩的玩意。

引入 Control Point 以操控曲线

想要操控曲线，最便捷的方式，就是点上几个点，然后运用“ 多项式内插 ”，得到一条穿过这些点的曲线。操控点的位置，就操控了曲线的位置。

电脑擅于处理大量资料。我们可以制作非常多条曲线，让曲线衔接曲线，就得到各式各样的形状了。因此，通常我们不会制作无限长的曲线，其实制作一小段曲线就够了。

我们习惯让 t 值的范围是 0 到 1。设定三个点、用二次多项式实施内插，三个点的 t 值分别是 0、0.5、1。或者设定四个点、用三次多项式实施内插，四个点的 t 值分别是 0、1/3、2/3、1。

一次多项式只能产生直线，二次以上的多项式就足以产生曲线。

引入 Knot Point 以微调曲线

自由调整控制点的参数 t，不一定要等分。曲线仍然穿过所有控制点，但是曲线形状会改变。

额外建立一条数线，范围是 t = 0 到 t = 1。在数线上放置四个枢纽点，分别调控四个控制点的参数 t。第一个枢纽点固定于 t = 0，最后一个枢纽点固定于 t = 1。

简单起见，以下暂不考虑枢纽点。

採用 Vandermonde Matrix 演算法，进行多项式内插。

一、设定内插多项式。

平面上四个点 (1,3) (1,0) (2,2) (3,4)
X 座标、Y 座标分别处理，採用三次（四项）多项式。
x(t) = a₀t⁰ + a₁t¹ + a₂t² + a₃t³
y(t) = b₀t⁰ + b₁t¹ + b₂t² + b₃t³

二、求得内插多项式的係数。

首先处理 X 座标！
令四个点对应的 t 值是 t = 0, 1/3, 2/3, 1。
也就是说 x(0) = 1 , x(1/3) = 1 , x(2/3) = 2 , x(1) = 3

[     0⁰     0¹     0²     0³ ] [ a₀ ]   [ 1 ]
[ (1/3)⁰ (1/3)¹ (1/3)² (1/3)³ ] [ a₁ ] = [ 1 ]
[ (2/3)⁰ (2/3)¹ (2/3)² (2/3)³ ] [ a₂ ]   [ 2 ]
[     1⁰     1¹     1²     1³ ] [ a₃ ]   [ 3 ]
                                       -1
[ a₀ ]   [     0⁰     0¹     0²     0³ ] [ 1 ]
[ a₁ ] = [ (1/3)⁰ (1/3)¹ (1/3)² (1/3)³ ] [ 1 ]
[ a₂ ]   [ (2/3)⁰ (2/3)¹ (2/3)² (2/3)³ ] [ 2 ]
[ a₃ ]   [     1⁰     1¹     1²     1³ ] [ 3 ]

[ a₀ ]   [    1     0     0     0 ] [ 1 ]
[ a₁ ] = [ -5.5     9  -4.5     1 ] [ 1 ]
[ a₂ ]   [    9 -22.5    18  -4.5 ] [ 2 ]
[ a₃ ]   [ -4.5  13.5 -13.5   4.5 ] [ 3 ]

无论一开始给定哪四个点，矩阵都是固定不变的。
无论一开始给定哪四个点，往后都可以直接套用公式，求得多项式係数。

[ a₀ ]   [    1     0     0     0 ] [ x₀ ]
[ a₁ ] = [ -5.5     9  -4.5     1 ] [ x₁ ]
[ a₂ ]   [    9 -22.5    18  -4.5 ] [ x₂ ]
[ a₃ ]   [ -4.5  13.5 -13.5   4.5 ] [ x₃ ]

a₀ =    1 x₀ +     0 x₁ +     0 x₂ +    0 x₃
a₁ = -5.5 x₀ +     9 x₁ +  -4.5 x₂ +    1 x₃
a₂ =    9 x₀ + -22.5 x₁ +    18 x₂ + -4.5 x₃
a₃ = -4.5 x₀ +  13.5 x₁ + -13.5 x₂ +  4.5 x₃

三、曲线座标的公式。

内插多项式的係数公式
a₀ =    1 x₀ +     0 x₁ +     0 x₂ +    0 x₃
a₁ = -5.5 x₀ +     9 x₁ +  -4.5 x₂ +    1 x₃
a₂ =    9 x₀ + -22.5 x₁ +    18 x₂ + -4.5 x₃
a₃ = -4.5 x₀ +  13.5 x₁ + -13.5 x₂ +  4.5 x₃

代回到内插多项式
x(t) = a₀t⁰ + a₁t¹ + a₂t² + a₃t³

得到曲线座标的公式
x(t) =  -4.5       (t-1/3) (t-2/3) (t-1) x₀
     +  13.5 (t-0)         (t-2/3) (t-1) x₁
     + -13.5 (t-0) (t-1/3)         (t-1) x₂
     +   4.5 (t-0) (t-1/3) (t-2/3)       x₃

代入各种 t 值（范围是 0≤t≤1），得到曲线上每个点的 X 座标。

保持矩阵模样的推导方式。教科书喜欢这样推导。
x(t) = a₀t⁰ + a₁t¹ + a₂t² + a₃t³

                       [ a₀ ]
     = [ t⁰ t¹ t² t³ ] [ a₁ ]   写成点积
                       [ a₂ ]
                       [ a₃ ]

                       [    1     0     0     0 ] [ x₀ ]
     = [ t⁰ t¹ t² t³ ] [ -5.5     9  -4.5     1 ] [ x₁ ]   内插多项式的係数
                       [    9 -22.5    18  -4.5 ] [ x₂ ]
                       [ -4.5  13.5 -13.5   4.5 ] [ x₃ ]

                                   [ x₀ ]
     = [ a₀(t) a₁(t) a₂(t) a₃(t) ] [ x₁ ]   前面两个矩阵先相乘
                                   [ x₂ ]
                                   [ x₃ ]
其中
a₀(t) =  -4.5       (t-1/3) (t-2/3) (t-1)
a₁(t) =  13.5 (t-0)         (t-2/3) (t-1)
a₂(t) = -13.5 (t-0) (t-1/3)         (t-1)
a₃(t) =   4.5 (t-0) (t-1/3) (t-2/3)

四、X 座标、Y 座标分别处理，如法炮制。

x(t) =  -4.5       (t-1/3) (t-2/3) (t-1) x₀
     +  13.5 (t-0)         (t-2/3) (t-1) x₁
     + -13.5 (t-0) (t-1/3)         (t-1) x₂
     +   4.5 (t-0) (t-1/3) (t-2/3)       x₃

y(t) =  -4.5       (t-1/3) (t-2/3) (t-1) y₀
     +  13.5 (t-0)         (t-2/3) (t-1) y₁
     + -13.5 (t-0) (t-1/3)         (t-1) y₂
     +   4.5 (t-0) (t-1/3) (t-2/3)       y₃

五、代入各种 t，得到曲线座标。

Surface

Surface

曲线从一维推广到二维，参数 t 推广到参数 u 和 v。

大家习惯採用 4x4 个控制点。欲得到参数 u 和 v 所对应的点，先算横向：每四点以参数 u 求得曲线上一点；再算纵向：方才得到的四个点以参数 v 求得曲线上一点。

也可以改成先纵再横，结果相同。

Bézier Surface

大家习惯採用 4x4 个控制点。计算方式与前面小节相同。

http://www.scratchapixel.com/lessons/advanced-rendering/bezier-curve-rendering-utah-teapot/bezier-surface

Polyline

Polyline

电脑擅于处理大量资料。与其处心积虑、用少量控制点制造曲线，不如直截了当、用大量控制点制造折线。法理上，根据微积分的极限概念，极短的、绵密的、大量的直线，可以逼近曲线。情理上，只要点数够多，折线就足够耐看了。

Polyline 应用广泛。例如 Microsoft PowerPoint 的徒手画。写程式实作时，不断撷取当前滑鼠座标，自然而然形成 polyline。

Polyline Simplification（Polyline Decimation）

当折线太乱，我们可以减少点数、截弯取直。

知名演算法如 Ramer-Douglas-Peucker Algorithm。

http://geomalgorithms.com/a16-_decimate-1.html

Polyline Smoothing

当折线太乱，我们可以截弯取直。

每个线段取中点。实施越多次，折线越平滑。

每个线段取中点，可以化作矩阵。

N = 4
[ x₀']   [ ½ ½ 0 0 ] [ x₀ ]      [ y₀']   [ ½ ½ 0 0 ] [ y₀ ]
[ x₁'] = [ 0 ½ ½ 0 ] [ x₁ ]      [ y₁'] = [ 0 ½ ½ 0 ] [ y₁ ]
[ x₂']   [ 0 0 ½ ½ ] [ x₂ ]      [ y₂']   [ 0 0 ½ ½ ] [ y₂ ]
[ x₃']   [ 0 0 0 0 ] [ x₃ ]      [ y₃']   [ 0 0 0 0 ] [ y₃ ]
这一点与下一点的加权平均值，权重都是 0.5，得到中点。

还可进一步实施特徵分解（转换到频域）。折线平滑 K 次，即是特徵值的 K 次方。

因为实数对称矩阵保证有实数特徵基底（而且是正交基底），所以大家习惯採用封闭折线、以平滑两次的矩阵实施特徵分解。

时间複杂度，原先为 O(NK)。化作矩阵，O(N^3 * logK)。特徵分解，而且预先计算特徵基底，O(N^2 * logK)。

[ ½ ½ 0 0 ]   [ ½ ½ 0 0 ]   [ ¼ ½ 0 ½ ]
[ 0 ½ ½ 0 ]   [ 0 ½ ½ 0 ]   [ ½ ¼ ½ 0 ]
[ 0 0 ½ ½ ]   [ 0 0 ½ ½ ]   [ 0 ½ ¼ ½ ]
[ 0 0 0 0 ]   [ ½ 0 0 ½ ]   [ ½ 0 ½ ¼ ]
平滑一次      平滑一次      平滑两次
开放折线      封闭折线      封闭折线

还可进一步连结到图论的 Laplacian Matrix：

https://books.google.com.tw/books?id=NeA_CQAAQBAJ&pg=PA63

Mesh（Under Construction!）

Mesh

Mesh Subdivision

分割。增加点数。内插。

https://en.wikipedia.org/wiki/Subdivision_surface
http://www.cs.kent.edu/~zhao/acg13/lectures/Subdivision.pdf

Loop subdivision
Catmull-Clark subdivision
Doo-Sabin subdivision
Butterfly subdivision
sqrt(3) subdivision

Mesh Simplification

简化。减少点数。缩边。

Garland–Heckbert method

Mesh Smoothing

平滑。移动点。

http://www.cin.ufpe.br/~tlam/detail%20preserving%20mesh%20edition.pdf

Taubin smoothing
FVM smoothing

Mesh Parameterization

参数化。给定一点找到参数（座标）。

PN Triangles