计算机图形学教程（第5版 微课版）课件 第7、8章 自然景物模拟与分形艺术、真实感图形显示

第7章自然景物模拟玉芬性艺术哈尔滨工业大学计算机学院苏小红2什么是分形？（1/21）著名理论物理学家约翰·惠勒(J.Wheeler)说过：在过去，一个人如果不懂得熵是怎么回事，就不能说是科学上有教养的人；在将来，一个人如果不能同样熟悉分形，他就不能被认为是科学上的文化人。哈尔滨工业大学计算机学院苏小红3什么是分形？（2/21）非线性科学(nonlinearscience)中最重要的三个概念混沌(chaos,也译作“浑沌”)分形(Fractal)孤子(soliton，也称“孤波”(solitarywave))分形理论是非线性科学研究领域中一个十分活跃的分支本质是一种新的世界观和方法论揭示了有序与无序的统一，确定性与随机性的统一被认为是科学领域中继相对论、量子力学之后，人类认识和改造世界的最富有创造性的第三次革命哈尔滨工业大学计算机学院苏小红4第一个分形例子由文艺复兴时期德国著名画家丢勒(AlbertDurer，1471-1528)

(“杜勒”)给出什么是分形？（3/21）D=log5/log(3+SQRT(5)/2)=1.672艺术创作特点：精细，讲究科学和数学与其父精于金银细工有关与文艺复兴时期重视自然科学和数学的时代风气也有关丢勒正五边形分形哈尔滨工业大学计算机学院苏小红5什么是分形？（4/21）1827年，英国植物学家R.Brown（1773-1858）用显微镜发现微细颗粒在液体中作无规则行走，此现象被称为布朗运动。后来科学家对布朗运动进行了多方面的研究，维纳(N.Wiener，1894-1964)等人在此基础上创立随机过程理论。进入80年代，人们以分形的眼光看待布朗运动，并与“Levyflight”相联系，找到了确定论与随机论的内在联系。

哈尔滨工业大学计算机学院苏小红6什么是分形？（5/21）学过微积分的人都知道，函数的可微(即可求导数)性与连续性有内在联系。两者的关系是可微的函数必定连续，但连续的函数未必可微。一个简单的例子就是函数y=｜x｜在x=0处连续，但不可微。有的函数在有限个点处是不可微的，也有更特别的函数，它们几乎处处不可微。

哈尔滨工业大学计算机学院苏小红7什么是分形？（6/21）1860年，瑞士一个名气不算大的数学家C.Cellerer(1818-1889)在课堂上讲：“连续函数必定可微”的流行观念是错误的，并给出一个类似维尔斯特拉斯(K.T.W.Weierstrass,1815-1897)函数的反例1970年有人证明，Cellerer函数不同于维尔斯特拉斯函数，它们不是处处不可微的，在某些点上它们是有导数的。

哈尔滨工业大学计算机学院苏小红8什么是分形？（7/21）1872年，维尔斯特拉斯向柏林科学院报告了分析学中的一个反例——一个处处连续、但处处不可微的三角函数级数，即著名的维尔斯特拉斯函数。不过此函数直到1875年才由杜布瓦-雷蒙(E.duBois-Reymond)正式发表出来。在维尔斯特拉斯之前，已有不少数学家知道存在所谓的“维尔斯特拉斯函数”，但都耻于发表它!因为它破坏了分析学的完美性。

哈尔滨工业大学计算机学院苏小红9什么是分形？（8/21）1883年，G.F.P.Cantor(1845-1918)构造了三分集与实直线相对立被认为是病态的如今它已成为分形几何学的最典型、最简单的模型每次去掉线段中间的1/3最后剩下的就是Cantorset为了显示方便，无宽度的［0,1］线段在这里故意用一矩形框表示Cantor三分集的生成过程D=log2/log3=0.6309哈尔滨工业大学计算机学院苏小红10什么是分形？（9/21）从什么是曲线谈起直观上有长无宽的线叫曲线。但这不是定义，甚至矛盾

1890年，意大利数学家G.Peano构造了一种奇怪的曲线能够通过正方形内的所有点，有面积令数学界吃惊Peano曲线(前四步)围成的区域D=log4/log2=2.0哈尔滨工业大学计算机学院苏小红11什么是分形？（10/21）1891年，大数学家D.Hilbert也构造了一种性质相同的曲线按一定顺序相继穿过每一个小正方形的“中位线”。D=log4/log2=2.0哈尔滨工业大学计算机学院苏小红12性质：能够填充空间十分曲折，连续但不可导具有自相似性什么是分形？（11/21）分形几何兴起以后由反例跃居为主角

这类曲线现在统称为Peano曲线此性质很令数学界吃惊。如果这是可能的，那么曲线与平面如何区分?哈尔滨工业大学计算机学院苏小红131906年，瑞典数学家H.VonKoch在研究构造连续而不可微函数时，构造了Koch曲线。

周长无穷，但面积为定值（0）什么是分形？（12/21）构造方法演示哈尔滨工业大学计算机学院苏小红14构造方法周长无穷，但面积为定值

VonkochsnowflakeD=log4/log3=1.2618什么是分形？（13/21）哈尔滨工业大学计算机学院苏小红15什么是分形？（14/21）1915-1916年，波兰数学家W.Sierpinski(1882-1969)构造了Sierpinski曲线、海绵、墓垛。Sierpinski地毯是平面万有曲线(planeuniversalcurve)Sierpinski海绵是空间万有曲线奥地利数学家门格尔(K.Menger)证明，任何曲线都可嵌入Sierpinski地毯中SierpinskigasketSierpinskicarpet哈尔滨工业大学计算机学院苏小红16什么是分形？（15/21）1919年，F.Hausdorff(1868-1942)给出维数新定义，为维数的非整化提供了理论基础。1918-1920年左右，法国数学家G.Julia(1893-1978)、法图(P.J.L.Fatou,1878-1929)研究复迭代。G.Julia于1918年(当时他25岁)在《纯粹数学与应用数学杂志》上发表了长达199页的杰作，一举成名。

1924年11月20日B.B.Mandelbrot生于波兰。1952年，Mandelbrot获博士学位。传统的欧式几何理论描绘已显得无能为力

哈尔滨工业大学计算机学院苏小红17什么是分形？（16/21）60年代，B.B.Mandelbrot将雪花与海岸线、山水、树木等自然景物联系起来现代分形理论的奠基人经历、性格、举止非同寻常的人物

Mandelbrot与北京大学非线性科学中心主任赵凯华教授

哈尔滨工业大学计算机学院苏小红什么是分形？（17/21）67年，英国《科学》杂志，《英国的海岸线有多长？统计自相似性与分数维数

