StructureSynth: сыграйте мне про архитектуру

АрхивСофтерра

Пакет StructureSynth - пример практического использования формальных грамматик для описания даже очень сложных изображений. Как это всё работает?

Ещё за школьной партой мы узнаём, что любое изображение можно представить в виде множества точек. Сегодня, право, никого не удивить уже фрактальными генераторами ландшафтов или растительности, которые автоматически "отрисовывают" фотографического уровня изображения, опираясь, по сути, на математические формулы, и не более.

Использование формальных грамматик в качестве метода описания изображений впервые появилось в конце 60-х в работах венгерского биолога Аристида Линдермайера, который исследовал микроскопические грибы и бактерии и позднее распространил этот метод и на описание макрообъектов, в частности растений и деревьев. Его метод получил название L-системы (сокращение от Lindermayer-system).

Вслед за его исследованиями последовало большое количество практических приложений и научных публикаций, часть из которых удачно совпала с бумом на фракталы, теорию хаоса и динамические системы в начале 90-х, благо генерация сложной графики стала доступна не только на специализированных мейнфреймах, а любому кодеру-энтузиасту с Amiga или PC. (Интересующимся можно посоветовать прочитать некоторые из его, весьма наглядных и интересных трудов, переводами которых занимаются, к примеру на Хабрахабре).

Основной интерес к L-системам вызван тем, что, как несложно уже догадаться, они представляют собой один из самых простых и наглядных вариантов фракталов (вместе с треугольником Серпинского и кривой Коха). Для понимания принципов подобных изображений не требуется погружаться в бездны комплексного анализа и топологии, достаточно разве что вспомнить школьную геометрию.

Методы L-систем нашли множество как художественных, так и практических применений. Например для создания высокореалистичных текстур, ландшафтов и растений, практически неотличимых на изображении от реальных.

Из числа арт-программ 2000-х одной из самых известных и канонических де-факто стал открытый проект ContextFreeArt:

Неудивительно, что после столь эффектных изображений в 2d, энтузиасты обратились к третьему измерению, благо современные мощности позволяют визуализировать сложнейшие сцены почти в реальном времени. Собственно проект Structure Synth и стал первой известной программой такого рода.

Единственный его автор - Микаель Хвидтфельд Кристенсен (Mikael Hvidtfeld Christensen) в одиночку развивает проект в течение нескольких последних лет (с 2007 г.).

Проект распространяется по GPL и написан на C++ под OpenGL и QT, что позволяет портировать приложение на любые платформы (кроме разве что мобильных, для которых поддержка этих фреймворков если и появилась, то совсем недавно).

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

Основы формальных грамматик

Идеи, лежащие в основе формальных грамматик одновременно и очень просты и очень мощны. Объем теории по машинным языкам очень велик и изучается на многих специальностях, но в первом приближении нам понадобятся только аксиомы.

Для определения “языка” - то есть всех возможных цепочек символов - требуется задать:

1. Множество конечных символов

Множество самых базовых объектов, из которых строится структура или язык. Для естественного или машинного языка это символы, буквы, цифры, для двумерной фигуры это точки на плоскости, прямые, кривые, для трехмерной - соответственно точки в трехмерном пространстве, полигоны, векторы, поверхности.

2. Множество правил

Правило - это некая формальная запись, в которой определяется, как из одной структуры получается другая структура. Правила могут состоять из других правил.

Весьма условный пример правил для русского языка:

СЛОВО = “один или несколько слогов”
СЛОГ = “согласная”+”гласный”
СОГЛАСНАЯ = {б,в,г,д,ж, …, щ}
ГЛАСНЫЙ = {a, е, о, .., я}

Для трехмерной структуры:

КУБ = “Полигон с координатами (0,0,0), (0,1,0), (0, 0, 1)”, “Полигон с координатами (0, 0, 0), (1, 0, 0), (1,1,0) и т.д.

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

3. Стартовое правило

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

Язык Structure Synth

Трехмерные фигуры как грамматики описываются в текстовых файлов специального формата .es (EisenScript).

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

Правила и трансформации оперируют с базовыми геометрическими фигурами (примитивами) в трехмерном пространстве. У фигур, помимо 3d-координат, есть только цвет (но, к сожалению, не текстура, не материал и т.п.).

Очень хочется, но нельзя в качестве базовой фигуры взять уже готовую 3d-фигуру или сцену (хотя при желании и умении это можно добавить в код, например в документации заявлены, но не реализованы несколько примитивов типа цилиндра и конуса).

Результат выполнения - трехмерная полигональная сцена с базовой моделью освещения, которая может быть экспортирована в другие форматы или сохранена как растровое изображение. Её также можно просто покрутить, увеличить или уменьшить в редакторе в окне предпросмотра, программа достаточно быстра на современных PC и начинает притормаживать на сценах от ста тысяч объектов.

Итак, посмотрим, как в Eisenscript реализованы формальные грамматики.

1. Базовые примитивы

Алфавит среды - исходные строительные блоки, из которых создается фигура. Это шар, куб, вектор, прямоугольник, точка, поверхность.

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

Пример примитивов:

• box
• sphere
• grid
• line
• dot

2. Трансформации

Трансформации описывают всевозможные действия, применяемые к текущему состоянию (примитиву): сдвиг по осям x, y, z, повороты по трем осям, изменение цвета (абсолютное значение в RGB, смешивание текущего цвета с другим, изменение параметров тона-яркости-насыщенности (HSV), изменение альфа канала), масштабирование объекта в трех осях, зеркальное отражение, применение матрицы поворота.

