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解析


C++多线程编程——C++11 thread初探


引言

由于项目需要,尝试在代码中引入多线程操作。看了一些博客介绍多线程,但普遍为入门级别的教程;尝试在项目中使用,性能又不忍直视,遂决定在博客中记录C++多线程的学习过程。
std::thread是C++11引入的新特性,在此之前只能使用Windows api或Linux的Pthread编写多线程程序,增加了代码跨平台移植的难度。C++11后,我们可以在编程语言层面使用多线程。本系列文章主要探讨C++标准库的多线程。

简单例程

std::thread类声明在头文件<thread>中。下面给出一个最基本的使用例程

// thread example
#include <iostream>       // std::cout
#include <thread>         // std::thread
 
void foo() 
{
  // do stuff...
}

void bar(int x)
{
  // do stuff...
}

int main() 
{
  std::thread first (foo);     // spawn new thread that calls foo()
  std::thread second (bar,0);  // spawn new thread that calls bar(0)

  std::cout << "main, foo and bar now execute concurrently...\n";

  // synchronize threads:
  first.join();                // pauses until first finishes
  second.join();               // pauses until second finishes

  std::cout << "foo and bar completed.\n";

  return 0;
}

该例输出为:

main, foo and bar now execute concurrently...
foo and bar completed.

该段代码首先声明了两个线程并在构造期间传入相应的函数和参数,之后线程就调用相应函数,该函数的参数即由线程构造函数中的参数给出。在线程执行完之前,主线程main等待子线程的执行完成(join)。

小结

本文仅仅示例了std::thread最简单的用法,它只是后续内容的一个引子。希望自己多学习多思考多记录多交流,做出一些微小的贡献。


关于近期工作的一些看法与总结(一)


UAV+VR+Semantic 3D reconstruction,很明显三维重建是核心。目前结合语义的三维重建颇为冷门,仍处于探索阶段,有几个组已经做出了一些开创性工作,但在如何将传统重建方法更好的与DL、ML结合上还有很长的路要走。这个方向是一个趋势,是一片蓝海,而UAV和VR的介入,既是三维重建现实应用的体现,也为三维重建提供了一个工作载体。
以上是近期阅读文献的一些肤浅的感悟。在代码方面,voxel hashing的源码结构上着实有些复杂,读来略显吃力,抛却算法不谈,工程架构就很值得钻研学习,在此深感自身代码能力欠佳。从头复现有些难度,计算在移植到TX2的同时做一些简化,方便后续开发。
以上