技术美术成长之路——Games101图形学篇（五）、几何篇

xiaozongpeng

本文参考Games101课程，文章链接：
如果想要系统从头看的话，文章汇总如下：有问题欢迎留言！
下面开始正题：


对于图中的杯子，各种各样的曲线，都是涉及到几何，都是如何生成这些不太形状的几何。


还有这里的曲面，我们应该如何去定义它，因为曲面是一个连续而非离散的，并不像我们以前三角形网格模拟的样子。


复杂的部件，应该怎么去描述设计。


这种透明的布料，这种几何形式又是如何搞出来的。


对于这种现象的模拟重现。这种几何形态，如何描述。


这种超复杂的场景，其中的几何该如何表述，如何存储，如何渲染。


这种毛发的几何型态，如何去表述这些细节。


更近距离的微观几何，这种的复杂又该如何表述。


这种2D的几何情况。
上述就是我们的几何带来的各种问题，从而也就是几何的各种研究方向。所以说，几何并不是一个简单的事情，并不是拿三角形面就能解决任何的问题的。
关于几何的分类：


分类就是我们有不同的方式来表示不同的几何。
隐式几何：比如我们要表示一个面，然后用点来组成的面，他这种隐式表示，并不会直接给出点在哪，而是给出点之间的关系，就比如下面的球的隐式表示：


我们可以由此可以很容易的确定，某一个点是否在球上。
而相对而言，如果说一个球想要进行一个显式的表示，那么我们可以通过三角形网格来实现，我们只需要给出所有顶点的坐标就可以表示出来。
隐式表示：表示一些关系，并不给出一些实际的点。而满足的关系，自然就可以用一个方程来表示。


这里隐式表示会有他的好处，自然也有不好的。
它可以很简单判断一个点是否属于这个几何，但是如果想知道哪些点在这个几何上，就很难确定。


单纯从一个式子出发，我们很难，直接推测出他表示什么形状，从而也就很难确定哪些点在他上边。
显示表示：就是把实际的点坐标等等的都直接给出来。之前的三角形模型就是一个典型的例子。还有一种显式的方法，就是给出所有的参数，和相应的一个映射关系，根据参数和映射关系可以算出所有的点。


比如下面映射的例子：


这里我们是知道所有的uv的，也就是可以算出所有的点，那么自然就是显式的。就可以得出表示的是什么几何形体。
对于显式表示来说，我们想要判断一个点在几何上还是几何内还是外？这一点是比较难的。


到此我们总结一下，关于两种表示方法，各有自己的优劣，所以我们针对不同的问题来选择不同的解决方法，这也是分类方法的意义。——这也是导致几何比较难的原因。





按照需要选择表示方式


其实刚刚说的隐式，用公式来表示，但是对于表示方法远远不止这些。在隐式表示中有：


数学公式，不直观他最大的缺点。但是对于复杂的就很难表示了，奶牛。
还有一种CSG，就是通过一些基本几何的基本运算，来定义新的几何，形成更加复杂的几何：




这种玩法，应用非常广泛。
这里隐式很好理解，因为他是拿几何操作，并没有给出具体的点。
还有一种叫距离函数的东西：就是对于几何，本来描述是描述一下他的表面，从而确定下来这个几何，这也就是几何的描述。而这里现在是描述空间中的任何一个点到要表述的这个几何形体的最近距离。这个距离有正负之分，正负来表示空间中的点在几何的内外。
其实有了这些距离，是足以确定下来表示的几何的表面的，就是有空间中任意的点，加上他们对应的最近距离，我们可以对空间中每一个点确定一个自己的球，因为球和我们的模型会存在一个交点，所以无数的交点也就会组成我们的几何表面。至于哪些是交点，因为他们能够凑成面，所以交点是可以判断出来的。
想一些简单的平面几何体是很容易想通的。
而针对两个物体，我们可以把他们的距离函数做一个融合（距离函数就是给空间中任意一点，给你吐出来他的最近距离），那么两个几何也就会发生融合，当然这个不一定但是可以是几何上的相交融合，主要是距离函数融合后，他俩就代表一个整体几何了。


所以这种表示就很适合来自类似融合的工作。
下面来一个例子：


