几何 Geometry

表示方式

隐式表示 Implicit

形式为：$f(x,y,z)=0$.

对于点 $(x,y,z)$

• 若 $f(x,y,z)=0$，则该点在几何体表面上；
• 若 $f(x,y,z)<0$，则该点在几何体内；
• 若 $f(x,y,z)>0$，则该点在几何体外.

显式表示 Explicit

两种方法：

1. 直接给出所有点
2. 参数映射：

$$f:{\mathbb{R}}^2\to {\mathbb{R}}^3;(u,v)\mapsto (x,y,z)$$

Contructive Solid Geometry (CSG) (Implicit)

Combine implicit geometry via Boolean operations.

Distance Function (SDF) (Implicit)

Gradually blend surfaces together using distance functions

距离函数：空间中任意一点距离物体表面的距离，外部为正，内部为负.

通过融合两个物体的距离函数实现表面的融合，先将距离函数融合，再将融合后的距离函数恢复成表面
$$blend=base\ast (1-a)+a\ast current$$

Level Set Methods

怎么通过距离函数求得物体表面呢？

通过一系列的点利用插值方法近似求得“等高线”.

分形 Fractals (Implicit)

分形，具有以非整数维形式充填空间的形态特征。通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。

点云 Point Cloud (Explicit)

点云就是一系列的点 $(x,y,z)$ ，容易表示任何形状的几何体，但是需要大量的数据点。

多边形面 Polygon Mesh (Explicit)

在 3D 计算机图形学和实体建模中，多边形网格是定义多面体对象形状的顶点，边和面的集合。面通常由三角形（三角形网格），四边形（quad）或其他简单的凸多边形（n-gons）组成，因为这可以简化渲染，但通常也可以由凹面多边形甚至带孔的多边形组成。

The Wavefront Object File (.obj) Format

一种文本文件，其中描述了顶点、法线与纹理坐标的信息与它们的联通信息.

• v：顶点坐标 $vertex$
• vt：纹理坐标 $vertextexture$
• vn：法线 $vertexnormal$
• f：面 $face$ 每一行表示一个三角形，对于 a/b/c，a 表示第 a 个顶点，b 表示第 b 个纹理坐标，c 表示第 c 个法线.

上图定义了一个立方体，而立方体只有六条法线，所以有两条为冗余的.

贝塞尔曲线 Bézier Curves

贝塞尔曲线的起点为 $p_0$，终点为 $p_3$，起点方向向量为 $\overrightarrow{p_0{p}_1}$，终点方向向量为 $\overrightarrow{p_2{p}_3}$。

不断进行线性插值，观察到给定 $n+1$ 个控制点 $b_0,b_1,\cdots ,b_n$，可以得到最高为 $n$ 阶的点 $b_0^n$

b 0 1 ( t ) = ( 1 − t ) b 0 + t b 1 b 1 1 ( t ) = ( 1 − t ) b 1 + t b 2 b 0 2 ( t ) = ( 1 − t ) b 0 1 + t b 1 1 b 0 2 ( t ) = ( 1 − t ) 2 b 0 + 2 t ( 1 − t ) b 1 + t 2 b 2

b01​(t)b11​(t)b02​(t)b02​(t)​=(1−t)b0​+tb1​=(1−t)b1​+tb2​=(1−t)b01​+tb11​=(1−t)2b0​+2t(1−t)b1​+t2b2​​

其中
B i n ( t ) = ( n i ) t i ( 1 − t ) n − i B_{i}^{n}(t)=\left(

\right) t^{i}(1-t)^{n-i} Bin​(t)=(ni​)ti(1−t)n−i

特性

以三次贝塞尔曲线(四个控制点，cubic Bézier)为例:

1. $\mathbf{b}(0)={\mathbf{b}}_0,\mathbf{b}(1)={\mathbf{b}}_3$

2. ${\mathbf{b}}^{{}^{\prime }}(0)=3({\mathbf{b}}_1-{\mathbf{b}}_0),{\mathbf{b}}^{{}^{\prime }}(1)=3({\mathbf{b}}_3-{\mathbf{b}}_2)$

3. 仿射变换控制点后绘制的曲线与对曲线上每个点做仿射变换后得到曲线相同，投影变换下不成立.

4. 绘制出的贝塞尔曲线在控制点形成的凸包内

   凸包：能够包围所有点的最小的凸多边形

   

逐段贝塞尔曲线 Piecewise Bézier Curves

如果用多个控制点来画贝塞尔曲线，那么很难通过控制点描述曲线的走势。因此我们分段绘制，然后连接.

一般三次贝塞尔曲线 (四个控制点) 比较常见.

定义：

• $C_0$ 连续：$a_n=b_0$，即两点相连
• $C_1$ 连续：$a_n=b_n=\frac{1}{2}(a_{n-1}+b_1)$，即一阶导相等
• …

Other Types of Splines

Splines 样条

由一系列控制点控制的l连续线条，在任意点都满足一定的连续性.

贝塞尔曲面 Bézier Surface

在两个方向上分别定义贝塞尔曲线：

在一个方向上绘制贝塞尔曲线，将每个贝塞尔曲线上的点当作控制点，在另一个方向上绘制贝塞尔曲线 (显式).

网格操作 Mesh Operaton: Geometry Processing

• 网格细分 Mesh subdivision
• 网格简化 Mesh simplification
• 网格规则化 Mesh regularization

网格细分 Mesh subdivision

Loop Subdivision

• 把每个三角形分裂成四个

  

• 根据权重确定每个顶点的位置，新旧顶点不同处理

  

对于新的顶点

一般情况下，这个新顶点由两个三角形共同拥有，所以它由这两个三角形的顶点来确定位置
$$position=\frac{3}{8}(A+B)+\frac{1}{8}(C+D)$$
对于旧的顶点，

它的新位置 $O^{{}^{\prime }}$ 由自己原本的位置 $O$ 与相邻旧顶点的位置 $V_i$ 决定
$$\begin{gathered} O^{{}^{\prime }}=(1-n\beta )O+\beta \sum _{i=0}^{n-1}{V}_i \\ where\beta =\frac{1}{n}[\frac{5}{8}-(\frac{3}{8}+\frac{1}{4}\cos \frac{2\pi }{n})] \end{gathered}$$
由上式可以看出，顶点的度 $n$ 越大，顶点的新位置就越由原本的位置所决定。

Catmull-Clark Subdivision

如果网格不是三角形网格，则不能用 Loop Subdivision 来细分，那么可以用下面的方法

奇异点定义为度不为 4 的点，选取每个面的中心与每条边的中点作为新顶点，连接每个新顶点

划分三角形新生成了两个奇异点，可以判断非四边形面上的新顶点细分后成为奇异点；细分后不再有非四边形面。这种细分在每次细分后增加非四边形个数个奇异点，之后奇异点数不再会增加

更新顶点：

网格简化 Mesh Simplification

边坍缩 Collapsiing An Edge

边坍缩是一种网格简化的方法.

利用二次误差度量 Quadric Error Metrics 来判断哪些边需要进行坍缩

新顶点应当使它到所有原先顶点相关联的三角形平面的距离和（二次度量误差）最小，我们提前算出每条边的分数，即其二次度量误差，按照由小到大的优先级顺序进行简化

但是，当我们坍缩一条边后，其相连的边也会发生变化，这样的话，变化的边它的二次度量误差也会发生变化。所以我们需要一种数据结构，可以取到最小值，也可以动态更新其他边，所以我们可以用优先队列（堆）作为数据结构。

但这种算法实际上是一种贪心算法，并不一定就是最优解，但是算法的效果不错，所以是不是最优解并不重要.

​