《Fundamentals of Computer Graphics》第五版笔记

图形学虎书第5版笔记

封面

2022年出版。

本书网站

未完成

1 Introduction

计算机图形学一词描述了使用计算机来创建和操作图像的任何方式。

这一章定义了基础术语、提供了历史背景和一些计算机图形学相关的信息来源。

本书尽量避免依赖具体硬件或API。

1.1 Graphics Areas

大多数人认同的计算机图形学主要领域：

• 建模
• 渲染
• 动画

其它领域：

• 人机交互
• 虚拟现实
• 可视化
• 图像处理
• 三维扫描
• 计算摄影

1.2 Major Applications

• 视频游戏
• 卡通
• 视觉效果
• 动画电影
• CAD/CAM（computer-aided design / computer-aided manufacturing）
• 仿真
• 医学图像
• 信息可视化

1.3 Graphics APIs

每种图形程序都需要两种API，用于视觉输出的图形API和获取用户输入的用户界面API。

图形和用户界面API有两种主导范式，一种是Java那样图形和用户界面工具包是集成的、可移植的包，完全标准化并作为语言的一部分得到支持；一种是Direct3D和OpenGL那样绘图命令是与C++等语言相关的软件库的一部分，而用户界面软件是一个独立的实体，可能因系统而异。

1.4 Graphics Pipeline

3D图形管线是一个高效绘制透视3D图元的特殊软件/硬件子系统。

Z缓冲用内存缓冲区暴力解决从后到前顺序绘制三角形的问题。

管线中的几何操作几乎都在4D坐标空间中完成，三个传统几何坐标和一个齐次坐标。

以不同距离查看模型时，可以将模型用变化的LOD（level of detail）表示以提高绘制效率。

1.5 Numerical Issues

许多图形程序只是3D数值代码。

所有现代计算机都遵守1985年的IEEE浮点标准。

以32位浮点数为例，1位符号位、8位指数位、23位尾数位。

特殊数表示方法如下：

无穷数的符号位为1或0，指数位全为1，尾数位全为0。

NaN的符号位为1或0，指数位全为1，尾数位不为0即可。

另外，符号位为1或0，指数位全为0，尾数位全为0，表示+0或-0。

对于特殊数有以下计算规则（a是正数）： \[ +a/(+\infty)=+0 \] \[ -a/(+\infty)=-0 \] \[ +a/(-\infty)=-0 \] \[ -a/(-\infty)=+0 \] \[ \infty+\infty=+\infty \] \[ \infty-\infty=NaN \] \[ \infty\times\infty=\infty \] \[ \infty/\infty = NaN \] \[ \infty/a=\infty \] \[ \infty/0=\infty \] \[ 0/0=NaN \] \[ +a/+0=+\infty \] \[ -a/+0=-\infty \] 任何包含NaN的算术表达式的结果都是NaN。

任何涉及NaN的布尔表达式都为false。

1.6 Efficiency

目前内存的速度没有跟上处理器的速度，比起操作计数应该更关注内存访问模式。

提高代码速度的步骤：

1. 以最直接的方式编写代码。根据需要即时计算中间结果而不是存储他们。
2. 以优化模式编译。
3. 使用现有的任何分析工具查找性能瓶颈。
4. 检查数据结构以寻找改进局部性的方法。如果可能，使数据单元大小与目标架构上的缓存/页面大小匹配
5. 如果分析揭示了数值计算中的瓶颈，请检查编译器生成的汇编代码是否存在效率下降的情况。重写源代码以解决发现的任何问题

现代CPU执行浮点运算的速度通常与执行整数运算的速度一样快。

1.7 Designing and Coding Graphics Programs

为几何实体（向量、矩阵）和图形实体（RGB颜色、图像）设计合适的类。

作者认为位置和位移应该是不同的类。

建议几何计算使用单精度、颜色计算使用双精度。

DEBUG方法：

1. 创建一张图像观察哪里错了，提出假设并测试。直接使用图像作为DEBUG输出。
2. 固定随机种子，在单线程中运行，使用debugger。
3. 编写可视化程序显示程序内部状态。

2 Miscellaneous Math

此章笔记略。

2.1 Sets and Mappings

2.2 Solving Quadratic Equations

