L-системи: від рядка до 3D-рослини

1. Що таке L-система?

Система Ліндермайєра (L-система) — це формальна граматика, винайдена 1968 року біологом Аристідом Ліндермайєром для моделювання росту водоростей, а пізніше й вищих рослин. На відміну від граматики хомскіанського типу, яку використовують для парсингу, L-система є генеративною: вона стартує з короткого рядка-«зерна» і переписує кожен символ паралельно на кожній ітерації. Саме це паралельне переписування робить її природним інструментом для моделювання біологічного росту — адже кожна клітина справжньої рослини ділиться в один і той самий «такт».

Формально L-система задається кортежем G = (V, ω, P):

Щоб отримати наступне покоління рядка, скануємо поточний рядок зліва направо й замінюємо кожен символ одночасно на відповідний наступник із P (символи без відповідного правила лишаються без змін — вони діють як власне тотожне правило). Повторення цього процесу n разів дає рядок «покоління n», який зазвичай позначають Lₙ.

2. Переписування рядків на прикладі

Найпростіша можлива L-система — модель водоростей, яку Ліндермайєр використав у своїй оригінальній статті 1968 року — має алфавіт {A, B}, аксіому A і два правила:

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

function rewrite(axiom, rules, generations) {
  let current = axiom;
  for (let g = 0; g < generations; g++) {
    let next = '';
    for (const symbol of current) {
      // якщо правила немає — використовуємо тотожне правило
      next += rules[symbol] ?? symbol;
    }
    current = next;
  }
  return current;
}

const algaeRules = { A: 'AB', B: 'A' };
rewrite('A', algaeRules, 5); // → "ABAABABAABAAB"

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

3. Графіка черепахи: символи в лінії

Щоб перетворити рядок символів на зображення, проходимо рядок зліва направо й інтерпретуємо кожен символ як інструкцію для черепахи — курсора з позицією та напрямком погляду. Класичний алфавіт (введений Пруцінкевичем і Ліндермайєром у книзі The Algorithmic Beauty of Plants) виглядає так:

Саме пара [ ] перетворює просту ламану лінію на гіллясте дерево: збереження стану перед бічною гілкою й відновлення після неї дає змозі черепасі «телепортуватися» назад до стовбура й продовжити рух, ніби гілки й не було. Класична аксіома гілкування виглядає так:

4. Графіка черепахи у 3D

2D-черепасі достатньо кута напрямку. 3D-черепасі потрібна повна орієнтація — три взаємно ортогональні одиничні вектори: H (heading, напрямок руху), L (left, ліворуч) і U (up, вгору). Поворот черепахи означає обертання цієї системи координат навколо однієї з трьох осей. Розширений алфавіт Пруцінкевича додає ще шість символів:

У коді орієнтацію черепахи краще представляти кватерніоном (або матрицею обертання 3×3), а не окремими векторами H/L/U — це дозволяє уникнути gimbal lock і чисто композиціюється з Three.js:

class Turtle3D {
  constructor() {
    this.pos = new THREE.Vector3(0, 0, 0);
    this.quat = new THREE.Quaternion(); // тотожність = напрямок +Y
    this.stepLen = 1.0;
    this.stack = [];
  }

  forward(draw, segments) {
    const dir = new THREE.Vector3(0, 1, 0).applyQuaternion(this.quat);
    const next = this.pos.clone().addScaledVector(dir, this.stepLen);
    if (draw) segments.push({ from: this.pos.clone(), to: next.clone() });
    this.pos = next;
  }

  rotate(axis, degrees) {
    const q = new THREE.Quaternion().setFromAxisAngle(axis, THREE.MathUtils.degToRad(degrees));
    this.quat.multiply(q); // обертання у власній локальній системі черепахи
  }

  push() {
    this.stack.push({ pos: this.pos.clone(), quat: this.quat.clone(), len: this.stepLen });
  }

