前段时间实在是十分焦虑, 于是投了NVIDIA的graphic engineer的职位,

一天后收到面试通知, 5天后的今天面试, 写下面经及复习准备经历, 也好让有同好的人做个参考.

第一题是开胃菜, 问我说, 你有这样一段代码:

while ()   {

        for ()      

       {      if ()   

            break;}

}

那个break以后是去哪儿?

回答: break是break出for循环, 然后做之后的事.

"good, 听下一题, say, 你有一个浮点数, 3.999, 你对它取整(int)a, 是多少?"

3,

那么, 你如果想让一个浮点数四舍五入, 但仍然用(int)这个操作, 你该怎么办?

答:我就把它加上一个数然后再(int).

那个magic number是多少?

 答: 0.5.   (int)(a+0.5) 就是对a做四舍五入操作.

very good, 请听下一题, 你如何交换a和b?

(我操, 终于来这道了, 我平时想过无数遍的无须tmp交换a和b的方法终于派上用场了.....)

答, a -= b, b += a, a = b - a,

你这个方法有什么issue? 

答 奥, 当两个数太大的时候可能会exceed 整数的表达.

那怎么办?

答, tmp = b, b=a, a=tmp;

不用tmp呢?

答, 假设你的地址是32位的, double是64位的, 那么我能这么做:

swap(double *addr1, double *addr2)

{

          addr1 | = addr2<<32;

          addr2 = addr1 &0x0000ffff;

         addr1 = addr1>>32;

}

Okay, 我们来看下一题. (貌似他对我这里的回答不是十分满意, 但没办法我这个也是对的, 我后来查了查, 发现最好的做法是)

void xorSwap (int *x, int *y) { if (x != y) { *x ^= *y; *y ^= *x; *x ^= *y; } }
如何找出一个数的msb(most significant bit)? 最高位的bit数. 答 : while(v>>1) count++; 还有更快的吗?

答, 可以采取二分的思路. 先看v>>16, 如果不是0, 就测v>>24, 如果是0就测v>>8这样子类推. 当然, 最快的方法是说, 就一个数最高位bit的位置其实是对它求log2(v)的过程, 比如说4 就是100, 8 就是1000, 9 是1001但是9的最高位bit数和8一样, 就是log2(9)取整. 所以可以把这个数先cast成double, double x=(double)v|1; 然后, 这个浮点数的指数断的数-1023就是它的msb, 也就是说 (x&0x00000000ffffffff)<

good, 请听下一题. 你给我描述一下fixed graphic pipeline. (啊...终于到我的老本行了.....)

答, fixed graphic pipeline的方法是, 对于送到图形pipeline里的任务(顶点数据, index数据, 目前的变换矩阵), 先对每个顶点数据进行modelview变换, 然后施加透视投影变换, 下一步是根据index数据以及透视变换的结果进行光栅化, 对于固定管线来说, 光照计算在光栅化之前逐顶点地完成, 然后由光栅化来对像素的颜色进行逐像素插值, 通常采用双曲型插值算法. 然后就是进行z-buffer遮挡检测及剔除, alpha通道合成, 然后完成渲染.

very good, 那你和我讲一下有shader的pipeline

答, 在我的知识里最up to date 的pipeline有四个步骤, vertex shader, tesellation shader, geometry shader, 和pixel shader. vertex shader里可以根据用户编写的shader程序来替换固有管线的顶点变换步骤, tessellation shader是在DirectX11和opengl4.0以后新加入的内容, TS包括hull shader和patch shader两个部分, 对于传入的顶点数据和index数据, HS用来计算control points的变换, 此时可能也可能不对顶点进行进一步地变换, 因用户所采用的算法而定, PatchS中, 根据patch的uv坐标和它的control points的数据, 采用相应的插值算法来计算生成光滑的patch, 比如bicubic spline, bezier patch什么的, whatever, 然后计算的结果传入到GS中去, GS根据需求可能也可能不生成更多的图元或者计算法线, 最后是PS, PS课根据编写的光照程序根据传入的数据逐像素插值, 然后计算最后的光照合成.

问: 谈一下你所知道的shading approachs.(这一问我可能答非所问了, 但看似他后头有补充问了我他想问的然后我也回答了...)

我此时的回答是: 我所知道的最好的shading approach是deferred shading过程, 它的第一步不计算位置插值和颜色,光照, 只计算并存储下场景的zbuffer值, 这个过程比通常的绘制快4倍, 然后它计算并差值出当前场景的position值, 法线值, 反射折射系数, default颜色值, 再把这些拿到最终去compositing, compositing时, 可以根据已有的z-buffer缓存纹理进行像素的pre-zculling, 避免传统管线中的先计算颜色-后culling的冗余计算, 然后再根据光照公式计算颜色.

