0,0
рейтинг
18 сентября 2009 в 02:09

L-Systems — математическая красота растений

Красота растений привлекала внимание математиков веками. Активнее всего изучались интересные геометрические свойства растений, такие как симметрия листьев относительно центральной оси, радиальная симметрия цветов, и спиральное расположение семечек в шишках. «Красота связана с симметрией» (H. Weyl. Symmetry). Во время роста живых организмов, особенно растений, можно четко видеть регулярно повторяющиеся многоклеточные структуры. В случае составных листьев, например, маленькие листочки, которые являются частью большого взрослого листа, имеют ту же форму, что весь лист имел на раннем этапе формирования.

В 1968г. Венгерский биолог и ботаник Аристид Линденмайер (Aristid Lindenmayer) предложил математическую модель для изучения развития простых многоклеточных организмов, которая позже была расширена и используется для моделирования сложных ветвящихся структур — разнообразных деревьев и цветов. Эта модель получила название Lindenmayer System, или просто L-System.

Для тех, кто в теме и не хочет все читать целиком, проскрольте вниз, есть вопрос.

Я буду сокращать L-System до L в тексте.

Rewriting.



Основная идея L — постоянная перезапись (rewriting) элементов строки. О чем это? Вкратце, rewriting — это способ получения сложных объектов путем замены частей простого начального объекта по некоторым правилам. Классическим примером является снежинка. На рисунке initiator — это начальный объект, грани которого заменяются на generator. Далее с новым объектом проделывается то же самое. В данном случае обычный фрактал.



Возвращаясь к L и проводя аналогию с фракталами, можно сказать, что L оперирует со строкой символов по специальным правилам, начиная с первоначальной простой аксиомы. Люди, знакомые с понятием грамматики, сразу заметят, что по сути L ей и является. Но фундаментальное отличие L от формальных грамматик состоит в том, что правила применяются одновременно ко всей строке, к каждому символу, плюс, нет понятий терминальных и нетерминальных символов. То есть «вывод» по этой грамматике может продолжаться бесконечно. Одновременность применения правил очень быстро становится понятна, если учесть откуда пришла эта модель. В биологии каждая клетка растет, делится и развивается параллельно во времени. На следующей картинке видно соотношение между контекстносвободными (OL), контекстнозависимыми (IL) L и другими формальными грамматиками в иерархии Хомского.



Самые простые L-Systems.



Также, как и в классификации Хомского, L имеют и свою классификацию от простых до сложных и мощных.

Самым простым примером являются детерминированные контекстносвободные L или сокращенно DOL. Я не люблю формальные определения грамматик, так что скажу просто своими словами. Есть некоторый набор символов — алфавит. Этим алфавитом записывается строка, с которой работает L. Есть аксиома — первоначальная строка из одной или более буквы и набор правил вида a → ab. Во время каждой итерации алгоритма, применяя правило к букве из текущей строки, она (буква) заменяется на набор букв справа от стрелки. Проще рассмотреть конкретный пример развития многоклеточного организма Anabaena catenula, который изучал Линденмайер, когда он предложил модель L.

Пусть наш алфавит состоит из следующих символов, каждый из которых обозначает некоторую клетку: al ar bl br.
Аксиома состоит из одного символа.
ω: ar

И 4 правила.
p1: ar → albr

p2: al → blar

p3: br → ar

p4: bl → al


Правила говорят какие символы меняются на какие в процессе роста организма. На картинке видно как применяя правила мы наблюдаем «деление» клеток и развитие.



Черепашья интерпретация строк.



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

  • F — продвинуться вперед и нарисовать линию
  • f — продвинуться вперед ничего не рисуя
  • + — повернуть влево
  • — — повернуть вправо
  • & — повернуть вниз
  • ^ — повернуть вверх
  • \ — наклониться влево
  • / — наклониться вправо
  • | — развернуться на 180 градусов


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



Растения и ветвящиеся структуры.



Все, что было до этого является, в общем-то, непрерывными кривыми. Разумеется, таким образом весьма трудно смоделировать растения с их ветвящейся топологией. Для этого в алфавит были добавлены символы [ и ], которые обозначают начало и конец ветвления соответственно. Когда черепашка встречает символ [, ее текущее состояние пишется в стек и вытаскивается оттуда при встрече символа ].

