简介
这篇文章[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。
文章中给出了二维和三维下的算法伪代码，这里就不列举了。
参考文献
[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解析
0 条评论