》正确答案令人吃惊：不确定，依赖测量单位长度研究发现一个很重要而有趣的性质，即自相似性。75年，法文专著《分形对象:形、机遇与维数》77年，英译本《分形：形、机遇与维数》(Fractals:Form,Chance,andDimension)82年，增补本，改名为《大自然的分形几何学》哈尔滨工业大学计算机学院苏小红19什么是分形？（18/21）70年代末，fractal传到中国，一时难以定译。中国科学院物理所李荫远(1919-)院士说，fractal应当译成“分形”郝柏林、张恭庆、赵凯华、朱照宣等科学家表示赞同于是在中国大陆fractal逐渐定译为“分形”如今台湾还译“碎形”，显然不如“分形”好。创造的词Fractal根据拉丁语fractus造的词词根含义：细片的，破碎的，分裂的，分数的哈尔滨工业大学计算机学院苏小红20什么是分形？（19/21）分形？指具有多重自相似的对象它可以是自然存在的，也可以是人造的分形几何在极端有序与真正混沌之间提供了一种中间可能性.它的最显著特征是:看起来十分复杂的事物,大多数可以用很少参数的简单公式来描述哈尔滨工业大学计算机学院苏小红21什么是分形？（20/21）典型的分形随处可见花椰菜、树木、山川、云朵、脑电图、材料断口、海岸线、树枝、山脉、星系分布、云朵、聚合物、多变的天气、大脑皮层褶皱、肺部支气管分支、血液微循环管道、动荡的股市、经济收入分配关系、棉花的价格波动视网膜中央动脉颞上支阻塞视乳头旁毛细血管瘤河流分布图星云语音信号股票分时走势图哈尔滨工业大学计算机学院苏小红22什么是分形？（21/21）85年获得BarnardMedal奖章爱因斯坦(A.Einstein,1879-1955)、费米(E.Fermi,1901-1954)、卢瑟福(L.Rutherford,1871-1937)等人获得过此殊荣1986年获FranklinMedal

1993年获WolfPrizeinPhysics1994年获本田奖(HondaPrize)美国艺术与科学学院(AmericanAcademyofArtsandSciences)院士美国国家科学院(U.S.NationalAcademyofSciences)院士现任职于耶鲁大学哈尔滨工业大学计算机学院苏小红23什么是分形维数？（1/12）分形物体的细节变化用分形维数（分数维）来描述，它是物体粗糙性或细碎性的度量。什么是分数维？整数维数分数维数拓扑维数度量维数哈尔滨工业大学计算机学院苏小红24什么是分形维数？（2/12）只能取整数表示描述一个对象所需的独立变量的个数在一维直线上确定一个点需要一个坐标在二维平面上确定一个点得用两个坐标在三维空间中确定一个点得用三个坐标整数维数拓扑维数哈尔滨工业大学计算机学院苏小红25什么是分形维数？（3/12）从测量的角度定义的从测量的角度看，对象的维数是可变的。例如：看一个毛线团远看是一个0维的点，在广阔的银河系外宇宙空间看地球近看是三维的球进入太阳系后，乘航天飞机在太空沿地球轨道飞行贴近其表面看是二维球面，甚至是二维平面站在旷野上环顾左右再近一些，看一根毛线再接近，看毛线上的纤维分数维数度量维数哈尔滨工业大学计算机学院苏小红26什么是分形维数？（4/12）从测量的角度重新理解维数概念精确描述世界中的现象要有度量“尺度”的观念《楚辞·卜居》中说：“夫尺有所短，寸有所长”事物都有其自己的特征尺度，要用适宜的尺度去测量用寸来量度细菌，用尺来量度万里长城前者失之过长，后者又嫌太短对于一个有确切维数的几何体若用与其维数相同的“尺”去度量，可得到确切数值若用低于其维数的“尺”去度量，结果为无穷大若用高于其维数的“尺”去度量，结果就会为零哈尔滨工业大学计算机学院苏小红27什么是分形维数？（4/12）分形曲线的测量和幂律不同长度尺子s测得的海岸线长度us/kmu/km50025001003800505700178640分形测量哈尔滨工业大学计算机学院苏小红28210345612345678109081632241101001110100100010100(a)线性(b)指数(c)幂指数(d)线性坐标系(e)半对数坐标系(f)双对数坐标系

几种函数关系及研究这些函数关系常用的坐标系N

cl

+dN

clN

l

c与维数定义有关的函数关系是幂指数关系，简称幂律(Powerlaw)哈尔滨工业大学计算机学院苏小红29什么是分形维数？（5/12）1919年F.Hausdorff(1868-1942)

推广了维数的概念,为维数的非整化提供了理论基础理论性强，实际背景较少在很多情形下难以用计算方法求得

在实际应用中，经常应用的是盒维数能通过实验近似地计算，且在一些比较“规则”的分形集上，这种维数的值与Hausdorff维数相等哈尔滨工业大学计算机学院苏小红30什么是分形维数？（6/12）一根一维线段L，单位长度A，将其边长扩大到原来的3倍，能得到几个原始对象(单位长度为A的线段)。3个：

L→3L=3^1*LL3L哈尔滨工业大学计算机学院苏小红31什么是分形维数？（7/12）一根一维线段L，单位长度A，将其边长扩大到原来的3倍，能得到几个原始对象(单位长度为A的线段)。3个：

L→3L=3^1*L平面上的一个正方形P，边长为A，将其边长扩大到原来的3倍9个正方形：

P→9P=3^2*P哈尔滨工业大学计算机学院苏小红32什么是分形维数？（8/12）一根一维线段L，单位长度A，将其边长扩大到原来的3倍，能得到几个原始对象(单位长度为A的线段)。3个：

L→3L=3^1*L平面上的一个正方形P，边长为A，将其边长扩大到原来的3倍9个正方形：

P→9P=3^2*P三维空间上的正方体V，边长为A，将其边长扩大到原来的3倍27个立方体：V→27V=3^3*V

哈尔滨工业大学计算机学院苏小红33什么是分形维数？（9/12）一根一维线段L，单位长度A，将其边长扩大到原来的3倍，能得到几个原始对象(单位长度为A的线段)。3个：

L→3L=3^1*L平面上的一个正方形P，边长为A，将其边长扩大到原来的3倍9个正方形：

P→9P=3^2*P三维空间上的正方体V，边长为A，将其边长扩大到原来的3倍27个立方体：V→27V=3^3*V

得到的总个数可表达为：

M=B^d其中，B指放大倍数，M是总个数，d相当于对象的维数。换一种写法有：