Уже такой простой грамматикой можно сгенерировать довольно интересные двумерные и трехмерные объекты похожие на деревья.



Более сложные грамматики.



Разумеется, наука не стояла на месте, и сейчас мы имеем солидную иерархию L начиная с простых DOL рассмотренных ранее.

Стохастические L.

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

Контекстнозависимые L.

Также, как и контекстнозависимость в формальных граматиках, в L синтаксис правил усложняется и принимает во внимание окружение заменяемого символа.

Парамметрические L.

К каждому символу добавляется параметр-переменная (возможно не одна), которая позволяет, например указывать величину угла поворота для + и -, длину шага и толщину линии, проверять условия для применения правила, считать количество итераций и передавать «сигналы» вперед и назад. Пример парамметрической L.

ω : B(2)A(4, 4)
p1 : A(x, y) :y <= 3 → A(x ∗ 2, x + y)
p2 : A(x, y) :y > 3 → B(x)A(x/y, 0)
p3 : B(x) :x < 1 → C
p4 : B(x) :x >= 1 → B(x − 1)


Парамметрические контекстнозависимые L позволяют моделировать рост многоклеточных организмов и растений с учетом биохимических процессов и окружающей среды. Например, наша старая знакомая Anabaena catenula в более сложной форме. Пример из книжки [1].

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

L-System ниже моделирует рост бактерии с учетом вышесказанного.

#define присваивает значения константам используемым в L.
#include загружает форму гетероциста, в данном случае круг.
Клетки представлены модулем F(s, t, c), где s — длина клетки, t — тип клетки (0 — гетероцист, 1 и 2 — вегетативные клетки), а c — концентрация азота.

#define CH 900 /* high concentration */
#define CT 0.4 /* concentration threshold */
#define ST 3.9 /* segment size threshold */
#include H /* heterocyst shape specification */
#ignore f ∼ H
ω : -(90)F(0,0,CH)F(4,1,CH)F(0,0,CH)
p1 : F(s,t,c) : t=1 & s>=6 → F(s/3*2,2,c)f(1)F(s/3,1,c)
p2 : F(s,t,c) : t=2 & s>=6 → F(s/3,2,c)f(1)F(s/3*2,1,c)
p3 : F(h,i,k) < F(s,t,c) > F(o,p,r) : s>ST|c>CT → F(s+.1,t,c+0.25*(k+r-3*c))
p4 : F(h,i,k) < F(s,t,c) > F(o,p,r) : !(s>ST|c>CT) → F(0,0,CH) ∼ H(1)
p5 : H(s) : s<3 → H(s*1.1)




Гипножаба.



Вот, например, недавняя гипножаба, покорившая интернет, по сути является комбинацией простейших L.



#define R 1.456
ω : A(1)
p1 : A(s) → F(s)[+A(s/R)][−A(s/R)]


Более advanced.



Это всего лишь поверхностное описание теории и небольшие примеры применения на практике. Что ждет любопытного исследователя дальше?

  • Моделирование роста двумерных и трехмерных многоклеточных организмов
  • Анимация роста организмов деревьев
  • Моделирование влияния окружающей среды
  • Моделирование химикобиологических процессов и growth functions
  • Применение L для генерации поверхностей
  • Другие разнообразные варианты использования, в том числе для моделирования недвижимости и городов


Примеры.











Использование.



Еще в конце 80х L использовались для визуализации моделей растений. Сейчас возможности компьютеров ушли далеко вперед. Многие игры и инструменты 3d моделирования используют процедурную генерацию контента, в том числе и L-Systems. Как видите, из набора простых правил можно получить огромное количество разных растений и засадить ими целые поля.

Из редакторов я сам пользуюсь L в Houdini, слышал, что есть плагины и для других пакетов. Так называемая Виртуальная Лаборатория позволяет экспериментировать и анимировать L.

Методы использования грамматик также используются в так называемых Shape Grammars, но об этом потом.

Некоторые посты в интернете.
http://avalter.blogspot.com/2009/08/2d-l.html

Книги и дополнительный материал.



