几何表示方法的分类

• 隐式
  • 可以通过一个函数来表示的几何体。给出点满足某些特定关系 Points satisfy some specified relationship
  • 例如圆可以表示为f（x，y，z）=0（通常将关系化为该形式）

• 显式
  • 通过参数映射表示的几何体（uv坐标转换为xyz坐标） / 直接表示
    • 参数映射：通过某个带有u，v的函数分别表示出x，yz的坐标
  • 直接给出几何体
  • 缺点：难以判断点在内部还是外部 Inside/Outside tests hard
  • 优点：容易看出来几何体的真实形状，容易判断面上的点在哪 Sampling Is Easy

隐式几何 “Implicit” Representations of Geometry

代数曲面(Algebraic surfaces)、CSG(Constructive solid geometry)、水平集(Level set methods)、分形(Fractals)…

代数曲面 Algebraic Surfaces

表面是x、y、z的多项式的零点集 Surface is zero set of a polynomial in x, y, z

CSG Constructive Solid Geometry

通过布尔运算组合隐式几何 Combine implicit geometry via Boolean operations

距离函数 Distance Functions

• 不直接描述几何的表面，而是描述空间中任何一个点到该表面的最近距离(垂直)
• signed表示有正负，0表示就在几何表面上，+表示在外部，-则在内部
• 这种方法是通过融合(Blend)距离函数的方式来描述新的物体，得到融合后的距离函数后，可以令距离函数为0时的位置为表面

如下是直接融合两张图和融合距离函数的差别：
对这两个函数做一个线性的融合，然后就可以找到融合的新的边界(数值为0的那些点)，并且负数表示物体内部，正数表示外部，进而得到新的几何形体，两个距离函数相加,就是两个物体表面的特征融合相加

水平集 Level Set Methods

• 对于融合距离函数的方法，得到融合后确定的函数后，可以通过距离函数为0的地方确定为表面；对于解析式很难描述的复杂形状，替代方案是存储数值近似函数的网格，然后通过插值找出为0的表面Closed-form equations are hard to describe complex shapes. Alternative: store a grid of values approximating function
• 可以提供对形状的更明确的控制(如纹理) Provides much more explicit control over shape (like a texture)
• 在地理上有类似概念——等高线

水滴在落下四溅的过程中也可以通过定义距离函数或水平集的方式表述水滴和水滴融合在一起后的表面 Level set encodes distance to air-liquid boundary

分形 Fractals

• 表现出自相似性 Exhibit self-similarity, detail at all scales
• 经常被用来描述一些自然现象 “Language” for describing natural phenomena
• 难以控制形状 Hard to control shape!

隐式几何的优缺点 Implicit Representations – Pros & Cons

• 优点 Pros： 
• 简洁的描述(如一个函数) compact description (e.g., a function)
• 某些查询容易(物体内部，到表面的距离，点是否在几何体上) certain queries easy (inside object, distance to surface)
• 利于求光线到表面的交集 good for ray-to-surface intersection
• 对于简单的形状，描述准确/没有采样错误 for simple shapes, exact description / no sampling error
• 容易处理拓扑结构的变化(如流体) easy to handle changes in topology (e.g., fluid)
• 缺点 Cons： 
• 难以创建复杂的形状 difficult to model complex shapes
• 缺点：难以通过函数判断出几何体的真实形状

显式几何 “Explicit” Representations of Geometry

三角形面(triangle meshes)、贝塞尔曲面(Bezier surfaces)、曲面细分(subdivision surfaces)、非均匀有理B样条(NURBS)、点云(Point Cloud)…

点云 Point Cloud

• 最简单的表示方法：点列表(x,y,z) Easiest representation: list of points (x,y,z)
• 轻松表示任何类型的几何体 Easily represent any kind of geometry
• 适用于足够大型的数据集 (>>1 点/像素) Useful for LARGE datasets (>>1 point/pixel)
• 通常转换为多边形网格 Often converted into polygon mesh
• 难以使用欠采样的数据进行绘制 Difficult to draw in undersampled regions

多边形面 Plygon Mesh

• 存储顶点和多边形(通常是三角形或四边形) Store vertices & polygons (often triangles or quads)
• 更容易进行处理/模拟，自适应采样 Easier to do processing / simulation, adaptive sampling
• 更复杂的数据结构 More complicated data structures
• 也许是图形中最常见的表示 Perhaps most common representation in graphics

