GAMES001课程笔记02-计算几何

这个系列是GAMES001-图形学中的数学(GAMES 001: Mathematics in Computer Graphics)的同步课程笔记。课程旨在总结归纳图形学学习过程中重要的数学概念、理论和方法，并将以索引的形式在每一章节中穿插讲解该数学专题在图形学中的应用。本课程既可以作为GAMES系列其它课程学习的基础或「手册」，也可以作为站在不一样的视角复习图形学知识的平台。本节主要介绍计算几何的相关内容。

计算几何(computational geometry)是伴随着图形学发展而逐步兴起的一门学科。计算几何的主要目标是高效地求解二维和三维空间中的各种几何问题，包括三角剖分、凸包、扫描线等经典几何问题都属于计算几何的研究范畴。和传统算法研究相比计算几何的研究更加注重对实际应用问题的解决，因此大多情况下是在低维实数空间进行研究。

点、线、面的表示

研究空间中的几何对象首先要明确所在的坐标系。在计算几何中，没有特殊说明的情况下一般都默认使用三维笛卡尔坐标系(Cartesian coordinates)，其xyz三个坐标轴可以分别使用RGB三个颜色的向量来表示。在不同的三维软件中，笛卡尔坐标系的原点以及三个坐标轴可能有不同的定义方式，使用时需要查看相关的手册来进行确认。

需要说明的是，OpenGL使用右手系来定义三个坐标方向，而Direct3D则是使用左手系。

有了坐标系就可以来定义各种基础的几何元素。空间中的点一般等同于它的位置向量，我们可以用它二维或者三维的坐标来进行表示。不过在一些图形库中会使用Point和Vector两个类对点以及向量进行区分，在使用时要注意它们是不完全一致的概念。

基于点的定义我们可以继续定义直线和线段，它们分别由相应的参数方程给出：

\[\mathbf{x} (t) = \mathbf{p} + t \mathbf{v}, \ \ \ t \in (-\infty, +\infty)\] \[\mathbf{x} (t) = \mathbf{p}_1 + t (\mathbf{p}_2 - \mathbf{p}_1), \ \ \ t \in [0, 1]\]

对于平面，我们同样可以利用相应的隐式方程来定义：

\[(\mathbf{x} - \mathbf{p}) \cdot \mathbf{n} = 0\]

在计算几何中三角面也是一种常见的几何对象，我们可以利用三角形的三个顶点来定义它：

\[\begin{aligned} \mathbf{x} &= \mathbf{p}_1 + u (\mathbf{p}_2 - \mathbf{p}_1) + v (\mathbf{p}_3 - \mathbf{p}_1) \\ &= (1 - u - v) \mathbf{p}_1 + u \mathbf{p}_2 +v \mathbf{p}_3 \end{aligned}\]

如果进一步要求点位于三角形内部，则可以对三角形三个顶点的坐标进行插值：

\[\mathbf{x} = u \mathbf{p}_1 + v \mathbf{p}_2 + w \mathbf{p}_3, \ \ \ u,v,w \in (0, 1)\]

点、线、面的关系

点与直线的关系

对于给定的点\(\mathbf{p}\)以及直线方程\(\mathbf{x} = \mathbf{o} + t \mathbf{d}\)，点到直线的距离可以用下列公式计算：

\[h = \frac{\Vert (\mathbf{p} - \mathbf{o}) \times \mathbf{d} \Vert}{\Vert \mathbf{d} \Vert}\]

而点\(\mathbf{p}\)在直线上的投影可以表示为：

\[\mathbf{q} = \mathbf{o} + \frac{(\mathbf{p} - \mathbf{o}) \cdot \mathbf{d}}{\Vert \mathbf{d} \Vert^2} \ \mathbf{d}\]

对于射线以及线段的情况可以类似地处理，不过需要注意参数\(t\)的取值范围。

线与线的关系(2D)

在二维平面上，具有共端点的射线/线段之间的绕序可以通过它们方向向量的叉乘来确定。

两条直线的角度可以通过联立方程组来求解。判断两条线段是否相交同样可以使用类似的方法，不过更加简洁的方式是使用线段的跨立测试。

线与线的关系(3D)

对于空间中的异面直线，求它们之间的最短距离有两种处理方法。第一种是基于异面直线之间距离的定义，我们构造出它们公垂线的方向向量\(\mathbf{n}\)并进行投影：