  pop() {
    const s = this.stack.pop();
    this.pos = s.pos; this.quat = s.quat; this.stepLen = s.len;
  }
}

const UP = new THREE.Vector3(0, 0, 1);   // вісь H
const LEFT = new THREE.Vector3(1, 0, 0); // вісь L
const FWD = new THREE.Vector3(0, 1, 0);  // початковий напрямок

function interpret3D(str, turtle, angle = 22.5) {
  const segments = [];
  for (const c of str) {
    switch (c) {
      case 'F': turtle.forward(true, segments); break;
      case 'f': turtle.forward(false, segments); break;
      case '&': turtle.rotate(LEFT,  angle); break;
      case '^': turtle.rotate(LEFT, -angle); break;
      case '+': turtle.rotate(UP,    angle); break;
      case '-': turtle.rotate(UP,   -angle); break;
      case '\\': turtle.rotate(FWD,  angle); break;
      case '/': turtle.rotate(FWD, -angle); break;
      case '|': turtle.rotate(UP,    180); break;
      case '[': turtle.push(); break;
      case ']': turtle.pop();  break;
    }
  }
  return segments;
}

5. Стохастичні L-системи

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

function pickWeighted(options) {
  // options: [{ str, p }, ...], де p у сумі дає ~1
  let r = Math.random();
  for (const opt of options) {
    if ((r -= opt.p) < 0) return opt.str;
  }
  return options[options.length - 1].str; // запобіжник на похибку округлення
}

const stochasticRules = {
  F: [
    { str: 'F[+F]F[-F]F',   p: 0.34 },
    { str: 'F[+F][-F]F',    p: 0.34 },
    { str: 'F[+F][-F][F]',  p: 0.32 },
  ],
};

Оскільки кожна гілка розв'язує власний випадковий вибір незалежно, дві гілки, що починалися однаково, швидко розходяться — це візуальна ознака природної крони, а не фрактального «шпалерного» візерунка. Завжди задавайте seed для джерела випадковості (напр., невеликий PRNG mulberry32), якщо потрібні відтворювані дерева для збереженої сцени.

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

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

function expandParametric(axiomTokens, apply, generations) {
  let tokens = axiomTokens; // [{sym:'F', args:[1.0, 0.1]}, ...]
  for (let g = 0; g < generations; g++) {
    const next = [];
    for (const tok of tokens) {
      const produced = apply(tok); // повертає масив токенів або null → залишити як є
      next.push(...(produced ?? [tok]));
    }
    tokens = next;
  }
  return tokens;
}

function applyRule(tok) {
  if (tok.sym !== 'F') return null;
  const [l, r] = tok.args;
  if (l < 0.05) return [tok]; // умова зупинки: гілка занадто мала, щоб розгалужуватись далі
  return [
    { sym: 'F', args: [l * 0.9, r * 0.7] },
    { sym: '[' }, { sym: '+' },
    { sym: 'F', args: [l * 0.7, r * 0.5] },
    { sym: ']' },
    { sym: 'F', args: [l * 0.9, r * 0.7] },
  ];
}

7. Від шляху черепахи до сітки

Інтерпретатор черепахи, описаний вище, дає плаский список відрізків — чудово для налагоджувального превью LineSegments, але справжньому дереву потрібні тверді звужені гілки. Стандартний підхід: замінити кожен відрізок коротким циліндром (або зрізаним конусом, оскільки радіус змінюється вздовж гілки), орієнтованим від точки from до точки to, а потім об'єднати всі їх в одну BufferGeometry для одного виклику малювання.

function segmentToCylinder(seg) {
  const dir = new THREE.Vector3().subVectors(seg.to, seg.from);
  const len = dir.length();
  const geo = new THREE.CylinderGeometry(
    seg.radiusEnd, seg.radiusStart, len, 6, 1
  );
  geo.translate(0, len / 2, 0); // точка опори в основі, циліндр за замовчуванням центрований

  // вирівняти локальну +Y з напрямком відрізка
  const quat = new THREE.Quaternion().setFromUnitVectors(
    new THREE.Vector3(0, 1, 0), dir.clone().normalize()
  );
  geo.applyQuaternion(quat);
  geo.translate(seg.from.x, seg.from.y, seg.from.z);
  return geo;
}