他然后问了我, 你刚才谈到compositing, 说说什么是compositing,

答, compositing就是通过将你拿到的法线, 坐标, default, 反射折射系数, shadow map这些用一个光照公式来进行光照计算, 产生像素最终颜色的过程.

问: 你知道什么non-rasterization based 算法吗? (现在回想起来, 这似乎是对上一个问题的补充, 也就是说他当初实际想问的...)

答: 哦, 据我所知还有两种, 一种是光线跟踪类的算法, 一种是pixar的renderman采用的算法, 都可以算是非光栅化的算法, renderman采用的方法是将多边形subdivide成比像素还小的polygon然后逐顶点进行光照, 然后在像素范围上加权平均多个polygon的光照贡献.

那光线跟踪呢?

答: 光线跟踪是说, 基于我的视点的范围, 对屏幕的每个像素射出"视线", 然后这个视线与后面的几何体求交点, 求交点的过程一般采用kd-tree来进行加速, 然后在从交点处引出光源线, 反射线和折射线, 光线跟踪的算法认为, 这个像素的颜色, 由主级光线传回的光照贡献和反射光线以及折射光线传回的贡献加和的结果, 而计算反射线和折射线则是同主光线一样递归的过程.

接下来是进阶阶段了, 开始问我正在做的项目的解决方案....

问: 现在我们有这样一个项目, 我们的组是做一些关于SLI技术的研发, 我们采用两种approach, 一种是balabala, 另一种是balabala2(这里之所以是balabala因为我没听懂.) 请你谈一下你认为这两种方法的思路是怎样的?

答 : 根据我多年做并行的经验来讲, 加速计算总的思路来说就是把任务分成多分, 通过多处理器的同时运作来加快计算速度, 而gpu一般认为的bottleneck在数据传输上, 我不知道你是不是想问关于如何解决这个瓶颈的方法?

问 : 那我说仔细些, 我们有一种方法是说把屏幕分成两份, 一个GPU计算其中一个, 另一个计算另一份, 你觉得这个方法有什么问题?

答 : 我想的话, 可能由于浮点数精度的问题会在屏幕中央的分界区造成走样.

他 : 这个不是最主要的, 事实上两个屏幕的问题是, 当你在使用比如shadow map的时候...

答 : 奥, 对, 当你使用shadow map的时候你无法把这个shadow map在不同的gpu上分割, 不得不一个传一份过去.问 : 后来我们采用了另一种方法, 让这个gpu计算一帧, 那个gpu计算下一帧, 你觉得这个方法的问题在哪?

答 : 我认为, 玩家的操作是不可预知的, 所以在这个gpu计算这一帧的时候到下一个gpu计算下一帧之间可能会发生什么不可预知的问题.

他 : 你想的方向对了, 再想想?

答 : 我此时跟他开始胡扯, 什么同步啊, 延迟啊......(一下子也想不到点子上)

他 : 事实上当我们在送给另一个gpu任务的时候我们不可能知道下一帧的时候viewport会变成什么样, 所以这之中就会有同步的问题了.

我 : 所以总的来说还是input based issues.

他 : yes, good, 那我还有个问题.

问完这两个问题后, 他似乎发现还有个问题要问, (我估计还是之前那个我答非所问的问题中他想知道的)

问 : 你知道phone shading是怎么做的?

我 : 知道, 但我不可能把公式背给你听, 但他的做法是unlike 高洛德光照, which is 逐顶点的计算光照, phone shading在计算光照前用插值算法逐像素的对position, 法线, 进行插值, 然后逐像素的用光照公式计算光照, 结果就是, 尽管采用的模型比较粗糙, 但是着色的结果可以十分平滑, 甚至能有sub-polygon的高光.

接下来就是说你有什么问题要问我?

我问了些关于做什么的事情, 然后他回答了一下, 然后我说总的来说我对这些还都是很有兴趣的, its a nice interview, and have a good day.

然后人家问了下我关于relocating的问题, 然后在随便客套了几句就88了.   

关于复习, 我发现, nv很喜欢问关于bit码有关的运算, 也是我常年用nvidia的sdk发现的, 他们写的代码很喜欢用bit运算, 所以我之前特意复习了所有可能想到的和bit码运算有关算法与优化技巧, 找到一个好网站... http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd 基本上把里头的东西都搞下来应该是不怕它的低阶区的题目了...