八股

哈希表

实现原理：

哈希函数的作用是将给定的键转换为一个数组的索引。哈希函数接收一个输入并输出一个整数，这个整数在哈希表中对应的索引位置。

哈希函数的设计要确保以下几点：

• 均匀分布：哈希函数应当能够将输入均匀地映射到表中的各个桶位置，减少碰撞的概率。
• 低冲突：哈希函数应尽量减少不同的键映射到同一个位置（即哈希冲突）。

冲突解决方式：

1. 链接法：每个桶是一个链表，发生冲突就在该位置尾插冲突元素。
2. 开放地址法：开放地址法是一种将所有元素直接存储在哈希表数组中的方法，不使用链表来处理冲突。当发生冲突时，系统会查找哈希表中的下一个空桶位置，并将元素插入到该位置。常见的开放地址法有以下几种：
   • 线性探测（Linear Probing）：当发生冲突时，检查当前位置的下一个位置，直到找到空位置为止。
   • 二次探测（Quadratic Probing）：探测时按照二次方规律进行，即 i=(h+f(i))mod  TableSizei = (h + f(i)) TableSizei=(h+f(i))modTableSize，其中 f(i)f(i)f(i) 是一个平方数序列。
   • 双重哈希（Double Hashing）：使用第二个哈希函数来决定下一个探测位置。

堆和栈

栈是一种 先进后出数据结构，通常用于存储局部变量和函数调用信息（如函数的参数、返回地址等）。栈由操作系统管理，程序的执行栈在函数调用时不断压入和弹出。

堆是一块由程序员显式管理的内存区域，用于存储动态分配的内存。程序员通过 new（C++）或 malloc（C）等函数申请内存，并在使用完毕后，通过 delete（C++）或 free（C）手动释放这部分内存。

算法题

链表

1. 约瑟夫环问题的三种解法讲解 - 力扣（LeetCode）：环形链表模拟，有序集合模拟，数学归纳推导

二叉树

1. 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
2. 106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
3. 889. 根据前序和后序遍历构造二叉树 - 力扣（LeetCode）

哈希

1. 594. 最长和谐子序列 - 力扣（LeetCode）

二分查找

1. 153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
2. 【不用库函数求】69. x 的平方根 - 力扣（LeetCode）：也能用牛顿迭代

分治法

1. 12.4 汉诺塔问题 - Hello 算法 (hello-algo.com)

智力题

1. 将一根木棍分成三段，求这三段构成三角形的概率

虚拟地址空间

以32位机器为例，它的虚拟内存空间大小为，也就是4GB。但操作系统会独占一部分虚拟内存空间，因此进程实际上最多占用3GB。

进程, 线程和协程

概念和区别

进程、线程和协程是操作系统和程序设计中重要的概念，它们的主要区别在于执行单元的粒度、资源开销以及调度方式。下面详细解释它们之间的区别：

1. 进程（Process）

• 定义：进程是操作系统资源分配的基本单位，它是正在运行的程序的实例。每个进程都有自己独立的地址空间、代码段、数据段、堆栈以及文件描述符。
• 资源管理：进程拥有自己独立的资源，如内存、文件句柄、网络连接等，进程间不能直接共享数据。
• 开销：进程间切换的开销较大，因为涉及到上下文切换，操作系统需要保存和恢复各个进程的状态信息。
• 调度：操作系统的调度程序管理进程的调度，通常通过时间片轮转（preemptive scheduling）来调度不同进程的执行。
• 优点：进程之间相互独立，一个进程的崩溃不会直接影响到其他进程。
• 缺点：进程之间的通信（IPC）比较复杂，开销也大。

2. 线程（Thread）

