Lecture 11 Geometry 2 (Curves and Surfaces)
Curves 曲线
Bézier Curves 贝塞尔曲线
用一系列控制点定义摸一个曲线，这些控制点会定义曲线满足的一些性质
图中通过三个控制点，可以定义曲线起始点和结束点一定在\(p_0\)和\(p_3\)上，并且起始的切线和结束的切线一定都是\(p_0p_1\)方向和\(p_2p_3\)方向，这样就可以得到一条唯一的曲线（曲线不一定要经过控制点，取决于定义，我们只定义曲线一定经常起止点）
Evaluating Bézier Curves (de Casteljau Algorithm) 如何画出一条贝塞尔曲线
给定一系列任意多个控制点，怎么画出一条贝塞尔曲线？
de Casteljau算法
如图，给定三个控制点，生成的是quadratic Bezier（二次贝塞尔曲线）
曲线一定从\(b_0\)开始，在\(b_2\)结束，\(b_1\)决定了曲线往哪个方向弯曲
de Casteljau算法实则是要把在任意一个在\((0,1)\)之间的时间\(t\)，这个曲线的点对应在空间中这个平面的哪个位置找出来，把画整个曲线的算法转化成了找一个点
三个输入的点形成了两个线段\(b_0b_1\)和\(b_1b_2\)，在\(b_0b_1\)上认为\(b_0\)是\(0\)，\(b_1\)是\(1\)，\(b_0^1\)大约在\(b_0b_1\ 1/3\)的位置，取这个点，同理在\(b_1b_2\ 1/3\)处取点\(b_1^1\)，得到线段\(b_0^1b_1^1\)，再在线段\(b_0^1b_1^1\ 1/3\)处取一点\(b_0^2\)，此时已无法找到更多的线段了，则该点为这条贝塞尔曲线在时间\(t\)所在的位置
为什么贝塞尔曲线是显式表示？
显式表示要么直接定义，要么通过参数来定义，这里的\(t\)自然是一个参数
只需枚举所有可能的时间\(t\)，就能画出曲线
四个控制点的情况
很显然，de Casteljau算法是一个递归算法
当然控制点的移动会引起贝塞尔曲线本身的移动
代数上的形式
代数上的形式
在两个控制点之间线性插值得到新的点
给定时间\(t\)，贝塞尔曲线上的点可以表示为控制点的组合
公式中控制点的上标不是次方，是表示第几层计算
\[关于n阶贝塞尔曲线的伯恩斯坦多项式：\\ b^n(t)=b_0^t(t)=\sum_{j=0}^{n}{b_jB_j^n(t)}\\ n为贝塞尔曲线阶数，b_j为贝塞尔曲线控制点,B_j^n为伯恩斯坦多项式 \\ 其实就是描述二项分布的一个多项式\\ 伯恩斯坦多项式： B_i^n(t)=\begin{pmatrix} n\\ i \end{pmatrix} t^i(1-t)^{n-i} \]在空间中仍然可以得到贝塞尔曲线，只需把不同控制点输入成三维坐标即可，然后同样用伯恩斯坦多项式进行插值
伯恩斯坦多项式
伯恩斯坦多项式相当于对1自己的\(n\)阶展开，因此从图上可以看到，任意时间\(t\)，画一条竖线，四个竖线交点的值相加等于\(1\)
贝塞尔曲线的性质
-
贝塞尔曲线必须过起点和终点，以三阶贝塞尔曲线为例，b(0)=b_0;\ b(1)=b_3$
-
对于三阶贝塞尔曲线，起始位置的切线一定为三倍的\(b_1-b_0\)，\(b'(0)=3(b_1-b_0);b'(1)=3(b_3-b_2)\)
倍数取决于阶数
-
在仿射变换下，可以直接对顶点做仿射变换（旋转、缩放、平移），再对变换后的顶点画贝塞尔曲线，结果和直接对原曲线做仿射变换的一样的
因此要对一条贝塞尔曲线做仿射变换，只需对其控制点做仿射变换，再重新画曲线即可
只对放射变换有如此性质，如对投影就不是这样
-
凸包性质
画出的贝塞尔曲线一定在所有控制点形成的凸包（能够包围几何形体的最小 凸多边形)内
Piecewise Bézier Curves 逐段贝塞尔曲线
Piecewise是逐段的，相当于一段一段地考虑贝塞尔曲线
当控制点多的时候不容易控制曲线，来得到一些我们想要的形状
于是我们可以一次用较少控制点，定义一段贝塞尔曲线，然后将多段贝塞尔曲线连起来。特别的，人们喜欢用四个控制点，也就是三次贝塞尔曲线(Piecewise cubic Bézier)
（图中为了美观没有画出\(b_1b_2\)线段）
几何连续
当第一段终止点等于第二段起始点\(a_n=b_0\)，则称为\(c^0\)连续(continuity)
切线连续
如何保证两段贝塞尔曲线连接处光滑呢（切线连续：大小一样，方向相反）
我们可以将连接处的A贝塞尔曲线\(b_2\)和B贝塞尔曲线\(b_1\)相距连接点等距且共线（导数连续）
\(C^1 continuity: a_n=b_0=\frac{1}{2}(a_{n-1}+b_1)\)
\(C^1\)连续
再高阶的连续如曲率连续等等
Spline 样条
连续的曲线，由一系列控制点控制，在任意一点都满足一定的连续性
简单总结：一个可控的曲线
B-splines (basis splines) B样条 基函数样条
相当于对贝塞尔曲线的拓展
B样条具有局部性，改变一个控制点，至多影响一定范围内的曲线，不同于贝塞尔曲线改变一个控制点就会改变整条曲线，相较于分段贝塞尔曲线，B样条不需要分段
比B样条更复杂的有NURBS（非均匀有理B样条）
Surfaces 曲面
Bézier Curves 贝塞尔曲面
在平面上定义\(4\times4\)个控制点，每四个控制点在不同时间\(t\)产生的四个控制点，认为这四个新的控制点是另一个贝塞尔曲线的控制点，就可以画出另一条贝塞尔曲线
水平方向做一下得到四个控制点，再用这四个控制点在竖直方向做一下
在水平方向上走，需要一个时间\(t_1\)，在竖直方向上也需要一个时间\(t_2\)，所以需要一个二维一个控制，我们叫其\(uv或t_1t_2\)
要找点\((u,v)\)的位置，只需先找时间为\(u\)时，四条贝塞尔曲线上的点，将这四个点作为控制点，再找时间为\(v\)的点即为所求。
通过\((0,1)\)范围内的坐标\(uv\)可以映射到任意一个点，所以我们说贝塞尔曲面是显式表达
不同贝塞尔曲面怎么拼在一块，保证边界严丝合缝？复杂
Mesh 网格
用来表示空间中面的形状的最普遍方法是Mesh 网格（三角形、四边形...）
以三角形为例
用三角形来描述空间中各种各样不通风的表面，自然而然对于它形成的网格会有一定的操作——几何处理
Mesh subdivision 网格细分 (upsampling)
用更多三角形获得更光滑的表面
对triangle meshes三角形网格的一般细分规则：
首先，引入更多三角形（顶点）
第二，调整顶点位置
Loop Subdivision 细分曲面
-
将每个三角形分裂成四个
-
根据权重确定新顶点的位置
-
对于新的顶点
对于一个新的顶点（图中白点），它一定会出现在一条边上，只要这条边不是物体的边界，该点就会被不同的三角形所共享（图中\(ABD\)和\(ABC\)），找到这两个三角形共享的边叫做\(AB\)，不共享的顶点叫做\(C\)和\(D\)，则将新生成的点位置调整到\(3/8*(A+B)+1/8*(C+D)\)（一种加权平均）
-
对于旧的顶点
一部分情况下保留自己原先的位置，一部分情况下改变位置，根据该顶点的度\(n\)（顶点连接的边的数量）判断
再考虑\(u\)（仅仅是跟度\(n\)有关的一个数）
则新的顶点位置为
\[(1-n*u)*original\_position+u*neighbor\_position\_sum \]（如果该点连接了很多三角形，则该点不重要，第二项占比重大，反之第一项占比重大）
-
Catmull-Clark Subdivision (General Mesh)
Loop Subdivision 适用于三角形网格，对于一般网格，可以用Catmull-Clark Subdivision
我们定义Quad face 四边形面、Non-quad face 非四边形面和Extraordinary vertex 奇异点（度不为4的点）
我们取三角形三个边的中点以及面取一个点（可以是重心或任意点，反正之后要调整位置），连接边上的点和面中心的点（假设取重心）
现在有四个奇异点（原本两个奇异点，新产生了两个奇异点），但非四边形面全部消失了，可以理解为非四边形面转化成了奇异点
因此Catmull-Clark算法有一个性质：在细分之前有多少非四边形面，细分一次之后就会转化成多少个奇异点。
然后再继续进行细分，因为已经没有非四边形面了，因此不会有新的奇异点
随着细分次数的增多，顶点增多会导致曲面越来越光滑
Catmull-Clark细分公式
FYI：Catmull-Clark Vertex Update Rules (Quad Mesh)
根据点的位置更新（在面上的新点、在边上的新点、旧的顶点）
Mesh simplification 网格简化 (downsampling)
保持基本形状的情况下，用更少三角形来描述它（控制损失在一定范围内）
edge collapsing 边坍缩
要判断那些边重要，不能进行边坍缩，那些边不那么重要，可以进行边坍缩
Quadric Error Metrics（二次误差度量）
二次指的是平方而不是做两次
这里简化到二维举例
如图要删去上面三个顶点，用一个新顶点代替它们，若是新顶点等于五个原顶点求平均（图1蓝点），则发现新三角形太小，不符合原三角形轮廓，若是用被代替的三个顶点求平均，也还是比原三角形轮廓小
Quadric error（二次度量误差）为新顶点到与其相关联的面的距离的平方和
当二次度量误差最小时，即为新顶点位置
Quadric Error of Edge Collapse
对于一个模型，可以通过边坍缩的方式来简化，那如何决定坍缩那条边呢？
答案是从二次度量误差最小的边开始坍缩，再坍缩第二小的、第三小的...
先给每条边打上一个分数，分数为这条边的二次度量误差，再从分数小的边开始坍缩
-
有一个问题，当一条边坍缩时，可能会改变别的边的二次度量误差
所以需要对受影响的边更新二次误差，因此应选用优先队列/堆作为存储二次度量误差的数据结构（允许求最小且允许动态更新）
我们是在对局部做最优解的同时试图找到全局最优解，是典型的贪心算法
Mesh regularization (same #triangles)（正则化）
让三角形不至于出现特别尖、特别长的三角形，让三角形基本变成更正三角形相似的一些三角形
标签：11,Surfaces,坍缩,曲线,贝塞尔,控制点,顶点,Lecture,三角形 From： https://www.cnblogs.com/Tellulu/p/18092222