前言:
如今我们对“计算机图形学几何算法总结”大致比较看重,我们都想要学习一些“计算机图形学几何算法总结”的相关资讯。那么小编同时在网摘上收集了一些对于“计算机图形学几何算法总结””的相关资讯,希望兄弟们能喜欢,朋友们一起来学习一下吧!为什么“不是做‘元宇宙’的公司”?
最近经常遇到这样的情景:
“你们公司是做什么的?”
“我们是做线上虚拟空间,&%&¥#¥%R&$%#%...”
“哦,你们做的就是那个元宇宙啊。”
“我们做的事跟“真正的元宇宙”有一定的关系,但其实我们觉得关系并不大。”
作为从业者,我们相信元宇宙、web3.0确实是未来,但目前硬件、软件和应用场景都还不成熟,至于什么时候能成熟,在我们这一代能不能成熟,我们并不知道,现阶段的“元宇宙”,还只是一个初期概念。
当下热衷于“元宇宙”概念的个人或者企业,目的不外乎:绑定热点提高知名度,提升形象拉高产品或服务的售价,借势概念炒高估值或股价。
但对于我们这样一个年轻的团队,从创立之初我们就决定靠自身的核心竞争力去做有门槛的事,在市场上站着把钱挣到,并且在这个前提下做好了长期发展的规划和准备,概念的红利,我们确实不需要
不做元宇宙,那我们在做些什么?
灵境至维专注为品牌和艺术活动打造开放和连接的线上虚拟空间。每一个虚拟空间包含可漫游的3D虚拟空间、虚拟形象,多媒体内容、社交网络和多样化的互动内容,这些虚拟空间相互连通,形成完整的虚拟社区和世界。
OPPO MWC World项目(可长按扫码进入)
我们会用到的技术包括:虚拟空间、虚拟人、3D视觉、平面视觉、游戏引擎、云服务器、云渲染、各种名交互技术等,为我们服务的客户解决真实的痛点和问题,为品牌和用户创造价值。
去年底我们上线了国内首个具有虚拟世界体验的基于Web的线上虚拟科技大会,在未来我们将提供包括针对会议活动、音乐节、艺术展和线上社区等多种不同场景类型的虚拟空间服务。
相较于追逐热点,我们更热衷于追求知识,享受用知识去实现理想和梦想的过程,并坚信一定可以实现。当我们的才华撑不起我们野心的时候,静下心来学习是我们唯一的选择。
计算机图形学基础内部学习分享
计算机图形学跟当下的许多技术和热点息息相关,游戏、影视、设计建模、计算机图形界面、AR、虚拟人、动漫等等,我们用户做虚拟的空间的“实时渲染”这块要想做好,需要知其所以然,这个学科就是基础。
这是我们内部的一次学习分享,分享人是灵境至维团队的前端主程,学习内容是加州大学圣芭芭拉分校阎令琪教授在GAMES平台上开设的《GAMES101: 现代计算机图形学入门》课程,分为22讲,总时长约28小时,根据课程内容以及分享人的个人理解,将分为以下7个主要部分来进行分享。
这门课程是国内应该是首个讲底层原理的课程(之前只有国外),非常感谢阎令琪教授为这个领域在中国的发展做出的贡献。
粉丝福利:关注灵境至维公众号,发送“计算机图形学”可获得本次分享的内容大纲。
以下就是这次课程分享的内容实录:
一、图形学概述
这部分主要介绍计算机图形学的一些基础概念。
1. 什么是计算机图形学(CG)?和计算机视觉(CV)、数字图像处理(DIP)有什么区别?
事实上,图形学发展到现在,内容已经变得十分丰富,与很多学科都有交叉,目前并没有一个很好的定义能够准确解答这个问题。
因此这里从数据处理的角度出发,说一下图形学与几种相似学科的区别,便于大家理解。
首先,图形学是一种将二维或三维的图形数据,经过一系列数学算法,转化为显示设备上栅格图像的科学,核心概念是由数据到图像,其主要应用领域有电子游戏、影视、设计建模、计算机图形界面等。
计算机视觉则与之正好相反,是通过给定的图像,提取其中的信息,转化为计算机可分析的数据,核心概念是由图像到数据,主要应用领域有人脸识别、无人驾驶等。
数字图像处理则是一门将图像转成数字信号,由计算机处理的科学,核心概念可以大致理解为由图像到图像,主要应用领域有图片美化、航天航空、显微图像分析等。
2. 图形学有哪些子领域?
这里根据中科大教授刘利刚老师2013年发表的一篇文章为参考,将图形学的主要研究领域分为建模、渲染、动画、人机交互,这门课主要涉及到前三种领域,重点介绍了图形学渲染基础。其中渲染根据渲染速度可分为实时渲染和离线渲染;根据风格可分为真实感渲染(也叫基于物理的渲染)和非真实感渲染(NPR)。
3. 为什么要学计算机图形学?
这个问题的答案就因人而异了,但归根结底都是为了让显示的视觉效果达到赏心悦目的地步。
二、线性代数基础
这部分主要介绍了学习图形学所需的一些线性代数基础,其中主要是利用向量和矩阵,对数据进行变换操作。
1. 向量
一个同时具有大小和方向,且满足平行四边形法则的几何对象。
1.1 单位向量
指长度为1的向量
1.2 向量加法
1.3 向量点乘
性质:满足结合律和分配律和交换律笛卡尔公式:
几何意义:
1.4 向量叉乘
性质:满足结合律和分配律,但不满足交换律笛卡尔公式几何意义:求法线的内外方向
2. 矩阵
Wiki:将一些元素排列成若干行,每行放上相同数量的元素,就是一个矩阵
2.1 矩阵乘法
性质:满足结合律和分配律,但不满足交换律矩阵与矩阵相乘(A的列数必须等于B的行数)矩阵与向量相乘
2.2 转置矩阵
2.3 逆矩阵
2.4 正交矩阵(wiki)
性质:矩阵转置等于矩阵的逆几何意义:行(列)之间两两正交,因此各个行(列)可表示为坐标系的坐标轴,通常用于表示线性变换。
三、图形渲染管线
图形渲染管线是实时渲染的底层工具。其最主要的功能就是根据一个虚拟的相机、3D的物件、光照等信息,渲染生成一个2D的图片。
管线根据概念大致可分为四个阶段(非标准,以RRT书中为参考):
应用阶段(课程中没有提及);几何处理阶段;光栅化阶段;像素处理阶段。
需要注意的是,其中每个阶段本身通常又可分为几个小的阶段。以下分别对这四个阶段进行梳理。
1.应用阶段
跟之后的几个阶段需要硬件参与的情况不同的是,应用阶段是全部通过软件实现的,软件开发者对这一阶段有完全的控制。这一阶段执行的功能通常有:碰撞检测、输入检测、动画等。
在应用阶段的结尾,CPU会将模型数据传递给GPU,这一过程被成为Drawcall。
2.几何处理阶段
几何处理阶段的主要目的是将3D空间的数据转化到屏幕空间上,其中最主要的步骤就是MVP变换
2.1模型变换(Modeling Transformation)
模型变换的目的是将需要处理的几何体顶点/法线数据统一到世界坐标系下,这个过程主要会应用到上一章节提到的线形代数的知识。
齐次坐标
引入齐次坐标的目的是为了将仿射变换统一到一个矩阵中
缩放矩阵平移矩阵旋转
- 绕坐标轴旋转
- 绕任意轴旋转(罗德里格旋转公式)
2.2视图变换(View/Camera Transformation)
视图变换的目的是规范化相机在世界空间下的位置和朝向。当然,如果只移动相机而不移动物体,则会导致相机与物体的相对位置发生变化,因此在变换相机的同时,也要改变物体。
规范相机矩阵
以右手坐标系为例,需要将相机位置e移到原点,相机朝向g正对z轴负方向,相机顶部t正对y轴正方向,g与t的叉乘方向为x轴正方向。然而按照这个思路很难做变换矩阵,因此需要巧妙借用正交矩阵的特性:转置矩阵=逆矩阵,进行逆变换:
经过视图变换的相机与物体如图
2.3 投影变换(Projection Transformation)
投影变换的目的就是将三维坐标投影成二维,其中涉及两种类型:正交投影和透视投影。
正交投影的视图体通常为一个矩形框,正交投影将其转成一个单元立方体。其主要特点就是变换后平行线要依然保持平行。这种变换是平移和缩放的组合。透视投影比较复杂,它的视图体是一个截锥。应用透视投影会让物体有现实世界中“近大远小”的现象。求透视矩阵的思路是先将其转化为正交投影,再进行求解。那么目的就是找出透视转化正交的矩阵,这里直接贴结论
求出转化矩阵后,还有个问题,转化后的正交矩阵的top、bottom、left、right怎么求呢?
3.光栅化阶段
经过几何变换步骤,顶点已经能够投影到屏幕上了。而光栅化的目的则是将空间中连续的坐标离散化为屏幕上一个个的像素点。其主要步骤可以分为:
1)使用包围盒等算法求出图像区间;
2)使用叉乘或渐进增量等方法对像素进行遍历,求几何内部的点。
这个步骤也会产生一些问题,例如图像的“锯齿”问题,其生成原因是由于信号的采样频率跟不上图像变化,业界目前也有一些相对可行的优化算法,例如:MSAA(模糊边界超采样)、FXAA(基于数字图像处理优化)、TAA(基于上一帧对比数据优化)。
4.像素处理阶段
像素处理阶段分为着色阶段和合并阶段,课程中主要对着色进行了讲解,而着色的目的就是计算出每个采样像素点的颜色是多少并将结果储存起来,要考虑的因素通常有:光照、着色频率、纹理。
4.1光照模型
当光照射到物体表面时,物体对光会发生反射、透射、吸收、衍射、折射、和干涉,其中被物体吸收的部分转化为热,反射、透射的光进入人的视觉系统,使我们能看见物体。为模拟这一现象,我们建立一些数学模型来替代复杂的物理模型,这些模型就称为光照模型。
光栅化技术的特点是只能考虑单个像素的颜色值,而不能考虑这个像素受其它像素影响的光照部分。基于此的光照模型被成为局部光照模型,课程中介绍了现阶段比较常用的一种局部光照模型——BlinnPhong光照模型。
BlinnPhong光照模型主要由三部分组成:Diffuse(漫反射)、Specular(高光)、Ambient(环境光)。
DiffuseSpecularAmbient
4.2着色频率
知道光照模型等式后,还需要了解模型上每个着色点的分布,这里就需要引入着色频率的概念,常见的着色频率有三种:Flat Shading、Gouraud Shading、Phong Shading。分别对应以下三种样子:
从左到右的算法消耗依次增加,需要注意的是,Phong Shading虽然可以让模型表面看上去更为光滑,但是却解决不了地面模型边界棱角的问题。
4.3纹理(Texture)
解决了光照模型和着色频率的问题后,我们已经能够模拟光线照到物体上的现象了,那么接下来如何描述物体本身的复杂材质呢?这里就要引入纹理的概念了,纹理就是使用预处理的数据(大多数是图片)丰富3D表面的表现。
如何将2D纹理对应到3D模型的表面上?
通过UV(纹理坐标)来实现,实现上UV通常都是通过3D设计工具(如c4d、blender)实现的。
非顶点位置的属性值如何计算?
插值,插值的实现主要用到重心坐标。
屏幕分辨率和纹理分辨率不一致怎么处理?
- 当1屏幕像素 < 1纹素(texel),也就是纹理图片不够清晰,会产生锯齿现象,此时通常使用线形插值的做法进行优化。通常的算法有Nearest、Bilinear、Bicubic。
- 当1屏幕像素 >1纹素(texel),也就是纹理图片过于清晰(通常出现在场景远处),会产生摩尔纹现象。常用的解决方案有Mipmap、Anisotropic Filtering、EWA(椭圆加权平均)过滤。
部分纹理类型。
- 漫反射纹理
- 环境纹理
- 凹凸/法线纹理
- AO(环境遮挡)纹理
5. 图形渲染管线作业
四、几何图形
正如渲染的目的是要将一个三维物体渲染成2D的画面,几何图形部分的研究目的就是如何通过数学工具表示各种三维物体。
1. 表示形式
几何的数学表示形式可分为隐式表示和显示表示两种:
1.1 隐式表示
隐式表示则是不通过笛卡尔坐标来表示几何图形,例如:
Algebraic surface(代数曲面)Constructive solid geometry (构造实体几何)SDF(有距离函数)Level Set(水平集)Fractals(分形)
隐式表示优点在于根据给定点与隐式公式间的大小关系,可以很方便知道点是否在几何体的内部。缺点则是不方便进行采样。而显示表示的优缺点则与之相反。
1.2 显示表示
显示表示则通常有以下类型
Point Cloud(点云)Polygon Mesh(多边形网格)The Wavefront Object File (.obj) Format
2. 曲线和曲面
构造复杂几何体最核心的问题是表示复杂的曲线和曲面。其中常见的算法有Bézier、B-splines、NURBS。课程中着重介绍来Bézier曲线与Bézier曲面。
2.1 Bézier曲线
属性几何表示(de Casteljau Algorithm(德卡斯特里奥算法))代数表示(伯恩斯坦多项式)多段贝塞尔曲线如何保持平滑?
1)三点一线
2)两边长度相等
2.2 Bézier曲面
曲面无非就是将曲线进行升维,在做插值的时候多考虑一维的信息。
3. 网格处理
网格指的是三维多边形网格模型,以下简称为“网格”。简单来说,可以给网格下一个简单定义:由多边形集合定义的,用以表示三维模型表面轮廓的拓扑和空间结构称为“网格”,英文称作“polygon mesh”或“mesh”。
而我们在项目中使用网格模型时,经常会存在面过多或者过少的情况,这时就需要对网格进行处理,常见的网格处理形式分为三种:Mesh subdivision(网格细分)、Mesh simplification(网格简化)、Mesh regularization(网格规范化)。
3.1 网格细分
网格细分则是将相对低面的模型转化为多面。
目前常见有两种实现算法:1. Loop细分:针对三角面的细分方式,将一个三角面转化为四个三角面。2.Catmull-Clark细分:针对任意形状的细分,经过一次细分可将原本不是四边的面转化为四边面。
3.2 网格简化
网格简化则是将相对高面的模型转化为低面。
目前比较常见的算法是基于二次度量误差
二次度量误差(QEM,quadric error metric)指的是当前顶点到其邻域所有三角面(也称关联平面)的距离平方和。过程:
1)统计所有参与边折叠的边
2)计算所有顶点的QEM(v),计算所有边的QEM(e)=QEM(v1)+QEM(v2)
3)根据QEM(e)的排序找到最小的QEM(e)的边
4)折叠该边并找到最优的QEM的新顶点v’,删除v1,v2,和相关face,更新v’的QEM为QEM(v1)+QEM(v2),更新相关联的QEM(e)
5)重复3)、4)直到要求达到要求。
3.3 网格规范化
这块课程中只是简单提及,通过查资料了解到是与3D重建等技术相关,游戏这块用的并不多。
五、光线追踪
之前在图形渲染管线板块有介绍BlinnPhong光照模型,其中有提到这种局部光照模型没办法处理全局光线传播的效果,而现实世界中的场景是经过无数次光线传播再传入人眼的。因此,要想渲染出更加逼真的效果,就需要引入光线追踪的算法。
顾名思义,光线追踪算法中对于光线的定义是非常重要的,这里图形学中采用的是几何光学的定义,主要把光线做了以下定义:
1)光线是沿直线传播的;
2)光线间不发生碰撞;
3)光线到观察点的路径是可逆的。
根据第三点光路可逆的法则,我们就可以把光线的起点定在人眼(摄像机),以此来描述光线追踪的步骤。
1. Ray Casting
从摄像机想投影平面的每一个像素点发出一条射线,通过射线寻找与物体的交点,再将交点与光源进行连线判断交点是否在阴影中。
2. Recursive (Whitted-Style) Ray Tracing
Ray casting的过程仍然是局部的,那么如何引入全局概念呢?这里就用到了经典的Whitted-Style路径追踪算法。算法中定义每一个交点的颜色贡献是由直接光照、间接反射光照和间接折射光照(可能)组成的,将这些部分进行权重累加,再使用BlinnPhong模型进行着色,则得到投影平面上最终点的颜色。
3. 光线表示方程
将每条光线想象成一条射线,则这条射线由三部分组成:
起点 - o方向 - d发射出去的时间(长度)- t
4. 光线求交
4.1 与隐式表面求交
4.2 与显示表面求交
更快的求交方法(Möller Trumbore Algorithm)
补充信息
光线追踪这块这篇文章写的非常详细:
4.3 加速结构
遍历每一个面求交点的性能消耗是非常恐怖的,加速的大体思路就是不直接遍历面数,而是使用包围盒等算法进行加速。
轴对齐包围盒有了包围盒还不够,我们还可以对场景进行分区,常见的分区算法有以下几种
Oct-Tree(八叉树):每次都切割八份
KD-Tree:每次都沿轴线切割一次
BSP-Tree:按一定算法沿任意轴切一刀
BVH(推荐):在KD-Tree的基础上以包围盒为单位进行分割
BVH的一些优化:每次都分割最长的边、分割点以中心物体为参照、当节点中包含很少的物体时则停止。
5. 现代光线追踪算法
上面描述的whited-style光线追踪模型虽然将全局光线传播的算法引入到光照模型中,但仍然不够准确,原因有二:
1)光线传播中只考虑当前交点反射和折射出去的光线,而没有追踪漫反射的光线;
2)着色采用的还是BlinnPhong这个经验模型,无法精确的模拟真实物理的现象。
针对以上的问题,我们就要引入真实的物理概念来定义光线追踪的现象,因此就有了基于物理的渲染(PBR),而辐射度量学就是这样一套测量光线能量的学科。
5.1 辐射度量学
一些比较重要的物理概念:
Radiant Energy(辐射能):表示能量,单位:J(焦耳)。Radiant flux(辐射通量/功率):单位时间的辐射能量,单位:W(瓦特)/ lm(流明)。Radiant intensity(辐射强度):每单位立体角的辐射通量,单位:W·sr−1。Irradiance(辐照度)*:入射表面的辐射通量(不带方向)(从所有方向到达某一点的能量之和),单位:W·m−2。Radiance(辐射率)*:每单位立体角每单位投射表面的辐射通量(带方向),单位:W·sr−1·m−2。
5.2 双向反射分布函数(BRDF)
直观的理解,不同物体表面材质自然会把一定方向上的入射亮度反射到不同的方向的光线上,如理想光滑表面会把入射光线完全反射到镜面反射方向,其它方向则完全没有。如理想粗糙表面会把入射光线均匀的反射到所有方向。因此所谓BRDF就是描述这样一个从不同方向入射之后,反射光线分布情况的函数,定义如下:
5.3 反射方程
5.4 渲染方程
5.5 如何解出渲染方程(蒙特卡洛积分)
当一个积分很难通过解析的方式得到答案的时候可以通过蒙特卡洛的方式近似得到积分结果。
5.6 真实照片(左)与基于物理渲染的效果(右)的对比
六、材质与外观
这一章主要介绍以下一些基于物理的常见材质:
Diffuse/Lambertian Material
Glossy Material
Ideal reflective/refractive Material
Microfacet Material
Anisotropic Material(各向异性材质)
七、动画与模拟
1. 图形学中的动画分类
1.1 Keyframe animation(关键帧动画)
1.2 Physical simulation(基于物理的模拟)
Mass Spring System(弹簧质点系统)
1.3 运动学(Kinematics)
Forward KinematicsInverse Kinematics
1.4 Rigging
1.5 Motion Capture
2. 动画相关的算法
2.1 单粒子模拟
常微分方程(ODE)欧拉方法刚体模拟流体模拟
3. 动画制作流程
《我们不是做“元宇宙”的公司》今后将成为一个围绕“虚拟空间”主题进行专业知识分享的系列内容,不定期在灵境至维公众号推出,欢迎大家持续关注,希望你能在这里看到想要的内容!
标签: #计算机图形学几何算法总结 #brdf定义 #mip算法 #a算法计算h估值用什么算法 #计算机图形学经典算法