• 定义：线程是进程中的一个执行单元，一个进程可以包含多个线程，它们共享进程的资源（如内存、文件描述符等），每个线程有独立的栈空间和程序计数器（PC）。
• 资源管理：多个线程共享进程的资源，可以直接共享内存中的数据，这使得线程之间的通信更加高效。
• 开销：线程切换的开销比进程切换小，但仍然需要保存和恢复线程的上下文，线程的创建和销毁比进程更轻量。
• 调度：操作系统通常使用抢占式调度或者协作式调度来调度线程。线程的调度比进程更频繁，通常会比进程切换更加高效。
• 优点：线程之间的共享资源使得数据传输更简单，适合执行并发任务。
• 缺点：线程之间的共享内存可能会导致数据竞争（race condition）和死锁（deadlock）等问题，必须小心同步。

3. 协程（Coroutine）

• 定义：协程是一种比线程更加轻量级的执行单元，通常是程序中的一个函数或代码块。协程不像线程那样由操作系统调度，而是由程序本身进行调度。
• 资源管理：协程通常共享进程和线程的资源，因为它们在同一线程中运行。协程不需要额外的内存栈，因为它们是通过用户级的调度来管理的。
• 开销：协程的创建、切换和销毁的开销极小。与线程相比，协程更轻量，可以在同一线程中创建成千上万个协程。
• 调度：协程的调度完全由程序控制，通常是通过事件循环或回调机制来管理执行。协程通过 yield 或 await 等操作来挂起和恢复执行，允许在执行中暂停并切换到其他任务。
• 优点：协程的切换非常轻便，适合处理大量 I/O 密集型任务（如网络请求或文件操作），并且协程通常不会有线程间的竞态问题。
• 缺点：协程不适合 CPU 密集型任务，因为它们是单线程执行的。如果有大量 CPU 密集型计算，可能会造成性能瓶颈。

主要区别总结：

应用场景：

• 进程：适合于需要高度隔离和独立运行的任务，或者多进程并发（如 Web 服务中的多进程模式）。
• 线程：适合需要在同一应用内共享资源且并发执行的任务（如多线程下载、计算等）。
• 协程：适合大量 I/O 操作且希望极低的创建和切换开销的场景（如网络爬虫、异步编程）。

通信方式

进程间通信：

• 管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
• 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
• 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
• 套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。

线程间通信：

• 锁机制：包括互斥锁、条件变量、读写锁

  互斥锁提供了以排他方式防止数据结构被并发修改的方法。

  读写锁允许多个线程同时读共享数据，而对写操作是互斥的。

  条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

• 信号量机制：包括无名线程信号量和命名线程信号量。

• 信号机制：类似进程间的信号处理。

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

图形学

渲染管线

渲染管线的构成

在概念上可以将图形渲染管线分为四个阶段：

1. 应用程序阶段：在CPU端完成，该阶段主要是在软件层面上执行的一些工作，包括空间加速算法、视锥剔除、碰撞检测、动画物理模拟等。

   大体逻辑是，执行视锥剔除，查询出可能需要绘制的图元并生成渲染数据，设置渲染状态和绑定各种Shader参数，调用DrawCall，交给GPU渲染。

2. 几何处理阶段：负责大部分多边形操作和顶点操作，将三维空间的数据转换为二维空间的数据。

   1. 顶点处理阶段：执行顶点变换和着色的工作，通过MVP矩阵将顶点从局部空间转换到屏幕裁剪空间，方便后续转为NDC坐标。

      还可以进行顶点着色计算，如Flat shading和Gouraud Shading。

      之后有一些可选阶段，例如曲面细分等。

   2. 裁剪阶段：裁剪掉不在屏幕内部的图元，由硬件控制。

      在CPU已经视锥体剔除了，为什么这里还要裁剪？

      主要是两次裁剪的粒度不同。CPU端的视锥体剔除是根据物体包围盒是否在视锥体内，针对整个物体裁剪；而这里的裁剪则是针对图元单位裁剪。

   3. 屏幕映射阶段：将之前步骤得到的坐标映射为标准屏幕坐标NDC。