我们想要上边上一行两个黑白图的一个中间状态，那么如果尝试把他俩实现一个混合，混合了之后中间出现一道灰色的，左1/3黑，右1/3白，中间1/3灰。但我们想要的是左黑右白，这样才是两个图过渡的中间状态。
那么怎么搞成我们想要的呢？就是先求出来有向的距离函数，SDF，S表示signed，其实这里就是任何一个点到这个黑线的最短距离。这里认为右边正，左边的距离为负数，右边靠近她的值是比较小的，远离他的是比较大的。
同理对于B也是一样的，得到这俩图之后，把这俩图进行一个blend操作，注意你就看正中间的部分，由于A正中间是1/6，B是-1/6，那么blend之后的正中间就是0，其他地方，正中间左边你会发现是负的，右边是正的。这时候再恢复到原来的形状。
对于0的地方是边界，其实把两个SDF进行blend，就等于把他们的边界进行一个blend。这里恢复出来之后，就是左边是黑的，右边是白的，把边界实现了一个blend。


其实这里就是把距离函数进行了blend，然后把blend之后的距离函数再恢复成原本的面，而SDF为0的地方就是边界。
那么距离函数的应用是什么？


包括我们之前的蜗牛的shader中的蜗牛，就是用距离函数表示的，都是隐式的几何表示。几何之间要做一些圆滑的过渡，中间就是用的距离函数。
距离函数的表示能力非常强！
对于blend之后恢复成原来的几何表面，其实就可以把所有距离为0的点连接起来，所形成的边界就是几何表面。


但是有时候距离函数并不能很好的用一种式子表示，用其他方法也是可以的，比如这里的level set，把函数值写到了格子上。也是一样的去寻找边界为0来确定几何表面。至于他在什么地方等于0 ，我们可以用我们的双线性插值来确定出来。


当然，水平集也可以定义在三维空间中的格子，和我们之前的3D纹理就扯上了，如果我们有一个三维的纹理，表示的是人体的不同位置的密度，那么如何从这个三维信息提取出物体的表面呢？
其实这里说的纹理存的密度就是要放到水平集格子里，然后水平集的格子，可以通过找到所有密度等于某一个值的边界，从而确定处对于某一个密度下的表面。


这里水花四溅的时候，水花和水花结合再一起了，我们怎么去描述，这里也是可以用水平集或者用距离函数的方式来实现。（水滴融合了呀，然后提取出融合后的表面）


还有一种叫分型的描述方法，就是自己的局部和整体长得非常像，就像计算机里的递归。其实雪花的放大，整体是个六边形放大之后每一个边上还有六边形，不断的重复。
中间的植物，他也是这样的，关于自然界的分型。对于这些分型的几何，也有相关的研究如何表示。
其实对于这个中间的西兰花，渲染的时候，会有强烈的走样问题，因为变化频率非常高，因为他一个小的突起就像是再重复一个大的突起，指数级复杂。
隐式表示的总结：


隐式函数表示都很简单，而且他是非常易于做光线和他的求交的，如果想要严格描述一些几何，隐式也是更好的。
他的问题：


显式几何





1、点云
不直接考虑表示表面，而是直接表示点，只要点足够细密，面就出来了。
可以表示任何形式的几何，只要够密集。对于一些三维空间物体的扫描操作，得到的结果多数都是点云。


2、多边形面


三角形相对点云来说，需要处理他们之间的连接关系等。
对于obj文件：


上边的就是一个立方体完整的obj文件。
有8个顶点，6个法线（有两行是多余的，他数据精度在建模的时候有点问题），纹理坐标。最后的f是表示他们之间的连接关系。
3、曲线


摄像机在沿着一个曲线运动，而这个曲线怎么去描述就是我们的目标。


在maya中搞这个曲线。


这个就是曲线中搞上一些控制点。
这些玩意就是贝塞尔曲线，你放大之后他仍旧是光滑的，不会是折线。接下来就开始介绍重点的贝塞尔曲线。


一句话说明：贝塞尔曲线是用一个控制点来定义某一段曲线。
控制点会定义曲线满足的一些性质：比如在点切线（起点终点的），起点终点。


至于为啥有一个系数3，待会说。
这样我们就可以得到我们的曲线：


注意控制点不一定要经过他，也就只是给我们用来做控制用的，辅助点。
这样形成的线就是贝塞尔曲线，那么我们怎么去画一个贝塞尔曲线，给定控制点，怎么得到这个贝塞尔曲线。


就是：德卡斯特里奥算法




我们有了控制点，可以确定起点和终点，那么只需要确定中间的具体位置即可。那么做这么一种操作：把起点和终点看作时间上的0和1，那么我们只需要找到t时间的曲线的位置，这样这条曲线就可以确定下来了。
而算法就是通过给出这个关于t时间的曲线的位置。
具体操作：我们这里有三个点，形成了俩直线，那么我们就对每一个直线进行操作：我们先取出b0b1的t时的位置，然后取出b1b2的t时的位置。这样你就找到了俩新的点。


