Generating trees on HTML5 Canvas

Hello Habr!
Today I want to talk about generating trees on HTML5 Canvas using JavaScript. Immediately I will explain that this is not about reference trees or B-trees, but about those trees that we see every day outside our window, those that make our air cleaner and richer in oxygen, those that turn yellow in autumn and lose their leaves in winter , in general, about those very living, forest, real trees, only painted on Canvas and will be discussed.


Such trees are obtained

Tree generation was needed for my game. But I could not find any adequate algorithms. So I wrote my generator ...
')

I do not want to read anything, I want the result immediately!

And so, what under a soot?

Everything works the notorious Bezier curves, thanks to them the trunk and branches are rounded and seem alive. I tried many ways, it was the use of curves that turned out to be the most productive and simplest. They are easy to build, it is easy to get the right direction from them, and you can also calculate their trajectory programmatically.

The structure of the generator is as follows:



The TreeGenerator class (in the Generator diagram) uses the Branch class object to generate branches and the trunk, and TreeGenerator calls the Drawer method to generate leaves. Branch is an abstraction providing each branch as an object. He also uses Drawer for drawing.

Step 1. Generate the branch

The Drawer class is a layer between the canvas API and Branch. This class performs the drawing of leaves and branches according to specified parameters.
And here is the function for drawing a branch from Drawer:

//x  y -   , leng -  , w - , deform -  , rotate -  DrawStick = function(x, y, leng, w, deform, rotate) { // canvas   . this.c.save(); this.c.translate(x, y); this.c.rotate(rotate.degree()); // degree     // x  y  . x = 0; y = w / -2; //       this.c.beginPath(); //  x  y this.c.moveTo(x, y); //        xy    (  w/BRANCH_CONSTRICTION) this.c.bezierCurveTo(x, y, x + leng / 2, y + deform, x + leng, y + (w - (w / BRANCH_CONSTRICTION)) / 2); //     this.c.lineTo(x + leng, y + w / BRANCH_CONSTRICTION + (w - (w / BRANCH_CONSTRICTION)) / 2); //     this.c.bezierCurveTo(x + leng, y + w / BRANCH_CONSTRICTION + (w - (w / BRANCH_CONSTRICTION)) / 2, x + leng / 2, y + w + deform, x, y + w); //   this.c.lineTo(x, y); this.c.closePath(); // ,     this.c.arc(x + leng, y + w / BRANCH_CONSTRICTION / 2 + (w - (w / BRANCH_CONSTRICTION)) / 2, w / BRANCH_CONSTRICTION / 2, 0 * Math.PI, 2 * Math.PI, false); //  this.c.fillStyle = BRANCH_COLOR; this.c.fill(); // canvas this.c.restore(); } 

From the code, you probably did not understand how the top points of the branch are defined. As you know, a tree branch at the end is a bit narrower than at the beginning. How much is already defined by the constant BRANCH_CONSTRICTION. By default, it is 1.5. BRANCH_COLOR - sets the color. The value is selected randomly from an array of colors.

The result of this function will be something like this:



Frankly, as long as it is not very similar to what we need. Therefore, go further!

Step 2. Generating a tree from branches

If you have ever looked narrowly at small trees, only sprouted from seed, you might notice that they are one single branch with leaves, then other branches sprout from this branch, and it also grows and expands itself. What is it for me? And besides, the trunk is essentially one big branch from which other branches grow, and from these branches there are eyelids, and so on ...