3. 光栅化阶段：将图元离散化成片段的过程.

   1. 三角形设置：计算出三角形的一些重要数据(如三条边的方程、深度值等)以供三角形遍历阶段使用，这些数据同样可用于各种着色数据的插值。
   2. 三角形遍历：找到哪些像素被三角形所覆盖，并对这些像素的属性值进行插值。通过判断像素的中心采样点是否被三角形覆盖来决定该像素是否要生成片段。通过三角形三个顶点的属性数据，插值得到每个像素的属性值。此外透视校正插值也在这个阶段执行。

4. 像素处理阶段：给每一个像素正确配色，最后绘制出整幅图。

   1. 像素着色：进行光照计算和阴影处理，决定屏幕像素的最终颜色。各种复杂的着色模型、光照计算都是在这个阶段完成。
   2. 测试合并：包括各种测试和混合操作，如裁剪测试、透明测试、模板测试、深度测试以及颜色混合等。经过了测试合并阶段，并存到帧缓冲的像素值，才是最终呈现在屏幕上的图像。

各种测试及其顺序

1. 裁剪测试：在裁剪测试中，允许程序员开设一个裁剪框，只有在裁剪框内的片元才会被显示出来，在裁剪框外的片元皆被剔除。裁切测试可以避免当视口比屏幕窗口小时造成的渲染浪费问题。

2. 透明测试（Alpha测试）：根据物体的透明度来决定是否渲染。

3. 模板测试：根据物体的位置范围决定是否渲染。

4. 深度测试：根据物体的深度决定是否渲染。

PBR

概念

基于物理的渲染，是指在渲染过程中，有关材质、光照、相机、光传输等都要基于准确的物理定律。

实现

使用Cook-Torrance模型实现PBR，这个BRDF模型有漫反射和镜面反射两部分组成： 首先是漫反射项： 其中是表面颜色，是常数。可在预处理后的环境贴图（即辐照度贴图）中采样获取。除以是为了对漫反射光进行标准化，因为前面含有BRDF的积分方程受影响。

然后是镜面反射项： 包含三个函数，此外分母部分还有一个标准化因子。三个函数如下：

• 法线分布函数：Normal Distribution Function，估算在受到表面粗糙度的影响下，朝向方向与半程向量一致的微表面的数量。
• 菲涅尔函数：Fresnel Equation，描述的是在不同的表面角下表面所反射的光线所占的比率。
• 几何函数：Geometry Function，描述了微表面自成阴影的属性。当一个平面相对比较粗糙的时候，平面表面上的微表面有可能挡住其他的微表面从而减少表面所反射的光线。

这三个函数有很多实现。UE4 中所使用的是：

• D 项使用 Trowbridge-Reitz GGX，
• F 项使用 Fresnel-Schlick 近似，
• G 项使用 Smith’s Schlick-GGX。

阴影技术

Shadow Mapping

原理

1. 从每个光源的位置渲染一遍场景，将得到的深度信息写入到贴图中，
2. 正常渲染一次场景，利用得到的shadowmap来判断哪些片段落在了阴影中。

常见问题

1. 光源VP矩阵的选择：平行光选用正交投影，点光源和聚光灯选用透视投影。需要注意的是，在透视投影得到的深度贴图中，深度值是 非线性的，在正式使用之前需要进行线性化操作。

   // 线性化操作
   float LinearizeDepth(float depth)
   {
       float z = depth * 2.0 - 1.0; // Back to NDC 
       return (2.0 * near_plane * far_plane) / (far_plane + near_plane - z * (far_plane - near_plane));
   }

2. 阴影抖动问题：可以通过偏移技术来解决，增加一个bias来比较片段深度，还有更好的一种方式是使用一种自适应偏移的方案，基于斜率去计算当前深度要加的偏移；

