L-systems. Моделирование деревьев

Пост представляет собой вольный перевод второй главы книги «Алгоритмическая красота растений» Пшемыслава Прущинкевича и Аристида Линденмайера (The Algorithmic Beauty of Plants, Aristid Lindenmayer, Przemyslaw Prusinkiewicz), и является продолжением замечательной статьи «L-Systems — математическая красота растений» valyard (ему спасибо за вдохновение :)

Первые модели.

Компьютерное моделирование процессов ветвления деревьев имеет относительно долгую историю. Первая модель, предложенная Юлэмом, была основана на концепции клеточных автоматов, разработанной фон Нейманом. Процесс ветвления осуществлялся итерациями, и начинался с одной окрашенной клетки на треугольной сетке, потом окрашивались те, которые касались одной и только одной вершиной клеток, окрашенных в предыдущей итерации.

Далее, эту идею развили. Мейнхардт заменил треугольную сетку квадратной, и использовал полученное клеточное пространство, чтобы проверить биологические гипотезы формирования структур сетей. В дополнении к чистому процессу ветвления, его модель учитывала эффекты повторных соединений или анастомоза, которые могли возникать между листьями или например, венами. Грин переписал клеточный автомат для трех измерений и моделировал процессы роста, которые учитывали окружающую среду. К примеру, рисунок 2.1 показывает рост виноградной лозы над домом. Модели Кохена учитывали в правилах роста понятие «плотности поля», что оказалось лучше, чем, например, работа с дискретными клетками.


Рисунок 2.1. Гармоничная архитектура Грина.

Общая особенность этих подходов — акцент на взаимодействии, как между разными элементами структуры, так и структуры с окружающей средой. И хотя это взаимодействие, очевидно, влияет на рост реальных растений, его моделирование является очень сложной задачей. Поэтому сегодня более распространены простые модели, игнорирующие даже такие фундаментальные вещи, как столкновение между ветками.

Модель Хонды.

Хонда предложил первую модель в категории простых, и сделал следующие допущения:

• сегменты дерева прямые, площадь их поперечного сечения не рассматривается;
• в течение итерации материнский сегмент производит два дочерних;
• длина двух дочерних сегментов короче материнского в и раз;
• материнский сегмент и два его дочерних находятся в одной плоскости ветвления. Дочерние сегменты выходят из материнского под углами ветвления и ;
• в связи с действием гравитационной силы, плоскость ветвления является «ближайшей к горизонтальной плоскости», иными словами, линия, перпендикулярная материнскому сегменту и лежащая в плоскости ветки — горизонтальная. Исключение делается для веток, присоединенных к главному стволу. В этом случае используется постоянный угол расхождения .

Рисунок 2.2. Геометрия дерева согласно Хонде.

Варьируя численные параметры, Хонда получил большое разнообразие древоподобных форм. С некоторыми улучшениями, его модели были применены к изучению процессов ветвления реальных деревьев. Впоследствии, были предложены разные правила для углов ветвления, для того, чтобы охватить также структуры деревьев, в которых плоскости дальнейших разветвлений перпендикулярны друг другу. Результаты Хонды послужили основой для моделей, предложенных Эоно и Кьюниай. Они предложили несколько улучшений, самым важным из которых был поворот сегментов в определенных направлениях, соответствующих стремлению веток к солнцу, учёту ветра и гравитации. Похожая концепция была предложена Кохеном, а Рефай и Армстронг разработали более точный с физической точки зрения метод «изгиба» веток.

В моделях Хонды, Эоно и Кьюниай использовались прямые линии постоянной или переменной ширины для построения «древесного скелета». Значительного улучшения фотореализма синтезируемых моделей достигли Блуменфел и Оппенхеймер, которые представили изгибающиеся ветки, тщательно смоделировали поверхности вокруг узлов ветвления, и наложили текстуры на кору и листья (рисунок 2.3)


Рисунок 2.3. Блуменфел, Acer graphics.

В работе Хонды структуры ветвления строилась согласно детерминированным алгоритмам. Напротив, в группе моделей, предложенных Ривсом и Блау, де Рефай, Ремфри, Нила и Стивса использовались стохастические законы. Хотя эти модели построены по-другому, они разделяют общую парадигму описания структуры деревьев, в частности, расчёт возможностей формирования веток. Ривс и Блау стремились не углубляться в биологические детали моделируемых структур (рисунок 2.4). Напротив, де Рефай использовал стохастический подход для создания реалистичных растений и моделировал активность почек в дискретные моменты времени. Получив сигнал таймера, почка могла либо:

• ничего не делать;
• стать цветком;
• стать сегментом стебля, оканчивающимся новой вершиной и одним или несколькими боковыми ответвлениями стебля;
• умереть или исчезнуть.

Эти события происходили согласно стохастическим законам, описанным отдельно для каждого вида растений. Геометрические параметры, такие как длина и диаметр сегмента стебля, углы ветвления, также рассчитывались согласно стохастическим алгоритмам.


Рисунок 2.4. Картина леса, Ривс, © 1984 Pixar.


Рисунок 2.5. Навес из масличных пальм, CIRAD Modelisation Laboratory.

Используя базовые типы законов развития в этом методе, Хелле, Олдемен и Томлинсон установили 23 разных типов архитектуры деревьев. Детализированные модели выбранных типов растений разработаны и описаны в литературе. Простая модель дерева показана на рисунке 2.5. Подход Ремфри был сходен с подходом де Рефай, но первый использовал бОльшие временные промежутки. Выяснилось, что для достижения достоверных результатов, стохастические модели должны описывать поведение боковых ростков, возможное в течение года.

Применение L-systems для генерирования деревьев было впервые рассмотрено Эоно и Кьюниай. Для начала, основываясь на формальном определении L, они доказали её непригодность для моделирования высших растений. Но доказательство не относилось к параметрическим L-systems с черепашьей интерпретацией строк. К примеру, L-systems на рисунке 2.6 выполняет те модели Хонды, в которых один из углов ветвления равен нулю, податливая моноподиальная структура и ясно выраженные главная и боковые оси.


Рисунок 2.6. Модели деревьев с моноподиальным ветвлением Хонды, полученные на L-systems.

n = 10
#define  r1  0.9     /* коэффициент уменьшения длины ствола */
#define  r2  0.6     /* коэффициент уменьшения длины веток */
#define  a0  45      /* угол ветвления для ствола */
#define  a2  45      /* угол ветвления для боковых сегментов */
#define  d   137.5   /* угол расхождения */
#define  wr  0.707   /* коэффициент уменьшения толщины */