GAMES101-Note5-Geometry

课程链接：GAMES101-现代计算机图形学入门-闫令琪
本篇笔记为本人学习上述课程总结之笔记，仅供交流

represent_geometry

几何的表示方法

几何分为隐式几何（Implicit geometry）和显式几何（Explicit geometry）。我们有不同的方式来表示不同的几何。我们从隐式几何表示开始。

Implicit Geometry

所谓隐式曲面指的是并不会告诉你任何点的信息，而是去表达这些点满足的关系。比如说最典型的球的公式:
\[x^2+y^2+z^2=1\] 我们都知道这是一个球的公式，但是除去一些我们已经知道形状的公式，其余的从公式上很难看出来这是一个什么形状。一般地的我们会把隐式曲面的代数方程写作：$f(x,y,z) = 0$
则上述球体为$f(x,y,z) =x^2+y^2+z^2-1$

对于隐式方程来说因为没有给出任何点的信息，因此如何采样到曲面上具体的点是一个很难的问题，如下图这样一个例子: implicit 例如，我们如何找到令$f(x,y,z) = 0$的点呢？这是一个相对困难的事，也很难看出来，我们将其结果绘出如上图所示，它其实是一个圆环，仅从函数来看很难看出它是一个圆环的结构，也就是说隐式几何的表示不直接。
implicit2
当然隐式几何也有好处，它判断一个点与表面的关系非常容易，只需要将点代入到函数中，根据结果的正负值即可判断该点在表面内、在表面上还是在表面外。例如，我们判断点$(3/4,1/2,1/4)$与表面$f(x,y,z)=x^2+y^2+z^2-1$的位置关系，将其代入得$f(x,y,z)=-1/8<0$，因此可知该点在表面内。

Explicit Geometry

相对地，图形学还有显式几何表达，比如之前我们用到的三角形，就是真的将表面显式地表达出来。还有一种显式的表达方法，听起来不直观，称为通过参数映射的方法定义的表面。例如我们在平面上定义一个空间，上面任意一个点用$(u,v)$表示，并且我们可以定义，对于任何该空间中的点的坐标都可以映射到对应的三维空间中的点，也就是说可以定义一个函数，输入的是$(u,v)$，输出的是空间中的$(x,y,z)$，如果把所有的$(u,v)$都计算一遍，就可以找到对应空间中的表面，例如下图所示的马鞍面。因此显式表示方法，要么直接给出，要么通过参数映射的方法来定义表面。
explicit

举个例子，$f(u,v)=((2+\cos u)\cos v,(2+\cos u)\sin v,\sin u)$，（因为我们给出了的对应的具体表示方法，因此这是一种显式表示方法）我们想求出在表面上的点。求出后会发现这是一个与之前的案例同样的圆环。可见，隐式的表示方法并不容易想象出表面的实际样子，但是对于显式的表示来说很容易。
explicit2 但是，显式表达中，检测点与表面的关系会相应的变难，例如，去判断点与表面的位置关系就会变得很难。

因此，有些问题适合隐式的表示方法，有些问题适合显式的表示方法，没有最好最完美的表示方法，我们要根据需要去选择。Best Representation Depends on the Task!
“I hate meshes. I cannot believe how hard this is. Geometry is hard.” – David Baraff (Senior Research Scientist, Pixar Animation Studios)

Implicit Representations in Computer Graphics

隐式的表示方法还有很多，在这里再介绍几种。

more_implicit

Algebric Surfaces(Implicit)

最简单最直接的是Algebric Surfaces(Implicit)，即使用数学公式去表示表面。前面提到，数学公式表示曲面的严重问题就是不直观，圆环的表达就已经很不直观了，对于一个复杂形状，想要表达出来就极其困难。

algebric_surfaces

Constructive Solid Geometry(Implicit)

另外一种表示方法是CSG (Constructive Solid Geometry, Implicit) 表示方法，它是通过基本几何的基本运算来定义新的几何，例如一个圆柱和球，做布尔运算，通过几何之间的求交集、叉积和并集就能得到新的较复杂的几何，如下图所示。这种操作得到了非常广泛的应用，在不同的建模软件中都支持这种方法，通过这种方法可以把简单的几何变成复杂的几何，仅通过几何之间的相互关系来得到，最后还可以写成表达式，因此它仍然是隐式的方法。