d=logM/logB其中指数d相当于维数哈尔滨工业大学计算机学院苏小红34什么是分形维数？（10/12）从放大的反面——铺砌或者细分的角度去理解对给定对象，用小单元块（相当于测量尺度）r填充（覆盖）它，数一数所使用的小单元数目N(r)r越小，得到的N越大；r越大，得到的N就越小将测得结果在“双对数”坐标纸上绘制出来，会得到一条直线此直线斜率的绝对值就是对象的维数d。容量维数的数学表达：

log(1/r)logN(r)r为细分时缩放因子哈尔滨工业大学计算机学院苏小红35什么是分形维数？（11/12）以Koch曲线为例细分线段数为N=4，细分单元长度为S=1/3Koch曲线的分数维为：

d=ln4/ln3=1.2619而按照欧氏几何方法将一条线段4等分则N=4，S=1/4，d=1。一般来说，二维空间中的分形曲线维数介于1和2之间三维空间中的分形曲线维数在2和3之间。哈尔滨工业大学计算机学院苏小红36什么是分形维数？（11/12）对于实际的自然景物，我们可以用计盒维数的方法测量分维数盒子法(Box-countingMethod)取边长为r的小盒子(可以理解为拓扑维为d的小盒子)，把分形覆盖起来。由于分形内部有各种层次的空洞和缝隙，所以，有些小盒子是空的，有些小盒子覆盖了分形的一部分。数数多少小盒子不是空的，所得的非空(non-empty)盒子数记为N(r)。然后缩小盒子的尺寸r，所得N(r)自然要增大。海岸线哈尔滨工业大学计算机学院苏小红37什么是分形维数？（12/12）其它分数维容量维柯尔莫哥洛夫维信息维关联维雷尼(A.Renyi)维不同定义的分数维概念，从不同的角度描述分形图形的不规则性、复杂或粗糙程度哈尔滨工业大学计算机学院苏小红38什么是分形？（1/2）什么是分形？Mandelbrot开始时把那些Hausdorff维数不是整数的集合称为分形但该定义将某些显然为分形的集合排除在外例如，Peano曲线是分形曲线，但Hausdorff维数为2，是整数修改了这个定义强调具有自相似性的集合为分形哈尔滨工业大学计算机学院苏小红39什么是分形？（2/2）至今无统一定义，比较合理、普遍被人接受的定义定义具有如下性质的集合F为分形F具有精细的结构，有任意小比例的细节F是如此地不规则，以至于它的整体与局部都不能用传统的几何语言来描述F通常有某种自相似的性质，这种自相似性可以是近似的或者是统计意义下的一般地，F的某种定义之下的分形维数大于它的拓扑维数

在大多数令人感兴趣的情形下，F通常能以非常简单的方法定义，由迭代过程产生哈尔滨工业大学计算机学院苏小红40分形几何欧氏几何使用方程描述有平滑的表面和规则形状的物体分形几何使用过程对具有不规则几何形态的物体（如自然景物）建模哈尔滨工业大学计算机学院苏小红41分形几何应用自然景物的逼真模拟自然景物的表面往往包含有丰富的细节或具有随机变化的形状，它们很难用传统的解析曲面来描述尽管凹凸纹理映射技术可以模拟规则景物表面的几何纹理细节，但在表达诸如山脉、云彩、火焰、树木、浪花等自然景象时，凹凸纹理映射技术仍难以胜任海图制作分形图像压缩——作为文献综述内容之一地震预报信号处理苏小红哈尔滨工业大学计算机科学与技术学院第6章自然景物模拟与分形艺术哈尔滨工业大学计算机学院苏小红43随机插值模型（1/3）1982年由AlainFournierDonFussellLorenCarpenter提出能有效地模拟海岸线和山等自然景象不是事先决定各种图素和尺度用一个随机过程的采样路径作为构造模型的手段

哈尔滨工业大学计算机学院苏小红44随机插值模型（2/3）构造二维海岸线的模型：选择控制大致形状的若干初始点在相邻两点构成的线段上取中点，沿垂直连线方向随机偏移一个距离将偏移后的点与该线段两端点分别连成两个新线段如此继续可得到一条曲折的有无穷细节的海岸线，其曲折程度由随机偏移量控制，它也决定了分数维的大小

哈尔滨工业大学计算机学院苏小红45随机插值模型（3/3）在三维情况下用类似过程构造山模型：多边形（如三角形）细分在三角形三边上随机各取一点沿垂直方向随机偏移一段距离得到三个新点连接成四个三角形如此继续，可形成皱褶的山峰哈尔滨工业大学计算机学院苏小红46迭代函数系统（1/20）IteratedFunctionSystem（简称IFS）美国佐治亚理工学院Demko,Barnsley教授首创在SIGGRAPH’85国际会议上，IFS专题报告IFS方法的魅力是分形迭代生成的“反问题”哈尔滨工业大学计算机学院苏小红47迭代函数系统（2/20）确定性算法与随机性算法相结合的方法生成植物杆茎或叶片用以迭代的规则是确定性的，它们由一组仿射变换(如R_1，R_2，R_3等)构成迭代过程是不确定的，每一次迭代哪一个规则，即R_i中具体哪一个，非预先定好，而要靠掷骰子的办法来决定。设最终要生成的植物形态图为M，它要满足下述集合方程：

M=R_1∪R_2∪…∪R_N含义：随机地从R_i(i=1,…，N)中挑选一个迭代规则迭代一次然后再随机地在R_i(i=1,…，N)中选一个规则迭代一次不断重复此过程最后生成的极限图形M就是欲求的植物形态图。每个迭代规则R_i都是一个仿射变换。

哈尔滨工业大学计算机学院苏小红48迭代函数系统（3/20）一个变换S：Rn→Rn称为线性的假若S(x+y)=S(x)+S(y)，且S(λx)=λS(x)S称为非奇异线性变换当且仅当x=0时，有S(x)=0ω称为仿射变换如果变换ω

：Rn→Rn具有形式ω(x)=S(x)+a，这里S为非奇异线性变换，a为Rn中一点哈尔滨工业大学计算机学院苏小红49迭代函数系统（4/20）正交变换保持几何图形的度量性质不变向量的夹角，点与点之间的距离，图形的面积等仿射变换一般会改变几何图形的度量性质但不改变共线、平行、相交、共线点的顺序、中心对称、二次曲线的次数等仿射变换在不同方向可以有不同的压缩和扩张例如可将球变换为椭球，正方形变换为平行四边形哈尔滨工业大学计算机学院苏小红50迭代函数系统（5/20）每个迭代规则R_i都是一个仿射变换。

