🌿 Математика · Комп'ютерна графіка

📅 Червень 2026⏱ 14 хв🟡 Початковий–Середній

L-системи та процедурні рослини: від теорії граматик до 3D-дерев

У 1968 році біолог Арістід Ліндемаєр винайшов формалізм переписування рядків для моделювання росту водоростей. Той самий математичний апарат — нині відомий як L-система — лежить в основі процедурно згенерованих дерев у The Witcher 3, фрактальних папоротей раннього комп'ютерного мистецтва та складних моделей росту рослин, які використовуються в ботанічних дослідженнях сьогодні.

1. Переписування рядків: основна ідея

L-система (система Ліндемаєра) — це формальна граматика, що задається трьома компонентами:

Алфавіт V: скінченна множина символів (наприклад, {F, +, −, [, ]})
Аксіома ω: початковий рядок (наприклад, «F»)
Правила продукції P: правила підстановки, що застосовуються одночасно до кожного символу поточного рядка

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

// Ріст водоростей (оригінальний приклад Ліндемаєра 1968 року) Алфавіт: { A, B } Аксіома: A Правила: A \to AB B \to A Покоління 0: A Покоління 1: AB Покоління 2: ABA Покоління 3: ABAAB Покоління 4: ABAABABA Покоління 5: ABAABABAABAAB Довжини рядків: 1, 2, 3, 5, 8, 13 \dots \to послідовність Фібоначчі! (Відношення довжин \to золотий перетин φ \approx 1.618)

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

2. Інтерпретація через черепашачу графіку

Рядок символів — це лише текст, доки ми не надамо йому геометричного змісту. Черепашача графіка забезпечує таке відображення: уявіть черепашку з пером, що має позицію та напрямок. Символи керують рухом черепашки:

Стандартна інтерпретація символів черепашки: F — рухатися вперед на довжину кроку d, провести відрізок f — рухатися вперед на d, НЕ малювати (перо піднято) + — повернути ліворуч на кут δ - — повернути праворуч на кут δ | — повернути на 180° (зворотний напрямок) [ — покласти поточний стан (позиція, напрямок) у стек ] — зняти стан зі стека (повернутися до збереженої позиції) & — нахилити вниз на δ (3D: обертання навколо лівої осі) ^ — нахилити вгору на δ (3D: обертання навколо лівої осі) \ — повернути (roll) ліворуч на δ (3D: обертання навколо осі напрямку) / — повернути (roll) праворуч на δ (3D: обертання навколо осі напрямку) | — повернути на 180°

Символи дужок стека [ та ] — це те, що уможливлює розгалуження: покладіть стан черепашки перед тим, як піти вздовж гілки, потім зніміть його, щоб повернутися до точки розгалуження й продовжити. Кожна розвилка рослини — це підрядок […].

Інтерпретація відокремлена від граматики: один і той самий рядок L-системи можна відрендерити з різними параметрами черепашки (різна довжина кроку, кут, 2D або 3D), отримавши абсолютно різні зображення. І навпаки — однакове зображення може виникнути з різних граматик. Це розділення генерації (граматика) та рендерингу (черепашка) є ключовою особливістю дизайну.

3. Класичні приклади DOL-систем

DOL-система (детермінована, контекстно-вільна, з 0 попередників) — найпростіший клас: кожен символ має рівно одне правило переписування, і контекст не перевіряється. Більшість ілюстрацій фрактальних рослин використовують DOL-системи.

Сніжинка Коха

Алфавіт: { F, +, - } Аксіома: F--F--F Правило: F \to F+F--F+F Кут δ: 60° Покоління 2 дає контур сніжинки Коха. Кожен відрізок F замінюється на 4 підвідрізки \to периметр \times 4/3 кожне покоління. Після n поколінь: периметр = (4/3)ⁿ \times початковий \to \infty (фрактал)

Крива дракона

Алфавіт: { F, G, +, - } Аксіома: F Правила: F \to F+G G \to F-G Кут δ: 90° Крива дракона — це гранична форма, яку отримують, багаторазово згинаючи смужку паперу навпіл у тому самому напрямку.

Форма куща / дерева