2.3 Trigonometry

Spherical Trigonometry 球面三角学

Solid Angles 立体角

2.4 Vectors

2.5 Integration

2.6 Density Functions

2.7 Curves and Surfaces

2.8 Linear Interpolation

2.9 Triangles

2.10 Discrete probability

2.11 Continuous probability

2.12 Monte Carlo Integration

FAQ

为什么没有向量除法？

向量除法没有好的类比。

实数域上的可除代数只出现在1、2、4维，分别对应到实数、复数、四元数，如果不要求是结合代数的话还有8维八元数。其他维数的实线性空间没法定义在非零元上可逆的乘法。

为什么复数没有定义叉乘点乘，向量没有定义除法？

Hurwitz.pdf (uoregon.edu)

什么是quasi–Monte Carlo(QMC)？

即拟蒙特卡罗方法，使用低差异序列而不是伪随机数进行数值积分或研究其它数值问题。

低差异序列高效的生成在高维空间分布均匀的随机数。

低差异序列（一）- 常见序列的定义及性质

🔺什么是四元数？（自己整理） \[ q=w+xi+yj+zk \] \[ i^2=j^2=k^2=-1 \] \[ jk=-kj=i \] \[ ki=-ik=j \] \[ ij=-ji=k \] \[ \|q\|=\sqrt{w^2+x^2+y^2+z^2} \] \[ q_v=xi+yj+zk \] \[ q_w=w \] \[ q^*=q_w-q_v \] \[ q^{-1}=q^*/\|q\| \] \[ q1_v\cdot q2_v=x1x2+y1y2+z1z2 \] \[ q1_v\times q2_v=(y1z2-y2z1)i+(z1x2-z2x1)j+(x1y2-x2y1)k \] \[ q1\cdot q2=q1_wq2_w+q1_v\cdot q2_v \] \[ q1\times q2=(q1_wq2_w-q1_v\cdot q2_v)+(q1_wq2_v+q2_wq1_v+q1_v\times q2_v) \] 单位四元数存在于四维空间的单位球上，满足\(\|q\|=1\)。

将三维球投影到二维平面y=0得到一个圆，球上y=0的点投影位于圆上，y>0半球和y<0半球的点投影位于圆内，圆内一点对应两个三维点。将四维球投影到三维超平面w=0得到一个三维球的情况类似，三维球内一点对应两个四元数，三维球面上的点唯一对应一个纯四元数（w=0）。所以将三维旋转矩阵转换为四元数时有两个对应值，四元数的范围是2倍覆盖于3D旋转。四元数所在群为S3，四元数代表的三维旋转是SO(3)，前者是后者的两倍覆盖。

对于旋转轴\((a,b,c)\)和旋转角\(\theta\)，对应四元数： \[ q=cos(\theta/2)+sin(\theta/2)ai+sin(\theta/2)bj+sin(\theta/2)ck \] \[ q^{-1}=cos(\theta/2)-sin(\theta/2)ai-sin(\theta/2)bj-sin(\theta/2)ck \] 将三维点\(d\) （将其表示为w=0的纯四元数）做以上旋转，得到的新点： \[ d_r=q\times d\times q^{-1} \] 这个运算形式是为了限制其结果所在空间，只有纯四元数与三维空间的点一一对应，对纯四元数运算得到纯四元数，才表示三维点旋转得到三维点。每次转\(\theta/2\)的原因如下图。

复数可以表示二维平面（横轴为实部，纵轴为虚部）上的旋转。二维向量1+i与横轴正半轴夹角为45度，任何二维向量乘1+i相当于将其旋转45度。参考A Visual, Intuitive Guide to Imaginary Numbers – BetterExplained。

什么是万向锁？

使用基于物体自身坐标系的欧拉角表示旋转时会产生万向锁问题。为方便理解，假设物体旋转前自身xyz轴与世界xyz轴重合，第一次绕自身的z轴旋转，第二次绕自身的x轴旋转，第三次绕自身的y轴旋转，当第二次旋转使自身的y轴与世界z轴（即旋转前自身的z轴）重合时，第三次绕自身的y轴旋转就是绕世界z轴旋转（即绕旋转前自身的z轴旋转），这样第三次旋转与第一次旋转都是在绕同一个轴旋转，丢失了一个自由度。

