苏小红哈尔滨工业大学计算机科学与技术学院

1、苏苏 小小 红红哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机学院 苏小红2迭代函数系统（迭代函数系统（1/24）Iterated Function System（简称（简称 IFS）美国佐治亚理工学院美国佐治亚理工学院 Demko,Barnsley教授首创教授首创在在SIGGRAPH85国际会议上，国际会议上， IFS专题报告专题报告IFS方法的魅力方法的魅力是分形迭代生成的是分形迭代生成的“反问题反问题”哈尔滨工业大学计算机学院 苏小红3迭代函数系统（迭代函数系统（2/24）确定性算法确定性算法与与随机性算法随机性算法相结合的方法生成相结合的方法生

2、成植物杆茎或叶片植物杆茎或叶片 用以迭代的规则是确定性的，它们由一组用以迭代的规则是确定性的，它们由一组仿射变换仿射变换(如如R_1，R_2，R_3等等) 构成构成 迭代过程是不确定的，每一次迭代哪一个迭代过程是不确定的，每一次迭代哪一个规则，即规则，即R_i中具体哪一中具体哪一 个，非预先定好，个，非预先定好，而要靠掷骰子的办法来决定。而要靠掷骰子的办法来决定。 设最终要生成的植物形态图为设最终要生成的植物形态图为M ，它要满足下述集合方程：，它要满足下述集合方程： M=R_1R_2R_N含义：含义：随机地从随机地从R_i(i=1,，N)中挑选一个迭代规则迭代中挑选一个迭代规则迭代 一次一次

3、然后再随机地在然后再随机地在R_i(i=1,，N)中选一个规则迭代一次中选一个规则迭代一次不断重复此过程不断重复此过程最后生成的极限图形最后生成的极限图形M就是欲求的植物形态图。就是欲求的植物形态图。每个迭代规则每个迭代规则R_i都是一个仿射变换。都是一个仿射变换。 哈尔滨工业大学计算机学院 苏小红4迭代函数系统（迭代函数系统（3/24）一个变换一个变换S：Rn Rn称为线性的称为线性的假若假若S(x+y)=S(x)+S(y)，且，且S(x)= S(x)S称为非奇异线性变换称为非奇异线性变换当且仅当当且仅当x=0时，有时，有S(x)=0称为仿射变换称为仿射变换如果变换如果变换 ：Rn Rn具有

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