哈尔滨工业大学计算机学院苏小红51迭代函数系统（6/20）图形经仿射变换后面积变小，则此变换是收缩的面积变大，则是扩张的保持不变，则是恒等的。因为极限图形M应是所有迭代R_i的吸引子每个仿射变换是收缩性的才能保证迭代收敛到M上所以只用到收缩性仿射变换

（ContractiveAffineTransformation）

哈尔滨工业大学计算机学院苏小红52迭代函数系统（7/20）设给定一个仿射变换f，对任意向量x和y，如果总存在一个非负实数，满足则s称为压缩因子使得上式成立的最小实数称为Lipschitz常数（李普希茨常数

）因s<1，因此仿射变换f是收缩仿射变换

哈尔滨工业大学计算机学院苏小红53迭代函数系统（8/20）

上的收缩仿射变换（压缩映射）记为迭代函数系统

若干个收缩仿射变换的组合哈尔滨工业大学计算机学院苏小红54迭代函数系统（9/20）IFS方法生成分形图像的步骤：一个二维的IFS的组成收缩仿射变换的集合概率的集合

确定仿射变换

确定概率向量按照相应的概率，随机从仿射变换集中选择一个作为迭代规则迭代一次，不断重复此迭代过程（通过迭代过程产生点集序列来绘制分形图形）

哈尔滨工业大学计算机学院苏小红55迭代函数系统（10/20）怎样确定仿射变换？确定a,b,c,d,e,f哈尔滨工业大学计算机学院苏小红56迭代函数系统（11/20）怎样实现掷骰子操作？设N=4，每次生成一个随机数E∈(0，100)

设0＜β_1＜β_2＜β_3＜100，作如下规定：

若0＜E＜β_1，则选择规则R_1若β_1≤E＜β_2，则选择规则R_2若β_2≤E＜β_3，则选择规则R_3若β_3≤E＜100，则选择规则R_4指定β_i的过程相当于为每种迭代规则R_i指派一个概率p_i怎样确定概率向量？控制概率就是控制图形各部分的落点密度，使图形在有限迭代步数内显现出浓淡虚实不同的绘制效果。哈尔滨工业大学计算机学院苏小红57迭代函数系统（12/20）D=log3/log2=1.585Sierpinski三角形fabc

defp

10.5000.52510.3320.5000.51500.3330.5000.550500.33哈尔滨工业大学计算机学院苏小红58Sierpinskicarpet迭代函数系统（13/20）D=log8/log3=1.8927哈尔滨工业大学计算机学院苏小红59迭代函数系统（14/20）Barnsley蕨的参数表fabc

defp

10000.16000.0120.850.04-0.040.8501.60.8530.2-0.260.230.2201.60.074-0.150.280.260.2400.440.07fabc

defp

10000.250-0.140.0220.850.02-0.020.83010.8430.09-0.280.30.1100.60.074-0.090.250.30.0900.70.07蕨子叶的参数表哈尔滨工业大学计算机学院苏小红60迭代函数系统（15/20）树冠的参数表fabcdef

pi

f00.01000.45000.05f1-0.0100-0.4500.40.15f20.42-0.420.420.4200.40.4f30.420.42-0.420.4200.40.4fabcdef

pi

f00.01000.45000.05f1-0.0100-0.4500.20.15f20.12-0.820.420.4200.20.4f30.120.82-0.420.4200.20.4六角枫叶的参数表哈尔滨工业大学计算机学院苏小红61迭代函数系统（16/20）fabcdef

pi

f00.6000.60.180.360.25f10.6000.60.180.120.25f20.40.3-0.30.40.270.360.25f30.4-0.30.30.40.270.090.25fabcdef

pi

f00.05000.6000.1f10.0500-0.5010.1f20.460.32-0.3860.38300.60.2f30.47-0.1540.1710.423010.2f40.430.275-0.260.476010.2f50.421-0.3570.3540.30700.70.2哈尔滨工业大学计算机学院苏小红62迭代函数系统（17/20）fabcdef

pi

f00.25000.5000.154f10.5000.5-0.250.50.307f2-0.2500-0.250.2510.078f30.5000.500.750.307f40.500-0.250.51.250.154fabcdef

pi

f00.382000.3820.30720.6190.2f10.382000.3820.60330.40440.2f20.382000.3820.01390.40440.2f30.382000.3820.12530.05950.2f40.382000.3820.4920.05950.2哈尔滨工业大学计算机学院苏小红63迭代函数系统（18/20）fabcdef

pi

f00.5-0.50.50.5000.5f10.50.5-0.50.50.50.50.5fabcdef

pi

f00.8240740.281482-0.2123460.864198-1.882290-0.1106070.8f10.0882720.520988-0.463889-0.3777780.7853608.0957950.2哈尔滨工业大学计算机学院苏小红64迭代函数系统（19/20）增减规则R_i，可以改变最终植物M的形态。即使不改变迭代规则，采用同样的程序，只改变参数也可以生成完全不同的植物形态。ProcedureAFF(a,b,c,d,e,f,S,T:real);Varlins:real;Beginlins:=a*S+b*T+e;y:=c*S+d*y+f;x:=lins;End;65迭代函数系统（20/20）应用自然景物模拟分形图像压缩哈尔滨工业大学计算机学院苏小红66L系统（1/13）由美国生物学家林德梅叶(Lindenmayer)创立，1984年由Smith等人将L系统引入图形学1990年，普鲁辛凯维奇(P.Prusinkiewicz)与林氏出版《植物的算法美》(TheAlgorithmicBeautyofPlants)是一种形式语言字符串重写系统通过符号串的解释，转化为造型工具基本思想：从一个初始串(叫做公理)开始将变换规则多次作用于其上最后产生一个较长的命令串哈尔滨工业大学计算机学院苏小红67L系统（2/13）L系统分类0L系统与上下文无关1L系统仅考虑单边的文法关系，即左相关或右相关在植物的生态模拟中左相关文法用于模拟植物从根向叶、茎的传播过程右相关文法用于模拟从叶到茎、根的传播过程2L系统同时考虑左边和右边文法关系哈尔滨工业大学计算机学院苏小红68L系统（3/13）D0L系统确定的上下文无关的L系统定义为一个三元组〈V,ω,P〉V：字符表(alphabet)V*：V上的所有单词(words)ω：ω∈V*是一个非空的单词，称公理(axiom)P

：包含于V×V*，是产生规则的有穷集。

哈尔滨工业大学计算机学院苏小红69L系统（4/13）设计D0L系统的步骤：定义字符表V给出公理，即初始图ω定义产生式P

