（生物医学工程专业论文）基于体绘制的三维可视化算法的优化实现研究.pdf

浙江大学硕士学位论文 a b s t r a c t a b s t r a c t v i s u a l i z a t i o no fm e d i c a lv o l u m ed a t ai sap r o c e s st or e c o n s t r u c tt h ed i s c r e t e3 d d a t ab yi n t e r p o l a t i o n ，a n dt h e nt r a n s f o r mt h ed a t ai n t oi m a g ew i t h3 dv i s u a le f f e c t i t c a nb eu s e dt oa s s i s tt h ed o c t o rt op l a nt h es u r g e r y , a n ds i m u l a t et h eo p e r a t i o nu s i n g c o m p u t e r , w h i c hc a ng r e a t l yi m p r o v et h ea c c u r a c ya n ds c i e n t i f i co fm e d i c a ld i a g n o s i s v o l u m er e n d e r i n gi saw i d e l yu s e dt e c h n o l o g yf o r3 dv i s u a l i z a t i o n b u td u et ot h e l a r g ea m o u n to fc o m p u t a t i o n ，i to f t e nr e q u i r e sh a r d w a r es u p p o r t f o rt h i sr e a s o n ， s c h o l a r sh a v ep u tf o r w a r dav a r i e t yo fm e t h o d st oi m p r o v ei t m o s to ft h e mf o c u s e d o nt h eo p t i m i z a t i o na tt h ed e s i g nl e v e l t h et h e s i sf o c u s e so nt h eo p t i m i z a t i o na tt h e i m p l e m e n t a t i o nl e v e l a f t e r c a r e f u l l yc o m p a r i n gv a r i o u sw i d e u s e dv o l u m er e n d e r i n gm e t h o d s ，t h et h e s i sd e v o t e s m o s to fi t se f f o r tt ot h er a y - c a s ta l g o r i t h mf o rv o l u m er e n d e r i n g b a s e do nt h ev o l u m e r e n d e r i n gi m p l e m e n t a t i o n i nv i s u a l i z a t i o nt o o l k i t ( v r k ) ，t h et h e s i sl o c a t e st h e b o t t l e n e c ko ft h ew h o l ea l g o r i t h mt h r o u g hs y s t e m a t i ca n a l y s i sa n dr e s e a r c h ，a n dt h e n f u l l ye x p l o i t st h ep o t e n t i a lo ft h ee x i s t i n gp cb yc a r e f u l l ya p p l y i n gt h ef i n e g r a i n e d a n dc o a r s e - g r a i n e do p t i m i z a t i o n t h eo p t i m i z a t i o n sf o c u so nt h ea r c h i t e c t u r eo ft h e p r o c e s s o r s t h r o u g ht h ea n a l y s i so ft h es i n g l ei n s t r u c t i o nm u l t i p l ed a t a ( s i m d ) i n s t r u c t i o n sa n dc a c h eu s a g e ，t h et h e s i sa p p l i e st h ec o r r e s p o n d i n go p t i m i z a t i o n s t r a t e g yt or e d u c ec a l c u l a t i o na n di m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h m t h et h e s i sa n a l y z e sa n do p t i m i z e st h et w ob o t t l e n e c k so f r a y c a s ta l g o r i t h m ：r a y g e n e r a t i o na n dr e - s a m p l i n g t ot a c k l et h ef i r s tb o t t l e n e c k , s t r e a m i n gs i m de x t e n s i o n ( s s e ) i su s e dt oo p t i m i z e t h e f l o a t i n go p e r a t i o n ，a n d t h ep e n a l t yo fb r a n c h m i s - p r e d i c t i o ni sr e d u c e d t ot a c k l et h es e c o n db o t t l e n e c k ，s s e 2i su s e dt oo p t i m i z e t h et r i - l i n e a ri n t e r p o l a t i o n a n dp e r f o r m a n c ep e n a l t yo fc a c h em i s si sd e c r e a s e db y u s i n gd a t a b l o c k i n g 。 i nt h et h e s i s ，v a r i o u sd a t as e t sw i t hd i f f e r e n tc h a r a c t e r i s t i c sa r eu s e dt od e s i g nt h e t e s tc a s e s t e s tr e s u l t ss h o wt h a t ，t h eo p t i m i z e da l g o r i t h mc a no b t a i n3 0 t o5 0 e f f i c i e n c yg a i nw i t h o u th a r d w a r eu p g r a d e s ，s oo r d i n a r yp cc a na l s oo b t a i nt h eb e t t e r v i s u a l i z a t i o nr e s u l t sp r o v i d e db yt h ev o l u m er e n d e r i n ga l g o r i t h m i i i 浙江大学硕士学位论文 a b s t r a c t k e y w o r d s ：v o l u m er e n d e r i n g ，r a y - c a s ta l g o r i t h m ，k ，s i n g l ei n s t r u c t i o n m u l t id a t ai n s t r u c t i o ns e t ，o p t i m i z a t i o n i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得浙婆太堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：1 包晕稠 签字日期：_ 的8 年6 月i 乙日 学位论文版权使用授权书 本学位论文作者完全了解 浙婆太堂 有权保留并向国家有关部门或机构送交本 淦文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝塑太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 杲存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：1 己擎闷导师签名： 整字日期：砂旧召年6 月f1 ，日 签字日期 浙江大学硕士学位论文 致谢 致谢 六年的大学生活即将结束。首先感谢夏顺仁教授这么多年来的关心和帮助。 从本科到研究生，夏教授兢兢业业的治学精神，精益求精的工作作风，深深地感 染和激励着我。从毕业设计课题的选择到论文的最终完成，夏教授都给予了我极 大的帮助。夏教授不仅在学业上给我以悉心指导，还在思想和生活上给予无微不 至的关怀，在此向夏教授表达感谢! 感谢实验室的诸位同门。包括大师兄张赞超，已经毕业的0 4 、0 5 级师兄， 0 6 级同学傅聪和本科的师弟师妹，他们都在学术和生活上给予了我莫大的帮助， 使我获益良多。 感谢研究生阶段和我一起参与生物医学工程综合实践的同学，综合实践 时积累的知识和经验为论文的研究工作奠定了良好的基础。 感谢我的两位室友薛在岳和邓文亮陪伴我度过了两年的研究生时光。 最后感谢我的父母，他们给我创造了良好的学习环境和宽松的学 - - j 氛围，使 我能够专注于学业和科研。 浙江大学硕士学位论文1 绪论 1 绪论 1 1 课题的研究背景和意义 医学数据的三维可视化是在计算机上对离散的三维数据进行插值重构，将其 转变成为具有直观立体效果的图像。体数据的三维影像可以展示物体器官的立体 形态，提供若干用传统手段无法获得的解剖结构信息。医生可以在此基础上对病 变体和周围组织进行分析。三维可视化技术能够辅助医生进行手术规划，实现虚 拟手术，从而大大提高医疗诊断的准确性和科学性。 三维可视化技术始于2 0 世纪7 0 年代，并在近十几年得到长足的发展。美国 国立医学图书馆实施了一项可视人体的项目( v i s i b l eh u m a np r o j e c t ，v i - i p ) 1 1 。该项 目对人体进行了大规模的扫描和数据采集，一共得到了5 6 g b 的数据，被称为 v i s i b l eh u m a n 共享数据集。这在整个医学吏上是首创的，它改变了医学可视化 的模式。共享数据集的出现为计算机图像处理和虚拟现实进入医学敞开了大门。 随着大量数据集的出现，三维可视化处理技术也蓬勃发展起来，并逐渐走向成熟。 国内于2 0 0 2 年启动了“虚拟中国人”计划【2 1 。 目前，许多国内外高校都在进行医学图像三维可视化方面的研究，并且已经 有了一些成熟的算法。与此同时，专业的医学成像设备和医学图像处理软件也逐 渐发展。但是这些设备和软件大多是在图形工作站上完成的，需要强大的硬件支 持，因此价格非常昂贵，限制了三维可视化在我国的普及和应用。随着现在p c 机的广泛应用和处理器性能的不断提高，使得在廉价的p c 机上完成以前图形工 作站上才能实现的功能成为可能。因此，研究基于p c 机的三维可视化技术，提 高其运算性能是当前学术界的热点之一。 1 2 国内外研究现状 目前，医学图像的可视化方法，根据绘制过程的不同可分为两大类：间接绘 制方法和直接绘制方法。 间接绘制方法是利用等值面等手段，从三维空间数据场中提取出中间几何图 元( 如曲面、平面等) 表征物体的边界，然后再使用传统的计算机图形学技术进 浙江大学硕士学位论文1 绪论 行绘制，也称为面绘制。 直接绘制方法不需要构造中间几何图元，而是直接从三维数据场产生二维图 像，并显示到屏幕。所以也称为直接体绘1 9 j ( d i r e c tv o l u m er e n d e r i n g ) 或体绘制 ( v o l u m er e n d e r i n g ) 。 医学数据中的很多物体是不规则的，体绘制非常适合描绘这类物体的三维形 态。论文主要研究基于体绘制的三维可视化算法。 目前常见的体绘制算法有： 基于图像空间扫描的光线投射体绘制算法。其主要特点是生成的图像质量较 高，但是渲染速度较慢。因此很多学者提出了算法的改进方案3 】【4 1 。比如空区域 优化和光线提前终止。【5 仲利用g p u 对算法进行加速，取得了不错的效果。 基于物体空间扫描的错切变形( s h e a r - w a r p ) ；g ：法。其主要特点是渲染速度较 快，而生成的图像质量较差。通过采用三线性插值、进行过采样等手段，可以提 高图像的质量，但是性能下降较为明剐6 1 。 基于频域的体绘制算法。所有的计算映射到频域进行，优点是采样与观察方 向无关，但是转换的计算量很大。目前使用的不是很广泛。 基于纹理映射的硬件体绘制算法。其主要特点是能够提供比较流畅的实时交 互，因此相关的研究比较丰富。但是该算法的限制较多，生成的图像质量不如基 于图像空间扫描的体绘制算法。它的渲染速度主要依赖于专业图形加速卡的性 能。 对体绘制算法实现的优化措施主要集中在优化处理器缓存访问和使用 s i m d 指令集进行并行化两个方面m 。通过合理的优化，算法的实际性能能够有 显著的改善【8 1 。 1 3 论文的工作和组织结构 论文的研究目标为基于体绘制的三维可视化算法的优化实现研究。通过对各 类体绘制算法的分析研究，从中选择合适的算法。在现有实现的基础上，利用各 种优化手段提高三维可视化的效率。 论文的主要工作有： l 、研究常见的体绘制算法 浙江大学硕士学位论文 1 绪论 2 、选择合适的体绘制算法和实现，并在此基础上进行分析优化 3 、使用系统的测试方法对现有实现的性能瓶颈进行准确的定位，提出具有 针对性的优化策略 4 、利用处理器的体系结构特性和s i m d 指令集，对现有的实现进行粗粒度 和细粒度的优化 5 、定性和定量的分析优化实现的效果 论文的内容安排如下： 第一章绪论是对课题背景、国内外研究现状和文章主要内容的介绍。 第二章对体绘制算法进行了介绍，为论文的分析优化工作提供了理论基础。 本章还着重介绍了体绘制算法中的光线投射算法。 第三章介绍了s i m d 指令集，对c p u 的体系结构特性作了介绍。这是后续 章节分析性能瓶颈，选择优化策略的主要依据。 第四章介绍了v t k 可视化开发包，详细分析了它的渲染引擎和提供的体绘 制实现。通过对v t k 体绘制实现的研究，决定将其作为论文优化工作的基础。 之后利用性能分析工具初步定位了算法的性能瓶颈。 第五章是论文的主要章节，通过微观和宏观两种测试方法，分析了导致性能 瓶颈的主要原因。通过对代码的分块研究，结合算法本身的特性、c p u 体系结 构的特点以及s i m d 指令的强大的并行化处理能力，选择具有针对性的优化策略 对算法进行了改进，从而达到了理想的优化结果。 第六章选取了若干组特性各异的实验数据对优化前后的算法进行了比较分 析，对设计层次和实现层次上的优化方法作了对比。 最后一章是论文内容的总结，同时对论文提出的优化算法的应用前景进行了 展望。 浙江大学硕士学位论文 2 体绘制原理与方法 2 体绘制原理与方法 体绘制技术要实现的功能，是在重采样的基础上，计算采样点对屏幕像素的 贡献，从而得到每一个像素的光强度值【9 1 。 2 1 光学模型 n e l s o nm a x 在【l o 】中对几种不同的光学模型进行了综述。光学模型假定连续 分布的三维数据场中充满着小粒子，由于这些小粒子的发光、吸收、反射等功能 使得光线通过三维数据场时发生了变化。 如果假定三维空间中的小粒子不具备发光功能，可以完全吸收所射入的光 线，而无反射，那么就构成了一个光线吸收模型，这是光学模型中最简单的一种 【9 】 地) = i oe x p ( 一f f ( f ) 班) ( 2 - 1 ) 式中，s 为光线投射方向的长度参数，( s ) 为距离s 处的光线强度，f ( s ) 是 光线强度的衰减系数，它表征了距光线投射起点距离s 处的光线吸收率。1 0 是光 线进入三维数据场时( 光线投射起点，s = 0 ) 的光线强度。 r ( s ) = e x p ( 一ff (f)班)(2-2) t ( s ) 表示了距光线投射起点距离s 处的透明度。如果定义口为这段距离的不 透明度，则 口= 1 一丁0 ) = l e x p ( 一【r ( t ) d t ) ( 2 - 3 ) 母 砌 从( 2 3 ) 可以看出，如果某一数据的衰减系数为0 ，那么光线能够完全穿过三 维数据场而不被空间中的小粒子吸收，因此在结果图像中该数据代表的物质将是 透明的；如果某一数据的衰减系数为o o ，则光线将被完全吸收，因此在结果图像 中该数据代表的物质是完全不透明的。 浙江大学硕士学位论文 2 体绘制原理与方法 2 2 体绘制方法 2 2 1 图像空间扫描的体绘制技术 光线投射体绘制算法( r a y c a s t i n g ) 是m l e v o y 于1 9 8 8 年提出的，该算法是 基于图像空间扫描实现体绘制的经典算法。 在光线投射体绘制算法中，为了生成图像，图像平面的每个像素都要沿着视 线方向发出一条射线穿过体数据。沿着这条射线选择k 个等距采样点，并由距离 采样点最近的8 个数据点的颜色值和不透明度值作三线性插值，求出该采样点的 不透明度和颜色值。然后将这条射线上的所有采样点的颜色及不透明度值由前向 后或由后向前加以合成，得到该像素的颜色值，形成最终的可视图。 由于采用了三线性插值，该方法可以很方便地利用光照计算生成高质量的可 视图。但是与此同时，光线投射算法的运算量较大，因此渲染速度较慢。 2 2 2 物体空问扫描的体绘制技术 物体空间扫描算法是在光线投射之前对体数据进行变换，使其和观察方向对 齐，然后合成结果图像。体数据可以按照距图像平面由近到远的顺序投影，也可 以按照由远到近的顺序进行投影。下面介绍最常用的错切变形算法【1 1 】。 错切变形( s h e 扑w | a r p ) 算法是目前为止渲染速度较高的软件算法之一。它将 体数据看成一系列二维面片，因此可以将三维视觉变换分解成三维的错切变换和 两维的变形变换。体数据按照错切变换矩阵进行错切，投影到错切空间形成中间 图像。然后，中间图像经变形生成最后的结果图像。 该算法的主要特点是按照主视线方向选择切片数据集和投影数据，当视线的 方向发生变化后，投影方向不一定变化。因此当不透明转换函数保持不变时算法 速度很快。但是，由于错切的影响，z 轴的采样率会在l 3 之间变化，同时， 由于使用双线性插值，会导致对角线方向的伪影，使得最后生成的图像比较模糊， 质量不高。这是错切变形算法的一个很大的缺陷。为了提高图像质量，可以减 小采样间隔，或者利用三线性插值进行重采样。但是这些措施会大大降低算法的 效率。 2 2 3 频域体绘制技术 与光线投射方法和投影成像方法不同，频域体绘制技术不是在空间域进行操 浙江大学硕士学位论文2 体绘制原理与方法 作，而是先利用f o u r i e r 变换，将三维的数据场空间转化为三维的频域空间【1 2 】。 由频域的切片原理可知，过频域中心且垂直某个方一向的一维切片经过反 f o u r i e r 变换所得的图像，就是沿该方向进行光线投射方法或投影成像方法所产 生的可视图。虽然频域体绘制技术进行空域频域变换时开销较大，但因为频域 空间与视点无关，可以反复使用。另外，由频域空间的一维切片可以直接获得三 维数据场空间的可视图。 和其它频域方法类似，该方法生成的图像不能反映空间域中不同物质的遮挡 关系，因此观察者很难判断物质分布的位置关系。频域方法在实际应用中比较少 见。 2 2 4 纹理映射硬件支持的直接体绘制 二维纹理映射的硬件实现是指，在进行体数据的直接体绘制时，首先对数据 值进行分类，然后根据转换函数将每个数据点转换为相应的颜色值及不透明度 值，构建一系列二维纹理图。在确定了观察方向之后，计算数据场空间中的采样 点坐标与纹理空间中的坐标的映射关系。最后，在纹理空间中进行重采样和图像 合成，形成最终图像。 三维纹埋映射的硬件实现是指，根据体数据直接生成三维纹理，然后纹理空 间中的重采样插值运算和图像合成均由硬件完成。 目前，能提供硬件体绘制功能的图形工作站中，比较有代表性的是s g i 公 司的r e a l i t ye n g i n e t l3 1 。 纹理映射的优点是，硬件能够快速进行体数据的排列，不会受到非顺序访问 的影响。然而基于纹理映射的体绘制还面临着很多的限制，譬如不能立即计算明 暗，输入的纹理必须进行预处理；只能进行二值分类；采样率不足会导致细节丢 失等等。由于每一个视角都需要计算切片平面，涉及到大量的c p u 到g p u 的数 据传输，必须依赖高速的终端硬件的支持。 2 2 5 总结 从上面的介绍可以看出，有很多方法进行体绘制。【1 4 对各种体绘制算法进 行了分析综述。从性能的角度来看，纹理映射硬件支持的直接体绘制能够达到最 理想的帧数【1 5 】【1 6 】。但是通常需要高档的硬件支持，譬如能够支持3 d 纹理以及 p i x e ls h a d e r 进行g p u 编程的专业图像加速卡【1 7 】，以及大容量的显存。论文主要 浙江大学硕士学位论文2 体绘制原理与方法 研究具有通用性的体绘制算法优化技术，因此着重考虑软件实现的方法。图像空 间扫描的体绘制技术和物体空间扫描的体绘制技术各有优缺点。后者在以前比较 流行，因为当时的c p u 处理能力和内存的传输带宽大体相当，因此访问预先根 据视线方向生成的转换之后的数据比直接进行转换的效率更高。但是随着现在 c p u 处理能力的大幅提高，内存传输带宽日益成为算法性能的瓶颈。通常从内 存中读取数据需要几百个时钟周期，而几百个时钟周期在当前主流的c p u 上可 以完成非常复杂的操作。为此，现代的c p u 都引入了缓存( c a c h e ) ，包括代码 缓存、一级至三级数据缓存，以提高对海量数据处理的效率。但是因为缓存的容 量都比较小，无法完全存放海量的体数据，因此物体空间扫描的体绘制技术采用 的预转换可能就会得不偿失。根据 1 8 】的结果，基于物体空间扫描的错切变形算 法的渲染速度并不理想。同时，物体空间扫描的体绘制技术生成的图像质量较差 【6 1 。 2 3 光线投射算法 光线投射算法是由m l e v o y 在1 9 8 8 年提出的一种图像空间扫描的实现体绘 制的离散方法【1 9 】。不仅重新采样是用离散方法实现的，而且图像合成也应用了 光学模型的离散形式。鉴于光线投射体绘制算法的计算量较大，学者们进行了大 量研究，提出了许多改进方案【3 】【4 1 。 2 3 1 基本原理 光线投射算法的流程图参见图2 1 所示【9 1 。 浙江大学硕士学位论文2 体绘制原理与方法 最终图像 图2 - 1 光线投射算法流程图 光线投射算法假定三维空间数据( 工，少，z 。) 分布在均匀网格或规则网格的 网格点上( 为简化起见，流程图中三维空间数据用f ( i ，j ，k ) 表示) 。 流程图中的数据预处理包括数据格式转换、数据平滑去噪等。数据值分类的 目的是，根据不同的数据值，将数据正确地分为若干类，然后根据每类数据的不 浙江大学硕士学位论文 2 体绘制原理与方法 同特性赋予相应的颜色值和不透明度值，从而准确地表示多种物质的不同分布或 单一物质的不同属性。 分类之后需要进行重采样。重采样就是从屏幕上的每一个像素点根据设定的 观察方向发出一条射线，这条射线穿过三维数据场，沿着这条射线选择k 个等距 的采样点，并根据距离采样点最近的8 个数据点的颜色值和不透明度值作三次线 性插值，求出该采样点的不透明度值及颜色值。在进行重新采样之前，需要将具 有颜色值及不透明度值的三维数据场由物体空间坐标转换为相应的图像空间坐 标。 算法的最后一步是图像合成。即将每条射线上所有采样点的颜色值及不透明 度值由前向后或者由后向前地加以合成，从而得到发出该射线的像素点处的颜色 值。 2 3 2 颜色赋值 首先，要根据分类结果给每一个体元赋予不同的颜色值( r ，g ，b ) 。同时为了 显示三维数据场的内部结构，还要给每一个体元赋予不同的不透明度值口，以生 成具有透明效果的图像。口= 1 表示体元完全不透明，口= 0 表示体元完全透明。 由于各体元的颜色值是人为赋予的，因此最终图像的颜色是伪彩色。 当一个体元中包含多种物质时，则该体元的颜色值为： c = p ，e i = 1 ( 2 4 ) 其中p i 为第i 种物质所占的百分比，c = 口，( r ，g i ，量) 为第i 种物质的颜色值。 2 3 3 图像合成 图像合成的目的是计算像素点的最终颜色值。为此，需要沿着像素点发出一 条射线，计算该射线上各采样点的颜色值及不透明度值，并按照一定的规则合成 出最终颜色值。将屏幕上各像素点的颜色值都计算出来后，就形成了最终的图像。 在图像空间扫描的体绘制中，有两种不同的图像合成算法【9 1 。 1 、由后向前的图像合成 这种合成算法是沿射线由后往前将所有采样点的颜色及不透明度合成在一 浙江大学硕士学位论文 2 体绘制原理与方法 起，以得到最终图像。 设采样点的颜色值为，不透明度值为o t n o w ，进入采样点之前的颜色值为 巳，不透明度值为a i n ，经过采样点之后的颜色值为吒，不透明度值为口。埘， 则有： c o 哪= 巳( 1 一口) + c 7 ，。口一 ( 2 - 5 ) 令投射的初始颜色值为g ，最终颜色值为c 。设第i 个采样点的颜色值为 o ，不透明度值为口，透明度值为屈( 屈= 1 - a ，) 。 按( 2 5 ) 式将各单元值累加后可得： c = c o 届厦尾+ c 1 q 屐屈成+ c 2 口2 岛屈展+ + e 一1 口川尾+ e 口。 = c o r i 屈+ 窆口，f laj(2-6) i = 1i = l = i + l 2 、由前向后的图像合成 这种合成算法是沿射线由前往后将所有采样点的颜色及不透明度合成在一 起，以得到最终图像。 由前向后的图像合成公式为： 巳删二，：? 曩? ，j ( 2 - 7 ) o ! o u t2 口加+ 口m 【l 一口加j 由后向前的图像合成和由前向后的图像合成的主要区别是，在由前向后进行 图像合成的过程中，不透明度值口是递增的。当口的值趋近于l 时，说明像素点 的图像已经接近于完全不透明，后面的体元对像素点的图像的贡献可以忽略不 计，因而可以跳过后面的体元提前结束计算。由前向后的图像合成方法可以利用 不透明度递增的特性提前结束图像合成，省去不必要的计算，速度较快，因此实 际中更为常用。 2 3 4 改进的光线投射体绘制算法 使用l e v o y 算法产生的二维图像可能会不够清晰，其原因在于该算法不是对 原始的离散三维数据场进行卷积运算，实现重构，而是在数据值分类、颜色赋值、 浙江大学硕士学位论文2 体绘制原理与方法 不透明度赋值及明暗计算以后再进行卷积操作的。由于卷积运算实质上是一个低 通滤波的过程，因此这样做的结果，势必将明暗计算后颜色值中的高频分量滤掉 了，因而使图像不够清晰9 1 。 为此，目前常见的实现通常先进行重采样，然后再对数据进行分类、赋值。 改进后的算法流程参见图2 2 f 9 1 。 0 最终图像 图2 - 2 改进的光线投射算法流程图 浙江大学硕士学位论文 3c p u 概述和s i m d 指令集 3c p u 概述和s i m d 指令集 3 1c p u 概述 3 1 1 缓存 由于现代c p u 的总线频率不断提高，处理性能大大增强，内存访问越来越 成为系统的瓶颈。为此，现代c p u 引入了缓存的概念。缓存是内存中数据的一 份拷贝，位于c p u 和内存之间，可以被c p u 快速的访问。通常会有2 到3 级数 据缓存用于加快内存数据的访问速度。通过合理的安排内存访问顺序和优化缓存 使用，可以在很大程序上提高程序的整体性能。 下面，对缓存的结构和工作原理做一下介绍： 大多数缓存都可以分成若干组流水线和集合。譬如说，p 4 中一级缓存的大 小通常是8 k ，每条流水线的大小是6 4 个字节，覆盖连续的内存区域。由此可知， 一共有8 1 0 2 4 6 4 = 1 2 8 条流水线。这些流水线被分成3 2 组，每组4 路。这意味 着，在内存某一特定地址中的数据并不是可以随意载入缓存的任意一条流水线中 的。只能使用3 2 组流水线中的一组，不过一组中的4 路流水线都可以使用。下 面的公式可以用来计算某一特定内存地址中的数据将被载入到哪组流水线中： 组= 内存地址流水线长度组数 这里表示整除，表示取余。比如说，如果希望从内存地址a = 1 0 0 0 0 读入 数据，那么它将被载入第( 1 0 0 0 0 6 4 ) 3 2 = 2 8 组流水线中。换言之，它将被载入第 2 8 组流水线的4 路流水线中的其中一路。注意，从地址a 读取数据会导致c p u 将内存地址1 0 0 0 0 1 0 0 0 6 3 的整个6 4 字节的内容加载到缓存之中。所以，如果之 后程序需要访问这一区间内的其它数据，由于它们已经加载到缓存之中，就无需 耗时的内存访问操作了。 因此，为了提高缓存的利用率，最好顺序访问内存。如果随机访问内存的话， 缓存带来的性能提升会被大大削弱。 如果内存访问的间隔为2 的高次幂，每次访问都会被指定到同一组流水线。 因为缓存中的每组流水线只包含4 路流水线，当4 路流水线都被占用之后，处理 器将不得不丢弃某路流水线中的数据，从而导致缓存饱和的现象。程序性能会因 此受到很大的负面影响。 浙江大学硕士学位论文 3c p u 概述和s i m d 指令集 3 1 2 分支预测 现代的高速c p u 通常都会采用指令预取技术提高执行效率。在指令被执行 之前，c p u 会先进行预取、解码等工作。但是，如果代码中存在分支语句，那 么c p u 将无法准确的知道需要预取哪个分支中的代码。如果c p u 错误的选择了 分支，那么至少要1 0 2 0 个时钟周期以后c p u 才能发现，从而导致大量的无用 工作。为了解决这一问题，处理器的制造商大多采用分支预测技术降低分支语句 对性能的影响。现代的处理器会根据之前的跳转结果合理的选择分支。 当c p u 正确的预测了分支时，通常仅需要消耗1 2 个时钟周期。而从错误 的分支预测恢复则需要1 2 - 2 5 个时钟周期，具体数值随c p u 种类的不同而有所 差异。因此，为了提高程序的性能，应当尽量避免分支语句。 3 1 3 部分写入延迟 为了提高内存读写的性能，现代处理器大多会采用m o b ( m e m o r yo r d e r b u f f e r ，存储器排序缓冲器) 。m o b 作为处理器的内存子系统，充当了一个中转 站的角色。它保存了延迟读取和写入的信息，并在适当的情况下执行这些延迟的 命令。如果一条指令需要从某一内存地址中读取大量的数据，而之前有指令将少 量数据写入相同的地址，那么就不能利用m o b 进行中转，从而导致数据不得不 直接从内存载入。 通常写入操作会阻塞之后的读取操作，因为读取指令必须等待写入操作完成 之后，才能继续执行。m o b 的目的就是为了避免不必要的阻塞，直接将写入的 数据中转给读取指令。当读入操作被阻塞时，通常会导致6 到9 个时钟周期的延 迟。在写入操作执行完毕之前，所有的写入操作都被缓存在m o b 之中。当处理 器遇到读取操作时，如果读取的恰好是之前写入的内容，并且没有访问冲突，换 言之，在读取顺序能被保证的情况下，系统会直接将写入的内容传给读取指令， 而无需等待写入操作完成。 由此可见，当执行读取指令的时候，要么是通过m o b 的中转，从写入指令 直接获取数据，要么是被阻塞，直到写入操作完成为止。充分利用m o b 的中转 可以大大提高程序性能。 为了实现从m o b 直接获取数据，必须符合以下的条件： 读取和写入必须针对同一个内存地址 浙江大学硕士学位论文3 c p u 概述和s i m d 指令集 读取的数据是之前写入数据的子集 否则，读取操作将不得不被阻塞。为了避免这类阻塞，在对同一地址或重叠 区域读写数据的时候，最好采用相同的大小和对齐方式。如果代码不可避免的会 导致阻塞，那么可以通过指令重排，将读取指令尽可能和写入指令分开( 间隔几 十个时钟周期) ，以减轻阻塞造成的性能损失。 3 2s i m d 指令集 s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) 是指单指令多数据的运算技术。这 种技术可以使一条指令同时应用于多个数据，从而显著的提高运算性能。譬如， 有了s i m d 指令集之后，可以使用一条指令同时处理三维向量中的所有元素。而 如果只使用通常的c p u 寄存器或者f p u 浮点单元的话，所有元素都需要逐个进 行计算，从而大大浪费了处理器的资源。因此s i m d 指令集特别适合于图像处理、 信号处理以及涉及大量向量和矩阵运算的科学计算。 桌面c p u 中最早出现的s i m d 指令集是1 9 9 7 年i n t e l 公司在p e n t i u mm m x 处理器中提供的m m x 多媒体指令集。不过当时的m m x 指令集仅提供了针对整 数的s i m d 指令。对于浮点运算，m m x 指令集是无能为力的。而且m m x 指令 集和浮点运算单元共享寄存器，因此两者无法同时进行，相互之间切换的开销也 很大。第一个支持使用浮点s i m d 指令的指令集是a m d 在k 6 2 处理器中首先 提供的3 dn o w ! 指令集。随后出现的i n t e ls s e 多媒体指令集提供和3 dn o w ! 类 似的s i m d 浮点操作。随着技术的发展，a m d 又推出了增强型3 dn o w ! 指令集， i n t e l 则在推出p e n t i u m4 处理器的时候提供了性能更为强劲的s s e2 指令集。处 理器厂商推出这些指令集的主要目的，是提高c p u 对大量元素进行相同运算时 的效率。 论文主要用到了s s e 和s s e 2 指令集。 s s e 指令集可以在p e n t i u m3 以及之后的处理器上使用，部分a m d 的处理 器也支持s s e 指令集。s s e 指令集提供了8 个1 2 8 位的寄存器( x m m 0 x m m 7 ) ( 6 4 位处理器中还支持8 个额外的x m m 寄存器) ，并提供了7 0 余条指令，其中大多 数是与浮点运算相关的。m m x 指令集主要用于整数或者定点数的运算，而s s e 浙江大学硕士学位论文 3c p u 概述和s i m d 指令集 指令集则主要是针对浮点运算设计的。它包括了以下这些类别的指令： 算术运算指令：a d d p s ，s u b p s ，m u l p s ，d i v p s ，s q r t p s 逻辑运算指令：a n d p s ，a n d n p s ，o r p s ，x o r p s 倒数运算( 近似) 指令：r c p p s ，r s q r t p s 浮点整型转换指令：c v t p i 2 p s ，c v t p s 2 p i 浮点比较指令：m a x p s ，m i n p s ，c m p e q p s ，c m p l t p s s h u f f l e 指令：s h u f p s ，u n p c k l h p s ，u n p c k h p s 数据移动指令：m o v a p s ，m o v h p s ，m o v h l p s 缓存控制指令：p r e f e t c h ，s f e n c e ，m o v n t q 状态寄存器控制指令：l d m x c s r , s t m x c s r 以及少量新增的整数指令：p s h u f w , p m i n s w 其中前六类指令是经常要用到的。 s s e 指令集除了支持向量运算外，也提供了相应的标量版本，以便程序模拟 浮点寄存器的运算。值得注意的是，浮点寄存器的内部运算精度是8 0 位的，比 直接使用s s e 指令的精度要高，如果在对精度要求较高的场合，需要采取相应 的措施保证运算结果的可靠性。 s s e 2 是在p e n t i u m4 系列处理器中首先引入的。它和s s e 共享寄存器。s s e 是对4 个单精度浮点数进行并行操作，而s s e 2 则是对两个双精度浮点数进行并 行操作。所以它主要适用于需要双精度运算的场合。同时，s s e 2 提供了对m m x 指令集的扩展，可以同时对4 个3 2 位整数，或者8 个1 6 位整数，或者1 6 个8 位整数进行并行操作。 利用s i m d 指令集，可以充分挖掘现有处理器的并行运算能力，提高算法的 整体性能。很多文章在实现体绘制算法时，都使用s i m d 指令集进行优化【7 】【8 1 。 3 3s i m d 编程 通常，在代码中使用s i m d 指令集有三种方式： 1 、在单独的文件中编写汇编代码，编译生成o b j 目标文件后直接链接到主 程序中 浙江大学硕士学位论文3 c p u 概述和s i m d 指令集 2 、使用编译器提供的内嵌汇编进行编写 3 、使用编译器提供i n t r i n s i c 函数进行编写 方式l 可以获得最高的运行效率，因为通过手工对汇编指令进行调度优化， 能够实现更为紧凑的指令序列。但是编写、测试和维护的成本较高。在现代的开 发过程中采用的不是很广泛。一般仅见于对性能要求非常高的程序。 方式2 的主要问题是编写的代码不具有可移植性。通常编译器提供的内嵌汇 编语法各异，为了支持不同的编译器，不得不编写多个版本的代码。 方式3 是目前使用最为广泛的s i m d 编程方式。目前i n t e l 兼容的处理器使 用非常广泛，i n t e l 公司的编译器专门制定了一系列i n t r i n s i c 函数，以方便应用程 序使用s i m d 指令集进行开发。相应的，w i n d o w s 平台的主流c + + 编译器v i s u a l c + + 和u n i x l i n u x 平台的主流c + + 编译器g + + 均提供了对i n t r i n s i c 函数的良好支 持。因此，在此基础上编写的代码，具有良好的可移植性。唯一的缺点是编译器 生成的汇编代码和手写的代码相比，会有一些冗余。经过测试，由此导致的性能 差距并不是很大。所以论文选择方式3 进行s i m d 级别的优化。 浙江大学硕士学位论文 4v t k 简介和体绘制算法分析 4v t k 简介和体绘制算法分析 经过调研，论文决定在v t k 的基础上进行体绘制实现的优化改进。 4 1v t k 简介 v t k 是k i t w a r e 公司开发的一套开源的可视化工具包【2 0 1 ，全称是 v i s u a l i z a t i o nt o o l k i t 。它使用c + + 语言编写，同时提供接口供c 、p y t h o n 、t e l 等语言进行调用。它支持各种流行的操作系统和硬件平台，具有良好的可移植性。 全世界的数以千计的研究人员和开发人员用它来进行3 d 计算机图形的图像处理 和可视化。它基于三维函数库o p e n g l ，采用面向对象的设计方法，将在可视化 开发过程中经常遇到的问题抽象出来，并对一些常用的算法进行了封装，其中就 包括了体绘制算法。 v t k 中的体绘制部分包含了常见的光线投射( r a y c a s t ) 和错切变形 ( s h e a r - w a r p ) 算法，并且做了很多算法层次上的优化2 。目前很多对体绘制算 法进行优化的文章在比较算法性能的时候，并没有采用统一的标准。根据实际分 析和测试，体绘制的实际效率，不仅取决于体数据本身的大小和特性，还和使用 的色彩和透明度属性、光线重采样时的采样点数、观察区域的大小和视角以及渲 染窗口的大小有很大的关系。譬如，v t k 的体绘制代码中，会根据之前纪录的 渲染时间动态调整采样间隔，在牺牲成像质量的前提下，提高用户交互的响应速 度。为了获得具有更高可信度和可重复性的比较结果，论文决定采用v t k 作为 今后优化工作的基础。 v t k 中包含了若干种体绘制算法的实现【2 2 1 。根据v t k 的渲染框架，所有的 渲染请求都是由v t k m a p p e r 类处理的，处理体绘制的v t k m a p p e r 派生类是 v t k v o l u m e m a p p e r 。论文感兴趣的是它的两个使用光线投射算法进行渲染的派生 类v t k v o l u m e r a y c a s t m a p p e r 和v t k f i x e d p o i n t v o l u m e r a y c a s t m a p p e