三维数据场体绘制研究进展

何丽君，王晓强，云 健，包书哲

(大连民族学院计算机科学与工程学院，辽宁大连 116605)

三维数据场体绘制研究进展

何丽君，王晓强，云 健，包书哲

(大连民族学院计算机科学与工程学院，辽宁大连 116605)

介绍了体数据场按物理特征和几何特征的分类，综述了三维数据场体体视化的两类绘制算法——面绘制和直接体绘制，描述了各种体绘制算法的基本思想，分析比较了相应的关键技术，详细讨论了体绘制技术的最新研究进展。

体数据场;体绘制;空间域;变换域

三维体数据处理及可视化的研究工作及应用实验十分活跃，其技术水平正在从后处理转向实时交互控制发展，并且将其与超级计算机、光纤高速网、高性能图形工作站及虚拟现实等新技术结合起来，成为这一领域技术发展的重要方向。三维数据场可视化［1，4］主要是指运用交互计算机图形学和图像处理及计算机视觉技术，将大量的数据转换为直观的图形和图像信息在计算机屏幕上显示出来，供人观察研究，并进行交互处理的理论、方法和技术，包括体数据的表示、操作和绘制［5］。体数据描述的是三维(可能是时变的)实体及其内部性质，是对某个物理场的离散采样，没有明确的表面和边界。体数据可以通过采样、仿真或模型技术获取，例如:由磁共振成像(magnetic resonance imaging，MRI)或计算机断层摄影(Computed Tomography，CT)得到一系列二维切片数据构成三维体数据。

几何图元的绘制方法已经比较完善，早期的体绘制方法都是逼近体数据的一个等值面，然后使用几何图元绘制方法对等值面进行绘制的办法。当体数据的绘制使用面绘制技术时，体数据的内部信息就会丢失，只能绘制表面信息。近年来大量技术应用于体绘制，产生了直接体绘制技术描述全部的三维信息，直接体绘制技术比面绘制描述的信息多，但绘制时间长，计算复杂。为了提高绘制效率，出现了大量优化方法和加速技术。

1 体数据场及其绘制方法分类

体数据场是由一些称为体素(voxel)的采样点数据(x，y，z，v)构成的集合 V，这些采样点数据(x，y，z，v)表示在三维位置(x，y，z)的数据一些性质的值为v。根据采样点取值特点和采样点位置分布特点可以对体数据场进行分类。

根据采样点数据的物理特征，可将体数据场分为二值数据场、标量数据场、向量数据场和时变数据场四类。在每个三维空间位置，采样点v的取值可以是二值、标量、向量或者时变值。若v的取值只取两个值:0和i，其中0表示背景，i表示对象I，此时称为二值数据场;若v的可取多个值，用来描述可度量标量性质，如灰度、密度、温度、压力等，只有大小而无方向，称为标量数据场;若v是向量，比如用来描述每个位置的速度，不仅有数值的大小，还有方向的变化，称为向量数据场;若v是时变的，此时数据场变为四维采样点数据(x，y，z，t，v)的集合，称为时变数据场。

根据采样点空间分布几何特征［6］，可将体数据场分为结构化数据场和非结构化数据场两类。非结构化的又称为散乱的数据场。若数据场在逻辑上是较规整的，则称为结构化的。结构化数据场又可进一步分为规则结构化和非规则结构化数据。非规则结构化网格数据也称曲线(Curvilinear)型网格数据，这类数据中，每一体素是逻辑上的六面体，相对的面并不要求平行，且每一面的四个定点可以不共面。规则结构化网格数据包含笛卡儿型、等距型、矩形型三种类型，笛卡儿型(均匀网格型):建立在笛卡尔坐标系上的体数据。每一个体素大小相同、也各维比例也完全相同，按照坐标轴方向均匀排列成正方体形状。等距型的所有体素大小相同，按坐标轴方向排列成长方体。矩形型:沿每一坐标轴，体素间距各不相同，但体素仍是沿坐标轴排列的长方体。一般地，非规则结构化网格数据和非结构化网格数据可以通过计算几何方法转化成规则结构化体数据，所以只需考虑规则结构化体数据。