• obj格式文件经常用于图形研究 Commonly used in Graphics research 
• OBJ格式讲几何体的点、法线、纹理坐标分别表示，然后再表示，面与面的连接关系 Just a text file that specifies vertices, normals, texture coordinates and their connectivities

• v：顶点8个
• vt：纹理坐标，其中有共用的纹理坐标，下面代码是用软件生成的，会有重复问题。
• vn：法线，6个面有6个法线，但vn却有8个，重复定义，3 4行、5 6行是一样的(忽略精度)
• f：顶点索引，定义哪三个点组成三角形，后面分别是定义顶点对应的纹理坐标、法线。

曲线 Curves

接下来从曲线开始详细说明其他显式几何表示方法

曲线的应用 Examples of Curves

• 镜头的运动路径 Camera Paths
• 物体沿曲线运动的动画 Animation Curves
• 矢量文字 Vector Fonts

贝塞尔曲线 Bézier Curves

贝塞尔曲线是需要一系列的控制点去定义的一个曲线，这个曲线满足一些性质，比如下图的要沿着切线方向

贝塞尔曲线的计算——de Casteljau Algorithm

1. 定义三个点(二次贝塞尔曲线) Consider three points (quadratic Bezier)
2. 根据t值在两条边上分别插值出两个点 Insert two points using linear interpolation on both edges
3. 连接两个点再次根据t值插值 Repeat recursively
4. t在[0,1]中不断取值，最终插值得到的点移动的路径即为贝塞尔曲线 Run the same algorithm for every t in  

三次贝塞尔曲线(Cubic Bézier Curve)也一样

贝塞尔曲线的代数表示

de Casteljau算法给出了这样一个代数金字塔 de Casteljau algorithm gives a pyramid of coefficients

三次贝塞尔曲线的代数表示如下，写出后发现各项系数正好是二项式平方 \(\left((1 – t) + t\right)^2\)
展开的结果 Example: quadratic Bézier curve from three points

推广到n阶，展开项系数是一个描述二项分布的多项式(可以用伯恩斯坦公式来表达)

这里的(n,i)是组合C(n,i)的意思,注意c(n,0)=1

当n=3时，我们可以用来表示三维空间中的贝塞尔曲线

\(b^3(t) = b_0(1-t)^3 + b_1 3t(1-t)^2 + b_2 3t^2(1-t) + b_3 t^3\)

三次贝塞尔曲线下伯恩斯坦多项式对应图像

贝塞尔曲线的性质

• 对于三次贝塞尔曲线，插值的端点： b(0)=b0​；b(1)=b3​
• 对于三次贝塞尔曲线，与端点相切的切线表示的系数为3： b′(0)=3(b1​−b0​)；b′(1)=3(b3​−b2​)
• 在仿射变换时，只需要对顶点做仿射变换，就能得到这个贝塞尔曲线在仿射变换下的结果(注意限制了时仿射变换，投影变换时不成立) Transform curve by transforming control points
• 贝塞尔曲线在控制点形成的凸包(能够包围给定点的最小凸多边形 – 套一个橡皮筋)内 Curve is within convex hull of control points

分段贝塞尔曲线

当控制点比较多时，贝塞尔曲线并不直观，不易控制

为了便于控制曲线，可以定义多段贝塞尔曲线然后连起来，普遍习惯每四个控制点定义一段 Piecewise cubic Bézier the most common technique

钢笔工具画曲线就是这个原理，用相邻的4个点做分段贝塞尔曲线

分段贝塞尔曲线的连续性 Piecewise Bézier Curve – Continuity

– \(C^0\) 连续：只需要点相同 \(a_n = b_0\) ，第一段终点等于第二段起点

– \(C^1\) 连续：点相同并且切线也在一条线上 \(a_n = b_0 = \frac{1}{2}(a_{n-1} + b_1)\)

– \(C^1\) 连续看起来已经不错了，但不能达到工业要求

其他样条曲线 Other types of splines

样条 Spline

• 样条是通过一定控制点控制的连续的曲线

B样条 B-splines

• B是基函数 Short for basis splines
• B样条具有局部性，不会像贝塞尔曲线一个点影响整个曲线 Require more information than Bezier curves
• 满足贝塞尔曲线具有的所有重要属性(即超集) Satisfy all important properties that Bézier curves have (i.e. superset)
• 本课程没有再详细讲解B样条和非连续性NURBS，推荐了胡事民老师的课

