MC算法研究及在三维流体可视化模拟中的应用（可编辑）

MC算法研究及在三维流体可视化模拟中的应用（可编辑） 苏州大学 硕士学位论文 MC算法研究及在三维流体可视化模拟中的应用 姓名:叶再春 申请学位级别:硕士 专业:计算机软件与理论 指导教师:孙涌 20090501算法研究及在三维流体可视化模拟中的应用 中文摘要 算法研究及在三维流体可视化模拟中的应用 中文摘要 ,算法是应用最广泛的等值面方法,其研究 移动立方体 主要集中在算法的改进和算法在不同领域的应用上。算法在三维流体可视化 中的 应用己成为计算机图形学中一个重要研究热点。本文主要研究了算法及其在 三维 流体模拟中的应用,在 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 算法的基础上,对算法进行改进,以使其更好地 应用到三维流体可视化模拟中,达到基本实时绘制的效果。本文的主要内容 如下: 、总结了算法和流体模拟的研究现状。研究了算法的原理及实现方法, 并分析了其可能存在的二义性问题及其解决方法;讨论了流体模拟的主要方 法。 , 、对算法进行改进,提出分块逐层遍历的移动五面体 算法。本文提出了算法来绘制等值面,同时也分析了算法可能存在的 二义性问题及其解决方法;为提高算法的时间效率,提出了将空间体数据场分为若干’ 块,然后对每一块实现由外层向内层的逐层遍历的方法。该改进算法提高了算法 的时间效率和等值面精度。 、对双气泡聚并过程的动力学规律进行了分析与研究,并对其进行了三维可视化 模拟。首先根据动力学规律建立了双气泡聚并的动态特征数值模型,并对该模型进行 数值求解与分析。采用进行了数值模拟,另基于算法,用 方法 对两气泡聚并的演化过程进行了三维可视化模拟,其结果与等的实验结果吻合 的很好,与李向阳等的数值模拟结果亦吻合的很好。 、提出了一个支持分块逐层遍历算法、以六面体为基础的五面体、四面体逐级 细分的网格划分 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 与方法,形成了一个完整网格划分体系。并在此体系上对算 ,算法和分块逐层遍历的算法进行性 法、移动四面体 能比较和实验分析。 关键词:面绘制,移动立方体,流体模拟,方程 作 者:叶再春 指导老师:孙涌’, . ? . . , , :. .’. , . . . , . . ,, , ?. . . . ., 算法研究及在三维流健可视化模拟中的应用 , . 埘’ ’. . 鲥 , , , . , ,, ,. , : , , : : 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声瞬 本人郑重声舞:所提交的学位论文是本入在导师的指导下,独立 进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文 不舍其健个人或集体已经发表或撰写过的研究成果,也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体,均已在文中以骧确方式标明。本人承担本 声明的法律责任。 臻究生签名:盟鱼盔 翟期:塑缝塑兰。日 学位论文使用授权声明 苏州大学、中国科学技术信患研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档,可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文棼,允许论文被查阅帮借阕,可以公布包括刊登论文的 全部或部分内容。论文的公布包括刊登授权苏州大学学位办办理。 曰 研究生签名:咀璺查 导萍签名:毒址.尽算法研究及在三维流体可视化模拟中的应用 第一章绪论 绪 三百 论 匕 第一章 弟一早 本章阐述了算法研究及在三维流体可视化模拟中的应用这一课题的研究背 景和重要意义,分析了算法和流体模拟的国内外研究现状,并在此基础上提出了 本课题的主要研究工作。 . 选题的背景和意义 科学计算可视化方法主要分为两类:体绘制方法和面绘制方法。体绘制方法通过 灰度体数据场中的体素或体元来进行三维绘制。面绘制是科学计算可视化方法中常用 的一种方法,其特点是从体数据中提取解剖结构的等值面,通过图形学的方法对等值 面进行某一视角的三维绘制,从而得到该解剖结构的三维图像。面绘制技术 的基本原 理是,首先对整个数据进行等值表面分割和定义,用各种几何元拟合表面,然后绘制 出所有的几何元。实际上,从数据场中构建的表面就是提取的某一阈值的逼近等值 方法以其简单和高效的特点,成为应用最广泛的等值面方法。近 面。 算法得到了广泛的关注,应用到很多可视化问题中,如流体的 年来, 三维可视化模拟;医学图像中的三维重建;有限元计算中的标量场分析;分子化学中 的分子表面显示;地质中矿藏分布的构造;等等。 计算流体力学: 作为现代流体力学的一个 新兴分支,在最近几十年中有了长足的发展。计算流体力学是以理论流体力学、计算 数学和计算机科学为基础一门交叉学科。它的特点是可以给出流体运动区域内的离散 解,也即数值解。随着现代计算机技术、网格生成技术、数值计算方法的迅速发展, 计算流体力学求解流体运动问题的能力越来越高,基于物理的流体模拟成为目前一个 研究热点,也成为一个当前和未来计算机图形学发展的一个重点方向。基于 物理的流 体模拟的研究主要集中在烟雾与云彩、燃烧与爆炸、自由运动界面、混合流和多相流、 非牛顿流体,以及流固耦合等问题上瞳,羽。另外整个发展研究的重点在于基于方程 的方法。对于火焰、爆炸这类现象,温度占很重要的位置,这个时侯黑体辐射不可忽 视,而且还需考虑亮度过高带来的色适应问题。而对于烟雾之类的常温现象,其密度 场就可以完全表现了。对于烟、火这种参与媒介的绘制通常采用体绘制技术可以解决。第一章绪论 算法研究及在三维流体可视化模拟中的应用 而对于自由运动界面这类问题,则通常需要采用 方法重新构建出界 面多边形,然后采用几何体的绘制方法就可以了,如光线跟踪。因此流体的模拟方面 的技术取决于计算机图形学领域的其他方面的进展。目前,烟雾与云彩、燃烧与爆炸、 自由运动界面等方面的研究已取得相当的发展,有了很多成熟的算法,但是混合流和 多相流的模拟问题由于其相对复杂,已成为目前流体模拟的一个热点和难点问题。 算法的不断完善和发展,使得提供直观、逼真而且能够包含原始 信息中隐含的丰富的三维信息成为可能。在混合流和多相流的模拟中,不同 流体间的 方法来进行绘制将成为一个广泛的应用方 界面绘制极其重要,利用 方法结合起来完成对流体三维可 法。将计算流体力学的数值方法与 视化的模拟对分析结果的准确性和正确性有深远意义,并促进了应用领域的发展。 .研究现状 .. 算法的研究现状 在 年,由..和..提出的 以下将称其为 算法是基于体元的一种典型的面绘制方法。算法作为一种构造等值面的方法, 使用三角面片作为中间几何元的基本表达元素,较好地解决了在任意不规则、非线性 数据场中进行等值面重建的问题。 由于目前的显卡都可以对三角面片进行硬件加速的绘制,并且算法本身原理 简单,容易实现,因此得到了广泛的应用,被认为是目前最流行的面绘制算法,对面 绘制的研究产生了深远的影响。一直到现在为止在可视化领域的著名杂志和会议上还 经常有针对方法的改进算法。自 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的算法提出以来,研究人员在这一方法 的研究主要集中在对方法的扩展和拓扑二义性问题的解决这两个方面圈。 ‘‘ 的二义性包括面二义性和体二义性。在方法提出后不久,在 年首先发现了面二义性,、对其进行了论证。最初,众多学者的注意 力主要集中在面二义性的问题上,目的是提取正确的边界多边形。然而,边界多边形 是等值面与体元边界的交点,不同的三线性插值曲面与体元相交可产生相同或相似的 边界多边形,从而导致体二义性的存在。年, 发现了体二义性的 存在。 算法研究及在三维流体可视化模拟中的应用 第一章绪论 消除二义性的方法之一是重采样,实现简单,适用于数据集的函数是己知的情况, 缺点是可导致面片数的增加,因此并不常用。非重采样的方法可以分为布尔法和度量 法。布尔法有基于四面体剖分法方法移动四面体法 及其改 进算法??修改查询表的方法和粗糙面片化模式。提出的基于传播的等值面抽 取法,提出的渐近线方法 都属于度量法。这些方法中比 较经典的方法是渐近线方法和移动四面体法。 ’ 标准的扩展的已有研究成果可以归结到输入、加速和输出三个方面。在输入 方面,由基本数据类型测量体积的数据点扩展到多决议直线网格数据障、 非矩形数据、网格、.直线网格陋等。在加速方面的改进是通过减少对不必要 元空元的处理来提高计算效率,可分为三大类。一类是分等级几何法,其方法有 阻, 和 提出的八叉树压缩算法.. 和 对的扩展们;一类是基于间隔的算法,它依据元间隔对 元分组,避免对空元的遍历,其方法有等提出的算法九、等提 出的算法船;还有一类是基于传播的方法,传播处理只访问活跃元羽。输出 的扩展,就是对输出的三角面片的组成的扩展,已有的研究可将三角面片扩展到四边 形、齿形网格、点和多边形。高级等值面钔采用三角形的贝尔曲线法和三线插补法用 于每个立方体来确定片约束,它的好处是产生更平滑的等值面,可用于更重要的计算。 间隔体的抽取习是为打破标准非易碎结构边界的限制而进行的扩展。像素等值面 町将多面片映射到简单的像素,节省了产生点的计算。交替三角形采用离散的 方法钉,用被分割的中点而不是用插补法来找等值面与边的相交点。 的使用使得一些临近的面片是共面的,这些面片可以合并减少网格的大小,以降低内 存消耗和更快的网格描绘。此外,崔世华羽提出两种分别将等值点移动到高于阈值和 低于阈值的立方体顶点位置来简化等值面的拓扑构形,明显减少了重建三角面片的数 ? 量,显著缩短重建时间。 算法在三维流体可视化模拟中的应用主要是在自由运动界面问题上,这方面 算 的研究成果有利用 算法重构出海洋表面盯,利用 法重构出液体中的气泡表面嘲。第一章绪论 算法研究及在三维流体可视化模拟中的应用 ..流体模拟的研究现状 在计算机图形学领域,人们一直试图利用计算机再现周围的真实世界,流体的模 拟成为目前一个研究热点,也成为当前和未来计算机图形学发展的一个重要方向。 在三维图形软件产品中已有不少包含了流体模拟的模块。如中的 ,该模块的方法主要来自 的论文位?;在 中则提供有 推出的和,被称 流体插件;独立的软件包,如 为机上最好的两种流体动力学模拟软件;公司开发的软件,是通 用流场计算分析软件,用于计算流体流动和传热问题,是目前功能最全的 软件。 早期的流体模拟,由于计算机能力有限,主要采用参数建模的方法,即利用二些 简单过程函数来描述流体自由表面的变化。如馏明通过将波浪函数表示成一系列线性波 型的组合,将各个波型简化为波型和相位的组合函数,从而合成浅水表面高度场。又 如基于统计的 经验模型叼可以很好的描述波幅较小的 海平面。但是对于以上这些模型,人们觉得控制起来很困难,而且不能模拟一些复杂 的、细节更为丰富的效果,于是很多研究者转向基于物理的方法。这样基于纳维.斯 托克斯.流体运动方程组的流体模拟方法开始普及起来。由于纳维一斯托克斯 .流体运动方程组本身的复杂性导致计算代价太大,对时间步长的要求过于苛 刻,以致应用起来比较麻烦。 基于物理的方法主要分为两种:第一种方法是从研究流体所占据的空间中各个固 定点处的运动着手,分析被运动流体所充满的空间中每一个固定点上的流体 速度、压 强、密度等参数随时间的变化,以及研究由某一空间点转到另一空间点时这些参数的 变化,该方法被称为欧拉法,是一种基于网格的方法,其方法主要有, ?,,等; 第二种方法是从分析流体各个微团的运动着手,即研究流体中某一指定微团的速度、 压强、密度等描述流体运动的参数随时间的变化,以及研究由一个流体微团转到其他 流体微团时参数的变化,以此来研究整个流体的运动,被称为拉格朗日法,是一种基 于粒子的方法,目前已经得到广泛应用的方法包括, , , 等四。 , 算法研究及在三维流体可视化模拟中的应用 第一章绪论 来求解对流项,同时结 乜订引入半拉格朗日方法. 合隐式迭代的方法来求扩展散项,这样求解格式稳定,使得整个模拟可以采用大的时 间步长。这种方法的引入无疑是流体模拟在计算机图形学领域里的一个里程碑。在此 之后,各种复杂流体的模拟很多都是基于该方法之上。 目前流体模拟的研究主要集中在烟雾与云彩乜钔、燃烧与爆炸幢朝、自由运 动界面瞳们、 混合流和多相流?、非牛顿流体汹,以及流固耦合汹等问题上。空气、水两相流的模 拟问题是混合流和多相流模拟问题中最常见的。气泡的模拟也有了一定的发展。本文 主要探讨了气泡现象的模拟。 气泡动力学在很多方面都有很重要的应用,如空化气泡对螺旋桨的破坏,水下沼 气的收集,危险化学反应的模拟,生物呼吸,动画,游戏等。如.?的研究应 用于多项流气泡的化学反应堆;...?等研究了气泡聚并对电离子的影响;张 阿漫等?的研究侧重于气泡对船舶的影响;顾汉洋司的研究应用于核动力 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 ; . 瞳伽的研究应用于动画和游戏。 自从上个世纪以来,气泡动力学一直是一个很重要的研究领域。学者无论在理论 分析、实验研究和数值模拟方面都进行了大量的研究工作,女:、、、 等人用轴对称模型研究了气泡在刚性壁面附近的运动特征;和 、啪等人用同样的轴对称模型模拟了近自由液面气泡的动力学特征; ..矛四对纯净液体中的气泡聚并过程进行了动态数值分析。在国 内,李建民啪用测量的方法研究单个气泡的动态特性;张阿漫等?用 .方法对单个气泡的动力学特征和气泡在刚性壁面附近的 运动特征进行了数值模拟;双气泡聚并的研究工作则相对较少。 近年来,计算流体力学被广泛应用到流体的模拟中,气泡的三维可视化模拟取得 了很大的发展。、、、、等人用三维模型模拟 算法, 了近结构、近自由液面的气泡的动态特征;? 基于 模拟了两气泡聚并、近自由液面的气泡的动态特征。而在国内,关于气泡动态特征的 可视化模拟尚处于发展阶段,李建民用测量的方法研究单个气泡的动态特性;张阿漫 等侧采用的?.方法对单个气泡的动力学特征和气泡在刚 性壁面附近的运动特征进行了数值模拟;这些研究大多是单个气泡的模拟,且他们的 工作大多基于轴对称模型。李向阳等?町采用改进质量守恒的体积校正法模拟了两气泡 第一章绪论 算法研究及在三维流体可视化模拟中的应用 聚并的动态过程,给出了满意的数值模拟结果。双气泡聚并的三维可视化动态模拟的 研究则相对较少。 .论文的主要研究工作 本文的主要研究工作包括: 总结了 算法和流体模拟的研究现状,阐述了 算法及其在三维流体可视化模拟中应用的研究意义。 算法抽取等值面的基本思想、算法原理及实现方法, 研究了 分析了算法中连接方式产生二义性的原因及消除方法。讨论了基于物理的流体模拟的 两种方法:欧拉法和拉格朗日法。 在对用于从体数据场提取等值面的经典算法进行研究的基础上,提出 ,算法,并在此基础上建立 了分块逐层遍历的移动五面体 了一个以六面体为基础的五面体、四面体逐级细分的网格划分流程与方法,形成了一 个完整网格划分体系。本文提出的基于五面体剖分的算法?郴算法,先将一个六 面体由体对角线划分成两个五面体,再依据类似六面体剖分的方法,抽取等值面。为 提高算法时间效率,采用分块逐层遍历的方法减少对空元的遍历。 对双气泡聚并过程的动力学规律进行了分析与研究,并对其进行了三维可视 化模拟。首先根据动力学规律建立了双气泡聚并的动态特征数值模型,并对该模型进 行数值求解与分析。采用进行了数值模拟,另基于算法,用 方 法对两气泡聚并的演化过程进行了三维可视化模拟,其结果与等的实验结果吻 合的很好,与李向阳等的数值模拟结果亦吻合的很好。 从算法实现难度、绘制的等值面的精度、算法的时间复杂度和生成的三角 面片数这四个方面来在理论上论述并比较了标准、算法和分块逐层遍历的移 动五面体算法,并通过实验对三种方法进行了进一步的比较结果分析。 .论文的章节安排 全文共分五章,每一章的具体内容如下: 第一章绪论。阐述了算法研究及在三维流体可视化模拟中的应用的研究背 算法研究及在三维流体可视化模拟中的应用 第一章绪论 景和重要意义,分析了算法和流体模拟的国内外研究现状,在此基础上提出了本 课题的主要研究工作,然后给出了本文的章节安排。 第二章基本理论。本章研究了算法和基于物理的流体模拟的方法。首先研究 了算法的原理,详细阐述了算法单个体素等值面确定的三个计算体素中等 值面剖分方式的确定、求等值面与体素边界的交点和三角面片各顶点法向量计算和 算法的实现步骤,然后分析了算法存在的二义性问题及其解决办法,详细研 究了渐近线方法和算法:最后讨论了基于物理的流体模拟的两种方法,欧拉法和 拉格朗日法。 算法的一种改进。本章首先对移动五面体算法的基本原 第三章 理、剖分方式、移动五面体算法的二义性及其消除进行了研究,同时阐述了分块逐层 遍历算法的基本思想。以此为依据,提出了一个支持分块逐层遍历算法、以六面体为 基础的五面体、四面体逐级细分的网格划分流程与方法,形成了一个完整网格划分体 系。最后将本文提出的算法与标准和算法进行了比较分析。 第四章模型的三维可视化。对双气泡聚并过程的动力学规律进行了分析 与研究,并对其进行了三维可视化模拟。根据动力学规律建立了双气泡聚并的动态特 征数值模型,并对该模型进行数值求解与分析。另基于分块逐层遍历的算法,用 方法对两气泡聚并的演化过程进行了三维可视化模拟,其结果与等的 实验结果吻合的很好,与李向阳等的数值模拟结果亦吻合的很好。 第五章总结与展望。对全文工作进行了回顾与总结,提出算法发展的趋势,并对 未来发展进行了展望。 算法 算法研究及在三维流体可视化模拟中的应用 第二章 第二章基本理论 弟一早荃今璀匕 本章研究了算法和基于物理的流体模拟的基本方法。首先研究了算法的 原理及实现方法,分析算法在连接方式上二义性的产生和消除;然后讨论了 基于 物理的流体模拟的两种方法:欧拉法和拉格朗日法。 . 算法 .. 算法基本原理 算法是三维数据场等值面生成的经典算法,是体素单元内等值面 抽取技术的代表。这一类算法所处理的数据一般是离散的三维空间规则数据场,可表 示成: 一,‰,以, 伽,?,聆,..‘虬,. . 在这里,本文先给出在算法中所用的几个定义。 定义:在三维空间的某一个区域内进行采样,若采样点在,,三个方向 上的分布是均匀的,采样间距分别为缸,知,止,则体数据可以用三维数字矩阵 来表示。每八个相邻的采样点所定义的立方体区域就构成了一个体素也称为体元, 而这八个采样点称为该体素的角点,它们的坐标分别为,胛,,,聆,, 聊,,后, ,”,七, 研,行,七, ,刀,, 聊,,和 刀,,,如图.所示。 图移动立方体的体素体元 定义:假设/,少,为三维连续图象,其付氏变换,,在频域中的一个有 限区域外处处为零,设对/,,按直网格均匀取样,工,,方向上的取样间隔 算法 算法研究及在三维流体可视化模拟中的应用 第二章 分别为缸,卸,止,则取样点的位置为,,,,刀,,?,?, 定义空间取样函数,,是理想的引咏冲阵 ? ,,???,一刀缈, ?月?” 其中,”菇。。 取样后的图象,,等于原模拟图象,,与取样函数的乘积取样间隔满 足奈奎斯特采样定理, ,,称为三维规则体数据。 ? ,,,,,弘 定义:厂称为等值点,/?为正点,厂为负点,,,。 定义:等值面的定义:等值面是空间中所有具有某个相同值的点的集合。它可 以表示为,,,,,,是常数。则称力为体数据中的等 .. 值面。.一 在算法中,假定原始数据是离散的三维空间规则数据场。算法的基本思 想是逐个处理数据场中的体素,分类出与等值面相交的体素,采用线性插值计算出等 值面与体素棱边的交点。根据体素中每一顶点与等值面的相对位置,将等值面与立方 体边的交点按一定方式连接生成等值面,作为等值面在该立方体内的一个逼近表示。 在计算出关于体数据场内等值面的有关参数后由常用的图形软件包或硬件提供的面 绘制功能绘制出等值面。 .. 算法的实现 由上节中算法的基本思想,可知,算法中每个体素内等值面的抽取是核 心问题,每个体素内等值面的抽取的两个主要计算是: 体素中由三角面片逼近的等值面计算; 三角面片各顶点法向量计算。 体素中由三角面片逼近的等值面计算又可分解为两个计算:体素中等值面剖分方 式的确定和求等值面与体素边界的交点。下面详细介绍这三个计算。 .体素中等值面剖分方式的确定 算法 算法研究及在三维流体可视化模拟中的应用 第二章 算法的基本假设是沿着体素的棱边数据场呈连续线性变化,也就是说,如果 一条棱边的两个顶点的数据场值分布大于、小于等值面的值,则该条边上有且仅有一 点是等值面与该边的交点。确定立方体体素内部的等值面的分布是该算法的基础。 首先对体素的个顶点进行分类,以判定该顶点是位于等值面之内还是等值面之 外。再根据个顶点的状态,确定等值面的剖分方式。 假定等值面的阈值为,则顶点分类规则为: 如果体素顶点的数据场值?,则定义该顶点位于等值面之外,标记“: 如果体元顶点的数据场值,则定义该顶点位于等值面之内,标记“”。 由于每个体素有个顶点,每个顶点只有两种状态,因此共有种组合状 态。根据互补对称性,即体素的顶点标记置反变为,变为,不影响该体素 内三角面片的拓扑结构,这样种构型可以简化成种。再根据旋转对称性,可 将这种构型进一步简化成种,再根据镜面对称性,可将种构型再进一步简 化成种。图.给出了这种基本构型的三角剖分,其中黑点表示标记为的角 点。对于个角点的标记都为或者都为的体素,它属于“号构型,没有等值 面穿过该体素。当只有一个角点标记为时,即“”号构型,可用一个三角面片代 表体素内的等值面片,它将该角点与其它个角点分成两部分。对于其余几种构型, 将产生多个三角面片。 在实际上,根据图.中所建立的等值面的构型,构造两个长度为的查 找表。一个记录所有情况下的等值面连接方式,即等值面与体素条棱的交点,定 义为边查找表。则以根据体素的顶点分类规则所得的数值为下标,查找边查找表获得 等值面连接方式,再连接等值点就形成等值面片。但由于需要以图形学方式表达等值 面片,而仅知道等值面与体素的交点,是无法确定其空间拓扑结构的,因此通过另外 一个表记录等值面连接方式对应的三角面片的边的组成,定义为三角形结构查找表, 。 用来构造对应的三角化等值面。 体素中等值面剖分方式确定的方法是:首先,将体数据场中当前体素的个顶点 的函数值与等值面阂值进行比较,得到该体素的关键索引字节 。然后, 根据关键索引字节 的值在边查找表中找出对应的等值面接方式用来计算 等值面与体素的交点和等值面三角面片各顶点的法向量,并且根据关键索引字节 的值在三角形结构查找表中找出该体素对应的三角剖分构型用来绘制等 算法研究及在三维流体可视化模拟中的应用 算法 第二章 值面,其过程如图.所示。 面厦 羼莺 凰厕 留圆 图 等值面的种构型 固 皿 图.体素中等值面剖分方式的确定的过程算法 算法研究及在三维流体可视化模拟中的应用 第二章 .求等值面与体素边界的交点 在确定立方体内三角剖分模式后,就要计算三角面片各顶点的位置。当三维离散 数据场的密度较高时,即当体素很小时,可以假定函数值沿体素边界呈线性变化,这 就是算法的基本假设。因此,根据这一基本假设,可以直接用线性插值计算等值 面与体素边的交点。 对于当前被处理体素的某一条边,如果其两顶点,吃的标记值不同,那么等值 面一定与此边相交,且仅有一个交点。 体素棱边与轴平行,设该边的两顶点为聊,门,,,刀,,则交 点为,甩,后: :聊丝二』塑 . 一/】 体素棱边与】,轴平行时,设该边的两顶点为聊,刀,,,,,则 交点为,,尼: . ,:刀上』掣: 。 一/】 体素棱边与轴平行时,设该边的两顶点为聊,,,,力,,则 交点为,,尼: :尼.鬯』垒址 . 【】 求出等值面与体素棱边的交点以后,就可以将这些交点连接成三角形或多边 形, 形成等值面的一部分。 .三角面片各顶点法向量计算 为了利用图形硬件显示等值面图象,必须给出形成等值面的各三角面片的法 向分 量,选择适当的局部面光照模型进行光照计算,以生成真实感图形。 对于等值面上的每一点,其沿面的切线方向的梯度分量应该是零,因此,该点 的 梯度矢量的方向也就代表了等值面在该点的法向。而且等值面往往是由两种具有不 同密度的物质的分界面,因此其上的每点的梯度矢量均不为零,即 算法研究及在三维流体可视化模拟中的应用 算法 第二章 ,,,, 由于直接计算三角面片的法向很费时,而且,容易在各三角面片之间产生明暗度 的不连续变化,因此在本论文中采用由三角面片顶点的梯度替代三角面片法向量,最 后采用光照模型实现等值面的绘制。 本文采用中心差分计算出体素各角点处的梯度,然后再一次通过体素棱边两个端 点处梯度的线性插值求出三角面片各项点的梯度,也就是各项点处的法向,从而实现 等值面的绘制。体素角点的中心差分公式如下: 矗:盥血盐婪掣监盟 ? 蹦,丛监亳掣 &训,:盥碰地筌墅盟 ? 其中,血,知,位分别为体素的边长。 解决了这三个主要的问题,现归纳算法抽取等值面的步骤如下: 将三维离散规则数据场分层读入,得到初始的体数据场;‘ 将数据场中当前体素的每个顶点的函数值与给定的等值面阈值做比较, 具体见计算; 根据比较结果,得到该体素的关键索引字节 根据该体素的关键索引字节 ,查找使用的边查找表得出该 体素的等值面连接方式【具体见计算; 通过线性插值方法计算出体素棱边与等值面的交点具体见计算; 利用中心差分方法,求出体素各角点处的法向量,再通过线性插值方法, 求出三角面片各顶点处的法向向量具体见计算; 根据该体素的关键索引字节 ,查找使用的三角形结构查找 表得到该体素内的等值面的三角面片组成结构,同时根据各三角面片各顶点 的法向 量,在一定的光照模型下绘制该体素内的等值面。 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 体数据场中的所有体素是否全部处理完毕,如否,则进行到下一个体 素,回到第步处理。如是,则体数据场中等值面的提取完毕,最后获得的等值 面即是所求等值面。算法 算法研究及在三维流体可视化模拟中的应用 第二章 .. 算法的二义性问题 最早发现算法中的二义性问题。如果在体素的一个面上,标号为和 标号为的角点分别位于对角线的两端,则该表面上存在四个等值点,那么就 会有两 种可能的等值线的连接方式,因而存在着二义性,如图所示,图中包含黑点的区 域为正点区。通常把这样的面称为二义性面,这种二义性称为面二义性。如果两个包 含二义性面的体素相邻,并且两个面对面连接方式选择不一致时,在相邻的面之间可 能出现“孔洞”。 观察图.中的体素状态模型可知,、中有一个面存在二义性,中有两个 面存在二义性,、中三个面存在二义性,而中的六个面都存在二义性。 面二义性的二维表示 面二义性的三维表示 图?方法的面二义性 随着方法的广泛应用和对其研究的逐步深入,人们又发现了新的问题, 年, “帕发现了体二义性的存在。根据三维线性插值,即使体素的六个表 面都不存在二义性,体素内部的等值面仍然不确定。如图.中所示体素状态模型, 其内部的等值面可能为两片分离的面片,也可能为一“管”状曲面,也就是说, 算法的体元状态模型查找表不完整,不能保证逼近等值面的拓扑正确性。 算法研究及在三维流体可视化模拟中的应用 算法 第二章 图.体二义性和“管”状曲面 .. 算法二义性问题的消除 消除二义性的方法之一是重采样,实现简单,适用于数据集的函数是已知的情况, 缺点是可导致面片数的增加,因此并不常用。非重采样的方法可以分为布尔法和度量 法。布尔法有基于四面体剖分法方法移动四面体算法蛆及其改进算法??修改查询 表的方法“和粗糙面片化模式朝。提出的基于传播的等值面抽取法引, 提出的渐近线方法 “印都属于度量法。这些方法中比较经典的方法 ,算法?,本文主要研究 是渐近线方法一叼和移动四面体 这两种方法。 ...渐近线方法等人提出的渐近线方法习是应用最为广泛的二义性消除算法,本论 文在三维流体可视化时亦采用该方法来消除等值面连接方式的二义性。基本原理是: 当出现面二义性时,等值面与该边界面的交线是双曲线,该双曲线的两支将该边界面 分成三个区域,双曲线中两条渐近线的交点必然与边界面中位于对角线上的一对交点 落在同一区域,根据等值面阈值与双曲线的渐近线交点处线性插值结果的大 小情况 来判定这个体素表面采用那种连接方式。 根据渐近线方法,位于体素某一边界面的等值线是一对渐近线分别与体素边 相平 行的双曲线,该双曲线的两支及其渐近线与体素的该边界面可能交于、、、、 、个交点,如图所示。其中、和三种均为退化情形,为处理简单,将归 并为,归并为。只考虑双曲线与体元表面存在、和个交点的情形, 即图中、和所示的情形。算法 算法研究及在三维流体可视化模拟中的应用 第二章 ??? \ 久 ‘ ‘ ???? 广 弋 ?孓. ?孓~. ??卜 ?、?一 \ ,‘ 图等值面与体素某一边界面的相交情况示意图 在图.所示的种情况中,模式,,,,,,和不存在二义性面, 等值面是确定的。模式、各存在一个二义性面,各有种连接方式;模式、 各有两个二义性面,各有种连接方式;模式有三个二义性面,有种连接方式; 模式有六个二义性面,有种连接方式。将以上模式加在一起,共有种不同 的连接方式,根据互补对称性和旋转对称性,同时限定体素的同一个面上不 能出现同 一个三角面片的两条边,这些模式可以简化为种。根据渐近线方法,模式、、 、和的体素内部等值面连接方式如图?所示,其中模式的连接方式与图 .中是对称的,这里不再给出。 画国◎画 两?薅霆 禽?画 图.渐近线方法判定面二义性的结果 算法 算法研究及在三维流体可视化模拟孛的巍用 第二章 按上述方法可以解决算法的面二义性问题,但是不能解决算法的体二义 性问题。本论文扩展渐近线方法来解决算法的体二义性问题。根据.节中体 二 义性问题的描述和上述的渐近线方法,可以将二义性体素中同时包含标号为 和标号 为的角点的体对角面看作是渐进线方法中的二义性面,则按着上述的处理可 以解决 算法的体二义性问题。在图.所示的种情况中只有模式存在体二义性, 有两种连接方式,如图.所示。 圈.扩展渐近线方法判定体:义性的结果 对于存在二义性的体素,按上述方法鳃决二义性问题,可以得到完全正确的结果。 与前面解决面二义性问题时的种模式含并,则最后得到种模式。采用这种 模式来建立算法所需的边查找表和三危形结构查找表,就麓解决算法的二义 性问题。因此,采用渐近线方法可以正确的解决算法的二义性问题,并且不会产 生太多的三焦面片,嚣丽是一季孛简洁丽高效的消除二义性的方法。 。。,移动四面体算法 移动四面体 算法简称为算法,它是在算法的基 础上发展起来的,是算法的改进算法。算法的基本原理是首先将立方体体素 剖分成多个四面体,然后在各四面体中构造等值面。 假设在四面体的边上,数据场呈线性变化,由予四面体的每个面都是三角形,生 成的等值面片的连接方式是唯一的,并且对于每个四面体,等值面模式只有三种情况, 如图所示。如果顶点数据值全大于或者全小于等值面阈值,则等值面与单元不 相交,如图所示;如果一个顶点大于而另外三个顶点小于等值面阈值,则 算法 算法研究及在三维流体可视化模拟中的应用 第二章 四面体中的等值面是一个三角面片,如图所示;如果两个顶点大于而另外两 个顶点小于等值面阈值,则等值面是一个四边形,可以由两个三角形构造,如图 所示。四面体内等值面的绘制步骤与算法一致。 图四面体中的等值面 在实际上,根据图中所建立的四面体中的等值面的构型,构造两个长度为 的查找表。一个记录所有情况下的等值面连接方式,即等值面与剖分四面体条棱的 交点,定义为边查找表。则以根据体素的顶点分类规则所得的数值为下标,查找边查 找表获得等值面连接方式,再连接等值点就形成等值面片。但由于需要以图形学方式 表达等值面片,而仅知道等值面与剖分四面体的交点,是无法确定其空间拓扑结构的, 因此通过另外一个表记录等值面连接方式对应的三角面片的边的组成,定义其为三角 形结构查找表,用来构造对应的三角化等值面。 常见的立方体剖分成四面体的方法有个,个和个四面体剖分法。然而, 个或个四面体的剖分是一种不对称的剖分,剖分后形成的四面体不全等。对于 个四面体的剖分,如图.所示,由于立方体体素两对面的剖分线不平行,则两个 相邻的立方体体素若采用相同的剖分方式,相邻体素的公共面上的剖分线相交,可能 出现裂缝,这无疑增加了处理的复杂性。为了避免在其公共面上出现裂缝,必须保证 在相邻体元的公共面上的剖分一致性因此考虑在一系列体素中使四面体剖分方式交 替变化,从而保证在相邻体素的公共面上的剖分一致性。虽然个四面体的剖分是 一种全等四面体的剖分,四面体的插值计算比较简单,却产生太多的三角面片,并且? 在立方体内的等值面没有二义性时,立方体也会被剖分处理,这都大大增加了算法的 时间耗费。面对庞大的数据,为达到实时交互的要求,减少计算和存储显得尤为重要, 尤其是近年来随着成像设备物理分辨率的不断提高,对可视化运算速度提出更高的要 求。虽然个四面体的剖分也是一种不对称的剖分,但是单个立方体体素对面上的剖 算法 算法研究及在三维流体可视化模拟中的应用 第二章 分线是平行的,则各体素采用相同的剖分方式,可以产生拓扑一致的等值面。 本文第 三、四章中的算法采用的是个四面体的剖分法,如图.所示。 图.立方体的个四面体剖分 图.立方体的个四面体剖分 算法流程如下: 将三维离散规则数据场分层读入,得到初始的体数据场; 在结构上对当前体素进行剖分,剖分成个四面体,各四面体顶点的连接 顺序为: ,,,, ,,,, ,,,, ,,,, ,,,, ,,, 对每个剖分四面体进行等值面的判定和绘制,与算法中单个体素的处 理相似,具体为: ?将当前剖分四面体的个顶点的函数值与给定的等值面阈值做比较,根 据比较结果,得到该剖分四面体的关键索三 ; ?根据该剖分四面体的关键索弓 ,查找使用的边查找表得出 该剖分四面体的等值面连接方式; ?通过线性插值方法计算出剖分四面体棱边与等值面的交点; 算法 算法研究及在三维流体可视化模拟中的应用 第二章 ?利用中心差分方法,求出四面体各顶点处的法向量,再通过线性插值方法, 求出三角面片各顶点处的法向向量; ?根据该剖分四面体的关键索引 ,查找使用的三角形结构 查找表得到该剖分四面体内的等值面的三角面片组成结构,同时根据各三角面片各顶 点的法向量,在一定的光照模型下绘制该剖分四面体内的等值面。 检测体数据场中的所有体素是否全部处理完毕,如否,则进行到下一个体 素,回到第步处理。如是,则体数据场中等值面的提取完毕,最后获得的等值 面即是所求等值面。 算法有很多优点。由于每个四面体,等值面模式只有三种情况,在进行四面 体剖分后,等值面在四面体中的剖分模式减少,算法实现简单。又由于四面体是最简 单的多面体,其他类型的多面体都能剖分为四面体,则在将立方体剖分为四面体后, 在四面体中构造的等值面较算法在立方体中构造的等值面精度高。其最大的优点 是通过在四面体内构造等值面可以避免算法中存在二义性问题。 虽然如此,算法也存在一些缺点。算法将立方体体素剖分成个、个 或个四面体,再抽取等值面,则同等体素数量下,算法会产生更多的三角面 片;与算法相比,提高了算法的时间复杂度。 .基于物理的流体模拟 基于物理的流体模拟的基本思想是:对于初始点,给出流体的速度和压力,然 后通过给出的纳维一斯托克斯方程来演化随时间推移的表示流体的各个量。 基于物理的流体模拟的方法主要分为两种:欧拉法和拉格朗日法。 .. 欧拉法 描述流体现象最为完整的为纳维一斯托克斯方程: , 该方程是根据牛顿第二定律推导出来的,详细资料可以参阅文献刀。下面给 出了常用 的不可压粘性方程组的欧拉形式, 质量方程: ?“ . 动量方程: . 。.:一.”一三跏 算法研究及在三维流体可视化模拟中的应用 算法 第二章 其中为密度,为压强,.厂为体积力,材为速度,为运动粘性系数,跟动力 粘性系数‖的关系是‖/户,为空间部分衍生的矢量,更准确的二维中为 /,/,三维中为/苏,/砂,/,同时采用速记符?。基于 网格的欧拉法即是将上述方程离散到网格上,然后计算各个固定网格节点上 状态量的 变化,从而来得到整个场。这里有两种思路进行网格化,一种是交错网格,即一般情 况下标量,如压强,分布在网格单元的中心,而速度之类的量分布在单元表面,这种 离散的好处是容易保证守恒性条件,目前多采用此思路;另一种思路则是所有的量都 处于同一个位置,这种方法简单,不需太多的插值运算,对各个变量也无不需区别对 待。 早期为了真实地描述流体的运动,引入浅水场方程求解高度场,通过采用隐式格 式构成三对角方程组,从而快速稳定地求解。采用高度场计算的好处就是整个模拟二 。 维化,避免了三维复杂耗时的计算,但是效果不尽理想 真正采用三维方程来模拟流体运动始自文献心们,其中利用 ’? 求解流体,但由于采用显式格式,时间步长必须满足条件 .. 以使整个计算收敛。文献乜妇采用半拉格朗日法求 解对流项,并结合隐式求解器,从而保证计算绝对稳定。自此,采用方程来模 拟 真三维的计算机动画越来越普遍。 ..拉格朗日法 而如果采用拉格朗日法这种非基于网格的方法,即基于粒子系统的方法,则 方程可以写为:告云一跏协 如果将右边整理成一个力,则退化为牛顿第二定律: /氕? 其中为粒子的加速度,%为粒子的速度,‖为粒子,受到的合力,肛为粒子 所在位置的密度。显然,该类方法就是对于各个相对独立的粒子进行力的分析,通 过积分计算出这些粒子下一个时刻的位置和其他状态量。 算法 算法研究及在三维流体可视化模拟中的应用 第二章 拉格朗日法方法的优点为容易表达,不需要对整个空间进行处理,不仅容易保证 质量守恒,而且比较容易实施控制。但拉格朗日法对于平滑运动界面的重建比较难处 理,而且自由界面拓扑的改变必须采用复杂的算法才能构造出该表面的几何,计算量 随着粒子数的增多而加大。 欧拉法和拉格朗日法各有优缺点,为了更真实地模拟流动,基于网格的欧拉 算法 往往结合拉格朗日的粒子算法一起使用,比如得到广泛应用的半拉格朗日算法瞳?,或 者用来对流体进行约束,从而加强交互控制。 .本章小结 本章对标准算法和基于物理的流体模拟的方法进行了研究。对于标准算 法的研究,首先研究了算法的原理和实现,然后分析了算法二义性问题,最 后讨论了两种比较经典的二义性解决方法一渐近线方法和算法。对于基于物理 的流体模拟的方法的研究,主要讨论了欧拉法和拉格朗日法,并比较了两种方法的优 缺点。算法磺究及在三缫漉锌霹筏他模蓣孛秘藏耀 第三章算法鹃一静改进 第三章算法的一种改进 本章提出了一种算法的改进算法一一基于五面体特征体元的分块逐层遍历 的抽取等值面的算法,根据标准和算法提出了五面体特征体元的等值面抽取 算法,分析了其二义性问题及解决方法,通过分块逐层遍历的算法来提高算法效率。 并在此基础上建立了一个以六面体为基础的五面体、四面体逐级细分的网格划分流程 与方法,形成了一个完整网格划分钵系。’ . 引言 在对标准算法和算法进行分析讨论的基础上,针对标准算法实现复杂 和二义性问题,以及算法产生太多三角面片的瞄题,提澎了基于五面体的剖分算 法,降低了算法的实现复杂度,同时采用分块逐层遍历的方法,’提高了算法的效率。 本章首先对移动五瑟体算法的基本原理、剖分方式、移动五面体算法的二义性及 其消除进行了研究,同时阐述了分块逐层遍历算法的基本思想。以此为依据,提出了 一个支持分块逐层遍历算法、以六面体为基础的五西体、四面体逐级细分的网格划分 流程与方法,形成了一个完整网格划分体系。最后将本文提出的算法与标准和 算法进行了比较分析。 算法 .移动五面体 .. 算法基本原理 由...节中介绍的移动四面体算法,它将一个立方体体素分成个面体, 这个四面体中的任意相邻的个四面体可以组成一个五面体,且它正好是该体素的 一半,其分界为立方体体素的一个对角面,由此,本文提出基于五面体特征体 元的等 值面提取算法??移动五面体算法。 算法简称为算法,基本原理是首先将立 移动五面体 方体体素剖分成多个五面体,然后在各五面体中构造等值面。通常将一个立方体体素 割分成个五面体,如图.所示。第三章算法的一种改进 算法研究及在三维流体可视化模拟中的应用 图立方体的五面体剖分 .. 算法等值面剖分方式的确定 假设在五面体的边上,数据场呈线性变化。首先对五面体特征体元的个顶点进 行分类,以判定该顶点是位于等值面之内还是等值面之外。再根据个顶点的状态, 确定等值面的剖分方式同算法。 假定等值面的阈值为,则顶点分类规则为: 如果五面体特征体元的顶点的数据场值?,则定义该顶点位于等值面之 外,标记“; 如果五面体特征体元的顶点的数据场值,则定义该顶点位于等值面之 内,标记“”。 由于每个五面体特征体元有个顶点,则如果让这个顶点的情况分别对应 位二进制数的相应位。按着上面的定义可以得到种不同的取值,分别为到 ,因此五面体特征体元与等值面相交的情况共有种组合状态。?根据互补对称性, 即体素的顶点标记置反变为】,变为,不影响该五面体特征体元内三角面片 的拓扑结构,这样种构型可以简化成种。再根据旋转对称性,可将这种构 型进一步简化成种。图.给出了这种基本构型的三角剖分,其中黑点表示标一 记为的角点。对于个角点的标记都为或者都为的体元,它属于“”号构型, 没有等值面穿过该体元。当只有一个角点标记为时,即“号构型,用一个三角 面片代表体元内的等值面片,它将该角点与其它个角点分成两部分。对于其余几种 构型,将产生多个三角面片。 算法研究及在三维流体可视化模拟中的应用 第三章算法的一种改进 圄嘭 ?国圃 ? 蹴 图五面体特征体元的分类 在实际上,根据图.中所建立的五面体特征体元的等值面的构型,构造两个长 度为的查找表。一个记录所有情况下的等值面连接方式,即等值面与五面体特征 体元条边的交点情况,称为边查找表。则以根据五面体特征体元的顶点分类规则所 得的数值为下标,查找边查找表获得等值面连接方式,再连接等值点就形成等值面片。 但由于需要以图形学方式表达等值面片,而仅知道等值面与五面体特征体元的交点, 是无法确定其空间拓扑结构的,因此通过另外一个表记录等值面连接方式对应的三角 面片的边的组成,称为三角形结构查找表,用来构造对应的三角化等值面。 五面体特征体元中等值面剖分方式确定的方法是:首先,对体数据场中当前五面 体特征体元的个顶点的函数值与等值面阂值比较,得到该五面体特征体元的关键 索引字节 。然后,根据关键索引字节 的值在五面体特征体 元的边查找表中找出对应的等值面连接方式用来计算等值面与体素的交点和等值面 各顶点的法向量,并且根据关键索引字节 的值在五面体特征体元的三角 形结构查找表中找出该体素对应三角剖分构型。 算法中另外两个主要的计算求等值面与体元边界的交点和三角面片各项点法 向量计算与..节中介绍的算法的对应计算一样,在这里不再描述。则算 法中一个立方体体素内的等值面的抽取算法,描述如下: 在结构上对当前体素进行剖分,剖分成个五面体特征体元,各五面体特 征体元顶点的连接顺序为: 第三章算法的一种改进 算法研究及在三维流体可视化模拟中的应用 ,,,,,, ,,,,, ; 对中剖分所得的个五面体特征体元分别进行等值面的判定和绘制, 与算法中单个体素的处理相似,具体为: ?将当前五面体特征体元的个顶点的函数值与给定的等值面阈值做比较, 根据比较结果,得到五面体特征体元的关键索弓 ; ?根据该五面体特征体元的关键索弓 ,查找使用的边查找表 得出该五面体特征体元的等值面连接方式; ?通过线性插值方法计算出五面体特征体元棱边与等值面的交点; ?利用中心差分方法,求出五面体特征体元各角点处的法向