5、不同的压缩和扩张例如可将球变换为椭球，正方形变换为平行四边形例如可将球变换为椭球，正方形变换为平行四边形哈尔滨工业大学计算机学院 苏小红6迭代函数系统（迭代函数系统（5/24）每个迭代规则每个迭代规则R_i都是一个仿射变换。都是一个仿射变换。 bxTxf)()(feyxdcbayxfBAXX)(fdcbaAyxXdcB 哈尔滨工业大学计算机学院 苏小红7迭代函数系统（迭代函数系统（6/24）图形经仿射变换后图形经仿射变换后面积变小，则此变换是面积变小，则此变换是收缩收缩的的面积变大，则是面积变大，则是扩张扩张的的保持不变，则是保持不变，则是恒等恒等的。的。 因为因为极限图形极限图形M应是所有迭

6、代应是所有迭代R_i的吸引子的吸引子每个仿射变换是收缩性的才能保证迭代收敛到每个仿射变换是收缩性的才能保证迭代收敛到M上上 所以所以只用到只用到收缩性仿射变换收缩性仿射变换 （Contractive Affine Transformation） 哈尔滨工业大学计算机学院 苏小红8迭代函数系统（迭代函数系统（7/24）设给定一个仿射变换设给定一个仿射变换f，对任意向量，对任意向量x和和y，如果总存，如果总存在一个非负实数在一个非负实数 ，满足，满足则则s称为压缩因子称为压缩因子使得上式成立的最小实数称为使得上式成立的最小实数称为Lipschitz常数（李普常数（李普希茨常数希茨常数 ）因因s 1

7、，因此仿射变换，因此仿射变换f是是收缩仿射变换收缩仿射变换 ) 10 ，syx)y()x(sff222211)()(yxyxyxTxx21x Tyy21y 哈尔滨工业大学计算机学院 苏小红9迭代函数系统（迭代函数系统（8/24） 上的收缩仿射变换（压缩映射）上的收缩仿射变换（压缩映射） 记为记为2R),(yxfifeyxdcbayxfi迭代函数系统迭代函数系统 若干个收缩仿射变换的组合若干个收缩仿射变换的组合哈尔滨工业大学计算机学院 苏小红10迭代函数系统（迭代函数系统（9/24）IFS方法生成分形图像的步骤方法生成分形图像的步骤 ：一个二维的一个二维的IFS的组成的组成收缩仿射变换的集合收缩

8、仿射变换的集合概率的集合概率的集合 ,.,21nfff，,.,21nppp，确定仿射变换仿射变换 确定概率向量概率向量按照相应的概率，随机从仿射变换集中选择一个作为迭代规则迭代一次，不断重复此迭代过程（通过迭代过程产生点集序列迭代过程产生点集序列来绘制分形图形） ifip1.21nppp0ip 哈尔滨工业大学计算机学院 苏小红11迭代函数系统（迭代函数系统（10/24）怎样确定怎样确定仿射变换？仿射变换？确定a,b,c,d,e,f哈尔滨工业大学计算机学院 苏小红12迭代函数系统（迭代函数系统（11/24）怎样实现掷骰子操作怎样实现掷骰子操作 ？设设N=4，每次生成一个随机数，每次生成一个随机数

9、E(0，100) 设设0_1_2 _3100，作如下规定：，作如下规定： 若若0E_1，则选择规则，则选择规则R_1若若_1E_2，则选择规则，则选择规则R_2若若_2E_3，则选择规则，则选择规则R_3若若_3E100，则选择规则，则选择规则R_4指定指定_i的过程的过程相当于为每种迭代规则相当于为每种迭代规则R_i指派一个概率指派一个概率p_i怎样确定怎样确定概率向量？概率向量？控制概率就是控制图形各部分的落点控制概率就是控制图形各部分的落点密度，使图形在有限迭代步数内显现密度，使图形在有限迭代步数内显现出浓淡虚实不同的绘制效果。出浓淡虚实不同的绘制效果。哈尔滨工业大学计算机学院 苏小红1

10、3迭代函数系统（迭代函数系统（12/24）概率向量概率向量对分形图形的影响假设硬币呈现正面、反面和侧立的概率分别为0.5，0.47，0.03可以发现计算机的迭代次数（n）与图形清晰度的关系。1. 在平面上任意确定三个点A、B、C，使得甲、乙、丙三人分别占据其中一个点；并轮流在平面上添画并占据新的点。2. 一个新点出现后，由谁接着画要由掷硬币来决定：硬币出现正面时由甲画，出现反面时由乙画，出现侧立时由丙画。3. 当平面上出现一个新点时，不论轮到谁画，他都必须在新点与自己所占据的点之间的连线的中点处画出一个新点 n =106n =107迭代函数系统（迭代函数系统（13/24）哈尔滨工业大学计算机学

11、院 苏小红15迭代函数系统（迭代函数系统（14/24）D=log3/log2=1.585 Sierpinski三角形三角形fabc defp 1 0.5000.52510.332 0.5000.51500.333 0.5000.550500.33哈尔滨工业大学计算机学院 苏小红16Sierpinski gasket迭代函数系统（迭代函数系统（15/24）D=log3/log2=1.585 Sierpinski三角形三角形哈尔滨工业大学计算机学院 苏小红17Sierpinski carpet迭代函数系统（迭代函数系统（16/24）D=log8/log3=1.8927 哈尔滨工业大学计算机学院 苏

12、小红18迭代函数系统（迭代函数系统（17/24）21cossinsincosbbyxsrsryxfirsb1b2pif00.00.16000.00.00.005f10.850.85-2.5-2.50.01.60.8f20.30.3449490.01.60.0975f30.30.37120-500.00.440.0975蕨子叶蕨子叶 哈尔滨工业大学计算机学院 苏小红19迭代函数系统（迭代函数系统（18/24）增减规则增减规则R_i，可以改变最终植物，可以改变最终植物M的形态。的形态。即使不改变迭代规则，采用同样的程序即使不改变迭代规则，采用同样的程序 ，只，只改变参数改变参数也可以生成完全不同的

13、植物形态。也可以生成完全不同的植物形态。 哈尔滨工业大学计算机学院 苏小红20迭代函数系统（迭代函数系统（19/24）Barnsley蕨蕨的参数表fabc de fp 10000.160 00.0120.850.04-0.040.850 1.60.8530.2-0.260.230.220 1.60.074-0.150.280.260.240 0.440.07fabc defp 10000.25 0-0.140.0220.850.02-0.02 0.83 010.8430.09-0.280.30.1100.60.074-0.090.250.30.09 00.70.07蕨子叶蕨子叶的参数表哈尔滨工

14、业大学计算机学院 苏小红21迭代函数系统（迭代函数系统（20/24）树冠树冠的参数表fabcdef pi f00.01000.45000.05f1-0.0100-0.45 00.40.15f20.42-0.420.420.4200.40.4f30.420.42-0.42 0.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六角枫叶六角枫叶的参数表哈尔滨工业大学计算机学院 苏小红22迭代函数系统（迭代函数系统（21/24）

15、fabcdef pi f00.6000.60.18 0.36 0.25f10.6000.60.18 0.12 0.25f20.40.3-0.30.40.27 0.36 0.25f30.4-0.30.30.40.27 0.09 0.25fabcdef pi f00.05000.6000.1f10.0500-0.5010.1f20.460.32-0.3860.38300.60.2f30.47-0.154 0.1710.423010.2f40.430.275-0.260.476010.2f50.421-0.357 0.3540.30700.70.2哈尔滨工业大学计算机学院 苏小红23迭代函数系统（迭

16、代函数系统（22/24）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哈尔滨工业大学计算机学院 苏

17、小红24迭代函数系统（迭代函数系统（23/24）fabcdef pi f00.5-0.5 0.50.5000.5f10.50.5-0.5 0.50.50.50.5fabcdef pi f00.8240740.281482 -0.212346 0.864198-1.882290 -0.1106070.8f10.0882720.520988 -0.463889 -0.377778 0.7853608.0957950.2哈尔滨工业大学计算机学院 苏小红25迭代函数系统（迭代函数系统（24/24）应用应用自然景物模拟自然景物模拟分形图像压缩分形图像压缩Barnsley蕨对应的迭代函数系统只有蕨对应的迭

18、代函数系统只有24个参数，但这个参数，但这24个参个参数却决定了一个高度复杂的精细结构。数却决定了一个高度复杂的精细结构。如果以如果以8比特代表一个系数，那么比特代表一个系数，那么192比特就可以代表一片蕨子比特就可以代表一片蕨子叶，可见压缩比是很大的叶，可见压缩比是很大的 哈尔滨工业大学计算机学院 苏小红26OpenGL函数实现的Sierpinski三角形三角形哈尔滨工业大学计算机学院 苏小红27OpenGL函数实现的Sierpinski三角形三角形哈尔滨工业大学计算机学院 苏小红28OpenGL函数实现的三维三维Sierpinski地毯地毯算法：算法：3D_Sierpinski标题：标题：

19、 三维空间中的三维空间中的Sierpinski地毯地毯变量：端点坐标变量：端点坐标 a(x1,y1,z1), b(x2,y2,z2) c(x3,y3,z3), d(x4,y4,z4) a1( ), a2( ), b1( ), b2( ) c1( ), c2( ), d1( ), d2( ) a_( ), b_( ) c_( ), d_( ) 函数：函数： glVertex2s(x,y) （顶点坐标函数） glVertex2s(x,y,z)（顶点坐标函数）参考书：分形算法与程序设计参考书：分形算法与程序设计哈尔滨工业大学计算机学院 苏小红29point3d one_third(point3d &

20、 p2) return point3d(p2.x-x)/3+x, (p2.y-y)/3+y, (p2.z-z)/3+z); /算出所有点的坐标 point3d a1 = a.one_third(b), a2=b.one_third(a);point3d b1 = b.one_third(c), b2=c.one_third(b);point3d c1 = c.one_third(d), c2=d.one_third(c);point3d d1 = d.one_third(a), d2=a.one_third(d);point3d _a=a1.one_third(c2), _b= a2.one_

