Games101(3)-几何表示
几何 Gemoetry
几何表示
在计算机图形学中，模型的几何表示大体上可以分为两个种类，隐式几何表示和显式几何表示。
隐式几何表示描述的是构成模型的点之间的位置关系，但是不会直接告诉我们点在哪个位置，表示的含义非常不直观。隐式几何表示的优点在于我们能够非常方便地判断某个点是否在表面上，但是想要知道具体有哪些点则比较困难。举例来说，隐式几何有如下一些表示方式。
第一种是利用数学公式来表示模型上点满足的关系，称为Algebraic Surfaces。例如\(x^2+y^2+z^2=1\)表示一个球的表面；\((R-\sqrt{x^2+y^2})^2 + z^2 = r^2\)表示一个圆环面；\((x^2 + 9y^2/4 + z^2 - 1)^3 = x^2z^3 + 9y^2z^3/80\) 表示一个心形表面。
第二种方式是CSG(Constructive Solid Gemetry)，它指的是通过一系列基本的几何体，利用一些基本运算，例如交并差等，得到更加复杂的几何表示。
第三种方式是有向距离函数(Signed Distance Functions)，该函数的含义是空间中任意一点到达所定义模型表面的最短距离，该距离可正可负，与在模型内外有关。利用距离函数，我们可以恢复模型的表面，实际上就是将所有\(f(x, y, z) = 0\)的位置找到即可。
第四种方式是水平集方法(Level Set Methods)。这种方式与距离函数类似，距离函数方法需要使用一个封闭形式的函数来表达，在表征一些较为复杂的情况时，可能会较为吃力，而水平集方法可以在笛卡尔网络中对曲线或曲面进行数值计算，而不必对曲线或曲面积进行参数化，因此可以表达更加复杂的情况。
第五种方式是分形的方式。分形类似于递归，表达出的几何形式具有自相似的特点。
显式几何表示描述的是哪些点或者面构成了模型。显式几何表示相对隐式几何表示会更加直观，进行采样会非常简单，但是相应地会有其他缺点，例如判断点是否在对应面上会比较复杂。举例来说，显式几何有如下一些表示方式。
第一种方式是使用点云(point cloud)来表示模型，即利用位于模型上数量众多的点来表示整个模型。实际上，就是用一个由点坐标\((x, y,z)\)构成的列表来表征模型。可以想见的是，点云的密度越大，表示的模型精度也就更高，同时也能够表达更加复杂的模型。
第二种方式是使用多边形mesh(polygon
mesh)来表示模型。常见使用的多边形包括三角形和四边形。这种方式会描述所有的顶点，以及这些顶点如何组成多边形等信息。例如Wavefront
Object File对应的.obj文件，就是利用polygon
mesh来表示模型的。文件中以约定的格式记录了顶点坐标xyz信息、纹理坐标uv信息、法线信息、以及顶点如何构成多边形的信息。
还有一种方式是通过参数映射的方式将二维平面上的范围映射到三维空间中，这种方式直接给定了每个点坐标的确切的求法，所以也属于显式几何表示
实际上无论是隐式几何表示还是显式几何表示，它们都有各自的优缺点，适用于不同的任务和场景，并没有一种最好best的方式能够统一几何表示，具体使用何种表达需要视具体的任务而定。
曲线
在计算机图形学中表现曲线有许多方式，这里介绍一种非常常见的方式，贝塞尔曲线(Bezier Curves)。
贝塞尔曲线最终得到的曲线结果由一系列控制点决定，例如下面是一个包含4个控制点的贝塞尔曲线。这条曲线从第一个控制点出发，到最后一个控制点结束，过程中不一定会经过其他控制点。并且在曲线起始处，切线方向为\(t_0=3(p_1=p_0)\)，在曲线结束位置，切线方向为\(t_1 = 3(p_3-p_2)\)。
接下来，我们先可以从几何上理解贝塞尔曲线的工作流程，即确定了一系列控制点之后，如何绘制出这条贝塞尔曲线。首先可以确定的是，这条曲线一定会经过第一个和最后一个控制点，我们不妨将这两个点连接起来，得到一条线段，定义线段的长度为1，并以此为x轴定义一个坐标系，接下来就是需要确定当x坐标为任意t的时候，y坐标是多少。整个过程是一个递归的过程。控制点两两相连之后，在每条线段上按照x坐标比例找到新的点，重复这个过程，直到最终得到一个点，这个点就是对应x坐标下，在曲线上的点。
这里的描述可能比较抽象，绘制过程可以参考贝塞尔曲线-可莉视觉。
上面是贝塞尔曲线的几何理解，下面将介绍它的代数表示。我们现在有一系列控制点\(b_0, b_1, ..., b_n\)，那么实际上最终贝塞尔曲线上的任意一个点的坐标，都可以通过这些控制点的坐标得到，具体公式如下： \[ \mathbf{b}^n(t) = \sum_{j=0}^{n}\mathbf{b}_jB_j^n(t) \] 其中，\(B_j^n(t)\)是伯恩斯坦多项式中的第j项，实际上就是一个描述二项分布的多项式： \[ B_j^n(t) = \binom{n}{j}t^j(1-t)^j \] 贝塞尔曲线具有一些良好的性质，包括：
- 贝塞尔曲线一定会经过第一个和最后一个控制点
- 贝塞尔曲线具有凸包性质，即贝塞尔曲线一定会处于控制点所形成的凸包范围内
- 贝塞尔曲线具有仿射变换下的不变性，即先对控制点做仿射变换，再计算得到新的贝塞尔曲线，与对旧的贝塞尔曲线直接做仿射变换得到的曲线是相同的
理论上，如果我们想要模拟比较复杂的曲线，只需要增加贝塞尔曲线的阶数即可，即增加控制点的个数。但是当控制点增加的时候，曲线的变化会不够直观。因此实际的做法是采用分段贝塞尔曲线，每段贝塞尔曲线均采用4个控制点来控制。分段贝塞尔曲线可以在这里找到控制样例：Bezier Curve Edit
分段贝塞尔曲线能够保证整条曲线首尾相连不会断开，但是在连续性上有不同的定义：
- \(C^0\)连续：两条贝塞尔曲线在连接处相连
- \(C^1\)连续：两条贝塞尔曲线在连接处相连，并且在连接处的切线相同（不考虑方向，仅考虑大小）
补充材料：
当然除了分段贝塞尔曲线，还有其他的曲线，例如spline曲线(样条曲线)。样条曲线可以看作是对贝塞尔曲线的扩展，贝塞尔曲线通过一系列控制点来调整整条曲线，但是这种调整是整体性的，类似牵一发而动全身的感觉。但是有时候我们并不希望有这种整体性，例如当我想微调某个局部的曲线的时候，我就希望曲线的其他地方不会改变。而样条曲线就具备这样一种局部性。(当然分段贝塞尔曲线也能够做到局部性，不过分段带来了额外的复杂度)
曲面
贝塞尔曲面
一种常见的曲面表示方式是由贝塞尔曲线扩展而来的，我们称之为贝塞尔曲面。贝塞尔曲面可以看作是两个方向上多条贝塞尔曲线的组合。首先在一个方向形成多条贝塞尔曲线，然后在另一个方向上，将这些点看作是新的控制点。
几何操作
常见的曲面几何操作包括曲面细分(Mesh Subdivision)，曲面简化(Mesh Simplification)，曲面正规化(Mesh Regularization)等。
曲面细分
曲面细分的目的是在原曲面的基础上分出更多的三角形，使得模型变得更加精细。曲面细分包括两个步骤，第一个步骤是在原曲面的基础上细分出更多的面，第二个步骤是调整各个顶点的位置。接下来将介绍两种常见的曲面细分算法，分别是Loop Subdivision和Catmull-Clark Subdivision。
Loop细分对三角形进行操作。对于某个三角形，首先可以取各条边的中点相连，这样就可以将一个三角形细分成新的四个小三角形。细分之后需要进行顶点位置的调整，在Loop细分算法中，将顶点分为两类，一类是新出现的顶点，一类是旧的顶点。
对于新的顶点，它必然出现在原来的某条边上，因此会和原始的两个三角形有关，如图所示。因此对于该点位置的更新，也可以从相邻两个三角形共4个点出发，其中认为处在同一条边上的两个顶点对新的顶点具有更多的影响，因此权重更大。
对于旧的顶点，则考虑它原来所有相邻的顶点，使用这些顶点的坐标来更新自己，当然同时也需要考虑自己的原始坐标。这里的权重与顶点的度有关，顶点的度越高，表示这个点相邻的点越多，实际上表示这个点没有那么重要，它的位置可以由其他点来决定；反之如果这个顶点的度很小，则应该更加偏重自己的原始坐标。
Loop细分只能处理三角形的情况，而Catmull-Clark细分能够处理多边形的情况。在介绍这种细分之前，首先需要引入两个概念，一个是非四边形，一个是奇异点。前者见名知义，指的是不是四边形的多边形；后者奇异点，指的是那些度(degree)不为4的点。
同样，首先需要进行的细分出更多的形状。Catmull-Clark细分首先取各条边的中点，然后取各个面的中点，之后中点之间相互连接，这样就得到了细分的更多四边形。结合前面非四边形和奇异点的定义，我们可以发现，经过一次细分之后，所有非四边形面都消失了。并且之前有多少个非四边形面，经过一次细分之后，就会新出现多少个奇异点，并且此后不会再增加。而进行顶点位置更新的时候，Catmull-Clark细分算法将点分为三种情况，对应的更新算法如下所示：
曲面简化
曲面简化的目的是减少三角形的个数，但是同样能够一定程度上表征模型。减少三角形的个数必定会带来模型精度的下降，但是模型精度的需求是视情况而定的。在一些情况下，我们可能希望有更高的模型精度，但是另一些情况，例如这个模型离观察者很远的时候，我们也许使用更少的模型就已经能够达到可以接受的效果了。
一种曲面简化的方式是边坍缩(edge collapsing)。边坍缩指的就是将一条边坍缩成为一个点，从而减少三角形面。减少了一条边，新增了一个顶点，这个顶点的位置该如何确定呢。实际上，顶点位置可以视作一个优化问题，使用二次误差度量作为优化目标。二次误差度量(Quadric Error Metrics)指的是这个点到原来几个面距离的平方和，通过优化这个点的位置，可以使得这个点到原来几个面的距离平方和最小。
将该方式推广到整个模型，则选取二次度量误差最小的边开始坍缩，以此类推，直到剩下的三角形数符合要求。需要注意的是，当我们坍缩了某条边之后，相邻的面会发生变化，因此相邻的边对应的二次度量误差也会发生变化，从而导致排序会发生变化。堆(或者称为优先队列)这种数据结构可以很好地应对这类问题。实际上，这种曲面简化的方式是一种贪心的方式，它以局部二次度量误差最小作为标准，而不是全局的最优。但是在实际操作中，这种贪心算法得到的效果一般都是不错的。