1.1 体数据场的插值

在体绘制中，要绘制的对象本身最原始的时候都应该是连续的信号(数据)。而体绘制中最初的输入都是通过采样得到的三维离散数据场。体绘制算法中为了真实、准确地反映原始数据的特征，在绘制前，首先要将这些离散的数据重构成连续的三维数据场，然后根据绘制分辨率对重构的连续信号进行重新采样，最后选择某种具体的体绘制算法进行渲染。通常通过插值来完成三维数据场的重构，体绘制图像的质量很大程度上取决于所用的重构(插值)函数的精确度，另外重采样过程是制约体绘制运算速度的一个关键因素。

1.2 体数据场绘制方法分类

根据数据描述方法和绘制方法的不同，体视化技术可以分为两大类:面绘制方法(Surface Based Rendering，SBR)［7－8］和直接体绘制方法(DirectVolumeRendering，DVR，简 称 体 绘制)［9－16］。随着研究的不断深入，每一种技术又包含很多具体方法，如图1是体视化技术分类图。面绘制是指体表面的重建，它可以有效地绘制三维体数据的某个表面，但缺乏体数据内部信息的表示;体绘制也称为直接体绘制，直接由体数据生成三维体的图像，以体素作为基本单元，能够表示体数据的内部信息，但相应的计算量大，包括体数据的采样、重构、重采样、绘制等操作。

图1 体视化技术分类图

2 面绘制

在面绘制中，首先由三维空间数据场构造出中间几何图元(多边形或三角形面片)来逼近等值面，即逼近数据场中满足某一特性的物质，然后利用已有的算法对等值面进行光照计算和渲染。面绘制方法可以利用现有的图形硬件对绘制进行加速，使生成图像及其变换的速度加快，并且可以产生的等值面图像较清晰。然而面绘制方法生成的图像只能反映原始三维数据场的局部信息，不能反映其全局信息，生成的图像也不够精细，而且该方法需要对数据进行二值分割来生成等值面，分割精度要求较高。目前常见的面绘制方法有以下四种:轮廓线连接法、移动立方体法、移动四面体法和剖分立方体法。

2.1 轮廓线连接法

轮廓线连接法是首先提取每层图像的轮廓线，然后选取不同图像层间轮廓线上的顶点，连接这些顶点形成三角面片，最后通过光照计算进行渲染。

轮廓线连接法存在对应问题、镶嵌问题和分支问题，因此只适用于层间等值面变化较小或者具有几何形状上比较相似，且绘制精度要求较低的场合，这些缺点限制了轮廓线连接法的进一步应用。

2.2 移动立方体法

移动立方体方法是最有影响的面绘制重建方法，是进行规则体数据场等值面生成和绘制的经典算法。由两层间8个相邻体素构成的体素内部构造代表等值面的三角面片，首先根据二值分割确定的等值面，然后在每一个体素内逐个比较其顶点值，判断其位于等值面内或等值面之外。如果体素的一条边两个顶点一个在等值面内，一个在等值面外，则表示等值面与该边相交，求出其交点坐标，将这些交点作为三角面片的顶点。

虽然移动立方体方法的基本算法存在面片过多和二义性(Ambiguity)的缺陷，但经过改进后，现已经广泛用于各种体数据的可视化。

2.3 移动四面体法

移动四面体法的主要目的是为了解决移动立方体法二义性问题，首先将立方体体素剖分成四面体，然后在四面体内部构造等值面。

由于四面体是构成任何类型的多面体的基本元素，是最简单的多面体，因此移动四面体法比移动立方体法应用面更广。此外，移动四面体法比移动立方体法构建的等值面精度更高。

2.4 剖分立方体法

当离散三维数据场的密度很高，接近或者超过计算机屏幕的显示分辨率时，采用移动立方体法构造的三角面片与屏幕像素大小差不多，甚至更小，此时不必通过插值来计算小三角面片，剖分立方体法正好改进移动立方体法的这个缺点。