哈尔滨工业大学计算机学院苏小红70L系统（5/13）L系统的符号串也称“龟图”(turtle)龟图的状态用三元组(X,Y,D)表示X：横坐标Y：纵坐标D：当前的朝向δ：角度增量H：步长。L系统的符号规定与解释符号图形解释F从当前位置向前走一步，同时画线G从当前位置向前走一步，但不画线+从当前方向向右转一个给定的角度-从当前方向向左转一个给定的角度｜原地转向180°［Push,将龟图当前状态压进栈(stack)］Pop,将图形状态重置为栈顶的状态，

并去掉该栈中的内容\nn增加角度nn度/nn减少角度nn度Cnn选择颜色nn＜nn在此基础上增加颜色nn＞nn在此基础上减少颜色nn!倒转方向(控制+,-,/)@nnn将线段长度乘以nnn，nnn也可以是简单函数其他也是合法的，主要用于获得复杂的解释哈尔滨工业大学计算机学院苏小红71L系统（6/13）13世纪数学家Fibonacci（1170-1250）兔子的理想化繁衍问题

baby(b),adult(a)V：{a,b}W:bP:a->abb->abaababaabaababaababaabaababaabaababaababaabaababaababa哈尔滨工业大学计算机学院苏小红72L系统（7/13）vonKoch雪花曲线V：{F,+,-}w：FP：F->F-F++F-Fδ=60º几何解释F：向前画一条线+：右转60º-：左转60º

n=0n=1n=2n=3w：F++F++F

倒置的正三角形生成元初始图哈尔滨工业大学计算机学院苏小红73L系统（8/13）Koch岛V：{F,+,-}w：F﹣F﹣F﹣FP：F→F﹢F﹣F﹣FF﹢F﹢F﹣Fδ=90º令步长d在相邻两级子图之间缩短4倍，规定后继多边形线(折线)端点之间的距离等于前驱线段的长度

哈尔滨工业大学计算机学院苏小红74L系统（9/13）四方内生树四方内生树V：{F,+,-}w：F+F+F+FP：F->FF+F++F+F

δ=90º

生成元初始图哈尔滨工业大学计算机学院苏小红75L系统（10/13）植物w：FP：F->F[+F]F[-F]F[:将当前乌龟爬行的状态压入堆栈，信息包括所在位置和方向等]:从堆栈中弹出一个状态作为乌龟的当前状态，但不画线哈尔滨工业大学计算机学院苏小红76L系统（11/13）植物（a）n=5，δ=30°S：FP：F→F[﹢F]F[﹣F]F(b)n=5，δ=20°S:FP：F→F[﹢F]F[﹣F][F]

（c）n=4，δ=20.5°S:FP：F→FF﹣[﹣F﹢F﹢F]﹢[﹢F﹣F﹣F]哈尔滨工业大学计算机学院苏小红77L系统（12/13）模拟侧柏形态（左图）w：FP：F->F［+F］F［-F］［F］

δ=90º哈尔滨工业大学计算机学院苏小红78L系统（13/13）设计L系统的过程是根据自相似结构形成信息压缩的一个过程利用设计好的L系统进行绘制的过程是信息压缩的逆过程，或者说是信息复原的过程。

L系统能有效给出植物的拓扑结构但绘制真实感的二、三维植物形态还必须结合几何造型技术例如，若要生成逼真的树干和树枝的柱状曲面、花瓣或树叶的自由曲面等，还需要使用曲面造型技术哈尔滨工业大学计算机学院苏小红79粒子系统（1/8）ParticleSystem

W.T.Reeves1983年提出最重要的计算机生成模型方法描述对象不规则、结构随时间而变化的FuzzyObject

尤其擅长模拟不规则物体的随机动态特性自然现象，密集场景，真实的物理过程如跳动的火焰、烟雾、下雨、行云、远处随风摇曳的树林和草丛等

哈尔滨工业大学计算机学院苏小红80粒子系统（2/8）1985年，Reeves和Blau进一步发展了粒子系统并维妙维肖的模拟了小草随风摇曳的景象模拟动态模糊自然景物电视电影的特技制作最初引入是为了模拟火焰跳动的火焰被看作是一个喷出许多粒子的火山每个粒子都有一组随机取值的属性初始位置、速度、运动方向、初始大小、形状、颜色、透明度、纹理作为文献综述内容之一哈尔滨工业大学计算机学院苏小红81粒子系统（3/8）基本思想造型和动画是一个有机的整体单个随时间变化的粒子(Particle)作为景物造型的基本元素

由一组粒子构成的系统每个粒子有一个生命周期包括出生、成长、死亡等几个阶段粒子在不同的阶段具有不同的形态和属性（位置和速度）粒子形状可以是小球、椭球、立方体或其它形状粒子的运动由一定的规则控制，遵循Newton运动定律哈尔滨工业大学计算机学院苏小红82粒子系统（4/8）本质是随机模型采用随机过程的方法来实现粒子在“出生”、“生长”、“死亡”三个阶段的不确定性在生长过程中，粒子的属性被随机地改变粒子的大小和形状随时间变化其它性质如粒子透明度、颜色和移动等都随机地变化哈尔滨工业大学计算机学院苏小红83粒子系统（5/8）模拟动态自然景物的过程生成新的粒子，分别赋予不同的属性以及生命周期将新粒子加到系统中删去系统中老的已经死亡的粒子

根据粒子的属性，按适当的运动模型或规则，对余下的存活粒子的运动进行控制（Transformation）绘制当前系统中存活的所有粒子哈尔滨工业大学计算机学院苏小红84粒子系统（6/8）对于粒子系统的随机性Reeves采用一些非常简单的随机过程来控制粒子在它所在系统中的形状、特征及运动。先确定每个粒子的变化范围然后在该范围内随机地确定它的值变化范围由给定的平均期望值和最大方差来确定粒子的基本属性包括：（1）初始位置、大小；

〔2）初始运动速度和方向；（3）初始颜色；（4）初始透明度；

〔5）初始形状；（6）生命周期。哈尔滨工业大学计算机学院苏小红85粒子系统（7/8）粒子数目对模糊物体的密度有很重要的影响，粒子系统通过控制每一帧进入系统的粒子数和死亡的粒子数来控制粒子系统中粒子的数量。控制每帧的粒子数的两种方法由每帧产生的粒子平均数和其方差控制粒子数，实际在f帧产生的粒子数为新产生的粒子数取决于物体的屏幕尺寸。控制每个屏幕单位产生的粒子平均数MeanParts和其方差VarParts

，根据物体覆盖的屏幕尺寸ScreanArea计算出所需的粒子数：f是当前帧，f0