CSG

Distance Functions(Implicit)

还有一种表示方法叫距离函数(Distance Functions, Implicit) 表示方法。对于任何一个几何，我们不去描述它的表面，而是去描述空间中的点到这个表面的距离，先看一个例子，如下图所示，当两个球逐渐靠近时，两个球的形状发生变化，融合在了一起，最终变成一个球，在这个过程中，形状和拓扑结构都发生了变化，这就是通过对几何的距离函数做融合所形成的结果。

重申一下，距离函数是指：空间中的任何一个点到想要表达的表面的最近距离，这个距离可以是正的也可以是负的，即有向距离(Signed Distance) 例如在表面外为正，表面内为负，这样空间中任何一个点都可以定义出一个值，把这两个不同的物体的距离函数都算出来以后，就可以把两个距离函数做一个融合，再恢复出原来的物体，就可以做出融合的效果。

distance_func

以上图这样一个二维平面的例子，定义空间中每一个点的SDF为该点到阴影区域右边界的垂直距离，在阴影内部为负，外部为正，因此对于A和B两种阴影来说的SDF分别如上图下半部分所示。有了SDF(A)，SDF(B)之后对这两个距离函数选择性的进行一个blend也就是做一些运算得到最终的距离函数，这里采用最简单的SDF = SDF(A)+SDF(B)来举例，这样看起来直观一点。注意：并不是所有的SDF都是用加法求得，往往方法会更加复杂。
最终得到的SDF = 0的点的集合就是物体的新表面，对该例子来说，就是两道阴影之间中点的一条线。

通过距离函数，我们可以表达出一些复杂的、圆滑的几何，如下图所示。那么距离函数得到的函数，我们要如何把它恢复成表面呢？只需要把距离函数对应为0的位置全找出来即可。但是距离函数不太容易写成一种解析的形式，但是只要我们通过某种方法表示出来就可以了。

distance_func2

Level Set Methods(Implicit)

水平集方法(Level Set Methods, Implicit) 和距离函数几乎完全一样，仅仅是函数的表述是写在格子上的（原因是某些函数不太好用$f(x)$表示出来）。对该面内的每一个点利用已经定义好的格子值进行双线性插值就可以得到任意一点的函数值，根据双线性插值我们找出所有=0的点作为曲面。当然也可以找到其他的曲线，例如通过$f(x) = 0.1$得到另外一条曲线。

level set

这个概念其实在地理上早已得到广泛的应用，即等高线，它就是为了描述一个函数在不同的位置有相同的值，在这里对于这样一个例子来说很简单。当然水平集也可以定义在三维中的格子，而这就与我们前面说的纹理关联上了，如果有一个三维的纹理表述的是人体不同位置的密度，那么我们如何从这些三维信息中提取表面呢？我们可以让这个密度函数等于某个值，比如，我们可以找出所有的点，就能表示出一个表面，这就是水平集在三维空间中的运用。

levelset2

再比如水滴滴入水面造成水花的过程，我们该如何去描述它，这里也可以通过水平集的方法将水滴和水滴融合在一块，并提出融合之后的表面的样子。

levelset3

Fractals(Implicit)

几何还有一种特殊的描述方法，称为分形（Fractals）。分形就是自相似的意思，即自己的一个部分和整体非常相似，在计算机中和递归一个道理。例如雪花如果放大看会发现每一个六边形边都会有更小的六边形，即不断地自我重复所形成的形状。下图中中间的图是一种西兰花，仔细观察会发现它有很多凸起，如果放大去看会发现每一个凸起里又有很多更小的凸起，所以它是一个自带分形的植物，它是自然界中分形的例子。它在渲染中会引起强烈的走样，因为变化频率太高了，因此这样的几何对渲染来说是一个非常大的挑战。
$fractals$

Implicit Representations - Pros & Cons

接着总结一下隐式表达的优劣。好处有：描述容易（比如用一个函数），有利存储；有利查询（判断位置关系）；利于做光线求交（当然对显式来说也并不难）；对于简单的物体可以严格地描述出来，没有采样误差；容易控制拓扑变化等。坏处就是难以描述复杂形状的几何。这也是为什么我们还需要显式的表达。

implicit_con

Explicit Representations in Computer Graphics

显式表达也有很多种方法，例如三角形表达、贝塞尔曲面、细分曲面、NURBS、点云等。

