计算机图形学【GAMES-101笔记】几何(距离函数、点云、贝塞尔曲线、曲面细分、二次误差网格体简化)

2021/12/11 23:50:18

编程Tag： 函数 曲线 几何 图形学 顶点 点云 控制点 贝塞尔 games

本文主要是介绍计算机图形学【GAMES-101笔记】几何(距离函数、点云、贝塞尔曲线、曲面细分、二次误差网格体简化)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Lecture10~12

  • 1 几何图形的表示方式
    • 1.1 几何的隐式表示法
      • 1.1.1 函数
      • 1.1.2 Constructive Solid Geometry(CSG)
      • 1.1.3 距离函数
      • 1.1.4 水平集(Level Set)
    • 1.2 几何的显式表示法
      • 1.2.1 点云(Point Cloud)
      • 1.2.2 多边形模型
      • 1.2.3 贝塞尔曲线
      • 1.2.4 Splines样条线
      • 1.2.5 贝塞尔曲面
  • 2 几何的操作方式
    • 2.1 曲面细分
      • 2.1.1Loop细分(Loop Subdivision)
      • 2.1.2 Catmull-Clark细分
    • 2.2 曲面简化
      • 2.2.1 边坍缩
      • 2.2.2 二次误差网格简化
  • GAMES101图形学专栏

1 几何图形的表示方式

1.1 几何的隐式表示法

  • 优点
    (1)容易表述(一个函数就行)，对于存储空间来说非常有利
    (2)判断一个点在几何内/外特别快
    (3)与光线求交点特别容易
    (4)对于简单的形体，描述非常准确，不容易出现误差
    (5)处理变化的拓扑结构非常容易，比如流体模拟
  • 缺点：很难用函数描述一个复杂的模型，复杂的模型只能用显示表示咯

1.1.1 函数

  • 不告诉点的具体位置，只描述点的关系,即只给一个函数，表示一个几何形体
  • 缺点：非常抽象，不能马上知道是个什么样的几何模型。
  • 如下，前两个还好，后面一个光看公式你能知道是个什么三维图形么，不知道！
    在这里插入图片描述

1.1.2 Constructive Solid Geometry(CSG)

  • 就是用布尔运算来组合模型
    在这里插入图片描述

1.1.3 距离函数

  • 不直接描述几何的表面，而是描述空间中任何一个点到该表面的最近距离(垂直)
  • 有正负，0表示就在几何表面上，+表示在外部，-则在内部
  • 这种表示非常适合做圆滑过度的边界
    下面图：几何图形->算出俩球的距离函数->对距离函数做融合->恢复成新的几何图形。
    这个图，一开始是两个球，并且也算出了距离函数

在这里插入图片描述

  • 非常重要的解释图
    输入：某种物体的边界，A图的物体覆盖屏幕的1/3，B物体覆盖屏幕2/3
    在这里插入图片描述
    希望：做个线性融合，求出中间状态
    操作：
    (1)求出A,B的距离函数，如A 在1/3处是边界所以边界上的点全是0；边界左边的点在物体内部，所以为负数且越远负值越大，边界右边的点则正数递增。B同理。
    (2)然后对这两个函数做一个线性的融合(具体怎么操作不知道)，然后就可以找到融合的新的边界(数值为0的那些点)，并且为负数的表示物体内部，为正数表示外部，进而得到新的几何形体。

在这里插入图片描述

  • 对任意的两个几何模型，算出其距离函数->做函数线性混合->再变回几何模型->得到混合的模型

  • 太抽象，反正吧就那个意思但才疏学浅脑子不行描述不清楚。。。

  • 总而言之言而总之，就是两个距离函数F1，F2混合得出新的距离函数F新，这个距离函数呢，在空间中所有为0的点就是新的边界了，为负的点就是几何内部，为正就是几何外部，从而得到新的融合之后的图形，不知道说没说清楚。。不行的话就搜索别的大佬的文章吧- - 。
    在这里插入图片描述

  • 距离函数的应用
    下面这个场景的模型就是用距离函数来定义的，所以看起来才会那么的丝滑
    在这里插入图片描述
    在这里插入图片描述

  • 如何从距离函数得到几何体的表面呢？

1.1.4 水平集(Level Set)

  • 从距离函数，反求几何表面就是，类似的隐函数告诉了函数式f(x,y,z) = 0，求物体是个啥样
    但是有些距离函数连写成f(x,y,z) = 0很困难咋办，用水平集
  • 2D空间中
    在不同的格子中心有不同的值，格子之间的值用双线性插值可以求出来；在这样一个平面中里面找函数值为0的点连起来就是物体边界了f(x,y) = 0了
    在这里插入图片描述
  • 3D空间中的水平集
    跟3D纹理联系起来了，3D纹理就是描述的三维中物体的任意一个点的属性；但怎么找边界呢
    定义所有点的密度，比如骨骼的密度是5，那就找到空间中所有5的点连起来就得到边界了。
    在这里插入图片描述

