[Перевод] Процедурная генерация 3D-мешей для интро на 64 КБ

vdsdgsnk2rokucde2fscomwlpfw.jpeg


В предыдущей статье [перевод на Хабре] мы рассказали, как генерируются текстуры в демо H — Immersion. На этот раз мы изучим ещё один важный инструмент для создания демо нужного размера: процедурную геометрию.

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

Для начала кубы


Когда мы начинали создавать демо, ограничение в 64 КБ казалось пугающим. Мы ничего не знали о процедурной генерации мешей, и нам ещё многое предстояло сделать с рендерингом, камерой, текстурами, сюжетом… то есть, практически со всем. Поэтому ещё на ранних этапах разработки нашего первого демо B — Incubation мы приняли решение полностью отказаться от 3D-моделирования. Вместо него мы решили использовать только кубы и спроектировали демо на основании этой концепции.

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

1f076650c71033ad87a49928b9c546fa.jpg


B — Incubation, 2010 год

Вращение!


После этого первого демо на 64 КБ настало время наконец-то создать процедурные меши! Для демо F — Felix«s Workshop мы реализовали рудиментарную генерацию мешей. Демо получило хорошие отзывы, однако код, вероятно, был проще, чем ожидали многие.

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

afcaf3361f7426e5aab9ab57959f1a20.png


F — Felix«s Workshop, 2012 год

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

s1owplzqetgcxzrd3rfbr2ixw0e.png


Числа слева — это 2D-координаты списка контрольных точек. Мы выполняем интерполяцию между точками при помощи сплайнов Катмулла-Рома. Алгоритм Катмулла-Рома был опубликован в 1974 году, подробное его описание можно найти в статье Иньиго Килеза. Фигура справа — это результат (после применения симметрии) использования этой методики со списком точек.

После того, как всё готово, мы можем преобразовать данные в 3D, создав грани вдоль сплайна. Добавив небольшие вариации, можно также создать другие шахматные фигуры. Ниже показан готовый результат.

azhurbiwxhtnoc9u5yeuwzcxcbs.png


F — Felix«s Workshop, 2012 год

Сколько байтов для этого нужно? Не очень много, особенно если многократно использовать техники разнообразными способами на протяжении всего демо. Если хранить каждое число в одном байте, то для описания пешки нам понадобиться меньше 40 байтов данных… и это если не учитывать этап сжатия.

Если вы смотрели исходный код шахматной доски, то заметили, что на самом деле для хранения этих целых чисел в интервале от 0 до 255 мы используем числа с плавающей запятой. Каждое из этих 32-битных float занимает по 4 байта. Разве это не пустая трата байтов? Не совсем: как сказано в предыдущем абзаце, программа сжимается. Если изучить двоичное представление этих float, то можно увидеть, что они очень похожи и заканчиваются серией нулей. Инструмент сжатия (kkrunchy) способен эффективно их упаковывать, и получившийся результат будет меньше, чем если бы начали хитрить.

Если двигаться дальше, то степень сжатия может улучшить дельта-кодирование, но оно даёт выигрыш только при достаточно больших объёмах данных. О float можно сказать ещё многое, я касался этой темы раньше в статье Making floating point numbers smaller.

Расширение и комбинирование


0adf04a3801b90c36cb33c58c5e9e9d0.png


F — Felix«s Workshop, 2012 год

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

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

Просмотрев Felix«s Workshop, вы заметите, что всё создано или при помощи вращения, или из кубов. Мы создали широкий ассортимент объектов, просто комбинируя эти два примитива.

Выращиваем кубы


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

y9hbh2ujnsmo8xa2zkxfuc_na5y.png


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

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

0wjacdetdkz6ngdh7jriz-g4wfa.png


H — Immersion, 2017 год

Экструдирование кубов


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

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

Именно таким образом мы генерировали небольшие статуи, используемые как декоративный реквизит во многих местах демо:

x98y7upxnhl-1fk1nghhw5svjta.jpeg


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

Также для улучшения результатов мы создали две статуи с двумя жёстко заданными параметрами. Вот как они выглядят после применения текстур и освещения.

9wvntn_kmbte5db6afers0bum1w.png


H — Immersion, 2017 год

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

5fbp38jim5uo59npl92bkydxqcq.png


H — Immersion, 2017 год

Marching Cubes


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

Для этого мы использовали совершенно иную технику, которую никогда раньше не применяли: косвенную поверхность, выраженную при помощи полей расстояний со знаком (signed-distance field, SDF). Эта техника очень популярна в интро на 4 КБ, обычно для генерации результата она используется вместе с алгоритмом ray marching и реализуется как шейдер экранного пространства. Но поскольку наш рендеринг основан на мешах, мы сгенерировали полигональный меш, вычисляя функцию SDF при помощи алгоритма marching cube, а не ray marching. Мы выстроили гуманоидную фигуру в виде последовательности сегментов и немного видоизменили её, чтобы придать органичный вид.


sqksxt2ruo6zw2oxz9apslymsi4.jpeg


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

Мы могли позволить себе только такую степень детализации, не говоря уже о том, что моделировать гуманоидов сложно, а люди обычно очень хорошо замечают проблемы в человекоподобных моделях. Мы воспользовались преимуществом низкого разрешения генерируемого меша. Оказалось, что вычисление нормалей на готовом меше (вместо вычисления их из функции SDF) создаёт заметные артефакты: поверхность покрыта плавными сгибами и рёбрами. Такой очень грубый внешний вид придавал скульптуре вид вытесанной из камня. Поверх этого мы использовали освещение и кинематографические техники, чтобы хитростью заставить зрителя восполнить детали при помощи воображения. В кадре статуя выглядит более детализированной, чем есть на самом деле.

vdsdgsnk2rokucde2fscomwlpfw.jpeg


H — Immersion, 2017 год

Онлайн-кубы


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

На определённом этапе мы выложили наш генератор мешей на веб-сервер, как сделали это и с текстурами [перевод на Хабре]. На веб-странице было текстовое поле, куда можно записывать код на C++. При нажатии на кнопку она компилировала код на сервере и возвращала меш в формате JSON. Веб-страница отображала результат при помощи three.js, поэтому мы могли просматривать и вращать модель при помощи мыши. Как и Shadertoy, это позволяло нам быстро проверять идеи, делиться ими с командой, создавать форки и улучшения других моделей.

Позже мы перешли к другому решению, рекомпиляции C++, о которой говорили во вводной статье [перевод на Хабре].

Заключение


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

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

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

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

© Habrahabr.ru