这时候把新找到的俩点，连接起来，我们再一次得到一个直线，那么针对这个直线取处他时间t上的点，那么这个点就是我们要找的点。也就是贝塞尔曲线，在时间t时的点。


为啥他是显示表示呢？显式表示我们说过有两种，一个是直接给出的，一个是给出参数，同时给出参数所有的取值的（根据参数的所有取值可以算出所有的点）。
那么这里就是给了我们t，也就是参数的取值，然后可以根据这个t和上边的算法来算出所有的点。


看上去是一个递归的算法。


从而：




这个是相关的动画，但是到目前关于算法都是一些直观上的表示，并没有做抽象化的代数表达。那么代数怎么表达呢？
其实思考刚刚的过程，我们针对任何点的产生，都是通过四个控制点作为条件，同时把t作为变量来求出来的，那么代数的表达自然也需要具备这四个点和t了。


注意在求两个点中间的t位置的点的时候，其实就是利用的一个线性插值！


这里展开之后系数的形式很像1的平方的展开式。如果扩展到四个点，那么就另外一边就会同样有一个b12，求出之后，和这里的b02进行一个插值操作，得到b03，这时候看到系数就会是一个1331，就是一个立方的。((1-t) + t)的n次方的展开式。


这里的伯恩斯坦多项式：i和n表示的就是i从0到n。其实就是二项式的展开式。
总体来说就是拿伯恩斯坦多项式作为系数，然后对我们的给定控制点的加权插值。

同时，我们不必对控制点限制在平面内，定义在三维中得到三维中的贝塞尔曲线。


现在我们就完成了对与算法的代数化。


对于同一个t处的几个多项式进行一个加和得到的是1，因为它实际上就是一个1的n次方的展开。同时也是对称性的。
其实这里就是给定控制点，然后确定系数插值。这一概念不仅在贝塞尔曲线上有应用，其他曲线也有用的。


第二个性质针对四个控制点的贝塞尔曲线。他的起始和终点位置的切线是确定的。注意只针对四个控制点的情况。
第三个性质是：针对我们的贝塞尔曲线如果只进行放射变化的话，那么我们可以只对于所有的控制点进行仿射变换，然后把新得到的控制点重新利用算法计算出曲线，和把原来的曲线直接进行变换得到的是一样的。
所以我们针对贝塞尔曲线进行放射变换的时候，可以直接对控制点进行变换，如果对曲线变换，意味着你需要变换他上边的每一个点。但是受限于仿射变换，也就是说投影这些操作就不行。
凸包性质，就是说画出来的贝塞尔曲线一定是在几个控制点形成的凸包内。关于凸包：


就是他要包住几个点，然后包住这几个点所需的最小的凸多边形。其实这个过程可以理解为一个橡皮筋包一大推钉子，橡皮筋绷紧后最后的形状就是符合最小的凸多边形，就是一个凸包。
比如说：给出一系列控制点在一条直线上，那么最后形成的曲线一定是经过这些控制点的直线，因为凸包性质，凸包就是这条线。


逐段的贝塞尔曲线。


首先还是针对之前的玩法，现在把n取到10，11个控制点，我们进行插值可以得到上边的曲线。但是这时候你会发现这里的线和控制点之间没有那么明确的关系了，尤其线的中间部分和中间的控制点。
那么也就意味着如果我们想要通过调整控制点来控制曲线的形状走向，这件事是很不直观的。也就意味着这个曲线变得很难控制。
解决方法就是：不要一次性用那么多的控制点，把线拆开，定义多端贝塞尔曲线。


多数情况下，人们倾向于定义每四个控制点一条贝塞尔曲线。四个成一段贝塞尔，然后贝塞尔相互之间进行连接。
对于四个控制点，人们往往不连接中间的俩。这种定义就得到了非常广泛的应用，你这时候可以把中间的俩点当成一个控制杆，然后对曲线进行各种控制，这个在photoshop的钢笔工具中就有使用，针对一些mind图有时候也有。


每一段贝塞尔曲线都有四个控制点。
如果想要保证衔接处光滑，那么我们可以通过保证，一个线的末尾点的切线等于另一个线的起始点的切线方向。
而我们说过这个四个控制点的贝塞尔曲线的性质，就是切线是三倍的向量。


也就是把上边的三个点进行一个共线处理，同时保证中间的点是处在中点的位置。这时候无论你怎么去操作其他的控制点，这里连接处始终能保证平滑的连接。
为啥是中点？因为切线的值表示的是倾斜的程度，如果针对一个点两侧的倾斜程度是不一样的，那么就谈不上这个这个点是光滑的了。其实左右倾斜程度不一样，就是左右导数不一样，那么就意味着这个点是否可导，也就决定了这个点是否连续，这里只有是中点的时候，才能保证是连续的，也就是光滑的。
针对连续性：


