（计算机应用技术专业论文）光互体绘制关键技术及其应用研究.pdf

中文摘要体视化尤其是其中的体绘制是三维数据场可视化领域晟重要、近年来发展最迅速的一项技术，在医学三维重建、计算流体力学、有限元后处理、地震地质等众多领域得到了广泛应用。但是目前体绘制研究中存在很多亟待解决的问题，本文主要就其中制约交互体绘制的几个关键问题：包括体绘制加速技术、绘制图像质量改进方法、灵活科学的体绘制参数设置和调节等问题进行了深入研究。其中，针对传统光线投射算法计算复杂度高、绘制速度慢的缺点，本文提出了通过提自u 梯度估计、分类着色和明暗计算来降低重采样点计算量的加速光线投射算法，该方法可以有效提高光线投射算法的速度而不明显降低绘制图像质量。针对s p l a t t i n g 算法计算复杂度为o ( n 3 ) 的特点，本文首次将游程编码技术应用于物序体绘制，提出了基于游程编码体数据和屏幕图像扫描线的新型帧缓冲s p l a t t i n g 算法。该算法采用了提前分类、提前明暗计算的策略，通过游程编码体数据，实现了对透明体素的有效易4 除，通过新型的体素遍历方法实现了不透明度截止，大大加速了s p l a t t i n g 算法的绘制速度。为了能够解决s p l a t t i n g 算法计算不准确、存在多种走样现象的问题，本文提出了一种基于v i e w b u f f e r 的新型s p l a t t i n g 算法，新算法采用了v i e w b u f f e r而没有使用帧缓冲，并且通过定义平行于v i e w b u f f e r 的体素遍历策略和预先计算好的重构核查找表进行绘制，有效消除s p l a t t i n g 算法中重叠问题和p o p p i n g走样，也能够较好地降低积分问题对绘制图像的影响。为了优化体绘制算法的关键步骤重采样过程，本文提出并实现了一种通过两熏查找法进行重采样的新型物序体绘制方法。这种方法在继承物序体绘制算法优点的基础上，不仅能够最大限度预处理一部分计算，而且更符合重构采样理论、因而可以以较低的计算代价获得比s p l a t t i n g 更高质量的绘制图像。针对当前传递函数设计缺乏理论指导的问题，通过分析基于体数据局部三维图像矩所确定的惯量矩阵特征值，本文提出了一种新型的半自动化的数据驱动传递函数设计方法。该方法首次将局部形状特征引入传递函数设计，扩展和丰富了传递函数的定义域。并且具有计算简单、快速的特点，而且能够完成基于边界检测的传递函数所具有的功能。设计实现了面向医学三维重建的可视化系统v o l g r a p h ，在提供医学图像处理功能的同时，系统还集成了移动立方体、光线投射及s p l a t t i n g 等体视化算法。关键词：科学计算可视化，体绘制，光线投射，s p l a t t i n g ，游程编码，两重熏构查找法，传递函数a b s t r a c tv o l u m ev i s u a l i z a t i o ne s p e c i a l l yv o l u m er e n d e r i n gh a sb e e nt h em o s ti m p o r t a n ta n dr a p i dd e v e l o p e dt e c h n i q u e si nt h ev i s u a l i z a t i o no ft h r e e d i m e n s i o n a ld a t as e t si nr e c e n ty e a r s h o w e v e r , t h e r ea r es t i l ls o m ed i f f i c u l ti s s u e sn e e dt ob es t u d i e df u r t h e r ,i n c l u d i n gs e v e r a lk e yt e c h n i q u e s ：n e wa c c e l e r a t i n gm e t h o d s ，n e wr e n d e r i n gi m p r o v e m e n tt e c h n i q u e s ，f l e x i b l es e t u pa n dt u n i n gm e t h o d sf o rr e n d e r i n gp a r a m e t e r s ，w h i c ha r et h em a i nt o p i c so ft h i sp a p e r f i r s t ，b e c a u s et r a d i t i o n a lr a yc a s t i n ga l g o r i t h ms u f f e r sf r o mh i l g hc o m p u t a t i o n a l c o m p l e x i t ya n dl o wr e n d e r i n gs p e e d ，an e wr a yc a s t i n ga c c e l e r a t i n ga l g o r i t h mi sp r e s e n t e di nt h i sp a p e r t h em a i ni d e ao ft h en e wa l g o r i t h mi st or e d u c et h ec o m p u t i n gt i m eo ft h er e s a m p l i n gp r o c e s sb ya d o p t i n gap r e - g r a d i e n te s t i m a t i o n ，p r e 。c l a s s i f i c a t i o na n dc o l o r i n g ，p r e s h a d i n gs c h e m t h en e wa l g o r i t h mc a ne f f i c i e n t l ya c c e l e r a t er a yc a s t i n ga l g o r i t h mw i t h o u tt r a d e - o f fi m a g eq u a l i t yo b v i o u s l y s e c o n d ，a c c o r d i n gt ot h eo ( 3 ) c o m p u t a t i o n a lc o m p l e x i t yo fs p l a t t i n ga l g o r i t h m ，ar u nl e n g t he n c o d i n g ( r l e ) a c c e l e r a t e d ，p r e c l a s s i f i c a t i o na n dp r e s h a d i n gs h e e t - b u f f e rs p l a t t i n ga l g o r i t h mi sp r e s e n t e di nt h i sp a p e r t h i sn e wt e c h n i q u es a v e sr e n d e r i n gt i m eb ye m p l o y i n gr l em e c h a n i s mt os k i po v e rt r a n s p a r e n tv o x e l s af a s ta n da c c u r a t es h e e t b u f f e rs p l a t t i n gm e t h o di su s e di nt h er e n d e r i n gp r o c e s s ，w h i c ha c c e l e r a t e st h es p l a t t i n gb yt r a v e r s i n gb o t ht h ev o x e ls c a n l i n ea n dt h ei m a g es c a n l i n ei ns h e e t b u f f e rs i m u l t a n e o u s l y t h i si st h ef i r s tt i m ei ut h er e s e a r c hs o c i e t yt oa p p l yr l et e c h n i q u e si n t ot h ea c c e l e r a t i o no fo b j e c t o r d e rv o l u m er e n d e r i n ga l g o r i t h m s t h i r d ，w ef i n dt h a ts p l a t t i n gs u f f e r sf r o ms e v e r a lk i n d so fa l i a s i n g sb e c a u s eo ff u n d a m e n t a lp r i n c i p l ei n a c c u r a c y a sa ni m p r o v e m e n t ，an e wv i e w b u f f e rb a s e ds p l a t t i n ga l g o r i t h mi sd e m o n s t r a t e di nt h i sp a p e r t h en e wa l g o r i t h mi sb a s e do nv i e w b u f f e rr a t h e rt h a ns h e e t b u f f e r b yu s i n gav o x e lt r a v e r s a lo r d e rw h i c hi sp a r a l l e lt ot h ev i e w - b u f f e r , a n dap r e - i n t e g r a t e dt h r e ed i m e n s i o n a ll o o k u pt a b l eo fr e c o n s t r u c t i o nk e r n e l ，t h em e t h o dc a l ln o to n l ys o l v et h eo v e r l a ya n dt h ep o p p i n gp r o b l e m ，b u ta l s or e d u c et h es i d e - e f f e c to fi n t e g r a t i o np r o b l e mt ot h er e n d e r i n gi m a g e f o u r t h ，i no r d e rt oo p t i m i z eak e yp r o c e s so fv o l u m er e n d e r i n g ：t h er e s a m p l i n gp r o c e s s ，an e wo b j e c t - o r d e rv o l u m er e n d e r i n ga l g o r i t h mi sp r o p o s e di nt h i sp a p e r t h en e wa l g o r i t h mi n h e r i t sa l la d v a n t a g e so ft h eo b j e c t o r d e rm e t h o d s b e c a u s et h en e wm e t h o dc a nm a k ef u l lu s eo ft h es p e e d u pb r i n g i n gf r o mp r c - p r o c e s s i n g ，a tt h es a m et i m et h er e s a m p l i n go p e r a t i o ni nt h ep r o p o s e dm e t h o di sm u c hc o i n c i d e n t f lt ot h es a m p l et h e o r y ，i tc a no b t a i nh i g h e rr e n d e r i n gq u a l i t yt h a ns p l a t t i n gw i t ho n l yav e r yl i t t l et i m ec o s t l o c a ld a t af e a t u r e sp l a yi m p o r t a n tr o l e si nt h et r a n s f e rf u n c t i o nd e s i g nf o rv o l u m er e n d e r i n g b ye x a m i n i n gr e l a t i o n s h i p sa m o n gt h r e ee i g e n v a l u e so fi n e r t i am a t r i x ，as e m i a u t o m a t i cd a t a - d r i v e nt r a n s f e rf u n c t i o nd e s i g nm e t h o di sp r e s e n t e di nt h i sp a p e ：t h i si sa l s ot h ef i r s tt i m et oa p p l yl o c a ls h a p ef e a t u r e si nt h ev o l u m ed a t ai n t ot h eg u i d e n e s so ft h et r a n s f e rf u n c t i o nd e s i g n f u r t h e r m o r e ，t h ep r o p o s e dm e t h o dc a l lo b j e c t i v e l yf u l f i l lt h ef u n c t i o no ft h ep r e v i o u sb o u n d a r yb a s e dm e t h o da n de x t e n dt h ed o m a i no ft r a n s f e rf u n c t i o nt oi n d u d em o f ed a t af e a t t i r e s a tl a s t ，at h r e e d i m e n s i o n a lm e d i c a lr e c o n s t r u c t i o ns y s t e m v o l g r a p hi sd e v e l o p e d b e s i d e st r a d i t i o n a lm e d i c a li m a g ep r o c e s s i n gf u n c t i o n s ，t h es y s t e ma l s oi n t e g r a t e ss e v e r a lv o l u m ev i s u a l i z a t i o na l g o r i t h m si n c l u d i n gm a r c h i n gc u b e s ，r a yc a s t i n g , a n ds p l a t t i n g k e yw o r d s iv i s u a l i z a t i o n v o l u m er e n d e r i n g ，r a yc a s t i n g ，s p l a t t i n g ，r u nl e n g t he n c o d i n g ，t w o s t c pr e c o n s t r u c t i o nl o o k u p t a b l e ，t r a n s f e rf u n c t i o n独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得鑫整盘茎或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。学位论文作者签名：1 长匆w 历签字日期：文一毕年文月，4 只学位论文版权使用授权书本学位论文作者完全了解鑫壅盘茎有关保留、使用学位论文的规定。特授权盘壅盘茎可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：j 饫一小厂万导师签名：f 套h签字日期：。妒中年山月。日签字f 1 期：矿v 年t 月- 。f 1天津火学博士学位论文第一章绪论第一章绪论1 1 课题研究背景、目的和意义2 0 世纪8 0 年代后期，随着计算机软硬件技术的不断发展、科学和工程计算规模和复杂度不断增加，以及各科学领域新型实验手段不断丰富，所产生的大量数值数据与无法有效解释和有效利用之间的矛盾日益尖锐。科学计算可视化( v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ) 在这种背景下应运而生【1 】【2 】，它主要是指运用计算机图形学和计算机视觉及图像处理技术，将科学计算、工程计算以及实验和测量的数据转换为图形和图像在屏幕上显示出来，并进行交互处理的理论、方法和技术 3 1 1 4 1 1 5 1 。系统开展科学计算可视化研究具有重要意义。首先，可视化可以大大加快数据的处理速度，使时刻都在产生的海量数据得到有效利用。第二，视觉在人类的科学发现中发挥过杰出的作用，海量的数据只有通过可视化变成形象，爿+ 能激发人的形象思维。第三，可以在人与数据、人与人之间实现图像通信，从而使人们能够观察到数据中隐食的现象，为发现和理解科学规律提供有力工具。同时，可以实现对计算和编程过程的引导和控制，通过交互手段改变过程所依据的条件，并观察其影响，从而实现真正的交互计算和驾驭式计算。总之，可视化将极大地提高科学计算、工程、试验的质量，实现科学计算工具和环境的进一步现代化，从而使科学研究工作的面貌发生根本性的变化 6 1 1 7 1 。其中，三维数据场的可视化一直是科学计算可视化的核心技术，也是理解和处理更高维、时变、多元变量等数据场的基础。所以本文主要就三维标量场可视化问题展开研究。传统的图形学一般采用几何模型，如多边形等图形基元来描述形体并通过光照计算进行渲染、显示。几何模型是表示有形而且规则形体的理想模型，因此在机械、建筑设计等众多领域得到了广泛应用。但是传统的几何建模方法很难直接应用于三维数据场可视化。这主要有以下原因：夺第一，对于真实形体进行准确的几何建模十分困难，对于三维数据场的建模就更为困难，这是因为一组几何图元只能近似表示原始数据中的一种面结构，且绘制时一次只能表现一种结构，这导致绘制时间和绘制精度间存在不可调和的矛盾【8 1 。大津火学博士学位论文第一章绪论夺第二，即使能够建立起几何模型，传统的面绘制技术也无法刻画形体内部复杂的细微结构f 9 1 ；夺第三，基于几何建模的绘制复杂性正比于场景中的多边形数量 9 】。虽然可以充分利用显示硬件的加速特性，但对于较大场景，多边形数量庞大，实时交互渲染依然比较困难；第四，对烟、云、水、火、肌肉、地层等无定形体无法进行有效准确的建模和显示一直以来就是几何建模技术的致命弱点1 1 0 。直接体绘制( d i r e c tv o l u m er e n d e r i n g ) 【1 1 1 1 1 2 ，简称体绘制( v o l u m er e n d e r i n g ) ，是种完全不同的体可视化绘制方法。它与基于传统图形学的面绘制技术如移动立方体法( m a r c h i n gc u b e s ) 【1 3 】等有着本质的不同，其绘制过程中不需要生成几何模型( 如三角面片) ，而是根据选定的体光照模型，研究光线穿过三维体数据场时的变化，将三维空间的体数据直接映射成为带有深度信息的二维图像。体绘制能够根据用户需要，选择显示感兴趣的物质或结构( 如c t 中的骨骼或者血管) ，使人们从绘制结果可以感受到体数据所包含的完整信息，给人更直观、更方便的视觉感受。与传统几何建模方法相比，体绘制具有以下优点：夺体绘制理论上不需要传统面绘制方法所必需的图像分割和分类。由于当前设计自动化的、普适的图像分割、分类算法在技术上还很不现实，而体绘制通过传递函数实现物质的分类【1 4 1 ，从原理上巧妙地避开了这个技术难题。夺体绘制不仅可以绘制传统意义上的等值面，而且能够将实体不同层次的结构细节表现出来，达到了真正意义上的“透视”功能。夺体绘制算法复杂度从理论上来讲取决于绘制图像的分辨率，与绘制场景的复杂度之间没有直接关系【1 2 】，通过将大规模几何造型的场景体索化，并用体绘制的相关技术对场景进行渲染，可以避免了处理大量多边形的费时计算，这为实时显示大规模场景带来了希望。夺对于烟、云、水、火、肌肉、地层等无定形体进行渲染和显示是体绘制的强项 1 5 1 1 1 6 1 7 。由于体绘制能够将来自如计算机断层扫描( c o m p u t e dt o m o g r a p h y ，c t ) 、核磁共振( r n a g n e t i cr e s o f l a n c ei m a g i n g ，m r i ) 、计算流体力学( c o m p u t a t i o n a lf l u i dd y n a m i c s ，c f d ) 等的三维体数据有效地绘制出来，所以在生物医学工程、地质科学、化学、有限元分析后处理等领域得至h 广泛重视和应用。近年来体绘制技术又被应用于自然现象仿真、考古和文物保护、工业造型设计、地震学、宇航等领域【1 8 1 9 。天津人学博士学位论文第一章绪论开展交互体绘制研究，探索提高体绘制质量、速度和可交互性的理论和关键技术，对于完善可视化理论、拓展体绘制的应用领域等都具有重要的理论和实践意义。1 2 体绘制关键技术研究现状及面临问题虽然已经有将近二十年的历史，但体绘制目前仍然处在研究和发展阶段，其理论尚有许多不完善的地方，限制了体绘制的进一步推广、应用。近十年来体绘制技术在算法研究方面取得了巨大进展，先后提出了体光线投射 2 0 1 1 2 1 1 、足迹表法( s p l a t t i n g 2 2 2 3 、体元投射法( c e l lp r o j e c t i o n ) 【2 4 】、错切一变形( s h e a r w r a p ) 2 5 1 、频域体绘制( f r e q u e n c yd o m a i nv o l u m er e n d e r i n g ) 2 6 2 7 、以及基于纹理映射( t e x t u r em a p p i n g ) l 拘体绘制 2 8 2 9 1 等众多算法。但是由于体绘制计算复杂度较高，计算较为费时。虽然国内外学者已经提出了如包围盒空间八叉树( o c t r e e ) 【2 1 3 0 1 、k - d 树【3 1 】一索引表【3 2 】、距离变换f 3 3 】等数据结构以及提前不透明度截止( e a r l yo p a c i t yt e r m i n a t i o n ) 【3 4 1 1 3 5 1 等策略来加速体绘制过程，但是随着可视化技术的深入发展和应用，数据规模越来越大，导致体绘制速度与用户要求实时、交互进行显示处理之间的矛盾越来越严重。例如对于规模为1 0 2 4 3 分辨率的规则体数据。假设每个体素2 字节，要求以3 0 h z 的频率刷新，即使每个体素数据只处理一次且仅需要1 0 条指令，大约需要2 g 的内存容量，6 0 g 秒的数据传输量，3 千亿，秒的指令处理能力。对于超大规模体数据，对于处理机的性能和内存带宽要求就更高。在速度无法保证实时的情况下，可交互性也就无从谈起。所以在保证绘制质量的前提下，提高速度成为当前制约体绘制技术进一步发展的主要难题。因此探索如何综合应用已有体绘制加速技术、设计开发新型加速技术仍将是今后较长一段时间内体绘制研究的主要任务。体绘制算法中，光线投射算法能够产生高质量的绘制图像，但速度较慢：s p l a t t i n g 算法由于提前将重构函数积分成二维的足迹表，避免了费时的三维重构，速度很快，但是其足迹表生成基于近似计算的事实导致s p l a t t i n g 算法存在严重的走样现象f 3 6 1 ，要产生高质量的图像，需要使用高阶高计算复杂度的重构函数；错切变形算法虽然是目前最快速的体绘制算法，但其算法的理论缺陷使得它不能被应用到对准确度要求较高的领域。所以对现有体绘制算法进行改进优化，在此基础上，设计开发更优秀的体绘制算法也是目前一项重要任务。与科学计算可视化的目的一样，作为一项核心技术，体绘制的最终目的是通过对体数据的有效显示，使得用户能够发现数据背后隐藏的规律以及获得对数据天津火学博士学位论文第一章绪论的理解。所以经常需要调整体绘制中视点位置、灯的位置、剪切面选取、物质的材质特性等绘制参数。其中，对绘制结果影响最大的一个参数是物质的不透明度的设置，体绘制中通过传递函数( t r a n s f e rf u n c t i o n ) 实现物质分类，从而确定相应的不透明度，而目前传递函数设计缺乏理论指导，灵活通用的传递函数设计仍然较为困难，这成为限制体绘制进一步发展和推广应用的一个重要因素，所以包括传递函数在内的体绘制参数调整技术成为体绘制领域一个新的研究热点。虽然现代计算机普遍采用图形加速卡，但现有的图形加速卡都是基于传统图形学的多边形绘制算法设计的，对于体绘制技术中以体素为基本单元的绘制过程，无法借助于传统的图形硬件加速。设计能够利用现有加速图形硬件的新型体绘制算法和设计基于体绘制的加速硬件体系结构是当前体绘制的另外两个重要研究方向【3 7 】。对于大规模和超大规模体数据，如虚拟人( v i s i b l eh u m a n ) 数据，一台单机的内存系统不足以容纳这样的数据，绘制就更无从谈起。对于这样的情况，通过多个处理机进行并行或分布式计算就成为交互体绘制的必然选择。虽然前人已经进行了很多并行体绘制的研究工作【3 8 】，但这些研究大多基于大型机平台。随着分布式计算技术以及高性能价格比的集群系统、工作站网络( w a n ) 等的出现和发展，越来越多的高性能计算应用将从昂贵的大型机转向集群系统或者工作站网络 3 9 1 。所以，以工作站网络和集群系统为平台，开展并行分布式的体绘制算法研究就变得特别迫切。针对现有体绘制算法进行改进，克服其存在的缺陷，优化体绘制流程，并进一步提出更准确、更快速、更灵活的体绘制算法是解决上述问题的基础和关键所在。本文中作者对两种典型的体绘制算法像序的光线投射算法和物序的s p l a t t i n g 算法分别进行了分析研究，并针对提高绘制图像质量和提高绘制速度两个方面进行了深入研究，提出了相应的质量改进和加速算法。并在此基础上提出了一个新型物序体绘制算法，这些研究工作是对现有体绘制算法理论的拓展和丰富。另外，为了提高体绘制算法的可交互性和灵活性，作者还对体绘制传递函数设计进行了系统研究，并提出了一种额型的半自动化体绘制传递函数设计方法。该研究工作将局部形状特征引入传递函数设计，扩展和丰富了传递函数的定义域，为体绘制传递函数设计提供了一个全新的研究思路。1 3 本文主要研究工作和创新之处本文主要研究在保证绘制图像质量的前提下，提高体绘制实时性和可交互性的软件算法和相关技术。研究思路是从分析现有体绘制算法的绘制速度和绘制质天津大学博士学位论文第一章绪论量这一对基本矛盾出发，对现有算法缺点的产生原因进行细致分析，提出改进方案，提高其绘制速度和图像质量，并设计开发新型、高效体绘制算法。本文主要研究工作和创新之处如下：1 由于光线投射算法是目前最为精确和最典型的体绘制算法，本文系统分析了光线投射算法流程中各步骤的计算复杂度，并针对光线投射计算复杂度高、绘制速度慢的缺点，提出并实现了一种通过提前梯度估计、分类着色和明暗计算来降低光线投射重采样点计算量的加速光线投射算法。该方法可以有效提高光线投射算法的绘制速度而不显著降低绘制图像质量。2 s p l a t t i n g 算法是一种具有广泛应用前景的物序体绘制算法，根据其计算复杂度为0 ( 3 ) 的特点，本文首次将游程编码( r u n l e n g t h e n c o d i n g ) 技术应用于物序体绘制，提出了一种基于游程编码加速的新型帧缓冲s p l a t t i n g 算法。首先，该算法采用提前分类、提前明暗计算的策略来降低绘制过程计算量；其次。通过游程编码体数据实现了对屏幕无贡献透明体素的有效剔除；另外，新算法采用了对体素扫描线和帧缓冲区图像扫描线的并发遍历绘制策略，使得新算法可以充分使用提前不透明度截止等技术来加速绘制过程。该方法不仅可以大大加速s p l a t f i n g 算法，而且能获得较高质量的绘制图像。3 经典s p l a t t i n g 算法存在积分问题、重叠问题，导致绘制结果存在严重的走样现象，为了消除这些走样现象而提出的基于帧缓冲的s p l a t t i n g 算法又引入了严重的p o p p i n g 走样。为了能够消除s p l a t t i n g 算法中的各种走样现象，本文提出了一种基于v i e w b u f f e r 的新型s p l a t t i n g 算法，与帧缓冲按照平行于体层方向的构建方法不同，新算法中v i e w - b u f f e r 是按照与投影平面平行的方向建立的，并且通过定义一套简单的体素遍历策略实现了体素向v i e w b u f f e r 的投影。新算法不仅可以有效消除s p l a t t i n g 算法中重叠问题和p o p p i n g 走样现象，并能够较好地解决积分问题对绘制图像的影响。4 先重采样然后进行融合运算是体绘制算法的本质所在，其中重采样过程是体绘制中最重要、往往也是最费时的一个步骤，为了优化体绘制算法的重采样及其计算过程，在吸收和借鉴s p l a t t i n g 算法思想和具体实现流程的基础上，本文提出并实现了一种通过两重查找法进行重采样的新型物序体绘制方法。这种方法在继承物序体绘制算法优点的基础上，不仅能够最大限度预处理一部分计算，而且更符合重构采样理论、因而可以以较低的计算代价获得比s p l a t t i n g 更高质量的绘制图像。5 针对当前传递函数设计缺乏理论指导的问题，通过分析基于体数据局部三维图像矩( m o m e n t ) 所确定的惯量矩阵( i n e r t i am a t r i x ) 特征值，本文提出了一种新型的半自动化传递函数设计方法。该方法首次将局部形状特征引入天津大学博士学位论文第一章绪论传递函数设计，扩展和丰富了传递函数的定义域。并且具有计算简单、快速的特点，而且能够完成基于边界检测的传递函数所具有的功能。6 针对医学应用，设计并实现了面向医学三维重建的可视化系统v o l g r a p h ，该系统在实现常规的医学图像处理功能的基础上，集成了移动立方体、光线投射及s p l a t t i n g 算法等体视化算法，系统支持d i c o m 标准，可以有效实现对医学图像的处理和三维重建。1 4 论文结构第一章，介绍了本文的课题研究背景、目的和意义，指出了目前交互体绘制面临的主要技术问题和本文的主要研究工作和创新之处。第二章，主要介绍与论文研究工作相关的背景知识和主要技术基础，针对体绘制的理论基础一体绘制方程，重点讨论了体绘制流程中各个步骤的实现方法、现有各种体绘制算法的原理、特点，并且综述了目前体绘制加速技术的研究现状。第三章，介绍作者对光线投射算法的分析，并讨论本文提出的基于流程调整和模型简化的新型光线投射加速算法。第四章。首先介绍了s p l a t t i n g 的基本原理，在分析现有的s p l a t t i n g 加速方法基础上，主要讨论了作者提出的基于游程编码加速的新型帧缓冲s p l a t t i n g 算法的原理和实现方法。第五章，首先介绍了s p l a t t i n g 算法的缺陷及由此引发的各种走样现象，并分析了各种走样现象的产生原因。然后详细讨论了本文为了提高s p l a t t i n g 绘制质量和精度而提出的基于v i e w b u f f e r 的s p l a t t i n g 算法。第六章，介绍作者为了优化体绘制重采样过程，在借鉴s p l a t t i n g 算法优点基础上提出的基于两重重构查找表的新型物序体绘制算法。第七章，首先介绍了体绘制传递函数的概念，分析了体绘制传递函数设计中存在的问题，在介绍了现有传递函数设计的各种方法和发展趋势之后，详细讨论了作者提出的基于局部形状特征进行体绘制传递函数设计的新方法。第八章，简要介绍了作者开发的三维医学图像图像重建系统v o l g r a p h 的系统框架和主要功能。第九章，对全文研究工作进行总结，并对未来研究工作作出展望。天津大学博士学位论文第二章体绘制研究基础第二章体绘制研究基础本章论述与论文研究工作相关的理论和方法基础。其中第一节讨论了体数据的主要来源和分类。第二节综述了已有的体视化技术并对各种体视化技术进行了分类。第三节介绍了体绘制的理论基础一体绘制方程。在第四节中作者就体绘制流程以及对体绘制流程中各个步骤如三维重构、梯度估计、体数据着色和分类、明暗计算以及图像合成等都进行了详细论述。第五节综述了现有的体绘制方法，包括光线投射、s p l m t i i l g 、体元投射、错切变形、频域体绘制及基于纹理映射的体绘制算法，并对各种算法进行了相应评价。第六节针对体绘制速度较慢的问题，讨论了目前体绘制加速技术的研究现状。2 1 体数据体( v o l u m e ) 数据可以看作是一个三维空间网格上的采样点( 体素，v o x e l )集，每个采样点包含标量、向量或者张量值。其来源主要有：1 测量数据，如医学数据包括计算机断层扫描( c t ) 、磁共振成象( m r i ) ，超声( u l t r a s o u n d ) 、正电子发射成像( p e t ) 、单光子发射成像( s p e t ) 、x 射线。以及地震地质勘探数据、气象监测数据、天文学射电望远镜获取的星云数据等。2 科学计算或者仿真数据，如计算流体力学( c f d ) 、有限元分析( f e a ) 等，这是当前体数据的主要来源之一。3 几何实体的体素化( v o x e l i z a t i o n ) 数据。如工业造型设计、游戏、及大规模地形可视化等领域中将几何实体体索化所获取的数据。体数据通常定义在空间网格点上，网格结构决定体元( c e l l ) 的基本形状，也决定体元之间的相邻关系。网格结构取决于应用，对绘制具有很大的影响。根据其结构特点，下面简要汇总一下常见的网格数据格式：( 1 ) 结构化网格数据这类网格中的数据可看作在空间上三组相互垂直的平面公共交点的集合，逻辑上结构化网格数据组织成三维数组。也就是说，各个元素具有三维数组各元素之间的逻辑关系，每个元素都可以有它的层号、行号和列号。结构化网格又可分天津火学博士学位论文第二章体绘制研究基础为以下两类，一类称为规则结构化网格数据，共有三种类型：i 笛卡儿型( 均匀网格型) ：建立在笆卡尔坐标系上的体数据。每一个体元大小相同、也各维比例也完全相同，按照坐标轴方向均匀排列成j 下方体形状。体素坐标可以表示成( f ，f ，尼) ，笛卡尔网格数据中无需记录体素的空间位景，通过序号就可以计算出该体素的空间位胃及其体数掘。柬自医学的体数据大多数据这种类型，如图2 - 1 ( a ) 所示。i i 。等距型：所有体元大小相同，按坐标轴方向排列成长方体，体素坐标可以表示成( i s c a l e x ，s c a l e y ，k s c a l e z ) ，其中s c a l e x ，s c a l e y ，s c a l e z 为在三个坐标轴上相邻体素点的距离，如图2 - 1 ( b ) 所示。i i i 矩形型：沿每一坐标轴，体素间距各不相同。但体元仍是沿坐标轴排列的长方体，该类型体数据中必须记录体素坐标，这样体索的坐标可以表示为m f 】，_ ) ，【仆z t k ) ，其中x ，y ，z 分为坐标数组，如图2 - 1 ( c ) 所示。图2 1 体数据格式( a ) 笛卡尔型网格数据( b ) 等距型网格数据( c ) 矩形型网格数据( d ) 曲线型网格数据( e ) 非结构化网格数据( f ) 泄台网格数据另外一类称为非规则结构化网格数据，也称曲线( c u r v i l i n e a r ) 型网格数据，这类数据中，每一体元是逻辑上的六面体，相对的面并不要求平行，且每一面的四个定点可以不共面。体数据中也必须记录体素坐标，体素坐标可以表示成( x i ，j ，k ，y i ，j ，k ，z i ，j ，k ) ，如图2 - 1 ( d ) 所示。( 2 ) 非结构化网格数据这类数据中网格间的空间邻接几何关系需要另外提供，体数据中除了必须存天津大学博士学位论文第二章体绘制研究基础储体素的坐标信息之外，还要存储网格间的连接信息。其中有限元计算和计算流体力学中体数据大都属于这种类型，如图2 - 1 ( e 1 所示。( 3 ) 混合网格数据以上类型的组合，主要出现在跨学科问题中，如结构仿真数据和流体仿真数据的结合问题会产生该类数据，如图2 - 1 ( f ) 所示。由于非规则结构化网格数据和非结构化网格数据可以通过计算几何方法转化成规则结构化体数据，所以本文中只考虑规则结构化体数据。2 2 体视化技术及其分类体可视化( v o l u m ev i s u a l i z a t i o n ) ，简称体视化，就是研究如何将三维体数据有效的绘制成图像的科学。根据数据描述方法和绘制方法的不同，体视化技术可以分为三大类：面绘制方法( s u r f a c eb a s e dr e n d e r i n g ，s b r ) 、直接体绘制方法( d i r e c t v o l u m er e n d e r i n g ，d v r ，简称体绘制) 和混合绘制方法( h y b r i dr e n d e r i n g ) 。随者研究的不断深入，每一种技术又包含很多具体方法，图2 - 2 是体视化技术分类图。图2 2 体视化技术分类图天津大学博士学位论文第二章体绘制研究基础2 2 1 面绘制( s u r f a c eb a s e dr e n d e r i n g )第一类算法是面绘制方法。在面绘制中，首先由三维空间数据场构造出中间几何图元( 如曲面、平面等) ，然后通过光照计算进行渲染。最常见的中间几何图元就是三角面片，当我们需要从三维空间数据场中抽取出等值面时就属于这种情况。可以抽取出一个等值面，也可以抽取出多个等值面。这类方法可以利用现有的图形硬件实现绘制功能，使图像生成及变换的速度加快并可以产生较清晰的等值面图像。然而这种基于面绘制的方法构造出的可视化图形不能反映整个原始数据场的全貌，生成的结果也不够细腻，另外该方法对数据进行二值分割，且对分割精度要求较高。目前主要的面绘制方法有轮廓线连接法、移动立方体法( m a r c h i n gc u b e s ) 、移动四面体法( m a r c h i n g t e t r a h e d r a ) 、剖分立方体法( d i v i d i n gc u b e s ) 。轮廓线连接法( c o n t o u rc o n n e c t i o n )轮廓线连接法是应用较早的面绘制方法。首先将每层图像的轮廓线提取出来，然后在不同层间的轮廓线上选择顶点，通过连接这些顶点构造三角面片，进而通过光照计算进行渲染。但轮廓线连接法存在以下问题 4 0 4 1 4 2 4 3 ：1 ) 对应问题( c o r r e s p o n d i n g ) ：当层上轮廓线数据较多的情况下，相邻层间的轮廓线的对应连接问题非常难以确定，尤其是相邻层间距离较大即层间分辨率较小的情况下问题尤其严重。2 ) 镶嵌问题( t i l i n g ) ：即两条对应轮廓线上顶点的对应关系确定也较为困难。3 ) 分支问题( b r a n c h i n g ) ：由于一条轮廓线与相邻层上多条轮廓线相对应带来的面片生成问题。这些问题的存在使得轮廓线连接法只适合于层间等值面变化较小或者具有几何形状上的相似性、且绘制精度要求较低的场合，这大大限制了其进一步应用。移动立方体法( m a r c h i n gc u b e s )最有影响的面绘制重建方法是l o r e n s e n 和c l i n e 提出来的移动立方体方法1 3 1 。是进行规则体数据场等值面生成和绘制的经典算法。首先在由两层间8 个相邻体素构成的体元内部构造代表等值面的三角面片，首先根据二值分割( b i n a r ys e g m e n t a t i o n ) 确定的域值( t h r e s h o l d ) 即等值面的值，然后在每一个体元内逐个顶点比较其体素值是否大于( 或等于) 给定的域值，是则将该顶点标记为1 ，表示该顶点位于等值面内( 或者之上) ，否则为0 ，表示该顶点位于等值面之外。如果体元的一条边两个顶点一个为0 一个为i ，则表示等值面与该边相交。对于体元中1 2 条边分别确定其与等值面的相交情况，并根天津大学博士学位论文第二章体绘制研究基础据线性插值公式反向计算出交点坐标，就可以将这些交点作为三角面片的顶点，这就是移动立方体法构造三角面片的基本原理。由于每个体元共8 个顶点，根据排列组合原理体元内三角面片的构型总共有2 5 6 种可能，但根据互补对称性和旋转对称性原理，再加上所有顶点值都大于域值和所有顶点值都小于域值这两种构型实际是等价的，这样2 5 6 种构型被减少到1 5 种构型，每种构型对应固定的等值面三角片拟合形态，如图2