自适应多项式渲染
由于坑爹的 VR 课程的大作业需要选一篇 SIGGRAPH 2016 的论文来复现, 本着尽量偷懒的精神, 我选了一篇优化蒙特卡洛路径追踪(最简单的光线追踪算法)的采样次数的论文: Adaptive Polynomial Rendering, 这样能在我的期中作业上直接修改.
主要做三件微小的工作, 很惭愧:
[X]把之前实现的 SAHKdtree 的 bug 给调出来[X]把原来的多边形面片换成三角面片(这一步加速并不如我想象中的大).[ ]将底层的实现换成 CUDA, 实现 Adaptive Polynomial Rendering 算法
SAHKdtree
之前写的 SAHKdtree 性能被按中位数切割的 Kdtree 打爆, 几乎与朴素无异.
观察了一下建树过程之后发现启发函数非常不连续, 而且经常在边界取极小值, 因此建出的树非常不平衡. (某个节点分裂不平衡可能让子树更平衡).
之后发现错误在于没有处理边界条件, 加了一句"禁止左右儿子 size 与原节点 size 相同", 算法的效率迅速提升, 速度以几十倍吊打中位数版的 Kdtree.
BTW, 看了Yuxin Wu 的代码之后, 我发现我的 SAH 写法与他不太一样, 在启发函数:
\[H = N_L S_L + N_R S_R\]
中, 我的 \(S_L\) 和 \(S_R\) 算的是两个子节点包含三角面片的包围盒表面积, 而 wyx 的代码算的是原包围盒切割之后左右两侧的表面积.
多线程建树
这一步实际上并不是必要的, 因为建树时间与渲染时间相比相差太远. 按照 wyx 的做法, 只在顶层节点用多线程(排序并行, 顶层节点的两个子树并行), 速度略有提升. 一开始多线程建树的效果不显著, 后来发现原因是我的 SAHkdtree 在前几层不平衡, 强制要求在最高层均分就可以了.
CUDA
在做了一些主要的算法级的优化之后, 我发现剩下能做的优化几乎是挤牙膏, 不得不感叹`-O3`优化实在是太强大了. 除了传说中的 Bidirectional Path Tracing 算法之外, 大概唯一能做的比较靠谱的加速就是用 CUDA, 之前没有 GPU 编程基础, 看了以下资料用于速成:
- CUDA by example
- CUDA C best pratices guild
- CUDA C/C++ Basics
- cuBLAS Documentation
- Computer Architecture: A Quantative Approach
教程很丰富, 不必赘述.
相比其他的光线追踪算法, MCPT 可以实现 GPU 并行, 因为虽然算法看似是递归的, 实际上每次只走一条光路. 通过增大采样次数就能解决真实性的问题. 现在最关键的问题是, 如何在 GPU 上运行 KD 树的查询操作, 如果不写效果必定大打折扣, 但是不能直接在原来的基础上写因为, device 上的函数不能调用 host 的函数. KD 树建树可以保持在 CPU 上操作, 之后再复制到 GPU 上, 不是渲染的效率瓶颈. 在 GPU 上写 KD 树的难点在于, 虽然 KD 树查询的期望时间复杂度是 \(O(log(n))\) , 但是最坏情况仍然有 \(O(n)\) 的可能, 而且查询过程并不是一条链, 所以需要栈来储存中间状态, 对于 GPU 执行很不利. Eurographics 2005 的一篇 paper 提出了一个算法, 不需要使用栈.
- 从根节点找到第一个叶子节点, 如果没有交(fail), 令 tmin 为当先叶子的 tmax, 然后再从根节点开始搜, 循环往复.
- 上面的算法有许多重复节点, 所以每次 fail 的时候, 令 tmin 为当前叶子的 tmax, 从叶子往跟回溯, 直到找到一个 bounding box 与 ray 在新区间内有交, 则从当先的右子树开始搜.
如此显然的算法, 然而人家却发了 Eurographics. 那么是不是传统问题的一些“不那么显然”的算法是不是都可以披上一些新鲜问题的外衣发 paper… 不过仔细想了想, 在本机没有 GPU 的情况下进行如此大的代码重构真是够恶心的, 我抑制了这个冲动. 加上了许多优化之后可以较快地渲染面片比较多的图(来自我 github 上的 mode, 20samples + 抗锯齿):
Adaptive Polynomial Rendering
这篇来自 SIGGRAPH 2016, 首要解决的是 MCPT 噪点多的问题, 当 num_sample=32 的时候, 图像轮廓已经成型, 但是噪点颇多, 文中的方法虽然不能让原本模糊的区域变得更清楚, 但是可以把较清晰的区域变得光滑, 定量地来说, rmse 值变低.
算法的主要思想是用泰勒展开局部拟合函数. 具体的参数包括二维坐标, 还有光束射到的目标所对应的纹理, 三维坐标和深度, 多项式的参数可由最小二乘估计而得. 为了选择出最优的多项式系数, 用了一系列的数学技巧做估计. 在原来的代码上只需要加上储存每次采样的信息, 以及每个像素点的参数.
效果
就我目前的估计来看, 用一阶小量和用多阶的效果并没有什么本质上的差别. 从视觉效果上来看, 该算法擅长处理漫反射表面, 但是镜面反射和折射效果捉急, 可以考虑在参数中再加上几维(第二/三次反射之后表面的纹理, 深度位置之类的信息). 效果可以见小学英语水平的报告.
参考
- Adaptive Polynomial Rendering(SIGGRAPH 2016)
- Brook for GPUs: Stream Computing on Graphics Hardware(SIGGRAPH 2004)
- KD-Tree Acceleration Structures for a GPU Raytracer(Eurographics 2005)
- On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N) (2006 IEEE Symposium on Interactive Ray Tracing*)
- Yuxin Wu's repository: https://github.com/ppwwyyxx/Ray-Tracing-Engine
Footnotes:
命名来自神秘博士中的迦里弗雷星球（时间领主的母星）。