迭代函数系统及向量图形学在美学中综合应用.doc

电信学部专业英语作业 学生姓名：国兴 学号：21009329
迭代函数系统和向量图形学在美学中的综合应用(Integration of iterated function systems and
vector graphics for aesthetics)
Slawomir Nikiel
Computer & Graphics 30 (2006) 277-283
摘要
分形是众多的计算机图形学应用中必不可少的一部分。分形建模中的相对简单的实现就能够产生出无数的复杂而又吸引人的图像。分形图像生成这一主题已在文献中探讨的足够详细了。许多分形模型都是基于光栅图像显示（raster representation）的，但是这一方法在交互式建模和3D图形实现方面是非常不合适的。另一方面，向量几何学模型（vector-geometry models）现在在商业图形设计包装中很受欢迎。这就产生了一种对于分形模型的向量图像显示（vector representation）的需求。本文介绍了基于向量的迭代函数系统（iterated function systems，IFS）模型和辅助性的渲染算法（rendering algorithm）。本文的解决方案具有高性能和良好的建模灵活性。当IFS（迭代函数系统）与向量制图法结合起来之后，就会呈现出一种新的艺术表现形式。

关键词：分形建模；图像合成；渲染算法；交互式设计；向量制图法

1. 引言

Barnsely的工作主要集中在分形建模和分形图像压缩中的仿射变换的应用上。这些迭代函数系统（IFS）都已经被彻底的研究过了，尤其是二维的（2D）二元的和灰度的图像显示[1-4]。用于生成各种各样的2D的IFS分形光栅图像的程序有着广泛的用途[5]。IFS绘图法对于研究图像的形状和纹理而言是一种非常有用的方法。它通过一些简单的几何变换形成了一套用于交互式图像构造的基本工具。2D的二元IFS是一种最典型的IFS的光栅图像显示模式。关于基于向量的分形模型，我们可以从PL系统中得到更多的了解，PL系统常用来生成植物和一些简单的动物模型，像蜗牛、蚯蚓等。本文给出了一种可以应用于IFS的实用的向量绘图法。它的优点是生成的向量对象可以用法线来描绘，因此，这样就可以把光照和阴影应用在对象上面。我们也可以把分形对象包含到3D建模包装里。

2. 背景知识

IFS由Hutchinson提出，它是基于数学基础的。IFS分形有着优美的递归的定义形式—— 一个分形是由一组它自身的变换后的复制品拼贴而成的，自相似性是它的固有的性质，而且它可以无限的缩放。变换是由一组仿射映射完成的。一个平面上的仿射映射就是在（二维实数空间）中旋转、缩放、剪切和平移的组合。任何对于平面的仿射变换都有如下形式：
， （1）
这里是平面上的任意点。
我们可以这样说，一个在平面上的IFS是由作用在一个度量空间上的有限的几个仿射变换所给出的。没有任何的特殊条件强加于这些映射上，除了他们的收缩。在一组仿射变换（公式（1））中，每个映射都伴随着一个他们各自的收缩因子。在2D的线性的IFS中估测这些因子相对来说是比较容易的。然而，当考虑到其他情况时就会变得复杂了，比如非线性的IFS。一个IFS的本质特征之一就是它的独一无二的吸引子集合，它是一个分形，并且是封闭有界的[1]。

定义一 如果一个IFS 是收缩的，那么存在一个唯一的集合
， （2）
我们称之为的不动点（吸引子）。

IFS可以被看作是一般动力学系统中能够包含常常伴随着一些奇异吸引子的不动点的一个子集。如果我们将那些收缩因子都保持在1.0附近，我们可以看到这个IFS的行为像是一个经典的非线性系统。为了获得界限更清楚的吸引子，我们需要让所有的收缩比例都低于1.0，即。这样的IFS被称为是一个双曲线的IFS。

3. 向量IFS模型

IFS渲染算法一般是在点集或数个点集上进行，这样可以画出平面图像或是体积空间。Tesseral Synecdoche算法的作者提出我们可以在IFS代码中插入非缩放参数，从而使其得到进一步的发展。向量递归渲染（vector recursive rendering，VRR）算法（将在下节详细阐述）把递归函数调用应用于空间向量的变换上。向量可以按照一个点的坐标和一组角度值来描绘，或者根据空间中两个点的坐标来描绘。
中心思想就是只变换决定一个向量的那两个点。递归程序成对的改变所有点的位置和方向。因为双曲线的IFS使所有点都收缩，所以，在每次映射后定义一个变量的那一对点需要归一化的处理。这些向量是容易计算的，而且，一旦都求出了，他们可以和任何向量计算机图形学模型结合在一起，包括使用构造实体几何（constructive solid geometry，CSG）的基本实体。

