跳转至

5 Geometry

文本统计：约 2710 个字

5.1 Many ways to represent geometry

5.1.1 Implicit（隐式）

不告诉你这些点的位置，但告诉你每个点的关系，比如说告诉你一个关系 \(x^2+y^2+z^2=1\)，我们就知道这是一个三维的半径为1的球。

这种方法的优点为：

（1）compact description (e.g., a function) 拥有一个完美的表示

（2）certain queries easy (inside object, distance to surface) 方便查找，比如说判断这个点在不在这个面上在这个面外和内或者求这个点到表面的距离等等

（3）good for ray-to-surface intersection (more later) 方便与光线求交

（4）or simple shapes, exact description / no sampling error

（5）easy to handle changes in topology (e.g., fluid) ’

这种方式的缺点就是很难表示出复杂的图形

Algebraic surface

直接利用数学公式，严重的问题就是不直观。同时如果我们要表达一个很复杂的形状，更是几乎不可完成的。

Constructive Solid Geometry (CSG)

通过布尔运算组合隐式几何，就像下面这张图表示的就是A和B通过布尔运算所组合成的一些新的物体

Example

如何将复杂的图形用简单图形的二元运算进行表示？

Distance Functions

对于任意一个几何，不直接描述表面，而是描述空间中任何一个点到这个表面的最近距离，所以空间中任何一个点都会定义出一个值来。

下图把两个物体的距离函数定义出来，做一个blending就能融合

Blending a moving boundary

A,B 是两个不同的图，划线区域可认为是一个移动的物体挡住了视口，我们想要画出这两个不同状态的中间值，如果只是将两个图简单融合的话，会得到blend(A,B) ,可以看到这样左边1/3黑的，中间1/3 灰的， 右边1/3 白的（这里黑 白 灰只是方便理解），但如此并不能表示运动信息，其实我们想要的结果应该是 左边1/2 黑的，右边1/2 白的，这样才能表示运行的一个中间状态

我们可以用距离函数来解决这个问题，看\(\text{SDF(A),SDF(B)}\) 物体边界处的值接近0，负的表示在物体里面 (\(\text{SDF}\): Signed distance function)，可以看到，\(\text{blend}\) 两个距离函数就相当于是在 \(\text{blend}\)两个物体的边界，最后再将 \(\text{blend(SDF(A),SDF(B))}\) 恢复成物体即可

Level Set Methods

思想与距离函数基本一致，只是该方法将距离函数写在了格子上，利用双线性插值可以得到 \(f(x)=0\) 的曲线。这个和地理上的等高线道理相似

水平集在3维上的应用：Level Sets from Medical Data（CT， MRL， etc.)

Fractals (分型几何)

自相似，类似于计算机中的递归

5.1.2 Explicit（显示）

我们把所有的点表示出来，或者用参数映射的方式表示出来。All points are given directly or via parameter mapping

什么叫用参数表示出来？

Example

比如说下面这个圆环用显示的方式表达

\[ f(u,v)=((2+cosu)cosv,(2+cosu)sinv,sinu) \]

优点是很容易找到所有的点。

缺点就是判断点在表面内还是表面外

Point Cloud

利用一个点的列表来表示一个形体，非常容易表示各种几何图形，但是如果点比较少模型细节就比较少。

常常在一些模型的扫描中使用生成出来的一般都是点云，之后再转化为一些多边形的面（比较复杂）

Polygon Mesh (广泛应用)

  • 存储顶点和多边形（通常是三角形或四边形）

  • 更容易做处理/模拟，自适应采样

  • 更复杂的数据结构

储存一个模型的文件 The Wavefront Object File (.obj)

这是一个立方体的模型数据例子。3-10行定义了立方体的8个顶点信息。 12-25行定义了这些顶点的纹理坐标信息(每个面4个点，共6个面所以最多有24种不同的纹理坐标信息，这里有一些纹理对于不同面上的点是公用的)。 27-34行定义了6个面的法线信息，为什么有8个是因为建模软件输出的精度问题不必在意，其中有两个是重复的。最重要的就是36-47行了，f 代表一个面，其中x/x/x的第一位表示是哪个顶点，第二位表示该顶点纹理坐标是第几个，第三位表示法线信息是第几个。 3个 x/x/x表示3个顶点的信息构成一个面。

5.2 Curves

5.2.1 Bézier Curves

用一系列的控制点去定义某一个曲线，使得这条曲线满足某些性质，比如，给出如下图所示的4个控制点，我们定义一条曲线，使其射出切线以及收尾切线方向满足

\[ t_0=3(p_1−p_0),t_1=3(p_3−p_2) \]

5.2.2 De Casteljau Algorithm

1 Algorithm

以构建二阶贝塞尔曲线为例：

  • 考虑三个点

  • 在\(b_0b_1和b_1b_2\)进行插值操作（比例为t）得到\(b^1_0和b^1_1\)

  • 然后对\(b^1_0b^1_1\)之间再进行插值操作（比例为t）

  • 对t在\([0,1]\)之间运用同样的算法进行遍历即可得到相应贝塞尔曲线

2 Algebraic Formula

以二阶贝塞尔曲线为例：

\[ \begin{aligned} b^1_0(t)&=(1-t)b_0+tb_1\\ b^1_1(t)&=(1-t)b_1+tb_2\\ b^2_0(t)&=(1-t)b^1_0+tb^1_1\\ \end{aligned} \]
\[ \Rightarrow b^2_0(t)=(1-t)^2b_0+2t(1-t)b_1+t^2b_2 \]

将贝塞尔曲线的阶数从 2 推广到 \(n\)，得到 Bernstein form of Bézier curve of order n:

