游戏开发面试题 -- 图形学篇

以下文章来源于游戏君五尘，作者五尘君。

图形学和3D数学篇，收录了几十道面试真题，也欢迎小伙伴后续提供以便继续更新。

因第二篇内容主要来源于网上，未原创发表在公众号，文章链接如下。

游戏开发面试答案篇（二）– Unity篇 https://zhuanlan.zhihu.com/p/554529423

渲染管线
(1). 渲染管线就是一堆原始图形数据经过各种变化处理最终出现在屏幕的过程。
渲染管线可分为三个阶段，应用程序阶段，几何阶段，和光栅化阶段
(2). 应用程序阶段由CPU主要负责。CPU将GPU渲染需要的灯光、模型准备好，并设置好渲染状态，为GPU渲染做好准备。
(3). 几何阶段把输入的3D数据转换成2D数据。包括顶点着色器、图元装置、裁剪和屏幕映射几个过程。
顶点着色器主要进行顶点坐标变换。将输入的模型空间顶点坐标变换到裁剪空间顶点坐标。
图元装配将顶点装配成指定图元的形状。
几何着色器改变图元。通过产生新顶点构造出新的图元来生成其他形状。
(4). 光栅化阶段把图元映射为最终屏幕上显示的颜色。包括光栅化，片段着色，深度测试和混合。
光栅化将顶点转为屏幕上的像素。
片段着色器计算每个像素的最终颜色。
深度测试通过深度信息判断像素的遮挡关系。
混合阶段通过透明度将像素进行混合。
(5). 最终渲染好的颜色先被送入后置缓冲，随后再替换前置缓冲，显示在屏幕上
什么是depth buffer
深度缓冲也称z-buffer，用来存储深度值以及在深度测试时确定一个片段是否被其他片段遮挡。
深度缓冲由窗口系统自动创建并将其深度值存储为 16、 24 或 32 位浮点数。在大多数系统中深度缓冲区为24位。
当深度测试启用的时候，如果此测试通过，深度缓冲内的值将被设为新的深度值。如果深度测试失败，则丢弃该片段。
提前深度测试
提前深度测试(Early depth testing)是一个由图形硬件支持的功能。
提前深度测试允许深度测试在片段着色器之前运行。可以更早地踢掉一些片段永远可见的片元，节省GPU资源。
phong和billin-phong
Phong光照模型将光照分为三部分：环境光(Ambient)、漫反射光(Diffuse)和镜面(Specular)光照。
环境光即来自其它物体，而非直接光源的光照。在Phong模型中是一个常数。
漫反射即粗糙物体表面均匀的反射光线到各个方向所产生的光照效果。
镜面光照也称高光反射，由光滑物体表面平行地向一个方向反射出来的光照效果。
Phong光照模型中，视线向量和反射向量的角度不允许大于90度。如果大于90度的话，点乘的结果就会是负数，镜面的贡献成分就会变成0。
Blinn-Phong镜面反射的计算引入了半程向量（halfway vector）向量，半程向量是视线方向和反射向量之间的夹角。通过测量法线和半程向量之间的角度计算镜面反射。
前向渲染和延迟渲染的区别
前向渲染对于每一个需要渲染的物体，都要逐光源渲染，每个光源都会带来一定的渲染成本。
延迟渲染将计算量非常大的渲染(如光照)延时到后期进行处理。包含两个处理阶段(Pass)：在几何处理阶段中，先渲染场景一次，之后获取对象的各种几何信息，并储存在G缓冲(G-buffer)的纹理中。随后在光照处理阶段中使用G缓冲内的纹理数据对每一个片段计算场景的光照。
延迟渲染只需要对每一个像素执行一次光照运算，能够渲染大量的光源而不消耗大量的性能。
延迟渲染不能进行混合(Blending)，因为G缓冲中所有的数据都是从一个单独的片段中来的，而混合需要对多个片段的组合进行操作。
延迟渲染需要大内存开销，没有MSAA。
延迟渲染对小且没有很多的光源的场景，并不一定会更快。
延迟渲染不支持半透明物体渲染。
透明物体和不透明物体渲染顺序
先渲染所有的不透明物体，开启深度写入和深度测试
再渲染半透明物体，按由远到近排序，先渲染远处的物体，再渲染近处的。开启深度测试，开启混合，关闭深度写入。
如何优化shader
计算量优化
将计算从像素着色器移动到顶点着色器
在脚本中计算并传递给着色器，使用纹理读取的方式减轻运算量
代码优化
尽量使用系统自带的内建函数，因为很多是硬件支持的
简单的重复不多的计算，不应该将这种计算封装成函数，直接用代码计算即可
选择合适的数据精度，尽量使用低精度
尽量不要使用if分支语句，可以使用step函数替代
shader中的if会造成性能影响以及如何优化
if的效率问题是会导致多个分支重复执行。
在大多数没有标明关键字的情况下，编译器默认生成的是 flatten 形式的指令，flatten 把分支所有侧的逻辑都执行一遍，根据判断条件舍弃掉错误结果，选择其中一个结果。
优化：
从关系运算符和逻辑运算符两个角度，进行分支合并，转换为非分支形式。或者使用内置指令代替内置指令替代。如等于不等于可转换如下
图片
线性空间和srgb空间是怎么反映的
在线性空间物理世界中的颜色和光照规律是光强度增加了一倍，亮度也增加一倍
显示器显示图像的时候，电压增加一倍，亮度增加2.2次幂的非线性关系，线性的颜色显示在监视器上相当于降低了2.2次幂的亮度
图片
使颜色整体会偏暗，即显示器的输出在伽马Gamma2.2空间
sRGB格式相当于对物理空间的颜色做了一次伽马（gamma）校正
gamma校正将把线性颜色空间转变为srgb空间（Gamma0.45空间），即
图片
伽马校正和显示器输出平衡之后，结果就是Gamma1.0的线性空间。
gamma correction是怎么实现的
gamma 校正将线性空间变换到Gamma0.45空间，在数学上是一个约为0.45的幂运算
图片
顶点着色器实现光照会怎么样
逐顶点光照，也称为高洛德着色，在顶点着色器中对每一个顶点进行光照计算，然后会在渲染图元内部进行线性插值，最后输出成像素着色。
逐顶点光照的性能开销远远小于逐像素，因为顶点数远远要小于像素数。但是由于逐顶点的像素依赖于顶点的线性插值来取得效果，因此只要是非线性的光照计算使用逐像素光照都会或多或少的产生有问题的效果。（效果不一定正确）
顶点着色器作用，包括什么工作
顶点着色器，是对顶点进行一系列操作的着色器，对物体顶点进行控制，如位置改变。能实现各类效果如布类仿真，高级别动画，实时修改透视效果
顶点着色器到片元着色器中间流程
顶点着色器到偏远着色器需要经过：图元装配、几何着色器、光栅化
图元装配：将顶点装配成指定图元的形状（如三角形）。
几何着色器：改变图元。通过产生新顶点构造出新的图元来生成其他形状。外壳着色器和域着色器可编程，镶嵌器是由硬件管理。
光栅化：把图元映射为最终屏幕上相应的像素（把三角型切分成一个个像素）。
几何着色器的作用，顶点着色器传输给几何着色器什么数据
几何着色器在顶点和片段着色器之间，是一个可选的可编程的着色器。它能够将顶点变换为完全不同的图元，并且还能生成比原来更多的顶点。
以一个或多个表示为一个单独基本图形的顶点作为输入，如一个点、线、或三角形
EBO存储的数据是什么，有什么好处
索引缓冲对象(Element Buffer Object，EBO，也叫Index Buffer Object，IBO），专门存储顶点的索引。
EBO节省了顶点数组的size，减少了重复保存顶点数据
G-Buffer的底层结构
G缓冲(G-buffer)是对所有用来储存光照相关的数据，并在最后的光照处理阶段中使用的所有纹理的总称。本质就算一个帧缓冲对象。
Drawcall 原理以及如何减少DrawCall
DrawCall是对底层图形绘制接口的调用命令，调用GPU进行渲染。CPU往GPU发送渲染命令，GPU接受并执行相对应的渲染命令。
优化：
UI方面：使用图集，批渲染
将一些渲染状态一致的物体合成一个大物体，把图集转移到一张大图片，一次提交给gpu进行绘制。
模型方面：
每一帧把可以进行批处理的模型网格进行合并，再把合并后模型数据传递给GPU，然后使用同一个材质对其渲染。

18.光栅化的作用？
光栅化是把顶点数据转换成片元的过程，即将几何图元变成二维图像的过程，将三维场景投影到二维平面。

实时阴影如何实现、生成
阴影有硬阴影和软阴影。实时硬阴算法为shadowmap及其变种CSM、SSSM。
实时软阴影算法包括PCF、PCSS、VSSM、SDF阴影。
(1). shadow map将深度信息渲染到深度图上，并在运行时通过深度对比检测物体是否在阴影中的算法。
shadow map是一个2-pass的算法
pass1：从Light视角看向场景，记录每个像素的最浅深度，输出一个深度纹理图。
pass2：从camera视角出发，检测当前物体深度是否大于深度纹理中深度值，判断是否在阴影里
shadow map会产生自遮挡和走样现象。
(2). PCF(percentage Closer Filtering)
PCF能解决shadow map的锯齿块和硬边问题，产生柔和软阴影。
核心思想是从深度贴图中多次采样，每一次采样的纹理坐标都稍有不同（比如采样像素周围一圈范围）。每个独立的样本可能在也可能不在阴影中。所有的次生结果接着结合在一起，最终通过样本的总数目将深度结果平均化。
(3). PCSS
PCSS为了实现更真实的软阴影，达到离遮挡物距离近的时候硬，远的时候软的效果。
算每个区块深度（shadow map上，只算被遮挡点的平均深度）
通过深度估算需要采样范围多大（curDepth – AvgDepth） / AvgDepth
PCF在shadow map上采样，范围由第二步确定
(4). VSSM (Variance Soft Shadow Mapping)
解决PCSS（第一步和）第三步慢的问题，优化了第三步范围查询shadow map得到平均深度值，直接使用切比雪夫进行猜测。
第一步：对shadow map进行区域平均深度计算平均深度的平方，并使用记录
第三步：根据记录查询的方差值，根据当前点深度，用切比雪夫得到平均深度
(5). SDF(Disatance field soft shadows)
有向距离场SDF记录了空间中任何一点到定义该场的物体之间的最小距离。将SDF距离作为安全距离，判断光线是否与物体相交，可以加速光线步进。
SDF阴影原理：以采样点为起点，沿着光线来的方向，发射另一根射向光源的射线，并通过SDF加速光线步进。如果这根射线也击中了某个物体的表面，则证明该采样点处于阴影之中，并使用当前步进的长度和上一步步进的长度计算软阴影。
原理细节参考games202视频https://www.bilibili.com/video/BV1YK4y1T7yY?p=3&vd_source=247e85b9b80345fa83fa152be97c604e
shadowmap实现原理
shadow map将深度信息渲染到深度图上，并在运行时通过深度对比检测物体是否在阴影中的算法。
shadow map是一个2-pass的算法
pass1：从Light视角看向场景，记录每个像素的最浅深度，输出一个深度纹理图
pass2：从camera视角出发，检测当前物体深度是否大于深度纹理中深度值，判断是否在阴影里
屏幕空间的阴影算法原理
渲染shadow map

渲染得到屏幕视角的场景深度纹理。

绘制场景物体，对片元采样屏幕空间的阴影图

PBR的理解
基于物理的渲染(Physically Based Rendering)，指的是一些在不同程度上都基于与现实世界的物理原理更相符的基本理论所构成的渲染技术的集合。
判断一种PBR光照模型是否是基于物理的，必须满足以下三个条件
基于微平面(Microfacet)的表面模型。

能量守恒。

应用基于物理的BRDF。

参考https://learnopengl-cn.github.io/07%20PBR/01%20Theory/

哪些描边的技术以及有啥优缺点
法线外扩法：Vertex Shader阶段将顶点向顶点法线方向移动一定距离
问题：描边出现断裂、无粗细变化、额外的空间存储模型、额外一个Pass
菲涅尔方程描边：描边就发生在物体的边缘上，而越靠近边缘时顶点法线与摄像机向量间的点乘越靠近0，判断这个点乘结果来判断是否为描边
问题：效果太不稳定了，尤其是平面会出现大片的描边，适用于球型物体
基于贴图的描边：描边直接画在贴图上
问题：对贴图分辨率有着更高的要求，容易产生锯齿
基于SDF描边：到处描边贴图，将贴图制作成SDF图，渲染时将SDF图还原成原贴图
问题：需要多采样一张SDF图
色调映射，HDR与LDR的区别
HDR(High Dynamic Range, 高动态范围)：显示器被限制为只能显示值为0.0到1.0间的颜色，但是在光照方程中却没有这个限制。HDR使片段的颜色超过1.0，得到一个更大的颜色范围。HDR渲染可以保证在明亮和黑暗区域无细节损失。
LDR(Low Dynamic Range,低动态范围)：将所有HDR值转换成在[0.0, 1.0]范围。
色调映射(Tone Mapping)：转换HDR值到LDR值的过程。
为什么延迟渲染对MSAA支持不好
因为延时渲染丢失了几何信息。
1、MSAA本质上是一种发生在光栅化阶段的技术，也就是几何阶段后，着色阶段前，用这个技术需要用到场景中的几何信息
2、延迟渲染因为需要节省光照计算的原因，事先把所有信息都放在了GBuffer上，着色计算的时候已经丢失了几何信息
3、正常的延迟渲染兼容不了MSAA，因为GBuffer丢了几何信息，如果一定要兼容那么就想办法在GBuffer那一层把几何信息也记录下来
https://zhuanlan.zhihu.com/p/135444145
BRDF与兰伯特模型的联系是什么
兰伯特光照模型是经验模型，主要用来模拟粗糙物体表面的光照现象，被用作漫反射的模型
兰伯特光照模型的BRDF函数是一个常量，它表示入射到物体表面之后反射的光在任意的反射方向上都具有同样的能量
球谐光照的理解
球谐光照实际上是一种对光照的简化，通过球谐函数，将复杂的光照信号投影到基函数上存储，然后在使用的时候再将基函数上的数据加起来重建光照信号。达到用的简单的系数表示复杂的光照，节省时间空间。
对伽马校正的理解
RGB值与功率并非简单的线性关系，而是幂函数关系，这个函数的指数称为Gamma值，一般为2.2，而这个换算过程，称为Gamma校正。
屏幕空间阴影映射技术的优点
优化对阴影的overdraw。
卡通渲染思路
卡通渲染（Cel-shading）是一种非真实感的渲染技术（NPR），卡通渲染的目的是使图像呈现出手绘效果。
卡通渲染可以分为了三个部分，描边、着色、卡通渲染风格。其中最核心的两个部分是描边和着色。描边包括外轮廓和内轮廓。着色包括多色阶降为低色阶、冷色调和暖色调处理。
如何渲染半透明物体
先在CPU中对需要渲染的半透明物体进行距离排序，然后与相机距离由远及近逐个物体渲染、像素混合
为什么要用FrameBuffer
帧缓冲能够实现很多后期处理效果
纹理坐标？双线性插值怎么做的
纹理坐标(Texture Coordinate)，用来标明该从纹理图像的哪个部分采样，纹理坐标在x和y轴上，范围为0到1之间。
双线性插值基于纹理坐标附近的纹理像素，计算出一个插值，近似出这些纹理像素之间的颜色。一个纹理像素的中心距离纹理坐标越近，那么这个纹理像素的颜色对最终的样本颜色的贡献越大。
mipmap有什么缺点
占用显存
LOD怎么做的
静态Lod：在预处理过程中产生一个物体的几个离散的不同Lod模型。实时绘制时根据特定的标准选择合适的Lod模型来表示物体。
动态Lod：在动态Lod算法中生成一个数据结构，在实时绘制时可以从这个数据结构中抽取出所需的Lod模型。从这个数据结构中可以得到大量不同分辨率的Lod模型。
Bloom怎么做的
Bloom和HDR结合使用。
先渲染一个有光场景，提取出场景的HDR颜色缓冲以及只有这个场景明亮区域可见的图片。
再将提取的带有亮度的图片模糊处理。
最后将结果添加到HDR场景上面。
动态模糊怎么做的
先将图片进行最大程度的模糊处理，再将原图放置在模糊后的图片上面，通过不断改变原图的透明度(Alpha值）来实现动态模糊效果。
opengl与openglES
OpenGL ES是OpenGL的嵌入式设备版本，OpenGL ES相对OpenGL删减了一切低效能的操作方式
没有double型数据类型，但加入了高性能的定点小数数据类型。
没有glBegin/glEnd/glVertex。
没有实时将非压缩图片数据转成压缩贴图的功能。
后处理了解吗
后期处理是在3D渲染完成后，在输出最终效果之前，对渲染完成的图像再进行一定的处理。
抗锯齿方法的种类，各自优缺点
抗锯齿方案可分为三类，时间抗锯齿、空间抗锯齿、图像抗锯齿。
时间抗锯齿使用TAA（Temporal Anti-Aliasing），将过去帧中采样的像素与在当前帧中采样的像素混合以产生抗锯齿图像。在快速移动的镜头中容易出现鬼影问题。
空间抗锯齿以较低分辨率表示高分辨率图像。主要使用MSAA（多重采样抗锯齿）。使用多倍的屏幕分辨率大小的后台缓冲区和深度缓冲区，如4xMSAA使用4倍屏幕分辨率。需要多倍缓冲区，在延时渲染管线中难以支持。
图像抗锯齿也称后处理抗锯齿。主要使用FXAA（快速近似抗锯齿），通过将图像一定程度的模糊处理。是一种低消耗的抗锯齿技术，但效果一般。

41、遮挡剔除算法种类
遮挡剔除是剔除被其他物体遮挡住而不在摄像机的可视范围内物体，不对其进行渲染的技术。
包括离线和实时方案。离线方案常用PVS，通过预计算场景中哪些物体时可见的，并记录下来，运行时通过查询该位置可见物体进行渲染。但是无法处理动态物体。
实时方案包括SoftWare Occlsion（SOC）、Hierarchical Z-Buffering、GPU-Driven、硬件遮挡剔除。

42、光线追踪的原理及大致流程
原理：光线追踪是通过跟踪与光学表面发生交互作用的光线从而得到光线经过路径的模型。
过程：光线跟踪沿着到达视点的光线的反方向跟踪，从屏幕上每一个相素出发，找出与视线相交的物体表面点P0，并继续跟踪，找出影响P0点光强的所有光源，从而算出P0点上精确的光线强度。

数学相关

MVP矩阵空间变换过程
模型变换M、视图变换V、投影变换P，统称MVP
MVP 变换将3维模型映射到屏幕2维坐标中，参与 MVP 变换的信息包括点、矢量、法线、切线等
模型变换（Model）：物体本身的平移、旋转、缩放，将模型空间转换到世界空间
观察变换（View）：将世界空间转换到观察空间
投影变换（Projection）：将观察空间转换到裁剪空间
最后要获取屏幕坐标还需要一步：屏幕映射，获取对应屏幕的 2D 坐标，又叫视口变换
M矩阵中旋转、平移、缩放顺序，分别在M矩阵的哪个部分
模型变换不同顺序有不同的结果，一般地，先进行线性变换，再进行非线性变换，即缩放-> 平移-> 旋转
平移对应第四列，缩放对应主对角线，旋转对应前三行三列
四元数的理解，如何从两个向量判断四元数（四个参数的代表内容）
四元数是四维空间中一个超球上面的点，满足w²+x²+y²+z²=1，将三维空间无法解决的问题就映射到四维空间。
常用于解决3D旋转问题，如欧拉角产生的万向节死锁
变换矩阵里每一列代表什么
前三列代表缩放和旋转，最后一列代表平移
为什么MVP矩阵是 4*4
多一个w分量，可以很方便的在3D向量上进行位移
点乘叉乘几何意义，用处
点乘是向量的内积，结果是一个实数，表示两个向量的长度与它们夹角余弦的积。即一个向量在另一个向量方向上的投影，也用于判断两个向量是否同向。
叉乘是向量的外积，结果是一个向量，用于生成第三个垂直于a，b的法向量，或者构建坐标系。也等于向量a和向量b构成的平行四边形的面积
点到平面的距离如何计算
需要给定平面上一点P，过P做平面的发向量，该点与P的连线向法向量投影，距离即为投影长度
几何阶段的矩阵变换都有哪些
MVP
如何判断一个点是否在一个凸多边形内
方法很多：
（1）面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。
（2）夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。
（3）引射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。
旋转有哪几种方式？欧拉角会有什么问题？讲一下四元数
欧拉旋转、矩阵旋转、四元数旋转
欧拉旋转
优点：很容易理解，形象直观；表示更方便，只需要3个值（分别对应x、y、z轴的旋转角度）；但按我的理解，它还是转换到了3个3*3的矩阵做变换，效率不如四元数；
缺点：之前提到过这种方法是要按照一个固定的坐标轴的顺序旋转的，因此不同的顺序会造成不同的结果；会造成万向节锁（GimbalLock）的现象。这种现象的发生就是由于上述固定坐标轴旋转顺序造成的。理论上，欧拉旋转可以靠这种顺序让一个物体指到任何一个想要的方向，但如果在旋转中不幸让某些坐标轴重合了就会发生万向节锁，这时就会丢失一个方向上的旋转能力，也就是说在这种状态下我们无论怎么旋转（当然还是要原先的顺序）都不可能得到某些想要的旋转效果，除非我们打破原先的旋转顺序或者同时旋转3个坐标轴。
四元数旋转
优点：可以避免万向节锁现象；只需要一个4维的四元数就可以执行绕任意过原点的向量的旋转，方便快捷，在某些实现下比旋转矩阵效率更高；可以提供平滑插值；
缺点：比欧拉旋转稍微复杂了一点点，因为多了一个维度；理解更困难，不直观；
为什么使用齐次坐标
在MVP矩阵变换中为了将线性变换和非线性变换统一成一个线性变换
在3维到2维的过程中用于支持投影矩阵
AABB包围盒如何判断相交与分离
两个AABB包围盒a和b的中心位置pos的距离小于两个的两个包围盒半长的和的时候则相交