Lode 的计算机图形学教程

递归树

简介

分形具有自相似性。递归树就是满足这一特性的一类图形。其思路如下：先画树干，然后树干分裂为两个较小的分支，每个分支再分裂为两个更小的分支，如此无限循环。

两分支递归树

要编写这样的递归树，当然需要一个递归函数。该函数绘制一个分支，然后再次调用自身绘制两个新分支，由于它又调用了自身，这两个被调用的版本又会再次调用自身，如此循环。每次调用时参数都会改变，以便在正确的位置、以正确的角度和大小绘制分支。还有一个终止条件，在递归 n 次后停止，否则计算永远不会结束，陷入无限循环。在第 n 步递归时，需要绘制 2^n 个分支。

首先声明一些变量和递归函数。"pi" 可以方便地以弧度表示角度。"maxRecursions" 是递归函数的终止条件。"angle" 是常量，表示每个新分支相对于父分支的角度。"shrink" 表示每个新分支相对于父分支缩小的比例。你可以修改这些值，这里的值经过选择，能产生众多漂亮效果之一。

double pi = 3.1415926535897932384626433832795;

int maxRecursions = 8; //never make this too big or it'll take forever
double angle = 0.2 * pi; //angle in radians
double shrink = 1.8; //relative size of new branches

void recursion(double posX, double posY, double dirX, double dirY, double size, int n);

主函数除了设置屏幕之外，只是调用递归函数。递归函数参数中的 "h/2.3" 是第一个分支（树干）的初始长度。坐标是第一个分支的起点和方向向量。

int main(int argc, char *argv[])
{
  screen(320, 240, 0, "Recursion Tree");
  cls(RGB_White); //make background white

  //Now the recursion function takes care of the rest
  recursion(w / 2, h - 1, 0, -1, h / 2.3, 0);

  redraw();
  sleep();
  return 0;
}

接下来是递归函数，它只绘制一条线并多次调用自身，但最终会生成一棵庞大的树！

以下是绘制线段的部分。首先对线段进行屏幕裁剪，然后绘制。线段从 (posX, posY) 画到 (posX+dirX, posY+dirY)。线段的位置和方向以向量形式给出，而不是起点、角度和大小，因为方向向量更易于操作。size 参数本身不直接用于绘制线段，只在后面计算下一分支的方向向量时使用。若达到最大递归次数，函数在绘制线段后立即返回，不再调用自身。

void recursion(double posX, double posY, double dirX, double dirY, double size, int n)
{
  int x1, x2, y1, y2;
  int x3, x4, y3, y4;
  x1 = int(posX);
  y1 = int(posY);
  x2 = int(posX + size * dirX);
  y2 = int(posY + size * dirY);
  if(clipLine(x1, y1, x2, y2, x3, y3, x4, y4))
  drawLine(x3, y3, x4, y4, ColorRGB(128, 96, 64));

  if(n >= maxRecursions) return;

函数的第二部分计算新分支的位置（即上一分支的终点），并根据当前分支的大小和方向计算新分支的方向向量。新分支按角度旋转，正弦和余弦公式实际上是旋转矩阵的计算。然后以新分支参数再次调用递归函数。这样做两次：一次向右旋转的分支，一次向左旋转的分支。

  double posX2, posY2, dirX2, dirY2, size2;
  int n2;
  posX2 = posX + size * dirX;
  posY2 = posY + size * dirY;
  size2 = size / shrink;
  n2 = n + 1;
  dirX2 = cos(angle) * dirX + sin(angle) * dirY;
  dirY2 = -sin(angle) * dirX + cos(angle) * dirY;
  recursion(posX2, posY2, dirX2, dirY2, size2, n2);
  dirX2 = cos(-angle) * dirX + sin(-angle) * dirY;
  dirY2 = -sin(-angle) * dirX + cos(-angle) * dirY;
  recursion(posX2, posY2, dirX2, dirY2, size2, n2);
}

结果如下图所示：

扩大屏幕非常简单，只需修改 screen 函数的参数，其余代码都是相对于屏幕大小计算的。

以下是一个替代的主函数，会以不同角度不断重绘树。

int main(int argc, char *argv[])
{
  screen(320, 240, 0, "Recursion Tree");
  while(!done())
  {
    angle = getTicks() / 2000.0;
    cls(RGB_White);
    recursion(w / 2, h - 1, 0, -1, h / 2.3, 0);
    redraw();
  }
  return 0;
}

角度被设置为时间除以某个决定动画速度的系数。以下是不同角度下的几个结果：

