分类 Paper reading 下的文章

A Fast Voxel Traversal Algorithm for Ray Tracing解析


简介

这篇文章[1]提出了一种用于光线追踪的三维体素遍历算法。[2]中voxel block的分配环节采用了该算法来计算和当前视角下的ray相交的block。算法本质上属于一种数值微分法(Digital Differential Analyzer, DDA),能够将离散数据模拟出连续的特性,举例来讲,一张图片由一组离散的二维点表示,要在上面画出一条斜线,则需要决定何时在X或Y方向上前进。该类插值问题可以通过DDA解决,记得本科的CNC这门课就有讲过DDA算法。

具体实现

首先考虑二维的情况,三维同理。请看下图,一个正确的遍历算法应该按照a, b, c, d, e, f, g和h的顺序访问各个体素。ray的方程为$\vec{u}+t\vec{v}, t>0 $。$u$实际上是ray的起点坐标,$v$为ray的方向,$t$则为每一步的步进长度。该遍历算法将ray以间隔为$t$的大小分割,分割后的每一段都横跨一个体素。我们从ray的起点开始按照顺序访问每个体素。
该图中ray的起始位置是block a。记此时的ray与第一条垂直线相交的$t$为$tMaxX$,和第一条水平线相交的$t$为$tMaxY$。若$tMaxX < tMaxY$,则在X方向上前进$stepX$,反之则在Y方向上前进$stepY$。$stepX$和$stepY$为+1或者-1,由$v$的方向决定,表示ray在当前block的位置在X或者Y方向上前进或者后退一个block。
继续以该图为例,ray的起点在block a,在点1处与第一条垂直线相交,在点2处与第一条水平线相交,此时$tMaxX < tMaxY$,所以在X方向上前进一个block,ray的位置则右移到达block b。以block b中ray的某点为起点,在点3处与第一条垂直线相交,在点2处与第一条水平线相交,此时$tMaxX > tMaxY$,所以在Y方向上前进一个block,ray的位置则上移到达block c。以block c中ray的某点为起点,在点3处与第一条垂直线相交,在点6处才与第一条水平线相交,此时$tMaxX < tMaxY$,所以在X方向上前进一个block,ray的位置右移到达block d。以此类推,依次遍历block e,f,g,h。
20171206094701216.png
文章中给出了二维和三维下的算法伪代码,这里就不列举了。

参考文献

[1] AMANATIDES, J., AND WOO, A. 1987. A fast voxel traversal algorithm for ray tracing. In Proc. Eurographics, vol. 87, 3–10.
[2] Nießner, Matthias & Zollhöfer, Michael & Izadi, Shahram & Stamminger, Marc. (2013). Real-time 3D Reconstruction at Scale using Voxel Hashing. ACM Transactions on Graphics (TOG). 32. 10.1145/2508363.2508374.
[3] voxel hashing解析