4. VRR算法

在平面上的VRR算法可以用下面的伪代码来描述：

选择两个初始像素值q0(x0,y0)，q1(x1,y1)
选择最大迭代次数设为L
Procedure VRR(q0(x0,y0),q1(x1,y1),L)
Begin
For i=1 to N do
Begin
Apply q2=wi(q0)
Apply q3=wi(q1)
If L == 0 then Apply Plot_line(Normalize(q2,q3))
Else call VRR(q2,q3,L-1)
End for i
End

VRR算法是一个经典的递归算法。它的终止条件是当前的递归层次L等于零。VRR算法第一次调用的参数是VRR[(0,0),(1,1),10]，换句话说，用一个简单的初始参数和递归层次的最大值来递归的调用VRR函数。当然也可以把这种表示法推广到3D空间中的任何向量。VRR算法可在有限时间内快速逼近IFS的吸引子。
对于一个给定的IFS码我们可以估测它的最大迭代次数L，但是对于向量对象来说，情况有些不同。与光栅图像渲染算法主要的不同就是我们并不在空间中的点集上进行操作，而是在任何一种计算机图形学对象（圆，三角形，立方体，或者是一个CSG实体）里的向量上进行。所有的计算机图形学对象的大小都大于一个像素，因此，仅仅通过这个递归算法的数十步就足够生成有趣的结果了（图1）[9]。

图1. 作用在三角形上的IFS的几个阶段

在VRR算法的最简单的实现（没有包含归一化进程）中存在一个问题。我们知道一个双曲线的IFS是收缩的，因此在每次的递归映射后所有点都离得更近。我们需要执行一个归一化进程（即伪代码中的Normalize函数）来使所有的向量在递归迭代的每一步都达到统一的大小尺寸（图2）。我们可以引入一个收缩因子sf来使空间中两点的收缩失效。在递归渲染的每一层sf都被用来对所有向量进行归一化。

图2. 用不同的归一化因子进行渲染的IFS吸引子（80%，100%和110%）

图3. 用线和圆来构建的向量IFS吸引子2D实例

用表示，用表示，在一个平面上（坐标值为像素），我们可以使用根据欧几里得几何度量计算方法得出的距离：
。 （3）
sf为一个大于1的收缩因子。为了画出一个缩放之后的向量，我们使用了两个点，其中，一个作为基点，另一个作为方向点。设向量的方向参数为，计算如下：
。 （4）
计算的坐标：
。 （5）
考虑双曲线的IFS的最简单的实现，我们画出一条线（）来表示已被归一化了的向量（图3）。归一化进程在每一层递归的时候都重新调整了所有向量。VRR算法速度非常快，而且可以应用于任何向量图形基元上。

图4. 作用于一个三角形上的IFS的结构

图5. 向量IFS模型的3D实例

5. 应用

我们用线和圆实现了最简单的2D向量IFS，其中向量决定了线的长度和圆的中心及半径（图3）。三角形是一种具有明显方向的几何图形，因此，由VRR算法得到的向量不仅会改变它在平面上的位置，还会改变它的方向。一个向量可以依附在一个三角形的底边（两个顶点）上。第三个顶点可以根据以向量为底边的等边三角形的顶点来构造。该顶点是由底边向量旋转120度之后得到的（图4）。在VRR算法中经过几次迭代后，我们可以清晰的看到潜在的IFS吸引子的结构（图5）。我们可以用一个长方形来实现同样的渲染算法。长方形可以被看作是一个具有纹理图像的几何结构，经过变换之后映射于屏幕上。与IFS的交互式的渲染相类似的方法在基于图像的渲染算法中已被实现[10]。
一对点也可以在3D空间里被转换。它们可以用X,Y,Z坐标来描述一个向量，并在VRR的每一层改变它们的位置和方向。就像在2D空间里的情况一样，我们也可以使一个向量依附于任何3D CSG基元上，比如球体、立方体、圆柱体或者圆锥体（图6）。

图6. 向量IFS吸引子的3D实例（各子图中的IFS吸引子结构都相同，但使用了不同的构建模块）

6. 性能