1.2 几何的显式表示法

  • (1)直接给出所有点在空间的位置
  • (2)通过映射的方式给出、一张纹理图的每个uv坐标对应空间中一个点，遍历所有uv即得到几何形体
    在这里插入图片描述
  • 显示表示的优缺点
    优点：很容易、快速得到几何模型
    缺点：判断点是否在几何内/外很困难

1.2.1 点云(Point Cloud)

  • 最简单的表示方法：点(x,y,z)列表
  • 点云可以表示任何类型的几何体
  • 很少用，一般扫描出来的原始数据是点云数据
    在这里插入图片描述
    一般会把扫描出来的点会将其转换成不同的面再计算着色
    在这里插入图片描述

1.2.2 多边形模型

  • 用得最广泛的方法，一般用三角形或者四边形来建模
    在这里插入图片描述
  • 在代码中怎么表示一个三角形组成的模型？
    .obj文件：描述了“顶点、法线、纹理坐标、顶点组合关系”
    比如下面代码，描述的就是个立方体
    v：顶点8个
    vt：纹理坐标，其中有共用的纹理坐标，下面代码是用软件生成的，会有重复问题。
    vn：法线，6个面有6个法线，但vn却有8个，重复定义，3 4行、5 6行是一样的(忽略精度)
    f：顶点索引，定义哪三个点组成三角形，后面分别是定义顶点对应的纹理坐标、法线。
    在这里插入图片描述
  • 对几何的处理
    网格细分：增加模型面数
    网格简化：减少模型面数
    网格正规化：让网格大小更均匀、接近正三角形
  • 游戏引擎中的LOD技术不就是动态的进行网格细分/简化么。

1.2.3 贝塞尔曲线

以三次贝塞尔曲线为例
起点P0，终点P3， 起点切线P0P1，终点切线P2P3
P1和P2其实没啥关系，但是一般还是给他们俩连个线的
在这里插入图片描述

  • 如何用三个控制点确定一条二次贝塞尔曲线？？？————de Casteljau算法
    (1)认为时间从0~1，从0开始每个时刻都找到曲线的一个点，到1时就得到整个贝斯尔曲线
    (2)任取一个时刻t，根据t在时间的比例，分别插值三次(两个线段分别做一次，对得到的两个点之间再做一次插值)，最终得到的点就是曲线的一个点。
    在这里插入图片描述
  • 2次贝塞尔曲线(动图是偷来的…)

请添加图片描述)

  • 3次贝塞尔曲线

请添加图片描述

  • 贝塞尔曲线的代数公式
    比如2阶曲线是由3个顶点和时间t 做计算得到的，那么一定可以写出一个公式来表述。
    在这里插入图片描述
  • 更一般，给n个控制点，在t时刻的曲线点的计算公式
    在这里插入图片描述
    伯恩斯坦多项式：i = 1，2，3，…，n
    在这里插入图片描述在这里插入图片描述
    最终就算是3D空间的点，只需要更改每个点为三维坐标即可
    在这里插入图片描述
    在这里插入图片描述
    具体伯恩斯坦多项式推导可看这篇文章
  • 贝塞尔曲线好用的性质
    (1)首/尾两个控制点一定是起点/终点
    (2)对控制点做仿射变换(投影不行)再重新画曲线，跟原来的一样，不用一直记录曲线上的每个点
    (3)凸包性质：画出的贝塞尔曲线一定在控制点围成的线之内
  • 请逐段使用贝塞尔曲线(一般用4个控制点、3次曲线)这在各种游戏引擎中很常见
    在这里插入图片描述

1.2.4 Splines样条线

一条由一系列控制点控制的曲线
在这里插入图片描述

  • B-splines 基样条
    对贝塞尔曲线的一种扩展，比贝塞尔曲线好的一点是：局部性，可以更局部的控制变化。
  • NURBS
    比B样条更复杂的一种曲线，了解即可。