所以同一旋转，欧拉角表示不唯一，并且欧拉不能插值，所以用四元数表示旋转。

3 Raster Images

Raster images是通用的输入和输出形式，Vector images在输出时也要光栅化。

3.1 Raster Devices

输出

• 显示器（Display）

  • Transmissive：不发光，调节通过其的光通量，需要背光源。如LCD（Liquid crystal display）。

  • Emissive：自发光，直接控制光通量。如LED（Light-emitting diode）。

    LED与LCD显示屏的划分源自厂商的宣传，实际上，LED显示屏指采用LED作为背光源的LCD，LCD显示屏指使用CCFL为背光源的LCD。

• 硬拷贝器（Hardcopy）

  • Binary：喷墨打印机。
  • Continuous tone：热升华打印机。

输入

• 2D array sensor：数码相机。
• 1D array sensor：平板扫描仪。

3.2 Images, Pixels, and Geometry

图片区域到像素值集合的映射： \[ I(x,y):R\to V \] 像素值是图片上一个采样点的局部平均颜色。

图片大小一般用宽*高表示，单个像素索引为\((column_i,row_j)\)。

存储浮点数的一般称为high dynamic range (HDR) 图片，存储整数的一般称为low dynamic range (LDR) 图片。

显示器强度和输入像素值\(a\)是非线性关系，伽马编码的伽马值为\(\gamma\)： \[ displayed\ intensity=(maximum\ intensity)a^{\gamma} \] 测得伽马值\(\gamma\)后，可以对a进行伽马矫正（即用另一个伽马编码抵消）： \[ a_c=a^{\frac{1}{\gamma}} \]

\[ \begin{align}displayed\ intensity &= (maximum\ intensity){a_c}^{\gamma} \\ &= (maximum\ intensit)a \end{align} \]

图片在存储像素值时使用sRGB格式进行伽马编码（伽马值小于1，0.45），与显示器在显示图片时的伽马编码（伽马值大于1，2.2）抵消。

对图片伽马编码起源于对CRT显示器的伽马编码的抵消，但如今液晶显示器已经可以人工设定伽马值，不做线性显示器是因为需要伽马编码，人眼对暗部细节的感知灵敏度更高，伽马编码相比线性编码存储更多的暗部信息。

在shader中做计算时需要在线性空间计算，因此将图片读出的像素值转换到线性空间计算，再转换回去。

人眼感知的内容见19章。

3.3 RGB Color

红黄蓝三原色减色混合得到其它的颜色。显示器使用红绿蓝的加色混合。

3.4 Alpha Compositing

前景颜色\(c_f\)和背景颜色\(c_b\)： \[ c=\alpha c_f+(1-\alpha)c_b \]

4 Ray Tracing

对象顺序渲染依次考虑每个对象，图像顺序渲染依次考虑每个像素。光追是渲染3D场景的图像顺序算法。

4.1 The Basci Ray-Tracing Algorithm

基础光线追踪器有三部分：

1. ray generation 基于摄影集合计算每个像素的视线的原点和方向
2. ray intersection 找到与视线相交的最近物体
3. shading 基于视线相交结果计算像素颜色（结果包括命中点、光照、表面法线等）

4.2 Perspective

直线透视（linear perspective）：场景中的直线在图片中依然是直线。（鱼眼镜头就不是直线透视）

平行投影（parallel projection）：保留平行关系和形状尺寸，用于机械和建筑设计。

• 直角投影（orthographic）：投影平面与视点方向垂直。
• 斜投影（oblique）：不垂直。

透视投影也有斜投影，只是不常用。

透视投影（perspective projection）：近大远小，即人眼成像方法。

4.3 Computing Viewing Rays

光线的参数方程： \[ p(t)=e+t(s-e) \] 从视点e行进到一点s，t是参数。

相机坐标系\(\{u,v,w\}\)是右手坐标系，从相机视角来看，u指向右方，v指向上方，w指向后方（与相机视角方向相反）。

对于平行投影，光线的方向相同原点不同；对于透视投影，光线的原点相同方向不同。

4.4 Ray-Object Intersection