只要第一个的终点和第二个的起点是相同的，那么就管这种叫C0连续。（注意没说切线的要求，只要共用该点就算）。
如果说切线共线且共用点处于中点位置，这时候就叫做C1连续，可以认为是一阶导数的连续。
有时候会要求二阶甚至更高阶数的连续。


除了贝塞尔曲线还有其他的曲线，比如样条（spline）


就是通过控制点控制搞成的曲线，同时满足一定的连续性，这一一个可控的曲线就是样条。
这里有一个常用的叫B-splines基函数样条。
什么叫基函数呢？就比如刚才提到的伯恩斯坦多项式，我们可以这么理解，他就是拿控制点作为伯恩斯坦多项式每一项的系数，然后得到了一个新函数。
那么针对这些新函数都是由伯恩斯坦的特定的项组成的，这些项其实就可以视作基函数。
这里的B样条，相当于是贝塞尔曲线的一个扩展，针对刚刚的n=10的贝塞尔曲线，我们只要动其中的任何一个点，整个曲线每一个点都会有相应的变化。针对这一点其实就不太好，牵一发动全身，控制性不太好。
所以我们需要的是最好做到局部调整。局部性强一些！这就是我们的B样条。之前的贝塞尔分段之后也可以这么干，但是他毕竟是分段处理的。
具体的课上没说，因为细节及其复杂。可以说整个图形学里面最难的！他的基函数更加复杂，他和贝塞尔曲线的分析方法是类似的。


还有一个NURBS，非均匀有理B样条，这个更加复杂，更加延申的。
关于样条还有更多的，比如贝塞尔曲线的拼接变成高阶的贝塞尔曲线，高阶的怎么拆分，对于一些100个控制点的曲线怎么弄成90个控制点的，同时曲线是接近的等等的研究。先做好变换的改动，然后具体就看光栅化了。
接下来，关于曲面：
曲面



我们如何利用贝塞尔曲线得到贝塞尔曲面。


这个平面是由4×4个控制点决定的。同样的我们也可以理解为拽着这些点来控制这个曲面。对于曲面的形成，我们就是在两个方向上进行贝塞尔曲线。
先在一个方向上搞出来四个贝塞尔曲线。


然后在同一t上的四条线有四个点，这四个点给看作四个控制点，然后在另外这一个t轴上进行构建贝塞尔曲线，这一个贝塞尔曲线才是用来形成最终贝塞尔曲面的。让这四个点进行从0到1的滚动，得到n条贝塞尔曲线，这就形成了贝塞尔曲面。




这里同样还有很多的问题，比如两个曲面在衔接的时候如何做到无缝衔接，课上就不多介绍了。


这里我们在操作的时候，有两个t，这里写成uv：


这里就是先取u，然后得到四个点，然后针对一个v，就可以确定曲面上的一个点。也就意味着我们的每一对参数(u, v)，就能够对应到曲面上的一个点，这也说明了贝塞尔曲面是显式的表示，有参数和参数所有的取值范围。
但是最多的空间中面的表示还是用Mesh，而针对mesh形成的网格，我们会有各种各样的操作，这些操作就是几何处理。


第一个是网格的细分，就是表面三角形数切分更多，得到更加光滑的表面。反过来的一个过程，就是曲面的简化，简化之后更少的开销。还有最后的网格正规化，正则化，也就是让三角形不在出现那种特别尖锐的形状，三边都差不多的样子。


具体如何去细分


具体如何去去掉一些细节，同时保证不要去掉关键连接的部分，比如牛角你给去一圈直接掉下来了，那可不行。


其实这个是有意义的，针对那种细长的三角形会对渲染造成各种不便。如何改进？同时保证改进的同时模型的整体不变。


之前位移贴图的时候提过这个细分，位移贴图因为是实际改动顶点的位置，所以要想通过改动顶点位置获得一个较好的细节效果，必须保证三角形是非常小的，也就意味着需要很多的三角形。
引入更多的三角形，并不能让外型发生变化，细分是包括分出更多的三角形，同时让这些三角形的位置发生变化，使得外型发生变化。就像上边的两个变化。
第一个、loop 细分（和循环没关系，loop和人名字有关）


先1个变4个三角形，然后对新老顶点采用不同规则来改变他们的位置。
调整位置的算法：
针对新的顶点：


