（计算机科学与技术专业论文）面向核模拟的三维可视化技术研究与系统实现.pdf

国防科学技术大学研究生院学位论文 摘要 目前，科学计算可视化作为一种分析、挖掘与处理海量数据的有效手段，在 核模拟高性能计算应用领域发挥着越来越重要的作用。该领域的数据集通常具有 大规模、高维、复杂等特点，这些对传统的可视化建模、实时交互、数据并行绘 制等技术与方法提出了更高的要求和挑战。 本文在系统地研究与分析了传统三维几何实体可视化建模技术、三维空间区 域选择算法与可视化软件结构的基础上，面向核模拟可视化需求，基于高性能计 算环境对复杂三维实体可视化建模、实时交互绘制、并行绘制等关键技术展开了 深入研究，并完成了相关算法与原型系统实现。本文的主要工作和取得的主要研 究成果包括： 1 ) 提出一种高效复合的复杂几何实体可视化构造与表示算法。本文对多种相关算 法进行了深入研究和分析，针对存在存储空间需求大、绘制精度不高的问题， 新算法采用优化的空间单元表示法来记录实体信息，并结合表面模型对实体进 行实时可视化绘制，提供c s g 实体描述接口。实验结果表明新算法具有模型 描述准确、接口清晰、存储空间需求小与绘制模型精度高的优点，实体信息的 获取效率与传统方法相比可提高5 0 以上。 提出一种基于动态截面方法的实体数据抽取方法。本文在研究了现有区域选择 算法的基础上，针对已有算法存在计算量大、效率低的问题，本文以实体内点 坐标c s g 表达式特性为理论依据，采用动态截面技术实现拾取点的自由选择， 从而提供了实体选择、数据抽取与编辑等高级可视化交互方法。实验结果表明 新方法与传统算法相比具有拾取点定位精确、实时交互性好、数据抽取效率高 的特点，适用于不规则复杂嵌套实体集。 3 ) 为提高数据并行可视化效率，在研究现有并行可视化系统软件结构的基础上， 设计了一种支持多种运行模式与资源灵活配置的高可配优化软件结构。并对解 决s o r t - f i r s t 并行绘制模式中负载平衡问题的静态划分算法进行了改进，提出 一种改善负载平衡可控性的屏幕区域分配策略，分析表明采用该分配策略负载 平衡可控性与静态算法相比有较大提高。 钔在对上述算法进行分析设计与实现的基础上，构建了复杂几何实体可视化建模 与实时交互绘制原型系统y h d v s 。并针对m c n p 4 c 的b e n c h m a r k 数据进行 了应用研究与开发。结果表明系统具有交互性好、可视化功能较强、支持多窗 口绘制等特点。 主题词：科学计算可视化，核模拟，可视化建模，实时交互，并行绘制，y h d v $ 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t a sa l le f f e c t i v ei i l s m m l e mu s e df o ra n a l y 出舀d i g g i n ga n dp r o c e s s i n gt r e m e n d o u s d a t a s e t , v i s u a l i z a t i o ni ns c i e n c ec o m p u t i n gi sp l a y i n gm o r ea n dm o r ei m p o r t a n tr o l ei n a p p l i c a t i o nd o m a i no fh i g h - p e r f o r m a n c en u c l e a rs i m u l a t i o nc o m p u t i n g t h ed a t a s e ti n t h i sd o m a i nw h i c hi s u s u a l l yl a r g e s c a l e , h i g h - d i m e n s i o na n dc o m p l i c a t e d , b r i n g f o r w a r dh i g h e rc h a l l e n g et ot h et r a d i t i o n a lt e c h n o l o g ya n dm e t h o di nv i s u a l i z a t i o n m o d e l i n g ，r e a lt i m ei n t e r a c t i o na n dp a r a l l e lr e n d e r i n g b a s e do nt h er e s e a r c ho ft r a d i t i o n a l3 dv i s u a l i z a t i o nm o d e l i n gt e c h n o l o g y ，r e g i o n p i c k i n ga l g o r i t h m a n dv i s u a l i z a t i o ns o f t w a r ea r c h i t e c t u r e , w eh a v ea n a l y z e dt h e r e q u i r e m e n t si nn u c l e a rs i m u l a t i o nv i s u a l i z a t i o n , a i m i n ga tt h er e s e a r c ha n dr e a l i z a t i o n o f m o d e l i n ga n dr e a lt i m ei n t e r a c t i o nt e c h n o l o g y , a l s oa tt h er e s e a r c ho f f l e x i b l ep a r a l l e l r e n d e r i n go nh i g hp e r f o r m a n c ec o m p u t i n ge n v i r o n m e n t t h ec o n t r i b u t i o n sa n d r e l e v a n t w o r ki nt h ep a p e ra l ea sf o l l o w s ： f i r s t l y ，ac o m p o u n dm o d e l i n ga n dd e s c r i p t i o na l g o r i t h mo fc o m p l i c a t e ds o l i d m o d e li sp r e s e n t e df o rh i g he f f i c i e n c y w eh a v ea n a 】y e ds o m ee x i s t e da l g o r i t h m s t o s o l v ep r o b l e m so fl a r g em e m o r yr e q u i r e m e n ta n dl o wr e n d e r i n gp r e c i s i o n , t h en e w a l g o r i t h mw i t hc s gd e s c r i p t i o ni n t e r f a c ea d o p to p t i m i z ec e l lr e p r e s e n t a t i o nm e t h o df o r s o l i dm o d e lr e c o r d i ti si n d i c a t e db ye x p e r i m e n tt h a tt h ei l g wa l g o r i t h mh a sc a p a b i l i t i e s o f e x a c tm o d e ld e s c r i p t i o n , l e s sm e m o r yr e q u i r e m e n ta n dh i g h e rr e n d e r i n ga c c u r a c y s e c o n d l y , as o l i d - i n s i d e d a t ap i c k i n gm e t h o db a s e do nd y n a m i cs e c t i o ni s p r e s e n t e d w eh a v ea n a l y z e ds o m ee x i s t e dr e g i o np i c k i n ga l g o r i t h m s ，w h i c hh a v es o m e p r o b l e ma sl o we f f i c i e n c y f i r s tw em a d et h ef u n c t i o no fp i c k i n gt a r g e tp o i n tf r e e l y c o m et r u ew i t hd y n a m i cs e c t i o nm e t h o d t h e nd a t ap i c k i n ga sa na d v a n c e di n t e r a c t i o n a lm e t h o di sc a n i e do u td e p e n do ht h ec s ge x p r e s s i o nc h a r a c t e r i s t i c c o m p a r e dt o t h et r a d i t i o n a lo n e s ，n e wm e t h o di se x c e l l e n ti nt a r g e tp o i mo r i e n t a t i o n , i h t e l a e t i o n c a p a b i l i t ya n dp i c k i n ge f f i c i e n c y t h i r d l y , t h ea r c h i t e c t u r ei sp r e s e n t e dt oe n h a n c et h ev i s u a l i z a t i o ne f f i c i e n c yi n p a r a l l e lm o d e b a s e do nt h er e s e a r c ho ft h ea r c h i t e c t u r ei ns o m ee x i s t e dv i s u a l i z a t i o n s y s t e m s , w ep r e s e n tn e w a r c h i t e c t u r ew h i c hc a nb eu s e dt oc o n f i g u r er e $ o l l z c e sf i e e l y a n dan e ws a e nr e g i o nd i s t r i b u t i o ns t r a t e g yi sp r e s e n t e dt oe n h a n c et h es t a b i l i t yo f s t a t i cd i s t r i b u t i o na l g o r i t h m f i n a l l y , w eh a v ed e v e l o p e dap r o t o t y p es y s t e my h d v sb a s e do na n a l y s e sa n d r e a l i z a t i o no fa l g o r i t h m sa b o v e y h d v sh a sb e e na p p l i e dt ot h em c n p 4 cb e n c h m a r k d a t as u c c e s s f u l l y k e yw o r d s ：v i s u a l i z a t i o n i ns c i e n c e c o m p u t i n g ，n u c l e a rs i m u l a t i o n v i s u a l i z a t i o nm o d e l i n g ，r e a lt i m ei n t e r a c t i o n ，p a r a l l e lr e n d e r i n g ，y h d v s 第i i 页 国防科学技术大学研究生院学位论文 图目录 图1 1 核模拟、可视化建模与绘制技术 图1 2 c s g 树。 图1 3 半空间构造体素。 图1 4 论文结构 图2 1 结构化数据 图2 2 多边形数据拓扑结构类型 图2 3 流水线连接方式 图2 4 特殊流水线拓扑 图2 5 流水线执行方式 图2 6 曲面绘制流水线。 图2 7 方程采样算法 图2 8 空间数据内存表示。 图2 9 由半空间构造实体。 图2 1 0 空间单元实体表示法。 2 6 9 。1 2 1 3 。1 5 1 7 1 9 图2 1 1c s g 与空间单元混合模型2 0 图2 1 2 空间单元表示与绘制优化2 1 图2 1 3 实验数据绘制效果 图2 1 4 采样加速比估算值与实验结果比较图 图2 1 5 实体表示优化算法效果对比图 图3 1h r 7 u 实验系统几何剖面示意图 图3 2 三维场拾取点获取方法。 图3 3 截面抽取方法流程 图3 4 射线法临界情况 图3 5 基于实体选择的数据抽取流程一 图3 6 实体拾取验证图 图4 1 总体结构 图4 2 绘制流水线结构 图4 3 流水线并行执行流程。 图4 4 前分布拼接合成中的几何数据集分布模式 2 5 2 7 2 8 2 9 3 ( ) 。3 3 3 6 3 7 图4 5 图元不均衡分布的屏幕划分 图4 6 各种负载平衡算法 图4 7 屏幕区域分配策略流程图 4 2 第v 页 国防科学技术大学研究生院学位论文 图4 8 各功能模块独立时的物理连接方式4 5 图4 9 客户端服务器模式的模块分配4 5 图4 1 0 三种绘制流水线组织形式4 6 图4 1 l 图元分布模拟4 8 图5 1y h d v $ 总体结构5 0 图5 2y h d v s 类图 图5 3y h d v $ 界面5 2 图5 4y h d v $ 建模可视化流水线 图5 5y h d v s 绘制效果图 图5 6y i - i d v $ 用于m c n pb e n c h m a r k 测试数据的绘制效果。 5 5 第页 国防科学技术大学研究生院学位论文 表目录 表1 1m c n p 输入卡参数分类 表2 1 三种模型比较 表2 2 空间立方体表示数据结构 表2 3 平面方程采样加速比估算值 表2 4 平面方程采样加速比实验结果 表3 1 正方形节点数据结构表示 表4 1 新的图元数据结构 。1 6 。2 3 2 3 2 9 表4 2 屏幕区域分配算法伪码 表4 3 三种流水线组织形式的特点。 表5 1 单进程与4 进程可视化绘制时间比较5 6 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：亘囱丝搓挞数三丝互趣焦拄盔赞塞曼歪红塞理 学位论文作者签名：盔蕴生日期：凸6 6 年f f 月 j 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的金部或部分内容编入有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：堑自璧搓熊鲍三丝互塑焦挂盔叠容复丕缝塞理 学位论文作者签名：垄鱼生坠日期：z 一。年f 月f r 日 作者指导教师馘：二害阻日期：二口吖年月移日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题研究背景 科学计算可视化( v i s u a l i z a t i o ni ns c i e n c ec o m p u t i n g ) 是应用计算机图形学和图 像处理等技术，将科学计算产生的数值结果转化为图形、图像，在屏幕上显示出 来并进行交互处理的理论、方法和技术【l 】。它涉及到计算机图形学、图像处理、人 机交互、计算机辅助设计等多个领域，已成为研究数据表示、数据处理、辅助分 析等一系列问题的综合技术。1 9 8 7 年2 月在美国国家科学基金会召开的研讨会上 正式给出其定义，标志着科学计算可视化作为一门学科的正式诞生。近二十年来， 其应用领域不断扩大，主要包括核模拟、航空航天、空间信息处理、数值气象预 报、医疗诊断、流体力学等领域。 高性能计算对国民经济和军事有着重要的影响，它在许多领域能够解决传统 计算无法完成的问题，如核爆炸模拟、中长期气象预报、人类基因组测序、超音 速喷气式发动机研制等 2 1 。目前，主流的高性能计算机系统有并行向量机系统 p v p ( p a r a l l e lv e c t o rp r o c e s s o r s ) 、大规模并行处理系统m p p ( m a s s i v ep a r a l l e l p r o c e s s i n g ) 以及集群式计算机系统( c l u s t e r ) 等。由于科学与工程计算中的数值模拟 规模与精度不断扩大与提高，其产生的结果数据也随之呈几何级数增长，这对传 统的科学计算可视化提出了巨大的挑战；同时可视化是数据和计算密集型应用， 它又对高性能计算提出了更高的要求。 核模拟是高性能计算的重要应用领域，它采用大规模数值计算方法求解核反 应过程的数学物理模型，其中中子输运过程模拟是核计算的重要部分，而蒙特卡 罗方法以其完善的物理建模、复杂的几何描述能力、无需离敌、收敛速度跟维数 无关等优点一直在中子输运模拟中占有重要的地位。可以说，在核科学领域，蒙 特卡罗方法是最主要的方法之一美国能源部宣称，自从高性能计算机应用以来， 蒙特卡罗模拟花费了一半以上的机时【6 l 】。在蒙特卡洛方法中，大量的实体结构信 息被用作模拟程序的输入，采用可视化的手段代替传统的手工文本输入已成为主 流。基于高性能计算环境的并行绘制技术成为对海量数据进行可视化的必备条件， 而三维几何实体可视化建模与实时交互技术则是提高复杂实体集建模精确性与效 率的关键技术 4 1 。图1 1 以蒙特卡洛方法为例描述了核模拟、可视化、并行绘制技 术以及复杂几何实体建模技术间的相互关系。 第1 页 国防科学技术大学研究生院学位论文 图1 1 核模拟、可视化建模与绘制技术 1 1 1 国内外研究现状 国内外对面向核模拟的复杂几何实体建模与并行绘制做了大量研究，并针对 现有大型蒙特卡洛粒子输运模拟程序如m c n p 5 1 、e g s i s 6 、k e n o 5 2 1 、m o n k l 5 3 1 等，开发了多种可视化建模与实时交互绘制系统。主要有美国l o sa l a m o s 国家实 验室的m c n p v i s e d 、m o r i t z 、s a b r i n a ，国内西北核技术研究所基于m c n p 4 b 并 行版本开发的m c n p v s ，中国科学院等离子体物理研究所f d s 课题组自主开发的 m c a m ，清华大学工程物理系基于e g s 4 开发了一个包含较强可视化功能的应用 程序系统e g s w i n 。 1 1 1 1u c n p - v i s e d 6 1 美国l o sa l a m o s 国家实验室投入了相当大的精力进行核模拟可视化技术与系 统的研究开发，在m c n p 开发小组中，设有专门的v i s e d ( 用于m c n p 输入文件 的可视化编辑器) 项目组m c n p - v i s e d 是m c n p 程序的重要组成部分， m c n p - v i s e d4 c 2 能够用于创建m c n p 4 c 2 r l 可读的输入文件，开发该可视化编 辑器的主要目的是为了使m c n p 几何实体的可视化构造和调试更加方便，利用该 可视化工具可以快速的构造m c n p 中的复杂几何模型，包括单个几何实体以及由 各种几何实体组合变换合成的复杂模型。m c n p - v l s e d 可视化编辑器主要有以下 功能： 在多个绘图窗口显示m c n p4 c 几何模型； 通过面和单元构造几何实体； 用x s d i r 文件创建各种材料； 在材料库中存储常用材料； 支持将大单元空阅分割成小单元； 第2 页 国防科学技术大学研究生院学位论文 绘制窗口支持交互单元的权值设置等。 对于系统中的模拟粒子，v i s e d 可以在绘制窗口显示源位置和碰撞位置，而 几何结构不同角度的横截面视图可用于构造面或几何实体。面一旦被创建，不论 其是否被用于定义单元，就会在绘制窗口显示，灵活的菜单设置便于快速修改几 何结构和构建相似的面或单元 s l 。 1 1 1 2m o r i t z 与s a b r i n a 【1 0 】 m o r i t z 和s a b r i n a 都是由美国l o sa l a m o s 国家实验室专门成立的研究小组 w r s 开发的m c n p 可视化辅助分析系统网。 m o r i t z 构造的3 d 动态画面支持平移、翻转或者缩放等多种交互手段，支持 显示大部分的m c n p 的输入几何模型。m o r i t z 通过三个角度的2 d 绘制窗口和一 个3 d 绘制窗口来显示几何模型，鉴于现有硬件对o p e n g l 的普遍支持，其中3 d 窗口的图形绘制使用o p e n g l 图形库来加速绘制。在2 d 窗口中用户可以读入 b i l m a p 格式的设计图，然后以该设计图为底板，通过设定坐标刻度和关键点坐标， 构建3 d 几何模型。并且m o f i t z 还部分实现了显示c a d 几何模型以及从c a d 几 何模型到m c n p 几何模型的转换，这样一来有些c a d 数据可以直接用于m c n p 的建模，m o r i t 2 还支持m c n p 程序中粒子轨迹的动态显示。总之m o r i t z 的功能性 更倾向于几何模型的构造。 s a b r i n a 通过光线追踪算法绘制3 d 静态画面，并在此基础上开发了多种显示 效果。光线追踪算法的时间开销主要依赖于模型的复杂程度和计算机屏幕。用户 如果改变单元和材料的视角、缩放标尺、颜色或透明度，则需要重新进行光线追 踪。s a b r i n a 只能针对实体进行一些基于文本的几何模型编辑，支持显示能被m c n p 识别的几何模型。s a b r i n a 在静态显示效果和输入输出文件的兼容性多样性方面有 更加突出的性能。 虽然m o r i t z 和s a b r i n a 在功能方面各具特色，但还分别存在绘制精度不够高、 实时交互手段不够丰富的缺陷。 1 1 1 3f l 2 q p v s 1 3 】 m c n p v s 是由国内西北核技术研究所基于m c n p 4 b 开发的输入卡文件可视 化编辑系统，该系统着眼于简化用户编写输入卡文件的工作，其首要任务是解决 输入卡文件格式规范问题，无需用户记住m c n p 程序的输入卡文件格式。用户只 需在可视化输入界面上根据程序提示输入相应的参数，所有参数输入完成后由程 序自动生成规范的输入卡文件，解决用户手工编写输入卡文件的困扰并提高输入 卡文件的正确性。同时，通过的参数输入过程中对物理对象的体描述和相对位置 描述运用科学可视化方法进行验证，使参数输入错误在参数输入过程中，而不是 在经过多次试算后才能够发现并得到纠正。从而提高了工作效率并节省了计算资 第3 页 国防科学技术大学研究生院学位论文 源。m c n p 程序的输入卡文件所包含的参数被分成七种类型。这七种输入参数类 型如表1 1 所示。 表1 1m c n p 输入卡参数分类 。玲描述物理类型的参数，9 。 2 l 描述物理对象材料的参数， 3 1 。描述物理对象面的参数 4 ，描述物理对象体的对象 5 ) 描述例子源的参数 1 旬模拟数目参数 ” 。 ” 霄描述记录的参数 一。 参数的输入是通过可视化用户界面实现的。总的结构是，七种类型的参数分 别设置在七个属性页上，七个属性页构成一个属性单，引导用户输入参数构造计 算模型。最终由系统自动形成规范的输入卡文件。 该系统还需加强三维可视化验证功能。可视化验证除验证几何形状外，还应 包括源形状、源位置，并显示相应位置坐标或相互问的距离、体密度等参数信息。 1 1 1 4u c a t 一1 1 1 m c a mq l c n pa u t o m a t i cm o d e l i n gs y s t e m ) 是中国科学院等离子体物理研究 所f i ) s 课题组自主开发的m c n p 可视化自动建模软件m c a m 以s p a t i a l 公司的 三维几何与可视化引擎a c i s l l 2 】作为建模及转换核心，并提供可视化操作界面，在 此基础上开发实现了m c a m 五大功能。 1 ) 模型预处理：主要实现对读入的c a d 模型进行修复、简化、缝隙与重叠 校正、空腔填充等，为生成一个完整而正确的m c n p 计算模型做准备； 2 ) 正向转换：主要实现c a d - * m c n p 输入文件的转换。m c a m 可以读取通 用的c a d 格式( s t e p 、s a t 、i g e s ) 的几何模型，并将其转换为完整的m c n p 输 入文件： 3 ) 反向转换：主要实现m c n p - * c a d 模型的转换； 4 ) 模型分析：以可视化方式实现模型属性显示和交互式编辑。m c a m 具备强 大的三维可视化与交互能力，可根据需要以不同的显示方式来观察模型； 5 ) 几何建模：主要实现基本c a d 建模功能。可以绘制二维几何图形和创建 三维几何实体，可以对实体进行交、并、补布尔运算功能，以及缩放、平移、旋 转，镜像、复制、直角坐标阵列、极坐标阵列和分割等操作。 1 1 1 5e g s w i n 5 5 1 e g s 是一个成熟的开放式通用蒙特卡洛模拟程序包，其主程序、记录输出程 第4 页 国防科学技术大学研究生院学位论文 序和几何程序由用户自行编辑，用户可以自由地控制计算流程。e g s 可以模拟光 子电子的耦合输运。 e g s w 蹦是清华大学工程物理系基于e g s 4 开发的一个具有良好用户界面和 比较完善功能的应用程序系统。该系统集成了如下功能：面和区域的图形化输入、 几何区域的处理和探测器的模拟、计算参数的可视化输入以及p e g s 4 的集成、 p r e s t a 算法、并行计算和粒子的径迹显示【踟。这些功能的提供极大地方便了用 户的使用，避免了用户编写程序的麻烦，使用户可以把精力集中于物理问题的研 究。 e g s w 玳系统包括以下三个模块： 1 ) 图形输入模块：该模块能够独立运行，用户只需利用图形化的方法输入实体的 基本信息，程序就能够对这些信息进行处理，获得几何模型中面的方程与区域 的定义，然后再按照e g s w i n 要求的i n i 文件格式输出，这样就能被e g s w 酣 的主程序( e g s ) 使用。该模块不仅可以绘制基本的图形，包括长方体，球和圆 柱，而且可以绘制特殊六面体以及长方体和圆柱阵列，以方便用户绘制探测器 阵列之用。另外，通过集成o p e n g l 绘图环境，模块在用户输入的同时三维显 示相应的图形，用户可自行修改显示的颜色与样式，并且可以自由放大、缩小 以及移动、旋转图形。 2 ) 程序运行模块：该模块是整个系统的核心，包括源、介质、区域和记录的描述， 定义了与图形输入程序的接口，实现了抽象算法和复杂几何的处理。 3 1 粒子径迹模块：利用虚拟现实构造语言( v r m l ) 实现了几何实体集粒子径迹的 显示。 1 1 2 应用需求分析 中子输运过程模拟是核计算的重要组成部分，而蒙特卡洛方法( m o n t ec a r l o m e t h o d ) 5 l 】以其完善的物理建模、复杂几何描述能力、无需离散、收敛速度跟维数 无关等优点一直在中子输运模拟中占有极其重要的地位。 在蒙特卡洛方法粒子输运计算程序中，要求使用一阶( 平面) 、二阶( 球面、 柱面、锥面、双曲面和抛物面) 曲面和一些特定的四阶曲面( 圆环面、椭圆环面) 来定义三维实体，可以使用包围曲面的交、并、补来定义复杂几何体。实践表明， 不借助任何工具而采用手工以文本方式构造复杂问题模型，不仅烦琐而且出错率 高，需要经常进行反复修改，其中以几何模型部分的问题尤其突出，因此采用可 视化手段支持几何建模与交互势在必行1 1 4 j 。 对大规模核物理问题进行模拟时，其对应的几何模型的规模会随着问题复杂 度提高呈大幅增长，实现复杂模型的可视化实时绘制，需要耗费大量的计算和绘 第5 页 国防科学技术大学研究生院学位论文 制资源，采用单机绘制无论是绘制效果还是实时响应都无法达到要求。可视化并 行绘制能够很好地解决这一闽题，如何合理配置已有盼计算资源，通过合理组织 多条绘制流水线进行协同工作实现并行绘制，最大程度上优化可视化效率是目前 该领域亟待解决的课题。 1 2 研究领域与关键技术 1 2 1 三维几何可视化建模技术 几何模型描述中，整个空间被分成不同的区域，几何模型就是关于各个区域 的形状以及材料构成等信息的描述。这种利用解析曲面半空间的布尔运算来定义 几何形体的表达方式是构造实体几何c s g ( c o n s t r u c t i v es o l i dg e o m e t r y ) 力- 式【1 5 】。 c s g 利用某些基本几何体素( 如立方体、圆柱体、圆锥体等) ，通过适当的正则 布尔运算来构造复杂三维实体，可按某些语法进行递归定义，图1 2 是一个由简单 实体通过两级布尔运算构造的实体模型。 o 气汐 、 曰 图1 2 c s g 树 要用计算机构造一个实体，首先必须对实体做出明确定义。根据h - b v o e l c k e r 和a a g r e q u i e h a 提出的基于点集拓扑的理论，三维空间中的物体是空间中点的 集合。组成一个三维实体的点集可以分为内部点和边冥点，而由内部点构成的点 集的闭包就是正则集，这个正则集便可用来表示三维实体【。为此，首先采用曲 面方程配合半空间方法来构造基本体素，然后用基本体素的正则布尔运算来构造 复杂实体。 三维空间的任何曲面都将三维空问划分为两个区域，即曲面内和曲面外，各 做一个半空间。设三维空间任意曲面方程为f ( x , y ，z ) = 0 ，则其外侧半空间和内侧 半空间分别表示为 第6 页 国防科学技术大学研究生院学位论文 h = ( 而办力i f ( 毛弘力 o ) h = ( 五月z ) i f ( 焉只力 设有球面s 和平面p ，其中s 的方程为，+ y 2 + z 2 = 9 ，p 的方程为y = 0 ，则 其半空间e 和马分别表示为 喝= t ( x ，只z ) i ，+ y 2 + z 2 数据并行：通过对数据集的划分，使得计算机以多节点对单块数据进行相 同的并行可视化处理，该方法尤其适合海量数据集的处理。 并行绘制依据图元分布的阶段被分为全图像深度合成( s o r t - f i r s t ) 、前分布拼接 合成( s o a - l a g ) 和中分布拼接合成( s o r t - m i d d l e ) 1 2 2 。三种绘制方式的代表性系统主 要有：全图像深度合成的p i x e l - f l 佣尸】、p a r a l l e l m e d m 、s e p i a t 2 5 1 和前分布拼接 合成的w i r e g l 2 6 、d i s p l a yw a l l 2 7 和中分布拼接合成的i n f i n i t er e a l i t y u s 、p g l 2 9 1 等。 在主流的高性能计算机中，分布主存多处理机如m p p 和c l u s t e r 具有高可扩展、 性价比高的特点 3 0 1 。由于分布主存多处理机配置的高度灵活性，使得不同用户采 用的高性能计算环境在计算能力、i o 能力、图形处理能力以及节点间通讯能力等 方面存在着很大的差异。这就迫切需要其采用的可视化软件支持多种运行模式， 以及灵活配置计算与绘制资源以提高可视化效率。 1 3 论文结构 全文共分六章： 第一章为绪论，主要介绍论文的研究背景与现状，分析基于高性能计算的 核模拟过程中对可视化的需求，阐述需求相关的研究领域并由此引出了解 决问题的关键技术。最后对论文工作与研究成果进行了总结。 第二章对基于半空间理论的复杂几何实体建模技术进行研究。本文针对目 前通用的可视化数据类型提出由隐式方程定义的曲面绘制方法，在此基础 上结合c s g 实体描述与空间单元实体表示，实现了基于c s g 空间构造算 法的实体优化存储与绘制。 第8 页 国防科学技术大学研究生院学位论文 第三章对复杂三维模型的实时交互技术进行研究。针对现有算法的局限 性，提出运用多角度全纵深动态截面方法实现拾取点的自由选择，从面解 决大规模复杂实体集中目标实体的数据抽取与编辑。 第四章对并行绘制技术与可视化软件结构进行研究。为提高数据并行可视 化绘制效率，提出解决s o r t - f h s t 并行绘制负载平衡的屏幕区域细粒度划 分算法，并在此基础上设计了一种支持多种运行模式、功能模块灵活配置 的高可配可视化软件结构。 第五章在实现与综合上述算法的基础上，构建了复杂几何实体可视化建模 与实时交互绘制原型系统y h d v s 。主要介绍了总体结构与用户交互接口 的设计，以及几何可视化建模与实时交互绘制功能的实现。并应用于 m c n p 4 c 的b e n c h m a r k 数据可视化建模与实时交互绘制。 第六章为结束语。总结了论文主要工作，并对今后几何实体建模、实时交 互绘制与并行可视化技术做了展望。 图1 4 为本文的组织结构。 理论研究 图1 4 论文结构 1 4 论文研究成果 应用实现 本文完成的主要工作和取得的主要研究成果包括： 提出一种方程定义的曲面绘制方法，并在此基础上提出一种基于隐式方程 左式正则布尔运算的空间构造优化算法。该优化算法能够有效提高复杂实 体构造效率与模型绘制精度，并且不会造成区域的错误或重复定义。 基于动态截面方法提出一种深入实体内部的数据抽取方法。该方法能够准 确定位实体内部的拾取点，进而实现了实体内部数据的灵活抽取与可视化 第9 页 国防科学技术大学研究生院学位论文 实时交互。 提出一种基于静态划分的屏幕区域分配优化策略，有效解决了s o r t - f i r s t 并行绘制负载平衡问题。并在该策略基础上设计了一种用于提高数据并行 可视化效率的高可配可视化软件结构。 综合上述算法实现了复杂几何实体建模与交互系统原型y i - i d v s ，并成功 应用于处理m c n p 4 c 的b e n c h m a r k 数据。 第1 0 页 国防科学技术大学研究生院学位论文 第二章隐式方程定义的曲面绘制与实体构造优化算法 2 1 概述 三维实体几何模型用于表征现实世界中的实物时，不同于一般意义上的表现 形体的模型。计算机图形学大多采用线框模型或者表面模型，分别用线条与表面 来表示一个形体。由于线框模型给出的不是连续的几何信息，只有离散的边而没 有面与边的关系，因此会对形体的判断产生多义性；而表面模型无法明确定义实 体到底处于表面的哪一侧，并且无法得知其描述的是一个实心体还是一个具有一 定厚度的空壳，因此都不适用于蒙特卡洛方法中的实体构造与描述。三种模型的 应用范围与局限性如表2 1 i 叫】所示。 表2 1 三种模型比较 模型 应用范围局限性 线框模型绘制二、三维线框图不能表示实体、图形会有二义性 表面模型艺术图形、产品造型、星体表不能表示实体 面显示、数控加工 实体模型有限元分析、用集合运算构造 只能产生正则形体、抽象形体的层次 形体较低 实体模型能够定义形体的内部结构形状，完整地描述形体的所有几何信息， 是目前普遍采用的表示方法。在实体模型中，如何通过方程定义的曲面高效地构 造并绘制实体一直是该实体建模的难点。为此本文提出种包含实体正则点集信 息的曲面绘制算法，并对传统的实体构造及表示算法进行优化，提高了实体的构 造效率与表示精度。 2 2 1 数据类型 2 2 算法相关概念 可视化数据的分类方式p l 】有两种：l 、根据数据代表的物理量分类；2 、根据 数据场中的离散点与拓扑结构分类。前一章中分类方式将数据分为标量、矢量和张 量。后一种将数据分为结构化数据、非结构化数据和混合型数据。本文主要针对 结构化的均匀网格数据和非结构化的多边形数据展开研究。 结构化数据【3 2 j 指在逻辑上组织成三位数组的空间离散数据。按元素的不同空 间分布状态又可分为均匀网格结构化数据、矩形网格结构化数据和不规刚网格结 第1 1 页 国防科学技术大学研究生院学位论文 构化数据，如图2 1 所示。 a 均匀网格 b 矩形网格c 不规则网格 图2 1 结构化数据 非结构化数据 3 3 1 的单元结构各自不同，因此无规律可循，无法用三维数组表 示。一般采用点坐标数据结合拓扑结构信息来表示。 多边形数据是非结构化数据中的一种，通过内置最优化的拓扑结构描述模型， 从而提高绘制效率。用于表示多边形数据的拓扑结构有点、点集、线段、折线、 多边形和三角面片，分别对应了0 ，l ，2 维拓扑结构。如图2 2 。 其中三角面片是一种性能非常好的结构，只用n + 2 个点就能表示n 个三角形， 若用多边形结构表示，则需3 n 个点。 2 2 2 可视化流水线 图2 2 多边形数据拓扑结构类型 2 2 2 1 流水线构成 在可视化过程中，需要有一个用于实现将原始数据转换成图元表示的功能模 块，这个模块通常被称为可视化流水线或者可视化网络( v i 文l a l i z a _ 丘o n l 、 3 4 1 。 在这个流水线中主要有数据对象和处理单元两类，前者用于表示数据，后者用于 对数据进行各种操作。 数据对象：数据对象除了可以表示某些信息，也提供创建、访问和删除信息 的方法，包括获取所表示数据的特性。对数据的直接修改一般由处理对象完成。 第1 2 页 国防科学技术大学研究生院学位论文 主要通过不同的内部表示来区分不同的数据对象。同一数据由于需求或效率因素， 可能需要多种数据对象来表示。 处理单元：处理对象处理输入数据产生输出数据，在这过程中可能产生新的 数据，也可能只是将输入数据转换成另一种格式。 2 2 2 2 流水线拓扑 如何将流水线中的单元连接起来，最重要的两个准则为类型匹配和多重性。 类型匹配是指，在流水线中一个单元的输出作为其后续单元的输入，必须能 够被它的后续单元所接受。有两种方法实现类型匹配，即单一化类型和定制类型。 如图2 3 所示。 a 单一化类型 匹 匹 一 b 类型匹配 图2 3 流水线连接方式 单一化类型指的是只存在一种数据类型，各种数据都由这一种数据类型表示， 各种处理对象也只能处理这一类型的数据。但这样灵活性太差，在数据的表示和 访问上造成效率低下。 定制类型系统存在多种数据类型。在该类系统中只有数据类型匹配的两个处 理对象被允许连接，这样就自然需要进行类型检测。可能产生的后果是；数据类 型泛滥，需要很多的处理对象专门从事数据格式的转换，过度频繁的类型转换会 造成计算和内存能力的浪费。 a 多路输入与输出 图2 4 特殊流水线拓扑 b 环路 如图2 4 ，在流水线中，有时会出现多重性和回路等特殊情况。多重性主要针 对以下情况：一个操作需要多个输入或者产生多个输出。有些时候一些操作需要 第1 3 页 国防科学技术大学研究生院学位论文 多个输入数据，可以通过目录来管理和处理对象