Вообще говоря, единственная доступная книга — это The Algorithmic Beauty of Plants. Также, по интернету разбросаны старые рандомные статьи. Более-менее новые можно найти на springerlink.com за кучу денег или в институтской библиотеке забесплатно.

Что сказать, материала довольно маловато.

Околобиологические мысли.



Я сам имею ровно никакое отношение к биологии, а являюсь Магистром Математики с небольшими невиными увлечениями. Но мне чрезвычайно нравится идея L-Systems. Простота с огромными возможностями. Когда-то давно я задумывался как же так в ДНК содержится полная информация обо мне. Как же можно в каждую клетку впихнуть всю информацию обо всех клетках? А никак, можно сказать, теория L открыла мне глаза! У меня в ДНК написано не как я выгляжу, а как меня собрать (общими словами). Что-то похожее на набор правил в L, только относящееся к синтезу протеинов.

Простая модель так четко описывает нашу с вами жизнь.

Дальше больше — превращаем правила в «ДНК» и генетическим алгоритмом выращиваем виртуальных многоклеточных.

Научные мысли.



Мне бы хотелось найти людей, которые тоже заинтересованы в научной составляющей L, поделиться материалами и статьями. Так уж получилось, что я сейчас работаю над апгрейженной концепцией L-Systems, но не имею возможности просмотреть что писалось по этой теме за последние пять лет. Не хочется изобретать велосипед.