21、third(c1);point3d _c=b2.one_third(d1), _d= d1.one_third(b2);/递归绘制8个小块 Menger(a, a1, _a, d2); Menger(a1, a2, _b, _a); Menger(a2, b, b1, _b); Menger(_b, b1, b2, _c); Menger(_c, b2, c, c1); Menger(_d, _c, c1, c2); Menger(d1, _d, c2, d); Menger(d2, _a, _d, d1); 哈尔滨工业大学计算机学院 苏小红30OpenGL函数实现的Sierpinski金字塔

22、金字塔算法：算法：Sierpinski_pyramid标题：标题： Sierpinski金字塔金字塔 变量：端点坐标变量：端点坐标 a(x1,y1,z1), b(x2,y2,z2) c(x3,y3,z3), d(x4,y4,z4) 函数：函数： glVertex2s(x,y) （顶点坐标函数） glVertex2s(x,y,z)（顶点坐标函数）哈尔滨工业大学计算机学院 苏小红31point3d middle(point3d & p2) return point3d(x+p2.x)/2, (y+p2.y)/2, (z+p2.z)/2);glBegin(GL_TRIANGLES); glVerte

23、x3f(a.x, a.y, a.z); glVertex3f(b.x, b.y, b.z); glVertex3f(c.x, c.y, c.z); glVertex3f(d.x, d.y, d.z); glVertex3f(a.x, a.y, a.z); glVertex3f(b.x, b.y, b.z); glVertex3f(d.x, d.y, d.z); glVertex3f(b.x, b.y, b.z); glVertex3f(c.x, c.y, c.z);glEnd();/递归绘制四个锥体 seripinski(a.middle(b), b, b.middle(c), b.middl

24、e(d); seripinski(a, a.middle(b), a.middle(c), a.middle(d); seripinski(a.middle(c), b.middle(c), c, c.middle(d); seripinski(a.middle(d), b.middle(d), c.middle(d), d);哈尔滨工业大学计算机学院 苏小红32OpenGL函数实现的Sierpinski金字塔金字塔 哈尔滨工业大学计算机学院 苏小红33OpenGL函数实现的Sierpinski金字塔金字塔哈尔滨工业大学计算机学院 苏小红34OpenGL函数实现的Sierpinski海绵海绵算

25、法：算法：Sierpinski_sponge标题：标题： Sierpinski海绵海绵变量：端点坐标变量：端点坐标 x1,y1,z1, x2,y2,z2, x3,y3,z3, x4,y4,z4, x5,y5,z5, x6,y6,z6, x7,y7,z7, x8,y8,z8; 函数：函数： glVertex2s(x,y) （顶点坐标函数） glVertex2s(x,y,z)（顶点坐标函数）D=log20/log3=2.7268 Menger海绵海绵哈尔滨工业大学计算机学院 苏小红35void CRenderDlg:lft(double x, double y, double z, double

26、l)double x1,y1,z1, x2,y2,z2, x3,y3,z3, x4,y4,z4, x5,y5,z5, x6,y6,z6, x7,y7,z7, x8,y8,z8; x1=x-l/2; y1=y-l/2; z1=z-l/2; x2=x+l/2; y2=y-l/2; z2=z-l/2; x3=x-l/2; y3=y-l/2; z3=z+l/2; x4=x+l/2; y4=y-l/2; z4=z+l/2; x5=x-l/2; y5=y+l/2; z5=z+l/2; x6=x+l/2; y6=y+l/2; z6=z+l/2; x7=x-l/2; y7=y+l/2; z7=z-l/2; x

27、8=x+l/2; y8=y+l/2; z8=z-l/2;哈尔滨工业大学计算机学院 苏小红36void CRenderDlg:Drawscene(double x, double y, double z, double l,double n) if (n 1) /画一级Sierpinski海绵 l:=l/3; lft(x-l,y+l,z-l,l); /后左上 lft(x,y+l,z-l,l); /后中上 lft(x+l,y+l,z-l,l); /后右上 lft(x-l,y,z-l,l); /后左中 lft(x+l,y,z-l,l); /后右中 lft(x-l,y-l,z-l,l); /后左下 lft(x,y-l,z-l,l); /后中下 lft(x+l,y-l,z-l,l); /后右下 lft(x-l,y+l,z,l); /中左上 lft(x+l,y+l,z,l); /中右上 lft(x-l,y-l,z,l); /中左下 lft(x+l,y-l,z,l); /中右下 lft(x-l,y+l,z+l,l); /前左上 lft(x,y+l,z+l,l); /前中上 lft(x+l,y+l,z+l,l); /前右上 lft(x-l,y,z+l