explicit3

Point Cloud (Explicit)

最简单的显式几何表示方法是点云，点云的表示不考虑表面，全部都表示成点，只要点足够密，自然而然就看不到点与点之间缝隙，图像上就能看到一个表面。表示一个点很容易，用$(x,y,z)$就够了，点云就是$(x,y,z)$的列表，例如下图右侧，雕塑的上半部分点云的密度非常大，因此就能看到物体的表面，随着点云变得越来越稀疏，就看不到物体的表面。所以如果想用点云来表示一个非常复杂的模型，就需要特别密集的点。当然，理论上它可以表示任何类型的几何，只要点足够密即可。通常来说人们会做一些三维空间中的扫描，其输出就是点云，但这就会涉及到一个问题，给定足够多的点云，如何把它们变成三角形面，这里就有很多研究在做了。正常情况下，如果点云密度很低，自然而然就不太容易将其表达成表面，这也是为什么人们用点云去表示的情况不是特别多。
pointcloud

Polygon Mesh (Explicit)

在图形学中，得到最广泛应用的就是多边形面（通常是三角形或者四边形），它非常易于表示，任何形状都可以拆成很多小的三角形，如下图所示，类似胶囊的几何，两端三角形较密集，较规则，中间部分较稀疏，较细长。不过显然，使用三角形表达就自然涉及到一些连接关系，这就相比于点云造成了一些困难，但也有更多的研究。重申一下，多边形是图形学中最广泛运用的图形表示方法。

polygon

这里既然提到了三角形面，就顺便提一下我们平常如何表示三角形面形成物体的。如下图所示，这是一种特定的文件格式，这一种文件可以存储一个物体或一个场景，这种文件称为The Wavefront Object File (.obj)，注意这里的文件虽然后缀是.obj但是和编译时生成的.obj文件不是一回事。它其实是一个文本文件，这个文本文件里，只是把空间中的顶点坐标、法线、纹理坐标分开表示，然后再把它们组织起来。
下图所示示例，这个文件描述了一个立方体，一个立方体总共有8个空间点，它们分别被用$‘v’$表示的三个坐标来表达，也就是左图中的第3-10行。然后，一个立方体有6个面，所以它只有6种不同的法线，因此文件同样定义了6种不同的法线，为右图的第27-34行，这里有8行是因为在自动建模中有冗余的地方，比如29行和30行不考虑数值精度的时候其实是一回事，其实只定义了6个法线。再然后，它定义了24个纹理坐标（一个面有4个点），为左图第12-25行，当然这里也有冗余，其实不用定义这么多。最后，这个文件定义了它们之间的连接关系，也就是说哪三个点形成了一个三角形，用$‘f’$(face)表示，每一个数值的含义是为 v / vt / vn的索引，比如第36行的含义是：使用第5个顶点、第1个顶点和第4个顶点构造一个三角形，并且这三个顶点分别用第1个、第2个和第3个纹理坐标，并且都使用第1个法线。这样一来我们就可以通过这种形式来定义一个网格了。

obj format

Curves

下面我们从曲线开始，来讲解显式表示的其他方法。我们从一个例子开始看，如图为在Maya建模软件中绘制的曲线，摄像机会沿着该路径运动，并且会改变它的朝向，这些曲线我们可以定义好它。

curve

除此之外，使用曲线还可以定义一些字体，通过添加控制点的方法来定义曲线，这种曲线如果被无限放大，我们会看到任何地方都是光滑的，不会出现格子的情况，这就是我们接下来要说的贝塞尔曲线，一种显式的表示方法。

vectorfont

Bezier Curves

贝塞尔曲线的目的是用一系列控制点去定义某一条曲线，这些控制点会定义这条曲线所满足的一些性质，比如说从$p_0$开始，并且沿着从$p_0$到$p_1$的方向为切线向前走，同样道理这个曲线会在$p_3$处结束，并且结束时，其切线一定是沿着$p_2$到$p_3$的方向向外的。（图中会发现切线的长度也被定义了，即系数$3$，这里后面会做解释）总之，通过这四个点，我们可以定义曲线的起始点和终点一定为$p_0$和$p_3$，并且起始方向和结束方向为$p_0p_1$和$p_2p_3$，这样就会得到一条唯一的曲线。当然，曲线并不一定经过中间的控制点，这取决于我们如何定义它，只定义曲线一定经过控制点集中的起、止点。