光线： \[ \vec{p}(t)=\vec{e}+t\vec{d} \] 球心为\(\vec{c}\)，光线击中球： \[ (\vec{p}-\vec{c})\cdot(\vec{p}-\vec{c})-R^2=0 \] 击中球处\(\vec{p}\)的单位法线： \[ \vec{n}=(\vec{p}-\vec{c})/R \] 三角形顶点为\(\vec{a}\)、\(\vec{b}\)、\(\vec{c}\)，光线击中三角形： \[ \vec{p}=\alpha+\beta(\vec{b}-\vec{a})+\gamma(\vec{c}-\vec{a}) \] 击中点位于三角形内的条件是\(\beta>0,\gamma>0,\beta+\gamma<1\)。

设计程序时应该设定一个Surface类作为所有可与光线相交的对象和efficiency structures（参见12.3）的父类。

4.5 Shading

五种光源：

point lights 从一点发光

directional lights 从单一方向照亮场景

ambient lights 填充阴影的恒量照明（没有阴影测试）

area lights 发光的场景几何

environment lights 使用图像来表示来自天空等远处光源的光

计算所需的四个向量：着色点\(\vec{x}\)、法线\(\vec{n}\)、光照方向\(\vec{l}\)、视点方向\(\vec{v}\)。

计算阴影时，检测表面\(s\)上一点\(p\)与光源\(l\)的连线是否被遮蔽，为了避免数值计算的不精确导致\(p\)被\(s\)遮蔽，将\(p\)沿着其与\(l\)的连线移动一小段距离。

4.6 Historical Notes

光追的渐进时间复杂度低于基础的对象顺序渲染算法。随着硬件的进步实时光追越来越普遍。

5 Surface Shading

着色模型完全独立于渲染系统的其余部分，相同的模型可以用于光线跟踪和光栅化系统。

本章介绍点光源照明的不透明表面的基本着色模型。

5.1 Point-like light sources

点光源由其位置和强度描述。

手电筒和太阳也算点状光源，一个够小，一个够远。

irradiance 辐照度E 单位\(W/m^2\)

radiance 辐射率L 单位\(W/(m^2*sr)\)

5.2 Basic reflection models

镜面反射发生在表面顶部，并在反射方向附近反射；漫反射发生在表面之下，并向各个方向出现。

Lambertian reflection： \[ L_r=kE=\frac{R}{\pi}E \] albedo R表示反射的辐照度的百分比，k的取值原因参见第14章（能量守恒）。

Lambertian着色是理想的漫反射着色，颜色与视点无关。适用于纸张、平面油漆、泥土、树皮、石头等粗糙材质。（颜色的精确预测参见第18章）

Specular reflection：

Modified Blinn–Phong model。 \[ L_r=(\frac{R}{\pi}+k_smax(0,n\cdot h)^p)E \] \(\vec{h}\)是光照方向\(\vec{l}\)和视点方向\(\vec{v}\)的半向量，点积\((n\cdot h)^p\)描述了反射强度，\(\vec{h}\)与\(\vec{n}\)越接近反射越强，Phong指数\(p\)越大反射越强。

颜色与视点相关。适用于金属、塑料、光泽或半光泽油漆、大量植物叶子。

p的典型取值：

10——"eggshell"

100——mildly shiny

1000——really glossy

10,000——nearly mirror-like

（关于BRDF的完整讨论参见第14章）

Calculating shading

可以分为计算辐照度与计算反射光两部分，彼此无关。上面已计算反射光。

计算辐照度： \[ E=\frac{max(0,n\cdot l)}{r^2}I\ \ (point) \] \[ E=max(0,n\cdot l)H\ \ (directional) \]

\(I\)和\(H\)为光源强度。

光线追踪和光栅化之间获取计算所需量的方式有很大不同，但实际的着色计算本身是相同的。所有向量都要归一化。

5.3 Ambient illumination

\[ L_r=k_aI_a \]

防止阴影完全变黑，并可以轻松调整整个场景对比度。

6 Linear Algebra

此章笔记略。

6.1 Determinants

6.2 Matrices

6.3 Computing with Matrices and Determinants

6.4 Eigenvalues and Matrix Diagonalization

FAQ

逐元素的矩阵乘法称为什么？

Hadamard积。

奇异值和特征值的区别？

矩阵的奇异值与特征值有什么相似之处与区别之处？- 赵文和的回答

