(no subject)

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

Поэтому процедурные техники могут быть использованы для создания различных видов "активов". Одна из самых примитивных используемых техник - генерирование 3d-примитивов с набором случайных параметров, например, кубоиды различной высоты. Простые алгоритмы, использующие псевдослучайную генерацию могут быть использованы для генерирования шума при создании текстур и природного ландшафта. Более сложные рекурсивные алгоритмы, такие, как фракталы или L-системы, используются при воссоздании более сложных природных структур, например, уникальных снежинок или деревьев.
Эберт определил следующие важные особенности процедурных техник:
1. Абстракция: данные о геометрии и текстурах не определены в обычном смысле, вместо этого детали абстрагированы в алгоритм, или ряд процедур. Эти процедуры выполняются компьютером и вызываются тогда, когда они необходимы. Для этого необходим минимум деталей, и оператор может легко манипулировать данными о модели без необходимости досконально изучать реализацию объекта в реальной жизни.
2. Управление через параметры: специфика функционирования процедурной генерации предписывает чётко определять параметры модели. Разработчик может определить столько видов параметров, сколько необходимо для того, чтобы художник мог эффективно работать с полученной на выходе моделью. Примером таких параметров может служить высота гор в алгоритме создания ландшафта, который используется в множестве отраслей сферы процедурного генерирования.
3. Гибкость: возможность представить суть организации некоего "актива" без необходимости запихивать его в рамки реального мира. Параметры могут варьироваться для создания широкого спектра результатов, которые далеко не обязательно ограничены рамками оригинальной модели.
Процедурные техники нашли успешное применение в генерации большого количества сложных явлений в компьютерной графике, и использовать их действительно выгодно по целому ряду причин.
Текстуры, геометрия и эффекты, абстрагированные в процедурные алгоритмы, не фиксированы так, как разрешение экрана или количество полигонов. Поэтому процедурные техники являются по своей сути "мульти-разрешением в природе", и могут варьировать сложность результата, получаемого на выходе. Эта возможность и представляет интерес, в частности, для компьютерной графики. Например, уровень детализации (ЛОД) важен для любой системы 3d-рендеринга, и особенно существенен в системах реал-тайм рендеринга. ЛОД позволяет использовать упрощённые версии "актива", если в данный момент нет необходимости выводить финальный рендеринг, а имеет место промежуточный. Грубо говоря, объект, занимающий 4 пикселя в конечной картинке, не требует 10000 полигонов, и базовое представление объёмом в 10 полигонов будет достаточным. Природа мульти-резолюционная природа процедурных техник позволяет автоматически генеирровать модели различного с уровнем детализации.
Для генерируемого объекта также возможно "краткое описание", и чаще оно может быть выражено с помощью нескольких простейших параметров модели. Эти простейшие описания могут быть использованы для создания большого количества детализованных структур и геометрий, этот эффект известен как "усиление данных" (data amplification), и позволяют разработчикам замахнуться на создание целого игрового мира, который легко можно перенести передать по низкоскоростному соединению. Краткость процедурных техник используется создателями сложных высоко детализированных демосцен, умещающихся в один exeшник размером в районе 2 кб.
Гибкость и контроль через процедурные техники дают дизайнеру платформу для художественной свободы и экспериментов. Новые визуальные эффекты и оригинальные объекты могут быть созданы путём экспериментов с значениями параметров, выходящими за привычные рамки.
Обычно процедурные алгоритмы реализуются в ПО, однако в настоящее время прогресс в графическом оборудовании открывает возможности для их щапуска непосредственно на ГПУ. Например, такие сложные процедурные техники, как объёмные текстуры, которые раньше невозможно было релизовать в реалтайме, теперь вполне достижимы.
Теперь опишем ряд фундаментальных процедурных тезник и алгоритмов, успешно применённых в сфере компьютерной графики.
Фракталы
Природные формы не опишешь простыми геометрическими методами. Не бывает сферических облаков и коническимх гор. Природные форму неправильны, и не могут быть сравнены с обычной геометрией. Однако эти формы могут быть описаны при помощи фрактальной математики. Бенуа Мандельброт, которого называют "отцом фракталов", утвердил понятияе фрактала (от лат. fractus - разрушенный) в 1975 году.
Базовая концепция фракталов состоит в том, что они содержат огромное число "самосходств". То есть они обычно состоят из небольших копий самих себя, встроенных в оригинал, как звезда встроена в Снежинку Коха. Кроме того, фракталы обладают бесконечным количеством деталей, поэтому для любого заданного фрактала актуально следующее: чем ближе мы присмотримся к фракталу, тем больше деталей он демонстрирует.
Как и в любой процедурной технике, форма фрактала определена алогритмом. В этом случае эти алгоритмы рекурсивны, и последовательные рекурсии выдают более детализиорванную версию базового объекта. Самосходство достигается генерированием тех же форм или шаблонов для всё более и более меньшего масштаба по ходу рекурсии, это свойство чаще называют инвариантностью шкалы. Количество рекурсий теоретически не ограничивается, что и даёт бесконечность уровней детализации фрактала.
Визуализация фракталов вручную рутинна, утомительна и ограниченна, поэтому вычислительные алгоритмы, применяемые для создания фракталов, появились с самого начала. Мандельброт, будучи работником IBM, использовал компьютеры для визуализации сложных фракталов, включая Сет Мандельброта.
Фракталоподобные фигуры, вроде деревьев или папоротников, могут быть процедурно сгенерированы при помощи относительно простых рекурсивных алгоритмов. Фактически, широкий спектр природных структур от простейших растений до ландшафта могут быть сгенерированы таким образом. Фрактальные алгоритмы обеспечивают эффективную абстракцию структурной сложности природных объектов, которые они представляют, и могут использовать рекурсию для обеспечения разного уровня детализации. Эти техники также обеспечивают ключевое свойство "усиления данных" в этих сложных моделях, которые могут быть сгенерированы рекурсивным применением простых уравнений.
Фракталы, однако, ограничены тем, что содержат лишь структуры, сходные с оригиналом; объекты же, которые мы хотим смоделировать, могут и не содержать такие структуры. Поэтому во многих отраслях их приходится заменять более гибкими алгоритмами, такими, как формальная грамматика и L-системы.