Связаться с автором КНИГИ не удалось, автоответчик говорит, что он уехал на шабаш до января (8

Также, я ищу информацию по Shape Grammars для 3d моделирования. Есть задача генерировать из параметров космические корабли, ну знаете такие огромные штуковины с кучей мелких деталей — идеальные кандидаты для SG. Неужели придется писать плагин для Houdini на Python?
Валентин Владимирович @valyard
карма
138,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (33)

  • +4
    Природа гениальна…
    • 0
      Почитайте книгу Matt Ridley — Genome. Простыми словами об интересном. Доступна на некотором торент треккере как аудиокнига.
  • +3
    Но может именно в этом кроется изъян природы, когда, например, у человека не может вырасти новая рука взамен утерянной — из-за того, что система создана для постепенной «постройки» организма. На этапе формирования эмбриона нормально формируется клетка, которая в последствии превращается в руку. А в зрелом состоянии этот этап пройден и не смотря на то, что есть куча работающих органов, есть куча протэиновых и энергетических ресурсов «откат» к более раннему состоянию не возможен.
    • 0
      Но ведь есть же в природе механизм регенерации!
  • +2
    — Вот, например, недавняя гипножаба, покорившая интернет…

    Что-то я пропустил, когда это она успела сделать? )
  • 0
    Невероятная статья. Супер круто.
  • +6
    Хорошая статья. 5 лет назад пересёкся с этой темой и решил написать небольшую программу для рисования таких фракталов. Программа довольно простая, поддерживает лишь 5 команд: F,+,-,[,], но даже их хватает, чтобы оценить многие прелести :)

    L-system генератор

    Кому интересно, программу можно скачать здесь.
    • +2
      B вот еще до кучи приложение, рисующее «снежинки» по фрактальному принципу, которое я написал когда-то:



      a-i-studio.com/snowflake/
      • 0
        В GIMP можно спокойно «фракталить» встроенными средствами.
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    И при этом говорят, что в природе нет ни одного повторяющегося листочка…
    • +3
      как раз потому, что в ДНК записано КАК сделать листочек. во время сборки на него влияют миллионы внешних факторов.
  • 0
    Сам писал в школе интерпретатор L-языка, но я что-то не пойму чего хочет автор. L-системы=линейные фракталы. Это базовый объект для математиков, я не вижу что в нем самом по себе можно изучать. А вот среди интересных применений мне запомнилось использование фрактальных структур в статистической физике. За счет иерархаичности структуры их гораздо проще рассчитывать точно, чем квадратную решетку. Соотвественно можно в этих структурах пытаться наблюдать за разными фазовыми переходами.
    • +1
      в контексте моделирования роста растений параметрические контекстнозависимые L-Systems гораздо более сложны, чем фракталы в общем понимании (хотя вроде бы нет четкого определения, и из-за самоповторения такие L-Systems тоже причисляют поди к фракталам). ими можно не только моделировать топологию растения, но и передачу сигналов, внешние ограничение, биохимические процессы. в том расширениии, над которым я работаю, L-System расширяется до объектноориентированного языка приобретая множество интересных свойств.

      Если вы математик, вы знаете, что изучают даже натуральные числа (8 Куда уж базовее.
  • +1
    Красота растений привлекала внимание математиков веками.
    С этого предложения начинается каждая статья про моделирование растений=)) А ещё мой диплом;)
    Делал его на основе «Space colonization algoritm». Небольшую статью с его описание можно найти на том же сайте, что вы уже указали. По данному алгориитму существует целая книга, но видел её только в одном месте и за денежку.
    Вообще Space colonization algoritm не основан на L-системах, но это не мешает ему делать деревья безумной красоты=)

    В дипломе я делал плагин на python для Blender'а. Раньше было желание развивать проект, но как-то руки всё не доходят=\ Кстати для Blender'а есть плагины создающие деревья на основе L- систем — посмотрите у них на сайте.

    algorithmicbotany.org — самый крупный сайт по данной тематике с бесплатными статьями. Хотя на данный момент, возможно, появился ещё какой-нибдуь ресурс.
    • 0
      Да, сайт ценный. И материалы бесплатные. Жаль, с автором связаться пока не удалось.

      Плюс это предложение не что иное как перевод первой фразы книги (8
  • 0
    magnification reveals nature to be boring
    • +1
    • +1
      там уже другие науки работают
  • +2
    а вы ели такую капусту, как романеску?

    img0.liveinternet.ru/images/attach/c/0/35/874/35874252_x_45f79d1a.jpg
    • +1
      Математическая еда :)
  • 0
    это так шикарно, что просто не возможно выразить словами!
  • 0
    вставлю свои пять копеек. Для программеров на VB6.0 есть несколько примеров L-System http://rusproject.narod.ru/article/fractals.htm#l-sys
  • 0
    увлекался фракталами в «детстве». хорошая статейка.
  • +1
    а ведь символам, которые вырисовываются, не одни тысяча лет
  • +2
    В копилку: моё любимое квазипереодическое замощение Пенроуза :)

    Аксиома [X]++[X]++[X]++[X]++[X]
    W→YF++ZF----XF[-YF----WF]++
    X→+YF--ZF[---WF--XF]+
    Y→-WF++XF[+++YF++ZF]-
    Z→--YF++++WF[+ZF++++XF]--XF
    F→

    Его красота в непериодичности. Любой сколь угодно большой фрагмент узора повторяется бесконечное число раз, однако, нет таких двух точек где узор наложился бы сам на себя полностью (как не крути)

    P.S. Кстати, L-systems — это крайне медленно. Кто-нибудь знает, как быстрее всего можно построить это замощение?
    • 0
      Ой, забыл, конечно угол 36°
  • +1
    >У меня в ДНК написано не как я выгляжу, а как меня собрать

    Именно так!

    Жаль, очень мало кто это понимает.
  • 0
    Замечательная статья! Сама математик, упорно пытаюсь доказать окружающим, что в этой древнейшей науке таится невероятная красота. И эти фракталы — очень убедительная иллюстрация этого. Помнится, часть из них я использовала при создании презентации «Красота в математике» в университете, и даже наш суровый информатик, недолюбливающий математику, оценил )
  • 0
    Спасибо за статью. Написал скриптик, который рисует системы без ветвления. А вот с ветвлением что-то непонятное происходит, есть у меня ощущение, что я либо неправильно итерацию делаю при проходе по аксиоме, тибо как-то не так состояние сохраняю в стек.

    Я правильно понимаю, что это работает так:
    F->F[+F]
    аксиома: F
    шаг 1: F[+F]
    шаг 2: F[+F][+F[+F]]
    шаг 3: F[+F][+F[+F]][+F[+F][+F[+F]]]
    ???
    При этом мы при встрече [ сохраняем координаты и угол, а когда встречает ], вытаскиваем их?
    • 0
      черт. ключевое слово «стек»
      • 0
        хи хи хи
        • 0
          Понять бы еще как вырабатываются правила…
          Можно, конечно, на дурачка пробовать, повезет — что-нить получится…
          Вот например, водоросль получилась
          F[FF+F][F]+F-F

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.