Implicit
隐式的集合，拿了空间中的一个点，为了表示集合的一个面。不会告诉点具体在哪，会告诉点所满足的关系。满足一定关系的点，都在一个表面上，把点做个归类，例如球的公式。
DIstance Function
对于一个集合，不描述表面，而表述一个点的最近距离。对距离函数做融合、Blend。
距离函数：空间中任何一个点、到表述的集合形体上的任意一个点的最小距离，距离可正可负。如果点在物体外，距离为正，如果点在物体内，则可以算出点到表面的最小距离，且距离为负。可以把空间中任意一个点都定义成一个值。
如上图，如果把两个球的距离函数都算出来，就可以做个Blending。再恢复成原来的物体。
第一行假设A左边三分之一是黑的，右边是白的，B同理，左边三分之二是黑的，那么Blending之后希望得到的是左边三分之一平均后是黑的，中间三分之一是灰的，右边三分之一是白的。怎么求Blending呢？可以Blend 两个距离函数。
第二行0左边是距离为负，右边是距离为正。Blend之后，0的位置就是边界，也就是我们求出来BLend形状的边界。
得到Blend之后的距离函数，怎么样恢复成表面呢？那就把0的位置全找出来
距离函数可能不太好用式子来表达，还可以通过某种方法来表达，例如水平集。函数的表述写在格子上，在中间0的地方，就可以把整个函数试图描述的物体表面提出来。
函数为0可以得到一条曲线，0.1 处也可以得到一条曲线。这种概念在地理得到广泛应用：等高线。水平集关注的是在哪里等于0，例如双线性插值来求。
水平集也可以定义三维中的格子，这就和纹理联系上了。如果我们有个三维的纹理，或者是人体的不同位置、密度。那么怎么提取出物体的表面呢，我们可以根据密度等于某个密度，找到所有的对应的位置，从而找到表面。
水花也可以通过水平集/距离函数来描述。
Fractals （分型）
分型是指自相似，自己的一个部分和整体长得像，和递归概念类似。例如雪花、六边形的边上又有六边形。
中间的是一种植物、西兰花。凸起里放大看又有凸起。是自然界分型的一个例子。在渲染的时候会引起强烈的走样，因为变化的频率实在太高。
Implicit Representations - Pros & Cons
Pros：
- compact description (e.g., a function)
- 对于存储有利，一个公式就能描述形状
- certain queries easy (inside object, distance to surface)
- 小于0还是大于0
- good for ray-to-surface intersection (more later)
- 很容易求与光线的求交
- for simple shapes, exact description / no sampling error
- easy to handle changes in topology (e.g., fluid)
Cons：
- difficult to model complex shapes
Explicit
Point Cloud
需要特别多的点，三维扫描的输出一般都是点云。这样就会涉及一个问题：给一个点云，如何将其变为三角形面？有很多研究在做。
点云密度低就很难画，所以不会很多用点云。有不同的Shading方法，就会看到不同连续的面。
Polygon Mesh
The Wavefront Object File (.obj) Format
我们经常在图形学中是如何表示这种三角形面形成的物体的？
文本里面有一堆点、纹理坐标和法线来组织起来。左图描述的是一个立方体，前八行空间中有八个点。右边vn开头是法线，立方体有六个面、六个法线，自动建模有很多冗余的地方（右图有八行），例如29、30行是一回事，不考虑数字精度问题。再定义12个纹理坐标，也有冗余。
连接方式通过 f（face）来定义，哪三个点连接形成三角形。（5/1/1）（v 顶点， vt 纹理坐标，vn 法线）。而一行有三个点，来描述一个三角形。
Curves
无限放大区域，会看到都是光滑的。
Bézier Curves（贝赛尔曲线）
用一系列的控制点，去控制某一个曲线。
通过四个点，可以定义曲线的起始点和终点一定在P0和P3上，并且起始切线在P0 P1方向，结束切线在 P2 P3方向。曲线不一定要经过控制点。
怎么画呢？
用任意多个点，怎么画出贝赛尔曲线？
在任意一个时间 t （0~1之间），找出曲线的点在平面上哪一个位置即可。将画曲线的事情转化为找一个点的算法。
左边的 b10 点在时间 t 时点的位置，右边b11则是同一时刻另外一个点的位置。
将其连起来，再在线段上面找 t 时间的位置，点上一个点，这个点就是贝塞尔曲线在时间 t 所在的位置。
因为显式表示要么是直接定义，要么参数定义，所以 t 是参数，所以贝塞尔曲线是显式表示。
原本四个点，在这四个点三个线段上面再找 t 时刻的位置，b10 b11 b12，再连起来。这样就将问题规模变成了三个点。递归的解出最后一条线段的时候 t 时刻的点的位置。
画一条竖线，四条线的交点坐标加起来都等于1
通过定义一系列跟时间有关的多项式，来对不同的控制点进行插值（组合也是插值），得出一个新的点，这个点就是曲线上的点。这个概念不仅被应用在贝赛尔曲线上，也应用在其他更复杂的曲线上。
四个控制点贝塞尔曲线的性质：
简单来说，“仿射变换”就是：“线性变换”+“平移”。
贝塞尔曲线在仿射变换下有很好的性质：
贝塞尔曲线可以在不同的顶点做仿射变换，再重新对变换之后的顶点再画一个贝赛尔曲线，这个贝塞尔曲线一定和以前的贝塞尔曲线一样。
这给了我们一个很好的性质：
如果我们想对贝塞尔曲线做仿射变换，那只需对几个控制点做仿射变换，对仿射变换后的控制点重新画一条贝赛尔曲线即可。这样我们不需要对曲线每个点都记录着。但不一定对其他变换也如此，例如投影就不一样。
凸包（Convex Hull）
贝赛尔曲线一定在所有的控制点的凸包内。在二维欧几里得空间中，凸包可想象为一条刚好包著所有点的橡皮圈。
如果所有控制点都在一条线上，那么贝塞尔曲线可以根据凸包性质可得，那么贝塞尔曲线一定被限制在这条线上，一定是这条线自己。
Piecewise Bézier Curves
曲线不直观，不好被控制点控制。因此可以用很少的点来定义一段曲线，再把这些曲线连起来。
逐段的贝赛尔曲线每一段曲线都可以由四个控制点控制。
那么怎么保证曲线是光滑的？要保证导数连续
C1 连续也可称为一阶导数连续。C2 连续则为二阶导数连续。
其他种类的曲线
在任意的一个地方都满足一定的连续性。
上图是拿一个树枝一样的东西，再拿其他东西固定住，保证样条会经过固定的点。可控的曲线成为样条。
Other types of splines
B-splines（极其复杂）
- Short for basis splines
- 可以理解成：用伯恩斯坦多项式，在时间 t ，在几个不同的项，对不同的控制点做加权平均
- 也可以理解成：用控制点的位置对伯恩斯坦多项式进行加权求和。
- Bernstein多项式在这里充当着基函数的角色。
- Require more information than Bezier curves
- B样条是对贝赛尔曲线的一个扩展，比贝塞尔能力更强。
- 对于贝赛尔曲线，如果有十个点，如果动了一个点，那么曲线的其他部分也会发生变化。这对其他一些设计不太友好。可能只需改一些地方，希望有局部性的性质。局部性是指：改了一个点，我知道这个曲线最多改的范围内。（分段贝赛尔曲线就有这种性质）
- Satisfy all important properties that Bézier curves have (i.e. superset)
- 与贝塞尔曲线分析方法完全一样。算起来更复杂，还有一种样条叫 NURBS，相当于B样条更延伸的一部分。
To learn more / deeper, you are welcome to refer to Prof. Shi-Min Hu’s（胡事民） course:
曲线曲面方面说的透彻，也非常难。
Bézier Surfaces
怎么用贝赛尔曲线来得到贝塞尔曲面呢？
相当于双线性插值的理解，在两个方向上分别应用贝赛尔曲线即可。
- 首先，在平面上定义 4*4 个控制点，每一行四个控制点能得到一条曲线。
- 在这个曲线上，在不同的时间 t 会在不同的位置
- 如果把四个不同的点，认为是另一条贝塞尔曲线的控制点（图中蓝色的线）。
- 再给定时间 t （不同的时间 t），线不断地扫，就会得到一个曲面。
水平方向上需要一个时间 t，四个点连成一个曲线还要有一个时间 t，所以它是一个二维的(u,v)控制的东西。
因此我们可以用某一个 u 沿着四条得到的曲线上，得到时间 u 点在哪，就可以得到四个蓝色的点。再给一个 v，在四个点的曲线上找时间 v，就可以找到这个曲面在 u,v 参数下的位置。参数 u,v 在 0,1中就可以映射到曲面上任何一个点，因此贝塞尔曲线是显式地表示，因为是由参数控制的。
当然面的几何形状，用的最普遍的方法，还是 mesh 网格。对网格的操作，就是几何处理。
Mesh Operations: Geometry Processing
- Mesh subdivision 网格细分，图2→图3
- Mesh simplification 网格简化 图3→图4
- Mesh regularization 正规化 让三角形不会出现特别尖特别长的三角形，这样会有很不错的性质。
Mesh subdivision 网格细分
Common subdivision rule for triangle meshes
- First, create more triangles (vertices)
- Second, tune their positions
Loop 细分其中的Loop跟循环没关系，是发明人的姓。
Loop Subdivision - Loop 细分
细分之后，就要调整三角形的位置。对于Loop细分，把三角形顶点区分成新顶点和老顶点。
对于新顶点，被两个三角形共享的顶点，可以通过下图公式来进行加权平均。A和B离白点近，因此贡献更多一些。
对于旧的顶点，原来周围旧的顶点都会有贡献，自己也会有贡献。
定义两个值：
- n：顶点的度（图论中的度，下图中度为6，连接了六个顶点）
- u：考虑到顶点的度，定义了一个公式。
下图的公式（1-n*u）是指这个顶点连的三角形越多，自己越不重要
一个三角形分成四个，顶点位置都经过细微调整。越细分，越密越光滑。
如果模型原先是三角形网格，才能用 Loop 细分。如果不是，下面 Catmull-Clark 细分的非常好。
Catmull-Clark Subdivision (General Mesh)
- quad face：四边形面
- Non-quad face：非四边形面
- Extraordinary vertex（奇异点）：度不为四的点，都是奇异点。
细分步骤：
每一条边取中点，每一个面也取中点，将他们都连起来。
下图左上角的大四边形被分成了四个四边形
引入的新的点，度为3。因此细分后引入多两个奇异点，现在一共四个奇异点。
细分后，所有非四边形面都消失了。也就是说奇异点数不可能再增加。
现在知道了如何增加新的点，下面讲讲怎么调整点。
点被区分为三类：面中心的点（下图左上）、边中心的点（下图右上）、老的点（下图下方）。
老的点根据四边面中心的点来调整。
Mesh Simplification 曲面简化
Goal: reduce number of mesh elements
while maintaining the overall shape
（下图 Flat Shading）
- 可能不得不简化模型，例如在移动端平台上
- 要看场合用相应复杂度的模型。下图下方，如果我们很远去观察骷髅，就不需要太多三角形，例如三千个的三角形和三万个三角形没啥区别，三百个三角形的也不错。
Mipmap 给了我们图像层次结构，如果我们用了简化的模型，用 Mipmap 较高层的像素点就行，就不需要把最底层最细的像素点都平均出来。这个意义来看，层次结构的几何，和层次结构的图像是差不多的。
但几何的层次结构是很难做的，特别是涉及到不同类型的几何之间，相互变化的时候。例如近了用三万个远了用三千个，那什么时候切换，切换的时候变化会不会太大？需要做过渡的话，过渡要怎么做？从一个几何形状到另一个几何形状，没有什么三线性插值，这块是图形学界造成困难的话题。
Collapsing An Edge 边坍缩
简化的其中一种方法。
就好像把两个点捏成一个点，这个边就不存在了。
要坍缩哪些边？哪些边是重要的？
二次误差指的是平方
上图左下中，对五个点求平均得到的点来代替，或者上面三个点求平均得出的点，都不太能用，因此使用误差度量来做。
二次误差：找一个最优的位置，使得新顶点到几个面距离的平方和达到最小。
对于整个模型，有这么多的边，我都假设如果我坍缩这条边，并且我把坍缩后的点放在最佳位置上，会达到多大的二次度量误差。也就是说每一条边，我都可以假设如果我坍缩它，有多大的误差。
这样我可以先坍缩误差最小的，然后坍缩第二小的......
于是有了下面的算法：
Iteratively collapse edges
Which edges? Assign score with quadric error metric*
- approximate distance to surface as sum of distances to planes containing triangles
- 为每一条边都打上分数，分数就是其二次度量误差。
- iteratively collapse edge with smallest score
- 从误差小的开始，一个一个地坍缩。
- 注意：坍缩了一条边之后，会影响其他边的二次度量误差。
- 最好有某种数据结构可以取最小值（O1），有可以动态地以最小的代价去更新其他受影响的元素。——优先队列（堆）
- greedy algorithm... great results!
- 我们以不断的对局部做最优解的方式，试图找到全局的最优解。——贪心算法
(Garland & Heckbert 1997)
奶牛眼镜处较平缓，因此坍缩的地方的多。