\[ b^n(t)=b_0^n(t)=\sum_{j=0}^nb_jB_j^n(t) \]

其中 Bernstein polynomials为

\[ B_i^n(t)=\left(\begin{matrix}n\\i\end{matrix}\right)t^i(1-t)^{n-i} \]

Example

在三维中使用伯恩斯坦多项式同样可以得到贝塞尔曲线

3 Properties of Bézier Curves

Interpolates endpoints

  • For cubic Bézier: \(\bf{b}(0)=\bf{b}_0;\ \bf{b}(1)=\bf{b}_3\)

Tangent to end segments

  • Cubic case: \(\bf{b}'(0)=3(\bf{b}_1-\bf{b}_0);\ \bf{b}'(1)=3(\bf{b}_3-\bf{b}_2)\) 只需要对 \(t\) 求导就可以了

Affine transformation property

  • Transform curve by transforming control points
  • 对贝塞尔曲线进行仿射变换，只需要对控制点进行仿射变换（仅仅对于仿射变换成立）

Convex hull property

  • Curve is within convex hull of control points（曲线在控制点的凸包内）

4 Piecewise（逐段） Bézier Curves

贝塞尔曲线在高阶时，曲线很难被控制点控制

所以我们将贝塞尔曲线分段化 (Piecewise)，最为常见的就是分为三阶贝塞尔曲线的集合

5 Continuity

对于分段的贝塞尔曲线，在一个断点的连续性：

\(C^0 \text{continuity}\) \(a_n=b_0\) 意为第一段的终止点等于第二段的起始点

\(C^1 continuity:\) \(a_n=b_0=\frac{1}{2}(a_{n-1}+b_1)\) 意为切线方向相同，大小也相同

5.2.3 Splines

a continuous curve constructed so as to pass through a given set of points and have a certain number of continuous derivatives. 简单的来说就是一个可控的曲线。

样条里面比较常见的有B spline，它有一个好的性质就是局部性

  • Require more information than Bezier curves

  • Satisfy all important properties that Bezier curves have

过于复杂，在此不多阐述。

5.3 Surfaces

Bézier Surfaces

Bi-cubic Bézier Surface Patch

怎么样将贝塞尔曲线扩展到贝塞尔曲线？以上述例子为例，用16个点控制一个曲面的过程是先将每列的四个点做贝塞尔曲线，然后做横切面之后与四条线相交于四个点接着再做贝塞尔曲线进而得到一个曲面。

比如说下图，灰色的线就是每列的控制点得到的贝塞尔曲线，然后对每一行交四个点作为新的四个控制点再做贝塞尔曲线，遍历得到贝塞尔曲面。

For bi-cubic Bezier surface patch,

  • Input: \(4\times4\) control points
  • Output is \(2D\) surface parameterized by \((u,v)\) in \([0,1]^2\)

贝塞尔曲线上的每一个点都与 \([0,1]\) 上的每个 \(t\) 相对应，贝塞尔曲面上每一个点都与\([0,1]^2\)上的\((u,v)\)相对应。

5.4 Mesh Operation

  • Mesh subdivision 网格的细化 (Up-sampling)【从图二到图三】
  • Mesh simplification 网格的简化 (Down-sampling)【从图二到图四】
  • Mesh regularization 网格的正规化（让每一个三角形都与正三角形相似，没有很尖的三角形）(same #triangles)Subdivision【从图二到图三】

5.4.1 Subdivision

1 Loop Subdivision

Common subdivision rule for triangle meshes

大致思路：首先，创建更多的三角形（顶点）；其次，调整它们的位置

具体步骤：

  • 将每个三角形分为四个三角形

  • 调整顶点的位置 （新的顶点和老的顶点更新的方法不同）

对于新的顶点，更新为

\[ \frac{3}{8}\times(A+B)+\frac{1}{8}\times(C+D) \]

对于旧的顶点，根据周围点的数量以及周围点的坐标和自身原来的坐标来更新现在的坐标。

展示一下Loop Subdivision 的结果

2 Catmull-Clark Subdivision

针对一般的情况，做细分的方式。loop subdivision只能做三角形网格的情况。

首先我们定义：Non-quad face (非四边形面) & Extraordinary vertex (奇异点 degree != 4)

每一次细分我们都先取每条边的中点以及每个面的中点并相互连接。这样我们增加了一定数量的奇异点（与原先Non-quad face 数量相同），但是所有的表面都变成了四边形 。

对于每个点的更新：

5.4.2 Simplification

Goal: reduce number of mesh elements while maintaining the overall shape

我们可以观察到3000个三角形与30000个三角形对模型的表现几乎差不多，但是三角形更少的话，形体表现就不理想了，但是如果这个模型特别小的话（比如下面那一行），那么30000和3000就更看不出来有什么区别了，甚至300个三角形都足够了。所以我们要在不停的情况下使用不同复杂程度的几何模型。

Edge collapse (边坍缩)

Quadric Error Metrics (二次误差度量)

二次误差：新顶点到之前相关三角形平面的平方和应该最小化！

不使用平均值，因为其未能较好反映出原本的形状。而是采用了一种类似于最小二乘法的方法来估计

我们对每条边计算如果这条边坍缩了，其最优的点造成的二次误差，然后我们每次坍缩就坍缩造成二次误差最小的边，然后更新其他边。可以使用一个堆结构来存储

Which edges? Assign score with quadric error metric

  • approximate distance to surface as sum of distances to planes containing triangles
  • iteratively collapse edge with smallest score
  • greedy algorithm... great results!

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！