在计算机图形学的实时应用中需要有良好的性能。在处理分形的交互式构建时，生成IFS吸引子所需的时间应尽可能的短。但是，渲染所用的总时间难以计算，因为这取决于很多因素，包括数字图像的绘制（例如图像的分辨率和图层的数量）、显卡的性能、硬件的配置、操作系统以及程序的运行环境等等。IFS渲染算法的基本思想可能是用尽量简单的方式实现目标，或者是使结果高度的最优化，这也会影响完成一个IFS吸引子图像所需的时间。
我们可以计算总的迭代次数（number of iterations，简记为NoI），现考虑二元图像或者是灰度/伪彩色图像，显示于一个8位（256色）的且已给定分辨率（）的视窗里。如果我们假定当前显示屏的分辨率为，，那么我们就能够粗糙的估算出一个IFS分形图像充满整个屏幕所需的迭代次数。我们考虑循环指令和读写操作。在下面的研究中没有将堆栈操作和逻辑操作的开支计算在内。
我们将讨论一个带有概率参数的双曲线的IFS，且它的各部分都是不重叠的。这个IFS由几个线性方程组成，且不包含聚点。
IFS ，。我们假定此IFS的吸引子图像充满了视窗屏幕。图像可能是二元的（黑白两色）或是单色的/伪彩色的（基于调色板），且不进行缩放。
VRR算法操作于两个点上，且在每次新的位置判定的时候都需要归一化。归一化进程牵涉到反三角函数的计算，这是很费时间的，耗时是不含归一化操作的算法的四倍。这里所说的“4倍”是由图形引擎在进行和不进行归一化操作的比较试验中得出的大概的估测值。我们需要进行L次递归来充满整个屏幕，计算如下：
。 （6）
我们应该记得构造VRR算法是为了使用计算机图形学图像的基元。现考虑应用于直径为10个像素的实心圆的VRR。有
， （7）
如果按照上面所提出的条件计算的话，L的值应该在5附近。
因此，完成此IFS吸引子图像所需的总的迭代次数为
。 （8）
这个方法看来速度非常快而且确实适合于实时的渲染。值得注意的是，我们是用小实心圆而不是像素点来近似IFS吸引子的。下面的表1给出了由一个IFS得出的帧频，此IFS是由两个映射组成的，且最大的递归层次数为十。所有从第五层到第十层的向量对象都被画出，基元（向量、正方形、圆、球体、立方体和二十面体）的总数为2016个。测试是在Microsoft Windows环境下进行的。应用程序是用Java3D语言写出的，且在Mozilla中运行。应用程序的测试平台为Intel Pentium 4，4.0 GHz CPU，512MB内存和带有256MB显存的ATI Radeon 9800XT显卡。

表1. 一个IFS渲染程序实例的性能测试
图形基元
2016个对象
对象生成所用时间
（秒）
渲染/可视化
（帧每秒）
向量（2D）
正方形2D）
圆（2D）
球体（3D）
立方体（3D）
二十面体（3D）
0.15
0.31
0.13
0.187
0.36
0.42
未测试
未测试
未测试
100
100
100

7. 结论及将来的工作

艺术效果的图像合成软件的用户们往往找不到可以让他们直观地控制对象生成的工具。例如，现有的工具一般不能够根据用户的拖拽和旋转动作来直接的改变对象的结构。因为IFS模型使用了经典的几何变换，这使得创造出易于使用的分形设计环境成为可能。本文介绍了在实时的CG建模中IFS的2D和3D模型的向量绘图法。基于这种方法，平面图像合成和真彩色的3D对象都可以绘出。文中的方法拓宽了分形建模在交互式的计算机图形学中的应用领域（图5和图6）。

致谢

本文所使用的IFS渲染程序的Java-3D代码中部分是由Szymon Zmudzin在做一名Socrates-Erasmus与Hull大学的交换生期间编写的。

参考文献

[1] Barnsley MF. Fractals everywhere, 2nd ed. Academic Press: San Diego, CA;1993.
[2] Barnsley MF. Fractal image compression. Wellesley, MA: Academic Press; 1993.
[3] Barnsley MF, et al. Solution of an inverse problem for fractals and other sets. Proceedings of the National Academy of Sciences 1986;83:1975-7.
[4] Barnsley MF, Demko S. Iterated function systems and the global construction of fractals. Proceedings of the Royal Society, London 1985;A399:243-75.
[5] SPANKY Fractal Database, http://spanky.triumf.ca/.
[6] Prusinkiewicz P, Lindemeyer A. The algorithmic beauty of plants. New York: Springer; 1990.
[7] Bell SB. Fractals: a fast, accurate and illuminating algorithm. Image and Vision Computing 1995;13(4):253-77.
[8] Nikiel S, Stec P. The recursive rendering algorithm for iterated function systems. In: Proceedings of the conference in methods and systems in science and engineering. Cracow, Poland. 1999. p. 75-80 [in Polosh]
[9] Zmudzin S. Constructive solid geometry and iterated function systems, MSc thesis, Faculty of Electrical Engineering, Computer Science and Telecommunications, University of Zielona Gora, 2001, p. 73p [in Polish]
[10] VanWijk JJ, Saupe D. Image-based rendering of iterated function systems. Computers & Graphics 2004; 28(6):937-43.
8