bezier

de Casteljau Algorithm

那么我们怎样才能画出一条贝塞尔曲线呢？我们可以用任意多个控制点（当然数量大于等于2）去画出一条贝塞尔曲线，这里用到的算法就是de Casteljau Algorithm。如下图所示为一条由三个点形成的贝塞尔曲线，称为二次贝塞尔曲线（quadratic Bezier）。

画出这条曲线前，我们知道$b_0$决定了这条曲线从哪开始，$b_1$决定了它往哪个方向弯曲，$b_2$决定了曲线的终点。
我们假设这条曲线的起点为时刻$t=0$，它的中点时刻为$t=1$，那么如果我们想画出这条曲线，实际上就是求出这条曲线上的点在$[0,1]$中任意一个时刻$t$所处的位置。de Casteljau Algorithm就是告诉我们该如何找出这个点，它将画出整个曲线的方法转化成了找一个点的问题。

如上图所示，三个点形成了两条线段$b_0b_1$和$b_1b_2$，假设方向也是输入顺序。假设给定了时间$t$，$t$在$b_0b_1$上，那我们认为在$b_0$是0，在$b_1$是1，$t$假设约等于$\frac{1}{3}$，那么我们就找出线段$b_0b_1$上$\frac{1}{3}$的点$b_0^1$。同样道理，我们在$b_1b_2$上也能找出位于$\frac{1}{3}$处的点，记为$b_1^1$，这样一来我们就找到了三个点所形成的两条线段上的两个点。
那么如果我们把新得到的两个点连起来，再去找这条线段$b_0^1b_1^1$上位于$\frac{1}{3}$处的点，这时发现找到这里就结束了，因为无法再找出更多的线段了，那么这一个点就是贝塞尔曲线在时间$t$所在的位置。最后我们需要枚举所有可能的时间$t$，即可画出曲线。

显式表示要么是通过直接定义，要么通过参数来表示，这里的$t$就是一个参数，因此贝塞尔曲线是一种显式表示方法。可见de Casteljau Algorithm是一个很简单的递归算法，我们可以一直找，直到找到最后一个点。

bezier6

同样地，如果给定了4个点$b_0b_1b_2b_3$，用这4个点来定义一条贝塞尔曲线，这条曲线必经过和$b_0b_3$，那么我们该如何画出它呢？假设找一个时间$t$，得到了，对于每条线段都能找到点$b_0^1b_1^1b_2^1$，然后再连起来，原本四个点三条线段，连起来后变成了三个点两条线段，同样地，再对这两个点取的位置$t$，即可得到$b_0^2$和$b_1^2$，连起来后变成了两个点一条线段，最后再取$t$的位置，得到$b_0^3$，该点就是贝塞尔曲线在时的位置。可见，算法每次递归，线段的数量和点的数量会减一，不断递归下去，直到最后剩下一个点。

bezier7

Algebraic Formula

算法已经解释清楚，但只是一个直观形式的解释，下面尝试能否从直观的解释推出代数的形式。贝塞尔曲线是由控制点和时间$t$来决定的，因此它们之间一定有一种代数表示的方法。如下图所示，我们在每两个点之间寻找$t$的位置，就相当于在这两个点之间做了线性插值，所以整个过程是不断地进行线性插值得到的点。

bezier8

因此我们可以将其显式地写出来，例如二次贝塞尔曲线可以写成：
bezier_formula

展开后可以得到：
\[b_0^2(t)=(1-t)^2b_0+2t(1-t)b_1+t^2b_2\]

我们发现，给定时间$t$，其实是$b_0$、$b_1$和$b_2$的组合，因此任意一个点必须要由控制点的坐标来决定，并且与$t$有关。我们令$1-t=s$，则公式变成：$b_0^2(t)=s^2b_0+2stb_1+t^2b_2$
这就发现了贝塞尔曲线各项前面的系数其实就是$(s+t)^n$的展开式。例如三点二阶的贝塞尔曲线，各控制点的系数就是$(s+t)^2$的展开式。

总结归纳，给定$n+1$个控制点，我们可以得到一个$n$阶的贝塞尔曲线，它在任意时间$t$都是给定控制点的线性组合，它组合的系数是一个跟时间有关的多项式，这个多项式叫做Bernstein多项式（其实就是一个描述二项分布的多项式）。

