分形理论能很好地描述一大类复杂无规则的几何对象, 如蜿蜒曲折的海岸线, 繁茂的树木植物, 起伏不定的山脉等, 因此在自然景物的仿真绘制中得到了广泛应用。树木一直是虚拟现实, GIS等领域的重要描述对象, 而分形为人们表达树木实体提供了很好的方法, 因此近年来对分形树的研究也逐渐成熟[1]。通常对分形树的描述有递归算法、IFS算法和LS算法, 其中由Bamsley提出的分形叠代系统IFS具有较大的影响力, 在植物与树木的计算机生成方面显示出明显的优势。近年来研究人员对IFS算法生成2D、3D树进行了大量深入的研究, 并对构造分形3D树的IFS码的获取提出了切实可行的方法, 本文对原有的IFS算法提出了改进, 利用改进的算法实现了3D树的构建, 并实现了3D树受不同方向不同风力影响而摇曳的各种形态。
1 带参IFS理论
1.1 叠代函数系统IFS
一个叠代函数系统由一个完备的度量空间 (X, d) 和一个有限的压缩映射集Wn:X→X及其相应得压缩因子Sn, n=1, 2, …N所组成, 因此IFS可表示为{X;nW, n=1, 2, …, N}, 其压缩因子便是S=MAX{nS;n=1, 2, …N}。
1.2 带凝聚的IFS
设{X;W1, W2LnW}为具有压缩因子0≤S≤1的IFS, 如果定义变换0W为:Φ (X) →Φ (X) , W0 (B) =C, ∀B∈Φ (X) , 则0W称为凝聚变换, C为凝聚集, 则{X;W0, W1, W2LnW}称为带凝聚的IFS[2]。
1.3 带参量的IFS
设 (X, d) 是度量空间, {X;W0, W1, W2LnW}是一个带凝聚的IFS, 令0W:P×X→X是以0≤s≤1为压缩因子的压缩映射族, 亦即对每个固定的p∈P, W (p, ·) 是X上的一个压缩映射, 对每一个固定的x∈X, W在P上是连续的, 则W的不动点xf连续地依赖于p, 相应地, 我们称此时的IFS为带参量的IFS。
2 摇曳的3D分形树的实现算法
2.1 大自然中风中树的特点
风向:较常见的风向一般是和地面近似平行的, 即风向的方向向量可定义为{nx, 0, nz}。
摇曳树的特点:树摇曳时, 一般是和风向垂直的分支摇摆幅度大, 而且幅度由外到内逐渐减小;树顶摇曳幅度大, 由上到下幅度逐渐减小。树枝摇曳的方向为风向。
2.2 带依赖参数的变换矩阵的确定
根据树枝摇曳的特点, 风从 (nx, 0, nz) 方向吹过来, 整个树身近似于绕直线nx×x+nz×z=0旋转, 同时两边的树枝的摇摆可看作近似于绕Y轴小幅度旋转。这里为保持更加真实性, 要求: (1) 旋转幅度不要过大; (2) 树顶影响最大, 往下影响逐渐减小, 我们可采用不同阶段的风力因子来控制。
根据IFS思想, 3D树的主枝到分枝的生长, 可近似认为由主干绕过树根 (原点) 的向量为 (x, 0, y) 直线作旋转变换, 再进行压缩、平移变换而成。其中仿射变换的形式可简写为 () nnnnBWA+=t BS, 其中nS为压缩因子, nA为仿射变换矩阵, nt为平移量。基于IFS思想, 我们可定义一颗3D分形树为:r S=θβα) , , , (, 在这里 () aaar=z, y, x, r的三个分量分别代表x轴, y轴, z轴方向的偏移量, α、β和θ分别是主枝依次绕x轴, y轴, z轴的旋转角度。设3D树的变换矩阵分别为:分枝偏移量矩阵, 绕x轴α角度矩阵, 绕y轴β角度矩阵, 绕z轴θ角度矩阵。求的逆变换分别为根据分形树定义有。β角θ和依据我们的需要而定 (即希望分枝的形态) , 此时的nA为无风时的变换矩阵, 为了加入树顶向风向摇曳特征, 我们设风向为, 风力为nPow, 则加入参数后的nA为:R当然, 还要加入和风向近似垂直的两侧树枝向风向方向摆动, 两侧树枝和风向越接近垂直摆动幅度越大, 此时可看作树枝绕Y轴旋转, 而且两侧树枝旋转方向相反。设树枝当前向量为风向为则同风向向量L垂直的向量为计算向量L与树枝向量Ln的夹角余弦:的范围为:, 当时, 即树枝与风向相同时影响最小, 当ω为0或π时影响最大。
2.3 IFSP码的确定
通常获取二维IFS码所依据的是Barnsley的拼贴定理, 即:设{ϖ, Pj|j=, 1, 2L, N}是一组IFS码, 压缩比为C, e是任意小的正数, T为R2上给定的边界闭合的子集, 假设ϖ已选定, 使得那么这里, B为该IFS的吸引子;h为Hausdorff距离, 同样将此定理的应用扩展到三维空间, 依此来判断由一个3D-IFS经连续变换所产生的吸引子与给定的初始集的相似程度, 三维空间上的仿射变换的形式可简写为。所以确定一组IFS码, 就是确定这组压缩映射中每一个ϖ的变换系数An和tn。在带参IFS中, 我们最终也是要确定仿射变换ϖ的变换系数, 由于我们加入的参数可表示ϖ的变换系数, 所以我们用参数代替An的系数作IFS码。由本文前面所论述, 我们可确定IFS码包括:分枝绕X轴的旋转角度, 绕Y轴的旋转角度β, 绕Z轴的旋转角度θ, X方向上的压缩因子Sx, Y方向上的压缩因子Sy, Z方向上的压缩因子Sz, 风力影响因子wn, 仿射变换的概率pn, X方向上的偏移量mx, Y方向上的偏移量my, Z方向上的偏移量mz。
3 图形绘制实例
根据上述思想, 制作一个四叉树, 初始化树干的方向为 (0, 1, 0) 。要注意的是以上wn一项为风力风力影响因子, 它控制树的每个部位受风力的影响力, 从数值可以看出, 树的上部的值为0.6, 即受风力影响最大, 旁枝分别为0.45, 0.45, 0.35, 0.25, 树干下部受风力影响最小为0.1。
4 结果分析
从实验结果可以看出: (1) 通过修改树枝旋转的角度可以有目的的改变树的形态。 (2) 通过改变风向和风力可以控制树的摇曳形态。由此, 本文利用分形算法模拟了一个树的多种形态。
摘要：论文首先阐述了带参IFS理论, 然后分析了自然界中在风中树的摇曳形态, 根据IFS理论定义了3D分形树的一般形式, 然后确定仿射矩阵和参数, 最后给出了一个四叉树的IFS码, 并绘制了此3D分形树在风中摇曳形态。
关键词：分形树,IFS,摇曳
参考文献
[1] 赵欣, 林和平.三维分形树木模型在3D GIS中的应用[J].吉林大学学报, 2003, 21 (3) :307～311.
[2] 李水根, 吴纪桃.分形与小波[M].北京:科学出版社, 2002.
[3] 孙家广, 等.计算机图形学[M].北京:清华大学出版社, 1998.