GAMES102 Lecture 11 Geometry 2 (Curves and Surfaces)

这里回顾GAMES101 Lecture 11，这一讲介绍了曲线与曲面。

课程主页：

https://sites.cs.ucsb.edu/~lingqi/teaching/games101.html

课程作业：

http://games-cn.org/forums/topic/allhw/

课程视频：

https://www.bilibili.com/video/BV1X7411F744?spm_id_from=333.337.search-card.all.click

本讲内容

这一讲介绍的内容：

显式表示
曲线
- 贝塞尔曲线
- De Casteljau算法
- B样条等
曲面
- 贝塞尔曲面
- 三角形和四边形
- 细分、简化、正则化

计算机图形学中的显式表示

点云

点云是最简单的表示方法：点列表$(x,y,z)$；
轻松表示任何类型的几何图形；
适用于大型数据集（>>1 点/像素）；
经常转换成多边形网格；
难以在采样不足的区域中绘制；

多边形网格

存储顶点和多边形（通常是三角形或四边形）；
更容易进行处理/模拟，自适应采样；
更复杂的数据结构；
也许是图形学中最常见的表示；

曲线

曲线主要讨论的是如何找到一条光滑曲线经过多个点，我们首先来回顾贝塞尔曲线。

贝塞尔曲线

经过四个点的贝塞尔曲线如下：

在$\mathbf p_0$处的切线为$3(\mathbf p_1 -\mathbf p_0)$，在$\mathbf p_3$处的切线为$3(\mathbf p_3-\mathbf p_2)$，具体如何构造见后续讨论，这里先假设贝塞尔曲线可以描述为$\mathbf x(t), t\in [0, 1]$。

de Casteljau算法

de Casteljau算法是一个递归算法，以4个点为例，首先对$(\mathbf b_0, \mathbf b_1)$按比例$t$进行插值，然后同样对$(\mathbf b_1,\mathbf b_2),(\mathbf b_2, \mathbf b_3)$按比例$t$进行插值，这样会得到三个点，然后继续应用该算法即可，可视化的结果如下：

熟悉二项式定理话不难推出对于$n$个点的计算公式为：

$\mathbf{b}^n(t)=\mathbf{b}_0^n(t)=\sum_{j=0}^{n} \mathbf{b}_j B_j^n(t)$

其中：

$\mathbf b^n(t)$为$n$阶贝塞尔曲线；
$\mathbf b_j$为贝塞尔控制点；
$ B_j^n(t)$为Bernstein 多项式，计算公式为：
$B_i^n(t)=\left(\begin{array}{c} n \\ i \end{array}\right) t^i(1-t)^{n-i}$

贝塞尔曲线的性质

这里总结贝塞尔曲线的性质：

是对端点的插值
- 对于三次贝塞尔曲线：$\mathbf{b}(0)=\mathbf{b}_0 ,\mathbf{b}(1)=\mathbf{b}_3$；
与结束段相切
- 三次情形：$\mathbf{b}^{\prime}(0)=3\left(\mathbf{b}_1-\mathbf{b}_0\right), \mathbf{b}^{\prime}(1)=3\left(\mathbf{b}_3-\mathbf{b}_2\right)$；
仿射变换性质
- 对曲线的仿射变换等价于对控制点的仿射变换；
凸包属性
- 曲线在控制点的凸包内；
- 凸包示意图：