这个新的白色顶点一定在三角形的边上，同时我们考虑一般情况，他是被俩三角形共享的，然后有以下规则：
就是一个简单的加权平均。而平均就是意味着平滑，就像我们之前交代过的图像的平均。
对于旧的顶点：
因为他是一个老的，所以他的最终结果来源有俩：一个是自己的原来的坐标，一个是周围老顶点的坐标。


这里的n表示的是度，也就是顶点相连的边 的数量。还有一个u，就是和n相关的一个数而已，没有啥几何意义。
然后更新之后的值就是分两个部分组成。针对这两个部分的比重，我们分析一下知道，如果说n比较大，也就是该点周围点很多，那么他自己占的比重就没那么大了，周围的结构更能决定他变化后的位置，相反n很小时，他自己占比就应该较大了。


上边的操作，我们做了一个前提设定，就是使用的网格时三角形的，才能用这个玩法。
而针对这些更一般的情况，如何去处理呢？


这里定义quad-face四边形面和非四边形面，注意下图中的小三角形是为了展示谁是非四边形面的，没有别的意思。奇异点就是度不等于4的点。


总的思路还是一样的，就是先引入一些新的点，然后做一些位置变动。
具体操作就是：先取点，对于边取中点，对于一个面，在面内部取一个点，让面内的点和边上各点相连。上边的三角形和小正方形都是一个面。




针对奇异点增加了俩，原来俩还是不变的5个度，对于新增加的俩，都是3。
其实你会发现，针对奇异点的增加，都是在一个非四边形内点上一个点，由于他要和边上每一个点进行一个连接，这样形成的必然是奇异点。
这时候的非四边形面已经消失了。是因为他们会引入一个奇异点，引入之后非四边形面会消失，奇异点数增加。相当于这些非四边形面在细分之后都变成了奇异点。
这时候如果再进行细分，因为没有非四边形面了，也就意味着奇异点数目不可能再增加了。也就是这个细分在第一次的时候，增加了非四边形面数个奇异点，之后再也不会增加了。




细分的同时是发生了一些位置上的变化的。
针对这些点完成细分之后如何更新位置：


这里是区分成了三类，新的点且在面中间的(f)，在边的中心和老的顶点：


这里不再详细展开。
都是通过一些平均来让整个平面更加的平滑。


这里这种细分方法可以针对四边形等非三角形。
针对三角形简化


我们可以根据距离的远近来决定模型的使用。这里会和以前的mipmap相关，就是一个像素覆盖很大的纹理区域，这时候采用mipmap中相对高层的像素，这里就对于我们的模型较远的时候直接采用简单模型。
这个层次上几何的层次和像素的层次是差不多的，但是几何的层次结构是非常难做的，以及几何结构的变换也是很难的。
什么时候做切换，直接切换是否会显得突然没有过渡，几何是不具有插值等操作的，几何的层次结构不好做！
那么具体的怎么简化？
边坍缩（一种简化）


就是找到一个边，然后把边的两头给一捏，融合在一起这样就少了一个边了。
具体去坍缩哪些的边？针对一些不重要的，那么不重要的怎么确定？


引入二次误差的概念，什么是二次误差呢？
先说下面的一个场景，就是想要把本来的五个黑点中间的仨简化成一个，应该如何确定简化后的位置，从而保证剩余三个围起来的轮廓和原来五个的轮廓差不多？
这里无论是五个求平均确定还是中间仨求平均，都不好使。接下来介绍二次误差：
因为新的点和原本的几个面（这里是边简化成了2D的了，实际应该是面）都有关系，也就是直接去求这个点和相关面的距离的平方和，让这个平方和最小。这时候点的位置就是我们要的。
这个就是关于二次误差的度量。


那么二次测量怎么应用到坍缩上呢？就是这个直线坍缩成一个点之后，通过移动该点位置，使得这个坍缩后对原本造成的影响最小。
也就是说我们可以去测量每一个边最小的二次误差，最终对比谁是最小的，坍缩谁！排个序，然后从小往大了坍缩。
另外注意，坍缩一个边之后，相关的周围几个边都会变化，需要我们重新计算他们的二次误差。那么我们排序的操作就有点乱了。
这样就需要我们搞一种数据结构，坍缩之后并把相邻直线的二次误差更新后依旧能够保持有序，这个就是优先级队列或者堆。


另外，我们这里想要的结果是整体简化后的轮廓和原来的模型是类似的，但是这里我们采用的都是在局部找二次误差，然后进行一个优化，这其实就是通过局部最优找整体最优解的操作，就是一个贪心算法。
并不能够保证一定最优解！但是针对各种各样的复杂模型，难以找到绝对的最优解。


几何部分就到此结束了~

下一篇再见~~