3. 阴影锯齿问题：可以使用百分比渐进过滤(PCF)技术进行解决：从深度贴图中多次采样，每次采样坐标都稍有些不同，比如上下左右各取9个点进行采样（即一个九宫格），最后加权平均处理，就可以得到柔和的阴影。标准PCF算法采样点的位置比较规则，最后呈现的阴影还是会看出一块一块的Pattern（图块），可以采用一些随机的样本位置，比如Poisson Disk来改善PCF的效果.

4. 采样Shadowmap的时候，需要将标准设备坐标系的坐标范围由[-1,1]修正到[0,1]，否则贴图的坐标范围是[0,1]，会采样错误。

PCSS

抗锯齿

光栅化的时候，是以像素中心点是否被三角形覆盖来决定是否生成片段，因此有些片段覆盖了采样点就生成，有些没有覆盖就不生成，最终导致了锯齿现象。

SSAA

向原画面大 x 倍的画面进行降采样，性能要求高。

MSAA

只对必要的地方（如边缘处）进行单画面 x 倍采样，也有一定性能要求，尤其是场景三角形数量极大时。

FXAA

即 Fast Approximate AA，快速近似 AA。它将每帧画面的边界提取出来，然后对其进行插值处理以达到快速近似 AA 的目的。

步骤：

1. 寻找整体画面边界：将画面的颜色空间从 RGB 转换到 HSL/HSV，根据亮度寻找；
2. 计算 AA 的混合朝向：对边界进行水平和垂直方向的滤波计算，比较二者的值得出朝向，方便进行后序混合操作；
3. 搜寻与朝向点相邻的部分边界：使用边界搜寻算法找到和朝向点相邻的部分边界；
4. 计算混合程度：知道朝向和部分边界后，就能求边界点沿朝向采样的程度了。利用类似相似三角形的原理，通过边界信息求自身的偏移值。

TAA

利用时序上的数据（上一帧信息 + Motion Vector）进行 AA 操作。

后处理技术

模糊

高斯模糊

优化

在处理千万级别顶点数量的大型3D场景时，如何提升渲染效率和优化用户交互体验

在千万级顶点的 3D 场景中，可以通过 渲染优化 和 交互优化 结合使用，以提高效率：

1. 渲染优化

   • 批处理（Instancing、Mesh Merging）
   • 视锥裁剪（Frustum Culling）
   • LOD 细节控制
   • 纹理优化（Mipmap、压缩）
   • 计算着色器加速

2. 交互优化

   • 多线程渲染
   • 异步加载
   • 遮挡剔除（Occlusion Culling）

数学

向量

点乘, 叉乘的公式和几何意义

点乘： 使用点乘可以：

• 求一个向量到另一个向量的投影；
• 判断两向量是否同方向；
• 找到两向量夹角；
• 计算向量大小；
• 沿某向量进行正交分解；

叉乘： 使用叉乘可以：

• 判断点在三角形的内/外侧

矩阵

3D的SRT变换

缩放：

绕x轴旋转：

前面的文章说过，矩阵其实是向量的数组，因此我们可以用三个轴的方向向量来表示一个旋转矩阵。按照上图描述，基本旋转矩阵为： 用齐次坐标描述：

类似的，绕y轴旋转为：

绕z轴旋转为：

平移：

通过SRT变换，也就是MVP变换中的M，将模型的点由局部坐标转换为世界坐标。

常见问题：

1. 是否可逆：SRT变换属于线性变换，线性变换与平移变换合起来为仿射变换，它们都是可逆的（除了投影变换外都可逆）。
2. SRT和TRS的结果是否相同：结果并不一样，这是因为像旋转和缩放这样的转换是相对于坐标系原点进行的。 缩放以原点为中心的对象产生的结果不同于缩放远离原点的对象所产生的结果。 同样，旋转以原点为中心的对象产生的结果不同于旋转远离原点的对象所产生的结果。

参考资料

• 【游戏开发面经汇总】- 图形学基础篇 - 知乎 (zhihu.com)