（计算机应用技术专业论文）基于lod方法的并行体绘制.pdf

浙江大学硕士学位论文 摘要 摘要 体绘制是体数据可视化的主要方法之一，是科学计算可视化的研究热点。体 绘制的目的是将各种体数据以图像的方式表现出来，以方便用户以直观的方式获 取信息。体数据的常见来源有科学计算数据、地震采样数据、医学数据等。 随着生成体数据的规模越来越大，体绘制技术遇到很多新的挑战。并行绘制 技术与多分辨率绘制技术( l o d ) 是大规模体数据绘制的两种重要方法，本文将 这两种方法结合起来。采用多分辨率层次结构( l o d ) 管理原始数据集能够提供 用户不同的精度数据以适应不同场合的需要，当用户概览数据时可以采用低分辨 率数据，而需要挖掘具体信息时则选择高分辨率数据。分辨率层次结构的灵活性 能够很好地均衡绘制速度和绘制质量，提高了可视化效率。 本文采用s o r t 1 a s t 并行绘制方法，在数据空间对数据集进行分割后分配给各 个集群节点并行处理，每个集群节点绘制完后再把中问图像合成最终的图像。本 文采取一系列技术提高绘制效率：采用内存映射文件技术加快数据从磁盘读取； 在绘制过程中，采用计算代理几何模板的方法，只对其中一个数据块模板计算代 理几何，其他数据块的代理几何只需要进行一定的平移即可得到，这样减少了c p u 的计算时间；在图像的合成阶段，采用b i n a r y s w a p 技术并行的对图像进行合成。 对每个绘制节点，我们采用三个进程并行工作，让不同硬件资源的利用并行 化：主线程负责绘制，一个进程负责从磁盘读取数据，另外一个进程负责图像合 成以及网络传输。 将l o d 技术与并行绘制相结合，会产生各个集群绘制节点负载不平衡的问 题，影响系统的整体性能。本文为了解决这个问题使用k d 树数据结构，根据上 一帧的绘制时间动态地分布数据，很好的达到了动态负载平衡效果。 本文在上述算法的基础上设计实现了一个高效率的并行体绘制平台。对虚拟 人生理切片数据的实验结果表明，平台对于大规模体数据绘制达到一定的交互水 平，能够获得高精度的绘制图像并显示在高分辨率多屏拼接系统上。 关键词：体绘制，l o d ，并行绘制，集群，多分辨率绘制 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t v o l u m er e n d e r i n gi so n eo ft h em a i nm e t h o d si ns c i e n t i f i cv i s u a l i z a t i o nf i e l d t h e i n t r i n s i ci n f o r m a t i o no fv o l u m ed a t a s e tc a nb ev i s u a l i z e di n t e r a c t i v e l yb yv o l u m e r e n d e r i n g t h e r e f o r et h eu s e r sc a ng e ti n f o r m a t i o nf r o mt h er e n d e r e di m a g e v o l u m e d a t ac a nb ea c q u i r e df r o md i f f e r e n ts o u r c e s ，s u c ha sd a t af r o mc o m p u t e dt o m o g r a p h y ( co ，m a g n e t i cr e s o n a n c ei m a g i n g ( m r i ) s c a n n e r so rc 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 ) w i t ht h ed e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , t h es i z eo fg e n e r a t e dv o l u m ed a t a h a sb e e ng e t t i n gl a r g e ra n dl a r g e r s u c hl a r g es c a l ed a t a s e t sp o s ei m m e n s ec h a l l e n g e s t ov o l u m er e n d e r i n g t h e r ea r et w oi m p o r t a n ta n dp o p u l a rt e c h n i q u e sf o rr e a lt i m e v i s u a l i z a t i o no fl a r g ed a t a s e t s ，p a r a l l e lv o l u m er e n d e r i n ga n dm u l t i r e s o l u t i o nr e n d e r i n g , w h i c hc o u l db ec o m b i n e da sp a r a l l e lm u l t i r e s o l u t i o nv o l u m er e n d e r i n g l e v e lo fd e t a i l ( l o d ) t e c h n o l o g yc a ns u p p l yd i f f e r e n tl e v e lr e s o l u t i o nd a t af o rd i f f e r e n tn e e d a s v i s u a l i z a t i o ni sa ni t e r a t i v ea n de x p l o r a t o r yp r o c e s s ，r e n d e r i n gal o w e rr e s o l u t i o no f d a t as o m e t i m e si ss u f f i c i e n tf o rt h ep u r p o s eo fo b t a i n i n ga no v e r v i e wo ft h ed a t a b e f o r et h eu s e rc a nq u e r yf u r t h e rd e t a i l si ns e l e c t e dr e g i o n s t h i sm e t h o dc a ni m p r o v e r e n d e r i n ge f f i d e n c y p a r a l l e lv o l u m er e n d e r i n gs o l v e st h el a r g ed a t av i s u a l i z a t i o np r o b l e mb ys p l i t t i n g b o t ht h ed a t aa n dr e n d e r i n gt a s ka m o n gc l u s t e rn o d e s i nt h i sp a p e r , w ea d o p ts o r t l a s t p a r a l l e lv o l u m er e n d e r i n gt e c h n o l o g ya n dp r o p o s eas e r i e sm e t h o d st oi m p r o v e r e n d e r i n ge f f i c i e n c y m e m o r ym a p p e df i l e st e c h n o l o g yi su s e dt os p e e du pd i s ka c c e s s a f t e re a c hn o d e sc o m p l e t et h e i rr e n d e r i n g ，w ea d o p tb i n a r y s w a pt e c h n o l o g yt o c o m p o s i t ea l ls u bi m a g e si np a r a l l e l w eu s es l i c et e m p l a t et e c h n o l o g yt or e n d e ra n y b r i c kb ys i m p l yc o m p u t i n gt h eo f f s e ta l o n gt h ev i e wd i r e c t i o na n dt h e nt r a n s l a t i n gt h e t e m p l a t es l i c ev e r t i c e sa l o n gt h ed i r e c t i o no p p o s i t eo f t h ev i e wd i r e c t i o n t oa c h i e v eg o o do v e r l a p p i n gb e t w e e nr e n d e r i n ga n dc o m m u n i c a t i o n ，e a c hn o d e f u l l st h r e et h r e a d s t h ef i r s tt h r e a dh a n d l e sr e n d e r i n g , t h es e c o n dt h r e a dh a n d l e s c o m p o s i t i n ga n d t h et h i r dh a n d l e sd a t al o a d i n g i i 浙江大学硕士学位论文 a b s t t a e t h o w e v e r , w h e nu s i n gl o dm e t h o di np a r a l l e lr e n d e r i n g , l o a du n b a l a n c eb e c o m e s ac h a l l e n g i n gi s s u e w es o l v et h i si s s u eb yu s i n gk dt r e ed a t as t r u c t u r et od y n a m i c a l l y d i s t r i b u t et h ed a t aa m o n gt h er e n d e r i n gn o d e sa c c o r d i n gt ot h el o a do ft h ep r e v i o u s f r a m e t h er e s u l ts h o wt h a tg o o dl o a db a l a n c i n gc a nb ea c h i e v e d f i n a l l y , a ne f f i c i e n tp a r a l l e lv o l u m er e n d e r i n gf r a m e w o r kh a sb e e nc a r e f u l l y d e s i g n e da n dd e v e l o p e d o u rf r a m e w o r kc a no b t a i ng o o dr e n d e r i n gs p e e da n dh i g h r e s o l u t i o ni m a g es h o w e di nl a r g es c a l ed i s p l a ys y s t e ma f t e rt e s t i n gb yv i s i b l eh u m a n i m a g ed a t as e t k e y w o r d s ：v o l u m er e n d e r i n g ，l o d ，p a r a l l e lr e n d e r i n g ，c l u s t e r ，m u l t i - r e s o l u t i o n r e n d e r i n g 浙江大学硕士学位论文 图目录 图目录 图2 1 体绘制算法流程7 图2 2 三维体数据8 图2 3 体绘制拓扑结构8 图2 4 光能量源到达人眼的衰减过程1 0 图2 5 体绘制算法框架图流程1 2 图3 1s o r t f i r s t 绘制流水线1 4 图3 2s o r t m i d d l e 绘制流水线。1 5 图3 3s o r t 1 a s t 绘制流水线1 6 图3 4 数据块间无重叠采样结果。1 8 图3 5 增加了数据重叠后的采样结果1 8 图3 6 并行绘制的文件存储结构1 9 图3 7 进程的代码页、数据页在磁盘存储器上的备份2 1 图3 8 传统的代理几何绘制方法2 2 图3 9 代理几何模板绘制方法2 3 图3 1 0 服务器与绘制节点的通讯结构2 4 图3 1 1b i n a r y s w a p 算法示意图。2 6 图3 1 2 读数据线程与绘制线程的同步2 8 图3 1 3 绘制节点中各个线程的同步2 8 图3 1 4 多分辨率数据结构3 0 图3 1 6 绘制节点选择l o d 子树集流程图3 1 图4 1 控制节点程序流程图。3 4 图4 2 控制节点程序流程图3 5 图4 3v i s i b l eh u m a n 数据集绘制图像( 分辨率为1 0 2 4 1 0 2 4 ) 4 1 图4 4v i s i b l eh u m a n 数据集近距离绘制图像( 分辨率为1 0 2 4 木1 0 2 4 ) 4 2 图4 5v i s i b l eh u m a n 数据集第一级与第二级低分辨率图像4 3 图4 6v i s i b l eh u m a n 数据集第三级与第四级低分辨率图像。4 4 图4 7 绘制节点为1 6 图像分辨率为5 1 2 5 1 2 的绘制时间走势。4 5 图4 8 不同平衡系数下的绘制速度4 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得逝姿盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：乒彳睹消l 签字日期：力帅了年舌月，日 学位论文版权使用授权书 本学位论文作者完全了解 堑姿盘堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝姿盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：关诤良 导师签名： 签字日期：二州孑年厂月 罗日 签字日期：碍年月歹日 学位论文作者毕业后去向： 工作单位：芦m 矿 通讯地址：上询涨c ，z 石升 电话：邝册i ，7 7 6 投1 习医 邮编：z 啦。弓 浙江大学硕士学位论文第1 章绪论 第l 章绪论 1 1 科学可视化与体绘制 科学可视化是以计算机图形学为基础发展而成的一门新兴的应用学科。1 9 8 7 年，由美国科学基金会的图形图像专题讨论组提交的报告中首次引入了“科学计 算可视化( 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 1 可视化是一种信息处理技术，随着科学仪器精密程度的增加，得到的各 种科学计算数据、工程计算数据以及测量数据容量越来越大，如果直接面对大规 模的抽象数据进行分析无疑是很困难的事情，而科学计算可视化的目标就是把大 量抽象数据转换成人的视觉可以直接接受的计算机图像。它将符号变为几何形 体，使研究者可以观察他们的计算结果，可以大大加快数据的处理速度以及使人 们能够观察到数据中隐含的信息，为发现和理解科学规律提供有力】：具。可视化 做为科学研究以及工程技术的一种手段，应用十分广泛，几乎涉及自然科学及工 程技术的切领域。 体绘制技术是科学计算可视化研究领域的核心。体绘制技术是一种基于光学 映射的方法，这种方法通过模拟光线在物体内部的一系列光学现象，使得到的体 绘制图像更具真实感、便于分析和想象【2 】。它能够从体数据集中抽取内在的本质 信息，并借助交互式的图形图像技术展现出来。体绘制技术研究的是如何表示、 维护和绘制体数据集，从而提供观察数据内部结构和理解物质复杂特性的机制。 在过去几年中，体绘制技术发展速度非常快。但随着计算机科学的发展和计算机 硬件性能的大幅度提高，对体绘制特别是实时体绘制的要求越来越高，所以，在 体绘制领域要不断地创新。 体绘制可视化技术的应用领域十分广泛，主要包括医学、气象学和地质勘探 浙江大学硕士学位论文第1 章绪论 等领域。在医学领域，由核磁共振、c t 扫描等设备产生的人体器官密度场，对 于不同的组织，表现出不同的密度值。通过在多个方面多个剖面来表现病变区域， 使医生对病变部位的大小、位置，有定性和定量的认识，尤其是对大脑等复杂区 域，体绘制可视化所带来的效果尤其明显。借助虚拟现实的手段，医生可以对病 变的部位进行确诊，制定出有效的手术方案，并在手术之前进行模拟。在临床上 也可以应用在放射诊断、制定放射治疗计划等。在气象领域，体绘制可视化技术 可以将大量的天文气象数据转换为直观的图像，使预报人员能对未来的天气做出 准确的分析和预测。在地质勘探领域，利用模拟人工地震的方法，可以获得地震 岩层信息。通过数据特征的抽取和匹配，可以确定地下的矿藏资源。由于地震数 据的数据量及其庞大，而且分布高度不均匀，因而根本无法从纸面数据做出分析。 利用体绘制方法对模拟地震数据进行解释，可以得到矿藏是否存在、矿藏位置及 储量大小等重要信息，大大地提高地质勘探的效率和安全性，节约资金，具有重 大的经济效益及社会效益。 1 2 研究概况 1 2 1 体绘制技术 三维空间数据场可视化方法大致可分为两大类：面绘制、直接体绘制【3 l o 面 绘制技术是从三维数据场中抽取有意义的直观信息的一种重要方法。其基本过程 是确定感兴趣物质的轮廓，并由一系列等值面表示出来，实际上是把体数据转换 成一种逼近面表示，从而进一步由传统计算机图形学技术进行绘制。由于面绘制 的绘制过程中需要构造等值面，生成中间图元，而不是直接在体数据上绘制图像， 所以面绘制技术被称为间接体绘制。面绘制有多种算法，各种算法的不同点在于 所采用的近似表面的几何单元不同或几何单元尺度的选择不同，典型算法有：m c 方法( m a r c h i n gc u b e s ) 、m t 方法( m a r c h i n gt e t r a h e d r a l ) 、剖分立方体法( d i v i d i n g c u b e s ) 等。面绘制只适用于绘制表面特征分明的组织和器官，对过渡平缓的体 数据绘制效果不佳。而且面绘制只能显示物质的轮廓信息，内部信息无法保留。 由于面绘制有诸多缺点，所以一般都是采用直接体绘制，本文主要讨论直接体绘 2 浙江大学硕士学位论文第1 章绪论 制。 体绘制的研究始于2 0 世纪7 0 年代。它伴随着c t 、m r i 等医学成像技术的 产生而发展起来的，随着l e v o y 和d r e b i n 等人提出直接体绘制算法1 4 i ，直接体绘 制技术已经成为三维数据场可视化的一种重要方法，它在一定程度上脱离了传统 图形学点、线、面的束缚，对象不再是以点、线、面等传统图形学表示形体的方 法组成的三维实体，而是由体素作为基本的单元，数据场是由大量的体素组成的。 对于此类数据场的绘制方法不同于传统的面绘制方法。它采用体光照模型直接从 三维数据场中绘制出各类物理量的分布情况。这种方法能产生高质量的图像。与 面绘制方法相比，直接体绘制免去了面绘制中构造几何多边形等表面的中间过 程，采用直接对所有的体数据进行明暗处理的方法，进而合成为具有三维效果的 图像。它可以使用来自一个物体的表面和内部的数据，而不仅仅显示等值面上的 数据，也就是无须进行分割即可直接进行绘制，有利于保留三维医学图像的细节 信息，增强整体的绘制效果。典型算法有光线投射法、s p l a t t i n g 体绘制算法，基 于错切一变形技术( s h e a r - w a r p ) 的体绘制算法和体元投射法等。 1 2 2 并行体绘制技术 随着科学技术的发展，获取体数据的设备越来越先进，生成体数据的分辨率 和规模越来越大。这为体绘制技术带来很多新的挑战。因为单台计算机无论是存 储还是计算速度上都无法满足大规模数据的绘制要求。所以基于集群的并行体绘 制是解决大规模体绘制的可行方法。 基于集群的并行体绘制技术将一个大的任务分割为很多小任务并分配给各 个集群节点，接着由各个集群节点并行的绘制和计算。这样，绘制的速度能够大 大的提高。其中对任务的分割可以在图像空间也可以在数据空间。每个集群节点 绘制完后再把得到的中间图像合成最终的图像。并行绘制技术突破了孤立图形系 统的局限，高性能的图形并行体绘制系统能够实时绘制大规模数据，大大节省用 户交互时间。 并行绘制技术的基础是绘制流水线内在的可并行性。绘制流水线主要由几何 3 浙江大学硕士学位论文第1 章绪论 处理和光栅化两个部分组成。几何处理包括模型场景变换、光照处理等步骤，它 的任务是将几何图元从物理空间的三维坐标转换到屏幕空间的二维坐标，并计算 顶点的颜色、深度等属性。光栅化阶段的主要操作有纹理映射、深度比较和a l p h a 混合等。光栅化的任务是由图元的屏幕坐标和顶点属性计算出像素值，并存入帧 缓存。将多条绘制流水线并列运行就可以实现并行绘制系统。 1 3 论文内容和结构 1 3 1 论文内容 本文首先介绍体绘制的一些基本概念，面绘制和直接体绘制的几种算法以及 目前广泛采用的体绘制算法的具体步骤。 接下来，讨论了并行体绘制问题以及l o d 方法。包括并行绘制系统的分类 及其各自优缺点以及怎么设计高效率的并行体绘制算法。为了提高绘制效率，本 文采用了l o d 方法管理数据集。这种方法将数据采样为不同的分辨率层次，提 供用户不同的精度数据以适应不同场合的需要，当用户概览数据的时候可以采用 低分辨率数据，这样可以大大的加快绘制速度。而需要挖掘数据具体信息时候可 以根据需要选择高分辨率数据。这样能够很好的在绘制速度和绘制质量之间做均 衡，很好的提高了效率。 为了更好的利用集群系统，提高绘制效率，本文采用了b i n a r y - - s w a p 方法并 行的合成图像。在图像合成的早期阶段，每台集群节点负责合成的图像区域比较 大，但是图像是由少数集群节点所贡献的。随着图像合成的加进，每台集群节点 合成的图像区域越来越小，但是图像中不同节点的贡献因素越来越大，直到最后， 每台集群节点得到的图像包含所有节点的绘制图像因素，这个即是最终的合成结 果。但是这个只是最终图的一部分。所有的集群节点将图像数据向控制节点发送， 控制节点然后将其拼接起来就可以得到完整的图像结果。 最后，本文设计并实现了一个通用的并行体绘制算法平台。并在此平台基础 上，绘制了由美国国家医学图书馆发起建立的v i s i b l eh u m a n 数据集。本文中详 细介绍了平台的设计、实现。 4 浙江大学硕士学位论文 第1 章绪论 1 3 2 论文结构 第一章是绪论，对科学计算可视化和体绘制技术产生的背景、应用领域、研 究现状和发展方向进行了概述，并且介绍了本论文的内容以及各章的内容提要。 第二章介绍了体绘制的基本概念和基本算法，如光线投射法、s p l a t t i n g 体绘 制算法，基于错切一变形技术( s h e a r - w a r p ) 的体绘制算法等。 第三章主要讨论了并行体绘制的问题，介绍了并行计算的一般概念、并行计 算机体系结构、并行绘制的分类方法以及提出了基于多分辨率层次结构的大规模 数据并行体绘制算法。本章详细说明了数据集层次结构的建立方法以及并行体绘 制算法。 第四章详细介绍了并行体绘制平台的设计与实现，在此章的最后列出了绘制 结果以及对它的分析。 最后一章总结了论文所做的工作，提出了研究中存在的问题，并对后继研究 工作的方向作了展望。 1 4 本章小结 本章对科学计算可视化和并行绘制技术产生的背景、应用领域、研究现状和 发展方向进行了概述，并且介绍了本论文的内容以及各章的内容提要。 5 浙江大学硕士学位论文第2 章体绘制技术介绍 第2 章体绘制技术介绍 体绘制技术是一种基于光学映射的方法，这种方法通过模拟光线在物体内部 的一系列光学现象，使得到的体绘制图像更具真实感、便于分析和想象。光学映 射法将三维数据场映射到一个具有透明特性，由体素作为基本造型单元的系统。 通过该系统描述光线穿过体数据场，在一定光照条件下呈现出来的各种亮斑、颜 色等照明特性，从而反映数据场的整体信息和内部信息。其过程就是将离散分布 的三维数据场，按照一定的规则转换为图形显示设备帧缓存中的二维离散信号， 即生成每个象素点颜色的r 、g 、b 值。直接体绘制算法很多，但是基本步骤大 致相同。如图2 1 所示。 第一步是获取体数据。根据应用场合，数据的获取方式可以有多种渠道。比 如医学图像通过c t 和m r i 设备获得；而一些科学计算数据可以由计算机程序模 拟产生。在这个过程中包括对数据的预处理，如由非规则网格到规则网格的重采 样、增强对比度和去噪声等。 然后是数据分类。数据分类就是对每个体数据根据其标量值赋予r ，g ，b ， a 等光学特性，这是最为关键的步骤。这个过程将决定哪些体数据可见，哪些不 可见，对最终的绘制结果产生非常大的影响。传输函数( t r a n s f e rf u n c t i o n ) 就是 数据分类的方法，它将数据值以及其它信息作为输入，将原始数据集中的物质进 行分类，输出每一类物质对应的颜色、不透明度等光学属性。传输函数的设计是 非常重要的。好的传输函数可以清晰的显示用户感兴趣的区域，而不好的设计将 得到不理想的图像，甚至是一片模糊，信息含量很少。传输函数的设计既依赖于 数据本身，又和用户的目标密不可分。 最后是绘制显示。确定视参数，如视点、投影类型( 平行或透视) 、剖面位 置等信息，将第三步产生的几何图素和属性转换为可供显示的图像。体绘制的流 程如图2 1 。 6 浙江大学硕士学位论文第2 章体绘制技术介绍 图2 1 体绘制算法流程 2 1 体数据的分类及表示 可视化的数据来源很广泛，既有来自科学计算的，也有来自工程测量的，还 有来自生产实践的。其中常见的是通过各种科学仪器、设备扫描而得到的，医学 上常见的有核磁共振、c t 等。这些数据可以是一维的、二维的、三维的、四维 的甚至更高维的，其中三维的研究最为热门。 体绘制的对象一般是指空间上离散的三维数据，根据数据场中样点分布的空 间几何特征，数据场一般分为结构化数据与非结构化数据。结构化数据是指，在 逻辑上组织成三维数据的空间离散数据，如图2 2 【5 1 。也就是说，这些空间离散数 据的各个元素具有三维数组各元素之间的逻辑关系，每个元素都可以有它自己所 在的层号、行号和列号。符合这一条件的三维空间数据就称为结构化数据【1 1 。而 非结构化数据是由一系列的单元构成的，但是，它不能组织成三维数组。这些单 元可以是四面体、六面体、三棱柱或者四棱锥等。这些单元的面可以是平面，也 可以是曲面；其边可以是直线段，也可以是曲线段。这种数据类型常常出现在有 限元分析和计算流体力学中。在它的数据结构里，必须给出每个数据点的空间位 置及其相互间的连接关系。体数据的拓扑结构如图2 3 。 7 浙江大学硕士学位论文 第2 章体绘制技术介绍 图2 2 三维体数据 规则数据场的另一种常见的表示方法是八叉树表示，通常用于加速算法中， 但是由于通常规则数据场所需的存储空间巨大，而且八叉树相对于3 d 数组表示 还需要相当多的额外存储空间，因此，怎样对八叉树进行组织是此类算法重点讨 论的问题之一，但是通常利用八叉树的线性存储是一种可行的方法，通常八叉树 的线性存储在能够利用八叉树特性的同时可以减少相当大的存储需求。 图2 3 体绘制拓扑结构 2 2 体绘制的基本理论 跟非直接绘制方法需要从体数据中提取表面不一样，直接体绘制根据传输 函数赋予每个体素r ，g ，b ，a 等光学特性，并且按照光学模型将采样点投影到 图像平面最后合成为完整的图像。 固 浙江大学硕士学位论文 第2 章体绘制技术介绍 2 2 1 光学模型 直接体绘制算法将体数据视为能够发送光能量而且有一定密度的物质，体素 的密度或多或少的映射成r g b a 值并且沿着视线方向合成1 5 1 。这个过程基于一个 物理光学模型。n e l s o nm a x 在他的论文里详细描述了比较常用的体绘制光学模型 1 6 】，这里我们只做简要的概括： ( 1 ) 只吸收光学模型： 体数据假设由黑色的冷物质组成，不会发射光线。 ( 2 ) 只发射光学模型：体数据假设由只发射光线但不会吸收任何能量的物质 组成，因为吸收部分是可以忽略的。 ( 3 ) 吸收加发射光学模型：这种模型在体绘制中最常见。体数据中的微粒能 够发送而且能够遮挡光线，比如能够吸收入射光线。但是，它们不能间接照明或 者散射。 ( 4 ) 散射和渲染模型：这种模型要考虑体数据的外部散射源对体数据产生的 影响。 在上述光学模型中，吸收加发射光学模型的应用最为广泛，我们在下一节描 述体绘制积分时也是用这种模型。 2 2 2 体绘制积分 每一种直接体绘制算法都有自己的计算体绘制积分的方法1 5 1 。光线投射算法 是一种比较直观的方法。在该算法中，投射到体数据上的光线被表示为z o ) ，其 中t 表示视点到数据点的距离，而在距离为t 位置处的相应的数据标量值被表示 为s o p ) ) 。如果我们采用吸收和发射光学模型，体绘制方程需要沿着光线对吸收 系数k ( s ) 和发射颜色c o ) 进行积分。为了使得表示简单，发射系数c 和吸收系数 k 被表示为距离t 的函数c ( t ) = c g o o ) ) ) 和尼o ) = 七o o o ) ) ) 。 图2 4 【5 】说明光线发射和吸收的原理。距离t = d 处发射的光能量在到达视点 的过程中会持续的被其他物质所吸收。这意味着原来能量为c 的光源只有一部分 能量c 到达视点。如果吸收系数是常数，那么 c c e - h 。( 1 ) 9 浙江大学硕士学位论文 第2 章体绘制技术介绍 但一般的，沿着光线的吸收系数不是常数，而是随着距离不断变换，那么到达视 点的能量c 要通过沿着光线从视点到发射点的积分得到 c 。c e - j ( k ( t ) a t 。( 2 ) 指数项的吸收系数积分可表示为 所( 口，6 ) 。f 七( f 渺。 ( 3 ) 上式表示的是某一点发出的辐射能量最终能到达视点的情况。如果要计算整个光 线中所有的点，我们需要对所有的位置t 进行积分 c f c o ) e - m ( o ，) d t ( 4 ) 而体数据是离散的，实际计算时这个积分是通过数值计算得到的，可以通过从后 往前或者从前往后地作合成( a l p h ab l e n d i n g ) 来得到。 i l l l l l l l l l l l l l 二：= = = 二= 二= = = = = = = = 二二二二l t = o 一。4 b s 。r p t i 。疗t = d 图2 4 光能量源剑达人跟的衰减过程 2 2 3 光线投射 光线投射是以图像空间为序的直接体绘制算法【4 1 ，它是体绘制积分公式的一 种数值计算方法。其步骤是对屏幕上的每一个像素点，沿视点发出视线穿过该象 素点，穿过三维数据场，沿这条光线进行等距离采样，使用三线性插值作为重构 滤波器，由距离某一采样点最近的八个体素求得采样点的标量值，然后通过传输 函数将该标量值映射为r g b a 颜色值以及不透明度等光学特性。当该射线方向上 所有采样点的颜色值和不透明度值得到之后，采用由后到前或由前到后的的方法 将每一采样点的颜色及不透明度进行合成以求得体绘制积分。在公式( 3 ) 中， 积分深度m 是沿着视线方向的累积吸收系数，可以近似的表示为r i e m a n n 和的形 式： 1 0 浙江大学硕士学位论文第2 章体绘制技术介绍 胁。荟七( f 。出洫 5 其中缸为两个连续采样点的距离。将上式右边代到公式中，可以表示为一系 列指数项的乘积 p ”一兀p 以俨叫血 ( 6 ) 将不透明度a 定义为 a ：；1 一e - t “) ，( 7 ) ( 6 ) 可以重新改写为： p 1 0 。2 ( 1 - a i ) 8 ) 这样a ；可以近似表示在光线的第i 段的吸收系数。类似的，光线的第i 段发 射的颜色值可以近似地表示为c i = c ( i a t ) a t 。有了这两项近似表示，我4 f - i 以 将体绘制积分最终近似为： c 2 荟c f i ：i ( 1 - a i ) 舻r 缸 ( 9 图2 5 是体绘制算法框架图。 2 2 4 不透明度合成( a l p h ab l e n d i n g ) ( 9 ) 式的具体计算可以迭代的按照从后往前的顺序作不透明度合成来得到， 其中i 从n 一1 变化到o ： d = c ，+ ( 1 4 ) + ， ( 1 0 ) d 是由位置i 处的颜色c ，和前面i + l 位置处的累积颜色作合成得到的，起始 位置c ：t0 ，上式的物理意义很清晰，由于位置i + l 体数据被i 处的体数据所遮 挡，所以被吸收的部分为加，穿过的能量为1 加。当i 为0 时，即为所有光线上 所有体数据对象素的贡献。 类似的，当按照从前往后的顺序计算体绘制积分时，i 从1 变化到n ： c 。一一- + ( 1 4 一- ) c i ( 1 1 ) 4 4 d + ( 1 4 一，x 4 f 1 1 浙江大学硕士学位论文 第2 章体绘制技术介绍 ( 三维空问教据场 ) 1 l ，、 ( 数据预处理 ) 上 ，、 (设计传输函数) 上 (发出射线，取采样点) 、l + i 由镑输函数得到采样 由传输函数得到采样 点颜色值 点不透明度值 上 计算光照 j r 采样点亮度值 + (图像合成) 0 l 绘制结果 ) 图2 5 体绘制算法框架图流程 按这种顺序合成是一个累加的过程，不透明度必然会逐步增大。当不透明度 接近1 时，后面的体素对象素点的贡献已经很少，可以忽略，因而可以不再计算 了。但是这种方式需要跟踪记录不透明度值，因而在基于g p u 加速的体绘制中 通常使用从后往前的方式。 2 3 本章小节 本章介绍了体数据的来源以及分类，以及体绘制中的四种光学模型：只吸收 光学模型，只发射光学模型，吸收加发射光学模型，散射和渲染模型。还有详细 介绍了体绘制算法的流程以及原理，分析了体绘制算法公式的物理意义。 浙江大学硕士学位论文第3 章基于l o d 方法的并行体绘制 第3 章基于l o d 方法的并行体绘制 目前，来自超级计算、天体物理、气象学、有限元分析、航空航天以及医学 等领域的信息量都以几何级数的速度增长。海量数据的获取使得对数据可视处理 的需求和复杂程度出现根本性交化。现有的单处理机图形工作站远远不能实现对 庞大数据集的实时处理川。由于超级计算机价格方面的因素，随着互连网络和p c 机性能的提高，集群被广泛的使用。特别是近年来，图形硬件性能的迅猛提高使 得基于集群的并行体绘制成为实时可视化有效的解决方案。使用集群系统有下列 优点：1 ) 高可用性：集群中的一个节点失效，它的任务可以转移给其他节点。 可以有效防止单点失效；2 ) 高性能：负载平衡集群系统允许同时接入更多的用 户；3 ) 高性价比：可以采用廉价的符合工业标准的硬件构造高性能的系统。而 采用多分辨率的层次结构( l o d ) 管理大数据集也是提高效率的有效途径。这种 方法能够提供用户不同的精度数据以适应不同场合的需要，当用户概览数据的时 候可以采用低分辨率数据，这样可以大大的加快绘制速度。而需要挖掘数据具体 信息时候可以根据需要选择高分辨率数据。这样能够很好的在绘制速度和绘制质 量之间做均衡，很好的提高了效率。 3 1 并行绘制技术简介 并行绘制充分利用集群系统的系能，将绘制任务细分并行处理，大大的提高 了绘制速度，为海量数据场景绘制、大规模虚拟现实和仿真、超高分辨率科学 计算可视化等高端应用提供了实时绘制的能力。一个并行绘制系统包含多条图形 绘制流水线，按照绘制流水线的组织方式，并行绘制系统可分为s o r t f i r s t 、 s o r t m i d d l e 、s o r t 1 a s t 三种i 引。 s o r t f i r s t 方法在图形流水线的几何处理阶段对图元进行分配，如图3 1 【8 l ，将 屏幕划分成多个子区域，并将每个子区域分配给相应的集群节点。开始，图元的 分配是随机的。可以通过计算图元包围盒对应的屏幕坐标来判定图元对应哪个屏 幕子区域，这个步骤称为预变换。当图元所在的屏幕子区域跟图元当前驻留的绘 1 3 浙江大学硕士学位论文第3 章基于l o d 方法的并行体绘制 制节点所应该负责的子区域不一致时，要通过网络将图元传递到实际应该负责绘 制它的节点上，这个步骤称为数据重分布。当每个图元的分布决定以后，开始进 入各个节点的绘制流水线，经过几何处理、光栅化等步骤之后，得到屏幕子图像， 然后将这些子图像按照相对位置关系简单的拼接起来就能得到最终的图像。 g r a p h i c sd a t a b a s e ( a r b i t r a r i l yp a r t i t i o n e d ) 1 j r d i s p l a y ( p r e t r a n s f o r m ) g e o m e t r y p r o c e s s t n g r a s t e r i z a t i o n 图3 1s o r t f i r s t 绘制流水线 从图3 1 可以看到，集群中的每个绘制节点实现了完整的图形绘制流水线， 得到了相应的子图像。集群节点之间需要通信较少，通信代价较低。当帧之间有 相关性时这个优点更突出。然而，s o r t f i r s t 方法有很多缺点，主要包括： 数据的重分布，因为在实际绘制时会有大量的图元进入错误的绘制节点，当 图元经过预变换后，错误的图元要进行重分布，这使得预变换跟图元重分布后在 实际节点上的几何处理相互重复，使得计算浪费。 存在图元落在多个子区域的情况，这时候相应的绘制节点都要导入并且绘制 这个图元。如果这种图元有很多，会导致绘制效率的降低。 1 4 浙江大学硕士学位论文第3 章基于l o d 方法的并行体绘制 容易造成绘制节点间的负载不平衡：因为任务的分配是根据屏幕划分的，而 不同的屏幕位置的图元数量很有可能相差较大，当几何图元在屏幕上分布不均匀 时，一些绘制节点因处理大量图元而处于忙碌状态，同时另一些节点因分配到稀 疏的图元而处于空闲，负载的不平衡将导致绘制速度的下降，严重影响系统性能。 由于有上述诸多缺点，而且不容易克服，所以在实际运用中s o r t f i r s t 不是很 常见。s o r t f i r s t 系统有w i r e g l 、d i s p l a yw a l l 等。 s o r t m i d d l e 方法在绘制流水线的几何处理和光栅化阶段之间重分布图元，如 图3 2 【8 l 这时图元已经变换为了屏幕坐标系下，所以在实际上打断了图形绘制流 水线。同s o r t f i r s t 方法一样，屏幕划分成多个子区域，每个绘制节点的光栅化器 对应一个屏幕子区域。而对于体绘制领域，s o r t m i d d l e 运用的极少，意义不大。 故在这里不作详细的介绍。 g r a p h i c sl a t a b a s e r a p h c sd a t a b a s e ( a r b i t r a r i l yp a r t i t i o n e d ) d i s p l a y g e o m e t r y p r o c e s s i n g r a s t e r i z a t i o n 图3 2s o r t - m i d d l e 绘制流水线 s o r t 1 a s t 方法在各个绘制节点已经将图元光栅化为象素之后进行图像的合 塑坚奎堂堡圭兰篁堡奎兰! 皇苎