最后简化一下，任意阶数的贝塞尔曲线的控制点的系数是由Bernstein多项式给定的，然后贝塞尔曲线是这些控制点与对应控制点系数的加权。通过这样一个性质，我们完全可以不必限制控制点在平面内，在空间中仍然可以得到贝塞尔曲线，只需要把控制点输入成三维坐标，同样使用Bernstein多项式来插值即可。
bernstein2

Bernstein多项式其实是对$1$自己的多项式展开，这也是为什么如果我们把多项式中的系数加起来最后都等于$1$。

bernstein3

Properties of Bezier Curves

贝塞尔曲线有很多不错的性质：

规定了起点和终点，例如$b(0)=b_0, b(1)=b_3$
对于三次贝塞尔曲线（Cubic Bezier），它的起始位置的切线一定是$b’(0) = 3(b_1-b_0)$，终点位置的切线为$b’(1) = 3(b_3-b_2)$，如果控制点数不是$4$，那么系数就不是$3$了。
仿射变换下有一个好性质，如果要对一条贝塞尔曲线做仿射变换，只需要对它的控制点做仿射变换，再重新绘制出来即可。因此不需要把曲线上每个点的位置都记录下来。但是对于投影变换就不行了。
凸包性质，凸包是计算几何中的概念，该性质是说，控制点形成的贝塞尔曲线上的任何一点一定在这几个控制点形成的凸包内，例如四个点形成了一个四边形，那么画出来的曲线一定在这个四边形内。

如下图所示，凸包的概念为能够包围一系列给定顶点的最小的凸多边形称为凸包（Convex Hull）。一个直观的比喻是，假设有一块板，下图中的黑点代表钉子，我们可以用橡皮筋拉开把这些钉子全部包住，然后松手，最后橡皮筋会收缩在这些物体形成的外框，这个框就是凸包。

ConvexHull

Piecewise Bezier Curves

我们可以使用贝塞尔曲线，但是它也有一定的问题，这也是为什么我们要引入逐段的贝塞尔曲线（Piecewise Bezier Curves）。
我们来看一个例子，当$n=10$时，也就是给定了$11$个点，我们就可以画出一条贝塞尔曲线出来。如下图所示，这条曲线能画出来但是并不直观，它变成了一条很平滑的曲线，没有控制点输入时那么剧烈的变化。也就是说，当控制点多的时候，这个曲线不容易控制，就得不到想要的形状。

piecewise_bezier

因此人们就想到，我们可以不用这么多控制点来定义一条贝塞尔曲线，可以使用多段贝塞尔曲线来定义，这样每次只用很少的控制点，最后再连起来，这样就解决了问题。人们更倾向于每$4$个控制点来定义一条贝塞尔曲线，也即是用Pievewise cubic Bezier来定义曲线。如图所示，它是每$4$个控制点定义的贝塞尔曲线拼接而成的，在发生剧烈变化的地方就是多段贝塞尔曲线的交点，因为贝塞尔曲线一定经过起点和终点。

piecewise_bezier2

图中黑色点就是多段贝塞尔曲线的交点（起点和终点，必须经过的点），蓝色点是控制点，本来应该是所有控制点都连在一起的，软件中给隐藏掉了中间两点之间的连线，这样对于Pievewise cubic Bezier来说，一条贝塞尔曲线内的控制点就可以当成一个控制手柄，这正是Photoshop中的钢笔工具带来的画曲线的能力。那么怎么保证连起来的曲线是光滑的呢？在物理上，曲线光滑不光滑是看切线方向是否光滑，即导数要连续，不只是方向还有大小，那么对于第一段曲线来说，终点的方向是由最后两个点来定义的，对于第二段曲线来说，起点处的方向是由前两个点来定义的，因此只要第一条曲线的倒数第二个控制点和第二条曲线的第二个控制点共线并且到终点的距离相等，曲线就能光顺地过渡。

bezier_demo

Continuity 连续性

如果给定两段贝塞尔曲线，都是由$4$个控制点构成，那么在几何上两个曲线都通过中间的黑点，图中展示的是切线上的连续，另外只要两条曲线的终点和起点接触的连续，就是几何上的连续。

continuity

用数学来表示：