Алфавіт: { F, +, -, [, ] } Аксіома: F Правило: F \to FF-[-F+F+F]+[+F-F-F] Кут δ: 22.5° Покоління 4 дає впізнаваний 2D-силует рослини. Дужки [ ] створюють структуру розгалуження.

Папороть Барнслі (через IFS — аналогічна за духом)

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

4. Стохастичні L-системи для природної варіації

Детерміновані L-системи дають геометрично досконалі, надто регулярні структури — дерева, наче відштамповані з форми. Справжні рослини мають варіацію: трохи різні кути гілок, нерівні довжини гілок, асиметричні крони. Стохастичні L-системи призначають імовірності конкуруючим правилам для одного й того самого символу:

// Два конкуруючі правила для F: F \to(0.7) F[+F]F[-F]F // імовірність 70% F \to(0.3) F[+F]F // імовірність 30% Щоразу, коли F переписується, випадковий вибір визначає правило. Різні випадкові початкові значення (seed) \to різні, але структурно схожі дерева. Імовірності для кожного символу-попередника мають у сумі давати 1.0.

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

Для відтворюваного процедурного контенту в іграх випадковий seed зберігається для кожного об'єкта. За того самого seed та граматики завжди регенерується те саме дерево без зберігання повної геометрії — це суттєво заощаджує пам'ять для великих лісів.

5. Контекстно-залежні L-системи

У контекстно-залежній L-системі (IL-система або 2L-система) переписування символу може залежати від його сусідів у рядку. Це моделює міжклітинну сигналізацію — поширення інформації крізь біологічну структуру:

// Запис контекстно-залежного правила left < symbol > right \to заміна Угода: left < A > right відповідає A лише тоді, коли йому передує left і за ним іде right. Приклад: поширення сигналу крізь нитку Алфавіт: { a, b, B } Аксіома: baaaaaaaa (один сигнал «b» на лівому кінці) Правила: b < a > \to b (сигнал b просувається в a праворуч від нього) b \to b (b у позиції без правого контексту лишається b) Покоління 0: baaaaaaaa Покоління 1: bbaaaaaaa Покоління 2: bbbaaaaaaa ... Сигнал «b» поширюється праворуч на одну клітину за крок.

Контекстно-залежні правила дозволяють граматиці моделювати:

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

Ці біологічно мотивовані моделі поєднують чисту математику та фізіологію рослин і були центральними для початкових дослідницьких цілей Ліндемаєра.

6. Параметричні L-системи

У параметричних L-системах кожен символ несе числові параметри, а правила продукції залежать від цих параметрів. Це уможливлює неперервні моделі росту рослин, де довжини й кути гілок змінюються з віком:

// Запис параметричного символу: A(t) — символ A з параметром t // Запис правила: // A(t) : t > 0 \to F(t) [ +(30) A(t-1) ] [ -(30) A(t-1) ] Аксіома: A(5) (починаємо з символу A, вік 5) Правило: A(t): t > 0 \to F(t) [+(30) A(t-1)] [-(30) A(t-1)] A(t): t == 0 \to L (термінальний: символ листка) Покоління 0: A(5) Покоління 1: F(5) [+(30) A(4)] [-(30) A(4)] Покоління 2: F(5) [+(30) F(4)[+(30)A(3)][-(30)A(3)]] [-(30) F(4)\dots] ... Кожен A(t) породжує дві дочірні гілки з віком t-1. A(0) стає листком. Сегмент стебла F(t) має довжину, пропорційну до t.

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

Книга Прусінкевича та Ліндемаєра 1990 року The Algorithmic Beauty of Plants (вільно доступна онлайн) каталогізує десятки параметричних L-систем, що відповідають виміряним ботанічним даним. Вона лишається визначальним довідником у цій галузі.

7. Генерація 3D-рослин

Розширення від 2D-черепашки до 3D вимагає відстеження повного 3D-репера орієнтації. Черепашка несе три ортогональні вектори: H (напрямок), L (ліворуч) та U (вгору). Команди обертання застосовують матриці обертання до цього репера:

