分数维的山峰与植物
http://www.newdu.com 2024/12/03 08:12:08 人民教育出版社 佚名 参加讨论
分数维的山峰与植物 大厅的灯光暗下来，帐幕徐徐打开，银幕上出现了根据J．R．R．Tolkien的三部曲“Lord of the Rings”所改编的电影。Frodo在一个开阔的峡谷里溜达着。远处，锯齿状的冰雪覆盖着的山峰耸入云端。近处有些不知是什么种类的奇花异木在阳光下闪烁。转眼，屏幕上的奇景变成了一个男巫凝视着一只水晶球，在这球体的中央出现了一个堡垒，火焰正从它的城垛里窜出来。 虽然现在还很难说Frodo是否会在这样的电影里出现，但我肯定那些山峰、树木、水晶球以及火焰都会奇妙地出现在银幕上。这个成就主要将归功于Pixar公司(即从前的Lucasfilm计算机绘图实验室)所开发的软件和硬件。有家用计算机的读者都能够在计算机上作出基本类似于这些东西的图形来。由于本文篇幅所限，不能在此对水晶球和火焰作一个广泛深入的论述，但还是能够揭示产生它们的基本原理。 在上面描述的假想的电影中，我们可以把摄像机移向Frodo身后的那些山峰上。人们可能从来没有见过比这些山峰更令人生畏的大片陆地了。每一个大的山峰都由一些较小的山峰构成，而这些较小的山峰又由比它们更小的山峰组成，如此下去就形成了一种小山峰的无穷回归。即使一个有皮质脚的滴水嘴一样的海怪站在这样一个犬牙般的地方也会感到难受(见彩图11)。 原则上，这样的一种山的图形是容易作出来的。为简便起见，我假定这山覆盖了一个三角形的地面。找出每条边的中点，用三条线段把这三个中点连起来。就把这三角形分成了四个较小三角形。用同样的办法再分这四个小三角形。这一过程不断进行，直到达到分辨率极限或计算时间极限为止。结果是得到一大堆令人感到枯燥无味的三角形。如果要使这图形变得生动一些，可以在作图过程中加进一条有关垂直方向上的规则：每当新的中点画在图上时，就使其向上或向下移动某一随机量。通常这个随机数必须随三角形的逐渐变小而减少。这一规则把那些三角形变成弄皱了的山峰和褶皱(见图)。 为什么这一种方法会作出那样逼真的山峰图案呢?答案在于这个过程中产生了一个分数维图形，即当图案不断放大时会显露出更多的细节的图形。分数维形态在自然界似乎是随处可见。我们可以用一个关于海岸线的例子解释分数维图形的基本概念。假设我们要用一根l000米长的测量杆测量出法国海岸线的长度，那么就得沿着海滩向前一杆一杆地进行艰难的测量，同时数出有多少个l000米。然而这样会把许多小的海湾和海岬遗漏掉，所以用这种办法测出的最后得数是不那么准确的。用一根l米长的测量杆重复这一过程，会得出一个更精确、数字更大的结果。但即使如此，也有大量的小海湾和岬地被遗漏掉了。无疑，用一根l厘米长的测量杆结果就会更为精确。 一般规律是，当测量杆变小时，测出的海岸线长度会增大。测出的长度与测量杆杆长之比率为一个专门值，这个值称为分数维。分数维与通常说的维不同，它往往被表达成一个分数，而不是一个整数。例如我们讨论的海岸线的维数可能就是一个3/2的分数维。可以把这样的一种形状想象成一个介于一维形状(直线)和二维形状(平面)之间的中间形状。如果海岸线比较直，其分数维就接近于1。如果海岸线很曲折，其分数维就接近于2，此时它几乎填满一个二维平面。 自然界的分数维模型实际上隐含了细节的无穷回归。从计算机绘图的角度来看，无穷回归是无关紧要的问题；只要景物看来是具有各级放大水平上的细节就行了。在达到屏幕分辨率的极限之前，计算机上生成的山的特征就与上述分割过程中最终所得的三角形的特征一样精细。完整的山峰绘制算法太长太复杂，无法在此作足够详细的介绍。但有一个简单的程度可以绘出Mandelbrot峰的断面，它称为MOUNTAIN。该程序体现了沿垂直轴随机移动中点这一基本早想。开始时是一条水平线段。确定其中点，使其向上或向下移动一段随机地确定的距离，然后把由此产生的两个线段再分，并使其各自中点也按此规则移动。用类似于再分三角形的方法可把这一过程不断地进行下去。 程序MOUNTAIN有两个数组，叫做points和lines。其作用是保持计算机屏幕上的山的轮廓。每个数组分别有两列和足够多的行(比如说2048行)以方便地调整屏幕分辨率；points的两列是坐标值，而lines的两列则是下标。每条线段定义为数组points中表明该线段终点坐标的一对位置。观察一个普通的多边形通过一连串的再分后形成山的轮廓这一过程是非常有趣的，所以程序MOUNTAIN使每一次图案的形成都处于用户的控制下。在—次主循环结束时，程序询问用户是否需要另一次迭代，如果回答是肯定的，那么执行会再返回此程序的开头。 主循环的作用是把当前的点与线段的集合变成大1倍的新集合。为实现这一点，它一次一行地对数组lines进行扫描，查寻其对应点的下标并从数组poinlts中检索出它们的坐标。在已知某一给定线段的两个端点坐标后，程序就可以计算出该线段的中点坐标，同时随机地改变y坐标的值。下面所列出的算法过程为程序的编制提供了充分的基础，其中变量j和k是指数组points和lines中当前正保持着再分的最新结果的那些“行”。变量pts和lns记录在进入主循环之前构成山的点和线段的数目。开始时j等于pts，k等于lns。下标i从1到lns。  MOUNTAIN程序的这一部分在很大程度上是不言自明的。当第j点的坐标计算出来后，下标j就被存贮起来作为第i条线段的第二个点和第k条线段的第一个点。第i条线段的第一个点与其原来的一样，而第k条线段的第二个点与第i条线段原来的第二个点，即带有下标b的那个点相同。当循环最终计算后，pts和lns必须分别复置为j和k的最新值。变量range是在程序的开头由用户确定各再分点在垂直方向上随机移动量的最大值。每次循环结束时，该变量就要除以2，使得这一随机移动量与线段尺寸成比例地减小。函数random(range)用于表示在0和变量range的当前值之间所选择一个随机数。 如果Frodo身后的那些山峰是令人难忘的，那么，他周围的村木和植物就更是令人难忘。它们既逼真又奇特。之所以逼真，是因为它们有与真实植物一样的分枝，而之所以奇特是因为它们不是常见的物种。大概是图形设计者有太多的参数可以任他使用，因此他禁不住要创造一些新的植物种类。 这些新的植物种类被叫做“嫁接”(graftal)植物，因为它们是在图形(graph)的基础上形成的，且有内在的的分数维性质。这里所谓的“内在分数维性质”，指的是用于生成植物图案的基本拓扑特征的规规则可以(但实际上没有)应用于屏幕分辨率的极限。简言之，植物的细枝条不会无限地回归成更小的枝条。一旦作为植物的基础的图形发展起来，计算机就能用大小、颜色、厚度、质地等解释植物的图形，从而把它变换成无数的令人信服的植物种类。  某一给定植物所据以形成的图形是由L系统产生，这种系统是丹麦生物学家和数学家Aristid Lindenmeyer在1968年提出的一种语法类别。一个L系统实际就是一套用于从旧的字符串中推导新的字符串的规则。例如，根据下列规则，用数字0和1以及符号[和]能够生成一系列复杂的植物： 0→l[0]1[0]0 l→11 [→[ ]→] 为了弄清如何应用这些规则，我们从由单个的符号0组成的字符串开始。将箭头左边的每一个符号都用与其对应的右边的符号来代替，就可以一个接一个地得到下列的字符串： 01[0]1 [0]011[1[0]l[0]0]ll[1[0]1[0]0]1[0]l [0]0 把每个数字(0或1)当作一条线段，每个括号当作一个分支点，就可把这样的字符串变换成树一样的图形。0和1所代表线段的长度相等，其区别在于0线段的外端上要加一片叶子，而1线段上则什么也不加。 例如字符串1[0]1[0]0的茎是由三个不在括号内的符号组成的。最下面的是1线段，中间也是1线段，顶部则是0线段。两根枝条(每根均是一条0线段)从茎上长出来。第一根枝条长在第一条1线段上，第二根枝条则长在第二条1线段上。读者可以试画一下树茎最初几次生成的图案。为了使植物更逼真，对这个模型可以加上另外一些解释性的规则；例如，对于任何给定的茎(不管它是否主茎)，都可以使枝条轮流地从左右两侧长出。 一个叫PLANT的由两部分组成的程序产生上述序列中的第n个字符串，然后把它表示成一个线段图。在该程序的第一阶段，PLANT将它所生成的字符串保存在被称为String A及string B的两个符号数组中。每一代植物图形轮流地占据两个数组中的一个，即某一数组中所存贮的那一代是由另一数组中所存贮的上；代得来的。也不一定非要在数组中存贮符号。只要程序的代换过程是正确的，数字0，l，2和3也完全可以。 L系统规则在条件语句中体现出来；例如可以采用下面这段算法编码把StringA的第i位上的1个0变成string B中的九个新的符号： 如果stringA(i)＝0，那么 stringB(j)←1 stringB(j+1)←2 stringB(j+2)←0 stringB(j+3)←3 stringB(j+4)←1 stringB(j+5)←2 stringB(j+6)←0 stringB(j+7)←3 stringB(j+8)←0 j←j+9 这里0和1代表它们自己，而2和3分别代表[和]，如果string A的第i个符号是0，那么，程序把序列l，2，0，3，l，2，0，3，0插入数组string B中以下标j(即数组string B的尚未填入符号的第；个年置)开头的九个连续位置上。程序PLANT的第一阶段中的一个单循环就含有四个上述的条件语句，每个语句相应于可能遇到的一个符号。循环用下标j来指出当前这一代中正被处理的那个符号。循环执行的次数依用户的愿望而定。在每一次生成后，程序PLANT会询问用户是否希望另一个更长的字符串。 PIANT的第二个阶段(即绘图阶段)把第一个阶段产生的字符串变换成一个图形。它循环地执行这一过程：只要左括号(或2)没有出现，它就在一个给定方向上绘出一系列线段。当碰到某一对括号中的左括号时。程序就在一个新的方向(从前一个方向反时针转45°)上绘出后面的线段。当对应的右括号出现后，这一过程就终止。这时画出一片叶子，它的形状和颜色都留给读者去想象。第二个左括号的出现使该程序又重复进行。只是现在的方向是顺时针45°。其他的工作都是自动进行的。 PIANT用了一个随被绘出的植物的复杂性而定的比例因数。例如，第n代植物的高度大约为2n条线段，如果屏幕的高是200个像元，那么每根线段就必须短于200／2n雄心勃勃的读者们无疑会尝试生成语法、枝条角度及叶片形状等方面的新花样。如果具有这些新花样的图案在同一屏幕上生成，植物和树木的风景就会出现了(当然不是很逼真的)。 Pixar绘图计算机的心脏是一个有24兆字节，2000×2000像元的存贮器，其分辨率对大多数应用是足够的。此外，每个像元由48个存贮位表示，足够存贮色采和透明度方面的信息。Pixar绘图计算机的大容量存贮器由四个高速并行完全可编程序的处理机操纵。它们每秒钟能执行约4000万条指令，其速度比普通的计算机大几个数量级。显示装置与存贮器问的数据交换速度可达每秒4．8亿个字节。 Pixar绘图计算机预定用于医学成像、遥感、工程设计及动画片制作这些领域中。也许还会用来制作我在本文开头所描述的假想电影。 (责任编辑：admin) |