Proceeding from this, it will be more convenient for us to represent each branch, in the form of an object that will store parameters and methods and information about processes and branches. For this, as I said, the Branch class:

 var Branch = function(x, y, leng, width, deformation, rotate) { this.params = { x: x, y: y, leng: leng, width: width, deformation: deformation, rotate: rotate, }; this.parent = null; // ,  ,     this.children = []; // ,   . //   canvas   this.render = function() { drawer.DrawStick(this.params.x, this.params.y, this.params.leng, this.params.width, this.params.deformation, this.params.rotate); } //       this.getEndPoints = function() { var ex = this.params.x + this.params.leng * Math.cos(this.params.rotate.degree()), ey = this.params.y + this.params.leng * Math.sin(this.params.rotate.degree()); return [ex, ey]; } // ,     this.createChild = function(leng, width, deform, rotate) { var exy = this.getEndPoints(); //  //          children this.children.push(new Branch(exy[0], exy[1], leng, width, deform, rotate)); //     this.children[this.children.length - 1].parent = this; return this.children[this.children.length - 1]; } this.render(); //    } 

Let's try a new class. Let's call:

 new Branch(100,300,200,20,-60,-50).createChild(100,20/1.5,30,-60); 

The result will be:


Well, well, vaguely like a branch, right? However, the trees all the time branch out and stretch towards the sun. To create, we need a kind of add-on to createChild, the createDivarication function. In nature, most often there are divisions of a branch into 2 shoots, one of which is main, it is therefore thicker, and the second thinner. As a result of some tests and rebounds, I realized that the best ratio is 1.9: 1.4. You can use a different attitude for your trees.
And here is the createDivarication function code:

 // branches -  c   [{leng:,deform:,rotate:},{}] main -    createDivarication = function(branches, main) { //   var wi = this.params.width / BRANCH_CONSTRICTION / 2; for (var i = 0; i < 2; i++) { bi = branches[i]; //     branches         this.createChild(bi.leng, (i == main) ? (1.9 * wi) : wi * 1.4, bi.deform, this.params.rotate - bi.rotate //     ); } return this.children; } 

Here's what we got:



Well, you can draw by hand, and so you can, but we need random trees. That is what the TreeGenerator class is intended for. Here he is in person:

 var TreeGenerator = function(){ //    - branch this.genF=function(branch) { if (branch.params.width > 1) { //      var divarications = [], //    dfm = BRANCH_DEFORMATION * branch.params.width / branch.params.leng; //      //    for (var di = 0; di <= 2; di++) { divarications.push({ leng: rand(40, branch.params.leng), //       deform: rand(-dfm, dfm), //      rotate: (di == 0) ? (rand(-20, -10)) : (rand(10, 20)) //     }); } //    var chld = branch.createDivarication(divarications, Math.floor(rand(0, 2))); //     for (var ci = 0; ci < 2; ci++) { this.genF(chld[ci]); } } else { //   ,        } } //  ,    this.genT=function(x,y){ //         var mainTreeBranch = new Branch(x, y, rand(70, BRANCH_MAXLENGTH), rand(10, BRANCH_MAXWIDTH), rand(-40, 40), rand(-120, -70)); //    this.genF(mainTreeBranch); // ()   drawer.DrawHill(x,y+20); return mainTreeBranch; } } 

Reading the code, you probably noticed the new constants BRANCH_DEFORMATION - deformation (curvature) of the branches (not the trunk), BRANCH_MAXLENGTH - the maximum length of the trunk and BRANCH_MAXWIDTH - the width of the trunk. In the deformations of the branches, their thickness also plays a role in relation to the width; the thinner the branch, the smaller the final devortment is, because it is initially defined in pixels. As for the length, the branch can not be longer than the one from which it grew. I did not show the code of the DrawHill function since it consists of only six lines, and draws a semicircle at the point x and y.

Well, well, it's time to test the generator. By calling the genT function with the necessary parameters, we get something like this:



Agree, the tree is growing! This could put an end to and rejoice in the dark silhouettes of trees, especially if we consider that it is winter and the trees are no better and sometimes much worse, however, I will not stop and continue to improve the generator to make the trees more lively and interesting. If you are with me, then we have to go to the next item.

Step 3. Generation of branches from branches

When trees stand without foliage, it can be seen that they consist not only of laconic, thick branches that grow from the tops of the same branches, but also from those small and not very twigs that grow from the main ones in arbitrary places. They do this so that the tree has more foliage, because the foliage performs things that are very important for our planet - it evaporates moisture and converts carbon dioxide to oxygen. These branches in this post will be called shoots. In fact, they are also branches (branch), as I said, they grow from arbitrary places, and not just from the top. And we have branches on Bezier curves! How to calculate where the process is located? The Bezier curve formula itself will help us with this:


On js - it will be like this:

 //    Branch. pointPos       getPointOnCurve = function(pointPos) { //       var ex = this.params.x + this.params.leng / 2 * Math.cos((this.params.rotate + this.params.deformation).degree()), ey = this.params.y + this.params.leng / 2 * Math.sin((this.params.rotate + this.params.deformation).degree()); //t -  t   [0,1] t = pointPos / 100; //    ep = this.getEndPoints(); //    x,y x = [this.params.x, ep[0]]; y = [this.params.y, ep[1]];   x,y p1 = [ex, ey]; //  par1 = Math.pow((1 - t), 2) * x[0] + (1 - t) * 2 * t * p1[0] + Math.pow(t, 2) * x[1]; // x par2 = Math.pow((1 - t), 2) * y[0] + (1 - t) * 2 * t * p1[1] + Math.pow(t, 2) * y[1]; // y return [par1, par2]; } 

The curve will be in the center of the branch. Visually, it will be like this:



Now it's time to generate the processes: create a new function in Branch

 //branches -      this.createOutgrowth = function(leng, width, pos, deform, rotate) { var startXY = this.getPointOnCurve(pos); //  outgrowths( )      this.outgrowths.push(new Branch(startXY[0], startXY[1], leng, width, deform, this.params.rotate + rotate)); return this.outgrowths.reverse()[0]; } 

We also expand the generator:

 this.genO = function(branch) { if (branch.params.width > 1) { //   1 var outgrowthsCount = rand(0, BRANCH_OUTGROWTH); //  BRANCH_OUTGROWTH - .   for (var io = 0; io < outgrowthsCount; io++) { //        this.genF(branch.createOutgrowth(rand(10, branch.params.leng), rand(1, branch.params.width), rand(1, 100), rand(-10, 10), rand(-40, 40))); } } } 

And extend the genF function by replacing this:

 //     for (var ci = 0; ci < 2; ci++) { this.genF(chld[ci]); } 

on this:

 //        for (var ci = 0; ci < 2; ci++) { if (OUTGROWTH_ISSHOWN) { //OUTGROWTH_ISSHOWN   ,   true if (chld[ci].params.width < OUTGROWTH_BRANCH_WIDTH) { //OUTGROWTH_BRANCH_WIDTH -       this.genO(chld[ci]); //   } } this.genF(chld[ci]); } 

Try it out? Here is a tree:



Looks not very beautiful, not enough leaves. The next step is about them.

Step 4. Leaf generation

The leaves are an integral part of any tree (needles are leaves, too, only deformed for protection from cold) and they are too different to generate them programmatically, so we will take one of the five types of leaves created by hand. Leaves are also best drawn on Bezier curves and stored in arrays with end points and deformation point of the curve. The leaf is a sevenfold entity and we only need to draw the left side, and the rights will be added automatically.
For example, take the simplest sheet code:

 [[ [100, 0], // (  -  ) [70, 40] //   ]], 

Also consider the draw function from Drawer:

 this.DrawLeaf = function(x, y, leafPoints, colors, scale, rotate) { //  x  y lx = x; ly = y; //    for (var io = 0; io < 2; io++) { this.c.save(); //  this.c.translate(x, y); // this.c.rotate((rotate).degree()); //  this.c.scale(scale, scale); //    if (io == 1) { //    this.c.setTransform(-1, 0, 0, 1, x, y); this.c.scale(scale, scale); this.c.rotate((-180 - (rotate)).degree()); } x = 100 / -2; y = 0; this.c.beginPath(); this.c.moveTo(x, y); var lastPair = [0, 0]; //  -    for (var bi in leafPoints) { var bp = leafPoints[bi]; //   this.c.bezierCurveTo(x + lastPair[0], y + lastPair[1], x + bp[1][0], y + bp[1][1], x + bp[0][0], y + bp[0][1]); //      lastPair = [bp[0][0], bp[0][1]]; } //    this.c.lineTo(x + LEAF_LENG, y); // LEAF_LENG -  .   100 this.c.closePath(); this.c.fillStyle = colors[1]; //  this.c.fill(); this.c.strokeStyle = colors[0]; //   this.c.stroke(); this.c.restore(); x = lx; y = ly; } } 

And now it's time to attach it to the generator. Write the function genL

 this.genL = function(branch) { leafCount = branch.params.leng / (LEAF_LENG * LEAF_SCALE) * LEAF_DENSITY; //   : LEAF_SCALE - , LEAF_DENSITY -   for (var li = 1; li < leafCount; li++) { // var lxy=branch.getPointOnCurve(branch.params.leng/leafCount*li); //    //  drawer.DrawLeaf(lxy[0], lxy[1], LeafMaps[LEAF_TYPE], ['#353', 'green'], LEAF_SCALE, branch.params.rotate - 180 ); } } 

Screw this function to genF, replacing the comment “There will be additional code, which will be discussed in the following steps” with the call to genL - like this:

 if(LEAF_ISSHOWN){ //LEAF_ISSHOWN - ,   .   true this.genL(branch); } 

Well, that tree has grown!



And thank you for your attention, all the code is on GitHub ,
the result of my labors, you can touch here