自适应多项式渲染

Table of Contents

由于坑爹的 VR 课程的大作业需要选一篇 SIGGRAPH 2016 的论文来复现, 本着尽量偷懒的精神, 我选了一篇优化蒙特卡洛路径追踪(最简单的光线追踪算法)的采样次数的论文: Adaptive Polynomial Rendering, 这样能在我的期中作业上直接修改.

主要做三件微小的工作, 很惭愧:

Source code: Gallifrey 1.

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 编程基础, 看了以下资料用于速成:

教程很丰富, 不必赘述.

相比其他的光线追踪算法, MCPT 可以实现 GPU 并行, 因为虽然算法看似是递归的, 实际上每次只走一条光路. 通过增大采样次数就能解决真实性的问题. 现在最关键的问题是, 如何在 GPU 上运行 KD 树的查询操作, 如果不写效果必定大打折扣, 但是不能直接在原来的基础上写因为, device 上的函数不能调用 host 的函数. KD 树建树可以保持在 CPU 上操作, 之后再复制到 GPU 上, 不是渲染的效率瓶颈. 在 GPU 上写 KD 树的难点在于, 虽然 KD 树查询的期望时间复杂度是 \(O(log(n))\) , 但是最坏情况仍然有 \(O(n)\) 的可能, 而且查询过程并不是一条链, 所以需要栈来储存中间状态, 对于 GPU 执行很不利. Eurographics 2005 的一篇 paper 提出了一个算法, 不需要使用栈.

2017-05-25-01-50-45.jpg

  1. 从根节点找到第一个叶子节点, 如果没有交(fail), 令 tmin 为当先叶子的 tmax, 然后再从根节点开始搜, 循环往复.
  2. 上面的算法有许多重复节点, 所以每次 fail 的时候, 令 tmin 为当前叶子的 tmax, 从叶子往跟回溯, 直到找到一个 bounding box 与 ray 在新区间内有交, 则从当先的右子树开始搜.

如此显然的算法, 然而人家却发了 Eurographics. 那么是不是传统问题的一些“不那么显然”的算法是不是都可以披上一些新鲜问题的外衣发 paper… 不过仔细想了想, 在本机没有 GPU 的情况下进行如此大的代码重构真是够恶心的, 我抑制了这个冲动. 加上了许多优化之后可以较快地渲染面片比较多的图(来自我 github 上的 mode, 20samples + 抗锯齿):

nine-render.jpg

Adaptive Polynomial Rendering

这篇来自 SIGGRAPH 2016, 首要解决的是 MCPT 噪点多的问题, 当 num_sample=32 的时候, 图像轮廓已经成型, 但是噪点颇多, 文中的方法虽然不能让原本模糊的区域变得更清楚, 但是可以把较清晰的区域变得光滑, 定量地来说, rmse 值变低.

算法的主要思想是用泰勒展开局部拟合函数. 具体的参数包括二维坐标, 还有光束射到的目标所对应的纹理, 三维坐标和深度, 多项式的参数可由最小二乘估计而得. 为了选择出最优的多项式系数, 用了一系列的数学技巧做估计. 在原来的代码上只需要加上储存每次采样的信息, 以及每个像素点的参数.

效果

就我目前的估计来看, 用一阶小量和用多阶的效果并没有什么本质上的差别. 从视觉效果上来看, 该算法擅长处理漫反射表面, 但是镜面反射和折射效果捉急, 可以考虑在参数中再加上几维(第二/三次反射之后表面的纹理, 深度位置之类的信息). 效果可以见小学英语水平的报告.

参考

Footnotes:

1

命名来自神秘博士中的迦里弗雷星球(时间领主的母星)。

Author: expye(Zihao Ye)

Email: expye@outlook.com

Date: 2017-04-17

Last modified: 2020-07-30 Thu 01:44

Licensed under CC BY-NC 4.0