Трансформации записываются в фигурных скобках и выглядят как буква (сокращение названия трансформации) и числовое значение-аргумент. Аргумент идет обязательно после пробела.

Аргументом является или число с плавающей запятой или целочисленное значение, зависит от типа.

Изменение в 3d-координатах это float, модификация цвета - integer.

Внутри одной трансформации может быть произвольное количество действий, если происходит несколько однотипных действий, то они автоматически складываются.

Также трансформации могут быть заданы рандомным числом.

Примеры:

• { x 1} // сдвигает текущее состояние по оси x на единицу
  
• {x 2 y 2 z 2} // равномерно сдвигает состояние на 2 единицы по трем осям
  
• {rx 30} // поворачивает относительно оси x на 30 градусов
  
• {sat 10 hue -30} //изменяет атрибуты цвета
  
• {x 1 x 1 x 1} // равно {x 3 }
  

Трансформации записываются сразу перед примитивами (или правилами). Либо это одна трансформация, либо их список, но со знаком умножения, который означает повторение трансформации N раз (итерация).

Пример:

• 1 * { hue 30 x 1 } // равно { hue 30 x 1}
• 10 * { x 1 hue 36 } 10 * { y 1 sat 0.9 } 10 * { z 1 b 0.9 } box

Итерация из примера выше является важным элементом языка.

Запись N * { transform t }, где N и t - некоторые числа, а transform - некоторая трансформация, эквивалентна N записям вида:

• { transform t} …
• { transform t*2} …
• { transform t*3} …
• { transform t*N} …

Как пример

3 * { x 2 } box

это то же самое, что и

• { x 2 } box
• { x 4 } box
• { x 6 } box

3. Правила

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

Неявным правилом является последовательная запись трансформации и примитива из примеров выше, формально это тоже правило языка, только без кодового слова.

Правило состоит из ключевого слова rule, названия (цифробуквенный идентификатор), открывающих и закрывающих фигурных скобок, внутри которых перечислены примитивы, трансформации и другие правила.

• R1

rule R1 {

{ x 0.9 rz 6 ry 6 s 0.99 sat 0.99 } R1

{ s 2 } sphere

• }

4. Стартовое правило

Если не объявить, какое из правил или примитивов вызывается первым, то мы получим пустое изображение. Порядок объявления не имеет значения, главное поставить хотя бы одно из них, в примере выше это R1.

Удивительно, но на этом практически и всё. Конечно, в языке имеется множество тонкостей, связанных с 3-d изображениями, ограничениями количества вычислений, генерацией последовательности цветов и т.д., но фактически достаточно изучить только набор примитивов, способы их трансформаций и запись этого всего в правила, чтобы начать создавать фигуры.

Рекурсия

Как вы могли заметить, после задания стартового символа и правила выполнения, мы нигде не указываем, когда это прекратится. Как уже было неоднократно сказано, правила допускают рекурсивное вложение и перекрестные ссылки. И более того, это и есть основа основ построения всех фрактальных объектов, которые, теоретически, бесконечны.

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

- глобальный лимит числа объектов на сцене (maxobjects)

- предел числа поколений фигур (maxdepth).

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

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

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

Даже с этими настройками наш язык кажется черезчур детерминированным и фигура будет черезчур упорядоченной и симметричной. Для борьбы с этим добавлена “игра хаоса”, выраженная в том, что имена различных правил могут повторяться. При выполнении будет выбираться случайно то или иное правило на основе генератора случайных чисел. К одинаковым правилам может быть приписан вес (weight), повышающий или понижающий его вероятность. Именно в этом месте и начинают получаться фигуры, похожие на живую природу, ведь в ней очень редко встречается строгая упорядоченность.

В итоге добавляется случайность выбора цвета, задаваемая одной из нескольких встроенных схем.

Итог

Рассмотренная программа является с одной стороны очень простой, с другой - очень сложной. Для полноценного творчества в ней требуется не только хорошее пространственное воображение, но и знание основ 3D-графики и школьной стереометрии с тригонометрией. Фигуры ведут себя непредсказуемо, уходят не туда, куда надо, бывают скучны и банальны, в общем демонстрируют все известные проблемы творческого процесса.

Полученные объекты могут быть прекрасными (или унылыми) как сами по себе, так и усилены экспортом в популярные среды типа Blender, в котором они являют обычный набор полигонов, к которым могут быть сопоставлены модели освещения, тумана, амбиентности, а также шейдеры. Также существует плагин для популярной среды реалтаймового видео VVVV, позволяющий сделать из скрипта интерактивную 3D-инсталляцию.

Можно предположить будущее таких программ. Развитие аппаратной поддержки 3D-языки описания шейдеров и модель вычислений CUDA, а также популярные библиотеки физического моделирования могут неимоверно украсить сцены, добавив туда “игру” не только с плоским цветом, но и с поверхностями, тенями, эффектами и искажениями перспективы. Именно “игру” как набор трансформаций внутри сцены, а не более реалистичный рендер средствами рейтрейсинга типа SunFlow.

Сейчас это всего лишь набор полигонов или кубиков, рисуемых, чего греха таить, сильно отстающей от современных возможностей видеокарт, библиотекой OpenGL, что в итоге не сильно отличается от первой 3D-графики начала 1990-х.

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