大佬们图形学小混子求教个问题

更新:已挂周一催了一下hr，hr直接回复暂不合适然后系统里流程中止（既然这样直接一面就把我挂了不行吗，害得我白期待了-------4.8 一面---------------面试官极其极其友好和专业，面试体验应该是目前最好的，面试官开场就说是工大的同学，直接亲切感拉满了（面试官是科大的），对比之前遇到过有面试官问:合工大什么档次?具体问题就不详细描述了，大致是围绕简历内容进行提问，和面试官讨论了关于透明渲染，级联阴影贴图，渲染大量物体等图形学的问题, 当然也问了不少CPP对于开放性或者我回答不确定的问题，面试官会加以引导手撕部分出现了编译期求值的题目（很新颖，之前完全没碰到，只会其中一个）然后算法题没写出来，这部分还是拉了，力扣刷了不少还是拉一面完后两小时，hr小姐姐通知已过，让我准备二面#本周投递记录##暑期实习##快手#

投的后台开发，变成客户端开发了。刚开始明确说了是做游戏的，用c++和c#偏多。自我介绍项目介绍（20min左右）算法（30min左右）：快排原理（三个步骤）堆排原理（两步：建堆、调整堆、建堆是怎么建立的、调整是怎么调整的）归并排序如何优化空间复杂度为O(1)（这里提示了半天，我说了一种方案双指针交换元素，面试官说还能优化。）AC自动机原理（简历上写了）记得KMP算法吗？（不记得）Hashmap扩容原理（简历上写了）红黑树红色节点和黑色节点表示什么含义，红黑树和avl有什么区别？（不是很了解红黑树）操作系统：加锁底层的原理是什么（不知道） 线程之间同步数据有哪些常见方法（互斥锁、PV原语）线程内...

包含了腾讯一二面，搜狐一面，雷火一二面，快手（游戏图形学）一二面等等内容，只记录一部分有意思的问题，图形学八股和cpp八股不在此处。我自己项目做的比较细，我不是实现了一个引擎而是实现了一些图形算法优化，这导致面试官都会对优化细节，实现细节细细拷问，同时夹杂一些面试官自己的思考（你是这么实现的，但我觉得你这样会有blabla问题 or 你是这么实现的，你遇到某某问题怎么办，能处理吗能优化吗）。延迟管线中需要处理复杂材质和光照模型怎么办？比如这一部分物体是某种shading model而另一部分物体是另一种model？csm如何处理每级之间分辨率突变的情况？csm每渲染一帧都要渲染4 or 8张阴影图吗？这样性能开销过大，怎么解决？（帧间）遮挡剔除的实现算法介绍一些？AA算法，RTGI算法介绍一些？原神是如何处理实时全局光照的你了解吗，均匀的在场景内布置光照探针如何应付大场景渲染？你是如何分析性能瓶颈，统计性能情况并进行优化的，怎么看出你实现了优化？bsdf和brdf的区别？各自的应用场景？介绍一些gpu driven的方法？半透物体如何在延迟管线中渲染（此题有坑）？（忘了，想起来再更）总结：一半的面试官会提到原神，建议去好好看看原神的图形算法实现（好像某乎上有大佬介绍）。我自己项目中大量使用compute shader但从未被问到（所以引擎岗不会太侧重编写shader的细节）。面试官还都特别喜欢问场景题，只能说纯背八股做项目是不行的，还是要多看别人文章，自己多思考总结举一反三。还有，一定要学一下renderdoc！这也是基础！ #牛客解忧铺# #我的成功项目解析# #如何判断面试是否凉了#

题目：给你一颗树，n个节点，边长为1，求任意两点的路径和。u, v 和 v, u 算同一条路径，故只算一次。（已经简化了，本来是还有一些边长为0，可以把0的点缩掉）先以节点1为起点，计算1到各个点的路径和。1-3, 1-2, 1-4, 1-5 = 8然后换根，进行dfs，向子树移动移动到 3 节点时，增量 = - (目标子树 - 1) + (n - 目标子树 - 1) = n - 2 * 目标子树例如：从 1 -> 3 时，8 + （5 - 4 * 2）= 53-1， 3-2， 3-4， 3-5 = 1 + 1 + 1 + 2 = 5例如：从 3 -> 4 时，5 + （5 - 2...