第一段的终点与第二段的起点相等，称为$C^0$连续，即$a_n=b_0$。即几何上，只要两曲线接上了，就达到了$C^0$连续，即几何连续。

continuity1

交点左右的两个控制点与交点共线并且到交点的距离相等时，称为$C^1$连续，即$a_n=b_0 = \dfrac{1}{2}(a_{n-1}+b_1)$，即切线连续。

continuity2 再高阶的导数，例如$C^2$连续称为曲率连续，高阶的导数就对控制点有着更高的要求。注意，切线连续看上去似乎已经很好了，但是在制造业上来说，往往有更高的要求，要保证$C^2$连续甚至$C^3$连续。

Other types of splines

简单再介绍一下，一个概念叫做样条曲线（splines），一条连续的曲线是由一系列控制点控制的，它能够满足一定的连续性，与阶数无关。下图为早期人们画曲线时，会使用一根树枝然后用一些工具将其固定住。简单来说，一个可控的曲线就称为样条曲线。

bspline

B-splines

样条曲线中，一种被广泛应用的曲线称为B样条曲线（B-splines, basis splines），即基函数样条，它是对贝塞尔曲线的一种扩展，它比贝塞尔曲线的能力更强。比如前面当$n=10$难操作了，也就是说，设计师需要有一种性质叫做局部性，即改变一个点时，这个点所影响的其他点的范围。分段贝塞尔曲线就具有局部性，B-splines就是一种不需要分段的可以控制局部点的样条曲线。关于B样条曲线和NURBS（非均匀有理B样条）的知识可能是图形学中最复杂的部分，如果有兴趣深入学习的话可以访问Prof.Shi-Min Hu的课程 https://www.bilibili.com/video/av66548502?from=search&seid=65256805876131485

Surface

曲面会比曲线稍微复杂一些，但是相对更好理解。首先，我们把曲线的概念延伸到一个平面上，比如下图中的分段贝塞尔曲面，它是由若干个块拼起来的，怎样在拼起来的同时保证连续性是几何上比较复杂的问题。

bezier_surface

那么我们如何从贝塞尔曲线得到贝塞尔曲面呢？对于下图所示的曲面，可以理解成由一个平面，施加一个向上的力，拖拽上去得到的结果，它是由$4\times 4$个控制点得到的，图中的黑点可以理解为拖拽时施加力的作用点。

bezier_surface2

具体的实现方法就是在两个方向上分别运用贝塞尔曲线。首先在平面上定义$16$个控制点，它有$4$行$4$列，先从行来看，这四根曲线上的点在不同的时间有不同的位置，如果我们把这四个曲线上的控制点，认为是另外一个方向的贝塞尔曲线的控制点，我们就可以画出这条贝塞尔曲线，在这根线不断地扫掠地过程中就可以得到一个曲面。通过这种方式我们可以定义非常复杂的曲面。相关动图

bezier_surface3

在一维对曲线控制时，我们使用的是时间$t$，在曲面中，有两个方向的曲线，所以我们使用$(u,v)$。

bezier_surface4

因此，我们也可以通过$(u,v)$来找到曲面上的点，这样范围在$(0-1)$的$(u,v)$可以对应曲面上任意一个点。贝塞尔曲面是显式表示就是因为它是通过参数映射来实现的。

bezier_surface5

如果需要更多了解Surface，可以访问Prof.Shi-Min Hu的课程 https://www.bilibili.com/video/av66548502?from=search&seid=65256805876131485

Mesh

一般来说，描述面最普遍的方法还是采用网格。既然我们用三角形来描述模型，那我们就需要了解一些关于网格的操作，例如 Subdivision （网格细分，用更多的三角形来得到更光滑的模型），Simplification（网格减面，以节省存储量），Regularization（正规化，使三角形都接近于正三角形）。 mesh_operation

subdivision

首先我们从最基本的操作Subdivision（细分）开始，即如何增加三角形的数量，把用三角形表示的曲面更加光滑。如上图所示，三角形数量很少时看上去就会棱角分明，我们希望能够变得更加光滑。对于现在的显卡来说，三角形的数量已经不是很大的问题了，这样一来，如果有一个模型，我们希望它的细节能够更丰富，我们就可以引入更多的三角形，就好像将一个图形提高它的分辨率以丰富它的细节。

simplification