7 Transformation Matrices

此章笔记略。参见GAMES101-03/04笔记。

7.1 2D Linear Transformations

7.2 3D Linear Transformations

7.3 Translation and Affine Transformations

7.4 Inverses of Transformation Matrices

7.5 Coordinate Transformations

8 Viewing

此章笔记略。参见GAMES101-03/04笔记。

8.1 Viewing Transformations

8.2 Projective Transformations

8.3 Perspective Projection

8.4 Some Properties of the Perspective Transform

8.5 Field-of-View

❓这章末尾的一个FAQ我没有看懂：

• The tessellated spheres I draw in perspective look like ovals. Is this a bug?

No. It is correct behavior. If you place your eye in the same relative position to the screen as the virtual viewer has with respect to the viewport, then these ovals will look like circles because they themselves are viewed at an angle.

9 The Graphics Pipeline

找到图像中被几何图元占据的所有像素的过程称为光栅化，因此对象顺序渲染也可以称为光栅化渲染。光栅化从对象开始到更新图像中的像素为止的操作序列称为图形管线。

9.1 Rasterization

Line Drawing

Triangle Rasterization

Perspective Correct Interpolation

透视投影是非线性的，因此透视投影或需要对重心坐标进行矫正。应从屏幕空间逆变换回三维空间，再用重心坐标插值。

可参考：矫正透视投影插值及属性插值详解

Clipping可以发生在变换前或齐次坐标空间。这节只讲了求点与平面交点的公式，裁剪三角形参见12.4.3。

9.2 Operations Before and After Rasterization

Simple 2D Drawing

没有vertex或fragment阶段。

A Minimal 3D Pipeline

做MVP和视口变换，需要按前后顺序绘制面元。

Using a z-Buffer for Hidden Surfaces

使用z-Buffer给每个fragment存一个深度值。考虑到精度问题，谨慎选择近平面n和远平面f，使n尽量大，f尽量小。

Per-vertex Shading

即Gouraud shading。

Per-fragment Shading

即Phong shading。（和Phong illumination model是两种东西）

Texture Mapping

给每个顶点赋纹理坐标。

Shading Frequency

根据实际需要选择不同着色频率的shading 方法。

（这节没提flat shading）

9.3 Simple Antialiasing

MSAA通过给每个fragment存储一个color加上一个coverage mask和一组 depth values。

9.4 Culling Primitives for Efficiency

三种Culling 策略（同时使用）：

• view volume culling
• occlusion culling
• backface culling

10 Signal Processing

信号处理。

10.1 Digital Audio: Sampling in 1D

10.2 Convolution

10.3 Convolution Filters

10.4 Signal Processing for Images

10.5 Sampling Theory

11 Texture

本章讨论使用纹理来表示表面细节、阴影和反射。

重点是纹理映射函数和克服纹理映射（重采样）造成的aliasing。

11.1 Looking Up Texture Values

Color texture_lookup(Texture t, float u, float v) {
    int i = round(u * t.width()- 0.5)
    int j = round(v * t.height()- 0.5)
    return t.get_pixel(i,j)
}

Color shade_surface_point(Surface s, Point p, Texture t) {
    Vector normal = s.get_normal(p)
    (u,v) = s.get_texcoord(p)
    Color diffuse_color = texture_lookup(u,v)
    // compute shading using diffuse_color and normal
    // return shading result
}

需要知道surface S到texture T的映射关系get_texcoord： \[ \begin{align} \phi&:S\to T \\ &:(x,y,z)\longmapsto (u,v) \end{align} \]

11.2 Texture Coordinate Functions

也称作UV mapping或surface parameterization。

设计\(\phi\)需要考虑的几个竞争性目标：

• Bijectivity，即injective和surjective。
• Size distortion，\(\phi\)的导数的变化不应太大，即表面上间隔大致相同的点对映射到纹理上间隔也应大致相同。
• Shape distortion，不同方向上\(\phi\)的导数不应相差太大，即形状不应变化太大，表面上的圆形映射到纹理上也是圆形。
• Continuity，\(\phi\)应该是连续的或者具有尽可能少的不连续性，即不应有太多接缝，表面上的相邻点应映射到纹理中的相邻点。

