考察知识汇总
参考¶
【游戏开发面经汇总】- 图形学基础篇 - 知乎 (zhihu.com)
零基础非科班校招图形/引擎/游戏面经长文分享 - 知乎 (zhihu.com)
项目与开放性问题¶
介绍一下做的项目是基于什么，在其中担当了怎样的角色？¶
图形学与游戏相关¶
渲染管线¶
图形渲染管线是图形学知识考察最重要的一个问题，绝对是最高频的，必须掌握。问法有很多种，比如屏幕中一个像素是怎么绘制出来的，绘制出一幅图像的具体过程等。
基本流程（OpenGL）¶
1. 顶点数据（Vertex data）¶
- 顶点数据一般包含顶点位置、纹理坐标、顶点颜色等顶点属性。
2. 顶点着色器（Vertex Shader）¶
-
坐标变换 ：对传入的顶点数据进行坐标变换，由局部坐标到世界坐标到相机坐标再到裁剪坐标。即通过模型矩阵、观察矩阵、投影矩阵（即MVP矩阵）计算出顶点在裁剪空间（clip space）中的坐标。值得注意的是，对法线向量的变换不可以简单地右乘MVP矩阵，而应该右乘MVP的逆矩阵的转置矩阵，即 (MVP\(^{-1}\))\(^T\)。
-
顶点着色 ：顶点着色器是可编程的，可以在此阶段进行 平面着色（Flat Shading） 或 高洛德着色（Gouraud Shading） ，然后经过后面的光栅化操作插值得到各个片元的颜色，但由于这种方法得到的光照比较不自然，所以一般在片段着色器进行光照计算。
3. *曲面细分¶
- 曲面细分是利用镶嵌化处理技术对三角面进行细分，以此来增加物体表面的三角面的数量。
4. *几何着色器（Geometry Shader）¶
- 对输入的图元（点、线等）进行操作，比如将输入的点或线扩展成多边形。
5. 图元组装¶
- 图元装配 ：将输入的顶点组装成指定的图元，即根据索引将顶点链接在一起，组成点、线、面等图元。
- 视锥裁剪 ：裁剪掉视锥体外的图元或图元在视锥体外的部分（裁剪过程）。
- 透视除法 ：将裁剪空间中顶点的4个分量都除以 \(w\) 分量，将顶点坐标转换到NDC空间。值得注意的是，透视除法对于顶点的三维坐标空间来说是非线性的变换，因此在根据NDC空间或之后的屏幕空间的顶点坐标对顶点属性进行插值计算时，需要做透视矫正。
- 视口变换 ：将顶点坐标从NDC空间（三维）变换到屏幕空间（二维）。
6. 光栅化¶
- 光栅化是将连续的图形转化为离散屏幕像素点的过程。光栅化会确定图元所覆盖的片段，利用顶点属性插值得到片段的属性信息，然后送到片段着色器进行颜色计算，我们这里需要注意到片段是像素的候选者，只有通过后续的测试，片段才会成为最终显示的像素点。
-
- Early-Z ：一种提前深度测试的技术，目的是减少进入片段着色阶段的片段，优化性能。但需要注意，Early-Z技术与Alpha测试会出现冲突，导致透明物体后的物体无法被正确渲染。
7. 片段着色器¶
- 片段着色器用来决定屏幕上像素的最终颜色。在这个阶段会进行纹理映射、光照计算以及阴影处理，是渲染管线高级效果产生的地方。
8. 测试混合¶
- 裁剪测试 ：程序员可以指定一个裁剪框，只有在裁剪框内的片元会被绘制，常在视口比屏幕小时被使用。
- Alpha测试 ：根据物体的透明度判断是否渲染。程序员可以设置的不透明度阈值，只有不透明度超过阈值的片元会被绘制，可支持全透明物体的剔除（详情）。
- 模板测试 ：根据物体的位置范围判断是否渲染。程序员可以指定一个模板，只有位于这个模板中的图元片段，才会被渲染出来。
- 深度测试 ：根据物体的深度判断是否渲染。图形管线会先对每一个位置的像素存储一个深度值，称为深度缓冲（z-buffer），代表了该像素点在3D世界中离相机最近物体的深度值。于是在计算每一个物体的像素值的时候，都会将它的深度值和缓冲器当中的深度值进行比较，如果这个深度值小于缓冲器中的深度值，就更新深度缓冲和颜色缓冲的值，否则就丢弃。
- Alpha混合 ：Alpha混合可以根据片段的alpha值进行混合，用来产生半透明的效果。值得注意的是，半透明物体的绘制需要遵循画家算法(painter Algorithm)由远及近进行绘制，因为半透明的混合跟物体的顺序有严格的对应关系，一般会使用顺序无关的半透明渲染技术(Order-independent transparency，OIT)。
- 抖动（Dither） ：在色彩深度有限的情况下，通过使用随机数或者添加一个特定的抖动矩阵来决定相邻像素之间的颜色过渡，以模拟出更多的颜色深度的方法。抖动处理可以使图像看起来更加平滑，颜色过渡更加自然，提高图像的质量和美观度。抖动处理主要应用于颜色分量较少或系统显示器显示颜色深度有限的情况下。
基本流程（RTR4）¶
图形渲染管线实际上指的是一堆原始图形数据途经一个输送管道，期间经过各种变化处理最终出现在屏幕的过程，在概念上可以将图形渲染管线分为四个阶段： 应用程序 阶段、 几何 阶段、 光栅化 阶段和 像素处理 阶段。
- 应用程序阶段（Application）：通常是在CPU端于软件层面上进行处理，包括碰撞检测、动画物理模拟、空间加速算法以及视锥体剔除等任务，最后将数据送到渲染管线中。
- 几何处理阶段（Geometry Processing）：负责大部分顶点操作和多边形操作，将三维空间的数据转换为二维空间的数据。
- 光栅化阶段（Rasterization）：将图元离散化为单个像素。
- 像素处理阶段（Pixel Processing）：像素的着色和混合。
坐标变换¶
在我的博客中有详细的推导 「计算机图形学」矩阵变换推导 | Hi~ Call me FUJI! (gitee.io)
坐标变化过程如下图所示：
其中特别要强调的， view矩阵 和 projection矩阵的推导 都是面试中十分常见的问题，需要掌握。
世界坐标系 -> 相机坐标系¶
-
相机坐标系是以相机的光心为原点，以相机的朝向（lookat）、向上方向（up）、向右方向（right）为基向量形成的三维直角坐标系。值得注意的是，一般在规定坐标系为左手或右手系的情况下，只需要知道三个基向量中的两个即可通过叉乘得到第三个基向量。
-
视图矩阵推导：可以先计算将光心平移到原点的平移矩阵 \(T_{view}\)，再计算旋转三个基向量到与坐标轴对其的旋转矩阵 \(R_{view}\)，两者相乘可得视图矩阵。
注意，此例将朝向转换到z轴负方向，向上方向转换到y轴正方向，两者叉积转换到x轴正方向。
相机坐标系 -> 裁剪坐标系¶
-
视锥体是指相机的可视区域，裁剪坐标系是将相机坐标系的视锥体变换到标准立方体[-1,1]\(^3\)后对应的坐标系。
-
投影矩阵推导：此处略，详情见我的博客。
纹理映射¶
切线空间¶
在3D世界中定了如此多的坐标系，每个坐标系当然都有它的用途。比如局部空间，或者叫模型空间，它的目的就是方便我们对3D模型进行建模。在这个空间中，我们不需要考虑该模型在场景中可能出现的位置、朝向等众多细节，而专注于模型本身。在世界空间中，我们关心的问题是场景中各个物体的位置、朝向，即如何构建场景，而不必关注摄像机的观察位置及其朝向。可见，一个坐标系的根本用途，即让我们在处理不同的问题时，能够以合适的参照系，抛开不相关的因素，从而减小问题的复杂度。
直观地讲，模型顶点中的纹理坐标，就定义于切线空间。普通2维纹理坐标包含U、V两项，其中U坐标增长的方向， 即切线空间中的tangent轴，V坐标增加的方向，为切线空间中的bitangent轴。模型中不同的三角形，都有对应的切线空间，其tangent轴和bitangent轴分别位于三角形所在平面上，结合三角形面对应的法线，我们称tangant轴（T）、bitangent轴（B）及法线轴（N）所组成的坐标系，即切线空间（TBN）。
相关问题¶
1. 三维坐标如何变成屏幕坐标，有哪些变换？¶
2. 顶点着色器和片元着色器区别？（小红书）¶
3. alpha测试是处于什么阶段，和深度测试哪个先？（小红书）¶
4. 了解切线空间吗？讲一下法线贴图原理（小红书）¶
5. 在整个渲染管线当中一共进行过几次裁剪？（小红书）¶
光照模型¶
数学知识¶
相关问题¶
1. 线性代数点乘叉乘（小红书）¶
2. 怎么判断点在三角形内？（小红书）¶
实践知识¶
相关问题¶
1. 写一个模糊的shader（小红书）¶
2. 水波纹在哪里实现？（小红书）¶
3. 自己实现过什么shader效果？（小红书）¶
C++与计算机基础知识¶
内存模型¶
C++ 程序在运行时也会按照不同的功能划分不同的段，C++程序使用的内存分区一般包括：栈、堆、全局/静态存储区、常量存储区、代码区。
-
栈 ：目前绝大部分 CPU 体系都是基于栈来运行程序，栈中主要存放函数的局部变量、函数参数、返回地址等，栈空间一般由操作系统进行默认分配或者程序指定分配，栈空间在进程生存周期一直都存在，当进程退出时，操作系统才会对栈空间进行回收。
-
堆 ：动态申请的内存空间，就是由 malloc 函数或者 new 函数分配的内存块，由程序控制它的分配和释放，可以在程序运行周期内随时进行申请和释放，如果进程结束后还没有释放，操作系统会自动回收。
-
全局区/静态存储区 ：存放全局变量和静态变量，程序运行结束操作系统自动释放。
-
常量存储区 ：存放的是常量，不允许修改，程序运行结束自动释放。
-
代码区 ：存放代码，不允许修改，但可以执行。编译后的二进制文件存放在这里。
C++ 11¶
智能指针¶
智能指针主要用于解决内存泄露的问题，它可以自动地释放内存空间。因为它本身是一个类，当函数结束的时候会调用析构函数，并由析构函数释放内存空间。智能指针分为共享指针(shared_ptr), 独占指针(unique_ptr)和弱指针(weak_ptr)：
-
共享指针 （shared_ptr）：资源可以被多个指针共享，使用计数机制表明资源被几个指针共享。通过 use_count() 查看资源的所有者的个数，可以通过 unique_ptr、weak_ptr 来构造，调用 release() 释放资源的所有权，计数减一，当计数减为 0 时，会自动释放内存空间，从而避免了内存泄漏。
-
独占指针 （unique_ptr）：独享所有权的智能指针，资源只能被一个指针占有，该指针不能拷贝构造和赋值。但可以进行移动构造和移动赋值构造（调用 move() 函数），即一个 unique_ptr 对象赋值给另一个 unique_ptr 对象，可以通过该方法进行赋值。
-
弱指针 （weak_ptr）：指向 shared_ptr 指向的对象，能够解决由shared_ptr带来的循环引用问题。
C++的虚函数机制¶
虚函数通过虚函数表来实现。虚函数的地址保存在虚函数表中，在类的对象所在的内存空间中，保存了指向虚函数表的指针（称为“虚表指针”），通过虚表指针可以找到类对应的虚函数表。虚函数表解决了基类和派生类的继承问题和类中成员函数的覆盖问题，当用基类的指针来操作一个派生类的时候，这张虚函数表就指明了实际应该调用的函数。
- 构造函数和析构函数能不能为虚函数？ - 构造函数一般不能定义为虚函数。如果构造函数为虚函数，则类在创建时需要通过虚函数表指针去找到构造函数，但没有构造函数无法创建类。
- 析构函数一般定义为虚函数。析构函数定义成虚函数是为了防止内存泄漏，因为当基类的指针或者引用指向或绑定到派生类的对象时，如果未将基类的析构函数定义成虚函数，会调用基类的析构函数，那么只能将基类的成员所占的空间释放掉，派生类中特有的就会无法释放内存空间导致内存泄漏。
-
虚函数表存放在哪个内存区？ - 虚函数表位于只读数据段（.rodata），即C++内存模型中的常量区；而虚函数则位于代码段（.text），也就是代码区。
-
struct（int char）大小，加一个静态变量之后呢？加一个虚函数之后呢？ - 8字节（内存对齐），还是8字节（静态变量在全局/静态区），12字节（多了一个虚函数表指针）。
- 创建10个实例有几个虚函数表？ - 1个，虚函数表数量与实例的对象数量无关。
- 哪些不能是虚函数？ - 构造、内联、静态成员、lamda函数
相关问题¶
1. C++11 新特性¶
2. 介绍一下智能指针（小红书）¶
3. 内存空间/局部变量（小红书）¶
4. 多态（小红书）¶
5. 虚函数 (怎么实现、虚函数表存在哪里)（小红书）¶
6. STL中 array 和 vector 区别（小红书）¶
数据结构与算法¶
实现单链表的翻转（小红书）¶
验证BST 力扣98（小红书）¶
矩阵相乘（小红书）¶
程序效率问题？了解内存连续吗？你写的三个循环怎么改成两个循环？