腾讯北极光游戏客户端一面

多项式求值

$a[0]x^0 + a[1]x^1 + ... + a[n-1]x^{n - 1}$

一开始使用pow函数，面试官说不让

之后改成了用一个变量来记录

for (int i = 0; i < n; ++i) {
    ret += a[i] * power;
    power *= x;
}

面试官说可以减少循环内的计算次数

变成一个加法和乘法

注意现在还是按顺序从左往右计算的

计算每一个项在求和

秦九韶算法：

将多项式转为嵌套形式，这种嵌套形式天然的不就适合循环计算吗，能保留上一次的结果

\begin{align} p^5+p^4+p^3+p^2+p \nonumber &= p \times(p^4+p^3+p^2+p+1)\\ \nonumber &=p \times \big( p \times (p^3+p^2+p^1+1)+1 \big) \\ \nonumber &=p \times \Big( p \times \big(p \times (p^2+p^1+1)+1\big)+1 \Big)\\ \nonumber &=p \times \Bigg( p \times \bigg(p \times \big( p \times (p+1) +1 \big)+1\bigg)+1 \Bigg) \end{align}

转化后, 阅读起来还像更费力了, 因为有很多括号。但是这个形式有一个最大的优点: 计算效率高!

计算式乘法运算次数加法运算次数

$p^5+p^4+p^3+p^2+p$	$4 + 3 + 2 + 1 = 10$	$4$
$p \times \Bigg( p \times \bigg(p \times \big( p \times (p+1) +1 \big)+1\bigg)+1 \Bigg)$	$4$	$4$

乘法运算明显减少, 而加法运算次数不变。当 $n = 1000$ 时呢？

计算式乘法运算次数加法运算次数

$p^{1000}+p^{999}+ \cdots +p^{2}+p$	$\begin{align} \nonumber & =999+998+997+\cdots +1 \\ \nonumber &= \frac{(999+1)\times999}2 \\ \nonumber &= 499500 \end{align}$	$1000$
$p \times \Bigg( p \times \bigg(p \times \big( p \times \cdots \times (p+1) + \cdots +1 \big)+1\bigg)+1 \Bigg)$	$1000$	$1000$

乘法运算复杂度由 $O(n^2)$ 降低到了 $0(n)$

口述LRU缓存，要注意什么
vector和list区别，使用场景区别？
const写在成员函数后面有什么区别？

struct AA {
    static void FuncA(){ printf("funca\n") };
	void FuncB() { printf("funcb\n")};
	virtual void FuncC() { printf("funcc\n")};
};

AA *aa =(AA*)malloc(sizeof(AA));
aa->FuncA();
aa->FuncB();
aa->FuncC();

Q: 这份代码有什么问题吗？

A: 不可以用malloc给类分配内存

Q: （笑）下面三个运行的时候会不会出问题？

FunC会出问题，因为malloc没有调用构造函数

自然不能发生动态绑定

但是aa是生成了虚函数表的（虚函数表是静态的）

只是运行时虚函数指针没有初始化

虚函数表跟着类走，虚函数表指针跟着对象走（实例化出来运行时才有）

unique_ptr了解底层实现吗，怎么实现它的独占权。
shared_ptr了解底层实现吗，怎么实现引用计数机制。
CPU的多级缓存机制，写代码的时候如何利用CPU的多级缓存机制？
为什么矩阵按行访问会快，按列访问会慢？
你说了按列访问会发生多次寻址，什么是寻址？
信号量和互斥锁有什么区别？
玩什么游戏，为什么想做游戏？
描述下VSSM、PCF，说下shadow map（没回答好）
说下光栅化的基本流程吧
深度测试必须在ps之后做吗？放之前行不行？
early-z可以控制它发生在那个阶段吗（默认不是ps之前吗）

原本的深度测试是在Fragment Shader计算之后的，如果不通过深度测试，这部分Pixel计算就是浪费的。

优化方式就是在Fragment Shader处理之前，先进行深度测试，可以避免过多的Pixel计算。

使用深度检测是方便的（硬件直接支持），这个优化，假设你的Pixel计算没有对深度进行任何修改，也就是说在Fragment Shader之前和之后进行深度检测的结果是一样的。（Therefore, an implementation is free to apply early fragment tests if the Fragment Shader being used does not do anything that would impact the results of those tests. ）

注意

这个是硬件支持的功能，图形API无法决定是否进行。（原文：Because this is a hardware-based optimization, OpenGL has no direct controls that will tell you if early depth testing will happen.）

如果进行了Alpha Clip或者深度写入，会造成EarlyZ失效。（原文：Similarly, if the fragment shader discards the fragment with the discard keyword, this will almost always turn off early depth tests on some hardware. Note that even conditional use of discard will mean that the FS will turn off early depth tests.）

失效

开启Alpha Test：由于Alpha Test需要在像素着色器后面的Alpha Test阶段比较，所以无法在像素着色器之前就决定该像素是否被剔除。

开启Alpha Blend：启用了Alpha混合的像素很多需要与frame buffer做混合，无法执行深度测试，也就无法利用Early-Z技术。

开启Tex Kill：即在shader代码中有像素摒弃指令（DX的discard，OpenGL的clip）。

关闭深度测试。Early-Z是建立在深度测试看开启的条件下，如果关闭了深度测试，也就无法启用Early-Z技术。

开启Multi-Sampling：多采样会影响周边像素，而Early-Z阶段无法得知周边像素是否被裁剪，故无法提前剔除。

以及其它任何导致需要混合后面颜色的操作。