Geometrically Determined Coordinates

对于简单形状或特俗情况。

Planar Projection

Spherical Coordinates

Cylindrical Coordinates

Cubemaps

Interpolated Texture Coordinates

对于需要细粒度控制纹理坐标的三角形网格表面。

顶点存纹理坐标，对整个三角形进行重心插值。

Tiling, Wrapping Modes, and Texture Transformations

可以对纹理进行平铺、缩放、平移。

Continuity and Seams

对于任何封闭的三维表面，没有连续的双射函数将整个表面映射成纹理图像是拓扑学的基本结论。在纹理坐标突然改变的表面上引入接缝曲线，可以在其他地方降低失真。

Texture coordinates in rendering systems

在光线追踪渲染器中，支持光线相交的每种类型的表面必须不仅能够计算相交点和表面法线，而且还能够计算相交点的纹理坐标。光线击中时，由三角形网格表示的几何体可以根据存储在顶点的纹理坐标通过重心插值来计算纹理坐标，对于其他类型的几何体必须直接计算纹理坐标。

在基于光栅化的系统中，三角形通常是唯一受支持的几何类型，所有曲面都必须转换为这种形式。光栅化器对纹理坐标进行插值，以便fragment着色器的每次调用都具有适合其的纹理坐标。

11.3 Antialiasing Texture Lookups

参考GAMES101-09笔记。

11.4 Applications of Texture Mapping

1. Controlling Shading Parameters：base color，metallic，roughness等贴图。

2. Normal Maps and Bump Maps：法线贴图 (切线参考系下) 是凹凸贴图的导数。

3. Displacement Maps：位移贴图实际改变曲面。（光追中没有ideal way应用位移贴图）

4. Shadow Maps：用一个单独的渲染pass提前计算，在光源处光栅化得到的深度图即为阴影贴图。执行一个普通渲染pass时，若需要知道一个fragment对光源是否可见时，将其投影到阴影贴图中（使用最初用于渲染阴影贴图的透视图投影），并将查找值\(d_{map}\)与实际距光源距离\(d\)进行比较，若\(d>d_{map}\)说明有阴影，相等则没有。

   由于数值计算的精度问题，需要引入shadow bias判断相等关系。

   对阴影贴图插值没有意义，在阴影边界会导致问题。阴影贴图中的纹理查找使用最近邻重构来完成。减少aliasing，可以使用多个样本，对1或0的阴影结果（而不是深度）进行平均，这被称为percentage closer filtering（PCF）。

5. Environment Maps：环境贴图。

11.5 Procedural 3D Textures

3D纹理容易定义映射函数，没有distortion。适合由固体介质雕刻而成的表面，如大理石雕像。

3D纹理若存储为3D光栅图像或体积会消耗大量内存。因此3D纹理坐标最常用于程序纹理，纹理值使用数学过程计算，而不是从纹理图像中查找来计算的。

3D Stripe Textures

Solid Noise (Perlin noise)

12 Data Structures for Graphics

12.1 Triangle Meshes

带宽比存储更宝贵。

Mesh Topology

manifold来自拓扑学的数学领域。一个二维流形是这样一个表面：任何一点的小邻域可以被平滑为一小块平表面。

边为manifold的条件：正好只由两个三角形share。

点为manifold的条件：周围正好只有一个完整的三角形环。

manifold不能有boundary，但实际应用中可以放宽条件：边由一个或两个三角形share，点连到一组边相连的三角形。

默认情况下，front是三角形顶点逆时针绕序的那一面。网格若朝向一致，称为consistently oriented。manifold可能无法定义为朝向一致，如Mobius band。

Indexed Mesh Storage

通过存储索引减小内存消耗。

Triangle Strips and Fans

更高效的三角形组织方式。n+2个顶点描述n个三角形。

Data Structures for Mesh Connectivity

修改网格需要知道点、边、三角形之间的关系。

低效的数据结构：

Triangle {
    Vertex v[3]
   Edge e[3]
 }

Edge {
    Vertex v[2]
    Triangle t[2]
}

Vertex {
    Triangle t[]
    Edge e[]
}

The Triangle-Neighbor Structure：

以三角形为核心。

Triangle {
    Edge nbr[3];
    Vertex v[3];
}