多分支递归树

当然，不必只有 2 个分支，也可以有更多分支。例如，给它 3 个分支，让递归函数调用自身 3 次而不是 2 次。但这会大幅增加复杂度：若 n 为最大递归次数，仅最后一步就需要绘制 3^n 个分支，若 n=8，则有 6561 个分支！

扩展到 3 个或更多分支并不难，只需为新分支选择合适的角度。以下代码还有一个额外功能：在每个分支末端绘制一个绿色圆形，使其看起来像叶子。还可以单独开启或关闭最多 4 个分支，并为每个分支设置固定或随时间变化的角度。主函数中有不同的输入键，可以创建不同的角度和设置。

所有变量重新声明，每个变量的说明在注释中。分支 i 的角度为 angle*ai+ci，其中 angle 随时间变化。

double pi = 3.1415926535897932384626433832795;

int maxRecursions = 6; //max number of recursions
double angle; //angle in radians, this parameter changes with time
bool enable1, enable2, enable3, enable4; //enable or disable up to 4 branches
double a1, a2, a3, a4, c1, c2, c3, c4; //angle multipliers and adders for those 4 branches
double size, shrink; //the size of the first branch, and the relative size of the next ones

bool releaseSpace; //for input
int drawLeaves = 4; //what type of leaves to draw, if any

void recursionTree(double posX, double posY, double dirX, double dirY, double size, int n);

在主函数中设置一些初始参数，然后 while 循环开始。该循环每次绘制树，并随时间改变角度 a。