1.2.5 贝塞尔曲面

  • 将贝塞尔曲线扩展到曲面
    依然是用多段贝塞尔曲线对应曲面进行无缝拼接的。
    在这里插入图片描述
  • 三次贝塞尔曲面
    下面这个曲面 是4x4=16个控制点应用双线性插值形成的
    在这里插入图片描述
  • 插值
    很容易理解，每4个控制点可以绘制出一条贝塞尔曲线，贝塞尔曲线上时刻t的值是通过3次插值得来的，这样在t时刻一共4条贝塞尔曲线又能分别提供1个控制点，一共4个控制点，再插值画一条贝塞尔曲线(下图蓝色部分)，这条线就是t时刻的平面的线，然后每个时刻都画一条线则得到贝塞尔曲面。
    在这里插入图片描述
    容易理解
    在这里插入图片描述
    注意时间那个变量变成二维了，t1 、t2用uv表示也行
    (u,v)对应两个时间，u时刻算的是4个控制点的位置，v时刻则是这四个控制点控制的贝塞尔曲线的点的位置，即最终曲面的位置。
  • 因为用(u,v)表示最终位置，所以贝塞尔曲面也是一种显示的表示
    在这里插入图片描述

2 几何的操作方式

2.1 曲面细分

2.1.1Loop细分(Loop Subdivision)

Loop是人名
两步：先增加三角形个数，后调整位置
如下图，够明显了吧，不仅仅是增加三角形的个数，还要调整新/旧顶点的位置。
在这里插入图片描述

  • 新顶点调整方法
    对于中间那个白点，处于共线的A、B顶的权重相对C、D高一些
    在这里插入图片描述
  • 旧顶点调整方法
    n：旧的顶点连接的边的数量为度，度越多，则自身位置的权值越小
    u：u就是个影响系数系数，n=3时，u=3/16；否则u=3/8n
    在这里插入图片描述
  • loop细分的结果
    很明显确实光滑了不少
    在这里插入图片描述

2.1.2 Catmull-Clark细分

这种细分对于更一般的情况效果也很好，(全三角形、全四边形、三角形四边形混合)
·

  • 细分步骤
    1)给每个面增加1个顶点
    2)给每条边增加1个中点
    3)连接所有新增加的点
  • 一次细分后
    奇异点增加了2个(有多少个非四边形面就增加多少个)
    非四边形面0个(不管多少个全部消失)
    在这里插入图片描述
  • 再细分下去
    奇异点不会再增加，因为首次细分后全是四边形了 顶点的度也不会变 在这里插入图片描述
  • 顶点位置更新规则
  • 新顶点，分为面新增点和边新增点
    在这里插入图片描述
  • 旧顶点，不光受8个新顶点影响还有4个旧顶点的影响
    在这里插入图片描述
  • 最终效果特别好
    在这里插入图片描述

2.2 曲面简化

减少三角形数量的同时保持原有的基本形状
可以看到，如果离得很远3万面和3000面甚至是300面根本看不出啥区别，仅仅笑掉大牙而已
所以在大型项目中应用LOD技术是非常有必要的！
在这里插入图片描述
如果说MipMap是纹理上的层次结构——根据不同距离(覆盖像素区域的大小)选择不同层的纹理
那么LOD就是几何的层次结构——根据不同距离(覆盖像素区域的大小)选择不同的模型面数

2.2.1 边坍缩

  • 如下图，其实是对两条边进行坍缩了
    首先，三角形的任意一条边坍缩，则两个顶点合成了一个顶点
    然后，只剩2个顶点1条边了，再坍缩这条边则成了右图模样
    并且坍缩一条边，跟边的两个顶点相连的别的边也都会受到影响
    在这里插入图片描述
  • 新的点放哪？
    -直接取平均(原本所有相邻的几个点的平均)，毫无疑问误差特别大 原本是E，现在A了，不妥！
    在这里插入图片描述

2.2.2 二次误差网格简化

  • 二次误差度量
    二次误差：即新点跟原本几个相邻面的距离的平方。
    找到一个位置，使得这个点到原本相邻几个面的距离平方最小
    在这里插入图片描述

  • 根据二次误差选择坍塌目标——贪心算法
    (1)计算每条边的二次误差，从小到大存起来
    (2)每次取二次误差最小的边，由于会影响到其他边，因此须动态更新其他边的二次误差
    (3)存放每条边的二次误差的数据结构采用 小顶堆 (每次取最小，并且动态更新)

  • 因为每一次都坍塌局部误差最小的边，希望得到一个轮廓变化不大但是面数降低很多的模型
    这就是贪心算法——希望通过对局部做最优解试图得到全局最优解

  • 二次误差网格简化结果
    在这里插入图片描述

GAMES101图形学专栏



这篇关于计算机图形学【GAMES-101笔记】几何(距离函数、点云、贝塞尔曲线、曲面细分、二次误差网格体简化)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程