Edge { // the i-th edge of triangle t
    Triangle t;
    int i; // in {0,1,2}
}

Vertex {
    // ... per-vertex data ...
    Edge e; // any edge leaving vertex
}

The Winged-EdgeStructure：

以边为核心。

Edge {
    Edge lprev, lnext, rprev, rnext;
    Vertex head, tail;
    Face left, right;
}

Face {
    // ... per-face data ...
    Edge e; // any adjacent edge
}

Vertex {
    // ... per-vertex data ...
    Edge e; // any incident edge
}

The Half-Edge Structure：

HEdge {
    HEdge pair, next;
    Vertex v;
    Face f;
}
Face {
    // ... per-face data ...
    HEdge h; // any h-edge of this face 
}

Vertex {
    // ... per-vertex data ...
    HEdge h; // any h-edge pointing toward this vertex
}

12.2 Scene Graphs

用层级结构组织对象，便于得到对象的子对象的transform矩阵（如车的轮子）。

对于光栅化，使用很多API支持的矩阵栈实现。

对于光追，使用instancing技术，存储对象和transform矩阵，显式的变换在渲染时完成。如果有一条光线要和变换后的对象相交，将反变换光线和未变换的对象相交。

优点：

• 未变换的对象可能更容易做相交。
• 大量变换后的对象可以共享一个未变换的对象。

12.3 Spatial Data Structures

空间数据结构旨在组织空间中的对象，以便有效地查找对象。可用于光追、视图剔除、碰撞检测。

Bounding Boxes

只有当光线击中边界框时，才会测试光线是否与表面相交。

Hierarchical Bounding Boxes

BVH (Bounding Volume Hierarchies) 算法。划分对象。

Uniform Spatial Subdivision

均匀划分空间。

Axis-Aligned Binary Space Partitioning

axis-aligned BSP。划分空间。

12.4 BSP Trees for Visibility

预先计算BSP树，运行时根据视点位置调用树，执行遍历，产生用于视图剔除的画家算法所需的从后向前的多边形顺序。

12.5 Tiling Multidimensional Arrays

通过tiling更好地组织多维数组的内存布局。例如，对于二维数组的普通布局方式，同行的相邻元素在内存中紧邻对方，但同列的相邻元素在内存中间隔（列数个）元素。

tile尺寸应与机器上的内存单元大小接近。

13 Sampling

13.1 Integration

13.2 Continuous Probability

13.3 Monte Carlo Integration

13.4 Choosing Random Points

14 Physics-Based Rendering

严格遵循物理模型而不是phenomenological。

推荐了pharr的PBR。

14.1 Photons

Photon在图形学里只是遵循几何光学的能量包。 \[ q=hf=\frac{hc}{\lambda} \] \(h=6.63\times 10^{-34}Js\)是Plank’s Constant。

14.2 Smooth Metals

Schlick approximation： \[ R_0(\lambda)=(\frac{n1(\lambda)-n2(\lambda)}{n1(\lambda)+n2(\lambda)})^2 \] \[ R(\theta,\lambda)=R_0(\lambda)+(1-R_0(\lambda))(1-cos\theta)^5 \] n为折射率（refractive indices）。

14.3 Smooth Dielectrics

一个启发式：不是导体就是电介质。

光滑均匀的电介质是透明的，如玻璃、水和眼睛的晶状体；混合物接近不透明，如皮肤、牛奶、头发、布料和几乎所有日常材料。

对于光滑电介质只有三个重要的属性：

1. 在每个入射角度和波长下反射的光有多少
2. 在给定的距离和波长内，光在材料中传播时被吸收的比例是多少
3. 反射光和折射光的方向是什么

Reflectivity of a Dielectric

电介质和金属同样适用Schlick approximation。

常用折射率n：水1.33，玻璃1.4-1.7，钻石2.4。

Refraction and Beer's law

Snell’s Law： \[ \eta_isin\theta_i=\eta_tsin\theta_t \] Beer's law： \[ I(s)=I(0)a^s \] \(a\)是degree of attenuation，\(s\)是距界面距离，\(I\)是光强。描述了光线被物质吸收产生的衰减。

14.4 Dielectrics with Subsurface Scattering

仅用光滑的电介质就可以呈现出一系列令人惊讶的材质。