int main(int argc, char *argv[])
{
  screen(512, 384, 0, "Recursion Tree");

  //Initial settings
  enable1 = 1; enable2 = 1; enable3 = 1; enable4 = 0; //1 enables, 0 disables branch
  a1 = 1.0; a2 = -1.0; a3 = 0.0; a4 = 0.0; //how fast the angles rotate
  c1 = 0.0; c2 = 0.0; c3 = 0.2; c4 = 0.0; //absolute angle
  size = h / 3; //size of the first branch (the stem)
  shrink = 1.5; //relative size of the new branch

  while(!done())
  {
    angle = getTicks() / 3000.0;
    cls(RGB_White);
    recursionTree(w / 2, h - 1, 0, -1, size, 0); //This function will draw a single line and call itself a few times, creating a tree
    redraw();

	//Presets of settings
    readKeys();

循环的第二部分根据一些预设更改设置，如角度、递归次数等。如果你想，可以轻松修改或添加更多预设。releaseSpace 变量用于空格键：按下空格键后，只有在松开空格键之后才会再次更改设置。

    if(keyPressed(SDLK_a)) {enable1 = enable2 = enable3 = 1; enable4 = 0;a1 =1;a2 = -1; a3 = 0;c1 = c2 = 0; c3 = 0.2; size = h / 3; shrink = 1.5; maxRecursions = 6;} //default one with rotating branches
    if(keyPressed(SDLK_b)) {enable1 = enable2 = enable3 = 1; enable4 = 0;a1 = a2 =a3 = 0; c1 = 0;c2 = 2 * pi / 3; c3 = -2 * pi / 3; size = h / 2; shrink = 2; maxRecursions = 8;} //sierpinski triangle
    if(keyPressed(SDLK_c) {enable1 = enable2 = enable3 = enable4=1; a1 = a2 = a3 = a4 = 0; c1 = 0; c2 = pi / 2; c3 = pi; c4 = -pi / 2; size = h / 2; shrink = 2; maxRecursions = 6;}  //square
    if(keyPressed(SDLK_d) {enable1 = enable2 = enable3 = 1; enable4 = 0;a1 = a2 = a3 = 0; c1 = 0; c2 = pi / 2; c3 = -pi / 2; size = h / 2; shrink = 2; maxRecursions = 8;} //90?
    if(keyPressed(SDLK_e) {enable1 = enable2 = enable3 = 1; enable4 = 0;a1 = a2 = a3 = 0; c1 = 0.5; c2 = 0.1; c3 = -0.7; size = h / 3; shrink = 1.5; maxRecursions = 8;} //a random tree with 3 branches
    if(keyPressed(SDLK_f) {enable1 = enable2 = enable3 = enable4 = 1; a1 = a2 = a3 = a4 = 0; c1 = 0.1 * pi; c2 = -0.1 * pi; c3 = 0.2 * pi; c4 = -0.2 * pi; size = h / 4; shrink = 1.25; maxRecursions = 6;} //a random tree with 4 branches
    if(keyPressed(SDLK_g) {enable1 = enable2 = enable3 = 1; enable4 = 0; a1 = 1; a2 = -1; a3 = 2.0; c1 = c2 = c3 = c4 = 0; size = h / 2; shrink = 2; maxRecursions = 6;} //some animating tree
    if(keyPressed(SDLK_h) {enable1 = enable2 = enable3 = 1; enable4 = 0; a1 = 1; a2 = -1; a3 = 2.5; c1 = c2 = c3 = c4 = 0; size = h / 2; shrink = 2; maxRecursions = 6;} //some animating tree
    if(keyPressed(SDLK_i) {enable1 = enable2 = enable3 = 1; enable4 = 0; a1 = 1; a2 = -1; a3 = 3.0; c1 = c2 = c3 = c4 = 0; size = h / 2; shrink = 2; maxRecursions = 6;} //some animating tree
    if(keyPressed(SDLK_SPACE)) {drawLeaves++; drawLeaves %= 5; releaseSpace = 0;}

  }
  return 0;
}

递归函数现在也做了一些扩展：

首先裁剪并绘制分支线段，然后在到达最后一次递归时绘制叶子。绘制哪种类型的叶子取决于 drawLeaves 设置，可以用空格键更改。若达到最大递归次数，函数返回，不再调用自身。

void recursionTree(double posX, double posY, double dirX, double dirY, double size, int n)
{
  int x1, x2, y1, y2;
  int x3, x4, y3, y4;
  x1 = int(posX);
  y1 = int(posY);
  x2 = int(posX + size * dirX);
  y2 = int(posY + size * dirY);
  if(clipLine(x1, y1, x2, y2, x3, y3, x4, y4))
  drawLine(x3, y3, x4, y4, ColorRGB(128, 96, 64));
  if(n == maxRecursions && drawLeaves == 1) drawCircle(x4, y4, 5, ColorRGB(128, 255, 128));
  if(n == maxRecursions && drawLeaves == 2) drawDisk(x4, y4, 5, ColorRGB(128, 255, 128));
  if(n == maxRecursions && drawLeaves == 3) drawCircle(x4, y4, 10, ColorRGB(128, 255, 128));
  if(n == maxRecursions && drawLeaves == 4) drawDisk(x4, y4, 10, ColorRGB(128, 255, 128));

  if(n>=maxRecursions) return;

最后，函数为下一批分支计算新的角度和向量，并在该分支已启用的情况下再次调用自身。

  double posX2, posY2, dirX2, dirY2, size2;
  int n2;
  posX2 = posX + size * dirX;
  posY2 = posY + size * dirY;
  size2 = size / shrink;
  n2 = n + 1;
  if(enable1)
  {
    dirX2 = cos(a1 * angle + c1) * dirX + sin(a1 * angle + c1) * dirY; //Rotation
    dirY2 = -sin(a1 * angle + c1) * dirX + cos(a1 * angle + c1) * dirY;
    recursionTree(posX2, posY2, dirX2, dirY2, size2, n2);
  }
  if(enable2)
  {
    dirX2 = cos(a2 * angle + c2) * dirX + sin(a2 * angle + c2) * dirY;
    dirY2 = -sin(a2 * angle + c2) * dirX + cos(a2 * angle + c2) * dirY;
    recursionTree(posX2, posY2, dirX2, dirY2, size2, n2);
  }
  if(enable3)
  {
    dirX2 = cos(a3 * angle + c3) * dirX + sin(a3 * angle + c3) * dirY;
    dirY2 = -sin(a3 * angle + c3) * dirX + cos(a3 * angle + c3) * dirY;
    recursionTree(posX2, posY2, dirX2, dirY2, size2, n2);
  }
  if(enable4)
  {
    dirX2 = cos(a4 * angle + c4) * dirX + sin(a4 * angle + c4) * dirY;
    dirY2 = -sin(a4 * angle + c4) * dirX + cos(a4 * angle + c4) * dirY;
    recursionTree(posX2, posY2, dirX2, dirY2, size2, n2);
  }
}

以下只是用这种方式可以生成的几种树：

你还可以做更多来创建非常自然的树，例如在每次递归时随机化角度，或随机化是否绘制下一个分支。你可以绘制带纹理的更粗的树干和更漂亮的叶子，甚至可以将其扩展到 3D 并制作精美的 OpenGL demo！发挥你的想象力吧 :)

Lode 的计算机图形学教程

递归树

目录

简介

两分支递归树

多分支递归树