是粒子系统开始的第一帧，InitialMeanParts

指第一帧粒子的平均数，DeltaMeanParts

是相应的变化率哈尔滨工业大学计算机学院苏小红86粒子系统（8/8）粒子系统运行的流程哈尔滨工业大学计算机学院苏小红87混沌吸引子气象学家E.N.Lorenz混沌理论的少有几位创立者之一，1963年，在研究大气环流的对流运动时，发现了第1个奇异吸引子运动为非周期性的，而且具有不可预测的随机性他在1963年发表的关于混沌理论的开创性研究在被冷落了12年之久以后才得到广泛承认，并很快引发对混沌研究的热潮，由此诞生和发展起了一门新兴学科—混沌理论，成为现代新兴学科的代表。(b)沿y轴方向投影的Lorenz吸引子(a)沿x轴方向投影的Lorenz吸引子(c)沿z轴方向投影的Lorenz吸引子图6-43Lorenz吸引子混沌可以理解为貌似随机的确定性。哈尔滨工业大学计算机学院苏小红88迭代（动力系统）的问题动力系统指随时间确定性地变化的系统。系统的状态可由一个或几个变量的数值来确定。哈尔滨工业大学计算机学院苏小红89复平面上的迭代（1/18）动力系统中的分形动力系统的奇异吸引子通常都是分形集，它们产生于非线性函数的迭代和非线性微分方程中

复平面上解析映射的迭代（复数的非线性映射）1918~1919年，Julia和Fatou研究发现，此迭代把复平面划分为两部分：Fatou集和Julia集Julia集的定义哈尔滨工业大学计算机学院苏小红90复平面上的迭代（2/18）C=-1C=-0.5+0.5iC=-0.2+0.75iC=0.64iJulia集的图象哈尔滨工业大学计算机学院苏小红91复平面上的迭代（3/18）80年代初，Mandebrot在迭代z→z^2+c时，用计算机绘制了著名的Mandebrot集，简称M集

哈尔滨工业大学计算机学院苏小红92复平面上的迭代（4/18）Julia集固定C值，对不同Zk值进行迭代，生成的图像用屏幕上不同的点Zk(xk,yk)作为初值迭代，产生的Zk序列会出现收敛与发散两种情况通过设定最大迭代次数N和阈值M对点着不同的色迭代到N，但模值未超过M——收敛，用固定颜色显示迭代到N，但模值已超过M——发散，根据其发散速度用不同色显示从Zk(xk,yk)到Zk+1(xk+1,yk+1)的迭代公式：哈尔滨工业大学计算机学院苏小红93复平面上的迭代（5/18）Julia集固定C值，对不同Zk值进行迭代，生成的图像M集令Zk=0，对不同的C值进行迭代，生成的图像Julia集是取一固定的c值后，观察复平面上每一点(x,y)在迭代中的表现，并把结果记录下来M集记录的是整个区域上的c值情况哈尔滨工业大学计算机学院苏小红94复平面上的迭代（6/18）标色有很多技巧表面看来好像属于计算机技术但实际上这属于传统的美术。分形图形艺术是传统美术与计算机的结合。虽然本质上具有同样的数学结构标上不同的颜色，就有完全不同的视觉效果哈尔滨工业大学计算机学院苏小红95复平面上的迭代（7/18）M集特征：一个主要的心形图与一系列圆盘形的“芽苞”突起连在一起每个芽苞又被更细小的芽苞所环绕还有精细的“发丝状”分枝从芽苞向外长出M集逐步放大图

哈尔滨工业大学计算机学院苏小红96复平面上的迭代（8/18）M集包含了关于Julia集构造的大量信息M集不同部位的形状反映了对应于该处的J集的形状哈尔滨工业大学计算机学院苏小红97复平面上的迭代（9/18）(a)c=0.1-0.1i，f有吸引不动点，J为拟圆(b)c=0.5-0.5i，f有吸引不动点，J为拟圆(c)c=1.0-0.05i，f有周期为2的吸引轨道(d)c=0.2-0.75i，f有周期为3的吸引轨道(e)c=-0.25-0.52i，f有周期为4的吸引轨道(f)c=0.5-0.55i，f有周期5的吸引轨道(g)c=-0.66i，f没有吸引轨道，且J为全部连通(h)c=-i，f为无圈曲线改变常数c的取值，可以得到各式各样的J集

主心形图上芽苞上或心形图边界

芽苞与心形图接触的“颈部”

“发状”分枝上

哈尔滨工业大学计算机学院苏小红98J集的快速生成算法图6-46“区域四分法”的原理n1(0,0)n3(0,b)n2(a,0)n4(a,b)c2(0,b/2)c4(a,b/2)c5(a/2,b)c1(a/2,0)c3(a/2,b/2)2区4区1区3区哈尔滨工业大学计算机学院苏小红99复平面上的迭代（10/18）二维复平面上二次映射广义的M集和J集任意多项式映射三角函数指数函数对数函数z→z^m+c,其中m分别为4，5，6，7，8，9哈尔滨工业大学计算机学院苏小红100广义Julia集与Mandelbrot集(a)复指数Mandelbrot集(b)复指数Julia集(c)复映射z→z4+c的M集哈尔滨工业大学计算机学院苏小红101复平面上的迭代（11/18）在二维复平面中表示复数只用两个基向量：1和i在四维空间中讨论超复数，有四个基向量：1,i,j和k任一复数可以表示为：q=x+yi+zj+qk高维M集与J集通过“四元数”(quaternions)推广到高维空间中

哈尔滨工业大学计算机学院苏小红102复平面上的迭代（12/18）四元数英国数学家W.Hamilton，1843年是复数的推广四元数表示在球面上的光滑旋转非常有效球面线性插值计算量小哈尔滨工业大学计算机学院苏小红103复平面上的迭代（13/18）四元数的二次迭代将z取为四元数表示哈尔滨工业大学计算机学院苏小红104复平面上的迭代（14/18）在四维空间中研究迭代x→x^2+c下的超Julia集按照四元数运算法则，做出Julia集和Mandelbrot集的空间结构图像选一个截面，将超Julia集投影到三维空间中，可以得到立体的J集图象用四元数法得到的高维Julia集的投影图哈尔滨工业大学计算机学院苏小红105复平面上的迭代（15/18）复平面域的牛顿法求根本质是“以直代曲”首先猜测一个值x1，用它近似方程的根c用过(x1,f(x1))点的切线

y=f(x1)+f’(x1)(x-x1)

近似代替曲线f(x)然后用切线方程

y=f(x1)+f’(x1)(x-x1)=0

的根

x=x2=x1-f(x1)/f’(x1)