第二个操作就是Simplification（简化）。如上图所示，如果有一个网格在渲染中位于远处而过于复杂，我们就可以用更少的网格来表示。问题在于我们删除部分网格面后如何保持基本的连接关系。例如牛角的面减少后并不会使这个牛角出现破损或者断掉，因此需要有一系列方法来指导这一算法。

regularization

第三个操作就是Regularization（正则化），三角形有大有小，形状不一，在渲染的时候会造成各种各样的不便，通常应对这种情况会对模型进行这一操作，使三角形更接近于正三角形。

Subdivision

之前在说位移贴图的时候就提到过细分。我们可以在物体表面应用贴图，这个贴图表示了顶点的位置移动量，即通过贴图定义了一个高度场。我们可以将不同的高度应用到不同的顶点上以实现顶点被移动过的模型，但是这要求网格的面数非常多才能赶上纹理本身要求的频率。我们当时提到了需要做细分，甚至动态的细分。那么细分怎么做？第一，引入了更多的三角形；第二，让三角形的位置发生了变化使模型变得更加光滑，因此我们说的细分其实是两步操作。如下图所示

subdivision2

Loop Subdivision

我们以Loop Subdivision算法为例，这个细分分为两步操作，第一增多三角形数量，给定一个三角形，连接三条边的中点，即可得到中间一个三角形，而该三角形又把原本的三角形分成了三个部分，这样一步算法就把原本的一个三角形分成了四个三角形。第二步，我们需要调整三角形的位置，其实是调整顶点的位置，特别对于Loop细分，我们会把三角形的顶点区分开，分为新顶点和老顶点，新的顶点就是我们在边上取的中点，老的顶点就是原本三角形的顶点，Loop细分就是对这两种顶点分别采用不同的规则来改变它们的位置。
BTW: 图形学中有很多命名的方法，这里的Loop不是指“循环”，而是这个算法的创始人的family name。

loop_subdivision

关键是如何把老的顶点和新的顶点分别移动来使模型变得更加光滑：
我们先看怎么更新新的顶点的位置，即边的中点。如下图所示，以图中白点为例，首先它肯定在一条边上，然后只要这条边表示的不是模型的边界那么它一定会被两个三角形共享，我们将两个三角形共享的边上的顶点分别叫做$A,B$，把不共享的两个顶点称为$C,D$(顺序无关)。那么Loop细分定义的规则中，这个白点的位置要变为$3/8*(A+B)+1/8*(C+D)$。这其实就是一种简单的加权平均，即离点$A,B$近一些则$A,B$的贡献更大一些，而$C,D$贡献相对小些。这样一个新的顶点的位置是周围几个点的位置的平均，这就起到了一个平滑的作用。

loop_subdivision2

对于旧的顶点，如下图所示。白色顶点由6个三角形拼在一起，与它相邻的老顶点都会对其有所贡献。Loop定义了一个规则是它采取一部分周围顶点的位置，接着它还会部分地保留自己的位置。我们定义一下顶点的度，在图论中，顶点所连接的边的数量就称为顶点的度，也即是说这里白色顶点连接了6条边，即$n=6$。此外我们再定义一个权重数$u$，因此这个白点的位置应该更新至。如果一个顶点连接了很多三角形，那它的位置会更受它的相邻顶点的影响，如果它只连接了两个三角形，那么意味着这个顶点非常重要，自身的权重会更高。

loop_subdivision3

通过这样的方法，我们就能得到如下图所示结果，每一个三角形被拆成了四个小三角形，并且顶点的位置都经过了细微调整，使模型变得光滑。因此Loop细分做了两个工作：先细分，再光滑。

loop_subdivision4

Catmull-Clark Subdivision (General Mesh)

Catmull-Clark Subdivision是Catmull（2020图灵奖得主）与Clark共同发明的算法。我们之所以提及这个算法是因为Loop细分只能对三角形网格进行操作，下图网格中既有三角形又有四边形的一般网格情况，就需要使用Catmull-Clark细分。我们先来定义一些概念，我们称四边形面为Quad face，而非四边形面当然就是Non-quad face。接着我们定义概念奇异点（Extraodinary vertex）：顶点的度（顶点所连边的数量）不为$4$的点都为奇异点。

catmull_clark_subdivision