\[\mathbf{n} = \frac{\mathbf{d}_1 \times \mathbf{d}_1}{\Vert \mathbf{d}_1 \times \mathbf{d}_1 \Vert}\] \[d = \mathbf{n} \cdot (\mathbf{o}_2 - \mathbf{o}_1)\]

另一种方法则是基于优化的视角，我们分别取两条直线上的动点\(\mathbf{x}_1\)和\(\mathbf{x}_2\)，当它们构成线段的距离取最小值时即为所求：

\[d = \min \Vert \mathbf{x}_2 - \mathbf{x}_1 \Vert = \min \Vert \mathbf{o}_2 + t_2 \mathbf{d}_2 - \mathbf{o}_1 - t_1 \mathbf{d}_1 \Vert\]

对于异面的线段最短距离问题，我们同样可以通过投影或是优化的方法来进行处理。

点与面的距离

要计算点到平面的距离，我们可以利用平面的法向量来计算：

\[d = \frac{\Vert (\mathbf{x} - \mathbf{p}) \cdot \mathbf{n} \Vert}{\Vert \mathbf{n} \Vert}\]

其中点\(\mathbf{p}\)为平面上的任意点，且它的选取不会影响计算结果。另一种计算方法是利用平面的解析表达式\(Ax + By + Cz + D = 0\)，在高等数学和解析几何中我们就解接触过点到平面距离的解析公式：

\[d = \frac{\Vert Ax + By + Cz + D \Vert}{\sqrt{A^2 + B^2 + C^2}}\]

容易验证这两种计算方法是相互等价的。

多边形

多边形的周长和面积

要计算多边形的周长，我们只需要遍历多边形的所有边并求和即可。而要计算多边形的面积，则需要先取平面上的一个固定点\(\mathbf{p}_0\)，按照逆时针的顺序遍历多边形的所有边，在进行遍历时累加这条边与固定点构成三角形的带符号面积即可。

点与多边形的位置关系

要确定一个点是否在多边形内部，可以根据多边形的性质进行分类讨论。凸多边形的情况比较简单，我们可以使用面积法或是绕序法来检测点是否位于多边形内部。如果无法确定多边形是否为凸多边形，则需要使用更加复杂的算法来进行处理，这里介绍光线投射算法以及回转数算法两种方法。

光线投射算法(ray casting)的理论基础是Jordan曲线定理。对于平面上给定的点，我们把该点当作光源向多边形发射光线。如果光线与多边形有奇数个交点则说明点在多边形内，如果有偶数个交点则说明点在多边形外。

回转数算法(turning number)通过考察曲线绕一点的次数来判断该点是否在多边形内。对于多边形内部的点，多边形的边界会正好绕它转过360°，而外部的点则会转过0°。这样只需计算多边形每条边绕定点的回转角度就可以判断点和多边形的内外关系。

三角形

点到三角形的距离

计算点到三角形的距离是图形学中非常基础的问题。当点和三角形位于同一平面时，我们认为点到三角形的距离为0。而当点在三角形外时，则可以先将距离\(d\)取固定点到三角形三个顶点距离的最小值，然后依次计算点到三角形三条边对应线段的距离并进行更新。

而对于三维的情形，则需要先把点投影到三角形所在平面上并计算投影点到三角形的距离。然后结合投影距离就可以得到最终的点到三角形距离。

三角形之间的距离

计算三角形之间的距离需要建立在计算点到三角形距离的基础上。对于二维平面的情况，可以证明两个三角形之间的距离一定会取在其中某个三角形的顶点上。因此我们可以通过计算6组点到三角形的距离并取最小值来得到两个三角形之间的距离。对于三维空间的情况，上述定理同样成立。

三角剖分

三角剖分的目的是将平面上的点集连接成三角网格，并且使得各个三角形的边互不相交。三角剖分有很多种方法，其中最经典的是Delaunay三角剖分(Delaunay triangulation)。从优化的角度来看，Delaunay三角剖分的优化目标是最大化每个三角形的最小角。除此之外，它还有很多优秀的数学性质，比如说它可以保证任意三角形的外接圆内没有其它点、三角化的结果唯一、最外层边界构成凸多边形等。