Генерация деревьев на HTML5 Canvas

Здравствуй Хабр!
Сегодня я хочу рассказать о генерации деревьев на HTML5 Canvas с помощью JavaScript. Сразу поясню, что речь идет не о деревьях ссылок или B-дереьях, а о тех деревья, которые мы каждый день видим у себя за окном, тех, которые делают наш воздух чище и богаче кислородом, тех, что желтеют осенью и теряют листья зимой, вообщем о тех самых живых, лесных, настоящих деревьях, только нарисованных на Canvas и пойдет речь.

Такие вот деревья получаются

Генерация деревьев нужна была мне для моей игры. Но некаких адекватных алгоритмов мне найти так и не удалось. Поэтому я написал свой генератор…
Не хочу ничего читать, хочу сразу результат! ^[1]

И так, что под копотом?

Все работает пресловутых кривых Безье, благодаря им ствол и ветви получаются округленными и кажутся жывыми. Я перепробовал множество способов, на самым производительным и простым оказалось именно использование кривых. Их легко строить, легко добиться от них нужного направления, а также можно рассчитать их траекторию программно.

Структура генератора такова:

Класс TreeGenerator(на схеме Generator) использует объект класса Branch для генерации ветвей и ствола, для генерации листьев TreeGenerator вызывает метод из Drawer. Branch — это абстракция предоставляющая каждую ветку, как объект. Он тоже использует Drawer для отрисовки.

Шаг 1. Генерация ветви

Класс Drawer — это прослойка между canvas API и Branch. Этот класс выполняет отрисовку листьев и ветвей по заданным параметрам.
А вот и функция по рисованию ветви из 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);

	//Рисуем первую кривую со сгибом в середине от x y до начала верней линии(имеющей ширину 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();
}

Из кода, вы наверное не поняли как задаются верхние точки ветви. Как известно, ветвь дерева в конце немного уже, чем в начале. Насколько уже, задается константой BRANCH_CONSTRICTION. По умолчанию она равна 1.5. BRANCH_COLOR — задает цвет. Значение выбирается рандомом из массива цветов.

Результатом этой функции станет примерно такая ветка:

Скажу честно, пока это не очень похоже на то, что нам нужно. Поэтому, поехали дальше!

Шаг 2. Генерация дерева из веток

Если вы когда нибудь присматривались к маленьким, только проросшим из семени деревцам, то могли заметить, что они представляют собой одну единственную ветку с листиками, затем из этой ветки прорастают другие, а она сама тоже растет и расширяется. К чему это я? А к тому, что ствол — это по сути дела и есть одна большая ветка из которой врастают другие ветки, а из этих веток еще веки, и так далее…

Исходя из этого, нам будет удобнее представлять каждую ветку, ввиде объекта, который будет хранить параметры и методы и информацию об отростках и ответвлениях. Для этого, как я уже говорил, класс Branch:

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(); //Вызываем функцию для рандиринга
}

Испробуем новый класс. Вызавем:

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

Результат будет таким:

Ну что-ж, отдаленно напоминает ветку, правда? Однако деревья всё время разветвляются и тянутся к солнцу. Для создания нам понадобится своебразная надстройка на createChild, функция createDivarication. В природе, чаще всего встречаются разделения ветви на 2 отростка, один из которых основной, он следовательно толще, а второй тоньше. В результате некоторых тестов и подборов, я понял, что лучшее отношенее 1.9:1.4. Вы можете использовать другое отношение для своих деревьев.
А вот и код функции createDivarication:

// 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;

}

Вот что у нас получилось:

Ну вручную нарисовать и так можно, а нужны то нам случайные деревья. Именно для этого и предназначен класс TreeGenerator. Вот и он собственной персоной:

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;
	}
}

Читая код вы наверное заметили новые константы BRANCH_DEFORMATION — деформация(кривизна) веток (не ствола), BRANCH_MAXLENGTH — максимальная длинна ствола и BRANCH_MAXWIDTH — ширина ствола. В деформации веток также играет роль их толщина по отношению к ширине, чем тоньше ветка тем меньше в итоге девормация, ведь она изначально задается в пикселях. Что касается длинны, то ветвь не может быть длинее той, от которой отросла. Я не стал показывать код функции DrawHill так как она состоит всего из шести строк, и рисует полукруг в точке x и y.

Ну что-ж, самое время опробовать генератор. Вызвав функцию genT с нужными параметрами, получим примерно такой результат:

Согласитесь, дерево то, растёт! На этом можно было бы поставить точку и радоваться тёмным силуэтам деревьев, тем более, если учитывать, что сейчас зима и за окном деревья ничуть не лучше, а порой и намного хуже, однако, я не остановится и продолжил совершенствовать генератор, чтобы сделать деревья ещё более живыми и интересными. Если вы со мной, то нам пора к следующему пункту.

Шаг 3. Генерация отростков от веток

Когда деревья стоят без листвы можно заметить что они состоят не только из лаконичных, толстых ветвей, вырастающих из вершин таких же ветвей, но и из тех маленьких и не очень веточек которые отрастают от основных в произвольных местах. Делают они это для того для того, чтобы у дерева стало больше листвы, ведь листва выполняет очень важные для нашей планеты вещи — испаряет влагу и преобразует углекислый газ в кислород. Эти веточки в данном посте будут называться отростками. По сути они тоже ветви(branch), как я и говорил растут из произвольных мест, а не только из верхушки. А ветки у нас на кривых Безье! Как же рассчитать, где будет находится отросток? В этом нам поможет сама формула ^[2] кривых Безье:

На js — это будет вот так:

//Функция используется в классе 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];

}

Кривая будет проходить по центру ветви. Визуально это будет вот так:

А теперь пора и генерировать отростки: создадим в 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];
}

Также расширяем генератор:

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)));

		}
	}
}

И расширим функцию genF, заменив это:

//Создание ответвлений от новых веток
for (var ci = 0; ci < 2; ci++) {
      this.genF(chld[ci]);
}

на вот это:

//Создание ответвлений от новых веток и создание отростков
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]);
}

Опробуем? Вот такое стало дерево:

Смотрится не очень красиво, не хватает листьев. Следующий шаг как раз о них.

Шаг 4. Генерация листьев

Листья неотъемлемая часть любого дерева(иголки тоже являются листьями, только девормированными для защиты от холода) и они слишком разные, чтобы генерировать их программно, поэтому мы будем брать один из пяти видов листьев, созданных в ручную. Листья рисовать тоже лучше всего на кривых Безье и хранить в массивах с конечными точками и точкой деформации кривой. Лист — сущность семеричная и нам стоит только нарисовать левый бок, а правы дополнится автоматически.
Для примера возьмем код простейшего листа:

[[ 
                        [100, 0], //Конечные точки( начало - вершина листа)
                        [70, 40] //Точка сгиба кривой
                ]],

Также рассмотрим функцию отрисовки из 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;
		}


	}

А теперь пора пристроить это к генератору. Напишим функцию 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
		); 

	}
}

Прикрутим эту функцию к genF, заменив комментарий «Сдесь будет дополнительный код, о котором пойдет речь в следующих шагах» на вызов genL — вот так:

if(LEAF_ISSHOWN){ //LEAF_ISSHOWN - определяет, показывать ли листья. По умолчанию true
	this.genL(branch);
}

Ну вот и вырасло дерево!

А вам, спасибо за внимание, весь код есть на GitHub ^[3],
результат моих трудов, можно пощупать тут ^[4]

Автор: RAZVOR

Источник ^[5]