近似代替曲线方程的根c这样就得到c的第二个近似值依此类推可得到迭代公式

x(n+1)=xn-f(xn)/f’(xn)哈尔滨工业大学计算机学院苏小红106复平面上的迭代（16/18）f(x)=x^p-1,其中p是大于2的正整数x^3-1=0有三个根：x1=1x2=[-1+SQRT(3)i]/2x3=[-1-SQRT(3)i]/2哈尔滨工业大学计算机学院苏小红107复平面上的迭代（17/18）用牛顿法求z^3-1=0的根得到的分形图三个根均匀地分布在单位圆上,这三个根周围构成三个“吸引盆”(attractorbasin)初始点迅速被吸引到盆内，最后停止在三点之一。用计算机迭代，以当前点到三个终点的距离远近为标准，标上不同的颜色，就能得到美丽的分形图特别是在120°线、240°线附近有复杂的“项链”结构。哈尔滨工业大学计算机学院苏小红108复平面上的迭代（18/18）改进方法分式线性映射w=1/z在扩充的复平面上是一一对应的且为具有保圆性和保对称性的保角映射将牛顿函数取倒数，并在迭代过程中嵌入控制参数用牛顿法求z^4-1=0的根得到的分形图分子部分完全相同超吸引不动点相同哈尔滨工业大学计算机学院苏小红109(a)α=1,β=1,p=1,q=0xmax=ymax=1.5(b)α=1.5,β=1,p=1,q=0xmax=ymax=1(c)α=1,β=1,p=1.3,q=0xmax=ymax=2(d)α=1,β=1.8,p=1,q=0xmax=ymax=2(e)α=0.5,β=1.2,p=1,q=0xmax=ymax=1.5(f)α=1,β=1,p=1,q=0xmax=ymax=2.5哈尔滨工业大学计算机学院苏小红110(a)α=2.5,β=1,p=1.5,q=0xmax=ymax=1.5(a)α=1,β=1.8,p=1.5,q=0xmax=ymax=1(a)α=0.5,β=1,p=0.5,q=0xmax=ymax=1.2(b)α=1.2,β=1,p=1,q=0xmax=ymax=1.5哈尔滨工业大学计算机学院苏小红111复平面上的迭代苏晓红等，Julia集的快速显示算法，计算机工程，1996，22(6):300-303苏晓红等．用改进的Newton-Raphson方法生成对称的分形艺术图形，计算机学报．1999,22(11):1147-1152（一）第8章真实感图形生成

真实感图形绘制流程场景造型113取景变换背面剔除和视域四棱锥裁剪计算场景中可见面的光亮度和颜色

透视投影隐藏面消除

取景变换（1/6）场景坐标系场景的局部坐标系完成物体的造型场景的世界坐标系（整体坐标系）放入待绘制的场景，定义物体之间的相互位置如果物体被设置了动画动画系统将提供一个随时间变化的变换矩阵逐帧把物体变换到世界坐标系中114xzyzyx取景变换（2/6）观察坐标系也称摄像机坐标系，或者视点坐标系完成取景变换所需建立的第一个坐标系115取景变换（3/6）建立观察坐标系的步骤确定观察参考点，即视点位置可以设在任何位置通常选在靠近或在物体的表面将视点位置取为视点坐标系的原点确定观察方向，即视线方向一般取深度坐标轴，即ze轴的正向为简便起见，设为总是指向场景坐标系的原点确定观察平面，即视平面位置一般取过视点且垂直于视线方向的平面，即xeye平面116取景变换（4/6）场景坐标系一般取右手坐标系观察坐标系通常取左手坐标系符合人们的观察习惯117xwzwywzexeye视点E观察坐标系为左手坐标系场景坐标系为右手坐标系O取景变换（5/6）将物体投影到观察平面之前必须将场景坐标系中的点转换到观察坐标系中

这一过程称为取景变换，也称视向变换包括平移和旋转的一系列几何变换的级联取景变换矩阵118取景变换（6/6）场景坐标系原点平移到视点位置E绕xe轴逆时针旋转90º绕ye轴顺时针旋转Ψ角绕xe轴逆时针旋转θ角调整x轴指向对x轴作对称变换119xwzwywzexeyeEOCxCyCzΨxwzwywzexeyeEOCxCyCz90ºxwzwywzexeyeEOCxCyCzxwzwywzexeyeEOCxCyCzΨθθ消隐算法（1/2）消隐的基本（核心）问题：排序整体排序：画家算法点排序：Z-Buffer算法、光线投射算法区间排序：扫描线算法区域排序：区域子分算法120消隐算法（2/2）按实现方式不同分为两大类：景物空间（objectspace）

消隐算法直接在视点坐标系中确定视点不可见的表面区域将它们表达成同原表面一致的数据结构侧重于景中各物体之间的几何关系图像空间（imagespace）消隐算法

在投影屏幕上，以屏幕像素为采样单位，确定投影于每一像素的可见景物表面区域将其颜色作为该像素的显示光亮度侧重于向屏幕投影后形成的图像121提高消隐算法效率的常用方法（1/5）提高消隐算法效率利用各种形式的相关性（连贯性）物体的连贯性面的连贯性区域的连贯性扫描线的连贯性帧的连贯性122提高消隐算法效率的常用方法（2/5）包围盒技术避免盲目求交包围盒--包围目标的简单形体包围简单常用的包围盒长方体球圆柱123提高消隐算法效率的常用方法（3/5）空间分割技术124提高消隐算法效率的常用方法（5/5）背面剔除算法

125法向向量N

视线向量V法向向量N

法向向量N<90°<90°可见可见不可见>90°隐藏面的消除-画家算法

（1/4）画家算法

1972年M.E.Newell受画家由远至近作画的启发景物空间消隐算法126隐藏面的消除-画家算法

（2/4）基本思想127画家消隐算法{

对场景中的多边形按深度进行排序， 形成深度优先级队列； 按从远到近的顺序显示多边形；}也称优先级表算法隐藏面的消除-画家算法

（3/4）基本步骤生成深度优先级队列据视点距离远的多边形优先级低，排在队列的前端据视点距离近的多边形优先级高，排在队列的后端从队列中依次取出多边形，计算其表面光亮度写入帧缓冲器

直到队列中所有多边形的光亮度都计算完毕，并写入帧缓冲器128隐藏面的消除-画家算法

（4/4）优点：简单，容易实现适于图形的动态显示飞行训练模拟器中显示飞机着陆时的情景场景中的物体是不变的，只是视点在变化只要事先把不同视点的景物的优先级队列算出再实时地采用画家算法来显示图形就可以实现图形的快速消隐与显示缺点：深度排序计算量大129隐藏面的消除-画家算法