剖分立方体法和移动立方体法一样对数据场中的体素逐一进行处理。当某一个体素8个顶点的体素值中有的在值面内，有的在等值面外，且此体素在屏幕上的投影大于屏幕像素时，则将此体素沿x，y，z三个方向进行剖分，直到体素都在等值面之内或都在等值面之外或者其投影等于或小于像素，将投影等于或小于像素的小体素投影到屏幕上，形成所需要的等值面图像。

3 直接体绘制

直接体绘制方法不构造中间几何元素，直接将三维数据场投射到二维屏幕上，能生成三维数据场的整体图像，包括体数据内部信息，绘制的图像质量高，能得到数据深度信息。但其计算量巨大，且很难利用传统的图形硬件进行加速，导致计算时间较长。然而，直接体绘制近年来发展迅速。

3.1 空间域体绘制

空间域体绘制方法的实质可概括为三维数据场的重采样和颜色合成两大步骤。根据绘制次序，空间域体绘制算法可以分为三类:以图像空间为序(简称像序)的体绘制算法、以对象空间为序(简称物序)的体绘制算法、及图像和对象空间混合序(混合序)的体绘制算法。

(1)像序体绘制算法由屏幕的像素点发出光线穿过数据场决定像素颜色值。其具有下述两个共同特点:一是从屏幕上的每一个像素点出发，根据视点位置，发射穿过三维体数据场的光线，沿这些光线进行离散化采样，按照一定原则选取若干重采样点;二是通过插值近似计算这些重采样点间的颜色和不透明度融合计算，计算对应屏幕像素的颜色。常见的像序体绘制方法根据采样方式和模式的不同包括X线绘制、最大强度投影法和等值面绘制三种模式，其中X线绘制算法直接将插值后的重采样点直接和值作为像素颜色，最大强度投影法则直接使用插值后的重采样点的最大值作为像素颜色。

(2)物序体绘制算法将体数据映射到二维的图像屏幕，将对二维屏幕像素的有影响的每一个体素的贡献计算出来，然后将其合成为像素的颜色来绘制图像，生成图像的步骤如下:首先将每一个体素点投影到屏幕空间的坐标，计算对屏幕的影响范围和贡献，Splatting算法是一种典型的物序体绘制算法。

(3)混合序体绘制算法结合了像序体绘制和物序体绘制算法两种算法的优点。它通过将三维离散数据场的投影变换分解为Shear变换和Warp变换，实现将三维空间的重采样简化为二维平面的重采样，减少了大量计算量，在不显著降低图像质量的前提下，可以在微机上接近实时速度绘制体数据。但由于Shear－Warp算法对二维图像空间的采样不可能得到完整、正确的三维信息，是以牺牲图像质量和准确性为代价来加速绘制的。

3.2 变换域体绘制

变换域体绘制首先将空间体数据变换到变换域，然后在变换域内直接生成投影或借助变换域的信息生成投影，从而进行显示。常见的变换域包括压缩变换域、频域和小波域，因此，对应的变换域体绘制方法有压缩域体绘制、频域体绘制和小波域体绘制。

(1)压缩域体绘制是不需要将压缩后的数据进行解压缩，直接在压缩域进行绘制，不需要装入全部未压缩的体数据，绘制结果可以立即显示。因此对计算机的内存、计算和传输要求降低，加快了绘制速度，是将绘制与压缩进行有机结合的好方法。首先在空间域对体数据用向量量化技术进行压缩，然后直接对量化块用一般的空间体绘制方法进行绘制。

(2)频域体绘制算法是根据Fourier切片定理提出来的，是在频域中进行体绘制过程的技术。根据Fourier切片定理，在三维数据场经过Fourier变换后相对应的频域场中，按视线方向抽取一个经过原点的截面，再对这个截面做Fourier逆变换，得到的恰好就是在空域中的图像平面的投影。频域体绘制先对三维数据场进行三维快速傅里叶变换，得到数据场的频域表示，然后对任意投影方向(即观察方向)，在频域内通过原点且垂直于投影方向的平面内进行二维切片重采样，最后对二维采样得到的数据场进行二维Fourier逆变换，即得到空间域表示的三维数据场沿投影方向的二维平行投影图像。

