Пост представляет собой вольный перевод второй главы книги «Алгоритмическая красота растений» Пшемыслава Прущинкевича и Аристида Линденмайера (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 /* коэффициент уменьшения толщины */
ω : A(1,10)
p1: A(l,w) : *→ !(w)F(l)[&(a0)B(l*r2,w*wr)]/(d)A(l*r1,w*wr)
p2: B(l,w) : *→ !(w)F(l)[-(a2)$C(l*r2,w*wr)]C(l*r1,w*wr)
p3: C(l,w) : *→ !(w)F(l)[+(a2)$B(l*r2,w*wr)]B(l*r1,w*wr)
* This source code was highlighted with Source Code Highlighter.Таблица 2.1. Константы для моноподиальных древесных структур на рисунке 2.6.
Прим. пер. – здесь интересно то, что толщина сегментов между узлами дерева должна быть постоянной, а на картинке видно, что толщина ствола начинает уменьшаться ещё до первого разветвления, что противоречит предыдущим и последующим рассуждениям. На других картинках подобного не замечено :)
Согласно выражению
, при каждой итерации от вершины главной оси 
отходит сегмент стебля 
и боковая вершина 
. Константы 
и 
указывают уменьшение длины для прямого и бокового сегментов, 
и 
— углы ветвления и 
— угол расхождения. Модуль 
устанавливает ширину линии 
, таким образом выражение уменьшает ширину дочерних сегментов от материнского в 
раз. Эта константа удовлетворяет постулату Леонардо да Винчи, согласно которому общая толщина всех веток, сложенных вместе, в любом сечении дерева горизонтальной плоскостью равна толщине ствола под ними. В случае, если из материнской ветки диаметром 
, выходят две дочерние, равного диаметра 
, этот постулат дает уравнение 
, следовательно, значение 
равно 
. Прим. пер. — под толщиной веток и толщиной ствола, вероятно, следует понимать их площади поперечного сечения, тогда становиться ясно, откуда появились квадраты в последних уравнениях.
Выражения
и 
описывают дальнейшее развитие боковых веток. При каждой итерации прямая вершина ( или 
) выпускает боковую вершину следующего порядка под углом или 
по отношению к материнской оси. Оба выражения используются для создания боковых вершин попеременно слева и справа. Символ 
вращает черепашку вокруг её собственной оси, причем вектор 
указывающий направление «лево» черепашки проведен горизонтально. Следовательно, плоскость ветки — «ближайшая к горизонтальной плоскости», как это и требуется в модели Хонды. Записывая в векторной форме, изменяет ориентацию черепашки в пространстве согласно:
где векторы
, и 
— главный, левый и верхний векторы, привязанные к черепашке, 
— вектор, направленный в противоположную сторону от направления действия гравитации. На рисунке 2.6 показаны деревья, которые смоделированы при константах, перечисленных в таблице 2.1, и совпадают с моделями деревьев Хонды.Симподиальное ветвление.
Другие L-systems, указанные на рисунке 2.7, охватывают симподиальные структуры, в которых оба дочерних сегмента формируют ненулевой угол с материнским. В этом случае активность главной вершины снижена из-за формирования ствола
и пары боковых вершин (выражение ). Дальнейшее ветвление осуществляется выражением . Простые структуры на рисунке 2.7 были получены, используя константы, перечисленные в таблице 2.2, и соответствуют моделям, представленным Эоно и Кьюниай.
Рисунок 2.7. Модели деревьев с симподиальным ветвлением Эоно и Кьюниай, полученные на L-systems.
n = 10
#define r1 0.9 /* коэффициент уменьшения длины 1 */
#define r2 0.7 /* коэффициент уменьшения длины 2 */
#define a1 10 /* угол ветвления 1 */
#define a2 60 /* угол ветвления 2 */
#define wr 0.707 /* коэффициент уменьшения ширины */
ω : A(1,10)
p1 : A(l,w) : *→ !(w)F(l)[&(a1)B(l*r1,w*wr)]
/(180)[&(a2)B(l*r2,w*wr)]
p2 : B(l,w) : *→ !(w)F(l)[+(a1)$B(l*r1,w*wr)]
[-(a2)$B(l*r2,w*wr)]
* This source code was highlighted with Source Code Highlighter.Таблица 2.2 Константы для деревьев с симподиальным ветвлением на Рисунке 2.7.
Предыдущие модели имеют несколько искусственный характер, потому что окончательная длина каждого сегмента задаётся ещё при его создании, и в дальнейших итерациях не изменяется. Но возможно моделировать сам процесс роста, то есть увеличивать длину и ширину материнских сегментов при росте дочерних. Пример L-system сконструированной по этой парадигме дан на Рисунке 2.8.
Тернарное ветвление.
Общая структура дерева определена выражением
. При каждой итерации вершина производит 3 новые ответвления, оканчивающиеся их собственными вершинами. Параметр и константа 
определяют соотношение ширины материнской ветки к ширине дочерней ветки . Согласно постулату да Винчи 
, таким образом, 
. Выражения и описывают постепенное изменение длины веток и увеличение их диаметра.
Рисунок 2.8. Модели деревьев с тернарным ветвлением.
#define d1 94.74 /* угол расхождения 1 */
#define d2 132.63 /* угол расхождения 2 */
#define a 18.95 /* угол ветвления */
#define lr 1.109 /* коэффициент удлинения */
#define vr 1.732 /* коэффициент увеличения ширины */
ω : !(1)F(200)/(45)A
p1 : A : *→ !(vr)F(50)[&(a)F(50)A]/(d1)
[&(a)F(50)A]/(d2)[&(a)F(50)A]
p2 : F(l) : *→ F(l*lr)
p3 : !(w) : *→ !(w*vr)
* This source code was highlighted with Source Code Highlighter.Таблица 2.3. Константы для моделей деревьев на Рисунке 2.8.
Тропизмом называется реакция организма, например растения, к внешнему воздействию ростом в направлении, определенным этим воздействием. В частности, стремление растений к свету проявляется в виде искривления веток. Это моделируется небольшим поворотом черепашки после прорисовки каждого сегмента в направлении, определенным вектором тропизма
(рисунок 2.9). Угол поворота a рассчитывается, используя формулу 
=
|
|, где — параметр, характеризующий чувствительность, восприимчивость оси к повороту. Эта формула имеет физическое объяснение: если интерпретировать как силу, приложенную к концу вектора , и может поворачиваться вокруг его начальной точки, то вращающий момент равен . Параметры, относящиеся к поколению моделей деревьев на рисунке 2.8, приведены в таблице 2.3. Реалистичный рендер дерева на рисунке 2.8d представлен на рисунке 2.10.
Рисунок 2.9. Коррекция
сегмента благодаря тропизму .
Рисунок 2.10. Чарующее озеро Масгрейва и др.
Рисунок 2.11. Сюрреалистичный лифт.
Заключение.
Примеры, приведённые выше, показывают, что модели деревьев Хонды, как и модели его последователей Эоно и Кьюниай могут быть получены с помощью L-systems. Шебелл также показал, что L-systems могут играть важную роль как инструмент для биологически-корректного моделирования деревьев и синтеза фотореалистичных изображений. Однако пока полученные модели имеют общий характер, и структуры конкретных деревьев ещё в разработке. Также L-systems широко применяются в сфере реалистичного моделирования травяных растений, обсуждаемых в следующей главе.
P.S. Если «фотореалистичные» изображения из книги 1990 года не доставляют, то возможно более современные рендеры из другой статьи (pdf) на algorithmicbotany.org покажутся интересными:
P.P.S. В переводе не приведено бесконечное множество ссылок на литературу, которое есть в оригинале книги. Нумерация таблиц и картинок оставлена исходная. Оригинал книги находится здесь: algorithmicbotany.org/papers/#abop. Если сайт лежит, книгу в pdf можно скачать здесь: всю, только вторую главу. Если в тексте найдутся орфографические/технические ошибки, прошу незамедлительно сообщить в личку))
