引言
GAMES101 现代图形学入门是由闫令琪老师教授。今天我们讲几何的第二部分曲线和曲面，讨论贝塞尔曲线。
Explicit Representations
Many Explicit Representations in Graphics
我们可以看看这里有很多三角形面、贝塞尔曲面以及各种细分曲面等等，这些我们会一一给大家介绍。
Point Cloud (Explicit)
首先给大家介绍最简单的显式物体面的表示：点云。作为点云我们不考虑这个物体是一个表面，而是表面上的一堆点，我把每一个点都给表示成一个点，那只要这些点我表示的足够细自然而然看不到点与点之间的缝隙而是表面，记录为(x,y,z)的一个列表。
图中是一个雕塑，它上半部分的点云密度非常大，所以可以看到物体表面；随着点云密度降低，当点云稀疏的时候大家就不太容易看出它是一个面。所以点云如果要表示成一个非常复杂的模型需要特别密集的点，理论上只要点云足够密集也可以表示任何类型的几何，通常人们做一些三维空间中的扫描输出就是一堆的点云。之后自然而然涉及一个点云如何把它变成三角形面？点云之后会变成多边形的面，正常情况下如果点云密度很低雕塑就不容易画出来，这就是人们为什么平常不特别多用点云，除了扫描出来最原始的数据。
Polygon Mesh (Explicit)
Store vertices & polygons (often triangles or quads)
Easier to do processing / simulation, adaptive sampling
More complicated data structures
Perhaps most common representation in graphics
如果大家接触过三维建模，在图形学中我们用的最多的一种是多边形面，特别的是三角形面得到非常广泛的应用。任何面都可以拆成小的三角形，所以完全可以用三角形或四边形去描述各种各样的复杂的物体。
The Wavefront Object File (.obj) Format
Commonly used in Graphics research
Just a text file that specifies vertices, normals, texture
coordinates and their connectivities
这里既然提到三角形面，顺便讲解一下我们在图形学中是如何表示用三角形面形成的物体的。这种.obj格式是一个文本文件，它把空间中的一堆点、法线和纹理坐标分开来表示，然后再一块组织起来形成一个模型。
在图中v表示立方体的八个顶点，vn则代表立方体六个面的法线（这里有八个是建模的冗余和精度问题），之后我们再定义12个纹理坐标vt。把这些定义好之后我们开始定义它们之间的连接关系f，也就是哪三个点会形成一个三角形。
Curves
Camera Paths
上图反应的是一个高新技术园区的建造，相机它在空间中沿着某一个曲线运动，并且可以转换不同的方向。既然要定义好一个曲线，那么势必通过某种形式来描述。
Animation Curves
在三维建模中Maya中可以定义一些曲线，然后我就可以让任意的模型沿着曲线去移动，这就是之前摄像机移动的制作过程。
Vector Fonts
Baskerville font - represented as piecewise cubic Bézier curves
在第一节课我们就说过用曲线可以定义一些字体，字体可以加入控制点，如果无限放大曲线的某个区域，它一定是光滑的而不会出现格子的情况。这是怎么回事呢？这就是我们今天要说的贝塞尔曲线，也是一种显式的几何表示方法。
Bézier Curves
Defining Cubic Bézier Curve With Tangents
贝塞尔曲线通过一系列的控制点去定义一个曲线。这些控制点它会定义曲线满足的一些性质，比如说满足从$p_0$开始并且沿着由$p_0$开始到$p_1$这么一个方向，这四个点定义了贝塞尔曲线，同样道理这个曲线会在$p_3$结束并且沿着$p_2 \space p_3$方向。
通过这四个点，我可以定义这条曲线的起始点和终点一定在$p_0$和$p_3$上，并且它的起始切线和结束切线为$p_0p_1$和$p_2p_3$，这样就可以得到一条唯一的曲线。需要注意的是曲线不一定经过控制点，这取决于我们怎么定义它，我们只定义曲线一定要经过起止点。
Bézier Curves – de Casteljau Algorithm
我们用任意多个点如何去绘制贝塞尔曲线？所以先介绍de Casteljau算法，示例中我们给定三个控制点，它生成的贝塞尔曲线被称为二次贝塞尔曲线。
首先我们从$b_0$开始在$b_2$结束，$b_1$决定它往哪个位置弯。假设这条曲线我可以定义它的起点是在时间$0$，终点是在时间$1$，那么我们想要画出这条曲线实际上我要把它在任意一个$0~1$之间的时间$t$找出曲线的点在空间平面的位置。de Casteljau算法告诉我们的就是怎么样找这个点，我们把绘制整个曲线转化为找一个点。
怎么找这个点呢？大家看到这三个点形成了两个线段，方向就是按照输入的顺序。在$b_0b_1$上我认为$b_0$是$0$，$b_1$是$1$，那时间$t$约等于1/3，那么就在$b_0b_1$找到1/3的位置这么一个点。
同样道理，我在$b_1b_2$上也找这么一个1/3的位置。这样一来我就找到了三个点形成两个线段中的两个点。
那么我们把新得到的两个点连起来，那么我再认为$b^1_0b^1_1$是从$0$到$1$开始的，找到时间$t$的1/3位置$b^2_0$。这个点就是贝塞尔曲线在时间$t$所在的位置，任意一个时间$t$都可以用类似的方式找到它。
只要枚举所有可能出现的时间$t$，就可以画出一条完整的曲线。只要能画一个点，理论上来说我们就能画不同其他的点。
Cubic Bézier Curve – de Casteljau
Four input points in total
Same recursive linear interpolations
下面一个例子给定四个不同的点定义贝塞尔曲线，$b_0 \space b_3$为曲线的起止点，中间的$b_1 \space b_2$用于控制曲线。我们同样用这种递归的方式来做，最终可以找到$b_0^3$就是贝塞尔曲线的位置。
Visualizing de Casteljau Algorithm
Animation: Steven Wittens, Making Things with Maths, http://acko.net
Evaluating Bézier Curves Algebraic Formula
Bézier Curve – Algebraic Formula
de Casteljau algorithm gives a pyramid of coefficients
算法咱们已经说明白了，但这是一种直观形式的解释，通过这种解释能不能推出一些代数上的形式呢？首先，贝塞尔曲线由不同的控制点决定的，所以任意时刻贝塞尔曲线的点一定是通过控制点操作得到，相当于把控制点位置和时间放在一块我们一定有一个代数的表示方法。
比如仍然是输入四个不同的点$b_0 \space b_1 \space b_2 \space b_3$，每两个之间在位置上做一个线性插值得出$b_0^1 \space b_1^1 \space b_2^1$，同理可得最后的$b_0^3$。整个过程一直在线性插值，最后得到一个值的算法。
Example: quadratic Bézier curve from three points
我们可以把它显式的写出来，我们知道$b_0 \space b_1$的坐标，时间$t$也知道。这里$(1-t)b_0$是因为当$t=0$时$b^1_0(t)=(1-t)b_0+tb_1=b_0$，同理可知，最后的点就是$b_0^2(t)=(1-t)b_0^1+tb_1^1=(1-t)^2b_0+2t(1-t)b_1+t^2b_2$。这也符合刚才我们的分析，任意一个时刻贝塞尔曲线上任意一个点当然得由几个控制点的坐标来决定，还得跟$t$有关系。
Bézier Curve – General Algebraic Formula
这里做一个总结，它是一个多项式。给定$n+1$个控制点，我们可以得到一个$n$阶的贝塞尔曲线，它在任意时间$t$都是之前给定控制点的线性组合，组合的系数就是一个和时间有关的多项式。这个多项式就叫做伯恩斯坦多项式，这个多项式用于描述二项分布。
Bézier Curve – Algebraic Formula: Example
我们不考虑多少层了，任意阶数的贝塞尔曲线任意时间$t$这个点的位置由伯恩斯坦多项式作为系数，对给定的控制点进行加权。不管它是什么，在时间$t$它一定会通过这么四个不同的系数，把$b_0 \space b_1 \space b_2 \space b_3$组合起来表述贝塞尔曲线的一个点。
Cubic Bézier Basis Functions
Properties of Bézier Curves
Interpolates endpoints
- For cubic Bézier: $b(0)=b_0\space b(1)=b_3$
Tangent to end segments
- Cubic case: $b’(0)=3(b_1-b_0) \space b’(1)=3(b_3-b_2)$
Affine transformation property
- Transform curve by transforming control points
Convex hull property
- Curve is within convex hull of control points
贝塞尔曲线在仿射变换下可以直接对不同的顶点做仿射变换，然后再重新对这个变换之后的顶点画一条贝塞尔曲线出来，那么这个贝塞尔曲线一定和另外一个贝塞尔曲线是一样的。我已经通过原始的控制点画出一条贝塞尔曲线，然后在这条贝塞尔曲线上面的每一个点做仿射变换，这样的方式得出的贝塞尔曲线是一模一样的。
贝塞尔曲线还有凸包性质。凸包是在计算几何上得到广泛应用的概念，这里简单解释一下，我们画出来的贝塞尔曲线一定是在几个控制点形成的凸包内。这个性质的简单应用是当几个控制点排列在一条直线上时，贝塞尔曲线一定就是这条直线，绝对不会超过凸包的范围。
BTW: What’s a Convex Hull
凸包的概念很好理解，其中一种定义是能够包围一系列给定的几何形体的最小凸多边形。直观来讲，我们可以想象平面上钉了很多钉子，然后用橡皮筋拉到非常大把所有钉子包住，然后突然松手，橡皮筋收缩在这些物体形成的某些外框上，这个框就可以理解是凸包。
Piecewise Bézier Curves
Higher-Order Bézier Curves?
11个控制点画出一条贝塞尔曲线。这条曲线是对的没有问题，但不够直观。也就是说这条曲线不好控制，当控制点多的时候不适合用中间控制点控制，得到想要的形状不是很好操作。
Piecewise Bézier Curves
Instead, chain many low-order Bézier curve
Piecewise cubic Bézier the most common technique
Widely used (fonts, paths, Illustrator, Keynote, …)
这时人们发现干嘛要一次用这么多的控制点去定义一个贝塞尔曲线呢？每次我用很少的控制点定义一段贝塞尔曲线，并且我把这些贝塞尔曲线连起来逐段定义。特别的来说，大家喜欢把逐段贝塞尔曲线定义成每四个控制点可以控制一条贝塞尔曲线。
Demo – Piecewise Cubic Bézier Curve
这种定义方法得到了非常广泛的应用，也正是Ps中的钢笔工具画曲线的功能。上图就是分段的三次贝塞尔曲线，有人会问如何保证连起来的曲线时光滑的呢？我们要求导数必须连续，无论方向还是大小。
Piecewise Bézier Curve – Continuity
给定两个贝塞尔曲线，都是由四个控制点构成。在几何上的这两个曲线都通过中间那个点，只要接触就是连续，这就是一种最简单的连续。
只要第一段的终止点等于第二段的起始点，我们就管这种连续叫做$C^0$连续，$C$表示连续性continuity，在几何上只要挨在一块，不管它形成多么大的锐角就是连续。
我们再定义一种连续，希望切线也能够连续。这两段离公共点的距离需要一样，并且方向也是一样，代数表达是$a_n=b_0=\frac{1}{2}(a_{n-1}+b_1)$。这时候我们管这种连续性叫做$C^1$连续，也可以认为是一阶导数的连续。
二阶导数被称为曲率连续，有很多各种各样的连续性要求。$C^1$连续看起来已经挺好的，但在制造上仍然不够。
Other types of splines
Spline
- a continuous curve constructed so as to pass through a given set
of points and have a certain number of continuous derivatives. - In short, a curve under contro
样条相当于对曲线的一种总结，一个连续的曲线是由一系列控制点控制的，它能够满足一定的连续性，取决于具体的例子。简单总结样条就是一条可控的曲线。
B-splines
- Short for basis splines
- Require more information than Bezier curves
- Satisfy all important properties that Bézier curves have (i.e.superset)
B样条使用的比较多，这里的B就是奇函数的意思。可以理解成波恩斯坦多项式在时间$t$它的几个不同的项对不同的控制点做一个加权平均；我也可以理解成控制点位置对伯恩斯坦多项式进行一个加权求和，那么伯恩斯坦多项式就理解成一个奇函数。就相当于由不同的函数通过不同的方式组合起来形成别的函数，这个函数就是奇函数。
B样条是对贝塞尔曲线的一个扩展，它比贝塞尔曲线能力要更强。贝塞尔曲线动一个点整个一条曲线在任意一个位置都会发生变化，而这个在设计上大家都不太喜欢这个性质，而大家想要的是局部性，改变一个点至多影响这条曲线的某个范围内。
Important Note
In this course：
- We do not cover B-splines and NURBS
- We also do not cover operations on curves
(e.g. increasing/decreasing orders, etc.) - To learn more / deeper, you are welcome to refer to
Prof. Shi-Min Hu’s course: https://www.bilibili.com/video/av66548502?from=search&seid=65256805876131485
Surfaces
Bézier Surfaces
Extend Bézier curves to surfaces
对于曲面来说如何去得到它？曲线的概念可以延伸到平面上，贝塞尔曲面也是分段一块一块拼接起来，并且中间肯定不能有缝隙，这些要求应当如何去满足？这都是几何上要研究的比较困难的问题。
Bicubic Bézier Surface Patch
我们如何用贝塞尔曲线得到贝塞尔曲面？首先对于这个块来说可以理解成一个平面，中间有一种力把它拉上去，然后由4*4=16个控制点得到的，上面不同的黑点也可以理解成某一种臂拽着表面得到一定的形变。
Visualizing Bicubic Bézier Surface Patch
具体做法是在两个方向上分别应用贝塞尔曲线，首先在平面定义4*4的点，我认为它有四行，每一行拿出四个控制点得到一条曲线，这个曲线在时间$t$在不同的位置上。如果我们把得到的这四个不同的点认为是另一个贝塞尔曲线的控制点我们可以画出这样一条蓝色的线，给定另外一个时间$t$在不断扫过空间的过程中得到一个曲面。
Evaluating Bézier Surfaces
Evaluating Surface Position For Parameters (u,v)
For bi-cubic Bezier surface patch,
- Input: 4x4 control points
- Output is 2D surface parameterized by (u,v) in $[0,1]^2$
这里我们要找到贝塞尔曲面上任意一个点，需要两个不同的时间$t$：在水平方向找同一个时间$t$；找到四个点之后还要找一个时间$t$。它需要一个二维的控制的东西，我们管它叫(u,v)。
Method: Separable 1D de Casteljau Algorithm
Goal: Evaluate surface position corresponding to (u,v)
(u,v)-separable application of de Casteljau algorithm
- Use de Casteljau to evaluate point u on each of the 4 Bezier curves in
u. This gives 4 control points for the “moving” Bezier curve - Use 1D de Casteljau to evaluate point v on the “moving” curve
然后我们就完全可以用某一个$u$沿着四条曲线得到蓝色控制点，然后再给任何的时间$v$，在这四个点形成的蓝色曲线上找到最后的点所在的位置，这个点的位置就是曲面在(u,v)参数下面的一个位置。
Mesh Operations: Geometry Processing
- Mesh subdivision
- Mesh simplification
- Mesh regularization