(3)小波域体绘制首先对体数据进行三维离散小波变换，将体数据进行多分辨率表示，并进行数据压缩;在绘制阶段，不需要执行任何解压缩操作，直接将小波变换的小波系数代入体绘制方程生成二维图像。小波变换具有在空间域和频域同时具有局部性质，可以用少量小波系数表示体数据。

4 优化网格数据的体绘制技术

优化网格是指以截八面体为体素的体心立方(body－centered cubic)网格和以菱形十二面体为体素的面心立方(face－centered cubic)网格。优化网格上的体素分布比立方网格更加紧凑和合理，在三维空间具有更好的采样性质，有关优化网格的直线生成［17］、Fourier变换［18］和立体显示［19］的研究日益活跃。运用采样性质更好的面心立方网格和体心立方网格代替传统的笛卡尔网格，在不影响质量的前提下，能减少大约30%的数据量，从而提高体绘制速度。因此，与立方网格体视化技术类似，根据数据描述方法和绘制方法的不同，优化网格体视化技术可以分为两大类:面绘制方法和直接体绘制方法，其中直接体绘制方法按处理数据域的不同可分为优化网格空间域方法和优化网格变换域方法，优化网格空间域体绘制可以分为三类:优化网格像序体绘制算法、优化网格物序体绘制算法、优化网格混合序的体绘制算法。

关于优化网格面绘制方法，Carr等人［20］提出了体心立方网格上的移动八面体法、改进的移动八面体法和改进的移动六面体法，这些算法都生成体心立方网格体数据场的等值面。体心立方网格可视为由两个交错的立方网格构成，分别称为主网格和次网格。构造采样网格最简单的方式为对角连接主网格和次网格点的Delaunay体元，这些Delaunay体元均为四面体，在主网格和次网格上具有公共边的4个四面体可以组成一个八面体，这些八面体能铺满整个三维空间，与移动立方体算法类似，可以得到移动八面体算法，该算法同样存在二义性的缺陷，但生成的三角面片数目比移动四面体算法少。移动六面体算法则是将具有公共对角边的四面体组成六面体。Strand等人［21］则提出了面心立方网格上的类似于移动立方体法的等值面生成算法。

优化网格像序体绘制算法中，Ibáñez等人［22］将光线投影算法推广到体心立方网格和面心立方网格，为了对穿过三维体数据场的光线进行采样，提出了任何结构化网格上的直线向量遍历算法逐个生成体素，并提出了四种策略(双线性插值、三线性插值、重心插值和剪切三线性插值)进行重采样。

优化网格混合序体绘制算法将像序体绘制和物序体绘制算法有机结合起来。Sweeney等人［23］将Shear－Warp算法推广到体心立方网格。由于体心立方网格可看成交错的两个立方网格构成，因此体心立方网格体数据可以非常方便地分解为两个立方网格体数据，然后分别对这两个立方网格体数据进行Shear变换和二维图像的Warp两步，最后再将其合成，值得注意的是在Z轴方向有半个网格距离的偏移量。

优化网格的变换域体绘制算法在最近几年被相继提出，Dornhofer在他的博士毕业论文［24］中建立了一般规则网格上的离散Fourier变换公式并将其应用于体心立方网格的频域体绘制。Alim等人［25］给出了面心立方网格和体心立方网格的一种快速Fourier变换算法。文献［26］和［27］提出了应用体心立方网格Box样条进行体绘制的算法。

5 体绘制的加速技术

由于体数据场的数据量巨大，体绘制计算复杂度较高，计算较为费时，导致体绘制速度与用户要求实时、交互进行显示处理之间的矛盾越来越严重。为解决这类矛盾，研究者提出了大量优化体绘制的加速技术。这些加速技术主要包括软件算法优化和图形硬件加速两类方法。

在软件算法优化方面［28］，主要有两大类技术可以有效提高体绘制算法速度:第一类是空间数据结构优化，这类技术使用八叉树、k－d树、索引表、距离变换等数据结构对体数据进行优化和编码，剔除无效体素，达到体绘制加速的目的。第二类称为提前不透明度截止，这类方法基本思想是:在应用由前向后融合算法的体绘制过程中，当累积的不透明度达到一个预先设置的阈值时，光线可以到达的任何其它体素可以不作处理，因为其将被遮挡。

