（计算机软件与理论专业论文）mc算法研究及在三维流体可视化模拟中的应用.pdf

m c 算法研究及在三维流体可视化模拟中的应用中文摘要 m c 算法研究及在三维流体可视化模拟中的应用 中文摘要 移动立方体( m a r c h i n gc u b e s ，m c ) 算法是应用最广泛的等值面方法，其研究 主要集中在算法的改进和算法在不同领域的应用上。m c 算法在三维流体可视化中的 应用己成为计算机图形学中一个重要研究热点。本文主要研究了m c 算法及其在三维 流体模拟中的应用，在分析m c 算法的基础上，对m c 算法进行改进，以使其更好地 应用到三维流体可视化模拟中，达到基本实时绘制的效果。本文的主要内容如下： 1 、总结了m c 算法和流体模拟的研究现状。研究了m c 算法的原理及实现方法， 并分析了其可能存在的二义性问题及其解决方法；讨论了流体模拟的主要方法。 2 、对m c 算法进行改进，提出分块逐层遍历的移动五面体( m a r c h i n gp e n t a h e d r a ， m p ) 算法。本文提出了m p 算法来绘制等值面，同时也分析了m p 算法可能存在的 二义性问题及其解决方法；为提高算法的时间效率，提出了将空间体数据场分为若干 块，然后对每一块实现由外层向内层的逐层遍历的方法。该改进算法提高了m c 算法 的时间效率和等值面精度。 3 、对双气泡聚并过程的动力学规律进行了分析与研究，并对其进行了三维可视化 模拟。首先根据动力学规律建立了双气泡聚并的动态特征数值模型，并对该模型进行 数值求解与分析。采用m a t l a b 进行了数值模拟，另基于m c 算法，用l e v e ls e t 方法 对两气泡聚并的演化过程进行了三维可视化模拟，其结果与m a n g a 等的实验结果吻合 的很好，与李向阳等的数值模拟结果亦吻合的很好。 4 、提出了一个支持分块逐层遍历算法、以六面体为基础的五面体、四面体逐级 细分的网格划分流程与方法，形成了一个完整网格划分体系。并在此体系上对m c 算 法、移动四面体( m a r c h i n gt e t r a h e d r a ，m t ) 算法和分块逐层遍历的m p 算法进行性 能比较和实验分析。 关键词：面绘制，移动立方体，流体模拟，n a v i e r - s t o k e s 方程 作 者：叶再春 指导老师：孙涌 a b s u a c t r e s e a r c ho fm ca l g o r i t h ma n di t sa p p l i c a t i o ni n3 dv i s u a ls i m u l a t i o no ff l u i d s r e s e a r c ho fm c a l g o r i t h ma n d i t sa p p l i c a t i o ni n 3 d v i s u a ls i m u l a t i o no ff l u i d s a b s t r a c t m a r c h i n gc u b e s ( m e ) a l g o r i t h mi st h em o s tw i d e l yu s e di s o s u r f a c em e t h o d ，t h e r e s e a r c h e sa r em a i n l yf o c u s e do ni t si m p r o v e m e n ta n di t sa p p l i c a t i o ni nd i f f e r e n tf i e l d s i t h a sb e c o m ea l li m p o r t a n th o t s p o tr e s e a r c ht oa p p l yt h em c a l g o r i t h mi nt h r e e d i m e n s i o n a l f l u i dv i s u a l i z a t i o ni nc o m p u t e rg r a p h i c s t h i sd i s s e r t a t i o nm a i n l yr e s e a r c h e so nt h em c a l g o r i t h ma n di t sa p p l i c a t i o ni n3 dv i s u a ls i m u l a t i o no ff l u i d g r o u n d so na n a l y s i so fm c a l g o r i t h m ，d oi m p r o v eo nm ca l g o r i t h mt od oa3 dv i s u a ls i m u l a t i o no ff l u i db yi t ，a n dt h e r e n d e r i n gp r o c e s s e sa r ep r e s e n t e d t h em a i np o i n t so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 m a k ear e s e a r c h i n gs t a t u ss u m m a r yo fm ca l g o r i t h ma n df l u i d s i m u l a t i o n d o s o m er e s e a r c h e so nt h ep r i n c i p l ea n di m p l e m e n t a t i o no fm c a l g o r i t h m ，a n df u r t h e ra n a l y z e t h ep o s s i b l ea m b i g u i t yo fm cm e t h o dt o g e t h e rw i t hi t ss o l u t i o n s t h e nd i s c u s st h el e a d i n g w a y so ff l u i ds i m u l a t i o n 2 ab l o c k e d p a r t i a lt r a v e r s a la l g o r i t h mi nt h em a r c h i n gp e n t a h e d r a ( m p ) i sp r e s e n t e d ， a n di ti si m p r o v e db a s e do nm ca l g o r i t h m m pa l g o r i t h mi sp r e s e n t e dt or e n d e rs u r f a c ei n t h ed i s s e r t a t i o na n dt h ep o s s i b l ea m b i g u i t yo ft h em pm e t h o dw i t hi t ss o l u t i o n si sp r o p o s e d i no r d e rt oi m p r o v et h ec a l c u l a t i o ns p e e d ，ab l o c k e dp a r t i a lt r a v e r s a la l g o r i t h mi sp r e s e n t e d ， i tf i r s td i v i d et h es p a t i a ld a t af i e l di n t os o m eb l o c k s ，t h e nm a r c h i n ge a c hb l o c kf r o mo u t e r l a y e rt oi n n e rl a y e r t h et i m ee f f i c i e n c ya n di s o s u r f a c ep r e c i s i o no ft h i sa l g o r i t h mi sb e t t e r t h a nm c a l g o r i t h m 3 ar e s e a r c hh a sb e e nc a r r i e do nt h ed y n a m i c so ft h ep r o c e s so ft w ob u b b l e s c o a l e s c e n c ea n da3 dv i s u a ls i m u l a t i o nh a sb e e nd o n eo ni t f i r s t l y , an u m e r i c a lm o d e lo f t w ob u b b l ec o a l e s c e n c ed y n a m i cf e a t u r eh a sb e e ne s t a b l i s h e da c c o r d i n gt ot h ed y n a m i c s l a wa n dan u m e r i c a ls o l u t i o na n da n a l y s i sh a sb e e nd o n eo ni t t h e nan u m e r i c a ls o l u t i o n h a sb e e nd o n eb yt h em e t h o do fm a t l a b ，a3 dv i s u a ls i m u l a t i o nt ot h ee v o l u t i o np r o c e s s l i m c 算法研究及在三维流健可视化模拟中的应用a b s t r a c t o ft w ob u b b l e sc o a l e s c e n c eh a sb e e nd o n eb yl e v e ls e tm e t h o d ，b a s e do nm c a l g o r i t h m t h er e s u l t si n o s c u l a t ew e l lb o t h 埘t 1 1m a n g a sa n dl ix i a n g y a n g s 4 ap r o c e s sa n dm e t h o do f 鲥dd i v i d i n gb yl a y e r sf r o mp e n t a h e d r at ot e t r a h e d r a w h i c hs u p p o r t sb l o c k e dp a r t i a lt r a v e r s a la l g o r i t h m ，b a s e do nc u b e s ，h a sb e e np r e s e n t e d ， a n df i n a l l yac o m p l e t eg r i dd i v i d i n gs y s t e mh a sb e e nf o r m e d p e r f o r m a n c ec o m p a r i s o na n d e x p e r i m e n ta n a l y s i sw i t ht h et h r e ea l g o r i t h m s ，m ca l g o r i t h m ，ab l o c k e dp a r t i a lt r a v e r s a l a l g o r i t h mi nt h em a r c h i n gp e n t a h e d r am e t h o d ，m a r c h i n gt e t r a h e d r a ( m t ) a l g o r i t h m ，h a s b e e nc a r r i e do ni nt h i ss y s t e m k e y w o r d s ：s u r f a c er e n d e r i n g ，m a r c h i n gc u b e s ，f l u i ds i m u l a t i o n ，n a v i e r - s t o k e se q u a t i o n s w r i t t e n b y ：y ez a i c h u n s u p e r v i s e db y ：s u ny o n g i i i 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声瞬 本人郑重声舞：所提交的学位论文是本入在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不舍其健个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以骧确方式标明。本人承担本 声明的法律责任。 臻究生签名：盟鱼盔翟期：塑缝! 塑兰。日 学位论文使用授权声明 苏州大学、中国科学技术信患研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文棼，允许论文被查阅帮借阕，可以公布 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：咀璺查 曰 导萍签名：毒2 址尽 m c 算法研究及在三维流体可视化模拟中的应用第一章绪论 第一章绪论弟一早 三百t 匕 本章阐述了m c 算法研究及在三维流体可视化模拟中的应用这一课题的研究背 景和重要意义，分析了m c 算法和流体模拟的国内外研究现状，并在此基础上提出了 本课题的主要研究工作。 1 1选题的背景和意义 科学计算可视化方法主要分为两类：体绘制方法和面绘制方法。体绘制方法通过 灰度体数据场中的体素或体元来进行三维绘制。面绘制是科学计算可视化方法中常用 的一种方法，其特点是从体数据中提取解剖结构的等值面，通过图形学的方法对等值 面进行某一视角的三维绘制，从而得到该解剖结构的三维图像。面绘制技术的基本原 理是，首先对整个数据进行等值表面分割和定义，用各种几何元拟合表面，然后绘制 出所有的几何元n 1 。实际上，从数据场中构建的表面就是提取的某一阈值的逼近等值 面。m a r c h i n gc u b e s 方法以其简单和高效的特点，成为应用最广泛的等值面方法。近 年来，m a r c h i n gc u b e s 算法得到了广泛的关注，应用到很多可视化问题中，如流体的 三维可视化模拟；医学图像中的三维重建；有限元计算中的标量场分析；分子化学中 的分子表面显示；地质中矿藏分布的构造；等等。 计算流体力学( c f d ：c o m p u t a t i o n a lf l u i dd y n a m i c s ) 作为现代流体力学的一个 新兴分支，在最近几十年中有了长足的发展。计算流体力学是以理论流体力学、计算 数学和计算机科学为基础一门交叉学科。它的特点是可以给出流体运动区域内的离散 解，也即数值解。随着现代计算机技术、网格生成技术、数值计算方法的迅速发展， 计算流体力学求解流体运动问题的能力越来越高，基于物理的流体模拟成为目前一个 研究热点，也成为一个当前和未来计算机图形学发展的一个重点方向。基于物理的流 体模拟的研究主要集中在烟雾与云彩、燃烧与爆炸、自由运动界面、混合流和多相流、 非牛顿流体，以及流固耦合等问题上瞳，羽。另外整个发展研究的重点在于基于n s 方程 的方法。对于火焰、爆炸这类现象，温度占很重要的位置，这个时侯黑体辐射不可忽 视，而且还需考虑亮度过高带来的色适应问题。而对于烟雾之类的常温现象，其密度 场就可以完全表现了。对于烟、火这种参与媒介的绘制通常采用体绘制技术可以解决。 第一章绪论m c 算法研究及在三维流体可视化模拟中的应用 而对于自由运动界面这类问题，则通常需要采用m a r c h i n gc u b e s 方法重新构建出界 面多边形，然后采用几何体的绘制方法就可以了，如光线跟踪。因此流体的模拟方面 的技术取决于计算机图形学领域的其他方面的进展。目前，烟雾与云彩、燃烧与爆炸、 自由运动界面等方面的研究已取得相当的发展，有了很多成熟的算法，但是混合流和 多相流的模拟问题由于其相对复杂，已成为目前流体模拟的一个热点和难点问题。 m a r c h i n gc u b e s 算法的不断完善和发展，使得提供直观、逼真而且能够包含原始 信息中隐含的丰富的三维信息成为可能。在混合流和多相流的模拟中，不同流体间的 界面绘制极其重要，利用m a r c h i n gc u b e s 方法来进行绘制将成为一个广泛的应用方 法。将计算流体力学的数值方法与m a r c h i n gc u b e s 方法结合起来完成对流体三维可 视化的模拟对分析结果的准确性和正确性有深远意义，并促进了应用领域的发展。 1 2 研究现状 1 2 1 m a r c h i n gc u b e s 算法的研究现状 在l9 8 7 年，由w e l o r e n s o n 和h e c l i n e h 3 提出的m a r c h i n gc u b e s ( 以下将称其为 m c ) 算法是基于体元的一种典型的面绘制方法。m c 算法作为一种构造等值面的方法， 使用三角面片作为中间几何元的基本表达元素，较好地解决了在任意不规则、非线性 数据场中进行等值面重建的问题。 由于目前的显卡都可以对三角面片进行硬件加速的绘制，并且m c 算法本身原理 简单，容易实现，因此得到了广泛的应用，被认为是目前最流行的面绘制算法，对面 绘制的研究产生了深远的影响。一直到现在为止在可视化领域的著名杂志和会议上还 经常有针对m c 方法的改进算法。自标准的m c 算法提出以来，研究人员在这一方法 的研究主要集中在对m c 方法的扩展和m c 拓扑二义性问题的解决这两个方面圈。 m c 的二义性包括面二义性和体二义性。在m c 方法提出后不久，d i l r s t 在1 9 8 8 年首先发现了面二义性，g e l d e r 、n a t a r a j a n 对其进行了论证。最初，众多学者的注意 力主要集中在面二义性的问题上，目的是提取正确的边界多边形。然而，边界多边形 是等值面与体元边界的交点，不同的三线性插值曲面与体元相交可产生相同或相似的 边界多边形，从而导致体二义性的存在。1 9 9 4 年，bkn a t a r a j a n 发现了体二义性的 存在。 2 m c 算法研究及在三维流体可视化模拟中的应用第一章绪论 消除二义性的方法之一是重采样，实现简单，适用于数据集的函数是己知的情况， 缺点是可导致面片数的增加，因此并不常用。非重采样的方法可以分为布尔法和度量 法。布尔法有基于四面体剖分法方法( 移动四面体法m a r c h i n gt e t r a h e d r a ( m t ) ) 及其改 进算法修改查询表的方法和粗糙面片化模式。w y v i l l 提出的基于传播的等值面抽 取法，n i e l s o n 提出的渐近线方法( a s y m p t o t i cd e c i d e r ) 都属于度量法。这些方法中比 较经典的方法是渐近线方法和移动四面体法( m t ) 。 标准m c 的扩展的已有研究成果可以归结到输入、加速和输出三个方面。在输入 方面，由基本数据类型( 测量体积的数据3 d 点) 扩展到3 d 多决议直线网格数据障1 、 非矩形数据、4 d 网格n 3 、n d 直线网格陋1 等。在加速方面的改进是通过减少对不必要 元( 空元) 的处理来提高计算效率，可分为三大类。一类是分等级几何法，其方法有 w i l h e l m s 和v a ng e l d e r 提出的八叉树压缩算法b o n o ( b r a n c h o n n e e do c t r e e ) 阻1 ，s u t t o n p 和h a n s e nc 对b o n o 的扩展t - b o n n 们；一类是基于间隔的算法，它依据元间隔对 元分组，避免对空元的遍历，其方法有l i v n a t 等提出的n o i s e 算法、s h e n 等提 出的i s s u e 算法n 船；还有一类是基于传播的方法，传播处理只访问活跃元n 羽。输出 的扩展，就是对输出的三角面片的组成的扩展，已有的研究可将三角面片扩展到四边 形、齿形网格、点和多边形。高级等值面n 钔采用三角形的贝尔曲线法和三线插补法用 于每个立方体来确定片约束，它的好处是产生更平滑的等值面，可用于更重要的计算。 间隔体的抽取n 习是为打破标准m c 非易碎结构边界的限制而进行的扩展。像素等值面 n 町将多面片映射到简单的像素，节省了产生3 d 点的计算。交替三角形采用离散的 m c ( d m c ) 方法n 钉，用被分割的中点而不是用插补法来找等值面与边的相交点。d m c 的使用使得一些临近的面片是共面的，这些面片可以合并减少网格的大小，以降低内 存消耗和更快的网格描绘。此外，崔世华n 羽提出两种分别将等值点移动到高于阈值和 低于阈值的立方体顶点位置来简化等值面的拓扑构形，明显减少了重建三角面片的数 量，显著缩短重建时间。 m c 算法在三维流体可视化模拟中的应用主要是在自由运动界面问题上，这方面 的研究成果有利用m a r c h i n gc u b e s 算法重构出海洋表面n 盯，利用m a r c h i n gc u b e s 算 法重构出液体中的气泡表面嘲。 第一章绪论m c 算法研究及在三维流体可视化模拟中的应用 1 2 2 流体模拟的研究现状 在计算机图形学领域，人们一直试图利用计算机再现周围的真实世界，流体的模 拟成为目前一个研究热点，也成为当前和未来计算机图形学发展的一个重要方向。 在三维图形软件产品中已有不少包含了流体模拟的模块。如m a y a 中的m a y a f l u i de f f e c t s ，该模块的方法主要来自j o ss t a m 的论文位；在3 d sm a x 中则提供有 g l u 3 d 流体插件；独立的软件包，如n e x tl i m i t 推出的r e a l f l o w 和r e a l w a v e ，被称 为p c 机上最好的两种流体动力学模拟软件；f l u e n t 公司开发的f l u e n t 软件，是通 用c f d 流场计算分析软件，用于计算流体流动和传热问题，是目前功能最全的c f d 软件。 早期的流体模拟，由于计算机能力有限，主要采用参数建模的方法，即利用二些 简单过程函数来描述流体自由表面的变化。如馏明通过将波浪函数表示成一系列线性波 型的组合，将各个波型简化为波型和相位的组合函数，从而合成浅水表面高度场。又 如基于统计的f f t ( f a s tf o u r i e rt r a n s f o r m ) 经验模型n 叼可以很好的描述波幅较小的 海平面。但是对于以上这些模型，人们觉得控制起来很困难，而且不能模拟一些复杂 的、细节更为丰富的效果，于是很多研究者转向基于物理的方法。这样基于纳维斯 托克斯( n s ) 流体运动方程组的流体模拟方法开始普及起来。由于纳维一斯托克斯 ( n s ) 流体运动方程组本身的复杂性导致计算代价太大，对时间步长的要求过于苛 刻，以致应用起来比较麻烦。 基于物理的方法主要分为两种：第一种方法是从研究流体所占据的空间中各个固 定点处的运动着手，分析被运动流体所充满的空间中每一个固定点上的流体速度、压 强、密度等参数随时间的变化，以及研究由某一空间点转到另一空间点时这些参数的 变化，该方法被称为欧拉法，是一种基于网格的方法，其方法主要有s p h ( s m o o t h e d p a r t i c l eh y d r o d y n a m i c s ) ，m p s ( m o v i n gp a r t i c l es e m i i m p l i c i t ) ，m p s - m a f l ，l b m 等； 第二种方法是从分析流体各个微团的运动着手，即研究流体中某一指定微团的速度、 压强、密度等描述流体运动的参数随时间的变化，以及研究由一个流体微团转到其他 流体微团时参数的变化，以此来研究整个流体的运动，被称为拉格朗日法，是一种基 于粒子的方法，目前已经得到广泛应用的方法包括m a c ，l e v e ls e t ，f r o n tt r a c k i n g ， v o l u m eo ff l u i d ( v o f ) ，p a r t i c l el e v e ls e t 等。 4 m c 算法研究及在三维流体可视化模拟中的应用第一章绪论 s t a m 乜订引入半拉格朗日方法( s e m i l a g r a n g i a nm e t h o d ) 来求解对流项，同时结 合隐式迭代的方法来求扩展散项，这样求解格式稳定，使得整个模拟可以采用大的时 间步长。这种方法的引入无疑是流体模拟在计算机图形学领域里的一个里程碑。在此 之后，各种复杂流体的模拟很多都是基于该方法之上。 目前流体模拟的研究主要集中在烟雾与云彩乜钔、燃烧与爆炸幢朝、自由运动界面瞳们、 混合流和多相流3 、非牛顿流体汹3 ，以及流固耦合汹3 等问题上。空气、水两相流的模 拟问题是混合流和多相流模拟问题中最常见的。气泡的模拟也有了一定的发展。本文 主要探讨了气泡现象的模拟。 气泡动力学在很多方面都有很重要的应用，如空化气泡对螺旋桨的破坏，水下沼 气的收集，危险化学反应的模拟，生物呼吸，动画，游戏等。如e o l m o s 3 的研究应 用于多项流气泡的化学反应堆；v s j c r a i g 3 等研究了气泡聚并对电离子的影响；张 阿漫等b 3 的研究侧重于气泡对船舶的影响；顾汉洋b 司的研究应用于核动力工程； j e o n g m oh o n g 瞳伽的研究应用于动画和游戏。 自从上个世纪以来，气泡动力学一直是一个很重要的研究领域。学者无论在理论 分析、实验研究和数值模拟方面都进行了大量的研究工作，女l ：l g u e r r i 、b l a k e 、b a k e r 、 b e s t $ 1 1 k u c e r a 等人用轴对称模型研究了气泡在刚性壁面附近的运动特征；b l a c k 和 g i b s o n 、w a n g 啪1 等人用同样的轴对称模型模拟了近自由液面气泡的动力学特征； a k c h e s t e r s 矛d g h o f r n a n 对纯净液体中的气泡聚并过程进行了动态数值分析。在国 内，李建民啪3 用测量的方法研究单个气泡的动态特性；张阿漫等b 3 用 m i x e d - e u l e r i a n l a g r a n g i a n 方法对单个气泡的动力学特征和气泡在刚性壁面附近的 运动特征进行了数值模拟；双气泡聚并的研究工作则相对较少。 近年来，计算流体力学被广泛应用到流体的模拟中，气泡的三维可视化模拟取得 了很大的发展。c h a h i n e 、w i l k e r s o n 、z h a n g 、w a n g 、k l a s e b o e r 等人用三维模型模拟 了近结构、近自由液面的气泡的动态特征；j e o n g m oh o n g 基于m a r c h i n gc u b e s 算法， 模拟了两气泡聚并、近自由液面的气泡的动态特征。而在国内，关于气泡动态特征的 可视化模拟尚处于发展阶段，李建民用测量的方法研究单个气泡的动态特性；张阿漫 等m 侧采用的m i x e d e u l e r i a n l a g r a n g i a n 方法对单个气泡的动力学特征和气泡在刚 性壁面附近的运动特征进行了数值模拟；这些研究大多是单个气泡的模拟，且他们的 工作大多基于轴对称模型。李向阳等町采用改进质量守恒的体积校正法模拟了两气泡 5 第一章绪论m c 算法研究及在三维流体可视化模拟中的应用 聚并的动态过程，给出了满意的数值模拟结果。双气泡聚并的三维可视化动态模拟的 研究则相对较少。 1 3 论文的主要研究工作 本文的主要研究工作包括： ( 1 ) 总结了m a r c h i n gc u b e s 算法和流体模拟的研究现状，阐述了m a r c h i n gc u b e s 算法及其在三维流体可视化模拟中应用的研究意义。 ( 2 ) 研究了m a r c h i n gc u b e s 算法抽取等值面的基本思想、算法原理及实现方法， 分析了算法中连接方式产生二义性的原因及消除方法。讨论了基于物理的流体模拟的 两种方法：欧拉法和拉格朗日法。 ( 3 ) 在对用于从体数据场提取等值面的经典m c 算法进行研究的基础上，提出 了分块逐层遍历的移动五面体( m a r c h i n gp e n t a h e d r a ，m p ) 算法，并在此基础上建立 了一个以六面体为基础的五面体、四面体逐级细分的网格划分流程与方法，形成了一 个完整网格划分体系。本文提出的基于五面体剖分的算法郴算法，先将一个六 面体由体对角线划分成两个五面体，再依据类似六面体剖分的方法，抽取等值面。为 提高算法时间效率，采用分块逐层遍历的方法减少对空元的遍历。 ( 4 ) 对双气泡聚并过程的动力学规律进行了分析与研究，并对其进行了三维可视 化模拟。首先根据动力学规律建立了双气泡聚并的动态特征数值模型，并对该模型进 行数值求解与分析。采用m a t l a b 进行了数值模拟，另基于m c 算法，用l e v e ls e t 方 法对两气泡聚并的演化过程进行了三维可视化模拟，其结果与m a n g a 等的实验结果吻 合的很好，与李向阳等的数值模拟结果亦吻合的很好。 ( 5 ) 从算法实现难度、绘制的等值面的精度、算法的时间复杂度和生成的三角 面片数这四个方面来在理论上论述并比较了标准m c 、m t 算法和分块逐层遍历的移 动五面体算法，并通过实验对三种方法进行了进一步的比较结果分析。 1 4 论文的章节安排 全文共分五章，每一章的具体内容如下： 第一章绪论。阐述了m c 算法研究及在三维流体可视化模拟中的应用的研究背 6 m c 算法研究及在三维流体可视化模拟中的应用第一章绪论 景和重要意义，分析了m c 算法和流体模拟的国内外研究现状，在此基础上提出了本 课题的主要研究工作，然后给出了本文的章节安排。 第二章基本理论。本章研究了m c 算法和基于物理的流体模拟的方法。首先研究 了m c 算法的原理，详细阐述了m c 算法单个体素等值面确定的三个计算( 体素中等 值面剖分方式的确定、求等值面与体素边界的交点和三角面片各顶点法向量计算) 和 m c 算法的实现步骤，然后分析了m c 算法存在的二义性问题及其解决办法，详细研 究了渐近线方法和m t 算法：最后讨论了基于物理的流体模拟的两种方法，欧拉法和 拉格朗日法。 第三章m a r c h i n gc u b e s 算法的一种改进。本章首先对移动五面体算法的基本原 理、剖分方式、移动五面体算法的二义性及其消除进行了研究，同时阐述了分块逐层 遍历算法的基本思想。以此为依据，提出了一个支持分块逐层遍历算法、以六面体为 基础的五面体、四面体逐级细分的网格划分流程与方法，形成了一个完整网格划分体 系。最后将本文提出的算法与标准m c 和m t 算法进行了比较分析。 第四章b u b b l e s 模型的三维可视化。对双气泡聚并过程的动力学规律进行了分析 与研究，并对其进行了三维可视化模拟。根据动力学规律建立了双气泡聚并的动态特 征数值模型，并对该模型进行数值求解与分析。另基于分块逐层遍历的m p 算法，用 l e v e ls e t 方法对两气泡聚并的演化过程进行了三维可视化模拟，其结果与m a n g a 等的 实验结果吻合的很好，与李向阳等的数值模拟结果亦吻合的很好。 第五章总结与展望。对全文工作进行了回顾与总结，提出算法发展的趋势，并对 未来发展进行了展望。 7 第二章m a r c h i n gc u b e s 算法 m c 算法研究及在三维流体可视化模拟中的应用 第二章基本理论 弟一早荃今璀y 匕 本章研究了m c 算法和基于物理的流体模拟的基本方法。首先研究了m c 算法的 原理及实现方法，分析m c 算法在连接方式上二义性的产生和消除；然后讨论了基于 物理的流体模拟的两种方法：欧拉法和拉格朗日法。 2 1 m a r c h i n gc u b e s 算法 2 1 1 m a r c h i n gc u b e s 算法基本原理 m a r c h i n gc u b e s 算法是三维数据场等值面生成的经典算法，是体素单元内等值面 抽取技术的代表。这一类算法所处理的数据一般是离散的三维空间规则数据场，可表 示成： e 一 2 ，( ，以，z k ) 伽= 1 ，m ，聆= 1 ，虬，k = 1 , - - n k ) ( 2 1 ) 在这里，本文先给出在m c 算法中所用的几个定义。 定义1 ：在三维空间的某一个区域内进行采样，若采样点在x ，y ，2 三个方向 上的分布是均匀的，采样间距分别为缸，知，止，则体数据可以用三维数字矩阵 来表示。每八个相邻的采样点所定义的立方体区域就构成了一个体素( 也称为体元) ， 而这八个采样点称为该体素的角点，它们的坐标分别为( m ，胛，k ) ，( m + l ，聆，k ) ， ( 聊，n + 1 ，后) ，( m + 1 ，”+ 1 ，七) ，( 研，行，七+ 1 ) ，( m + 1 ，刀，k + 1 ) ，( 聊，n + 1 ，k + 1 ) 和 ( 刀? + 1 ，n + 1 ，k + 1 ) ，如图2 1 所示。 图2 - 1 移动立方体的体素( 体元) 定义2 ：假设( x ，少，z ) 为三维连续图象，其付氏变换r ( u ，v ，w ) 在频域中的一个有 限区域外处处为零，设对( x ，y ，z ) 按直网格均匀取样，工，y ，z 方向上的取样间隔 8 m c 算法研究及在三维流体可视化模拟中的应用 第二章m a r c h i n gc u b e s 算法 分别为缸，卸，止，则取样点的位置为x = m a x ，y = n a y ，z = k a z ，( m ，刀，k = o ，1 ，) ， 定义空间取样函数s ( x ，y ，z ) 是理想的引咏冲阵y u - s ( x ，y ，z ) = 8 ( x - m a x ，y 一刀缈，z - k a z ) ( 2 2 ) h i - - 月= k = - - ” 其中8 ( x , y , z ，= ”菇。 取样后的图象z ( x ，y ，z ) 等于原模拟图象f ( x ，y ，z ) 与取样函数的乘积( 取样间隔满 足奈奎斯特采样定理) ，nf a x ，y ，z ) 称为三维规则体数据。 z ( x ，y ，z ) = f ( x ，y ，z ) s ( x ，弘z ) ( 2 3 ) 定义3 ：p l 厂( p ) = c 称为等值点，p l ( p ) c 为正点，p i 厂( p ) 孓 卜 _ j 1 (d，c)(-d 图2 - 6 等值面与体素某一边界面的相交情况示意图 在图2 2 所示的1 4 种情况中，模式0 ，1 ，2 ，4 ，5 ，8 ，9 和1 1 不存在二义性面， 等值面是确定的。模式3 、6 各存在一个二义性面，各有2 种连接方式；模式1 0 、1 2 各有两个二义性面，各有4 种连接方式；模式7 有三个二义性面，有8 种连接方式； 模式1 3 有六个二义性面，有6 4 种连接方式。将以上模式加在一起，共有9 3 种不同 的连接方式，根据互补对称性和旋转对称性，同时限定体素的同一个面上不能出现同 一个三角面片的两条边，这些模式可以简化为2 1 种。根据渐近线方法，模式3 、6 、 7 、1 2 和1 3 的体素内部等值面连接方式如图2 7 所示，其中模式1 0 的连接方式与图 2 2 中是对称的，这里不再给出。 画国画 两薅霆 禽 画 图2 7 渐近线方法判定面二义性的结果 1 6 m c 算法研究及在三维流体可视化模拟孛的巍用第二章m a r c h i n gc u b e s 算法 按上述方法可以解决m c 算法的面二义性问题，但是不能解决m c 算法的体二义 性问题。本论文扩展渐近线方法来解决m c 算法的体二义性问题。根据2 2 节中体二 义性问题的描述和上述的渐近线方法，可以将二义性体素中同时包含标号为l 和标号 为0 的角点的体对角面看作是渐进线方法中的二义性面，则按着上述的处理可以解决 m c 算法的体二义性问题。在图2 2 所示的1 4 种情况中只有模式4 存在体二义性， 有两种连接方式，如图2 8 所示。 c a s e4 ( a )c a s e4 ( b ) 圈2 8 扩展渐近线方法判定体：义性的结果 对于存在二义性的体素，按上述方法鳃决二义性问题，可以得到完全正确的结果。 与前面解决面二义性问题时的2 1 种模式含并，则最后得到2 2 种模式。采用这2 2 种 模式来建立m c 算法所需的边查找表和三危形结构查找表，就麓解决m c 算法的二义 性问题。因此，采用渐近线方法可以正确的解决m c 算法的二义性问题，并且不会产 生太多的三焦面片，嚣丽是一季孛简洁丽高效的消除二义性的方法。 2 。1 。4 ，2 移动四面体( m t ) 算法 移动四面体( m a r c h i n gt e t r a h e d r a ) 算法简称为m t 算法，它是在m c 算法的基 础上发展起来的，是m c 算法的改进算法。m t 算法的基本原理是首先将立方体体素 剖分成多个四面体，然后在各四面体中构造等值面。 假设在四面体的边上，数据场呈线性变化，由予四面体的每个面都是三角形，生 成的等值面片的连接方式是唯一的，并且对于每个四面体，等值面模式只有三种情况， 如图2 - 9 所示。如果顶点数据值全大于或者全小于等值面阈值c ，则等值面与单元不 相交，如图2 - 9 ( a ) 所示；如果一个顶点大于而另外三个顶点小于等值面阈值c ，则 1 7 第二章m a r c h i n gc u b e s 算法 m c 算法研究及在三维流体可视化模拟中的应用 四面体中的等值面是一个三角面片，如图2 - 9 ( b ) 所示；如果两个顶点大于而另外两 个顶点小于等值面阈值c ，则等值面是一个四边形，可以由两个三角形构造，如图2 - 9 ( c ) 所示。四面体内等值面的绘制步骤与m c 算法一致。 ( b ) 图2 - 9 四面体中的等值面 在实际上，根据图2 - 9 中所建立的四面体中的等值面的构型，构造两个长度为1 6 的查找表。一个记录所有情况下的等值面连接方式，即等值面与剖分四面体6 条棱的 交点，定义为边查找表。则以根据体素的顶点分类规则所得的数值为下标，查找边查 找表获得等值面连接方式，再连接等值点就形成等值面片。但由于需要以图形学方式 表达等值面片，而仅知道等值面与剖分四面体的交点，是无法确定其空间拓扑结构的， 因此通过另外一个表记录等值面连接方式对应的三角面片的边的组成，定义其为三角 形结构查找表，用来构造对应的三角化等值面。 常见的立方体剖分成四面体的方法有5 个，6 个和2 4 个四面体剖分法。然而，5 个或6 个四面体的剖分是一种不对称的剖分，剖分后形成的四面体不全等。对于5 个四面体的剖分，如图2 1 0 所示，由于立方体体素两对面的剖分线不平行，则两个 相邻的立方体体素若采用相同的剖分方式，相邻体素的公共面上的剖分线相交，可能 出现裂缝，这无疑增加了处理的复杂性。为了避免在其公共面上出现裂缝，必须保证 在相邻体元的公共面上的剖分一致性因此考虑在一系列体素中使四面体剖分方式交 替变化，从而保证在相