LycTechStack

从这一节开始用图形学知识学习 Shader 编写，虽然 Unity Shader 不完全等同于 Shader，但 Unity 提供了更方便的 Shader 编写环境，提供了大量的内置函数和变量，并且支持 GLSL , HLSL 和 CG 语言，是练习 Shader 编程的很好的平台。这一节我们从最简单的布林冯光照模型开始，学习如何用 Shader 渲染物体。

二分查找是一个常见的面试主题，也是计算机科学中最基本的算法思想之一，虽然二分查找比较简单，大部分专门考察二分查找的题目在实际机试中也几乎不会出现，但二分查找是许多困难题目中必不可少的一个步骤，因此值得单独花一定时间将其彻底掌握。这一节将学习三个不同的二分查找模板并在对应的题目上进行实践和巩固，这之中也不乏之前做过的题目，顺便复习一下。

区间动态规划一般用在单串问题上，以区间 [i, j] 为单位思考状态的设计和转移。一般是定义 dp[i][j]，表示考虑 [i..j] 范围内的元素，原问题的解，增加 i或减小 j 都可以得到更小规模的子问题。它与线性动态规划在状态设计和状态转移上都有明显的不同，但由于这两个方法都经常用在单串问题上，导致我们拿到一个单串的问题时，经常不能快速反映出应该用哪种方法。这是区间动态规划的难点之一，但是这个难点也是好解决的，就是做一定数量的练习题，因为区间动态规划的题目比线性动态规划少很多，并且区间动态规划的状态设计和转移都比较朴素，变化也比线性动态规划少很多，所以通过不多的题目数量就可以把区间动态规划常见的方法和变化看个大概了。

高级渲染和材质概述

这一节的内容涉及许多比较复杂的高级渲染方法和材质的知识，只做了解，增长见识，如果以后对哪方面需要深入学习可以方便查找。

材质（Materials）

这一节开始学习图形学中材质的相关内容。我们之所以能看到现实世界中不同的物体有不同的材质，本质上就是因为不同材质对光线的吸收、反射、折射的能力不同，而描述这种能力的函数就是我们上一节中简单了解过的双向反射分布函数（BRDF），上一节中也说过，BRDF 就是材质，因此这一节讨论的内容实际上就是 BRDF。

路径追踪（Path Tracing）

这一节我们正式开始学习路径追踪技术，首先我们要利用上一节的辐射度量学基础理解双向反射分布函数并推导出反射方程和渲染方程，然后利用渲染方程理解全局光照，之后简单复习一下蒙特卡洛积分的相关内容，最后通过解渲染方程来构建路径追踪算法。这一节内容可能非常硬核，涉及物理、微积分、概率论等多方面的知识，但这也是迈向真正的现代图形学大门的第一步。

在之前的很多题目中其实已经用到了前缀和，前缀和是一种查询数组中任意区间的元素的和的数据结构，这里数组给定之后就不变了。针对这个不变的数组，前缀和用于多次查询区间 [i, j] 上元素的和。
前缀和的推导和计算隐含着动态规划的基本思想，同时它的状态设计是线性动态规划中比较简单的那一类。与线性动态规划一样，前缀和也有一维和二维两种场景。
虽然前缀和本身很简单，但需要用到它解决的问题非常多，与其它数据结构配合的变化也很多，因此需要从线性动态规划中剥离出来单独学习。

辐射度量学（Radiometry）

上一节我们学习了 Whitted 风格光线追踪的基本原理和优化结构，Whitted 风格光线追踪是基于布林冯光照模型的渲染方式，回顾布林冯光照模型，其中有一个概念我们一直不清楚，那就是所有光照公式中的光照强度 $I$ 是如何定义的，光照强度到底是什么，是从哪里来的，又要用什么去衡量？并且上一节中我们也看到了，其实利用 Whitted 风格光线追踪渲染出来的图片并没有想象中那么真实，这是因为我们从头到尾都没有准确的对光照进行度量和描述，所有公式中的光都是抽象的，简化的结果。因此也无法解释上面的一系列问题。

从这一节开始我们将学习更为先进的路径追踪技术，路径追踪技术是基于辐射度量学的光线追踪算法，而辐射度量学是可以准确描述光线的空间属性的体系，可以保证在物理上绝对正确的情况下进行各种光照的计算。

从这一节开始我们将了解图形学中的光线追踪（Ray Tracing）技术，包括经典的 Whitted 风格光线追踪技术和效果更好的路径追踪技术。并且在之后的高质量实时渲染专题中还会进一步学习最新的工业界实时光线追踪技术。

1 矩阵问题

除了数组和字符串外，矩阵也是一种线性结构，很多一维数组或字符串的问题可以推广到二维，因此矩阵上也有一些经典的动态规划问题，矩阵上的动态规划问题，基本的状态设计就是用二维变量 (i, j) 共同表示以 (0, 0) 为左上角，(i, j) 为右下角的子问题。因此矩阵问题的状态定义和双串 $dp[i][j]$ 类似，状态的推导方向以及推导公式与双串相同，但是物理意义不一样，且求解时所需的子问题的变化相对更多。