Steps3D - Tutorials - Моделювання рослин за допомогою L-систем

Основною ідеєю його підходу було моделювання рослин з допомогою досить простого об'єкта. При цьому розвитку відбувається постійне заміщення простих частин більш складні, до частин яких застосовується той самий процес заміщення і так до будь-якого бажаного ступеня деталізації.

Для цього дуже вдалим виявився апарат формальних граматик. У найпростішому випадку (так званих D0L-систем, тобто детермінованих, контекстно-незалежних L-систем) система описується такими параметрами:

Алфавіт – деякий набір допустимих символів
Початковий стан - деякий рядок із символів алфавіту
Правила підстановки

Розглянемо наступну систему D0L:

Як алфавіт візьмемо всього два символи'a'і'b'. Як початковий рядок візьмемо символ'b'. Правила заміни визначимо так:

Згідно з цими правилами символ'a'замінюється на рядок'ab', а символ'b'- на символ'a'.

У цьому вважаємо, що це заміни у рядку відбуваються одночасно, тобто. одна заміна не впливає на можливість застосування інших правил на цьому етапі.

Розглянемо, яким чином відбуватиметься розвиток цієї системи для кроків 1..6.

Щоб за допомогою L-систем отримувати моделі рослин, слід приписати окремим символам деякий геометричний зміст, що дозволяє зіставляти рядку символів геометричний об'єкт.

Традиційно для цього використовується так званачерепаша графіка(turtle graphics) - деякий пристрій (черепашка), який може переміщатися вперед на задану відстань і повертати вправо та вліво на заданий кут. При цьому переміщення черепашкиможе відбуватися як із малюванням лінії, так і без малювання.

Зазвичай використовуються такі інтерпретації символів:

'F' - пересування вперед із малюванням лінії на задану відстань
'f' - переміщення вперед без малювання лінії на задану відстань
'+' - поворот наліво на заданий кут
'-' - поворот праворуч на заданий кут

Розглянемо наступну D0L-систему:

Початковий стан 'F+F+F+F'.

Правило: 'F' -> 'F+F-F-FF+F+F-F'

У початковому стані ця система дає квадрат (див. рис 1.).

Рис 1. "Острова Коха".

В результаті послідовного застосування правила підстановки ми отримуємо замкнуті криві, схожі на "Острів Коха".

На жаль описаним вище способом можна будувати лише прості ламані (замкнуті чи ні). Для побудови деревоподібних (ієрархічних) структур, що часто зустрічаються серед рослин, цього набору символів недостатньо.

Однак виявляється, що для підтримки деревоподібних структур достатньо додати до алфавіту лише два символи (разом з їх інтерпретаціями) '['' і ']'.

Символ '[' викликає збереження поточного стану черепашки (положення, орієнтації, величини переміщення тощо) на стеку. Символ ']' викликає відновлення стану системи зі стека.

Наступний приклад L-системи (системи, що використовують символи [] називаютьbracketed) демонструє достатність введення цих символів для побудови деревоподібних систем.

Початковий стан: 'F'.

Рис 2. Найпростіша деревоподібна система.

Ще кілька різних двомірних систем:

Початковий стан: 'X'

Початковий стан: 'F'.

Якщо необхідно отримати тривимірний об'єкт, то замість двомірної черепашки зручніше використовувати "літак", орієнтація якого задається трьома кутами - крен (roll), нахил (pitch) і поворот (yaw (9)).

3. Інтерпретація кутів.

Символи 'F', 'f', '+', '-', '[' і ']' зберігають сенс, але також вводяться ще чотири символи, що відповідають двом доданим ступеням свободи:

'&' - збільшенняpitch,
'^' - зменшенняpitch,
'' - зменшенняroll.

Також корисним виявляється запровадити ще один символ '!', визначивши його дію зміну знака повороту, тобто. він змінює між собою дії символів '+' та '-', '&' і '^' і ''.

Нижче наводяться два приклади найпростіших тривимірних L-систем.

Початковий стан: 'F'.

Початковий стан: 'AB'

Правила: 'A' -> '[F[+FCA][-FCA]]' 'B' -> '[F[>FCB][ '[+FBF] (0.8) 'A' -> F (0.2) 'B' -> '[-FBF] (0.6) 'A' -> F (0.4)

Для реалізації описаних класів L-систем можна використовувати наведені нижче класи.

МетодsetInitialStringслужить для завдання початкового рядка, за умовчанням вона дорівнює "F".

МетодaddRuleслужить для встановлення правила заміни одного символу на рядок. Жодних правил за замовчуванням немає.

МетодsetAngleслужить завдання кута, який відбувається поворот по командам '+','-', '&','^',' '.

МетодgetCurrentStringповертає поточний рядок, що є результатом виконання методуbuildSystem.

МетодsetDistScaleдозволяє задати параметр, що визначає у скільки разів необхідно змінитивеличину кроку після виконання команд 'F' та 'f'. За здійснення цієї зміни служить віртуальний методupdateState.

За замовчуванням цей параметр дорівнює одиниці. Завдання його у діапазоні 0.3-0.7 дозволяє контролювати розмір гілок "нового покоління" порівняно з батьківськими.

МетодsetAngleScaleдозволяє задати параметр, що визначає у скільки разів необхідно змінити кут, на який здійснюється поворот. Зміна відбувається за командами 'F' та 'f'. За здійснення цієї зміни служить віртуальний методupdateState.

МетодinterpretStringздійснює побудову зображення по рядку, що передається. Для малювання відрізків використовується віртуальний методdrawLine.

МетодbuildSystemслужить для побудови стану системи, що відповідає початковому рядку, правилам та заданій кількості ітерацій.

Методdrawздійснює побудови відрізка. За промовчанням малюється простий відрізок засобами OpenGL.

МетодgetBoundsповертає обмежує тіло (ААВВ), що відповідає поточному стану системи. Оскільки розміри системи можуть сильно змінюватись в залежності від кількості ітерацій та інших параметрів, то використання цього методу дозволяє налаштувати поточне перетворення для отримання потрібного зображення розміру.

МетодoneStepздійснює один крок у розвитку даної L-системи. Нижче наводиться його реалізація.

Методstepповертає вектор, який необхідно зробити переміщення цьому етапі.

МетодdrawLineздійснює побудову відрізка по початковій та кінцевій точках. Він може бути перевизначений для отримання зображення з урахуванням кольорів, товщини гілок та інших параметрів.

МетодupdateStateслужить длякорекції стану системи після команд 'F' та 'f'. Його реалізація наводиться нижче.

Для роботи зі стохастичними L-системами можна трохи модифікувати описаний вище клас. В результаті ми приходимо до наступного класу:

Основною відмінністю інтерфейсу цього класу від інтерфейсу класу LSystem є методaddRule- у ньому з'явився додатковий параметр - ймовірність застосування цього правила. Можна також задати правило без ймовірності - у разі ймовірність його застосування вважається рівної одиниці.

Крім розглянутих вище типів L-систем, є інші типи. Одним із них є контекстно-залежні L-системи. У контекстно-залежній(n,m)L-системі для кожного правила можна задати навколишній контекст - доnсимволів зліва і доmсимволів праворуч.

За цим посиланням можна завантажити весь вихідний код цієї статті. Також доступні для завантаження відкомпільовані версії для Windows, Linux і Mac OS X.