王云霄硕士论文PDF.pdf

论文分类号 T P 3 1 单 位 代 码 1 0 1 8 3 密 级 内部 研 究 生 学 号 1 9 9 0 6 0 1 9 吉 林 大 学 硕 士 学 位 论 文 分形的计算机真实感绘制方法的研究 The Research of Computer Photorealistic Rendering Method of Fractal 作者姓名 王 云 霄 专 业 计算机应用技术 导师姓名 王 钲 旋 及 职 称 教 授 论文起止年月 2 0 0 0年 9月至 2 0 0 2年 5月 目 录 提 要 1 第一章 前 言 2 1 1 分形及其计算机生成 2 1 1 1 什么是分形 2 1 1 2 分形艺术图形 3 1 1 3 分形的计算机生成 4 1 2 计算机图形绘制技术 5 1 2 1 真实感图形绘制技术 5 1 2 2 非真实感图形绘制技术 6 1 3 绘制分形的真实感图形 7 1 4 本文做的主要工作 8 1 5 本文的结构 9 第二章 基于简单光照模型的分形真实感绘制技术1 0 2 1 简单光照模型 1 0 2 2 简单透明模型 1 2 2 3 图形变换 1 2 2 4 基于光照模型的真实感分形图生成 1 4 2 4 1 结合了深度排序的递归细分方法 1 4 2 4 2 基于逆映射的点序列法 1 6 2 4 3 实例分析 1 7 2 4 4 算法实现 2 0 2 5 基于简单绘画的真实感分形生成算法 2 6 2 6 实验结果分析 2 9 第三章 结合轨迹井的分形真实感绘制技术 3 1 3 1 复迭代及其复迭代的计算机绘制 3 1 3 2 牛顿迭代法以及改进的牛顿迭代法 3 3 3 3 调色板技术 3 7 3 4 自适应轨迹井技术 3 7 3 5 本文采用的轨迹井以及算法描述 3 8 3 5 1 算法描述 3 8 3 5 2 本文采用的几种轨迹井 3 9 3 6 实验结果 4 0 3 6 1 时间逃逸法生成 M 集真实感分形图 4 0 3 6 2 改进的牛顿迭代法生成真实感分形图 4 3 3 6 3 牛顿迭代法生成的 M 真实感分形图 4 6 3 6 4 对周期函数生成的真实感分形图的探讨 5 1 3 7 实验结果分析 5 2 第四章 结束语 5 4 参 考 文 献 5 5 致 谢 5 7 摘 要 I A b s t r a c t I V 分形的计算机真实感绘制方法的研究 1 提 要 本文着重于对分形的计算机真实感绘制方法的研究 主要从以下两 个方面进行了探索 1 首先利用分形的生成方法结合计算机图形绘制技术 对于2 3维之间的 分形进行了绘制 其中突破了以往的生成方法 提出了结合深度排序的 递归细分方法 解决了绘制2 3之间的一类分形时会遇到的隐藏面消除问 题 很好的解决了分形递归方法与真实感绘制技术结合的难题 同时结 合绘画方法近似模拟了光照效果 大大减少了计算量 生成了真实感效 果较好的分形图 2 探讨了复迭代的真实感分形绘制技术 提出了自适应轨迹井技术 本 文将分形生成方法与自适应轨迹井技术结合在一起对几类迭代函数式进 行了详细探讨 得出了一些结论 可以通过轨迹井来控制真实感分形的 生成形状 分析了参数的变化对于分形图的影响 同时对于牛顿迭代法 进行了改进 丰富了真实感分形艺术图形的生成种类 分形的计算机真实感绘制方法的研究 2 第一章 前 言 1 1 分形及其计算机生成 1 1 1什么是分形 分形 f r a c t a l 一词源于拉丁文f r a c t u s 本意是指 破碎的 产 生不规则碎片 分数 等 是法国数学家曼德布罗特 B B M a n d e l b r o t 于1 9 7 5 年最先创用的 曼德勃罗是想用此词来描述自然界中传统欧几里 德几何学所不能描述的一大类复杂无规则的几何对象 例如 弯弯曲曲 的海岸线 起伏不平的山脉 粗糙不堪的断面 变幻无常的浮云 九曲 回肠的河流 纵横交错的血管 令人眼花缭乱的满天繁星等 它们的特 点是极不规则或极不光滑 直观而粗略地说 这些对象都是分形 曼德勃罗曾经为分形下过两个定义 1 满足下式条件 Dim A dim A 的集合A 称为分形集 其中 Dim A 为集合A的Hausdoff维数 或 分维数 dim A 为其拓扑维数 点是0维 线是1维 面是2维 体是3 维 一般说来 Dim A 不是整数 而是分数 2 部分与整体以某种形式相似的形 称为分形 然而 经过理论和应用的检验 人们发现这两个定义很难包括分形 如此丰富的内容 实际上 对于什么是分形 到目前为止还不能给 出一个确切的定义 正如生物学中对 生命 也没有严格 明确的定义 一样 人们通常是列出生命体的一系列特性来加以说明 对分形的 定义也可同样的处理 i 分形集都具有任意小尺度下的比例细节 或者说它具有精细的 结构 ii 分形集不能用传统的几何语言来描述 它既不是满足某些条件 分形的计算机真实感绘制方法的研究 3 的点的轨迹 也不是某些简单方程的解集 或者说分形集是不规整的 iii 分形集具有某种自相似形式 可能是近似的自相似或者统计的 自相似 iv 一般地 分形集的 分形维数 严格大于它相应的拓扑维数 v 在大多数令人感兴趣的情形下 分形集由非常简单的方法确定 也可能由迭代过程产生 下面为两个简单分形的例子 S i e r p i n s k i 垫片和五角星分形 图1 1 S i e r p i n s k 垫片和五角星分形 1 1 2分形艺术图形 分形是无标度意义下 具有无穷细节的自相似的形 是无序和变幻 无穷的美的体现 利用分形的自相似性 可以构造出千变万化而又具有 任意高分辨率结构的艺术图案 是近年来受到广泛关注和感兴趣的艺术 形式 分形艺术图形的生成 在很大程度上取决于构图算法模型的建 立和构图原理与创作思维的综合运用 分形艺术图形不同于电脑绘画 它是严格意义上的纯数学的产物 所有的作品均符合线性或非线性分形的定义 作品创造者要有一定的数 学功底 也要有熟练的编程技能 科学依赖于分析 艺术凭借直觉 这 分形的计算机真实感绘制方法的研究 4 些优美的分形艺术作品本身是科学的理性和艺术的感受完美的融合 是 数学和艺术的统一 分形艺术图形所以能给人以极大艺术震撼 是因为它 的数学内涵与自然和人类存在的数学内涵高度和谐 分形艺术图形的生成与设计的基本原理 除了与普通艺术图形具有 相同的规律与法则之外 最突出的就是运用了分形的自相似性 在造 型或构图过程中引入递归或迭代 以及对局部过程的随机扰动 基本技 法包括 1 纹样的构成主要采用函数迭代和基于几何过程 或规则 的重复应 用算法 例如著名的 J u l i a 集 M a n d e l b r o t 集 由迭代函数系统 I F S 和 L 系统生成的具有分形纹样 以及由几何元素变换的重复迭代而成的抽象 分形纹样等 2 采用算法与人机交互相结合的着色技术 例如基于模除取余的分形矩阵着色 J u l i a 集和M a n d e l b r o t 集的周期 性色彩渲染 交互式颜色设置 灰度等级选择和调色板编辑等 3 画面布局采用传统与分形相结合的算法构图技术 例如整体分形构图 规则骨架构图和各种灵活多变的算法分布构图 等 1 1 3分形的计算机生成 分形的研究离不开计算机 如果不是计算机图形图像处理功能的增 强 不能想象怎样才能直观地看到J u l i a 集或M a n d e l b r o t 集的精细结构 如图1 2 中所示 更不能想象可以产生具有无限细节的自然景物和高度 真实感的三维动画 反过来 分形理论与方法又极大地丰富了计算机图 形学内容 甚至分形的思想会在计算机科学的发展产生一定的影响 分形的计算机真实感绘制方法的研究 5 图1 2 M a n d e l b r o t 集的例子 分形的计算机生成 有重大的应用价值 采用分形生成方法可以从 少量的数据生成复杂的自然景物图像 反之 从给定的自然景物图像提 取少量的数据形成原来的图像代码 在数据压缩方面也具有价值 用计算机生成分形图形有两方面的重要作用 一个是进行艺术创 作 生成新的一类分形艺术图形 另一个是进行科学探索 揭示分形本 身的结构和性质 1 2 计算机图形绘制技术 计算机图形绘制技术可以分为两大类 具有照相真实感图形绘制技 术与非照相真实感图形绘制技术 也简称为真实感绘制 P h o t o r e a l i s t i c R e n d e r i n g P R 与非真实感绘制 N o n p h o t o r e a l i s c t i R e n d e r i n g N P R 1 2 1真实感图形绘制技术 真实感图形绘制是计算机图形学的一个重要组成部分 他综合利用 数学 物理学 计算机科学和其他学科的知识在计算机图形设备上生成 像彩色照片那样的真实感图形 利用计算机绘制真实感图形有很大的实 用价值 例如在产品外形设计中 常需要制作实物模型来检查设计效果 实际应用中常需要不断修改设计方案 以获得最佳效果 这就需要反复 制作模型 浪费大量的人力物力 而采用计算机真实感图形绘制技术 就可以方便的在屏幕上显示产品各种角度的真实感视图并在屏幕上直接 对外形进行交互式修改 从而取代对实物模型的制作 这种技术大大节 分形的计算机真实感绘制方法的研究 6 约了人力物力 缩短设计周期 提高质量 除此之外 真实感图形绘制 技术在飞行训练战斗模拟 分子结构研究 医学 计算机动画以及影视 广告领域都有广阔的应用前景 真实感图形绘制追求绘制所得客观世界的场景具有照相机拍照所获 得的那种真实 也就是要在计算机中重现客观世界的真实场景 真实感 绘制是计算机图形学自产生以来一个重要的研究领域 经过长时间的发 展已经比较成熟 真实感绘制方法把场景看作是由光源 物体的形状和 材质所组成 给定视点和视线方向后 绘制过程就是利用绘制过程来刻 画光源 形状 材质和视点这四个成分之间的相互关系 如此来生成具 有真实感效果的图像 用计算机在图形设备上生成连续色调的真实感图形必须完成四个基 本任务 第一 用数学方法建立所构造的三维场景几何描述 并将它们输入计算 机 第二 将三维几何描述转换为二维透视图 通过透视变换来完成 第三 确定场景中的所有可见面使用隐藏面消除算法将其他物体遮挡的 不可见面消去 第四 计算场景中可见面的颜色 严格地说 就是根据基于光学物理的 光照模型计算可见面投射到观察者眼中的光亮度大小和色彩组 成 并将它转换成适合图形设备的颜色值 从而确定投影画面上 每一象素的颜色 最终生成图形 经过上述各个步骤 结合分形生成方法 可以生成真实感分形艺术图形 这是本文所做的工作的一部分 1 2 2非真实感图形绘制技术 非真实感图形绘制不是求生成场景具有照相获得的那种真实 而强调 人的接受 理解和赏析 强调满足人们利用可视形象达和传递信息的需 求 现有的非真实感绘制技术主要是模拟了美术创作的方法和美术效果 在计算机中生成了具有 油画 水彩画 钢笔素描 中国画 等不同 分形的计算机真实感绘制方法的研究 7 艺术风格的作品 已经在计算机绘画与动画等可用于广告宣传和影视艺术方面的应用 中起到了重要的作用 因此 文献中非真实感绘制也被称为表达性绘制 E x p r e s s i v e R e n d e r i n g 或具有艺术风格的绘制 R e n d e r i n g i n A r t i s t i c S t y l e s 非真实感绘制技术在最近十几年中特别受到重视 正在成为计算机 图形学中一个富有活力的新的重要研究领域 这里一个原因可能是因为 真实感绘制技术已经被考察的相当深入 但其中数据复杂 计算量大 操作者负担重 调整和修改困难等缺点仍难以克服 而非真实感绘制允 许在生成视觉效果达到满意的条件下简化绘制过程 另一个可能更重要 的原因 是随着计算机动画 科学计算可视化 虚拟现实 地理信息系 统 分形及其应用等新技术的出现 发现非真实感绘制具有广阔的应用 需求和发展前景 照相的真实感获得的是瞬间的凝固 虽然有广泛的用 途 但受到有限的观察视角的限制 具有较多无关的细节 可能不利于 重要信息的表达 需要进行默写视觉形象的抽象 分形也是一类非真实 感图形 真实感分形是嵌入到三维空间中的有立体真实感的分形 考察 如何绘制真实感分形至少有两方面的用途 一个是进行艺术创作 生成 新的一类分形艺术图形 另一个是进行科学探索 揭示分形本身的结构 和性质 怎样在二维的显示平面上绘制维数不是整数 并且一般维数超 过1 的真实感分形 提出了非真实感绘制技术应该解决的新问题 这也是 本文所做的工作的一部分 1 3 绘制分形的真实感图形 用计算机生成二维平面上的分形艺术图形及研究平面分形图形的结 构已经被人们所熟悉 这自然地引出了绘制在三维空间中的真实感艺术 图形以及在二维空间中近似模拟出类似于三维空间中的分形图效果这一 研究问题 这就是我们要做的主要工作的两个具体方面 其中三维空间 中的真实感分形应该具有三维实体的立体感 通过加入视线 光照等引起 的效果 即采用上述的真实感绘制技术 在此基础之上我们亦想寻找另 分形的计算机真实感绘制方法的研究 8 外一种方法 来近似模拟这种真实感绘制技术产生的效果 以减少计算 量 加快绘制过程 经过实验发现 后一种方法亦生成了效果很好的真 实感分形图 而对于二维空间中的分形图生成 我们亦想找到简单方法 来生成拟3D效果的一类新的真实感分形图形 即我们这里所述的真实感 分形图形绘制技术即包括了上述的真实感绘制技术同时也包括了非真实 感绘制技术 考察如何绘制真实感分形至少有两方面的用途 一个是进行艺术创 作 生成新的一类分形艺术图形 另一个是丰富真实感图形学生成方法 目前各种分形文献不少 但大部分都是对分形基本思想的简单阐述 同时举一些简单的例子来说明 而真正介绍真实感分形绘制技术的资料 并不多 其中对于高于二维的真实感分形绘制大部分采用O p e n G L 或者借 助于其它的绘图工具来绘制 而我们的目标是不借助绘图工具而寻找相 对简便快捷的绘图方法 而对于低于二维的真实感绘制方式的文献主要 有调色板技术和P a u l W C a r l s o n 提出的轨迹井跟踪绘制 o r b i t t r a p t r a c i n g 技术 1 4 本文做的主要工作 本文主要实现了以下两个方面的主要工作 1 对于高于二维的分形图形的真实感绘制技术的研究 我们采用了基于简单光照模型的真实感图形生成技术 采用结合深 度排序的递归细分方法很好地解决了在分形绘制过程中通常会遇到的消 除隐藏面的问题 有效的将递归细分过程和真实感绘制技术结合在了一 起 保持了递归算法的简便性 本文对于具体的实例进行了绘制 生成 了效果极好的 形象逼真的分形图像 采用基于非真实感图形绘制技术 近似模拟分形图形的光照效果 我们可以颜色设定为和物体与视点的距 离相关的一个变量 距离越大 设定的颜色越深 采用这种绘制方法大大 减少了光照的计算量 快速的生成了拟三维真实感分形图形 2 对于1 2 维的分形图形的真实感绘制技术的研究 探讨了复迭代的真实感分形绘制技术 提出了自适应轨迹井技术 本 分形的计算机真实感绘制方法的研究 9 文将分形生成方法与自适应轨迹井技术结合对几类迭代函数式进行了详 细探讨 得出了一些结论 可以通过轨迹井的形状来控制真实感分形的 生成形状 分析了参数的变化对于分形图的影响 同时对于牛顿迭代法 进行了改进 丰富了真实感分形艺术图形的生成种类 1 5 本文的结构 本文共分为四章 第一章 前言 介绍了分形以及图形学绘制技术 同时还介绍了本文的主要工作和意义 第二章 基于简单光照模型的分 形真实感绘制技术 主要介绍了结合了深度排序的递归算法 应用此算法 结合其它的绘制技术对于维数在 2 3 之间的真实感分形的绘制进行了详 细探讨 第三章 结合轨迹井技术的分形真实感绘制技术 主要介绍本文 提出的自适应轨迹井技术 同时结合分形生成方法 对具体的迭代函数进 行了研究 第四章 结束语 对本文的主要内容进行了总结 分析了本文中 存在的不足 同时对所研究内容的前景做了讨论 分形的计算机真实感绘制方法的研究 10 第二章 基于简单光照模型的分形真实感绘制技术 2 1 简单光照模型 简单光照模型模拟物体表面对光的反射作用 假定光源为点光源 反射作用被细分为镜面反射 S p e c u l a r R e f l e c t i o n 漫反射 D i f f u s e R e f l e c t i o n 简单光照明模型只考虑物体对直接光照的反射作用 而物 体间的光反射作用 只用环境光 A m b i e n t L i g h t 来表示 P h o n g 光照模 型就是这样的一种模型 下面我们分别从光反射作用的各个组成部分来 简单介绍一下这个光照明模型 泛光也称为环境光 是指光源对物体的间接影响 是在物体和环境 之间多次反射 最终达到平衡时的一种光 我们近似地认为同一环境下 的环境光 其光强分布是均匀的 即它在任何一个方向上的分布都相同 例如 透过厚厚云层的阳光就可以称为环境光 在简单光照明模型中 我们用一个常数来模拟环境光 用式子表示为 aae IKI 其中 Ka为物体对泛光的反射系数 与物体表面性质有关 Ia为入射的泛光的光强 与环境的明暗度有关 漫反射光的空间分布也是均匀的 但是反射光强与入射光的入射角 的余弦成正比 这就是 Lambert 余弦定理 公式表示为 cos IK I ld 其中 Kd是漫反射系数 率 与物体表面性质有关 Il是入射光源的 光强 是入射光与物体表面法向量之间的夹角 若物体表面在照射点P处的单位法向量为N P到点光源的单位向量为L 则上式可表达为如下的向量形式 LN IK I ld 分析 1 当入射角大于 2 时 光源位于物体背后 光亮度为 0 分形的计算机真实感绘制方法的研究 11 2 当入射角为 0 时 光源垂直照射在物体表面上 反射光强度最大 3 材料的漫反射率不同 相同入射角照射不同材料时会出现不同的 颜色 在实际中 从周围环境投射来的环境光或泛光也会有相当的影响 这样 Lambert 漫反射光照明模型可写为 LN IKIK I ldaa 图 2 1 Lambert 漫反射光照明模型 根据光的反射定律 反射光线和入射光线对称地分布于表面法向量 的两侧 对于一般的物体表面 由于表面实际上是由许多不同朝向的微 小平面组成 镜面反射光将分布于表面镜面反射方向的周围 在实际应 用时 常做适当的简化 对于较光滑的表面 在视点所见的反射光光强 随着视线与反射方向的夹角的增加而减少的现象 即对于同一点来说 从不同位置所观察到的镜面反射光强是不同的 P h o n g 提出一个计算镜面反射光亮度的经验模型 公式表示为 2 0 cos n sls KII其中 K s 是与物体有关的镜面反 射系数 与入射角和波长有关 n 为镜面高光系数 用来模拟镜面反射 光在空间中的会聚程度 是视线方向 V 与反射方向 R 的夹角 cos n 近 似描述了镜面反射光的空间分布 Phong 光照模型与 Lambert 漫反射模型结合可得到在单一光源照射下的 Phong 光照明模型表达式 cos cos n sldlaaKIKIKI I 当用上述光照明模型来计算每点处的光亮度时 需分别对红 绿 蓝三 分形的计算机真实感绘制方法的研究 12 色进行计算 本文后面的绘制工作采用此模型 2 2 简单透明模型 透明物体不仅反射光也透射光 具体应用时 均不考虑折射 物体 表面总的光强度可表示为 I K I KI 21 1 其中 K 是透明系数 I1 透射强度 I2 为反射强度 设 t 是物体的透明度 t 0 表示物体是不透明体 t 1 表示物体是 完全透体 我们可以看到物体后面的背景和其他物体 这些物体的前后 位置可以通过隐藏面消除算法计算出来 实际上 我们最终所看到的颜 色 是物体表面的颜色和透过物体的背景颜色的叠加 设过象素点 x y 的视线与物体相交处的颜色 或光强 为 Ia 视线穿过物体与另一物体 相交处的颜色 或光强 为 Ib 则象素点 x y 的颜色 或光强 可由如下 颜色调和公式计算 ab IttII 1 其中 ba II 和可由简单光照明模型计算 由于未考虑透射光的折射 以 及透明物体的厚度 颜色调和法只能模拟玻璃的透明或半透明效果 2 3 图形变换 三维场景作为一个空间场景 就必然要有一个确定位置 大小的坐 标系 以便于进行三维场景造型 三维场景的定义和图形的输入输出都 是在一定的坐标系下进行的 坐标系描述了场景的形状 几何数据以及 拓扑信息 在计算机图形学中 为了通过显示设备来考察几何物体的特 性 引入了一系列用于显示输出的坐标系统来组成不同的视图系统 viewing system 世界坐标系 用户在定义场景时用到的坐标系统称为用户坐标系 也 称为世界坐标系 它用来定义空间中场景的几何信息以及拓扑信息 计算 分形的计算机真实感绘制方法的研究 13 机图形系统中涉及的其它坐标系统都是参照它进行定义 观察坐标系 V i e w i n g c o o r d i n a t e s y s t e m s 用户观察区定义的坐标 系统就是观察坐标系 观察坐标系通常是以视点的位置为原点 通过用 户指定的一个向上的观察向量 view up vector 来定义整个坐标系统 缺省 为左手坐标系 观察坐标系主要用于从观察者的角度对整个世界坐标系 内的对象进行重新定位和描述 从而简化几何物体在投影面的成像的数 学推导和计算 视平面 v i e w p l a n e 坐标系统 它是一个二维坐标系统 主要用于 指定物体在成像面上的所有点 往往是通过指定成像面与视点之间的距 离来定义成像面 成像面有时也称投影面 可进一步在投影面上定义称 为窗口的方形区域来实现部分成像 设备坐标系 生成的真实感图形需要在计算机显示器屏幕上显示出 来 它也有一个自己的坐标系统 称为设备坐标系 也叫屏幕坐标系或 显示坐标系 在进行真实感图形绘制时 各坐标系之间的关系需要进行 变换 才能正确的完成真实感图形的绘制 下列流程图表示了三维图形变换的流程图 图 2 2 三维图形变换过程 1 其中用户坐标系到观察坐标系采用的变换矩阵为 假定视点为 x0 y0 z0 用户坐标系下的一点为 www zyx 观察 坐标系下的一点为 eee zyx 设定 2 0 2 0 2 0 zyxu 2 0 2 0 yxv 分形的计算机真实感绘制方法的研究 14 变换矩阵为 100 0 0 0 0 0 0000 0000 u uzuv uyuvzyvx uxuvzxvy V 2 经过一点透视投影变换 投影到视平面上 假定 s z 为视点离视平面的距离 透视投影矩阵为 0000 1100 0010 0001 s z eses zzxx eses zzyy ss zz 3 经过简单的几何变换将视平面坐标转变为设备坐标 4 在屏幕上显示几何体 2 4 基于光照模型的真实感分形图生成 2 4 1结合了深度排序的递归细分方法 分形的计算机生成和图形绘制问题受到广泛重视 在众多的生成方 法中经常用的是递归细分的方法 这一方法依据分形所具有的整体与局 部间某种自相似性 实施一个可以任意深入的递归细分过程 许多分形 维数小于 2 的分形图形的生成和显示问题用此方法得到很好的解决 注 意到对于分形维数在 2 到 3 之间的一类分形用此方法时 可能会出现所 生成各子分形体彼此间互相遮挡而需要消除隐藏面 或者为观察内部结 构而希望绘制分形剖切面 本文据此提出了一个解决的方法是与递归细 分过程同步地做相对观察位置的深度排序 按照排序结果适当的处理后 再做接下去的递归细分过程 后面详细描述这一方法的实现算法 并给 出了较多的有代表性的实例 分形的计算机真实感绘制方法的研究 15 通常使用的基本的递归细分过程是对给出的初始形体 S 按照生成 规则操作将其细分为 m个子形体 A1 A2 Am 对每个部分形体再继 续做相同的操作 分形被认为是递归细分过程无限继续而得到的极限图 形 实用中自然地应事先指定一个适当地递归细分实行次数 iter 于是基 本地分形递归细分过程可概括为如下算法 Fractal1 S iter if iter 0 绘制 S 的图形 return 按照指定的生成规则操作将 S 细分为 m个子分形体 A1 A2 Am for i 1 i m i Fractal1 Ai iter 1 而对于分形维数在 2 到 3 之间的分形 为表现形体的空间深度 可选用 透视投影方法 为此应给出透视投影中心或观察位置点 P 将一个深度 排序过程结合到上述算法中 得到如下改进的算法 Fractal2 P S iter if iter 0 绘制相对观察位置 P 的 S 的透视投影图形 Return 按生成规则操作将 S 细分为 m个子分形体 A1 A2 Am 对 A1 A2 Am 按一定规则做深度排序得到序列 m BBBB 321 if 有剖切要求 按剖切要求进行调整得到序列 321m CCCC for i 1 i m i Fractal2 P Ci iter 1 对于上述算法的深度可以简单的选取 可求出各部分分形体 A1 A2 Am按某种度量的中心位置 O1 O2 Om 对 1 i m 就取 Oi到观察 位置 P 的距离为形体 Ai的深度 实用中为简便可用该距离的平方作为深 度 按照该数值递减排序 如果有剖切要求 进行调整要把应该剖切掉 的部分去掉或者按要求平移到另外的适当位置 剖切要求任意给出 对 分形的计算机真实感绘制方法的研究 16 按深度排序后的各部分形体 可按其中心位置来确定它们关于剖切平面 的相对位置 由此确定是否属于应被去掉或应被平移的部分 该处理方法所做的处理并不复杂 但实践表明一般都能够做到对递归 细分实行任意次数 使隐藏面被可见面正确覆盖 使这类分形能够取得 清晰合理的图形显示效果 显然 这里给出的算法是通用的 在对众多的 不同分形做实际处理时可能会遇到不同的复杂情况 如何针对不同情况 实现递归细分和深度排序 可能还需要克服不同的实际困难 下节我们 将对具体的实例进行详细分析 显示形体时采用逐个面显示 将每一个 面投影到投影平面上 之后扫描投影平面上的每一个点 通过逆映射求 出对应分形体上的点 之后计算光照将该点显示出来 这样就实现了子 形体的显示 2 4 2基于逆映射的点序列法 上述算法采用由远到近地显示动态显示物体 用简便的方法解决了 绘制分形图很难解决地消隐问题 下面我们再介绍本文提出的另外一种 方法 我们称之为基于逆映射的点序列消隐方法 这种方法我们扫描投 影区域中的每一个象素点 通过计算每一个象素点与视点的连线来求得 一个位于物体上的点序列 按照离视点的距离由小到大进行排序 每一 个象素对应的点列中第一个点始终保持为离视点最近的点 即我们要显 示在屏幕上的点 在递归过程中动态对点数组进行操作 递归完成之后 点的存储过程结束 再调用显示算法 将存储在每一个点列中的第一个 点即离视点最近的点显示出来 直至显示出整个分形体 算法描述如下 1 Fractal1 S iter if iter 0 存储点序列 return 按照指定的生成规则操作将 S 细分为 m个子分形体 A1 A2 Am for i 1 i m i Fractal1 Ai iter 1 分形的计算机真实感绘制方法的研究 17 2 读取点序列中的数据进行绘制 经过实验证明 这两种算法实现起来都不复杂 并且对于任意 2 3 维之间的分形图都能很好的解决消隐问题 下面我们将针对具体的实例 给出了详细介绍 并给出了部分实现代码 2 4 3实例分析 实例 选用不同的初始形体和不同的细分生成规则能得到不同的分形图 形 一些具体实例如下 例 1 初始形体 S 选为一个正方体 细分生成规则是每边 n等分 用过分点 平行于各表面的平面将原正方体细分为 m n3个小正方体 适当地舍弃一 些并对剩下地继续实行相同的操作 通过对每边等分数以及舍弃哪些小 正方体做不同的选择 可以得到一类分形图形 如果选取 n 3 舍弃的 是原正方体中心处以及六个表面中心处共七个小正方体 就得到熟知的 Sierpinski海绵分形 对于这个分形结合简单的光照模型可得到真实感效 果的分形 下图分别采用前面介绍的两种算法实现 分形的计算机真实感绘制方法的研究 18 图 2 3 Sierpinski 海绵分形 例 2 初始形体选为一个正四面体 每边 n 等分后 为简便可以只考虑得到 的如图所示的小正四面体 这是实现递归细分需要的坐标计算及生成的 部分形体的编号都不像处理正方体时那么简单 一个好的解决方案是采 用重心坐标 通过对每边等分数及舍弃哪些小正四面体做不同的选择 可 以得到一类分形图形 例如取 n 2 初始正四面体的一次细分情形以及涉 及各顶点的重心坐标已在图上标出 让这个细分过程继续进行 细分所得 各小正四面体均不舍弃 则可以得到的分形图形的显示效果如图 易见这 是平面上 S i e r p i n s k i 三角形向空间推广的一种情形 下图为采用两个正 四面体生成 好像水晶体一样 分形的计算机真实感绘制方法的研究 19 图 2 4 宝石 图 2 5 球状空间 S i e r p i n s k i 为了进一步丰富真实感分形艺术图形的生成 我们采用一个一个的 小球来构成正四面体的各边 结合光照模型 生成了如下的分形 其中 我们采用了三个点光源来生成光照效果 生成的分形图如2 4 所示 同时 我们将例一和例二结合在一起 绘制了两个形体交叉和包含的情形 其 中我们结合了光照模型和透明模型 生成的分形图如2 5 所示 分形的计算机真实感绘制方法的研究 20 图2 6 交叉体 2 4 4算法实现 1 基于深度排序的递归细分方法 以 Sierpinski海绵分形为例 给出了部分实现源码 v o i d S i e r p i n s k i C D C p D C O b j e c t C u b e i n t i t e r i f i t e r 0 d r a w F a c e r e t u r n 对剩余的 2 0 个立方体按照与视点的远近进行排序 C u b e 0 1 C u b e 0 2 C u b e 0 3 C u b e 0 2 0 f o r i 1 i 2 0 i S i e r p i n s k i p D C C u b e 0 i i t e r 1 分形的计算机真实感绘制方法的研究 21 v o i d d r a w F a c e C D C p D C P O I N T 3 p 0 P O I N T 3 p 1 P O I N T 3 p 2 P O I N T 3 p 3 P O I N T 3 p w 1 p w 2 p w 3 p w 4 p e 1 p e 2 p e 3 p e 4 p w 1 p 0 p w 2 p 1 p w 3 p 2 p w 4 p 3 p e 1 m t r a n T r a n s t o E y e p w 1 p e 2 m t r a n T r a n s t o E y e p w 2 p e 3 m t r a n T r a n s t o E y e p w 3 p e 4 m t r a n T r a n s t o E y e p w 4 0 d o u b l e N 1 N 2 N 3 N o r m a l p 0 p 1 p 2 N 1 N 2 N 3 d o u b l e x 1 x 2 y 1 y 2 P O I N T 3 q e 1 q e 2 q e 3 q e 4 q e 1 m t r a n P r o t o E y e W i n d o w p e 1 q e 2 m t r a n P r o t o E y e W i n d o w p e 2 q e 3 m t r a n P r o t o E y e W i n d o w p e 3 q e 4 m t r a n P r o t o E y e W i n d o w p e 4 x 1 M i n P o i n t q e 1 x q e 2 x q e 3 x q e 4 x x 2 M a x P o i n t q e 1 x q e 2 x q e 3 x q e 4 x y 1 M i n P o i n t q e 1 y q e 2 y q e 3 y q e 4 y y 2 M a x P o i n t q e 1 y q e 2 y q e 3 y q e 4 y i n t s t e p s t e p 1 f o r i n t x i n t x 1 x i n t x 2 x s t e p f o r i n t y i n t y 1 y S e t P i x e l i n t p p e x 2 0 0 i n t p p e y c o l o r 2 基于逆映射的点序列法 分形的计算机真实感绘制方法的研究 23 以初始形体为正四面体生成的分形为例给出了部分实现源码 v o i d t e t r a h e d r o n C D C p D C P O I N T 3 p 0 P O I N T 3 p 1 P O I N T 3 p 2 P O I N T 3 p 3 i n t i t e r i f i t e r 0 点序列建立过程 f a c e p D C p 0 p 2 p 1 t r i a n g l e f a c e p D C p 1 p 2 p 3 t r i a n g l e f a c e p D C p 0 p 3 p 2 t r i a n g l e f a c e p D C p 0 p 1 p 3 t r i a n g l e r e t u r n P O I N T 3 p m 0 1 p m 1 2 p m 2 0 p m 3 0 p m 3 1 p m 3 2 p m 0 1 M i d P o i n t p 0 p 1 p m 1 2 M i d P o i n t p 1 p 2 p m 2 0 M i d P o i n t p 2 p 0 p m 3 0 M i d P o i n t p 3 p 0 p m 3 1 M i d P o i n t p 3 p 1 p m 3 2 M i d P o i n t p 3 p 2 t e t r a h e d r o n p D C p m 3 0 p m 3 1 p m 3 2 p 3 i t e r 1 t e t r a h e d r o n p D C p m 0 1 p 1 p m 1 2 p m 3 1 i t e r 1 t e t r a h e d r o n p D C p m 2 0 p m 1 2 p 2 p m 3 2 i t e r 1 t e t r a h e d r o n p D C p 0 p m 0 1 p m 2 0 p m 3 0 i t e r 1 v o i d f a c e C D C p D C P O I N T 3 p 0 P O I N T 3 p 1 P O I N T 3 p 2 P O I N T 3 p w 1 p w 2 p w 3 p e 1 p e 2 p e 3 p w 1 p 0 p w 2 p 1 p w 3 p 2 p e 1 m t r a n T r a n s t o E y e p w 1 分形的计算机真实感绘制方法的研究 24 p e 2 m t r a n T r a n s t o E y e p w 2 p e 3 m t r a n T r a n s t o E y e p w 3 d o u b l e N 1 N 2 N 3 N o r m a l p 0 p 1 p 2 N 1 N 2 N 3 d o u b l e x 1 x 2 y 1 y 2 P O I N T 3 q e 1 q e 2 q e 3 q e 1 m t r a n P r o t o E y e W i n d o w p e 1 q e 2 m t r a n P r o t o E y e W i n d o w p e 2 q e 3 m t r a n P r o t o E y e W i n d o w p e 3 x 1 M i n P o i n t 1 q e 1 x q e 2 x q e 3 x x 2 M a x P o i n t 1 q e 1 x q e 2 x q e 3 x y 1 M i n P o i n t 1 q e 1 y q e 2 y q e 3 y y 2 M a x P o i n t 1 q e 1 y q e 2 y q e 3 y i n t s t e p s t e p 1 f o r i n t x i n t x 1 x i n t x 2 x s t e p f o r i n t y i n t y 1 y R 结束该点迭代 为该点赋予一定的颜色 否则进一步判断 n K 转到 S t e p 4 否则结束该点迭代 3 5 2本文采用的几种轨迹井 轨迹井 1 轨迹井 2 轨迹井 3 轨迹井 4 分形的计算机真实感绘制方法的研究 40 3 6 实验结果 3 6 1时间逃逸法生成 M集真实感分形图 采 用 自 适 应 轨 迹 井 技 术 对 参 数 平 面 上 的 具 体 的 复 映 射 czzf w 进行了真实感效果分形图形的生成 我们结合自适应轨迹 井跟踪技术 生成了真实感的分形图象 使生成的分形图象更加逼真 丰富多彩 图 3 1 迭代函数采用czzf 3 w 为整数 c 为复数 迭代区域 x m i n y m i n 2 5 y m i n y m a x 2 5 四个井的位置分别为 井 1 12 x 井 2 21 x 井 3 12 y 井 4 21 y 图 3 1 左边的图为采用轨迹井技术生成的 右图为用改进的轨迹井技术生成的 图 3 2 迭代函数采用czzf 3 w 为整数 c 为复数 迭代区域 x m i n y m i n 2 5 y m i n y m a x 2 5 两个井的位置分别为 井 1 11 xy 井 2 11 xy 分形的计算机真实感绘制方法的研究 41 图 3 2 左边的图采用原轨迹井技术生成 右边的图采用改进了的轨迹井技 术生成 上面两个例子均是对于条形轨迹井来说的 由这两个例子我们可以 看出 改进了的轨迹井跟踪技术能生成效果很好的真实感分形艺术图形 并且它能很好的控制分形的形状 图 3 3 为 迭代函数采用czzf w w 为整数 c 为复数 迭代区域 x m i n y m i n 3 y m i n y m a x 3 两个井的位置分别为 井 1 5 1 5 1 22 yx 井 2 5 1 5 1 22 yx w 3 图 3 3 w 5 图 3 4 为 迭代函数采用czzf w w 为整数 c 为复数 迭代区域 x m i n y m i n 4 y m i n y m a x 4 四个井的位置分别为 分形的计算机真实感绘制方法的研究 42 井 1 222 5 1 5 1 5 1 yx 井 2 222 5 1 5 1 5 1 yx 井 3 222 5 1 5 1 5 1 yx 井 4 222 5 1 5 1 5 1 yx w 3 图 3 4 w 5 上图分别为 w 3 w 5 时生成的 M 分形图 图 3 5 图 3 5是在图 3 4右图的基础之上生成的 左边的图采用将井的半径 由 1 5调节为 2 0的情形 图中显示的区域也随着放大 右面的图迭代 区域由x m i n y m i n 4 y m i n y m a x 4 缩为 x m i n y m i n 3 x m a x y m a x 3 显示的井的区域也随之放大 随着轨迹井半径的增大 显示的轨迹井的区域逐渐向边缘靠拢 中 心体现分形性质的部分逐渐增大 越来越清晰的呈现在面前 迭代区域 逐渐缩小时回出现同样的结果 由以上得实验结果以及大量的实验我们发现 对于czzf w w 分形的计算机真实感绘制方法的研究 43 为整数 c 为复数 我们可以通过轨迹井的设定来控制生成分形的形状 当幂指数以及井半径和迭代区域发生变化时 生成的真实感分形图的影 响并不大 而轨迹井始终在分形图形中得到清晰体现 无论采用什么方 式 w 正整数时 图像具有 w 1 个主花瓣 w 为负整数时 图像具有 w 1 个主花瓣 各主花瓣呈圆周均匀分布 这个特性在我们生成的图形中得 到了具体体现 3 6 2改进的牛顿迭代法生成真实感分形图 对于方程 0 czzF w 采用牛顿迭代法生成的分形种类单一 就象前节我们介绍的那样 对于参数 C的变化 只是分形发生了一定角 度的变化或者对局部的放缩 而整个分形的整体特征没发生什么变化 这样生成的分形结构比较单一 图 3 6 为采用轨迹井 1 1 4 zzF 应用牛顿迭代法 生成的 J u l i a 分形链 迭代区域 x m i n y m i n 1 y m i n y m a x 1 四个井的位置分别为 井 1 13 x 井 2 31 x 井 3 13 y 井 4 31 y 图 3 7 所取的参数和图六完全相同 采用牛顿改进式 3 生成 对牛顿 式进行分式线性映射 仍保持了原来 n向对称性 这里所生成的图形均 是按迭代式的自身规律生成 缺少外部控制参数对分形的控制 图 3 6 图 3 7 图 3 8 采用式 6 其中参数和图六相同 参数2 1 分形的计算机真实感绘制方法的研究 44 图 3 8 图 3 9 图 3 9 采用式 6 基本参数和图六相同 外部控制参数为2 1 通过轨迹井的介入以及两个外部控制参数 可以适当的调节真实感分形 图的效果 极大的丰富了生成的真实感分形艺术图形的种类 对于分形 分形的计算机真实感绘制方法的研究 45 艺术创作有一定的意义 图 3 1 0 式 7 生成 其中2 1 分形的计算机真实感绘制方法的研究 46 图 3 1 0 图 3 1 0采用牛顿改进式 7 采用不同的轨迹井生成的真实感分形艺术图 形 由以上图可见采用改进了的牛顿迭代法通过两个外部控制参数再加上轨 迹井本身的调节与控制可生成较好的真实感分形艺术图形 极大的丰富 了生成分形图形的种类 3 6 3牛顿迭代法生成的 M真实感分形图 R i n g S e g m e n t s M e t h o d 的改进方法 分形的计算机真实感绘制方法的研究 47 图 3 1 1 井描述 图中所示为第一象限的轨迹井 设定八个环片段作为轨迹井 迭代过程中我们选取每一个落入井中的点到中轴弧的距离与弧宽度 T的 一半的比值作为 R a t i o值 这样能保证生成的真实感分形图具有较好的 效果 采用牛顿迭代