Ayy3

时间停止吧,你是多么的美丽

cf想上橙,但没办法all in算法,所以进行复盘,多注重思维积累

刷题记录 2

dp

ABC373F

link:https://atcoder.jp/contests/abc373/tasks/abc373_f

在裸的完全背包上加了个条件:如果购买了 个相同物品,会有 的价值损失。

尝试先用正常的dp:记 为考虑前 个物品,用了 个容量的答案。

显然有转移 ,时间复杂度是 ,如果 全为1就是 级别的。

因此我们可以考虑将dp的第一维用单个物品容量来代替。记 为考虑单个容量不超过 的物品,用了 个容量的答案。

转移一样是 ,即考虑单个容量为 的物品的贡献,时间复杂度是

但是这里有个问题,就是单个容量为 的物品可能不是唯一的。假设对于容量为 的物品有两件,我们在dp转移枚举 (即购买两件物品)的时候,可能是购买同一个物品两件,也可能两件物品各购买一件,而这两种情况显然是不一样的,我们需要取最优。

因此我们将转移方程写为 ,这里的 为考虑购买 个容量为 个物品时对于答案的最优贡献。

怎么算这个 呢?第一反应是从 进行转移,当然这种想法是正确的。

假设我们从 转移到 ,且容量为 的物品有两件,记为a和b。而对于 ,我们假设它是购买了三个a,两个b。

我们转移到 时,就应该需要知道购买第四个a和第三个b时,二者分别对答案的贡献。购买第k件同一个物品时该物品的贡献为 (做个差分就行了)。这个东西(显然)是单调递减的,因此可以采用贪心策略:

  • 首先我们先算出所有单个容量为 的物品在 时对答案的贡献。
  • 搞个大顶堆,将这些答案以及对应的 放进去。然后开始计算 ,每次从大顶堆取出答案时,根据取出的答案对应的 ,计算出该物品取 的贡献,重新插到堆里。

Code:https://atcoder.jp/contests/abc373/submissions/59299326

总结:本题的突破口在于将传统的背包dp中枚举第几个物品转换为枚举单个物品的容量,同时还要在意到该题购买同一个物品时其对答案的贡献是单调递减的(从数学上来讲,就是 的二阶导为非正,因此你可以在出类似于校内新生赛的时候把这个式子改一改,从而转换成自己的题(不是)),如果不是单调递减的话那么贪心策略就是错的。

graph

misc

games101学习笔记

1. 线性代数

1.1. 线性变换

二维举例

二维线性变换可以写为: \[ x^{'}=ax+by\\ y^{'}=cx+dy\\ \] 可以用矩阵 \(M\) 来表示: \[ \begin{bmatrix} x^{'}\\y^{'} \end{bmatrix}= \begin{bmatrix} a & b\\c & d \end{bmatrix} \begin{bmatrix} x\\y \end{bmatrix} \] 可以带入两个基向量 \((1,0),(0,1)\),得知 \((a,c)\)\((b,d)\) 分别是这两个向量经过线性变换后在原坐标系的坐标值。可以用这个结论很快地得出矩阵 \(M\)

1.2. 齐次坐标(Homogeneous Coordinates)

在线性变换的基础上添加平移变换

线性变换不能表示平移: \[ \begin{bmatrix} x^{'}\\y^{'} \end{bmatrix}= \begin{bmatrix} a & b\\c & d \end{bmatrix} \begin{bmatrix} x\\y \end{bmatrix}+ \begin{bmatrix} t_x\\t_y \end{bmatrix} \] 为了将平移也加入一般的变换形式,提出齐次坐标,即在原有的坐标上添加一维 \(w\)(二维举例):

  • 2D点:\((x, y, 1)^T\)
  • 2D向量:\((x, y, 0)^T\)

这样就可以只用矩阵乘法来表示线性变换+平移(先变换后平移): \[ \begin{bmatrix} x^{'}\\y^{'}\\1 \end{bmatrix}= \begin{bmatrix} a & b & t_x\\c & d & t_y \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x\\y\\1 \end{bmatrix} \] 对于矩阵 \(M\) 求逆可得还原矩阵 \(M^{-1}\)

1.3. 复合变换

由于采用右手坐标系,因此变换为矩阵左乘,变换顺序由右往左: \[ A_n(...A_2(A_1(x))) = A_n\cdots A_2 \cdot A_1 \cdot \begin{pmatrix} x\\y\\1 \end{pmatrix} \]

1.4. 三维变换

三维旋转矩阵(非齐次坐标),绕轴 \(n\)\(\alpha\)\[ R(n,\alpha)=\cos(\alpha)I+(1-\cos(\alpha))nn^T+\sin(\alpha) \begin{pmatrix} 0&-n_z&n_y\\ n_z&0&-n_x\\ -n_y&n_x&0 \end{pmatrix} \]

1.5. 视图变换

MVP变换的V。或者MV。

想象你拿着相机进行拍照,需要哪些步骤

首先设置相机:

  • 选择位置 \(e\)
  • 选择观察方向 \(g\)
  • 选择相机朝上的方向 \(t\)

为了方便,我们将相机移动到原点,观察 \(-z\),上方向为 \(y\)。这可以采用复合变换实现:

  • \(e\) 平移至原点
  • \(g\) 旋转至 \(-z\)
  • \(t\) 旋转至 \(y\)
  • \((g \times t)\) 旋转至 \(x\) (事实上不需要这步,只不过方便后续数学推导表示)

上述变换除了第一步,后面旋转用矩阵难以实现,考虑逆复合变换。

假设矩阵为 \(M_{view}=R_{view}T_{view}\),其中平移矩阵很简单: \[ T_{view} = \begin{bmatrix} 1 & 0 & 0 & -x_e\\ 0 & 1 & 0 & -y_e\\ 0 & 0 & 1 & -z_e\\ 0 & 0 & 0 & 1 \end{bmatrix} \] 对于旋转矩阵,考虑其逆变换:\(x\) 旋转至 \((g \times t)\)\(y\) 旋转至 \(t\)\(z\) 旋转至 \(-g\)\[ R_{view}^{-1} = \begin{bmatrix} x_{g\times t} & x_t & x_{-g} & 0\\ y_{g\times t} & y_t & y_{-g} & 0\\ z_{g\times t} & z_t & z_{-g} & 0\\ 0 & 0 & 0 & 1 \end{bmatrix} \] 不难发现这是个正交矩阵,因此可以直接转置得到 \(R_{view}\)\[ R_{view} = \begin{bmatrix} x_{g\times t} & y_{g\times t} & z_{g\times t} & 0\\ x_t & y_t & z_t & 0\\ x_{-g} & y_{-g} & z_{-g} & 0\\ 0 & 0 & 0 & 1 \end{bmatrix} \]

1.6. 投影变换

MVP中的P,将3D转换为2D

分为正交投影和透视投影

二者区别如下,直接截图了:

1.6.1. 正交投影

一种简单的方式:

  • 首先用视图变换,让相机移动到原点,观察 \(-z\),上方向为 \(y\)
  • 然后去掉 \(z\)
  • 缩放至 \([-1,1]^2\)(讲真我不是很理解这步)

一般方式,在原来的基础上多了个平移变换:

其对应的变换矩阵为: \[ M_{ortho}= \begin{bmatrix} \frac{2}{r-l} & 0 & 0 & 0\\ 0 & \frac{2}{t-b} & 0 & 0\\ 0 & 0 & \frac{2}{n-f} & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & -\frac{r+l}{2}\\ 0 & 1 & 0 & -\frac{t+b}{2}\\ 0 & 0 & 1 & -\frac{n+f}{2}\\ 0 & 0 & 0 & 1\\ \end{bmatrix} \]

1.6.2. 透视投影

远的物体更小,平行线不再不行。

首先将锉面压缩成长方体 \(M_{persp\rightarrow ortho}\),然后可以使用上述正交投影 \(M_{ortho}\)

这里应该假设这个锉面是通过视线形成的,即中心轴为 \(-z\),因此不需要先作平移变换。

主要的idea是上述提到过的“找出向量经过线性变换后在原坐标系的坐标值”。

