Geometry

Many Ways to Represent Geometry

表示几何有隐式和显式的方法

“Implicit” Representations of Geometry

隐式指的是不会告诉空间中的点具体在哪，而是会说这些点满足的关系。比如说对于一个球，隐式的表示可以是 $x^{2}+y^{2}+z^{2}=1$ 。普遍而言，就是 $f(x,y,z)=0$ 。

隐式表示的缺点：不直观。比如对于 $f(x,y,z)=(2-\sqrt{x^{2}+y^{2}})^{2}+z^{2}-1$ ，我们并不能直观的看出哪些点在 $f(x,y,z)=0$ 上。但如果将其画出来，形状还是比较简单的

优点：判断某个点和几何形体的关系比较简答。比如想判断点 $(\frac{3}{4},\frac{1}{2},\frac{1}{4})$ 是否在 $f(x,y,z)=x^{2}+y^{2}+z^{2}-1=0$ 内，可以直接将该点代入，有 $f(x,y,z)=-\frac{1}{8}<0$ ，因此在里面。

“Explicit” Representations of Geometry

最直观的显示表达方法就是之前提到的用三角形的表示方法。同时还有一种不那么直观，但同样是显示的方法，就是通过参数映射来定义表面。普遍而言，就是 $f:\mathbb{R}^{2}\rightarrow \mathbb{R}^{3};(u,v)\rightarrow (x,y,z)$ 。

比如说，给定 $f(u,v)=((2+\cos u)\cos v,(2+\cos u)\sin v,\sin u)$ ，就是一种显示的表示，表示的同样是上面那张圆环图片。只要遍历 $u$ 和 $v$ ，就能遍历几何形体上的所有点。

但是显式的就不容易判断一个点是否在几何图形内。

More Implicit Representations in Computer Graphics

Algebraic Surfaces (Implicit)

直接用数学公式表示(就是之前举的隐式的例子)。对于稍微复杂一些的图形会很难表示。

Constructive Solid Geometry (Implicit)

用基本几何的布尔运算来表示更复杂一点的几何形体

Distance Functions (Implicit)

可以使用距离函数对两个表面进行blend操作。

像第一行那样，假如直接对两幅图做blend，那么会得到左边黑，中间灰，右边白的结果，而不是一个运动的中间结果。因此我们先求出一个有向的距离函数(这里是一个点到边界的最短距离，外侧为正，内测为负)，然后对这两个距离函数做blend，然后就会得到一个中间状态的距离函数，将该距离函数恢复成形状，就是我们想要的中间状态。

Level Set Methods (Also implicit)

那么如何从距离函数中重新恢复形状，得到物体表面？假如是有一个解析的函数，令 $f(x)=0$ 即可。但如果解析的形式不太好得到，可以使用水平集(类似于等高线)。就是将距离函数在各个格子中的值写出来，最后就能画出距离为 $0$ 的一条曲线，就是表面

Fractals (Implicit)

分形(自相似)。类似于算法中的递归。

Implicit Representations - Pros & Cons

优点

表示简短，方便存储
方便判断一个点是否在图形内
方便计算和光线相交关系
对于简单的模型，能够很简单的描述
比较容易变换拓扑结构

缺点：

不方便表示特别复杂的图形

Explicit Representations in Computer Graphics

Point Cloud (Explicit)

最简单的表示方法：表示出一堆点来，只要点和点之间足够密，就能得到想要的几何图形。因此理论上点云可以表示任意的几何形体。

在三维空间做扫面，输出一般就是点云。而将点云转化为三角形则需要一定的算法。

Polygon Mesh (Explicit)

在图形学中运用的最为广泛。

The Wavefront Object File (.obj) Format

如何用多边形来表示图形。通常将数据放在文本文件.obj中，一个文件存储一个物体。

这个文件存储的是一个立方体。图中的v存储点，vn定义的是法线，vt定义的是纹理坐标，最后的f(face)则表示由哪三个点构成一个三角形。其中第一个数字选取一个点，第二个数字表示选择第几个纹理坐标，第三个数字表示选取第几个法线。

比如说 f 5/1/1 1/2/1 4/3/1 就表示需要连接5，1，4这三个点，使用第1，2，3个纹理，以及三个点都是用第1个法线。

Curves

Bézier Curves

贝塞尔曲线是需要用一系列控制点来定义一条曲线。曲线需要满足性质：起点和终点分别在 $p_0$ 和 $p_3$ 上，同时切线也需要分别为 $p_0p_1$ 和 $p_2p_3$ 。

Evaluating Bézier Curves (de Casteljau Algorithm)

现在考虑给定一系列任意多个(大于等于三个)控制点，如何画出贝塞尔曲线。

首先考虑三个控制点的情况(此时做出的曲线叫二次贝塞尔曲线 quadratic Bezier)。给定参数 $t\in [0,1]$ ，对于任意的 $t$ ，在图像上我们令 $b_0b_0^{1}=t\cdot b_0b_1$ ， $b_1b_1^{1}=t\cdot b_1b_2$ ， $b_0^{1}b_0^{2}=t\cdot b_0^{1}b_1^{1}$ ，最终如图所示得到的 $b_0^{2}$ 点就是贝塞尔曲线的轨迹。

对于四个控制点的情形也是类似的

对于更多个控制点，递归操纵即可。

Evaluating Bézier Curves Algebraic Formula

首先还是考虑三个控制点的情形

$\begin{aligned} b_0^{1}(t)&=(1-t)b_0+tb_1 \\ b_1^{1}(t)&=(1-t)b_1+tb_2 \\ b_0^{2}(t)&=(1-t)b_0^{1}+tb_1^{1} \\ \Rightarrow b_0^{2}(t)&=(1-t)^{2}b_0+2t(1-t)b_1+t^{2}b_2 \end{aligned}$