Стан 3D-черепашки: (позиція, H, L, U) Початковий: H = (0,1,0), L = (-1,0,0), U = (0,0,1) Обертання навколо U (рискання): символи + та -, кут δ Обертання навколо L (тангаж): & (вниз) та ^ (вгору), кут δ Обертання навколо H (крен): \ (ліворуч) та / (праворуч), кут δ Команда F: рух на d у напрямку H new_position = position + d × H Стек [/]: покласти трійку (position, H, L, U) Стек ]: зняти трійку (відновити позицію та орієнтацію) Тропізм (реакція на гравітацію/світло): застосувати невеликий коригувальний момент τ = e × H до кожного сегмента, де e — пружний коефіцієнт, а H — вектор напрямку. Це згинає гілки вниз (гравітація) або до світла.

Тропізм — згинання росту в бік стимулу або від нього — моделюється невеликою корекцією обертання, застосованою до кожного сегмента гілки. Важка гілка провисає під дією гравітації (негативний геотропізм: e × gravity_vector); черешок листка повертається до сонця (фототропізм).

Вивід геометрії та інстансинг

Для рендерингу в реальному часі сегменти черепашки малюються не як окремі лінійні примітиви, а групуються в меші:

Циліндри гілок: кожна команда F породжує циліндр. Радіус звужується з глибиною: r(depth) = r_trunk × (2/3)^depth (трубкова модель — площа поперечного перерізу зберігається між гілками).
Білборди листя: термінальні символи L випромінюють квадратні білборди, повернені до камери, з текстурою листка. LOD зменшує кількість листя на відстані.
Інстансований рендеринг: великі ліси використовують GPU-інстансинг — рендеринг одного меша дерева N разів із різними матрицями трансформації, що зменшує кількість викликів відмалювання з N до 1.
Рівень деталізації (LOD): ближні дерева використовують повну геометрію L-системи (5–6 поколінь). Далекі дерева переходять на імпостори (попередньо відрендерені спрайти, що переглядаються з 8 ракурсів).

8. Застосування в іграх та візуалізації

L-системи — основа процедурної генерації контенту (PCG) в іграх та програмах візуалізації:

SpeedTree (Interactive Data Visualization): галузевий стандарт мідлвару, що використовувався в Ghost of Tsushima, The Last of Us Part II та багатьох інших. Застосовує параметричні правила у стилі L-систем у поєднанні з ручним налаштуванням художником та симуляцією вітру.
Houdini (SideFX): його вузол «L-System» — це повноцінний геометричний оператор. Художники й технічні директори задають правила граматики у параметрах вузла й отримують оновлення 3D-геометрії в реальному часі. Використовується для лісових сцен у кіно-VFX.
Blender (додаток «Sapling»): генерує скелети гілок з параметричних правил, потім застосовує модифікатори skin/subdivision для гладкої геометрії.
Ботанічні дослідження: Віртуальна лабораторія (vlab) в Університеті Калгарі створює кількісні моделі рослин, що відповідають виміряним даним росту — використовуються для вивчення архітектури посівів та перехоплення світла кроною.
Архітектура: процедурна генерація фасадів, розгалужені планування коридорів та органічні структурні форми використовують генерацію на основі граматик, аналогічну до L-систем.

Порада щодо реалізації: мінімальному рендереру L-систем потрібні три речі: розширювач рядка (застосувати правила N разів), інтерпретатор черепашки (пройти рядок, підтримувати стек) та примітив малювання (лінія canvas, Three.js BufferGeometry тощо). Повна робоча реалізація у 2D займає менш ніж 100 рядків JavaScript. Почніть з DOL-системи з фіксованим кутом, потім поступово додавайте стохастичні та 3D-розширення.

Глибший урок L-систем полягає в тому, що складна, нібито спроєктована структура може виникати з дуже простих локальних правил, застосованих ітеративно. Це знаходить відгук далеко за межами ботаніки: схожі механізми формування візерунків з'являються у візерунках шкіри тварин (реакція-дифузія), мережах міських вулиць, річкових притоках та бронхіальних деревах легень — усі вони виявляють статистичну самоподібність, добре описувану варіантами того самого апарату переписування.