首先考虑 \(y\) ,这个很简单,根据相似三角形直接求出 \(y^{'}=\frac{n}{z}y\)

将坐标系绕 \(z\) 轴旋转90度,可以发现对于 \(x\) 也一样:\(x^{'}=\frac{n}{z}x\)

根据目前的信息,用齐次坐标表示变换前后的坐标: \[ \begin{pmatrix} x\\y\\z\\1 \end{pmatrix} \Rightarrow \begin{pmatrix} nx/z\\ny/z\\unknown\\1 \end{pmatrix} == \begin{pmatrix} nx\\ny\\unknown\\z \end{pmatrix} \] 考虑根据变换前后,推出矩阵 \(M_{persp\rightarrow ortho}^{4\times 4}\)\[ M_{persp\rightarrow ortho}^{4\times 4} \begin{pmatrix} x\\y\\z\\1 \end{pmatrix}= \begin{pmatrix} nx\\ny\\unknown\\z \end{pmatrix} \] 注意到 \(x,y,z\) 都是变量,矩阵内部不能有这些变量,因此可以直接推出一些元素: \[ M_{persp\rightarrow ortho} = \begin{pmatrix} n & 0 & 0 & 0\\ 0 & n & 0 & 0\\ ? & ? & ? & ?\\ 0 & 0 & 1 & 0 \end{pmatrix} \]

可以发现这个似乎不是仿射变换矩阵的形式(最后一行前面都是0最后一个是1)。因此学到这里的时候,我知道,至少对于 \(z\) ,它的变换肯定不是线性的。

因此我有个疑问,就是明知道变换前后不是线性的,但为什么还能假定可以用矩阵来表示呢?矩阵可以表示齐次坐标的任意变换吗?

如何求出这些未知元素呢?这里我们考虑将坐标的 \(z\) 代入一些特殊值。

首先令 \(z=n\)\[ \begin{pmatrix} x\\y\\n\\1 \end{pmatrix} \Rightarrow \begin{pmatrix} nx\\ny\\n^2\\n \end{pmatrix} \] 可以得出矩阵第三行为: \[ \begin{pmatrix} 0&0&A&B \end{pmatrix} \begin{pmatrix} x\\y\\n\\1 \end{pmatrix} =n^2 \] 且可以得出: \[ An+B=n^2 \] 然后我们需要再来一个方程。我们知道所有在 \(f\) 面(即最后面的那一面)上的 \(z\) 前后是不会变的,因此有 \[ \begin{pmatrix} 0\\0\\f\\1 \end{pmatrix} \Rightarrow \begin{pmatrix} 0\\0\\f^2\\f \end{pmatrix} \] 因此得到第二个方程: \[ Af+B=f^2 \] 可以解得 \[ A=n+f\\B=-nf \] 因此成功求出了 \(M_{persp\rightarrow ortho}\)

对于一般的 \(z\) ,变换前后是变大还是变小了?(换句话说,更近还是更远了呢)

根据上述求解可以得知 \(z^{'}=n+f-\dfrac{nf}{z}\),直接算 \(z-z{'}\),乘 \(z\) 后可以求得 \(z^2-(n+f)z+nf<0\space(f<z<n)\)

但因为 \(z<0\) ,所以 \(z > z^{'}\),变换后的 \(z\) 更小,即更远了。

2. 光栅化

根据上面的MVP变换,我们得到了一个 \([-1,1]^3\) 的正方体。光栅化就是把这个正方体映射到二维屏幕上。

假设我们的屏幕为 \([0,width] \times [0, height]\)。每一个方格代表一个像素,这里假设每个像素都是纯色。

一种可以直接想到的简单方法是,不管 \(z\) 坐标,先变换 \(xy\) 平面,可以直接写出变换矩阵: \[ M_{viewport} = \begin{pmatrix} \frac{width}{2} & 0 & 0 & \frac{width}{2}\\ 0 & \frac{height}{2} & 0 & \frac{height}{2}\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{pmatrix} \]

2.1. 三角形的离散化

为什么选择三角形:

  • 最简单的多边形,可以组合成其它多边形
  • 是2D的
  • 是凸的
  • 方便重心插值

对于像素 \((x, y)\),我们通过采样的方式决定是否填充: \[ inside(t,x,y) = \begin{cases} 1 & (x,y)在三角形t内\\ 0 & otherwise \end{cases} \] 而像素的中心实际上为 \((x+0.5,y+0.5)\),我们只需要判断这个中心是否在三角形内部即可,这可以用叉积实现,判断该点是否都在三个方向一致的边向量的左边/右边。

2.2. 走样、信号与滤波

只通过上述对像素中心进行采样的光栅化方式,会产生锯齿(走样)。

采样在计算机图形学中是个十分常用的概念,但其往往却会产生一系列问题,称之为artifacts:

经典的走样包括锯齿、摩尔纹、车轮效应,前两者是空间上采用的问题,后者是时间上采样的问题。究其本质,是采样的速度跟不上信号变化的速度

傅里叶级数展开:任何周期函数都可以展开为不同频率的正余弦函数的线性组合加上一个常数。

傅里叶(逆)变换:可以将时域信号与频域信号相互转换。

对于低频率的信号,采用低频率的采样方式,我们可以根据采用点重建原信号。

而对于高频率的信号,采用低频率的采样方式,我们可能会错误地重建一个低频率信号。(这事实上就是摩尔纹出现的原理,对原图片进行降采样,可能会得到一个变化较少的纹路)

滤波:删除原信号在某些频率上的内容。

滤掉低频,原图片剩下高频的内容,对应的大概率是边界部分。

滤掉高频,原图片显眼的部分被去除,产生类似于模糊的效果。

卷积这个学过CNN的多少都有点印象,在图形学中也是一样,拿个卷积核在那对每个像素作加权平均。

卷积定理:空间域的卷积等于频域的乘积,反之亦然。

因此在原图片上进行卷积,相当于先用傅里叶变换将图片变为频谱,然后和卷积核的频谱形式进行相乘,最后用傅里叶逆变换变化回来。

值得注意的是,这里的均值滤波器经过傅里叶变换后得到的是一个低通滤波器。

而滤波器尺寸越大,所得到的低通滤波器越集中于低频率。

2.3. 抗锯齿(反走样)

前面提到,我们产生走样的原因是采样频率低于信号频率

用上述信号的原理来解释,可以理解为下图:

这里(a)是我们的采样函数,(c)是我们的采样点(冲激函数),(e)是我们最终采样得到的函数。右边是它们经过傅里叶变换后的频谱形式。

可以看出,对一个函数进行采样,在频率上相当于重复原函数的频谱内容

而走样在频率上,是重复频谱之间的混合交叉:

tip:采样频率越高(冲激函数频率越高),在频谱形式中频率越低,越不容易产生交叉。

所以我们想要反走样,可以从两步考虑:

  • 提升采样频率,这毫无意义
  • 降低采样函数频率(这样会让函数在频谱上显得更"窄")

上面也提到了,降低频率相当于在空间域上使用滤波,因此这里的抗锯齿方案是:

对进行光栅化的三角形提前模糊,然后再采样。

具体实现是针对每个像素而言的(相当于1x1滤波器),本质为二值平均。

当然要计算三角形在每个像素中覆盖的比例是件很耗性能的工作,因此有了一种近似的模糊方法MSAA。

2.3.1. MSAA 超采样

原理很简单,对每个像素,不再是只对中心进行采样,而是取若干坐标,进行混合平均。

事实上MSAA在拟合模糊的时候已经把采样也给做了,因此就省了一个步骤。

MSAA的问题也很明显,就是超采样方式带来的性能损耗。因此还有其它的方式,例如FXAA、TAA以及你最喜欢的DLSS。

2.4. 深度测试

如果我们要光栅化多个三角形,那么就需要使用各三角形的深度信息。

为了方便,我们与上面光栅化的步骤不同,这里的深度(即 \(z\) 坐标)采用正值。

2.4.1. Z-Buffer

关键idea是以像素为单位进行考虑。

算法思想很简单,对于同一个像素,如果被多个三角形给覆盖,取深度值最低的那个。

在实现的过程中,我们维护两个 buffer :一个是最终的结果,一个是深度图:

伪代码如下:

1
2
3
4
5
6
7
for(each triangle T)
for(each sample (x, y, z) in T)
if(z < zbuffer[x][y])
framebuffer[x, y] = rgb;
zbuffer[x][y] = z;
else
;

假设每个三角形占用的像素数量是常数,那么该算法是 \(O(n)\) 的。

Tip:深度测试不适用于透明物体。

2.5. 光栅化的阴影

算法:Shadow Mapping

Idea:对于没有被阴影的点,它应该同时被相机和点光源照到。

因此我们可以考虑对点光源设置深度图。然后考虑相机看到的点,将其映射到点光源的深度图上,对比深度值是否与深度图记录上的一致。

这种方法产生的阴影会有走样。阴影质量取决于shadow map分辨率。

对于点光源,其生成的阴影是硬阴影(hard shadow),因为阴影里的任何地方都接触不到光。

然而对于有体积的光源,则会有软阴影部分(soft shadow)

3. 着色

着色的定义:对物品施加材质

3.1. Blinn-Phong反射模型

该模型将光照分为三个部分:镜面高光、漫反射、环境光(间接光照)

3.1.1. 着色是局部行为

对于着色这一步,我们只考虑在一个点上的操作(称之为着色点)。

对于一个着色点,我们可以有以下输入:

  • 观察者视角 \(v\)
  • 着色表面(近似为平面)法向量 \(n\)
  • 光照方向 \(l\) (对每个光都有一个)
  • 表面参数(颜色、光泽度(与光照无关)等)

着色是局部的,代表某个着色点不受外部环境影响,因此着色并不产生阴影。(shading \(\neq\) shadow)

3.1.2. 漫反射

漫反射的性质是,光照经过一个表面后向各个方向均匀散射。

因此在任意视角观察同一个着色点,产生的结果是相同的。

我们首先明确,在给定上述的输入后,我们要的输出是漫反射光。具体而言应该是RGB形式的三维向量。

首先上面提到,我们的输出和观察方向无关。

其次,对于光照的方向,有 Lambert 余弦定理,即光照强度与光照和法线的夹角的余弦值成正比

再者,我们考虑到物体离光源越远,所吸收的能量会越少。(这里应该是指点光源)

根据能量守恒定律,以光源为中心的任何半径 \(r\) 形成的球面所拥有的能量是恒定的。假设 \(r=1\) 时能量为 \(I\),那么对于任意的 \(r\) ,能量为 \(\frac{I}{r^2}\)

最后我们得到的输出也与着色点本身有关,假设着色点本身的颜色会产生一个向量 \(k_d\),那么得到的漫反射光为: \[ L_d=k_d(I/r^2)\max(0, n\cdot l) \]

3.1.3. 镜面反射

镜面反射的强度与漫反射不同,它将与我们的观察视角有关。

根据实际经验来讲,如果观察视角和反射光很接近,那么就能看到镜面反射的高光,如下图:

事实上对于朴素的Phong反射模型,它确实采用了 \(v\) 和反射方向 \(R\) 之间的夹角作为参数。但事实上这个 \(R\) 是比较难算的,所以Blinn-Phong模型采取了一些简化措施:

诶🤓👆,这里模型先计算入射方向和视角的半程向量(俗称角平分线)\(h\),然后用 \(h\) 和法向量 \(n\) 之间的夹角来代替 \(v\)\(R\) 之间的角(实际上是大小为一半的关系)。

至于夹角项上的指数 \(p\) ,是为了控制高光更加集中。

可见,对于相同的角,如果指数 \(p\) 越高,其所得到的强度越低。

对于常项 \(k_s\),一般指定高光为白光,所以应该是个很大的值。

另外这里模型进行了简化,略掉了漫反射中光照方向和法向量夹角的一项。

3.1.4. 环境光

非常简单,这里Blinn-Phong做了简化:环境光照强度为常数 \(I_a\)

主要的作用是保证任何地方都能有光照,即都不是黑的。(下图是环境光+漫反射+镜面反射=BP反射)

3.2. 着色频率

对于同一个模型,我们可以以不同的单位进行着色(例如三角形平面、三角形顶点、像素等),这就是着色频率。

显然着色频率影响最终效果质量,但其也与性能有关。

  • Flat shading:即以三角形为单位进行着色,同一个三角形上的颜色是一样的。
  • Gouraud shading:以顶点为单位进行着色(至于顶点的法向量后面会说),顶点内部三角形用插值着色。
  • Phone shading:以像素为单位进行着色(与Blinn-Phone反射模型无关),像素的法向量用插值算出来。

对于三角形顶点的法向量,可以对顶点周围的所有三角形的法向量求平均: \[ N_v=\dfrac{\sum_i N_i}{\|\sum_i N_i\|} \] 对于像素的法向量,采用重心插值法(后面介绍)。

3.3. 图形管线(实时渲染管线)

我觉得管线就是流水线(pipeline),或者说步骤,不知道谁发明的这个说法,很别扭

我们现在掌握了光栅化和部分着色的知识,现在总结一下如何将一个3D物体渲染到屏幕上:

  1. 首先,我们的输入是三维空间的点(当然还有点之间维护的三角形的关系)
  2. 然后我们开始顶点处理(Vertex Processing):采用MVP变换,将摄像机移植原点,上方向旋转至 \(y\) 轴,视角朝向 \(-z\)。然后将整个点变换至 \([-1,1]^3\)的正方体上。(我没理解错的话)
  3. 然后进行三角形处理(Triangle Processing):没啥好处理的,点的变换并不影响其联通关系。
  4. 然后进行光栅化(Rasterization):将三维压到二维屏幕空间。
  5. 然后进行片段处理(Fragment Processing):可以理解为对每个像素进行处理(反走样、深度测试、着色等),当然这里的Fragment并不一定指像素,对于MSAA它可能会指超采样点。
  6. 然后进行Framebuffer Operations,这里我还不知道这是什么东西,课件也没说。
  7. 最后就可以渲染到屏幕上了。

对于图形管线的具体内容参见课件。注意对于某个特定的步骤,例如着色的时候,它的操作可能是对每个像素进行着色(片段处理),但是在着色的过程中我们事实上需要运用到点的三维信息,因此它可能也包含了图形管线的顶点处理。后面的Texture Mapping也是一样。

对于现代gpu,其内部高度并行化(非常多的core,想象一下可以并行地对不同像素进行渲染),且大部分都实现了特定的一套图形管线。当然内部有用户可定义的部分(可编程的部分),其中有一个叫做shader。

3.3.1. shader

shader指的是一段特定编程语言的程序,专门关注对一个顶点(或者片段)的着色操作。

https://www.shadertoy.com/view/ld3Gz2

3.4. 纹理映射(Texture Mapping)

我们之前可能会关注到Blinn-Phong反射模型中漫反射项的 \(k_d\)。我理解为它包含了着色点的颜色信息,而这个颜色信息是需要通过纹理映射得到的。

首先我们需要确认一个观点,就是任意的三维物体都可以展开成一个二维的矩形(俗称uv变换):

那个展示的图太掉san了,自己去看课件(

主要的思想是,三维空间中的顶点与二维展开后的纹理有一一对应关系。

具体如何转换的不在本课程讨论范围内

3.5. 重心坐标法

通过三角形三个顶点的属性,对内部任意点的属性进行插值。

我们可以插值得到的属性有:纹理坐标、颜色、法向量等。

重心坐标:以三个顶点的坐标为基准进行线性组合,所得到的系数即重心坐标。

注意三个系数之和为1,且非负。

可以通过计算三个点的对顶三角形的面积比来得到系数:

这里的重心坐标对于3D的三角形和光栅化后的2D三角形并不是不变的。对于同一个点,变换前后的重心坐标可能有变,这表明对于一些三维的属性(例如作业二对深度的插值),我们需要将二维的点进行逆变换后得到的三维点在三维三角形的情况下计算它的重心坐标,然后进行插值。

具体的插值方式是用系数进行属性的线性组合:

\[ V = \alpha V_A + \beta V_B + \gamma V_C \]

因此我们可以通过重心坐标对每个像素中心插值出它在纹理上的坐标。

对于纹理,它也是一个由许多像素构成的二维图像,不是连续的东西。因此我们假设它是一堆离散的整型坐标形成的二维空间。

如果得到的纹理坐标不是整数,我们这里朴素的将其round到最近的纹理像素区域,并根据该像素设置渲染的像素的颜色(漫反射项的 \(K_d\)),但事实上这么做会有问题。

3.6. 纹理过小

解释一下过小是什么意思,我们知道纹理也是一张图片,也有属于自己的像素,这里叫做texel(纹理元素)。

我对于纹理过小的理解是,纹理相比于屏幕的分辨率过小,因此用上述朴素方法(对重心坐标插值纹理坐标然后round)进行采色的时候会出现一片区域都映射到同一个texel的情况,这时候会导致渲染效果很差:

Nearest情况

为了不造成同一片像素映射到同一个texel的情况,我们采用双线性插值,即考虑最近的4个texel,然后根据这4个texel的颜色与纹理坐标位置之间的关系进行插值,具体实现很简单:

双线性插值=三次单线性插值

3.7. 纹理过大

纹理过小指的是多个屏幕像素映射到单个texel,那么纹理过大就是单个屏幕像素包含多个texel(或者反过来说,多个texel对应单个pixel)

会有什么情况呢?

这里我们观察到了之前光栅化一样的走样问题。

我们之前反走样采取的措施是MSAA,即针对一个屏幕像素设置多个超采样点,来解决“采样速度跟不上信号变化速度”的问题。

这里我们照样可以这么干,对于一个屏幕像素,设置512个超采样点,都映射到texel上,求平均,可得到较好的效果:

但是超采样的想法特别耗性能。

从信号的角度上进行分析,由于我们采样的速度需要与信号变化速度一致,因此不可避免地会需要提高采样频率。因此我们直接放弃采样的想法,使用ACM大法!

我们所要解决的就是这种“范围查询”的问题,将一定范围内的texel进行求平均。

对于纹理过小采用的双线性插值,事实上是一种点查询问题。

3.8. mipmap

这里提出了level的概念,每一个level是上一个level的1/4。

首先我们要清楚,mipmap的输入必须是一个正方形,因此对于一个屏幕像素,我们需要用某些方式求出其对应在纹理上的正方形。

开始可以先找周围像素中心的映射点:

然后用一种很神秘的方式得到正方形边长 \(L\)

假设我们得到的边长 \(L=4\),那么我们可以在 \(level=\log4=2\) 的mipmap上进行采样。(Round to the nearest level)

由于可能会有边长对齐问题,这里同样可以使用双线性插值得到最终结果。

但是考虑到 \(L\) 大概率不是2的幂,即深度可能是小数,因此可以采用三线性插值,在深度上再来一次线性插值:

这里你可能会觉得,这个方法在很多地方用了近似。首先是三线性插值本身就是种近似(感觉线性方法效果都不是很好?),其次是我们这里的输入限制了为与坐标轴平行的正方形,这可能和像素实际覆盖的范围的形状有很大出入。

实际上确实,对于上面的一个例子,采用朴素的mipmap和三线性插值得到的效果:

可以发现有很明显的模糊,这就是因为形状之间的出入:

一种缓解这种形状出入的方式是用长方形来代替正方形,这个叫各向异性过滤(Anisotropic Filtering)

当然还有种更好的方法叫EWA filtering,可以去课件了解一下。

3.9. 纹理映射的其它应用

纹理不一定只映射颜色

一种应用是让纹理包含深度信息:

这种深度信息让渲染出来的物体具有凹凸不平的视觉视角。然而它只是一种欺骗视觉的手段,几何形体本身还是没变。

具体欺骗视觉的方式是修改了每个渲染点的法向量

就是将原本的 \(p\) 转换为 \(n\)。至于为什么通过改变法向量就能有凹凸不平的效果,首先肯定和阴影无关(着色是局部行为)。我认为单纯就是它改变了Blinn-Phone模型中法向量和光线与视觉的角度,影响了亮不亮而已。

这个是2D情况,我们重点看看3D:

4. 几何

4.1. 表示

隐式(Implicit)表示:用方程 \(f(x,y,z)=0\) 来表示一个几何形体。

可以通过对方程代入点坐标来判断点是否在几何体内。

显示表示:直接给出点的形式(可能通过参数映射)

二者在不同的任务上各有优劣。

4.2. 曲线和曲面

这里主要介绍贝塞尔曲线和曲面。

对于 \(n\) 阶贝塞尔曲线,它由 \(n+1\) 个控制点决定。通过对这 \(n+1\) 个控制点从前往后每两个做时间维度 \(t\) 上的线性插值,可得到 \(n\) 个插值出来的点。然后递归进行这个过程,直到剩下一个点,那么这个点就是在时间 \(t\) 上贝塞尔曲线的位置。\(t \in [0,1]\)

如果用代数形式推导时间 \(t\) 时贝塞尔曲线的坐标,可以发现其等于 \(n+1\) 控制点的线性组合,其权重为伯恩斯坦多项式(Bernstein polynomial),和为1.

具体而言,可以写成: \[ b(t) = \sum_{i=0}^nC_n^i t^i(1-t)^{n-i} \mathbf{b}_i. \] 关于贝塞尔曲线,有以下性质:

  • 两个端点为首尾控制点。

  • 求两个端点的切线,相当于对上式求导: \[ b^{'}(t) = \sum_{i=0}^nC_n^i (it^{i-1}(1-t)^{n-i}-t^i(n-i)(1-t)^{n-i-1}) \mathbf{b}_i. \] 可得到 \(b^{'}(0) = n(\mathbf{b}_1-\mathbf{b}_0), b^{'}(n) = n(\mathbf{b}_n-\mathbf{b}_{n-1})\)

  • 仿射不变性:显然,对所有控制点作相同的平移,不改变贝塞尔曲线的形状。

  • 贝塞尔曲线被包含在控制点形成的凸包内。

实际应用中,一般会采用三阶贝塞尔曲线,并将其拼接(钢笔工具):

如果首尾相连,则定义为 \(C^0\) 连续。

如果首尾之间一阶导相同,则为 \(C^1\) 连续:

首先需要保证两条切线方向相同,其次保证长度相同。

贝塞尔曲面:一般采用16个控制点

输入二维信息 \((u,v)\),首先在一维上对 \(u\) 做4次贝塞尔曲线对时间 \(u\) 的计算,在得到的额外4个点的基础上计算时间 \(v\) 的坐标,得到输出。

4.3. 网格细分

这里首先介绍Loop subdivision,只适用于三角形网格

首先是分出更多的三角形,其次移动三角形顶点的位置。

分出三角形:取各边中点相连。

更新顶点位置,分为新的顶点和旧的顶点:

然后介绍Catmull-Clark Subdivision,适用于各种网格

每次细分,对每个网格中心添加点,再对每条边添加中点,相邻的新点进行相连。

经过一次细分,便只剩下了四边形网格。而奇异点的数量等于初始奇异点的数量加上初始非四边形网格的数量。

而顶点位置的更新较为复杂:

4.4. 网格简化

初始idea:通过坍缩一条边,可以减少一个网格:

因此我们需要有一个方法可以得知一条边值不值得被探索。这里采用二次误差度量的方法:我们希望将一条边坍缩后得到的新点的位置与坍缩之前对应的边的距离的平方和最小:

对于二次误差最小的边,我们优先坍缩。

5. 光线追踪

5.1. 基础

关于光线的三个idea:

  • 光线沿直线传播
  • 不同光线之间不会碰撞
  • 光线从光源传播到眼睛(这个过程可以逆向)

个人理解:光追尝试追踪从光源射到眼睛的路径,然而这样的路径本身可能非常复杂,而且不止一条(对于每个像素(终点),每个光源(起点)都有对应的路径)。因此光追则从相机(终点)出发,尽可能恢复光线路径。

这里介绍的是Whitted风格的光线追踪,它本身是一种递归算法:

5.2. 光线—平面相交

光线可以用 \(r(t) = o+td(t \ge 0)\) 来表示。

对于一般的隐式平面 \(p: f(p)=0\),将二者联立得到 \(f(o+td)=0\)

我们需要解出这个方程的正实数根。

其次是研究光线和三角形的交点。首先我们可以先尝试求出光线和三角形所在平面的交点(如果这都没有交点,和三角形本身更不可能有交点)。

对于一个三维平面,可以使用点法式表示:\(p: (p-p^{'})\cdot N=0\),代入 \(p=r(t)\) 可直接求出 \(t = \dfrac{(p^{'}-o)\cdot N}{d \cdot N}\) ($ t $)。然后检测对应的点是否在三角形内部即可。

当然有一个更简单的算法:

5.3. 加速结构

上面的算法贼慢,我们需要优化。

这里我们假设一个说法:对于三角形(或者说object)求交是慢的,而对于平面求交是快的。

因此就有了轴对齐包围盒的概念:

包围盒对每条轴都有两个相互平行的平面,对于这两个平面我们能求出相交的两个 \(t\),由大小分为 \(t_{\max}, t_{\min}\)

对三个轴对应的 \(t_{\max}, t_{\min}\) 形成的区间进行求交,即 \(t_{enter} = \max\{t_{\min}\}, t_{exit} = \min\{t_{\max}\}\)。如果光线与包围盒有交,则当且仅当

  • \(t_{enter} < t_{exit}\)
  • \(t_{exit} \ge 0\)

5.3.1. 空间划分

可以用树的结构进行:

KDTree用的最多。

对于KDTree结构,有:

  • 空间划分需要按照x,y,z轴方向划分(这样好算)
  • 中间节点存子节点指针
  • 只有叶子节点存物体信息

对于光线与包围盒的求交,本质是递归遍历KDTree的过程。但是这么做会有一个问题,就是同一个物体可能会出现在不同的叶子节点中。因此有一个更好的方法BVH。

KDTree方式是直接考虑整体空间的划分,而BVH则考虑了物体本身在空间的分布。

这样可以保证每个三角形只会对应一个叶子节点,但是包围盒之间可能存在交集(然而老师说这个没什么关系)

对于一个包围盒如何划分成两个子包围盒,很有讲究,一般有以下两个idea:

  • 优先选择轴最长的方向划分
  • 按照轴方向,取median的点作为划分点

5.4. 辐射度量学

辐射度量学是一种以物理层面让光线追踪渲染出来的结果更加真实的东西。首先需要知道一些概念:

  • Radiant energy:顾名思义,是一种度量电磁能量的物理量 \(Q[J=Joule]\)
  • Radiant flux(power):单位时间的能量 \(\Phi = \dfrac{dQ}{dt}[W=Watt][lm=lumen]\)
  • Radiant Intensity:单位立体角的Radiant flux \(I(\omega) = \dfrac{d\Phi}{d\omega}\)

立体角:空间的物体往单位球连线所形成的立体角度

  • Irradiance:单位面积的Radiant flux \(E(x)=\dfrac{d\Phi}{dA}\)

这里指的单位面积应当是垂直于光线方向的单位面积,在Blinn-Phone模型计算漫反射项的时候提到过类似的东西:

对于Blinn-Phone模型,我们之前提到过能量损失,这个实际上是irradiance的损失:

  • Radiance:单位立体角、单位面积的radiant flux:

两种角度看待radiance:

  • 单位立体角的irradiance
  • 单位面积的intensity

irradiance是不同方向对应的radiance的积分:\(E(p) = \int_{H^2}L_i(p,\omega)\cos \theta d\omega\)

个人理解:每个方向对应一个单位立体角,因此对方向积分相当于对单位立体角积分。

接下来我们考虑reflection。从方向 \(\omega_i\) 照射到照射点(这个点是个单位面积)会让该点的irradiance增加其对应的radiance(乘上余弦???):\(dE(\omega_i) = L(\omega_i)\cos \theta_i d\omega_i\)

对于反射后的能量散步,我们需要一个函数来描述,即BRDF\[ f_r(\omega_i \rightarrow \omega_r) = \dfrac{d L_r(\omega_r)}{d E_i(\omega_i)} = \dfrac{d L_r(\omega_r)}{L_i(\omega_i)\cos \theta_i d\omega_i} \] 它的含义是指出射方向 \(\omega_r\) 对应的radiance占入射方向 \(\omega_i\) 对应的增加的irradiance的占比。如果对一个反射点定义了对应的BRDF,则可以写出对应的反射方程\[ L_r(p, \omega_r) = \int_{H^2} f_r(p, \omega_i \rightarrow \omega_r) L_i(\omega_i)\cos\theta_i d\omega_i. \] 即对于所有的入射方向对应的微小irradiance增加量乘上BRDF后的东西进行积分。

我们发现方程两边都有radiance,因此求反射方程本质上是递归的。

当然有些物体本身就是会发光的,加上这一项可以得到渲染方程\[ L_o(p, \omega_o) = L_e(p, \omega_o) + \int_{\Omega^+} f_r(p, \omega_i \rightarrow \omega_o) L_i(p, \omega_i)(n \cdot \omega_i) d\omega_i. \] 接下来细致地了解一下渲染方程。首先假设只有一个点光源,则渲染方程只有一个项:

如果有多个点光源,求和即可:

如果有面光源,则可以将其微分成点光源,然后积分,也就是上面我们的形式:

注意这里的 \(L_r\)\(L_i\) 分别对应反射出去和照入进来的radiance,它们是不一样的,因为 \(L_i\) 包含了光源本身和其它被反射的光。

因此将 \(L_i\) 分解,让积分内部只有 \(L_r\) 相关项,光源本身放到外面。可以得到较为一致的形式:

后面开始玄学了。可以进一步简化上面式子:\(l(u)=e(u)+\int l(v) K(u,v)dv\)

然后进一步玄学,写成算子形式并推导:

考虑最后一行式子对应的意义,其 \(E+KE\) 其实是我们光栅化覆盖到的东西,而后面则是全局光照对应的东西。

5.5. 蒙特卡罗积分

Monte Carlo积分是一种基于随机化的求定积分的方式。

假设我们要求下面这么一个积分: \[ \int_a^b f(x) dx \] 可以用蒙特卡罗近似: \[ F_N = \dfrac{1}{N}\sum_{i=1}^N \dfrac{f(X_i)}{p(X_i)}, X_i \sim p(x). \]

5.6. 路径追踪(Path Tracing)

前面介绍的Whitted-Style ray tracing在物理层面上是解释不通的,因此我们需要一个符合一般物理规律的光线追踪方式。路径追踪就是一种基于上述提到的渲染方程的符合物理规律的光线追踪方式。

我们重新看一下渲染方程: \[ L_o(p, \omega_o) = L_e(p, \omega_o) + \int_{\Omega^+}L_i(p, \omega_i)f_r(p, \omega_i, \omega_o)(n\cdot \omega_i) d\omega_i. \] 它涉及到:

  • 对半球积分
  • 递归求解

考虑套用Monte Carlo,我们假设对半球进行等概率采样,那么有: \[ \begin{aligned} L_o(p, \omega_o) &= \int_{\Omega^+}L_i(p, \omega_i)f_r(p, \omega_i, \omega_o)(n\cdot \omega_i) d\omega_i\\ &\approx \dfrac{1}{N}\sum_{i=1}^N\dfrac{L_i(p, \omega_i)f_r(p, \omega_i, \omega_o)(n\cdot \omega_i)}{p(\omega_i)}. \end{aligned} \] 假设我们的 \(\omega_i\) 是由光源产生,那么可以终止递归。如果是碰撞到另一个物体,那么递归下去:

1
2
3
4
5
6
7
8
9
10
11
auto shade(p, wo):
Randomly choose N directions wi~pdf
Lo = 0.0
For each wi
Trace a ray r(p, wi)
If ray r hit the light
Lo += (1 / N) * L_i * f_r * cosine / pdf(wi)
Else If ray r hit an object at q
Lo += (1 / N) * shade(q, -wi) * f_r * cosine
/ pdf(wi)
Return Lo

这么做肯定有很多问题,首先就是爆栈:

当前仅当当 \(N=1\) 的时候,递归不会爆炸。(这就是路径追踪,因为只有一条路径)

但这相当于用一个点的函数值来整体近似积分,是非常noisy的。因此我们可以考虑对每个像素点进行随机,通过对像素点发出不同的光线,然后进行平均:

还有一种情况,就是有可能一条路径会对物体产生无数次碰撞,导致递归不会停止。因此我们需要一个递归停止的条件。

课程给出的解决方法是一种类似于俄罗斯轮盘赌的idea,我用一句话概括,就是用概率的方法来判断是否递归停止。

以前的方法,我们希望函数 shade 总是能返回radiance。

而现在,我们考虑有概率 \(p\) 可以返回radiance,而概率 \(1-p\) 停止递归(即返回0)。

和之前在学dl时遇到的dropout类似,我们发现,由于0的存在会导致最后期望的radiance会降低。因此我们需要对有值的radiance除以比例 \(p\) 来使总期望的radiance不变:

伪代码如下:

现在我们已经有了一个较为正确的路径追踪算法,但是它依然有点问题。因为我们mento carlo的 \(N=1\),所以当光源比较小的时候,我们可能对某个像素发出的路径,都不会追踪到该光源。然而根据现实情况,光源肯定是要照到物体的,因此我们考虑再做一次 \(N=1\) 的mento carlo,它只在光源的方向上进行随机取样。

我们知道,对于面光源,它对于某个点形成的单位球存在对应的立体角。因此我们考虑用微小面积来换元渲染方程的微小立体角:

因此对于光源的渲染方程可以写为:

还有一个小问题,在处理面光源的贡献时,我们还得需要判断当前采样的方向是否能够接触到面光源(不被其它物体遮挡)。判断该项之后,路径追踪算法就算大致完成了!

6. 材质

Material == BRDF

6.1. 漫反射、镜面反射、折射材质

查缺补漏,重点整理

引用

这里先只谈左值引用。引用和被引用变量是一回事,个人认为实质上是二者所代表的变量地址相同

函数返回值是引用

例如:

1
2
3
4
5
6
7
8
#include<iostream>
int n;
int &fuck(){return n;}
int main(){
fuck() = 2;
std::cout << n; // 2
return 0;
}

可以将函数调用作为赋值对象。

常引用

指的是 const int &,不能通过常引用去修改其引用的变量。

不能将常引用初始化给非常引用:

1
2
3
const int &p = n;
int &q = p;
// compile error

函数重载

这里重载的定义是:函数名相同,函数参数个数或参数类型不同。

因此,函数参数列表相同但返回值类型不同,是不允许重载的。

如果在类里,还可以通过分别定义非常量成员函数和常量成员函数(函数定义后面加 const )来重载。

例:

1
2
3
int fuck(int n){return n;}
long long fuck(int m){return 1ll * m * m;}
// 1.cpp:4:11: error: ambiguating new declaration of 'long long int fuck(int)'

函数缺省参数

指的是可以给函数参数列表后面几个连续的参数默认值。

1
int fuck(int n, int m = 0){return n + m;}

这里主要理解缺省参数存在的意义,它主要是为了优化程序的可扩充性。在初步进行需求开发时,可能对于一个接口的功能并没有完善的规划。到后期有了更完善的需求,可能会在同一个接口上扩充功能。这时可以在该接口(这里指函数)后面添加缺省参数,通过这个缺省参数来在扩充功能的同时,保证原程序中无需扩充功能的函数调用不需要修改调用形式(即一个一个在函数尾部添加参数)。

然后提醒一下,对于重载+缺省产生的二义性:

1
2
int fuck(int n = 1){return n * 2;}
int fuck(){return 1;}

当使用 fuck() 调用时,产生的二义性会让编译器产生错误。

私有成员

这里主要提醒一件事情,就是对于 private 修饰的成员,只能在成员函数内部访问。但是成员函数内部可以访问自己以及其它相同类的私有成员:

1
2
3
4
5
6
7
8
class fuck{
private:
int shit;
void printshit(fuck *a){
std::cout << shit + a->shit << std::endl;
}
};
// ok

复制构造函数

指的是形如 T (T &)T (const T &) 这样的用另一个对象的引用来初始化该对象的构造函数。如果不自己定义,会自动生成一个默认的复制构造函数。

新增tip:对于封闭类,编译器为其生成默认的复制构造函数时,会按照先调用其成员对象的复制构造函数的规则生成,而不是无参构造函数。

复制构造函数在三种情况下起作用:

  • 用一个对象去初始化另一个对象:Complex c2(c1);Complex c2 = c1; //初始化,不是赋值
  • 一个函数中有一个参数是类A的对象,调用该函数时,类A的复制构造函数会被调用。
  • 函数的返回值是类A的对象,则函数返回时会被调用,将返回值赋值给临时对象(注意)。

当然,像g++这种编译器可能会进行优化,可能不会生成临时对象,就少了中间的临时对象的复制构造函数和析构函数的调用(不愧是g++,主打一个激进)。而msvc这种就会按照C++的规定来编译。

类型转换构造函数

之前没听说过

指的是只有一个参数的构造函数。

这样无论是使用 = 进行赋值还是初始化,可以进行自动类型转换。具体看例子吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
class Complex{
public:
double real, imag;
Complex(int i){ // 类型转换构造函数
std::cout << "IntConstructor called" << std::endl;
real = i; imag = 0;
}
Complex(double r, double i){
real = r;
imag = i;
std::cout << "CommonConstructor called" << std::endl;
}
};
int main(){
Complex c1(7, 8);
Complex c2 = 12;
c1 = 9; // 9被转换成一个临时Complex对象,然后赋值给c1,在前面转换的过程中会调用类型转换构造函数
std::cout << c1.real << "," << c1.imag << std::endl;
return 0;
}

静态成员

对于类的静态变量,需要在定义类的文件中对其进行一次说明或初始化,否则会发生链接错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
class Complex{
public:
double real, imag;
static int total_number;
Complex(int i){ // 类型转换构造函数
std::cout << "IntConstructor called" << std::endl;
real = i; imag = 0;
}
Complex(double r, double i){
real = r;
imag = i;
std::cout << "CommonConstructor called" << std::endl;
}
~Complex(){
std::cout << "Destructor called" << std::endl;
}
};
Complex fun(Complex tmp){
return tmp;
}
int Complex::total_number = 0; // 初始化
int main(){
std::cout << Complex::total_number;
return 0;
}

思考:如何维护这个total_number呢?应该在怎么样的构造函数和析构函数来实时维护该变量?

封闭类构造函数/析构函数

封闭类:含有成员对象的类

封闭类对象生成时,先执行所有对象成员的构造函数(按照类中的说明次序,与初始化列表顺序无关),然后执行封闭类的构造函数。

封闭类对象消亡时,先执行封闭类对象的析构函数,再执行成员对象的析构函数(按照构造函数调用的反序)。

重载自增自减运算符

Tip:C++约定俗成的规则,就是前置形式的 ++c 返回的是对象 c 的引用,c++ 返回的是新的对象。

因此可以这么写 (++c)=1 。重载的时候注意返回值类型。

可以注意到前置的自增自减运算符效率更高,因为后置的情况会导致对象的拷贝。这也是为什么我喜欢在acm中写for循环喜欢写 for(int i = 0; i < n; ++i) ,当然对于内置整形变量其实无所谓了,更看个人风格。

protected

派生类可以访问的是当前对象的基类对象的protected成员,而不能访问非当前对象的protected成员。

多态

主要有两种表现方式:基类指针指向派生类对象、基类引用派生类对象

Tip:在类的成员函数(非构造、非析构)中调用虚函数,等价于 this 指针调用虚函数,表现为多态。而如果是构造函数和析构函数就不是多态(想想也是嘛,多态函数得等对象初始化完才能用)。

Tip2:派生类中和基类的虚函数同名同参数表的函数可以不加 virtual

Tip3:析构函数建议使用 virtual ,构造函数不能是虚函数。

模板

模板的实例化

指的是将具体的类型替换模板函数里的类型

可以不通过参数实例化函数模板:

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
using namespace std;
template <class T>
T Inc(T n){
return n+1;
}
int main(){
cout << Inc<double>(4)/2; //强制用double替换
return 0;
}
// 2.5

函数模板和次序

在有多个函数和函数模板名字相同的情况下,编译器如下处理一条函数调用语句:

  1. 先找参数完全匹配的普通函数
  2. 再找参数完全匹配的模板函数
  3. 再找实参经过自动类型转换后能够匹配的普通函数(注意)。
  4. 报错

因此下面这个程序会编译错误:

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
template <class T>
void f1(T n, T m){
cout << "fuck\n";
}
int main(){
f1(1.1, 2);
return 0;
}

编译器不会把 f1 的第二个参数 2 自动转换为 double 类型。不能使用自动类型转换后的模板函数,个人认为这是为了防止二义性。

类模板

类模板的"<类型参数表>"中可以出现非类型参数:template <class T, int size>

类模板初始化静态成员

对于相同的类模板实例化出来的不同的模板类,对应的 static 成员不一样,但是都要初始化:

1
2
template<> int A<int>::count = 0;
template<> int A<double>::count = 0;

STL

STL中“相等”的概念

有时,“x和y相等”等价于“x==y为真”:

例,在未排序的区间上进行的算法,例如顺序查找 find

但有时,"x和y相等"等价于"x小于y和y小于x同时为假"

例:有序区间算法,如binary_search ,或关联容器自身的成员函数 find

这玩意有点抽象,遇到坑的时候再补充吧


以上是暑假找某些面向对象的C++教程瞎学的

接下来是这学期重新从头学的笔记~

常量

常量分为编译时常量和运行时常量

关键字 constexpr 用于定义一个编译时常量,编译时常量的值需要在编译期就被确定,以方便被编译器优化。

只能使用 const expression 来初始化 constexpr ,这也是 constexpr 的命名来源,初始化所用表达式的值可以通过编译期就被确定。

另外地,使用 const 修饰的非整型常量只能是运行时常量,即便是用常量表达式来初始化(具体原因待解),可以通过 constexpr 来显式定义非整型编译时常量。

constexpr 函数

为了让函数调用能够出现在常量表达式中,可以采用对函数返回值进行 constexpr 修饰,来说明该函数返回值可以在编译期求出。

对于 constexpr 函数,需要满足以下条件:

  • 函数调用时传进去的参数必须也在编译器中求出
  • 函数内部的语句以及表达式都可以在编译器中求出

当然这不代表 constexpr 函数的任何调用处都得在编译期求出,它在运行时表达式中和非 constexpr 函数表现一致。

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

constexpr int getValue(int x)
{
return x;
}

int main()
{
int x { getValue(5) }; // may evaluate at runtime or compile-time

return 0;
}

由于 x 是变量,虽然初始化表达式是 constexpr ,但是是否用编译期常量优化由编译器实现而定。

内联 inline

早期 inline 关键字修饰的函数为内联函数,主要用于将函数体在调用处进行展开,减少调用时产生的额外开销。

然而现代编译器有足够能力判断一个函数调用是否用函数展开来替代会提升整体性能(毕竟太多次函数展开会增大可执行文件体积,导致负优化),因此 inline 在现代C++编译器中主要的用途是告诉编译器该函数可以有重复定义(ODR-exemption)。

inline 修饰的函数必须满足:

  • 每个翻译单元中调用处在编译时能够确定函数内容(即在当前cpp源文件中该函数被定义过,如果只有前向定义会报编译错误)
  • 所有同名的 inline 函数是一样的,否则UB(因为链接的时候链接器会去除重复的inline 函数定义,选择其中一个。具体选择哪个,不知道)。

inline 函数经常定义在header-only libraries中(不包括 .cpp 文件的库,这种库不需要提前设置默认链接路径,因为根本就没东西被链接,只需要 #include 就行了)

C++17 标准定义了 inline 修饰的变量,具体用途和内联函数差不多。至于它和全局变量之间的优劣比较,待解。

constexpr函数是隐含的内联函数

因为编译是对于单个文件而言的,因此在编译期间,内联函数需要进行函数展开时,我们需要函数的定义。

对于constexpr函数,在 const expression 环境下,同样需要其定义,以便知道其编译期的值。(需要注意,声明一个constexpr函数只是代表它可以出现在常量表达式中,但不代表它将在编译期中求得值,某些运行时表达式也可使用constexpr函数)

因此很多constexpr函数也定义在头文件中。

constexpr变量并非内联变量,需要显式加inline。

constexpr只是多了一个可以用于常量表达式的功能

具体如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

constexpr int greater(int x, int y)
{
return (x > y ? x : y);
}

int main()
{
constexpr int g { greater(5, 6) }; // case 1: always evaluated at compile-time
std::cout << g << " is greater!\n";

std::cout << greater(5, 6) << " is greater!\n"; // case 2: may be evaluated at either runtime or compile-time

int x{ 5 }; // not constexpr but value is known at compile-time
std::cout << greater(x, 6) << " is greater!\n"; // case 3: likely evaluated at runtime

std::cin >> x;
std::cout << greater(x, 6) << " is greater!\n"; // case 4: always evaluated at runtime

return 0;
}

作用域、生命周期、链接域

scope、duration、linkage,后面我就不翻译了,也不知道怎么翻译

https://www.learncpp.com/cpp-tutorial/scope-duration-and-linkage-summary/

保研记录

本人情况:

  • 本科院校:江苏某top4!
  • 本科专业:AI
  • 排名:1/87
  • 四级:595,六级:538
  • 竞赛:ICPC银若干,CCPC铜若干,JSCPC金银,CSP440,cf两紫名号(?)
  • 科研:无
  • 项目:水项目
  • 国奖,CCF优大(这俩感觉基本没用)
  • 偏就业向,未来偏向于做引擎开发。因此梦校是软微、南软和人大信专。

总结为A批,而且又菜又爱玩,不仅没拿到金牌,还因为这沟槽的网瘾,没有深入参与过含金量高的项目。不过好在大三因为一个队友去和大一的两位noi✌组队,另一个队友退出了,然后我也选择了退役,转去卷课内,得以保住rk。但就夏令营的情况来看,保rk弃acm是我做的一个非常正确的选择。

夏令营之前:

虽然我是AI专业,但是我对AI提不起一点兴趣,尤其是CV、NLP这些(别问我为什么没转专业)。大二ICPC赛季结束的时候被一个学长忽悠去做AI相关的科研,后面还进了某CV组,体会了一下开组会读paper做pre的氛围,也是感到十分不快。

后面大三上的时候考虑做过sys,虽然谈不上非常喜欢,但至少不反感。不过从大三开始入门sys说实话感觉有点晚了,而且AI的培养计划并不注重对计算机系统能力的培养,导致我甚至连CPU指令流水线这种基本概念都不清楚,加上保rk要学讨厌的课程,我没办法分配出太多精力出来,因此学术梦碎。

为什么选择就业向呢?首先我本身是一名ACM选手,非常喜欢coding。其次我也是个造轮子爱好者兼游戏爱好者,对工程较感兴趣,也开发过一些小型3D游戏。不过由于大学期间大部分时间在卷ACM和课内(基本在码python,pytorch那些,当调包侠),没有多少实践的机会(面南大的时候老师也指出了我这个问题,哈哈),因此也希望读研期间能精进自己的engineering能力。

总结来看,作为一名ACM败犬,我在选择读研方向上也是经历了一波三折的过程。期间经历了无数次痛苦,包括误入歧途、自我怀疑、被学长yygq。尤其是大三选择ACM退役的那段时间,感觉自己大学中唯一一件有意义的事情与我断绝了,只剩下一堆不喜欢的AI课程要卷,也不知道自己接下来的路该怎么走,每一步所做出的选择是否是正确的。不过好在就保研而言的结果还是能让我满意的。

夏令营情况:

学校 学院 类型 入营 结果
南京大学 cs 专硕 过线上测试,放弃线下
复旦大学 cs 专硕 撞nju和两门期末,放弃
南京大学 ai 学硕 放弃,不喜欢AI,但是因为是nju就报了,nju梦校
吉林大学 se 专硕 开的早,投着练练手,最后也是直接鸽了
哈尔滨工业大学(深圳) cs 专硕 × 正常,清北bar,投着玩
同济大学 cs 专硕 优营(第一个优营,感谢同济!)
上海交通大学 se 学硕 ipads太难,没sys基础,其余组方向不感兴趣,放弃
南京大学 se 专硕 优营,梦校
中山大学 cs 专硕 × ???海营我都没入?
中国人民大学 信院 专硕 撞nju,加上考虑到往年优营率低,放弃

可以看到,多亏了大三上学期选择放弃ACM,得以保住rk1,让我在没有任何科研项目的情况下入了很多营。但是实际上我只完整参加了两个,主要是今年和往年相比,夏令营的时间冲突的太多了,属于是大型车祸现场。特别是六月初得知ruc信院和南软冲突的时候,我真的有点破防。最后由于华五情节与优营率的考虑,选择了南软,鸽了ruc。

1. njucs

今年南计开的非常早,好像四月份就开了,然后五月初就截止报名。当时我根本没有做好准备,内心也是非常慌。

由于我夏令营的目标是南软,所以一开始是不想去南计的,因为按往年情况来看,南大cs,se,ai这三个夏令营只能去一个(njusz那里我不太清楚)。但是看绿裙说南大cs线上测不考虑冲突因素,可以放心参加,我就参加了(怎么说也是梦校)。

南计的线上笔试也算是著名的难,往年原题可以参考绿裙的github仓库(虽然很少)。范围大概是408+算法+编译原理+linux+其余杂项,题型是单选+多选,多选漏选超选错选皆不得分。我记得今年的题偏向于编译原理和数据结构。因为我本科AI的,很多课程没学过,因此大多数题都是蒙的,除去几个ACM中接触到的几个算法和数据结构(kmp,背包)。

结果比较出乎意料,过了:

然鹅后续放弃了。

2. tongji cs

本来是没想报同济的,但是绿裙里有个同济的宣传大使,说这个学校就业非常好什么的,再加上夏令营时间也比较好,没和其它学校冲突,我就报了。(不是)

然而没想到的是今年同济cs夏令营的bar非常高,整个学院只入了我一个人。最后只能孤身一人前往上海。

同济的考核非常硬核,机考+笔试408+英语笔试+英语口试+面试,五脏俱全。是计分制,满分350.

机考的话非常简单,第一题是给定一个字符串,然后对串的每个字母在其对应的位置(例如a对应第1列,z对应26列)一行一行输出。第二题是找给定数独九宫格的冲突位置。第三题是输出数字三角形。我大概花了十几分钟就做完了,但是后面静查的时候发现了第二题的一个bug,及时改正。

笔试408+英语,非常难,时间也特别赶。我记得大题后两题我都直接空着(分别是计组画什么数据通路,以及计网给定一个802帧分析其内容,ip地址,协议什么的)。英语是一道阅读理解,一篇论文。

可以参考:https://zhuanlan.zhihu.com/p/658346474

面试,有九个老师围着你坐,轮流提问。一开始是让我英语自我介绍两分钟,然后是让我英语说transformer的原理。后面就提问了一些项目和专业课的知识,我记得问了我系统调用和普通函数调用的区别。最后一个问题出乎我意料,一个老师问了我高数题(我记得是分部积分啥的),这我咋会?感觉我这个组比较压力面,然而另一个哥们的组感觉非常友好,问了很多生活问题,还有思政题。

结果没想到是优营,分数还挺高,满分350拿了二百八十几分,应该是稳offer了。

面试那天雨非常大,emmm

3. njuse

南软是我夏令营的最高目标,毕竟华五+两年制+放实习,太适合我这种就业鼠鼠了。

南软的bar也是很神奇,隔壁江苏top3的rk2+ACM银没入营,我校只入了软工的rk1和我(套磁了一个导师,可能捞了我进去),同院计科的rk1也没入。但是南软同时放了若干双非非rk1的金牌✌入营。现在想想,当初ICPC没拿金的我选择保住rk1,真是太明智了。

南软安排又紧又松。紧是因为我一天半就走完了夏令营流程,松是因为南软通知事项的方式很随意,就建个群,然后有通知了就@全体成员发消息,公告都不带发的,也没有流程pdf,感觉就非常敷衍。

南软考核也比较全,笔试+机试+面试。

笔试的内容有五项,顺序依次为离散数学(群论+图论的证明题)、软件工程(画状态图,软件测试)、操作系统(页式内存,PV操作)、计算机网络(DNS,ALOHA协议,求极限(啊?))和数据库系统(B+树索引,递归查询sql语句,事务undo+redo),各占20分。开卷,但是考的很偏,我很多都没做出来。

机试的话,今年是四道算法题,没有了往年的面向对象题。今年南软的机试题普遍反映非常难,和隔壁南计的机试题(没有算法题)形成鲜明对比,我记得第一题是给定已有的面额值 ,要求你求出最少的需要补充的额外面额值的个数,在每个面额值的使用次数小于等于一个给定值 的情况下,能够相加组合得到范围 内的所有数。第二题是要你用两个平行于坐标轴的不相交矩形来包围给定的二维点集,要求两个矩形的面积和最小。第三题是给定一个坐标轴,坐标轴的第二象限有 头牛,每头牛占据一个单位长度,左开右闭,并按照 的速度(这里的速度是每 瞬移一个单位,注意)朝着 +x 方向移动。然后你在原点朝着 +y 方向观察,问给定每头牛的坐标,及其速度,问最多有多少头牛经过你的视线。第四题是给定一个二维平面,平面上有字母,空白以及障碍,要求除去障碍,每一个行或每一个列内部的连续块(连续的字母与空,障碍隔开)形成的序列是一个回文串。求你能够确定的最多的空白对应的字母的坐标数量,并给出最终局面。

由于我是ACMer,AK了,全场快300人中有10个AK的。没有签到题,感觉对一般人比较不友好。四道题的难度大概在div1a, b这种。解法分别为数学+贪心,排序+枚举切割的横/纵坐标,离散化+线段树,BFS。

我记得笔试交卷的时候,大家动静很大。然后有个监考老师露出了诡异的笑容,说:“诶,你们先别叫,下午再叫,下午才是正菜(早上笔试下午机试),现在只是给你们开开胃。欸,下午你们叫也叫不出来,哈哈哈,那个才叫酸爽。”当时给我们都整懵逼了。

面试的话,虽然拿同济练过手,但是作为i人的我,还是很紧张。不过惊喜的是在面试前半个小时,我收到了同济优营的消息。拿到第一个offer的喜悦瞬间冲刷了我所有的焦虑,后续面试也不再紧张了。

具体面试内容也比较轻松,让你介绍你的项目经历,不问专业课。由于我的项目比较水,老师转而让我陈述大学期间做过的有意义的事情,我直接把我的ACM经历全炸出来,感觉老师也是比较感兴趣。期间问了我最喜欢的算法,我说树状数组,然后老师们似乎并不太清楚这个东西,我就大致介绍了一下它的功能和原理。后面稍微批评了我项目实践能力较为缺乏。最后一个老师问了一些关于实验室横向的问题,也是畅所欲言。

当然面试内容具体情况分组考虑,有的组会压力面,比如作英语自我介绍,翻译英语,问软工那些模型(瀑布、螺旋、敏捷开发)什么的,因此建议充分准备。

最后也因为机试AK,没有悬念地优营了。说实话当初面完南软就觉得自己稳了,以至于过于自信,后续的sjtu软就没去(当然也有懒得读论文的原因)。但说实话不建议大家这么干,有点冒险(

预推免情况:

估计不会报名预推免了,主要是除了ruc信院,感觉没有比南软更适合我的去处了。可惜ruc不开预推免,呜呜呜呜。

顺带一提,今年软微保研似乎改革,变成纯科研向了,鼠鼠top2梦碎。

数据库完整性

实体完整性

create table中用primary key定义

例:创建学生表Student,将Sno属性定义为主码:

1
2
3
4
5
6
7
8
create table student(
sno char(8),
sname char(20) unique,
ssex char(6),
sbirthdate date,
smajor varchar(40),
primary key(sno)
);

插入或对主码列进行更新操作时,关系数据库管理系统按照实体完整性规则自动进行检查。

  • 检查主码值是否唯一
  • 检查主码的各个属性是否为空

这种检查操作需要 遍历每一条记录,十分耗时。因此关系数据库管理系统一般都在主码上自动建立一个索引。例如B+树索引。

参照完整性

在create table中用foreign key短语定义哪些列为外码。

用references短语指明这些外码参照哪些表的主码。

例:关系SC中(Sno, Cno)是主码,Sno、Cno分别参照Student表的主码和Course表的主码。

1
2
3
4
5
6
7
8
9
10
create table sc(
sno char(8),
cno char(5),
grade smallint,
semester char(5),
teachingclass char(8),
primary key (sno, cno),
foreign key (sno) references student(sno),
foreign key (cno) references course(cno)
);

一个参照完整性将两个表中的相应元组联系起来。对被参照表和参照表进行增删改查操作时可能会破坏参照完整性,必须进行检查。

例:

  • 向SC表中增加一个元组,该元组的Sno属性值在表Student中找不到一个元组,其Sno属性值与之相等。
  • 修改SC表中的一个元组,情况如上
  • 从Student表中删除一个元组,造成SC表中某些元组的Sno属性值在Student中找不到一个元组对应
  • 修改Student表中的一个元组,情况如上

参照完整性违约处理:

  • 拒绝执行:一般为默认策略
  • 级联操作:当删除或修改被参照表的一个元组导致与参照表的不一致,则删除或修改参照表中的所有导致不一致的元组
  • 设置为空值:当删除或修改被参照表的一个元组导致不一致,则将参照表中所有造成不一致的元组的对应属性设置为空值

用户定义的完整性

针对某一具体应用的数据必须满足的语义要求。

属性上的约束

create table中定义属性约束

  • 列值非空 (not null)
  • 列值唯一 (unique)
  • 检查列值是否满足一个条件表达式 (check短语)

元组上的约束

在create table语句中可以用check短语定义元组间不同属性需满足的限制

完整性约束命名子句

constraint <完整性约束名> <完整性约束>

修改表中的完整性限制

使用alter table语句

例:

1
2
alter table student
add constraint c1 check(sno between '114514' and '1919810');

触发器

挖坑


作业

假设有下面两个关系模式

职工(职工号,姓名,出生日期,职务,工资,部门号),其中职工号为主码

部门(部门号,名称,经理姓名,电话),其中部门号为主码

用SQL定义这两个关系模式,要去在模式中完成以下完整性约束的定义:

  1. 定义每个模式的主码
  2. 定义参照完整性约束
  3. 定义职工年龄不超过65岁

oracle不支持constraint带有变量,这里需要使用触发器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
drop table 职工;
drop table 部门;

create table 部门(
部门号 char(8) primary key,
名称 varchar(20),
经理姓名 varchar(20),
电话 varchar(20)
);

create table 职工(
职工号 char(8) primary key,
姓名 varchar(20),
出生日期 date not null,
职务 varchar(20),
工资 decimal(10, 2),
部门号 char(8),
constraint fk_部门 foreign key(部门号) references 部门(部门号)
);

create or replace trigger ck_age
before insert or update on 职工
for each row
begin
if(extract(year from current_date) - extract(year from :new.出生日期) > 65) then
raise_application_error(-114514, '职工年龄不应超过65岁');
end if;
end;
/

测试:

1
2
3
4
5
insert into 部门 values('88488848', 'test1', 'name1', '114514');
insert into 职工 values('66666666', 'name2', TO_DATE('1980-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488848');
insert into 职工 values('66666666', 'name2', TO_DATE('1980-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488849');
insert into 职工 values('66666667', 'name2', TO_DATE('1980-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488849');
insert into 职工 values('66666667', 'name2', TO_DATE('1880-01-15', 'YYYY-MM-DD'), 'job1', '1145.14', '88488848');

前两行正确,后三行应出现错误:

0%