（信息与通信工程专业论文）三维数据场的信息处理与体绘制技术.pdf

y 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了 文中特别加以 标注和致谢的地方外， 论文中不包含 其 他人已 经发表和撰写过的 研究 成 果， 也不 包含为获得国防 科学技术大学 或其它 教育机构的学位或证书而使用过的 材料。 与我一同工作的同志对本研究所做的任 何贡献均已 在论文中作了 明 确的说明并 表示谢意. 学 位论文 题目 : 三 维数据场的 信息处 理与 体绘制 技术 学位论文作者签名: 日 期: ; )o d ;年 i月 ， p 日 学位论文版权使用授权书 本人完全了 解国防 科学技术大学有关保留、 使用学位论文的规定。 本人授权 国防 科学技术大学可以 保留并向国家有关部门 或机构送交论文的复印 件和电 子 文 档， 允 许论文 被查阅 和借阅 ; 可以 将学 位论文的 全部或部分内 容编入有关数据 库进行检索，可以 采用影印 、缩印 或扫描等复制手段保存、汇 编学 位论文 ( 保密学位论文在解密后适用本授权书。 ) 学位论文题目:三维数据场的信息处理导体绘制技 学位论文作者签名: 作者指导教师签名: a成 q; .新 日 期: 脚今年 ， j月 心日 日 期 :2 o a 了 年 “ 月1 8 日 国 防 禾 餐 学 技 术 人 学 研 究 , i院 学 位 论 文 图 目 录 图 1 . 1结构化数据场. ， . ， ， 卜 . . . . . . . . . . . . . . 5 图1 . 2 非 结 构 网 格. ， . 、 ， ， . . . . . ， 5 图 1 . 3混合型网格. 、 . . ， . ， . . . . . . . . . . 5 图 1 . 4三维规则数据场中的一 个 体素模型二， . . . . . . . . ， . . . . . . . 6 图 1 . 5 p r o n g 模型中涉及的各个方向 . ， 二， ， ， ， ，. 8 图 1 . 6 p r o n g 光照明模型 . . . . . . . . . . . . . . . . . . . ， . . . . . . . 8 图 2 . 1 两种绘制方法的绘制过程 ，. . . . . . . . . . . . . . . . . . . . . . . . . . . 曰 图3 . 1 离散的三维空间规则数据场中的一个体素 . . . . . ， . . 1 6 图3 . 2体元角点函数值分布的不同情况 ， ， . ， ， . . . . ， ， . 1 8 图 3 . 3体元角点函数值分布状态表. ， 二 二 . . . . . . . . . . . . . . 1 8 图 3 . 4 m c 算法生成等值面的近似表示 . ， ， 二， . . . . . . . . . . . . . . 2 1 图 3 . 5 .=线性插值运算原理图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 222325巧2525罗朋30313333犯别洲盯42招利45拓 图 3 . 6 m c 算法的二义性 . . . . . . . . . ，. . ， 二 ， .， 图3 . 7 等值面顶点连接顺序 图3 . 8立方体的四面体剖分 图 3 . 9四面体中的等值面 3 . 1 0立方体剖分为四面体的不同方式. . ， 3 . 1 1 相邻立方体公共面上的剖分一致性 . . 卜 3 . 1 2恢复相交状况查找表m c 算法 . . . . . . . . 1 3 m t 算 法. t ， . . 1 4引擎等值面图 二， 二， ， 1 5头颅等值面图. . . . . . 1 6原 始 图. . ， 二 ， . 图图图图 1 7 采用邻域平均法处理后的图 像 1 8三维空间角点( m , n , k ) 的邻域空间 n口njnood勺d 图图图图图 3 . 1 9无降噪处理的等值面图二 3 . 2 0进行降噪处理的等值面图二 4 . 1 体绘制过程 . . . . . 4 . 2光线投射算法流程图. . . . . . . . 二 4 . 3体数据通过变换到错切对象空间 图图图图图 图4 . 4功能模块示意图， . . 图4 . 5 切面绘制功能模块. 图 4 . 6光线跟踪以最大亮度值为终止条件流程图二 目 . . 一-，. 州目 . . . 白 ， 一 一-.-， 月 月 口 目 -一. . 卜 . 山七 . ， . . . . 月. . . . . . . . . . . . . . . 一. 电 网 网目 . 网 月 ， . . . . .目 . . . . 自 口 . . ， . ， . 户 ， 月 . . . . . . . . . . . . 叫 . . . . . . ， . . 叫 . . . . ，月， ， . . ， ， ， . 一 ， . . . . 叫. . . . . . . . -， . ， 一 ， . ，. ， 叫. . . . . . . . . . . -. . . ， ， 一一 . 甲 .叫- 镇 n 才 ; f 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 勺j只ojc钊lq自 山d且月q.月上5仄du月 图4 . 7 p h g n g 模型中 涉及的各个方向. . . . . . . . 图4 . 8光线跟踪以设定值为终止条件， . . . . 图4 . 9 引 擎 切面图. . . . . . . . . ， ， 二 ， ， ， . . . 图4 . 1 0设定值快速光线投射. . . . . . . . ， . . 图4 . 1 1 设定值高质量光线投射. . ， . . . . . . . . . 图4 . 1 2 设定最大亮度 值 . . . . . . . . . . . . . . . . . . ， . ， 233l 表目录 表 3 . 1 相交状况查找表 ， . . ， . . . . . . . . . . . . . . . . . . . . . . ， ， . . 表 3 . 2重建头颅等值面模型的三角面片数量及抽取时间表 第川灭 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 摘要 本论文详细论述了作者攻读硕士学位期间在三维数据场的信息处理与体绘 制技术方面从事的研究工作，包括基础算法研究和应用系统开发。 随着科学技术的迅猛发展， 待处理的数据量越来越大， 每大来自卫星、 航天 器、 地质设备、 医疗扫描仪等的数据与 1 俱增， 远远超出了人脑分析解释这些数 据的能力， 使得科学计算数据的可视化和计算过程的交互干预和引导日益成为迫 切需要解决的问题。 为了将科学计算过程中及计算结果的数据转换为图形及图象 在屏幕卜 显示出来并进行交互处理， 有着越来越多的科研工作者投入了对三维数 据场的信息处理工作中。 三维数据场是当前可视化研究的重点， 也是实践中最常遇到的。 体可视化算 法可分为表面体绘制和直接体绘制 ( 简称体绘制) 。 m a r c h i n g c u b e s算法是基于 规则体数据抽取等值面的经典算法。 针对 m c 算法存在的二义性问题进行了改进。 m a r c h i n g t e t r a h e d r a 算法是其改进算法。本 文对两种算法进行了研究， 实现了这两种算法对三维体模型抽取等值面构建表面 模型。 在体绘制算法的研究中， 作者主要研究了体绘制算法中的光线投射算法。 采 用包围盒技术对其实现加速绘制。 并用ms c + 十 开发了一个基于光线投射算法的 体可视化软件。 关 键词 : 体 可 视 化， 数 据 场， 面 绘制， 体 绘 制， m a r c h in g c u b e s 算 法， m a r c h in g t e t r a h e d r a 算法， 光线投射算法 第 1 贝 国 防 科 学 技 术 人 学 研 究 生 院 学 位 论 文 a b s t r a c t t h i s t h e s i s d e s c r i b e s t h e a u t h o r s w o r k o n 3 d v o l u m e t r i c d a t a f i e l d s p r o c e s s a n d v o l u m e r e n d e r i n g , i n c l u d i n g b a s i c a l g o r i t h m s a n d s o ft w a r e s y s t e m s a s s c i e n c e a n d t e c h n o l o g y d e v e l o p q u i c k l y , s t u d y i n g a n d a n a l y s i n g . t h e d a t a c o m i n g f r o m g e o g r a p h i c e q u i p m e n t s , a n d me d i c a l s c a n n e r s , m o r e a n d m o r e d a t a a r e a c q u i r e d f o r s u p e r - c o m p u t e r s , s a t e l l i t e s , a i r c r a f t s , a r e i n c r e a s e d a l l t h e d a y s , a n d f a r b e y o n d t h e a n a l y t i c a l a b i l i t y o f h u m a n . t h e v i s u a l i z a t i o n o f 3 d d a t a f i e l d a s w e l l a s i n t e r a c t i v e p r o c e s s i n g o f s u c h d a t a b e c o m e s m o r e a n d m o r e u r g e n t . i n o r d e r t o m o r e e f f i c i e n t m e t h o d t o d i s p l a y t h e g r a p h i c s c o n v e rt e d s c r e e n , m o r e a n d m o r e s c i e n t i f i c r e s e a r c h e r s j o i n t h e r e s e a r c h 3 d d a t a f i e l d . f r o m c o m p u t e d d a t a o n w o r k o n t h e p r o c e s s o f t h e r e n d e r i n g o f 3 d v o l u m e t r i c d a t a f i e l d s i s a h o t r e s e a r c h a r e a i n s c i e n t i f i c v i s u a li z a t i o n , a n d i t i s a l s o a k e y t e c h n o l o g y i n p r a c t i c a l a p p l i c a t i o n s . t h e v o l u m e v i s u a l i z a t i o n a l g o r i t h m s c a n b e d i v i d e d i n t o s u r f a c e r e n d e r i n g a n d d i r e c t v o l u m e r e n d e r i n g ( v o l u m e r e n d e r i n g f o r s h o rt ) . m a r c h i n g c u b e s ( mc ) a l g o r it h m i s a c l a s s ic a l a l g o r i t h m b a s e d o n e x t r a c t i n g i s o - s u r f a c e f r o m r e g u l a r v o l u m e d a t a . a n d a n i m p r o v e m e n t h a s b e e n m a d e o n a n a m b i g u o u s p r o b l e m i n mc a l g o r i t h m . ma r c h i n g t e t r a h e d r a ( mt ) a l g o r it h m i s a n i m p r o v e d o n e f r o m mc a l g o r i t h m . t h i s t h e s i s s t u d i e s t h e s e t w o a l g o r i t h m s i n d e t a i l , w i t h w h i c h t h e 3 d r e g u l a r v o l u m e d a t a c a n b e e x t r a c t e d t o c o n s t r u c t t h e 3 d s u r f a c e mo d e l s . i n t h e r e s e a r c h o f v o l u m e r e n d e r i n g a l g o r i t h m , t h e a u t h o r m a i n l y s t u d i e d r a y c a s t i n g a l g o r it h m . a n e f f i c i e n t v o l u m e r e n d e r i n g a l g o r it h m s i s d e v e l o p e d b y u s i n g b o u n d i n g - b o x t e c h n o l o g y . a v o l u m e v i s u a l i z a t i o n s y s t e m , w h i c h i s b a s e d o n t h e d e v e l o p e d a l g o r it h m , i s d e s i g n e d u s i n g ms c + 十w i t h s o m e p r i m a r y r e s u lt p r e s e n t e d i n t h i s t h e s i s . k e y wo r d s : v o l u m e v i s u a l i z a t i o n , d a t a f i e l d s , s u r f a c e r e n d e r i n g , v o l u m e r e n d e r i n g , ma r c h in g c u b e s a l g o r i t h m , ma r c h i n g t e t r a h e d r a a l g o r it h m , r a y c a s i n g a l g o r i t h m 第 2 i i 国 防 科 学 技 术 人 学 研 究 生 院 学 位 论 文 第一章 绪论 1 . 1 背景介绍 随着科学技术的迅猛发展， 待处理的数掀量越来越大， 每天来自1 . 星、 航人 器、 地质设备、医疗扫描仪等的数据与日 俱增， 远远超出了 人脑分析解释这些数 据的能力， 使得科学计算数据的可视化和计算过程的交互干预和引导日 益成为迫 切需要解决的问题。1 9 8 7 年2 月，美国国家科学基金会 ( n s f)在华盛顿召开 了有关科学计算可视化的首次会议， 会议认为， 将图形学与成象技术应用j 飞 计算 科学将产生一个全新的技术领域 科学计算可视化， 简称v i s c ( v i s u a l i z a t i o n i n s c i e n t i f i c c o m p u t i n g ) 或s v(s c ie n t i f i c v i s u a l i z a t i o n ) 。 并指出“ 科学家们不 仅需要分析由 计算机得出的计算数据，而且需要了解在计算过程中数据的变化， 而这些都需要借助于计算机图形学及图象处理技术” 。从 1 9 9 0年起，美国 i e e l 计算机学会计算机图形学技术委员 会开始举办每年一度的可视化国际学术会议。 同时 ， 可视化技术已 成为.s i g g r a 洲 e u r o g r a p h i c s 等国际图形学权威会议的热门 课题。另外，自 从 1 9 9 0年第一本可视化专著 v i s u a l i z a t i o n i n s c i e n t i f i c c o m p u t i n g问 世以 来， 己 经出 现了大量有关可视化技术的论著。 其中， 国际权威图 形学期刊i e e e c o m p u t e 厂g r a p h i c s x a p p l i c a t i o n 悔年出版一期可视化专刊。 所有这些表明， 国内外的专家学者在可视化领域已经取得了巨大的进展， 科学计 算可视化作为一门学科己经日趋成熟。 1 . 1 . 1 科学计算可视化的含义 科学计算可视化是指运用计算机图形学和图 象处理技术， 将科学计算过程中 及计算结果的数据转换为图形及图象在屏幕上显 示出 来并进行交互处理的理论、 方法和技术。其研究领域涉及到多个学科，它与计算机图形学、数字图像处理、 计算机视觉、计算机辅助几何设 计等学科紧密相连，并且 有着极强的应用背景。 来自 各个研究领域的大量的数据从不同的侧面揭示了物质和各种现象在一定条 件下的物理属性。可视化技术正是要深入到这些领域中去， 挖掘数据之问的斗 1 1 关 性及规律。 因此， 可视化技术不仅仅在于如何用图形表示数据场， 而和数据场的 物理背景密切相关。这里引述v i s c 报告u .给出的定义: “ 可视化是一 种计算方法。 它将符号转换成几何， 使研究者能观察他们的模 拟与计算。 它将不可见的变成可见的， 丰富了科学发现的过程， 给予人们深刻与 意想不到的洞察力。在很多领域使科学家的研究方式发生根本变化。 ” 第 3页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 “ 可视化包含图象理解与图象综合， 亦即它解释输入计算机的图象数据， 同 时又是山复杂多维数据集产生图象的工具， 它研究人与计算机观察、 利用及通讯 可视信息采用的机制。 ” 科学计算可视化的应用领域也十分广泛， 几乎涉及自 然科学及工程技术的一 切领域。主要集中在医学、地质勘探、气象学、分子模型构造、计算流体力学、 有限元分析、空间探测、天体物理和数学等领域。 川 . 2 国内外科学计算可视化的研究现状 近几年来， 在美国、 德国、日本等发达国家的著名大学、国家实验室及大公 司中， 科学计算可视化的研究工作及应用试验十分活跃， 其技术水平正在从后处 理向实时跟踪和交互控制发展，并且已经将超级计算机、 光纤高速网、 高性能图 形工作站及虚拟现实四者结合起来。其主要的研究成果有 . 可见人体 . 人类胚胎的可视化 . 分布式虚拟风洞 .大气及流体可视化软件 . 燃烧过程动态模型的可视化 目前， 我们国家在可视化方面也有了长足的进展。 例如数字化虚拟人的研究 等。 近儿年， 相应的可视化软、 硬件产品市场急剧扩大。 在软件方面，已有了许 多 实 用的 数据 场可 视 化系统， 有些已 经商品 化， 如 a v s , i b m d a t a - e x p lo r e r , i r i s _ e x p l o r e r , f a s 卫p i o t 3 d等。 山于可视化涉及的范围太广泛， 其应用和研究的发展太迅速， 本文不可能进 行全面的论述。 对此， 本章只简略地介绍可视化的基本原理和概念及其发展现状， 为后面各章论述本文的工作提供一个基础。 妇. 2 三维空间数据场的数据类型 科学计算可视化的数据是对有限空间的一组离散采样， 每个采样点上的采样 值可以是一种或多种， 代表在该点上的一个或多个物理)离性值。 体数据主要有两 种来源: 一种是科学计算得到的三维数据场， 如有限元分析或数值模拟得到的体 数据;另一种是通过实验设备获得的数据，如通过c t扫描或核磁共振得到的反 映人体器官的医学数据集。 实现三维空间数据场可视化的算法与数据类型有很大 的关系。 这里所谓的数据类型有两层含义， 一是数据本身的类型， 二是数据空问 分布及组织的类型。 数据本身的类型可根据数据的物理特征分为标量、 矢量和张 第 4% 国防科学技术人学研究生院学位论文 “可视化包含图象理解与图象综合，亦即它解释输入计算机的图象数捌，可 时又是山复杂多维数据集产生图象的工具，它研究人与计算机观察、利用及通讯 可视信息采用的机制。” 科学计算可视化的应用领域也十分广泛，几乎涉及自然科学及工程技术的一 切领域。主要集中在医学、地质勘探、气象学、分子模型构造、计算流体j 学、 有限元分析、空间探测、天体物理和数学等领域。 1 1 2 国内外科学计算可视化的研究现状 近几年来，在美国、德国、r 本等发达团家的著名大学、目家实验聿及人公 司中，科学计算可视化的研究工作及应用试验十分活跃，其技术水平i i i 在从后处 理向实时跟踪和交互控制发展，并且已经将超级计算机、光纤高速网、高性能图 形工作站及虚拟现实四者结合起来。其主要的研究成果有 可见人体 人类胚胎的可视化 分布式虚拟风洞 大气及流体可视化软件 燃烧过程动念模型的可视化 目前，我们国家在可视化方面也有了长足的进展。例如数字化虚拟人的研究 等。 近j l 年，相应的可视化软、硬件产品市场急剧扩大。在软件方面，已有了许 多实用的数据场可视化系统，有些已经商品化，如a v s ，i b md a t a e x p l o r e r ， i r i s e x p l o r e r , f a s t , p l o t 3 d 等。 由于可视化涉及的范围太广泛，其应用和研究的发展太迅速，本文不可能进 行全面的论述。对此，本章只简略地介绍可视化的基本原理和概念及其发展现状， 为后面各章论述本文的工作提供一个基础。- 1 2 三维空问数据场的数据类型 科学计算可视化的数据是对有限空问的一组离散采样，每个采样点上的采样 值可以是一种或多种，代表在该点上的一个或多个物理腻性值。体数掘 要钉两 种来源：一种是科学计算得到的三维数据场，如有限元分析或数值模拟得到的1 小 数据；另一种是通过实验设备获得的数据，如通过c t 扫描或核磁兆振得到的反 映人体器官的医学数据集。实现三维空问数据场可视化的算法与数据类型有很人 的关系。这里所谓的数据类型有两层含义，一是数据本身的类型，二是数据宁问 分布及组织的类型。数据本身的类型可根据数据的物理特征分为标量、矢量和张 蚺4 负 国防科学技术人学研究生院学位沧文 量；数掘的空削关系是根据数据场巾样点分布的空i + m j b 何特征，将数掘场分为结 构化数据场( 图1 1 ) 与非结构化数据场( 图1 2 ) 以及结构化与非结构化混合型 数据场( 图1 3 ) ，其中，结构化数据场又可根据数据场中各元素的不问的物删分 布进一步分成均匀网格结构化数据场、规则网格结构化数据场、矩形网格结构化 数据场、不规则网格结构化数据场。 1 1 ( a ) 均匀网格 i i ( c ) 矩形网格 图121 f 结构网格 l ( b 1 规则网格 1 1 ( d ) 不规则网格 图1 1 结构化数据场 1 3 三维空间规则数据场中体素( v o x e l ) 模型 图1 3 混台型网格 所谓“规则数据场”是指由均匀网格或规则网格组成的结构化数据，朗征i 维空间的某一个区域内进行采样，若采样点在l y ，z 三个方向上的分布是均匀 的，采样问距分别为缸，缈，位，则体数据可以用二维数字矩阵来表示，| 】 第5 页 国防科学技术人学研究生院学位论文 f ( m ，月，k ) 。每八个相邻的采样点所定义的立方体区域就构成了一个体素，而这 八个采样点称为该体素的角点，它们的坐标分别为：( m ，氓k ) ( m + l ，门，k ) ，( m ，胛+ 1 ，k ) ，( m + l ， + 1 ，k ) ，( 棚， ，k + 1 ) r ( ， + l ，九，k + 1 ) ( m ，m + l ，k + 1 ) 和( m + 1 ，月+ 1 ，k + 1 ) ，如图1 4 n 示。对于体素内的任一点，其值j 、i 能从体素的八个角点的采样值来估算。常用的体素模型有方向无关的三线性捕值 模型和方向有关的三线性插值模型两种。 ( m ，门+ 1 ，k + 1 ) ( ，竹+ 1 ， + 1 ，k + 1 1 一 一 。 。7 1 4 光照模型 ( 朋， 黔 一 ( m + 1 ，h ，k + 1 ) l ( 脚+ 1 ，仃十l ，忌) ( m + 1 ，盯，k ) 图14 三维规则数据场中的一个体索模掣 为了计算屏幕象素上相应景物可见点的颜色，需建立一个能计算物体表i 酊在 空间给定方向上光亮度的光照模型。本文使用p h o n g 光照模型，它是出p h o n g 在1 9 7 3 年提出的一个用来计算表面镜面反射光亮度的经验模型( 式1 1 ) 。 ，= 1 1 w ( a ) c o s “e ( 1 1 ) 其中w ( a 1 为景物表面的镜面反射率它是入射角a 与入射光波长的函数。经文 际应用中，w ( a ) 往往取为常数k 。，通常0 k ，茎1 。”为镜面商光指数，它破用 来模拟镜面反射光在空问的汇聚程度。目为视线与镜面反射光线之间的央角。，。 第6 负 国防科学技术人学研究生院1 学位论文 为表面投向视线方向的镜面反射光亮度。 在现实生活巾，反射光一般是三个分量的组合：j ；| = 境反射、漫反射和镜面反 射。计算环境反射时假定入射光均匀地从周围环境入射至景物表面并等量地向各 个方向反射出去；而漫反射分量和镜面反射分量则表示特定光源照射在景物表面 上产生的反射光。漫反射分量的计算可以使用朗伯余弦定律：对于一个漫反射体， 表面的反射光亮度和光线的入射角( 入射光线和表面法向量的央角) 的余弦成币 比。 ，= ，。dc o s o ( 12 ) 其中，为表面反射光的光亮度；。为光源垂直入射时反射光的光亮度；口为 光源入射角。 镜面反射光为朝一定方向的反射光，它遵循光的反射定律：反射光和入射光 对称地位于表面法向的两侧。对于纯镜面，入射至表面面元上的光严格地遵循光 的反射定律单向地反射出去；对于一般光滑表面，由于表面实际上是由许多敬向 不同的微小平面组成，其镜面反射光分布于表面镜面反射方向的周围。因此，实 用中常采用余弦函数的幂次来模拟一般光滑表面的镜面反射光的空间分布： ，= ，。c o s ”臼 ( 1 3 ) 其中，为观察者接收到的镜面反射光的光亮度；气为镜面反射方向上的镜面反 射光亮度：锄镜面反射方向和视线方向的央角：拧为镜面反射光的会聚指数。 如前所述，表面反射光可认为是环境反射、漫反射、镜面反射三个分量的组 合。对于一特定的物体表面，这三种分量所占的比例有一定的值。令如，白和 缸分别表示环境反射、漫反射和镜面反射分量的比例系数，则p h o n g 光照模型可 表示如下： ，= 女。j 胂+ 球d f 州c o s o + 囊，j 芦c o s “0 ) ( 1 4 ) 在实际计算时，我们仅需求出景物表面各采样点处的单位法向量j v 、坼位 入射光线方向矢量厶、单位视线矢量y 和，的单位镜面反射矢量r ，则d | c o s o r ，= ( ，) 、c o s b l = ( 弘r ，) 和式( i 4 ) 就可计算每一可见点处的光亮度。 在实际使用时，由于( 矿r ，) 的计算不方便，常用( h ，) 末代替它，其中h ， 为将入射光反射到观察者方向的理想镜面的法向量，显然，即为生毒旦的单付 z 向量( 如图1 5 所示) 。这样，p h o n g 模型成为： 第7 负 国防科学技术入学础f 究生院学位论文 ，= 女。，p 。+ 衅。，口，( 工，) + 、，( h ) ” ( 1 5 ) r 图15p h o n g 模型中涉及的各个方向 图1 6 为p h o n g 照明模型的示意图。 图1 6p h o n g 光照明模型 p h o n g 光照明模型是真实感图形学中提出的第个有影响的光照明模型，生 成图象的真实度已经达到可以接受的程度。因此本论文采用p h o n g 光照模型进行 图象真实感绘制。 1 5 本论文的主要工作 在硕士研究生期间，作者主要从事三维数据场的信息处理与体绘制技术的研 究，研究了三维体数据可视化算法，包括面绘制与体绘制两个方面。扯此划川i ： 要完成了对m c 算法的改进，以及设计并实现了基于光线投射算法的快这体可视 第8 贝 国防科学技术人学研究生院学位论文 化软件。 论文主要工作包括面绘制与体绘制基础算法的研究。并在此基础上研究了混 合绘制算法。论文各章的内容简述如下。 第二章主要论述了三维空间数据场的可视化方法。对其中的面绘制算法和体 绘制算法进行了探讨。并剥两种算法进行了比较，分析了各自的优缺点。同时还 对混合绘制算法进行了简单的论述。 第三章主要论述了面绘制的经典算法m a r c h i n gc u b e s 算法，对m c 算法的 原理、过程及步骤进行了详细论述。分析了m c 算法中连接方式产生二义性豹原 因及消除二义性的方法，提出了恢复相交状况查找表及采用m a r c h i n gt e t r a h e d r a 避免2 2 义性问题的新方法，在此基础上讨论了m t 算法的剖分一致性问题。实现 了改进的m c 算法以及m t 算法，并对两种算法进行了比较。 第四章主要论述了直接体绘制算法。对光线投射算法的原理、过程及步骤进 行了详细论述。介绍了基于错切一变形技术的体绘制算法及体元投射法，并剥直 接体绘制技术的发展进行了展望。本章还介绍了基于光线投射算法的快速体可视 化软件的设计方案、软件实现及实验结果。 第五章是全文的总结。 第9 页 国 防 科 学 技 术 大学 研 究 生 院学 位 论文 第二章 三维空间数据场可视化方法 2 . 1 三维空间数据可视化流程 三维空间数据场可视化的基本流程一般可分为四个步骤: 过滤， 映射， 绘制 和反馈。 ( 1 ) 过滤: 选取感兴趣的数据。即从原始数据集中提取感兴趣的数据，并经过预 处理 如滤去数据中的噪声等) ， 将它们转变成更能反映实际情况的数据。 ( 2 ) 映射:即将经过处理的数据转换为可供绘制的几何图素和属性。 ( 3 ) 绘制:几何图素转变为图像。即根据数据的几何图素的表达，对几何图素赋 予视觉特征，如确定图像的合成、颜色、透明度、纹理、阴影等各方面的性质， 并进行绘制操作。 ( 4 ) 反馈:显示图像。 这是可视化过程的最后一步。由研究人员观察图像进行分 析和研究。并由 此进行进一步的可视化操作。 可视化的流程中的四个步骤是一个周而复始的循环迭代过程。 因为研究人员 事先并不可能知道原始数据集的哪些部分对分析最重要， 而且也不可能预先确定 数据集到几何图素的最佳映射关系，甚至哪些光线属性绘制出的图象效果最佳。 这些都得靠实践的摸索，因而整个分析过程是一个反复求精的过程。 2 . 2 三 维 空间 数 据 场 可 视 化 算 法2 , 14 , 18 , 20 1 对于三维数据场，根据图象表达的方式，其成象方法可分为面绘制法 ( s u r f a c e r e n d e r i n g ) 和直接体绘制法( d i r e c t v o l u m e r e n d e r i n g ) . 2 . 2 . 1 面绘制法 基于面的体绘制算法3 , 1 . 1 ( 有时也称为形状提取算法或同 值表面算法) 一n 先 由 三维空间数据场构造出中间几何图元 ( 如曲面、平面等) ，然后再由传统的计 算机图形学技术实现画面绘制。 最常见的中间几何图元就是平面片。 可以 将中问 几何图元的生成过程看作是上述可视化流程中的第三步一一映射。 其中经典的算 法 是 m a r c h i n g c u b e s 算 法 “ ， ， 它是由 l o r e n s e n 和 c l i n e 在1 9 8 7 年 提出 来的。 在这 一方法中， 假定原始数据场是离散的三维空间规则数据场， 且每个体元彼此科 连 第1 0 页 国 防科 学 技 术 大学 研 究 生 院 学 位 论 文 二二二二二二二二二二二二二二二二二二二二二二二二二二二二二二二二二二二二泛竺竺竺竺竺竺竺竺竺竺竺竺竺竺竺一竺巴竺 竺 竺 竺 竺 竺竺 ， 且相互独立， 则每个体元在拓扑结构上相当 于一立方 体。 由于 此方法是对体元逐 个进行处理， 依次找出其中 包含的 等值面，因 此被称为 m a r c h i n g c u b e s 算法， 简 称m c 算法。 面 绘制法将感兴趣的部分以 等值面的方式较清晰的抽取出 来后， 便于利用真 实感技术生成高质量的图象， 使研究人员可以 方 便地进行观察和分析， 而月n j 一 以 利用现有的图形硬件加速绘制速度。 但是这种方法构造出的图形仅是将原始数州 中的部分属性映射成平面或曲面，因而不能反映整个原始数据场的全貌和细节。 使研究人员难以把握数据场的全局状? n , a 2 . 2 . 2 直接体绘制 直接体绘制5 ， 该算法是直接由 三维数据场产生屏幕上的二维图象， 并不构 造中间几何图元，而是采用给数据场中的 体元赋予一定的色彩和透明度， 由光 线 穿越半透明 物质时能量集聚的光学原理， 进行色彩合成的成象操作， 进而合成为 具有三维效果的图象。 直接体绘制算法按处理数据域的不同可分为空间域力 一 法和 变换域方法。 前者是直接对原始的可见数据 ( 体数据) 进行处理显示: 后者是将 体数据变换到变换域，然后再进行处理显示。 皇 l立 迭。 其典 型算法是光线 投射法。 其基本原 理是根据视觉成 像原理， 构造出理想化的物理视觉模型， 即每个体素都看成能够透射、 发射、 和反射光线 的 粒子， 然后根据光照模型或明 暗模型， 依据体素的介质特性得到创门 的颜色( 灰 度图象为亮度) 和不透明度， 并沿某个方向从屏幕上 的象素发出光线穿越数据场， 每条光线穿越数据场时进行采样和色彩累积， 得到相关象素的色彩， 直至在成象 平面上形成具有半透明效果的可视图。 一般地说， 该方法可以方便地利用光照计 算生成细腻的可视图， 但速度较慢。 变 夔 丛友 丛a z 11 。 与 空间 域 方 法不同 ， 变 换 域 方 法不 是 在空间 域 进行 操 作， 而是利用变换， 将三维的数据场空间转化为对应变换域空间。 变换域方法可分为 频域体绘制方法和基于小波的体绘制法。频域体绘制法是先利用 f o u r ie r 变换， 将三维的数据场空间转化为三维的频域空间， 然后由频域的切片原理可知， 过频 域中 心且垂直某个方向的二维切片经过反f o u r i e : 变换所得的图 象， 就是沿该 方 向进行光线投射方法或投影成象方法所产生的可视图。 虽然该方法产生频域空in l 时开销较大， 但频域空间与视点无关， 可以反复使用， 而由频域空间的二0切片 获得三维数据场空间的可视图， 则更体现了该方法的优越性。 但该方法所生成的 可视图不能反映空间域中色彩合成时的遮挡关系， 使观察者难以判断物质分布的 前 后 关 系。 基于小 波的 体 绘 制 法主 要由 小 波 光线 投 射法 ( r a y t r a c in g in w a v e le t s p a c e ) 和小 波足迹法 ( w a v e l e t b a s e s p l a t t i n g ) 。 前者的 基本思 想是将体数据的三 第u刀 之 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 二 一= 一一幸 = 一二 二 二 二 二 二 二 二 二 二 二 二 二 二 二 二 =竺 竺 竺 毕导竺竺竺 竺 竺 竺 竺 竺 竺 竺 竺 竺 竺 竺 竺 竺 竺 毕 李二 二 二 二 二 二二二 维离散小波变换的近似结果直接代入到体绘制方程中求解， 本质仁 看是光线投射 法在小波域的实现; 后者的基本思想是利用傅立叶频域绘制先得到梅个小波的尺 度函数的足迹，再通过小波系数加权得到投影图象。 直接体绘制是近年来得以迅速发展的一种体可视化方法。 这种算法能产/ i 三 维数据场的整体图象， 包括每一个细节以及揭示数据场中的多种分类物质间的相 互关系，并具有图象质量高、便于并行处理等优点。其主要问题是 . 由于缺乏棱角明显的中fu 几何图元的表达，其可视图通常比较模糊。常 常要从不同角度观察多幅可视图，刁 一 能对数据场有较好的认识。 . 直接体绘制所需计算量很大，且难于利用传统的图形硬件实现绘制，因 而计算时间较长，不利于交互实时处理。 2 . 3 体绘制与面绘制的比较 面绘制的主要思想是首先提取感兴趣物体的表面信息， 把体数据转换为山一 系列多边形表面片拟合的等值面， 然后再根据光照、 明暗模型进行消隐和渲染得 到三维的显示图象。 与面绘制相比较， 体绘制的一个特点就在于放弃了传统图形 学中体山面构造的这一约束， 采用体绘制光照模型直接从三维数据场中绘制出各 类物理量的分布情况。 等值面儿何面表示方法是研究者们为了适应图形显示， 人 为地提出的一种数据场表示形式。 体绘制的根本点就在于放弃了这一做法， 直接 研究光线穿过三维体数据场时的变化， 得到最终的绘制结果。 由于体绘制的这种 直接性， 非常符合人的视见过程， 因此保留了大量的细节信息， 从而大大地提高 了图象的保真度， 这时图象质量己 不再依赖面的如何分割问 题， 而是集中在光照 模型、 绘制过程上。 因而从结果图象的质量上讲， 体绘制要优于面绘制。 但从交 互性能和算法效率上讲， 至少在目 前的硬件平台上， 面绘制还是要优于体绘制的。 这是因为面绘制采用的是传统图形学的绘制方法， 现有的交互算法、 图形硬件和 图形加速系统可以充分发挥作用， 在一些对细节要求不多， 交互要求较高的环境 中，面绘制仍发挥着较大的作用。两种绘制方法的绘制过程如图2 . 1 所示。 第1 2 页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 3 6 / 2 6 莱禅设备、汁住镇型m od 几何透型工具软件 图 2 . 1两种绘制方法的绘制过程 2 . 4混合绘制 在三维数据场可视化的应用中， 有时需要将几何形体与数据场在一 幅图中同 时混合显示。 采用的方法一般是将这两种数据用同一种数据表达形式描述， 然后 再进行绘制。 方法一: 用几何面拟合数据场的数据， 或是通过三维的多边形转化， . 使几何 面由数据样点来表达。 方 法 二 : 直 接 显 示 这 两 类 数 据 7 1其 体 实 玩 方 法 有 : . 先将几何体与体数据场分别成象，再将二者进行图象合成。几何体可采用真 实感技术绘制， 而体数据场用体绘制技术成象。 但这种混合成象方法要求几何形 体与数据场不相交。 . 将几 何 形体 与 数据 场 直接 混合 成 象， 如m a r c l e v o y lyl在1 9 9 0 年提出 的 混 杂 光线跟踪法。 该方法首先为几何形体的面计算出色彩并赋予一定的透明度， 然后 运用体绘制的光线跟踪法进行直接的混合成象。 . 将数据场和几何面分别用光线投射方法和光线跟踪方法成象， 建立链表分别 保留数据场和几何面中每个象素的特征值， 特别是深度信息。 然后， 将这两个链 表合并进行混合成象。但该方法要为光线投射时的每个采样点保留一个链结点， 空间开销大; 几何面与采样点进行深度比较后在进行混合成象时， 在交错位置处 容易引 起误差， 该方法的改进是提高每条光线上的 采样密度， 但这样空间开销更 大，并且没有从根本上解决几何面对数据场剖分的问题。 1 9 9 6 年， j a y - j e o n g k im 1 等 提出 用二 叉 树组 织 数 据 场以 减 少空 rh 1 要 求， j f- m 于层次结构的加速处理， 用光线跟踪方法进行休绘制与等值面的混合显示。 但其 色彩的 合成计算主要是基于m a r c l e v o y 在1 9 9 0 年提出的方法。 第1 3 灭 国 防 科 学 技 术 人 学 研 究 生 院 学 位 论 文 在实际应用中， 对混合绘制这项技术的重视程度逐步提高。 人们在对三维数 据场进行绘制时，更多地希望可以实现交互， 加入人工干预。 例如，在虚拟手术 中，可以加入一把虚拟手术刀，这就需要采用混合绘