引言
GAMES101 现代图形学入门是由闫令琪老师教授。今天我们讲几何的最后一个部分，包括曲面细分、曲面简化以及曲面正则化，并且会提到一些Shadow Mapping。
Mesh Operations: Geometry Processing
- Mesh subdivision
- Mesh simplification
- Mesh regularization
上节课我们提到对于三角形面有一系列的处理方法，我们可以做三角形面的细分、增加更多三角形或简化减少、正则化，让这些三角形面变得更规则。
Mesh Subdivision (upsampling)
我们从最基本的三角形如何增加它的数量让它整个表示的曲面更加光滑开始。如果三角形数量非常少，就会变成当年很早期的第一代最终幻想7，人物的头发、手都是三角形，看得棱角分明。当然大家希望用到更多的三角形，随着现在显卡的发展，三角形的数量基本来说不是什么超级大的问题，可以处理很多的三角形。
这样一来我们有一个模型，我们希望它细节更丰富，当然可以引入更多三角形，这就和图像增大分辨率一个道理，让它看上去有更多的细节。
Mesh Simplification (downsampling)
第二个操作是网格的简化。如果说我们现在有一个网格非常非常复杂，而其实我们并不需要这么复杂的网格，那么我们就用少一点的网格数量去掉一些三角形，但是仍然要维持它们之间的连接关系。
Mesh Regularization (same #triangles)
另外一个话题是三角形有大有小，而细长的三角形会对渲染造成各种各样的不便，那么通常应对这种情况会对模型做一些正规化或正则化，让这些面看上去更像正三角形。在改进三角形本身质量的时候同时不能丢失模型本身的表示质量。
Subdivision
Loop Subdivision
Common subdivision rule for triangle meshes
First, create more triangles (vertices)
Second, tune their positions
细分自然是一个非常重要的操作。之前我们在说位移贴图的时候提到了细分，物体表面上应用一个贴图，这个贴图表示了它的相对位置移动或者高度场，然后我要把不同的高度应用在不同的顶点上，得到一个顶点被移动过复杂一点的凹凸模型。
然后我们说到要用很多的三角形才能赶上纹理本身的频率，所以说我们要用到很多三角形做细分。我们说的细分是两个事情：
- 分出更多的三角形
- 让这些三角形的位置发生一点变化，让模型变得更光滑一些
以Loop细分为例，第一步我们先把三角形数量增多。对于一个三角形连接三条中点就可以做出一个中间的三角形，而且拆成了四个三角形。
增多三角形数量之后还要调整三角形/顶点位置。特别的，对于Loop细分大家的做法就是把三角形的顶点区分成新的顶点和老的顶点，对于两种不同类型的顶点我们分别来改变它们的位置，让它们有一种规则来改变它们的位置。
Update
图中白点是新的顶点，它一定在一条边上，只要这条边表示的不是物体的边界它一定会被不同的三角形所共享，如图两个三角形共享一个白点。我们把共享的两条边设为$AB$，不共享的顶点叫做$CD$，下面Loop细分定义的规则是去把白点调整到$3/8 * (A + B)+1/8 * (C + D)$，这里的系数是简单的加权平均。
对于旧的顶点可以看到这个公式非常复杂，然而理解起来很简单。图中六个三角形堆在一块，中间虚线就是拆出来新的三角形，为了更新老顶点的位置肯定和周围相邻的点有关系。Loop细分提供了新的规则：一部分相信周围老的顶点周围的平均值；另外一部分它也愿意相信自己保留自己的属性，最后通过加权的方式合在一块。
Results
上图是Loop细分的结果，这样让整个模型得到一个光滑的效果，也再次印证Loop细分做的两个事情：细分与调整。
Catmull-Clark Subdivision (General Mesh)
Loop细分有一个前提是表示物体的面就是三角形网格，如果不是如图这种一半的情况，Catmull-Clark细分就可以把网格细分的非常好。
对于这个网格我们先定义一些概念。首先我们定义quad face为四边形面，那么Non-quad face就是非四边形面，比如这里两个三角形面就是非四边形面。另外一个概念是奇异点，定义为度（一个顶点和它相连的边数）不为4，例如圆圈点度为5，是奇异点，同理另一个圆圈点也是奇异点。
细分首先要引入更多的点/边，然后我再调整它们的位置。每一条边我都取它的中点，每一个面我也取中间的一个点并且边上的中点和面上的中点连起来就可以了：
图中原来的三角形取三条边的中点，面也取中点；连接中点和面中心点。经过一次细分后还有多少个奇异点呢？原本度为5的奇异点还是奇异点，新的点由于度数为3所以引入了两个新的奇异点，总计四个奇异点。可以发现只要是在一个非四边形面内点上这么一个点，由于我要和它每一条边都相连，所以形成的点一定是奇异点。
现在经过一次细分后，还有多少个非四边形面呢？这张图一数发现非四边形面全部消失了，三角形被拆成了三个四边形，也就是说经过一次细分所有的非四边形面都消失了，也可以理解为经过一次细分所有的非四边形面都变成了奇异点，以后的奇异点数也不可能再增加了。
如果我们再做一次细分会看到仍然还是四个奇异点，因为在第一次细分之后就不可能有非四边形面了。在细分的过程中这些点都会发生一些位置上的变化。
同样道理继续细分，位置继续发生变化就会变得越来越光滑。
Catmull-Clark Vertex Update Rules (Quad Mesh)
Convergence: Overall Shape and Creases
Mesh Simplification
我希望用更多的三角形来表示几何物体，但一些情况下比如游戏希望提升性能，不希望顶点太多，尤其是在移动端的应用上负担不起，我们不得不用简化的模型；其实来说在什么场合下用什么复杂程度的模型是有讲究的，一个最简单的事情是对于骷髅来说，想象仍然用这么多三角形，但我们在很远的地方去观察它根本不需要把这么细节的东西拿出来，比如三万个三角形和三千个三角形几乎无法区别出来，300个三角形离近了效果挺惨的但离远了效果还不错，这取决于我们在不同的情况下会选用不同复杂程度的几何模型。
Collapsing An Edge
Suppose we simplify a mesh using edge collapsing
首先肯定不能直接删掉一个三角形，物体上会留下各种洞。我们提供一种方法：edge collapsing，找到一条连着两个顶点的边，把两个顶点捏成一个点的过程就是边坍缩。
Quadric Error Metrics
- How much geometric error is introduced by simplification?
- Not a good idea to perform local averaging of vertices
- Quadric error: new vertex should minimize its sum of square distance (L2 distance) to previously related triangle planes!
边坍缩在实际做法中没有那么容易，比如我要坍缩哪些点，哪些边是重要的我不应该边坍缩，哪些边不重要我可以捏在一块儿？这个问题用二次误差度量来回答，如图所示蓝色顶点我们该放在哪儿才能保持蓝色三角形和原本灰色多边形基本保持轮廓形状的一致。
大家第一反应是平均试试，这个点和五个点都有关系，求五个点的平均可以发现原本面是比较鼓的，现在非常平，那肯定不对。人们引入了一种误差的度量，希望这个点放在某个位置上可以最小化二次误差。这个点和原本这几个面都有关系，那么我现在就要求这个点到原本这几个面距离平方和，我希望把这个点放在一个位置使得这个点到原本这几个面的平方和达到最小。
很明显这是一个优化问题。我不知道这个点在哪儿，但我可以优化它的位置找一个最优位置使得这个点到原本几个面的平方和距离最小，这就是二次误差的度量。
Quadric Error of Edge Collapse
- How much does it cost to collapse an edge?
- Idea: compute edge midpoint, measure quadric error
- Better idea: choose point that minimizes quadric error
- More details: Garland & Heckbert 1997.
有了二次误差我们如何坍缩这些边，这是一个非常重要的事情。如果我有一条边将其坍缩，我可以移动这个点的位置使坍缩对原本的面造成影响最小，也就是说我坍缩任意一条边之后，形成一个顶点可以放在最优的位置求出一个最小的二次度量误差。
Simplification via Quadric Error
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
- greedy algorithm… great results!
先把每一条边打上一个分数，这个分数就是它的二次度量误差，有大有小，从小的开始一个一个做坍缩。
Quadric Error Mesh Simplification
Shadow Mapping
An Image-space Algorithm
- no knowledge of scene’s geometry during shadow
computation - must deal with aliasing artifacts
Key idea:
- the points NOT in shadow must be seen both by the light and by the camera
Pass 1: Render from Light
Depth image from light source
Pass 2A: Render from Eye
Standard image (with depth) from eye
Pass 2B: Project to light
Project visible points in eye view back to light source
Visualizing Shadow Mapping
A fairly complex scene with shadows
Compare with and without shadows
The scene from the light’s point-of-view
The depth buffer from the light’s point-of-view
Comparing Dist(light, shading point) with shadow map
Well known rendering technique
- Basic shadowing technique for early animations (Toy Story, etc.) and in EVERY 3D video game
Problems with shadow maps
- Hard shadows (point lights only)
- Quality depends on shadow map resolution (general problem with image-based techniques)
- Involves equality comparison of floating point depth values means issues of scale, bias, tolerance
Hard shadows vs. Soft shadows