function buildTreeMesh(segments, material) {
  const geometries = segments.map(segmentToCylinder);
  const merged = THREE.BufferGeometryUtils.mergeGeometries(geometries);
  return new THREE.Mesh(merged, material);
}

Невеликої кількості радіальних сегментів (5–6 граней) достатньо для віддалених гілок; залиште 8–12 граней для стовбура, де фасети дійсно видно зблизька. Якщо ваша L-система параметрична, беріть radiusStart/radiusEnd напряму з аргументів F(l, r), записаних під час інтерпретації, замість фіксованого радіуса.

8. Додавання листя через інстансинг

Листя найкраще розміщувати на кінчиках рекурсії — фіксуйте позицію й орієнтацію черепахи щоразу, коли інтерпретація доходить до символу листка (зазвичай L), а потім малюйте тисячі листків одним викликом малювання за допомогою InstancedMesh замість тисяч окремих об'єктів Mesh:

const leafGeo = new THREE.PlaneGeometry(0.3, 0.5);
const leafMat = new THREE.MeshStandardMaterial({ color: 0x4aade80, side: THREE.DoubleSide });
const leaves = new THREE.InstancedMesh(leafGeo, leafMat, leafPositions.length);

const dummy = new THREE.Object3D();
leafPositions.forEach((leaf, i) => {
  dummy.position.copy(leaf.pos);
  dummy.quaternion.copy(leaf.quat);
  const s = 0.8 + Math.random() * 0.4; // невелика варіація розміру листка
  dummy.scale.setScalar(s);
  dummy.updateMatrix();
  leaves.setMatrixAt(i, dummy.matrix);
});
leaves.instanceMatrix.needsUpdate = true;

9. Продуктивність і типові пастки

• Експоненційне зростання рядка. Правила на кшталт F → FF[+F][-F] приблизно подвоюють довжину рядка з кожним поколінням. Восьме покоління гіллястого правила вже може перевищувати мільйон символів — обмежуйте кількість поколінь 5–7 для інтерактивного використання і віддавайте перевагу параметричним умовам зупинки, а не грубому лічильнику ітерацій.
• Не перебудовуйте сітку щокадру. Переписування рядка й інтерпретація черепахою — це одноразові витрати (або такі, що відбуваються лише при зміні параметрів). Кешуйте об'єднану BufferGeometry й перегенеровуйте лише тоді, коли параметри L-системи справді змінилися.
• Джиттер кута дешевший за випадковість на рівні рядка для дешевого урізноманітнення: лишіть один детермінований рядок L-системи, але додайте невелике випадкове відхилення ±ε градусів до кожного повороту черепахи на етапі інтерпретації. Значно дешевше, ніж підтримувати повноцінну стохастичну граматику, і все одно ламає ідеальну самоподібність.
• Баланс дужок. Одна незбалансована [ або ] у вручну написаному правилі тихо руйнує весь стек для решти рядка. Перевіряйте баланс дужок після кожного проходу переписування, особливо коли правила стохастичні й генеруються програмно.
• Масштабуйте перед відсіканням. Виконуйте frustum culling для цілих дерев, а не для окремих сегментів гілок — обчислення обмежувальних сфер для кожного сегмента дерева з 50 000 сегментів коштує дорожче, ніж просто його намалювати. Групуйте culling на рівні дерева (або чанку LOD).

Коли окремі дерева рендеряться плавно, природний наступний крок — рендеринг цілого лісу; дивіться GPU-прискорені дерева з L-систем про об'єднання тисяч згенерованих дерев в один інстансований виклик малювання.