在图形硬件加速［29］方面，针对体绘制算法不能很好的借助传统的图形硬件加速的问题，研究者开发设计了专用体绘制体系结构。

针对大规模和超大规模体数据，并行和分布式体绘制研究［30－32］也取得了很大进展。根据各处理器间分配的数据类型不同，目前提出的并行体绘制主要可以分为两大类:一类是基于图像空间数据划分的并行算法，比较适合于像序体绘制算法的并行计算。另外一类基于对象空间数据划分的并行算法，比较适合于物序体绘制算法的并行计算。

6 体绘制研究展望

随着数据场规模的不断膨胀，数据量越来越巨大，体绘制技术不能满足人们对数据场进行实时、精确、交互操作的要求。因此，提高算法效率是体绘制的发展方向，具体有以下几类:一是设计和开发专用的体绘制相关的硬件加速设备;二是设计分布式并行体绘制算法，以满足实时交互的要求;三是将硬件加速设备和分布并行算法相结合。

［1］ DEFANTI TA，BROWN MD.Brown.Visualization in Scientific Computing［J］.Advances in Computers，1991，33:247－307.

［2］DEFANTI TA，BROWN MD，MCCORMICK BH.Visualization:Expanding Scientific and Engineering Rendering Opportunities［J］.Computer，1989，22(8):12 －16.

［3］石教英，蔡文立.科学计算可视化算法与理论［M］.北京:科学出版社，1996.

［4］唐泽圣，孙延奎，邓俊辉.科学计算可视化理论与应用研究进展［J］.清华大学学报:自然科学版，2001，41(4/5):199－202.

［5］MIN C，ARIE K，RONI Y.Volume Graphics，Springer［M］.London，February，2000.

［6］DON S，STEVE K.Volume probes:Interaetive data exploration on arbitrary grids［J］.ACM SIGGRAPH Computer Graphics，1990，24(5):5－12.

［7］ Marc L.Display of Surfaces from Volume Data，IEEE Computer Graphics＆Applications［J］.1988，8(3):29 －37.

［8］LORENSEN WE，CLINE HE.Marching cubes:A high resolution 3D surface construction algorithm［J］.ACM SIGGRAPH Computer Graphics，1987，21(4):163 －169.

［9］WESTOVER L.Footprint evaluation for volume rendering［J］.ACM SIGGRAPH Computer Graphics 1990，24(4):367－376.

［10］LACROUTE P，LEVOY M.Fast volume rendering using a shear－ warp factorization of the viewing transformation［C］.Proceedings of the 21st annual conference on Computer graphics and interactive techniques 1994:451－458.

［11］SWEENEY J，MUELLER K.Shear－ Warp Deluxe:The Shear－ Warp Algorithm Revisited［C］.Proceedings of the symposium on Data Visualisation 2002:95 －105.

［12］ BUNEMAN O.Conversion of FFT＇s to fast Hartley transforms［J］.SIAM Journal on Scientific and Statistical Computing，1986，7(2):624－638.

［13］MALZBENDER T.Fourier volume rendering［J］.ACM Transactions on Graphics，1993，12(3):233 －250.

［14］LEVOY M.Volume rendering using the Fourier projection－slice theorem［C］.In Proceedings of the Graphics Interface ＇92，1992:61 －69.

［15］TOTSUKA T，LEVOY M.Frequency domain volume rendering［J］.Computer Graphics SIGGRAPH ＇93 Proceedings，1993，27(4):271 －278.

［16］GROSS M H，LIPPERT L，DITTRICH R，et al.Two methods for wavelet－ based volume rendering［J］.Computers and Graphics，1997，21(2):237－252.

［17］何丽君，刘勇奎，孙世昶.三维面心立方网格上的直线生成算法［J］.计算机学报，2010，33(12):2407－2416.

［18］姚继锋，孙家昶.平行十二面体区域上的快速离散傅立叶变换及其并行实现［J］.数值计算与计算机应用，2004(4):303－314.

