（计算机应用技术专业论文）实时光线投射算法加速技术研究.pdf

中文摘要 科学可视化技术可以广泛应用于医学、气象学、地质学等多个领域，是当前 发展最为迅速的技术之一。体绘制技术作为科学可视化的关键技术也得到了国内 外研究者的极大关注。虽然体绘制算法在观察绘制对象内部结构方面具有其独特 优势，但是，高计算复杂度、低绘制性能限制了体绘制技术的广泛应用。因此， 必须使用软件和硬件方法提高绘制性能，研究体绘制算法的加速技术势在必行。 近年来，基于g p u ( 图形处理单元) 的体绘制算法迅速发展起来。g p u 专为 图形处理而设计，在绘制性能方面具有优势，而且提供了越来越多的控制功能和 灵活性，已经成为最常使用的体绘制加速技术之一。本文首先实现了传统的基于 纹理的物序体绘制算法，并对其进行全面分析，指出物序体绘制算法固有的绘制 缺陷，肯定了基于三维纹理的像序体绘制算法的优势所在。在此基础上，提出以 三维纹理为基础数据结构的基于逆投影的光线投射算法。在新算法中，我们采用 逆矩阵投影方法求解重采样点的屏幕坐标，充分利用g p u 的矩阵计算功能，简化 了重采样操作的坐标控制。另外，还使用了依赖纹理技术，将传递函数映射的过 程从c p u 中转移到g p u 中进行，节省了大量的存储空间，也提高了绘制性能，实 验证明：基于逆投影的光线投射算法对于2 5 6 3 规模的体数据在绘制性能和绘制结 果质量上均比基于纹理的物序体绘制算法有很大提高；与其他基于g p u 的像序体 绘制算法相比，其绘制过程简单易控。 光线投射算法是最经典的体绘制算法，它能够产生高质量的结果图形，但是 绘制的时间复杂度高。文中我们提出一种新的基于片段的光线投射算法( s r e ) 以实现加速。同许多加速技术一样，s r c 是利用体数据的数据一致性，但是却将 优化重点放在不同的绘制阶段。s r c 将连续的具有相似属性的重采样点合并成一 个片段，并对片断进行融合而不是重采样点，减少了融合操作的次数和时间。我 们对s r c 从理论和实验两个方面进行验证，并对s r c 的适用性和灵活性进行了讨 论。实验证明：在不降低绘制质量的基础上，软件实现的光线投射算法使用s r c 后性能提高大约3 0 ，而基于g p u 的光线投射算法使用s r c 后性能提升的倍数与 片断长度几乎相同。 关键词：体绘制光线投射硬件加速片断融合 a b s t r a c t s c i e n t i f i cv i s u a l i z a t i o nh a sb e e no n eo ft h em o s tr a p i dd e v e l o p e dt e c h n i q u e su s e d i nt h ea p p l i c a t i o n so fm e d i c i n e 。m e t e o r o l o g y , g e o l o g ya n ds oo ui nr e c e n ty e a r s v o l u m er e n d e r i n gi sak e yt e c h n i q u eo fs c i e n t i f i cv i s u a l i z a t i o n i th a sa d v a n t a g e si n o b s e r v i n gs t r u c t u r e s o ft h r e e d i m e n s i o nd a t a s e t s h o w e v e r , v o l u m er e n d e r i n g a l g o r i t h m ss t i l ls u f f e rf r o mh i g hc o m p u t a t i o n a lc 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 s ot h e a c c e l e r a t i n gt e c h n i q u e s n e e dt ob ef u r t h e r s t u d i e d , i n c l u d i n g b o t h h a r d w a r e - b a s e da n ds o f t w a r e b a s e do n e s ，w h i c ha r et h em a i nt o p i co ft h i sp a p e r t h e r ei sa ni n c r e a s i n gn e e df o ri m p r o v i n gg p u - b a s e dv o l u m er e n d e r i n g a l g o r i t h m si nr e c e n ty e a r sb e c a u s eg p u ( g r a p h i c sp r o c e s su n i oh a sm a n ya d v a n t a g e s i ng e t t i n gb e t t e rr e n d e r i n gp e i f o r m a n c e n o w a d a y sg p u i so n eo ft h em o s tf r e q u e n t l y u s e dt e c h n i q u e sf o ra c c e l e r a t i n gv o l u m er e n d e r i n ga l g o r i t h m s a sg p u i sa l s ot h e b a s i ce l e m e n ti nt h el a t e re x p e r i m e n t , t h ei m p l e m e n t a t i o n sa n di m p r o v e m e n t so f t e x t u r e - b a s e da l g o r i t h m sa r ef i r s t l yp r e s e m e di nt h i sp a p e la n e w s a m p l i n gm e t h o di s a d o p t e dt o c a l c u l a t et e x t u r ec o o r d i n a t e so ft h es a m p l e sb yt a k i n ga d v a n t a g eo f p o w e r f u lm a t r i xf u n c t i o n s o ft h em o d e mg p u a d d i t i o n a l l y , d e p e n d e n tt e x t u r e t e c h n i q u e ，w h i c hm a p st h es c a l a rv a l u eo fs a m p l et oo p t i c a lc o l o ra n do p a d t y i nt h e g p u , i sa l s oe m p l o y e di no r d e rt os a v et e x t u r em e m o r y t h e t e x t u r e b a s e da l g o r i t h m s a r ed i v i d e di n t ot w oc a t e g o r i e s ：2 d - t e x t u r e - b a s e da l g o r i t h ma n d3 d t e x t u r e b a s e d a l g o r i t h m t h e s et w oa l g o r i t h m sa r er e s p e c t i v e l yd i s c u s s e da n dc o m p a r e dw i t he a c h o t h e r t h ee x p e r i m e n t sr e s u l t ss h o wt h a tt h ea l g o r i t h mu s i n gn e ws a m p l i n gm e t h o d p r o d u c e s b e t t e r r e n d e r i n gp e r f o r m a n c e a n di m a g e q u a l i t y t h a nt r a d i t i o n a l t e x t u r e b a s e da l g o r i t h m sf o r2 5 6 3d a t a s e t t h 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 mw h i c hi st h em o s ta c c u r a t ev o l u m er e n d e r i n g a l g o r i t h ms u f f e r sf r o mh i 曲c o m p u t a t i o n a lc o m p l e x i t y i no r d e rt o a c c e l e r a t et h e t r a d i t i o n a la l g o f i t h m an 哪r 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 m ，w h i c hi sc a l l e ds r c ( s e g m e n t - b a s e dr a yc a s t i n g ) f o rs h o r t ，i sp r o p o s e d i nt h i sp a p e r t h e r ea r em a n y o p t i m i z a t i o nt e c h n i q u e sm a k i n gn s eo fd a t ac o h e r e n c et or e d u c ep r o c e s st i m ei n f o r m e rr e s e a r c h e s s r cw o r k st h es a m ew a y , b u ti nt h ed i f f e r e n tr e n d e r i n gs t a g e s r c c o m b i n e ss e q u e n t i a ls a m p l e sw h i c hh a v et h es i m i l a ro p t i c a lv a l u e si n t oas e g m e n t t h es e g m e n t ss u b s t i t u t ef o rt h es a m p l e st ob et h eb a s i cc o m p o s i t i o nu n i t s t h e r e f o r e ， t h en u m b e ro fc o m p o s i t i o no p e r a t i o n si sr e d u c e d t h ee f f i c i e n c yo fs r ci s d e m o n s t r a t e db yb o t ht h e o r yr e a s o n i n ga n de x p e r i m e n t sr e s u l t s t h ee x p e r i m e n t s r e s u l t ss h o wt h a ts o f t w a r es r cc a ni m p r o v et h er e n d e r i n gp e r f o r m a n c eb ya b o u t3 0 c o m p a r e dw i t ht r a d i t i o n a lr a yc a s t i n gw i t h o u td e g r a d i n gi m a g eq u a l i t yn o t i c e a b l ya n d h a r d w a r es r cc a ni m p r o v et h ep e r f o r m a n c eb yn e a r l yt h es 8 m om u l t i p l ea st h el e n g t h o ft h es e g m e n t i na d d i t i o n , s r ci s e a s y t oc o m b i n ew i t ho t h e rs u c c e s s f u l o p t i m i z a t i o n s i nt h i sp a p e r , h a r d w a r e a s s i s t a n ts r c i sm a i n l yd i s c u s s e d k e yw o r d s ：v o l u m e r e n d e r i n g , r a yc a s t i n g , g p u ，s e g m e n tc o m p o s i t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他入已经发表 或撰写过的研究成果，也不包含为获得：苤叠盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：j 计管签字日期：y ，占年) ，月汀日 学位论文版权使用授权书 本学位论文作者完全了解苤星盘茎有关保留、使用学位论文的规定。 特授权墨盗态茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：；衫推 签字日期：) 一6 年月疗日 一名：以工f 手呵 签字日期：p 码年) 月略日 第一章绪论 第一章绪论 1 1 科学计算可视化技术的背景 最早使用的文字形成于公元前3 0 0 0 多年的古代埃及，叫象形文字。它将人 类用眼睛观察到的事物用直观的图形表示记载下来。象形文字的出现揭开了人类 古代文明进步的序幕。随着时间的流逝和文化的进展，许多古代文明曾经使用的 交流载体已经不复存在。但是图形，这个曾经是人类最主要和直观的认识和交流 方式在五千多年后高度发达的现代文明中仍然有其不可替代的重要作用。研究表 明，人类获得的关于外在世界的信息8 0 以上是通过视觉通道获得的，将视觉信 息直接用图形的方式表现出来，其信息扭曲和损失最小，同时图形还具有高速、 大容量、并行工作的特点【1 】。随着人类社会飞速发展，人们在科学研究和生产 实践中，获得越来越多的科学数据，而人们获得数据的最终目的是通过对数据的 分析理解，寻求事物的内在规律和普遍真理。人们发现将表面上看似无规律可循 的大量数据按照某种规则显示为图形，数据间的联系往往一目了然，因此可视化 技术应运而生。 科学计算可视化( 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 , 简称v i s c ) 指运用 计算机图形学和图象处理技术，将科学计算过程中产生的计算结果转换为图形及 图像在屏幕上显示出来并进行交互处理的理论、方法和技术。科学计算可视化是 计算机图形学中的一个重要研究方向。它将图形生成技术、图象处理技术和人机 交互技术结合在一起，其主要功能是从复杂的多维数据中产生图形，也可以分析 和理解送入计算机的图像数据【2 】。 1 2 科学计算可视化算法分类 科学计算可视化技术的核心是三维空间数据场的可视化。对于分布在三维空 间的体数据来说，有两类不同的可视化算法：面绘制和体绘制【2 】 第一类算法首先由三维空间数据场构造出中间几何图元( 如曲面、平面等) ， 然后再由传统的计算机图形学技术实现绘制，称为面绘制。面绘制构造出的可视 化图形不能反映整个原始数据场的全貌和细节，但是可以产生比较清晰的等值面 第一章绪论 图像，而且可以利用现有的图形硬件实现绘制功能，使图像生成及变换的速度加 快。【2 】 第二类算法与第一类算法完全不同，它并不构造中间几何图元，而是直接由 三维数据场产生屏幕上的二维图像，称为体绘制算法( v o l u m er e n d e r i n g ) ，或成 为直接体绘制( d i r e c tv o l u m er e n d e r i n g ) 。体绘制是近年来得以迅速发展的一种 三维数据场可视化方法【2 】。由于体绘制中没有模型的概念，绘制单元是三维数 据场中的单个体素质，因此对于没有精确的刚性模型的物体数据、模型结构未知 的物体数据、模型结构非常复杂的物体数据，以及需要观察数据内部信息的应用， 体绘制技术具有很大的优势，在工程测绘、医学影像、气象天文、地质勘探等诸 多领域得到广泛的应用。另一方面，体绘制的无模型绘制模式使得确定物体边界 很困难，通常无法获得层次非常清晰分明的绘制效果；基于体数据点的绘制使得 算法的计算量激增，且难以利用图形硬件加速，因而绘制时间很长。 1 3 本文的研究背景 本文的研究对象是光线投射算法的加速技术。 体绘制在观察科学和工程数据内部信息，探索未知事物结构方面具有强大优 势和潜能，因此自体绘制提出后，受到了广大国内外研究者的关注，取得了诸多 研究进展，先后提出了多种体绘制算法：光线投射算法【5 】，足迹表法【3 9 】，切错 变形算法 4 5 1 ，纹理影射算法，体元投射算法 4 9 】以及频域体绘制算法【4 6 】【4 7 1 。 由于体绘制算法计算复杂度高，绘制速度成为制约体绘制技术快速发展和广 泛应用的一大障碍，因此伴随着算法的发展，各种加速策略也逐渐成熟起来。当 前体绘制加速技术主要分为五类，分别为：无效体素剔除、提前不透明度截至、 多分辨率绘制、硬件加速和并行加速，其中前三种主要针对数据结构和算法流程 进行优化，而后两种在改进算法的同时，还要依赖计算机硬件的发展，尤其是硬 件加速，随着计算机图形硬件的普及，成为最有力的体绘制加速手段之一，加之 硬件加速与其他加速技术的兼容性很好，使用图形加速硬件进行体绘制是今后体 绘制技术发展的趋势。本文的大部分工作都是在图形加速硬件基础上完成的。发 展体绘制加速技术，在充分利用现代计算机硬件强大的计算功能的同时，仍然要 注重体绘制算法本身的优化潜能，完善体绘制算法理论，改进现有的绘制算法， 并致力于提出新的体绘制算法。随着可视化技术的深入发展和应用，用于绘制的 数据规模越来越大，对算法绘制性能造成的压力也越来越大，体绘制加速技术将 面临更大的挑战。 除了绘制速度，评价绘制算法的优劣还有另一个重要标准：绘制质量。为了 第一章绪论 在研究加速技术的同时能够保证绘制图像质量，我们选择绘制质量最为精确的体 绘制算法光线投射算法作为研究对象。 1 4 本文主要内容和结构 1 4 1 本文的主要研究内容 本文主要研究在个人计算机平台上，结合现有的软件优化算法和硬件加速手 段，提高体绘制算法的绘制性能的技术，同时挖掘现有优化算法中尚未开发的体 绘制算法加速潜力，提出新的简化方案，并对其进行理论验证和实验分析。 本文中的工作主要包括以下几个方面： 近年来g p u 的运算功能发展速度大大超过c p u 的发展速度，利用g p u 进行体绘制成为体绘制算法加速的一个通用手段。本文实现了以g p u 的 二维纹理和三维纹理作为基本数据结构的体绘制算法，进而利用高级可 编程显卡的可控编程能力对重采样操作进行改进，提出以三维纹理作为 基础数据结构的基于逆投影的光线投射算法。实验结果证明：基于逆投 影的光线投射算法与基于纹理的物序体绘制算法相比在绘制时间和绘制 质量上均有很大提高。 光线投射算法是体绘制算法中绘制质量最高的一种，同时也是绘制时间 最长的一种。本文通过分析三维体数据中固有的数据一致性，提出基于 片段的光线投射算法。首先通过对体数据尚存的数据一致性进行分析， 提出简化条件；其次依据我们的简化条件对融合阶段所用的光学积分方 程进行化简，为基于片段的光线投射算法的有效性提供了理论依据；另 外还对该算法中的关键参数的影响以及算法提供的绘制灵活性进行了理 论上的探讨。基于片段的光线投射算法简化了体绘制算法流程( 体绘制 算法基础请参考第二章) 中的融合阶段，具有良好的兼容性，可以与现 有的光线投射优化算法结合使用，对算法性能有进一步的提高。 在为基于片段的光线投射算法提供了理论依据后，本文实现了该算法基 于c p u 的版本和基于g p u 的版本。由于基于c p u 的实现在算法控制方 面比较灵活，因此首先实现该算法基于c p u 的版本，通过和传统的光线 投射算法进行性能比较，验证算法的有效性。而后实现了算法的g p u 版 本，有效利用现代g p u 的可编程特性进行了多步优化，本文探讨了在实 现新算法g p u 版本过程中的各关键技术。实验结果证明：基于片断的光 线投射算法在保证绘制质量的基础上，提高了绘制性能。 第一章绪论 1 4 2 本文创新点 基于1 4 1 节叙述的研究工作，本文的创新之处如下： 实现和分析基于二维纹理和三维纹理的物序体绘制算法，与依赖纹理技 术结合提出以三维纹理作为基础数据结构的基于逆投影的光线投射算 法，实现实时的像序体绘制算法。 分析体数据数据一致性，据此对绘制方程进行简化，推导出基于片段的 绘制方程。 将基于片段的绘制方程与光线投射算法相结合，实现基于片段的光线投 射算法，与传统的光线投射算法相比，提高性能3 0 - 5 0 。 基于片段的光线投射算法与可编程g p u 两种加速技术相结合，与基于可 编程g p u 的普通光线投射算法相比，在低采样情况下，提高绘制结果质 量，在超采样情况下，保持绘制结果质量，提高绘制性能。 提出一种传递函数的设置调整方案。 1 4 3 本文结构 第一章，介绍了本文的研究背景和意义。概括叙述了本文所做的工作。 第二章，主要介绍与本文研究工作相关的体绘制算法基础以及体绘制技术的 研究现状，即体绘制算法绘制流程中各个阶段的概念和原理；体绘制算法以及各 种优化算法的分类、简介；体绘制技术的研究现状及其存在的问题；g p u 工作 的基本原理，c g 语言的发展。 第三章，介绍，探讨基于二维纹理和三维纹理的物序体绘制算法和基于纹理 的体绘制算法在实现中的关键技术，提出以三维纹理为基础数据结构的基于逆投 影的光线投射算法，并通过实验对算法的性能和绘制质量进行分析评价。 第四章，对体数据存在的数据一致性进行分析，针对体绘制算法绘制流程中 的融合阶段进行简化，提出基于片段的光线投射算法，对其进行理论上的推导和 分析，从理论角度提供算法的合理性和有效性证明。 第五章，从实践角度为第四章提出的基于片段的光线投射算法提供证明，实 现在算法基于c p u 的版本和基于g p u 的版本。探讨了算法在实现过程中设计的 关键技术，并通过实验结果对算法的性能进行分析评价。 第六章，对全文研究工作进行总结，并对今后的工作做出展望。 第二章体绘制研究基础 第二章体绘制研究基础 本章论述了与论文研究工作相关的体绘制算法基础以及体绘制技术的研究 现状。其中第一节讨论了体绘制算法绘制流程，介绍体绘制算法关键步骤如重采 样、分类、明暗计算、融合的概念和原理。第二节概述体绘制技术中现有的几种 算法，包括光线投射、足迹表、切错变形、体元投射、纹理映射以及频域体绘 制，并对每个算法进行简要描述。第三节对各种体绘制的优化技术进行综述和评 价。第四节在读者对体绘制算法及优化技术有了整体了解的基础上，指出体绘制 技术中仍存在并亟待解决的问题。 2 1 体绘制算法流程及其关键技术 2 1 1 体绘制算法流程概述 进行体绘制研究，首先要了解体绘制算法的绘制流水线。明白绘制流水线中 的各个阶段是如何连接并互相影响，是寻找绘制流程中存在的优化潜力的基本前 提。虽然存在多种体绘制算法且各种算法的原理不同，但是所有的体绘制算法都 要经过绘制流水线中的各阶段，最终生成结果图像。 体绘制是以定义在空间三维网格上的体数据，即三维空间网格交叉点上的采 样点集合( 每个网格交叉点对应一个采样点，称为体素，v o x e l ) 作为处理对象， 体素的值可以是标量，向量或者张量。网格结构对于体素的存储格式以及绘制过 程具有很大的影响，可以分为结构化网格、非结构化网格和混合网格，非结构化 网格和混合网格可以通过一定的几何变换转化为结构网格，结构网格又分为笛卡 尔型、等距型和矩形型三种。本文对于体绘制算法的研究工作是基于体素值为标 量( 通常定义为该采样点的密度或者亮度) 的等距型的结构化网格展开的。 图2 - l 是典型的体绘制算法的流程图。绘制流程包括以下几个阶段：预处理、 重构和重采样、分类、明暗计算、图像合成和绘制。 第二章体绘制研究基础 俸数据j l 俸数据预处理一 上 l重采样一 工 1分类一 善 i朝暗计耸一 i图像合成一 结果图像。 图2 1 傩绘制算法流程圈+ i 在预处理阶段，可以对即将进入绘制流程的体数据进行简化剔除、去噪、划 分，设计数据结构，向内存和显存装载数据，以及进行一些在绘制过程中不会动 态变化的辅助参数计算，使得真正进入绘制流水线的数据都是对最终结果有贡献 的体素，使得数据在通过绘制流水线的各个阶段时不会因为辅助数据的计算而受 到阻碍，使得在绘制过程中所用到的参数都是经过最优化选择后的结果。 预处理阶段并不真正属于绘制流程的一部分，但是通常对绘制性能的提升有 着至关重要的作用。很有优化算法都是在预处理阶段完成的，如旨在剔除无效体 素的包围盒技术( b o u n d i n gb o x ) 【4 】、八叉树( o c t r e e ) 【5 】数据结构、游程编码 ( r u nl e n g t he n c o d i n g ) 技术的计算和构造都在预处理阶段完成：以改变体绘制 算法流程中各阶段处理顺序为基础的优化策略通常将绘制流程中其他阶段的计 算任务转移到预处理阶段完成。 除了进行性能优化，预处理阶段的一些工作对绘制结果图像质量也有着不可 低估的影响。其中最重要的两个是分割( s e g m e n t a t i o n ) 和梯度估计( g r a d i e n t e s t i m a t i o n ) 。 分割【6 】阴是一个图像处理问题，是指把一幅图像分成不同的区域【8 】。体绘 制中的分割把问题从二维空间扩展到三维空间，但是其基本任务和目标是相同 第二章体绘制研究基础 的。分割的目标是让不同的数据区域代表不同的含义。首先将体数据划分成不同 的部分，对体素进行重新组织，形成更高级的表示单元，使这种高级表示单元比 体素表示更有意义，或者更有利于进一步的分析【8 】。如医学图像中将病人的正 常组织和病灶组织进行划分，为医生诊断病症和进行手术计划提供帮助。分割为 体数据的每个区域分配特定的光学属性，替代了绘制流程的分类阶段，避免绘制 结果中出现的模糊和歧义，使绘制图像质量得到极大的提高。虽然几年来在分割 领域有很大的进展，但是仍没有一种准确的自动分割算法，精细的分割过程主要 依赖各领域专家的丰富经验。设计通用、健壮的分割算法是图像领域的一个技术 难题。在体绘制处理的各种数据中，事先可以得到准确分割的很少，于是在绘制 流程中避免了分割，而是通过分类来替代这个过程的。 梯度估计【9 】【1 0 】即对空间的离散数据点进行梯度计算。梯度( g r a d i e n t ) 可 以对空间数据在各个方向上数据值变化速率和趋势进行度量。梯度是一个矢量， 通常用v 来表示，由三个方向分量上的标量数值组成，标量数值越大，表示在该 方向上数据变化得越快，而梯度大小的增加通常是边界所具有的特征。梯度是三 维体素数据在各个方向上的偏微分结果，给定一个连续数值函数，l ，y , z ) ，则该 函数的梯度为： w 咖) 降面o f ，面o f ) 在体绘制中，梯度通常用来进行明暗计算( s h a d i n g ) 以及分割、分类 ( c l a s s i f i c a t i o n ) 等需要提取体数据特征的操作。明暗计算中梯度用作表面法向量 的近似值；而在分类中则作为体数据的一个结构特征，为体素值到光学特性的映 射提供依据。常用的梯度估计方法有中心差分( c e n t r a ld i f f e r e n c e ) 法和中间差 分( i n t e r m e d i a t ed i f f e r e n c e ) 法。中心差分法通过6 个相邻体素进行计算，中间 差分法与中心差分法略有差别，它将中心差分法隔点求差值改为相邻点求差值。 梯度估计可能用更多如2 6 邻域f 1 2 】或者更少如3 邻域【1 1 】相邻体素来估计梯度。 相邻体素越多，梯度估计的精度越高，但是相应的所需计算量也增大。由于梯度 估计结果在整个绘制过程中不会有所变化，因此通常放在预处理阶段计算，却因 此增加了对系统内存的要求。 2 1 3 重构和重采样( r e c o n s t r u c t i o n & r e s a m p l i n g ) 在体绘制中，我们取得的体数据都是离散的点值，而现实中我们要绘制的对 象本身却是连续的，由连续的对象数据场通过仪器离散化为体数据的过程，称为 第二章体绘制研究基础 采样( s a m p l i n g ) 。由于精度的要求，我们很难保证在绘制过程中所要处理的点 恰好都是体数据提供的点值，如图2 - 2 。对于那些原始体数据中未能提供的点值， 需要有一种计算方法通过现有的离散点值求得数据场中的任意点值。为了达到这 个目的，还原连续的数据场是非常必要的，这个还原的过程称为重构 ( r e c o n s t r u c t i o n ) ，而在还原的连续数据场中求得绘制过程中需要的离散点值称 为重采样( r e s a m p l i n g ) 。重构只是一个概念，在实际绘制过程中没有一种方法 可以精确的重现连续数据场的原貌，并且也无法采用一种数据结构把任何精度下 的重构结果存储起来，因此重构是由重采样来体现的。重采样是在确定数据点位 置的时候，用插值( i n t e r p o l a t i o n ) 方法通过附近的体素数值近似的确定该体素 的数值。 虚线的单点处为绘制所需的重采样点 网格白勺交点处为体数据 提供的离散傩素点 图2 - 2 体数据离散点与重采样点的关系图 插值是数字信号处理和图形学中的基本操作，它通过离散信号计算连续信号 中某一点的信号值。依据奈奎斯特采样定理，对一个信号的采样频率至少大于等 于该信号最高频率的两倍，才能从离散样本中正确重构该信号，我们假定体绘制 中用到的离散体数据是符合这一采样理论的。在信号处理中，存在一个理想的插 s i n c b ) 些 值函数 x ，但是由于s m c 函数是定义在无限长的空域区间上，无法在 体绘制中直接用作插值函数。体绘制中最常用的插值方法有以下四种：最近相邻 第二章体绘制研究基础 插值、线性插值、立方卷积插值和样条插值。 插值方法和它的计算复杂度是紧密相关的，一般来说，阶数越高的插值函数 产生的插值结果越好，但同时计算复杂度也越大，重采样的时间越长。由于重采 样操作是在绘制过程中动态完成，并且重采样的频度很高，因此重采样操作时间 的长短对绘制速度具有很大的影响，必须在绘制结果图像质量和绘制速度之间作 一个折衷。实践中，线性插值是最常用的插值方法。 一般来说，重采样过程在分类和明暗计算之前，但也可以将分类和明暗计算 放在重采样过程之前在预处理阶段完成，以加快绘制时间，称为提前分类 ( p r e c l a s s i f i c a t i o n ) 、提前明暗计算( p r e s h a d i n g ) 。由于分类和明暗计算并非线 形操作，因此操作顺序的更改对最终绘制结果会有影响，但只要原始体数据的采 样率够高，绘制结果不会有严重的走样。 2 i 4 分类( c l a s s i f i c a t i o n ) 由于用于采集数据的各种仪器不具备人眼和人脑的颜色感受和辨别功能，因 此外界提供用于体绘制的数据是不能直接用于绘制的。这些数据或者是与采集对 象相关的某种物理特性，例如密度、亮度、高度等等，或者可能是没有具体物理 意义，但是仪器容易采集到并量化的参数。分类是一个映射过程，它将体数据中 无法直接用于绘制的值映射成为人眼可以识别和分析的光学特性，即颜色和不透 明度。 分类和分割在绘制中的作用类似。由于分割研究多年，尚未有稳定和精确的 成果，因此体绘制的研究人员试图在体绘制中避免分割，而用分类来代替。分类 不能够准确反映绘制对象结构，因为绘制对象结构无法由有限个数据特征唯一标 志，如最简单的，如果绘制对象的不同结构在经过采集仪器的离散化后处于不同 的数据区间，那么设置不同的阈值，为每个阈值区间分配一种光学属性即可，可 是事实上，绘制对象不同结构之间的数据都有交叉，因此更多的数据特性如梯度、 散度被用到分类操作中。分类技术不断发展，力求找到一种方法可以清晰的标志 绘制对象的不同结构，这个目标和分割不谋而合。；另一方面，虽然分类技术尚 不能非常清晰的区分数据对象结构，但是为具有某些相同属性的数据分配同样的 光学特性，如实反映了数据对象存在的状态，绘制结果并不会对用户判断造成误 导。 分类是通过传递函数( t r a n s f e rf u n c t i o n ) 1 4 1 1 5 2 1 来完成的，如公式所示： 第二章体绘制研究基础 咒 g 。 玩 以 - 玎仁) 其中r g b a 分别代表颜色的蓝、绿、红分量和不透明度，对于数据对象结 构的描述，不透明度起了至关重要的作用，而颜色只是一个强调和美化的因素， 因此在传递函数的设计中不透明度是重点。口可以是标量，也可以是向量，根据 口分量数的不同，传递函数可以分为一维传递函数、二维传递函数和多维( 三维 或者三维以上) 传递函数。一维传递函数的a 是体素值，二维传递函数加入了其 他的数据特征，最常用的是梯度。传递函数维数的增加可以更好的标志数据特征， 但同时对存储空间和初始化时问的要求也呈指数级增长，因此实践中，很少用到 多维传递函数。 2 1 5 明暗计算( s h a d i n g ) 明暗计算是模拟光在绘制对象的表面产生反射、折射、衍射等光学现象的过 程，是真实感图形绘制中不可缺少的操作，在体绘制中却不是必需的。适合的光 照可以增加体绘制结果图像的质量，使图像轮廓清晰、过渡柔和，但是如果绘制 流程中的其他阶段作的很完善，没有光照，结果图像质量也可以足够好。 体绘制中的明暗计算是以p h o n e 光照模型 1 5 1 n 基础的。该模型描述了泛光 ( a m b i e n tl i g h t ) 、漫反射( d i f f u e s er e f l e c t i o n ) 以及镜面反射( s p e c u l a r r e f l e c t i o n ) 对一绘制对象表面颜色的影响效果。 在体绘制应用中，根据插值的顺序不同，明暗计算又分为p h o n e 明暗计算【16 】 和g o u r a u d 明暗计算f 1 7 】。p h o n e 明暗计算先对数据进行重构插值和分类，取得 重采样点的颜色和法向量，而g o u r a u d 明暗计算则是先对原体数据进行分类，而 后以分类的颜色结果为基础进行重采样点的插值。 体绘制的绘制对象数据是点集，并且在重构过程中并不进行建模，重采样点 处的曲面形状、走向无从得知，因此在实践中用该重采样点的梯度来代替法向量 进行明暗计算。 2 1 6 图像合成( c o m p o t a t i o n ) 图像合成是将多个有前后遮挡重叠关系的重采样点的光学属性沿光线传播 的方向，按照一定的规则作合并处理，最终形成像素，于绘制阶段在屏幕上显示。 图像合成是以模拟现实世界中人眼观察事物这一现象为基础的，因此每一像素对 第二章体绘制研究基础 应的一系列有前后遮挡关系的重采样点是随着观察方向不同而变化的。常用的图 像合成方法有三种：最大密度投射( m i p ，m a x i m u mi n t e n s i t yp r o j e c t i o n ) 、x 光 线投射( x - m yp r o j e c t i o n ) 和不透明度融合方法( a l p h ab l e n d i n g ) 。 最大密度投射选择沿视线方向重叠的一系列重采样点中密度( 体素值) 最大 的那个重采样点，作为该视线对应的像素的密度，而后进行分类和明暗计算。最 大密度投射多用在医学影像的处理上，如c t ( c o m p u t e dt o m o g r a p h y ) 、m r a ( m a g n e t i cr e s o n a n c e a n g i o g r a p h y ) 数据。 一般来说，图像合成操作在分类和明暗计算的后面进行，合成的元素是颜色 和不透明度，但是在最大密度投射算法中，需要依据密度对重采样点进行筛选， 将图像合成操作提前，可以极大地提升性能，并不会对绘制结果产生影响。 x 光线投射与最大密度投射相似，不同之处在于它是将沿视线方向重叠的一 系列重采样点的密度进行加总，作为该视线对应像素的密度。这种合成方法产生 的图像效果类似于医用的x 光成像。 不透明度融合( 简称融合) 的方法是在体绘制中最广泛应用的图像合成方法， 产生的图像质量优于其它两种方法。融合将沿视线方向重叠的各个重采样点的光 学属性根据绘制方程进行合并。每个重采样点根据其位置和光学属性的不同，对 最后的绘制结果或多或少都有贡献。根据融合方向的不同，可以分为从前向后融 合( f r o n t t o b a c k ) 和从后向前融合( b a c k t o f r o n t ) 。融合方法包含了原始体数 据最完整的信息，让用户可以随意观察绘制对象内部结构，真正体现了体绘制的 优越之处。第四章会对融合进行详细的分析，这里不再赘述。 2 1 7 绘制( r e n d e d n g ) 绘制是体绘制算法流程的最后一个步骤，它将图像合成后的二维图像显示在 屏幕上。显示图像所用的是屏幕坐标，而重采样等操作是建立在对象坐标基础之 上的，因此需要将两种坐标进行转换。 图形学中有三个坐标系，分别为世界坐标系( w o r l dc o o r d i n a t es y s t e m ) 、局 部坐标系( l o c a lc o o r d i n a t es y s t e m ) 和屏幕坐标系( s c r e e nc o o r d i n a t es y s t e m ) ， 对象坐标系包括世界坐标系和局部坐标系。世界坐标系是固定的，它为场景中所 有的对象提供了整体的参照系，我们定义这个坐标系的原点为u ，u j 。局部坐标 系是单独提供给各对象的参照系，每个场景中的对象都有自己的局部坐标系。局 部坐标系的原点通常定义在每个对象的中心，初始的原点和世界坐标系的原点是 重合的，即场景中的所有对象初始情况下都是重叠在世界坐标系的原点上，需要 通过对局部坐标系进行平移和旋转，将这些对象摆放在世界坐标系中适当的位 置。在局部坐标系所进行的所有操作全部可以在世界坐标系下完成，但是对于结 第二章体绘制研究基础 构非常复杂的对象，定义一个自己的坐标系对于简化操作人员的工作是非常有意 义的。屏幕坐标系是定义在显示器上的，是设备相关的。和对象坐标系不同，屏 幕坐标系是一个二维( 2 d ) 坐标系统，而对象坐标系是定义在虚拟的三维( 3 d ) 世界的。 一 对一个三维场景进行绘制，坐标系之间的转换依照图2 - 3 的顺序进行。在体 绘制中，绘制对象通常只有一个。 p 瓤的芋系1 世屏 界幕 协n 的未一， 坐坐 标标 系系 图2 3 三维场景绘制的坐标变换过程 三个坐标系之间的转换是通过矩阵乘法来完成的，参与坐标系转换的过程的 矩阵有：模型矩阵( m o d e lm a t r i x ) 、视图矩阵( v i e wm a t r i x ) 和投影矩阵( p r o i e c t i o n m a t r i x ) 。模型矩阵将对象在世界坐标系中进行平移和旋转，视图矩阵设置视点 的转移。视点移近对象和对象移近视点是从不同角度进行的同样的操作，因此实 践中把模型矩阵和视图矩阵合并为一个模型视图矩阵( m o d e l - v i e wm a t r i x ) 使 用。投影矩阵完成世界坐标系到屏幕坐标系的转换。投影又分为平行投影 ( o r t h o g r a p h i cp r o j e c t i o n ) 和透视投影( p e r s p e c t i v ep r o j e c t i o n ) ，在平行投影中 绘制对象在深度变化的时候，不会产生视觉差，而透视投影认为离视点近的对象 比较大，当对象离视点越来越远的时候，对象在视觉效果上会渐渐缩小。 体绘制所用的数据出于方便都是定义在局部坐标系上的，流程中其他阶段操 作也都在局部坐标系的基础上进行的，在绘制阶段，需要将在局部坐标系上绘制 出来的结果转换为屏幕坐标系进行显示。 2 2 体绘制中的主要算法概述 在体绘制研究得初期，算法分为像序( i m a g e o r d e r ) 体绘制算法的和物序 ( o b j e e t - - o r d e r ) 体绘制算法的两种，分别以光线投射算法和足迹表法为代表。随 第二章体绘制研究基础 着研究的进展，在两者基础上提出了混合方式的体绘制算法，以切错变形算法 为代表：随着硬件技术的发达，提出了基于图形硬件的体绘制算法，以纹理映射 算法为代表；随着体绘制理论的完善，提出非空域体绘制