曲面

贝塞尔曲面 Bézier Surfaces

1. 分别计算四条贝塞尔曲线的在u时间上的位置，得到这条移动贝塞尔曲线的4个控制点（控制点就是用来“拉”出贝塞尔曲线形状的那几个关键点） Use de Casteljau to evaluate point u on each of the 4 Bezier curves in u. This gives 4 control points for the “moving” Bezier curve
2. 4个不同的点认为是另一条方向与其垂直的贝塞尔曲线的控制点，可以画出蓝色的曲线，然后的移动贝塞尔曲线在v时间上的位得到完整的面 Use 1D de Casteljau to evaluate point v on the “moving” curve

通过把(u ,v) 映射到表面，计算出表面的位置 Evaluate surface position corresponding to (u,v)

 几何处理Geometry processing

• 网格细分
  • 让网格的面数更多
  • Loop细分
  • Catmull-Clark细分
• 网格简化
  • 让网格面数更少
  • 边坍缩
    • 通过“二次误差度量”得到坍缩后最优的点
• 网格正规化
  • 让网格中的三角形趋近于正三角形

网格细分Mesh Subdivision

Loop细分 Loop subdivision

• 不是循环细分，只是发明人的名字叫loop。将每个三角形变为4个三角形
• 根据新/旧顶点权重不同，更新顶点位置

对于新的顶点： \(V’ = \frac{3}{8} \cdot (A + B) + \frac{1}{8} \cdot (C + D)\)

• V′ 为新的顶点变换后的位置
• A、B 分别为于两个面被共享边的老顶点
• C、D 为非共享边的两个顶点。

对于旧的顶点：V′=(1−n⋅u)⋅V+original_position⋅neighbor_position_sum

• V′ 为旧的顶点变换后的位置
• n 为顶点的度（链接的顶点数）
• 如果 \(n=3\) 则 \(u=\frac{3}{16}\)，其他情况 \(u=\frac{3}{8n}\)
• neighbor_position_sum 为邻居点的平均位置
• original_position 为旧顶点原本的位置

Loop细分的结果

问题：只能对完全为三角形的几何体进行细分

Catmull-Clark细分

Loop细分只能用于三角形网格，但是Catmull-Clark细分可以定义四边形面与非四边形面

1. 度不为4的点，定义为奇异点，图中有2个奇异点
2. 在一次细分过程中，取边上的中点和面中心上的一个点，把这些点连起来
3. 一次细分结束后，引入了两个度为3的奇异点(两个三角形中点的点)，一共有4个奇异点；也就是说一次Catmull-Clark细分会将非四边形面都变为四边形，并且每一个非四边形面消失，就会引入一个新的奇异点
4. 继续细分，奇异点数目不变（因为Catmull在一次细分之后就再也没有非四边形面了）

顶点位置更新规则

新顶点，分为面新增点和边新增点

旧顶点，不光受8个新顶点影响还有4个旧顶点的影响

两种细分方法收敛结果的对比 Convergence: Overall Shape and Creases

网格简化 Mesh Simplification

目的：在保持整体形状的同时减少网格元素的数量

• 如果说MipMap是纹理上的层次结构——根据不同距离(覆盖像素区域的大小)选择不同层的纹理
• 那么LOD就是几何的层次结构——根据不同距离(覆盖像素区域的大小)选择不同的模型面数
  •  Level of Detail 细节层次

边坍缩 Collapsing An Edge

如果将减面时候的点直接平均将会得到左边的图，显然不理想。通过二次误差度量得到右边的点得到理想效果
二次误差 Quadric Error Metrics：新顶点的位置应该使得与先前的边(面)的距离平方之和最小

• 简单假设每一条边如果坍缩会导致多大的二次度量误差，然后从二次度量误差最小的开始坍缩
• 但是坍缩一条边后会改变其他的边的位置，其他边的二次度量误差也必须重新算，所以我们需要每次坍缩完二次度量误差最小的边后，动态的更新其他受影响的边，需要使用到的数据结构是优先队列/堆
• 通过对局部进行最优解，试图找到全局的最优解，这是一个典型的贪心算法
• 使用二次度量误差的简化结果 Quadric Error Mesh Simplification