（4/4）问题：深度优先级表的建立是动态进行的。假定观察方向同Z轴同向，则最初可按各面的最小z值排序。但排序可能出错130尽管面S1的最小z值小于面S2的最小z值，但正确顺序是面S2位于面S1前若存在两面相交和循环遮挡，必须求交分割后再进行排序隐藏面的消除-画家算法

（4/4）算法(1）计算各面最小z值zmin，并以此值的优先级进行排序，建立初步的深度优先表；(2）表空结束。否则取表中深度最大的面Sn,检查表中其它各面Sk(k=0,1,...,n-1)与Sn是否在Z方向存在重叠的关系。存在，记重叠面为Sj转(3)。否则，将Sn写入帧缓冲器，n=n-1转(2)；(3)检查Sn是否遮挡Sj，不遮挡则将Sn写入帧缓存器，n=n-1转(2)。否则，交换Sn和Sj在表中位置，转(2)。如果Sn和Sj已经交换过位置，则两面交叉遮挡，转(4)；(4)用Sn和Sj的交线分割Sn为两部分，转(1)。131隐藏面消除-Weiler-Atherton算法（1/3）Weiler-Atherton算法景物空间消隐算法基于Weiler-Atherton多边形裁剪操作132隐藏面消除-Weiler-Atherton算法（2/3）基本步骤

1)深度预排序，形成景物多边形表

将变换到屏幕坐标系中的景物表面按各顶点的z最小值进行排序2)当前具有最大z值的景物表面作为裁剪多边形CP

深度最大、离视点最近3)用CP对景物多边形表中排在后面的表面进行裁剪

产生内部多边形Pin和外部多边形Pout

133裁剪多边形将主多边形裁剪为内部多边形和外部多边形PinPout裁剪多边形CP主多边形SP隐藏面消除-Weiler-Atherton算法（3/3）4)比较CP与Pin的深度，检查CP是否真正离视点最近是，则CP为可见表面不是，则取Pin为新的CP，重复步骤3)5)将位于CP之外的景物表面组成外裁剪结果多边形表

取表中深度最大的表面为CP，重复步骤3)6)递归进行直到外裁剪结果多边形表为空时为止134隐藏面的消除-BSP树算法（1/2）BSP树算法BinarySpacePartitioning景物空间消隐算法基于BSP树，对景物表面进行二叉分类与画家算法类似，景物多边形由远至近绘制特别适合的场合场景中物体位置固定不变、仅视点移动135隐藏面的消除-BSP树算法（2/2）基本步骤

选一剖分平面P1，将场景空间分割成两个半空间剖分结果表示为一棵BSP树叶节点：景物左分支：位于剖分平面前面的景物右分支：位于剖分平面后面的景物依据视点位置，对子空间进行分类包含视点的子空间标识为“front”另一侧子空间标识为“back”递归搜索该BSP树，优先绘制标识为“back”的子空间中所含的景物136P1P2P2frontfrontfrontbackbackbackACDB与物体相交，就将它分割为两个物体

BfrontfrontbackbackACDP1P2隐藏面消除-深度缓冲器算法（1/10）深度缓冲器算法Depth—bufferalgorithm图像空间消隐算法1975年，Catmull提出在像素级上以近物取代远物有利于硬件实现，但需要较多存储空间137隐藏面消除-深度缓冲器算法（2/10）深度与可见性138uvnxmaxymax隐藏面消除-深度缓冲器算法（3/10）基本思想将投影到显示屏上的每一个象素所对应的多边形表面的深度进行比较取最靠近视点的表面的属性值作为该像素的属性值用frame—buffer记录该表面在该像素点的颜色或亮度值用Z—buffer记录该表面在该像素点的深度深度缓冲器帧缓冲器的扩充也称Z-Buffer算法139隐藏面消除-深度缓冲器算法（4/10）基本步骤

取景变换、透视变换、扫描转换将物体描述转化为屏幕坐标系中的投影坐标初始化深度缓冲器初始化为离视点最远的最小值帧缓冲器初始化为背景的属性值140隐藏面消除-深度缓冲器算法（5/10）流程：for（场景中的每一个多边形）{

扫描转换该多边形；

for（多边形所覆盖的每一个像素点(x,y)）

{

计算多边形在该像素点的深度值z(x,y)；

if（z(x,y)>Z-buf中对应此像素点(x,y)的z值）

{

把多边形在(x,y)处的深度值z(x,y)存入Z-buf中的(x,y)处；把多边形在(x,y)处的亮度值存入f-buf中的(x,y)处；

}}}当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像141隐藏面消除-深度缓冲器算法（6/10）优点简单，可轻而易举地处理任意复杂的画面在象素级上以近物代替远物，易于消除隐藏面，并准确显示复杂曲面之间的交线。计算量呈线性复杂度O(n)n:场景中景物表面采样点的数目图象空间的大小是固定的，计算量最多随画面复杂度线性增长无需对各景物表面片作深度预排序景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器易于硬件实现图形工作站上带有用于消隐的深度缓存，克服了深度缓存算法占用大量存储单元的缺点很多微型机上都装有基于深度缓冲器算法的图形加速卡142隐藏面消除-深度缓冲器算法（7/10）缺点需要很大的存储空间例如：象素数目500×500，深度值采用浮点型（4字节）除刷新缓存外，还需500*500*4=1M字节的额外存储空间在实现反走样、处理透明和半透明等效果方面存在困难，并产生巨大的处理时间开销由于在帧缓冲器内的同一象素点上可见表面的写入顺序是不确定的，所以可能导致画面上的局部错误。143隐藏面消除-深度缓冲器算法（8/10）改进一：减少需要相对测试的多边形平面数最小最大测试

144不重叠,不可能互相遮蔽测试无确定结果

对每条边进行最小最大测试XminXmax隐藏面消除-深度缓冲器算法（9/10）改进二：利用连贯性计算深度水平方向竖直方向145xmaxymax隐藏面消除-深度缓冲器算法（10/10）改进三：降低对存储空间的需求图像空间划分为4、16甚至更多的子正方形或条状区域在最小情况下，只对应一条扫描线的深度缓冲器扫描线相关算法146隐藏面的消除-扫描线相关算法（1/5）扫描线相关算法按扫描线顺序处理一帧画面在扫描平面（ZOX平面）上解决消隐问题由视点和扫描线所决定深度缓冲器算法的一维版本深度缓冲器所需的存储空间屏幕水平分辨率×每个深度值所占的存储位数147隐藏面的消除for(每条扫描线){

将扫描线帧缓冲器f_bu