Catmull-Clark Subdivision算法对每一个边取中点，每一个面也取中点，并且把边上的中点和面上的中点连起来，如下图。这样左上角的一个四边形变成了四个四边形，三角形就细分成了三个四边形。分析一下会发现，经过了一次细分后，非奇异点的顶点仍然是非奇异点，原本的两个度为$5$的奇异点仍然是奇异点，并且在三角形面上新增的点都变成了新的奇异点，因此细分一个三角形会产生一个度为$3$的新的奇异点，这样就有了四个奇异点。新的奇异点产生是因为三角形细分出来要和原本的三条边相连，推广一下也就是说，只要在非四边形面内新增点做细分，由于该点要和每条边相连，因此必定产生奇异点，和几条边相连，其度就为几。此外，我们还发现，经过这样一次细分之后，所有非四边形面全部都消失了，因为三角形被分成了三个四边形。因此，这样的细分会在每一个非四边形面上引入一个奇异点，并且会将这些非四边形面转换为四边形面。 那么如果我们再做细分操作，所有的面都已经是四边形面了，也就是说奇异点数不会再增加了，这也告诉了我们，Catmull-Clark Subdivision会在第一次细分后，增加了非四边形面的数量个奇异点，之后不再增加。

catmull_clark_subdivision2

例如我们再做一次细分，由于所有面都已经是四边形了，因此奇异点数量不增加。大家会看到在细分的过程中，点会发生位置变化，并且变得越来越光滑。

catmull_clark_subdivision3

关于顶点更新规则，它对于面的中心点、边的中心点及原始顶点会有不同的更新规则，其具体规则如图所示。定义看上去很复杂，简单来说就是一个加权平均的规则。

catmull_clark_subdivision4

通过Catmull-Clark Subdivision可以产生各种各样细分的结果。Loop细分只能用于三角形面，Catmull-Clark可以用于各种不同的面。注意下图中四边形细分结果不对称是因为定义了折痕（Crease）。

catmull_clark_subdivision5

Simplification

下面开始讲解如何进行简化操作。如下图所示，采用Flat Shading着色模型，有时模型离相机很远，为了简化，特别是在移动端性能考虑，因此在不同的情况下会我们要选择不同复杂程度的几何模型。这个算法和我们之前提到过的Mipmap有关，层次结构的几何和层次结构的图像是相似的，只不过几何更难去实现，它要求更多的平滑过渡，避免突变。

simplification2

这里提供一种方法，叫做边坍缩（Edge collaping）。

edge_collaping

Simplification问题的关键在于“要坍缩哪些边”？下图中左侧网格，我们把中间三个顶点都替换成一个顶点，但是我们应该把这个顶点放在什么位置才能保证蓝色网格和灰色网格基本保证轮廓形状一致呢？左图中体现出做放在平均位置的结果，显然结果是不对的，结果会过于扁平圆滑。接着人们引入了一种误差的度量，称为二次误差度量（Quadric Error Metrics），即将这个点放在某一位置时最小化二次误差。二次误差在机器学习中和L2距离非常相似，新的顶点与和它相关联的面的各顶点的距离的平方和，我们要让这个值达到最小，因此这就是一个非常清晰的优化过程。

edge_collaping2

有了这样的二次度量，我们就可以在坍缩任意一条边之后，都把坍缩后的顶点移动至一个二次误差度量最小的位置。这样，可以假设每一条边都计算出坍缩后对应的误差，然后将这些误差最小的边开始进行坍缩。但是要注意，如果我们坍缩了一条边为顶点，那么这条边所连接的其他边会相应地变长，如上图所示。因此坍缩后，坍缩边周围的边会受到影响，其二次度量误差也会发生变化。因此，在坍缩完最小的二次度量误差后，要对其影响到的边做更新，因此需要某一种数据结构，能够保证取到最小值后可以动态地以最小的代价来更新受影响的元素，这个数据结构就叫做优先队列，或者叫堆。（允许求最小并且允许动态更新任意一个点的值）

edge_collaping3

简单而言，具体步骤如下：

对于每一条边，打上一个分数，这个分数就是它坍缩后的二次度量误差
取最小误差的边，做坍缩
更新受影响的边的二次度量误差

再来反思这一方法，我们其实是在不断地通过找局部最优解的方法来找全局最优解，这种方法其实是一个典型的贪心算法。

「如果这篇文章对你有用,请随意打赏」