［19］李莉，杨忠，邢建芳，等.面向立体显示的点采样栅格优化策略及其性能分析［J］.山东大学学报(工学版)，2008，38(3):1－6.

［20］CARR H，THEU?L T，M?LLER T.Isosurfaces on Optimal Regular Samples［C］.Proceedings of Eurographics Visualization Symposium，2003:39－48.

［21］ STRAND R，STELLDINGER P.Topology Preserving Marching Cubes－like Algorithms on the Face－Centered Cubic Grid［C］.Proceedings of the 14th International Conference on Image Analysis and Processing，2007:781－788.

［22］IB??EZ L，HAMITOUCHE C，ROUX C.A Vectorial Algorithm for Tracing Discrete Straight Lines in N － Dimensional Generalized Grids［J］.IEEE Transactions on Visualization and Computer Graphics，2001(7):97 －108.

［23］SWEENEY J，MUELLER K.Shear－ Warp Deluxe:The Shear－ Warp Algorithm Revisited［C］.Proceedings of the symposium on Data Visualisation，2002:95 －105.

［24］DORNHOFER A.A Discrete Fourier Transform Pair for Arbitrary Sampling Geometries with Applications to Frequency Domain Volume Rendering on the Body－Centered Cubic Lattice［D］.Vienna:Vienna University of Technology，2003.

［25］ALIM UR，M?LLER T.A fast Fourier transform with rectangular output on the BCC and FCC lattices［C］.Proceedings of the eighth international conference on sampling theory and applications(SampTA ＇09)，Marseille，2009.

［26］ ENTEZARI A，VAN DE VILLE D，M?LLER T.Practical box splines for volume rendering on the body centered cubic lattice［J］.IEEE Transactions on Visualization and Computer Graphics，2008，14(2):313 －328.

［27］BERNHARD F，ALIREZA E，DIMITRI V，et al.Efficient volume rendering on the body centered cubic lattice using box splines［J］.Computers＆ Graphics，2010，34(4):409－423.

［28］HERNELL F，LJUNG P，YNNERMAN A.Local Ambient Occlusion in Direct Volume Rendering［J］.IEEE Transactions on Visualization and Computer Graphics，2010，16(4):548 － 559.

［29］JENS S，MARTIN K，R?DIGER W.GPU －Based Euclidean Distance Transforms and Their Application to Volume Rendering［J］.Communications in Computer and Information Science，2010，68(4):215－228.

［30］KWAN －LIU M，JAMES S，CHARLES D，et al.Parallel volume rendering using binary－swap image composition［C］.ACM SIGGRAPH ASIA，2008.

［31］PETERKA T，HONGFENG Y，ROSS R，et al.Endto－End Study of Parallel Volume Rendering on the IBM Blue Gene/P［C］.International Conference on Parallel Processing，2009.Vienna，566 － 573.

［32］Jeff AS，Cheng－Kai C，Kwan－Liu M，etal.Multi－GPU volume rendering using MapReduce［C］.Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing，2010.

Recent Advances in Volume Rendering for 3D Data Sets

HE Li－jun，WANG Xiao－qiang，YUN Jian，BAO Shu－zhe
(School of Computer Science＆ Engineering，Dalian Nationalities University，Dalian Liaoning 116605，China)

Volume rendering for 3D data sets，a hot research topic in computer graphics，has important significance in science and worthiness in practical application.Volume data sets are classfied by physical characteristics and geometrical characteristics.The basic ideas and the key techniques of the two kinds of methods of the 3D data sets called surface rendering and direct volume rendering，are introduced into this paper.The recent advances in volume rendering is discussed in detail.

volume data sets;volume rendering;spatial domain;transform domain

TP391

A

1009－315X(2012)05－0486－06

2011－11－16;最后

2012－02－28

辽宁省教育厅科学技术研究项目(L2010096);中央高校基本科研业务费专项资金资助项目(DC10010114);大连民族学院青年基金(2007A204)。

何丽君(1974－)，女，湖南新邵人，副教授，博士研究生，主要从事计算机图形学、计算几何、数据库技术研究。

(责任编辑 刘敏)