### MelRecursion & Branching

#### Introduction

This tutorial develops a practical application of recursion to generate shapes that resemble trees. The recursive procedure `tree`() (listing 1) presented in this tutorial produces two branches at each node. The procedure uses the following algorithm to find the end points of the branches that extend in a `growthDir` vector.

##### Finding the First Branch

Given `growthDir`, `branchAngle` and `branchLen`,

 1   Calculate a circle representing the branch radius - figure 1.     2   Find a random vector on the circle - figure 2.     3   Translate the vector up the y-axis by branch length units - figure 3.     4   Rotate the vector by the branch angle to find the end of a branch - figure 4.     5   Draw a line between the base of the branch and the (relative) end of the branch.     6   Recurse

##### Finding the Second Branch

Given `growthDir`, `branchAngle` and a vector defining the first branch
1   Define the second branch as if it were a reflection of the first
branch about the `growthDir` vector - figure 5,
2   Move the end of the second branch relative to the base point,
3   Draw the second branch,
4   Recurse

##### Sample Trees

Listing 1 (tree.mel)

 ```//============================================== // aimY //============================================== proc float[] aimY(vector \$vec) { float \$out[2]; float \$xAngle; float \$zAngle; float \$xyLength; float \$vecLength; \$xyLength = sqrt((\$vec.x) * (\$vec.x) + (\$vec.y) * (\$vec.y)); \$vecLength = sqrt((\$vec.x) * (\$vec.x) + (\$vec.y) * (\$vec.y) + (\$vec.z) * (\$vec.z)); // \$xyLength will be zero when \$vec is pointing // along the +z or -z axis if(\$xyLength == 0) \$zAngle = (\$vec.x) > 0 ? deg_to_rad(90) : deg_to_rad(-90); else \$zAngle = acos((\$vec.y)/\$xyLength); \$xAngle = acos(\$xyLength/\$vecLength); \$xAngle = (\$vec.z) > 0 ? \$xAngle : -\$xAngle; \$out[0] = rad_to_deg(\$xAngle); \$zAngle = (\$vec.x) > 0 ? -\$zAngle : \$zAngle; \$out[1] = rad_to_deg(\$zAngle); return \$out; } //============================================== // vectorOnCircle //============================================== proc vector vectorOnCircle(float \$rad) { // find a random vector within a 2 * rad square float \$x = rand(-\$rad, \$rad); float \$y = 0; float \$z = rand(-\$rad, \$rad); vector \$vec = <<\$x, \$y, \$z>>; // convert to a unit vector - this will place // head of the vector on a circle of radius 1 \$vec = unit(\$vec); // scale it by \$rad \$vec = \$vec * \$rad; return \$vec; } //============================================== // reflect //============================================== proc vector reflect(vector \$i, vector \$n) { \$i = unit(\$i); \$n = unit(\$n); return \$i - 2 * dot(\$i, \$n) * \$n; } //============================================== // tree //============================================== proc tree(int \$depth, vector \$base, vector \$growthDir, float \$branchAngle, float \$branchLen) { if(\$depth <= 0) return; // STEP 1 Find the size of a circle such that if it was // located at the end of the branch it would define // a cone whose apex angle equals twice the "branchAngle". \$rad = \$branchLen * sin(deg_to_rad(\$branchAngle)); // STEP 1.1 Randomly choose a point on a circle vector \$vec = vectorOnCircle(\$rad); // STEP 1.2 Transform the point on the circle so that // its "branchLen" units up the world y-axis vector \$x_axis = <<1,0,0>>; vector \$y_axis = <<0,1,0>>; vector \$z_axis = <<0,0,1>>; \$vec = \$vec + <<0, \$branchLen, 0>>; // STEP 1.3 Find the x-axis/z-axis rotations that will // align the branch \$vec to the "growthDir". float \$angle[2] = aimY(\$growthDir); \$vec = rot(\$vec, \$x_axis, deg_to_rad(\$angle[0])); \$vec = rot(\$vec, \$z_axis, deg_to_rad(\$angle[1])); \$vec = <<(\$vec.x), (\$vec.y), (\$vec.z)>>; // STEP 1.4 Locate the end of the branch relative to the // base of the branch. vector \$end1 = \$base + \$vec; // STEP 1.5 Finally, draw the curve segment that "represents" // the first branch. curve -d 1 -p (\$base.x) (\$base.y) (\$base.z) -p (\$end1.x) (\$end1.y) (\$end1.z); // Recurse to the next branch tree(\$depth - 1, \$end1, \$vec, \$branchAngle, \$branchLen * 0.6); // STEP 2 Define the second branch as if it were a // reflection of the first branch first about the "growthDir" \$vec = reflect(-\$vec, \$growthDir); \$vec = <<(\$vec.x), (\$vec.y), (\$vec.z)>>; // STEP 2.1 Locate the end of the branch relative to the // base of the branch. vector \$end2 = \$base + \$vec; // STEP 2.2 Finally, draw the curve segment that "represents" // the second branch. curve -d 1 -p (\$base.x) (\$base.y) (\$base.z) -p (\$end2.x) (\$end2.y) (\$end2.z); // Recurse to the next branch tree(\$depth - 1, \$end2, \$vec, \$branchAngle, \$branchLen * 0.6); } select -all; delete; //seed(1); vector \$begin = <<0,0,0>>; vector \$dir = <<0,1,0>>; float \$angle = 13; float \$len = 2; tree(7, \$begin, \$dir, \$angle, \$len); ```