基于CUDA实现Ray-Casting
By 猷子
@http://www.cnblogs.com/fengyuheliu/
目录
- 前言
- 三维可视化与体绘制
- Ray Tracing vs. Ray Casting
- 体绘制的加速技术
- 基于CUDA实现Ray-Casting
- 后话
- 参考文献
1.
前言
在读了大牛们的很多深入浅出的科普文章和教程系列并受益匪浅后，不免有自己尝试写写的冲动。本文将尽量平白地阐述一些基本概念和算法流程，同时尽可能多地给出进一步学习所需要的有用资料，一些关键链接就省去了，感兴趣者可以google之。
向乐于分享的大牛们致敬！
2.
三维可视化与体绘制
大家应该对可视化（visualization）这个词并不陌生了。这里限于3D数据场的可视化。譬如，一组CT\MRI切片是人体某个部位（也不限于人体，如客运站的行李安全检查也是CT扫描）的剖面图，逐张切片图像的2D观察不够形象，医学可视化技术就是实现了3D观察。当然也可以漫游这个3D数据场，只要变换观察点和观察角度就可以了。
图1 医学可视化
图2 流体力学模拟
也就是说，我们对现实世界进行采样而得到的一组数据，标识了这个3D空间里的采样点的某些属性；现在，把这个3D模型放在舞台上，用一台虚拟摄像机对它拍照，照片就是我们所需的可视化结果。这里的3D模型，是体模型、体数据，而传统图形学的是网格模型——我们看到的游戏人物，其实就是在建立好的3D网格模型上贴上纹理加入光照，是为“空壳”也！
3D模型不一样，那么渲染技术也不一样吗？两者的确差异很大。现在暂且不说，先讲讲其他几个概念。
3D数据场的可视化技术，可以分为面绘制（surface rendering）和体绘制（volume rendering）。
面绘制，是先抽取出3D数据场里的某个等值面，这个等值面的表示形式，是一个元素为三角面片的数组。这样，接下来用OpenGL/D3D的API函数就可以画出结果了。面绘制常用的方法有MC、MT和dividing cubes等。所以，可以说，面绘制是从原始的3D模型中抽取出我们感兴趣的某个网格模型，而忽略了其他数据。
体绘制，或者叫直接体绘制（DVR, Direct Volume Rendering），就是直接对原始的3D模型进行处理，利用了整个数据场信息。体绘制结果，不单单可以看到表面，还可以透过表面（赋予一定的透明度）看到里面。体绘制的自由度大得多，绘制结果也丰富得多，但是需要处理海量的体数据，不能直接使用图形学API，速度慢得多。其算法族有光线投射法（ray casting）、溅射法（splatting）、错切—变形法（shear-warp）、体元投射法（cell projection）和基于纹理映射（texture mapping）的方法。这样说，对于外行来说，可能还不够清楚，且看下文吧。
有书名为“Real-Time Volume Graphics”，可译为“实时体图形学”。这本书非常经典！记得年初我通过馆际互借从上海图书馆借来捧在手上时，如获至宝！——寻书的过程，也使得我对“诺大一个中国，却无书可读”深有感触。我忘记了“体图形学”是自己的译法还是在哪里见过，我们姑且用这个名称吧。看书中第一章开头：
“This book covers two seemingly very different applications of volume graphics: on the one hand, ‘special effects’ and realistic rendering of clouds, smoke, fire, and similar effects for computer games, movie production, and so forth; on the other hand, the scientific visualization of volumetric data.”
“…both fields rely on the same underlying physical models and therefore use identical, or at least very similar, rendering techniques.”
“Therefore, volume graphics targets the same goal as computer graphics in general: the simulation of light propagation in order to produce images as recorded by a virtual camera.”
到这里，你大概知道“3D模型不一样，那么渲染技术也不一样吗？”的答案了吧。如果还有疑问，又不想花太多时间，可以到“Real-Time Volume Graphics”这本书的主页上下载chapter 2的PPT看看。
3.
Ray Tracing vs. Ray Casting
说到“ray tracing”，先回顾一下我的计算机图形学（CG）学习过程。
开始时，因由做MC算法，把徐波译的《OpenGL超级宝典》翻了一遍，之后也看过OpenGL红宝书——感觉翻译水平有限，还不如看原版，另外推荐NeHe的OpenGL教程——其实学习CG就要做好足够的心理准备要看大量的外文资料。
之后做体绘制时，发觉有必要较为系统地看看CG。看书评，知国人写得较好的图形学教材有唐荣锡的《计算机图形学教程》和彭群生的《计算机真实感图形的算法基础》，浙大的CAD&CG国家key lab不乏牛人。国外有一大堆经典就不说了。
着色语言（shading language）的学习是看《OpenGL着色语言》、NVIDIA的“The Cg Tutorial”和康玉之大牛的《GPU编程与Cg语言之阳春白雪下里巴人》——向康大牛致敬！——不知他近况如何。
还有是随手翻翻了一些经典，如“GPU Gems”系列，也对OpenGPU论坛热衷过一段时间，现在也偶尔去逛逛。这样到现在，算是对CG不再陌生了，但水平很一般。
言归正传！
Ray tracing通常译作“光线跟踪”，而ray casting通常译作“光线投射”。个人觉得两者区别不是很大。Ray tracing是逆向跟踪射入virtual camera的光线，在光线与场景物体的交点处累积来自光源的直接辐照量和反射、折射而来的间接辐照量；而ray casting是向三维数据场投射出光线，然后沿着光线方向积分，数值化方法为由前往后或由后向前合成。
图3 ray casting
图4 ray tracing
4.
体绘制的加速技术
体绘制处理的是海量的数据，如何提高效率是难题。体绘制的加速技术可以分为：软件加速和硬件加速。
软件加速技术有提前光线终止（early ray termination）、空间跳跃（empty space leaping）和延迟渲染（deferred shading）等。这里，空间跳跃的实现，需要对三维数据场进行数据结构管理，如八叉树、二叉树和k-d树，类似于场景管理技术。
硬件加速技术有并行实现、专用硬件实现和GPU加速。其实说GPU加速也欠妥，因为这个概念是NVIDIA在1999年才提出来的。先概述GPU加速的过去与现状吧。——了解科技史，也是学习中必不可少的一环，如：学习编程就应该去了解Unix/C的历史。
最开始是基于二维纹理映射的方法：在虚拟的三维画布上设定好一个组正方形的坐标，然后把切片图像当作纹理贴上去，最后就可以按照一定的规则得到合成图像。
图5 基于二维纹理映射的方法
然后是基于三维纹理映射的方法：也是先设定代理几何体，不过这时代理几何体可以垂直于观察方向。
图6 基于三维纹理映射的方法
随着GPU的渲染管线由固定到可编程的转变，基于纹理映射的方法可以有更多的自由度，能够实现一些复杂的光照效果，而把ray casting由CPU移植到GPU也成为可能。
这几年出现GPGPU：GPU里的众核（就是众多的计算核心）可以用作并行计算。NVIDIA适时地推出CUDA，使得基于CUDA加速体绘制一时成为热点。
5.
基于CUDA实现Ray-Casting
在CUDA SDK里有这样的例程。Heresy大牛写的“CUDA Volume Rendering”对此作了详细的介绍。下面我多此一举，加个流程图吧。
图7 CUDA-based ray-casting算法流程图
传递函数：input为表征3D数据场中重采样点的属性值，如灰度值、梯度值和曲率等；output为重采样点处的光照属性值，如不透明度、颜色等。传递函数实质上是对3D数据场的分类，是可视化技术中的十大难题之一。1D传递函数（灰度—不透明度，和灰度—颜色值）效果有限，增加维度（如梯度值）设计高维传递函数可以更好地区分开各种物质，而当前的研究热点是先用模式分类的方法识别出3D数据场中的感兴趣部分。
图8 一维传递函数
图9 二维传递函数
【注】重采样：对离散3D数据场的采样，常用三线性插值，而为了更精确复原重采样点处的信息，可以使用复杂度更高的算法，如B样条插值。
6.
后话
Ray casting的最后一步是由前往后或由后向前。这可以理解成简单的融合——可以参照“Jim Blinn’s Corner”中的“compositing”两篇文章，也可以理解成光线吸收—发射模型中光照积分的离散方法。这个问题在接下来探讨预积分（pre-integration）的文章会有更详细的讲述。
上文对光照模型说得很少。这可以参照“Real-Time Volume Graphics”。Joe Kniss曾经在体绘制领域活跃过几年，也做了不少重量级的贡献。他用基于三维纹理映射的方法，实现了阴影和多重散射效果。在一系列的关于“Advanced Illumination Techniques for GPU Raycasting”的conference tutorials中，Christof Rezk Salama具体阐述了他在raycasting中添加多重散射效果的方法。他是渲染多个等值面，在等值面之间计算多重散射，分为多个pass，并在“first hit pass”中计算local illumination和ambient occlusion。Christof Rezk Salama的想法源于Joe Kniss。
我想，这两种实现做了很有意义的探索，而未来将会——现在大概也有了——是先用模式识别分类好物质，然后实现各种各样的光照效果。
【注】统称为“Advanced Illumination Techniques for GPU Raycasting”的tutorials其实都一样，只是在不同的conference中有不同的名字。这个tutorials还讲述了体数据结构的组织、多分辨率绘制和多规模数据处理等。
【注】听说Joe Kniss跑去做模式识别了，不知真否。
图10 Joe Kniss's
图11 Christof Rezk Salama's
7. 参考文献
在上面已经提及了不少，这里就略去了。
"