冰块可以通过在内部放置小气泡变得不透明，也可以通过使表面粗糙变得不透明。

人类皮肤可以被建模成一个粗糙的表面和折射率稍微不同的多层、色素粒子（遵循比尔定律）、血液（遵循比尔定律）。

14.5 A Brute Force Photon Tracer

描述了最基本的光子追踪过程。

14.6 Radiometry

参见GAMES101-14笔记。

14.7 Radiometry of Scattering

讲了BRDF的定义和Ideal Diffuse BRDF。参见GAMES101-17笔记。

14.8 Transport Equation

即反射方程： \[ L_r(x,w_r)=\int_{\Omega}L_i(x,w_i)f(x,w_i,w_r)\cos \theta_id\omega_i \] 但书这里的写法很不一样： \[ L_s(x,k_o)=\int_{all\ x^{'}}\frac{\rho(k_i.k_o)L_s(x^{'},x-x^{'})v(x,x^{'})}{\left \|x-x^{'}\right \|^2}dA^{'} \] \[ v(x,x^{'})= \begin{align} \left\{\begin{matrix} 1\ &if\ x\ and\ x^{'}\ are\ mutually\ visible,\\ 0\ &otherwise. \end{matrix}\right. \end{align} \] \(\rho\)代表BRDF。

14.9 Materials in Practice

A Taxonomy of Bidirectional Scattering Distribution Function Lobes for Rendering Engineers

14.10 Monte Carlo Ray Tracing

参见GAMES101-16笔记。路径追踪是分布式光追的简化版本，每个像素发射多条光线，但但每次弹射只产生一条光线。

15 Curves

15.1 Curves

15.2 Curve Properties

15.3 Polynomial Pieces

15.4 Putting Pieces Together

15.5 Cubics

15.6 Approximating Curves

15.7 Summary

16 Computer Animation

16.1 Principles of Animation

16.2 Keyframing

16.3 Deformations

16.4 Character Animation

16.5 Physics-Based Animation

16.6 Procedural Techniques

16.7 Groups of Objects

17 Using Graphics Hardware

17.1 Hardware Overview

17.2 What Is Graphics Hardware

17.3 Heterogeneous Multiprocessing

17.4 Graphics Hardware Programming: Buffers, State, and Shaders

17.5 State Machine

17.6 Basic OpenGL Application Layout

17.7 Geometry

17.8 A First Iook at Shaders

17.9 Vertex Buffer Objects

17.10 Vertex Array Objects

17.11 Transformation Matrices

17.12 Shading with Per-Vertex Attributes

17.13 Shading in the Fragment Processor

17.14 Meshes and Instancing

17.15 Texture Objects

17.16 Object-Oriented Design for Graphics Hardware Programming

17.17 Continued Learning

18 Color

18.1 Colorimetry

18.2 Color Spaces

18.3 Chromatic Adaptation

18.4 Color Appearance

19 Visual Perception

19.1 Vision Science

19.2 Visual Sensitivity

19.3 Spatial Vision

19.4 Objects, Locations, and Events

19.5 Picture Perception

20 Tone Reproduction

20.1 Classification

20.2 Dynamic Range

20.3 Color

20.4 Image Formation

20.5 Frequency-Based Operators

20.6 Gradient-Domain Operators

20.7 Spatial Operators

20.8 Division

20.9 Sigmoids

20.10 Other Approaches

20.11 Night Tonemapping

20.12 Discussion

21 Implicit Modeling

21.1 Implicit Functions, Skeletal Primitives, and Summation Blending

21.2 Rendering

21.3 Space Partitioning

21.4 More on Blending

21.5 Constructive Solid Geometry

21.6 Warping

21.7 Precise Contact Modeling

21.8 The BlobTree

21.9 Interactive Implicit Modeling Systems

22 Computer Graphics in Games

22.1 Platforms

22.2 Limited Resources

22.3 Optimization Techniques

22.4 Game Types

22.5 The Game Production Process

23 Visualization

23.1 Background

23.2 Data Types

23.3 Human-Centered Design Process

23.4 Visual Encoding Principles

23.5 Interaction Principles

23.6 Composite and Adjacent Views

23.7 Data Reduction

23.8 Examples