L-системы
Вкратце системы Линденмайера, или L-системы, есть формальная грамматика, разработанная биологом Линденмайером в качестве математической теории для биологических разработок. L-системы изначально разработаны для изучения размножения бактерий и шаблонов роста простейших организмов, вроде морских водорослей, описанных Линденмайером в Журнале Теоретической Биологии в 1968 году. Система и её применение эволюционировали, и теперь применяются в сфере компьютерной графики и в частности для генерации фракталов и реалистичных моделей растений.
Центральной концепцией L-систем является перезапись. В общем, перезапись есть техника для определения сложных объектов при помощи последовательной замены частей простого начального объекта путём использования комплекса правил или образцов перезаписи. L-системы содержат следующие компоненты:
1. V (алфавит) - комплекс символов, содержащих элементы, которые можно заменить (переменные);
2. S - комплекс символов, содержащих фиксированные, неизменяемые элементы (постоянные);
3. w (омега) (начало, аксиома, инициатор) - строка символов и постоянных, определяющих начальное состояние системы;
4. P - комплекс правил или шаблонос, определяющих, каким образом переменные могут заменяться комбинацией; постоянных или других переменных. Шаблоны состоят из двух строк: предшественник и последователь.
Начальное состояние, или аксиома, вызывается для того, чтобы быть затем перезаписанным при помощи серии правил или шаблонов перезаписи, P. Шаблоны применяются итеративно, позволяя определять свойства сложных комплексных объектов с помощью небольших наборов таких шаблонов.
V = {a, b}   ω:   a
ω=a   n=1 :   ab
P1 : a → ab   n=2 :   abba
P2 : b → ba   n=3 :   abbabaab
The Thue-Morse system
L-системы могут использоваться для визуализации структур добавлением графических символов в строку, которая может быть позднее использована при рендеринге. "Turtle"-команды мб использованы для описания и визуализации широкого спектра L-систем, включая снежинку Коха, растения и ветвящиеся структуры. Концепт Turtle Graphics в том, что "черепаха" суть заданные инструкции относительно её текущей позиции, и по мере своего движения она оставляет за собой след, сродни шариковой ручке. Использование "черепаховой графики": формы, рисование и структуры, описываемые с помощью L-систем. Используя "turtle graphics" в качестве подспорья, L-системы могут воспроизводить ветвящиеся структуры вроде деревьев, являющиеся предоминирующими в природе.
L-системы были созданы с тем, чтобы определить и визуализировать сложные растения и прочие природные структуры. Кроме того, что это академическое исследование было применено в ботанике, оно было продолжено и развито также и в процедурной генерации. Сделаны важные шаги в этом направлении, и уже сейчас доступны коммерческие приложения, применяющие L-системы для генерирования богатых ландшафтов с детализированной флорой с широким спектров представленных видов растений. Например, Speedtree.
L-системы - хороший пример процедурных техник по многим причинам. Они позволяют определить, смоделировать и визуализировать сложные комплексные модели и органические структуры с помощью небольшого набора параметров. Различный уровень сложности детализации обеспечивается такими параметрами, как уровень рекурсии L-системы. Алгоритмы могут быть определены компактным и интуитивно-понятным способом и могут эффективно абстрагировать рекурсивную структуру многих природных явлений. Генерирование с помощью L-систем может быть легко отрегулировано через внешние параметры, и легко расширяется при применении схожестей других природных объектов с различными видами формальной грамматики.

3. Perlin noise
Шум Перлина изначально был изобретён для создания более "натурально выглядящих" текстур. Техника изобретена Кеном Перлином для использования в фильме Трон в 1982 году. За результат работы в фильме Трон доктор Перлин получил Академическую Награду за Техническое достижение в 1997 году. Шум создан первой псевдослучайной функцией для генерации серии значений, которые затем интерполируются в когерентный шум. Различные уровни этого когерентного шума затем композируются вместе с применением различных взаимосвязей, в результате чего на выходе получается "натурально выглядящая" текстура с детализацией уровня фрактала.
Функция шума.
Функция шума генерирует случайные данные. Поэтому каждый раз, когда функция вызывается, возвращается новое число. Это полезно, однако не позволяет контролировать получение результатов. Обычно применяется параметрический контроль генератора шума с отобранной случайной функцией.
Функция интерполяции.
Интерполяция - процесс постановки кривой, в которой заложена функция, и которая проходит точно через точки введённых данных. Эта функция может генерировать новые точки данных, в этом случае вводные точки генерируются функцией шума. Для конечного набора точек данных может быть сгенерирована функция, что позволит нам получить бесконечный спектр точек. Несколько различных алгоритмов могут выполнить такую интерполяцию. Алгоритмы варьируются по точке, которую они принимают за входную, а также по точности и сложности вычислений, и по сглаженности кривой, которую они могут сгенерировать. (см. Кубическая интерполяция - медленно, но гладкая кривая).
Турбулентность.