【GPU编程】体绘制之用Summed-Area table判断体数据块是否透明

在体绘制（Volume Rendering）中，经常用到的一种加速技术是透明区域块跳跃技术（Empty Space Skipping）。透明区域块，顾名思义，就是这个块中各个体素对应的α（不透明度值或者叫阻光度值，依据传输函数映射而来）等于零。由于等于零的体素对于最终的绘制结果并没有绘制作用，因此跳过这些体素，不对其进行采样与合成计算可以起到加速的作用。

为了实现透明区域跳跃技术，首先需要将3D体数据划分为等大小的块（brick），块大小一般为16*16*16或者是32*32*32比较合适，太大的话，容易造成透明块数量太小，块划分太小的话会增加计算量。然后我们在体绘制的时候，很重要的一个步骤是需要判断块是否透明。下面就介绍一种高效的寻找透明块的方法。最常用的方法就是最小值-最大值编码和建立summed-area table。

Summed-Area table是依据体素对应的阻光度值如下计算的：

S(0) = α(0)

S(k) = S(k - 1) + α(k)

k的取值范围是[0,MaxScalarValue]即整个体数据的灰度范围比如[0,4095]，MaxScalarValue是体数据中最大的灰度值。

我们在划分块的时候，需要记录每个块中体素的最大值Imax和最小值Imin。这样，位于范围[Imin,Imax]之间的阻光度值之和可以如下查表计算得出：

（1）

如果S(Imax) - S(Imin)等于零，那么可以判断块是透明的，可以跳过。

这个时候，我们需要注意的是，针对传输函数两种分类方法Pre-Classification和Post-Classification（参考：体绘制传输函数-分类(Volume Rendering Transfer function：Pre- VS Post-Classification)），是有所区别的。对于后者，前面提到的min-max编码方法得出的结果要更加准确一些。因为是先对标量数据值进行插值，再进行传输函数映射，所以在最小值和最大值之间的所有值都有可能出现。但是如果采用的是Pre-Classification，当应用于较大的数据区域时，这个编码方法显得粒度太大，会丢失很多信息。

看下图，它显示了上述的min-max编码方法无法满足要求的情形：

上图显示，如果采用的是Pre-Classification，那么min-max编码的粒度问题。如果非透明对于的标量值的范围是130到150，那么一句此方法将会得出两个块均是非透明的。但事实是块1是透明的而块2是非透明的。

为了解决Pre-Classification这一问题，我们采用一个更加完善的数据结构，比如量化二值直方图，其一般编码方法为：

（2）

在这个式子中，B是某一个块中所有标量值的集合。值为1意味着该灰度值至少在块中的某一个网格点上面出现过，否则就是通过插值得到的。

这个编码方法比较有效，但是通常在内存使用方面不高效。

除此之外，我们可以对灰度值区间进行量化：

（3）

如果灰度值x取值范围是[0,4095]，那么i取值范围就是[0,31]。上式取值为1的意义是：存在某个网格点，其对应的灰度值位于区间[128*i,128*(i+1)]内。在预处理阶段，每个块被解析并编码。

同样的编码方式可以应用在传输函数的阻光度上：

（4）

x和i的意义同上面的式子。在灰度区间[128*i,128*(i+1)]内，存在传输函数映射之后阻光度不为零的值。每当传输函数发生变化，需要重新编码。

这样，我们就可以依据下式判断一个块是否透明:

（5）

式子（5）的含义是式子（3）和（4）不同时满足：在某个灰度区间段内，要么没有网格点在此范围内，要么在传输函数映射之后没有阻光度值不等于0.这就满足了块为透明的要求。

注意，上述方法仅适用于Pre-Classification的方法。

参考资料：

《Memory efficient acceleration structures and techniques for cpu based volume raycasting of large data》

《Advanced Illumination Techniques for GPU-based Volume Rendering-SIGGRAPH 2009 Course Notes》