Наверное, вы слышали про технологию Яндекса DeepHD, с помощью которой они как-то раз улучшили качество советских мультфильмов. Увы, в публичном доступе ее еще нет, а у нас, рядовых программистов, вряд ли найдутся силы написать свое решение. Но лично мне, как обладателю Retina-дисплея (2880х1800), недавно очень захотелось посмотреть «Рика и Морти». Какого же было мое разочарование, когда я увидел, как мыльно на этом экране выглядит 1080р, в котором существуют оригиналы этого мультсериала! (это прекрасное качество и обычно его вполне достаточно, но поверьте, ретина так устроена, что анимация с ее четкими линиями в 1080р выглядит мыльновато, словно 480р на FHD-мониторе)

Я твердо решил, что хочу увидеть этот мультсериал в 4К, хотя и совершенно не умею писать нейросети. Однако решение было найдено! Любопытно, что нам даже не придется писать код, понадобится лишь ~100 ГБ места на диске и немного терпения. А результат — четкое изображение в 4К, которые выглядит достойнее, чем любая интерполяция.

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

В этой работе мы сосредоточимся не на скорости, а на чётком объяснении концепций. Код примеров написан наиболее понятным образом, который не обязательно является самым эффективным для реализации алгоритмов. Есть множество способов реализации, я выбрал тот, который проще всего понять.

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

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

Как всегда, в нашем распоряжении только голый компилятор, никаких сторонних библитек использовать нельзя. Я не хочу заморачиваться с оконными менеджерами, обработкой мыши/клавиатуры и тому подобным. Результатом работы нашей программы будет простая картинка, сохранённая на диск. Я совершенно не гонюсь за скоростью/оптимизацией, моя цель — показать основные принципы.

Итого, как в таких условиях нарисовать вот такую картинку за 180 строчек кода?

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

Введение

Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

Алгоритм

Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.

Разработчик, с гуманитарным высшим, средним английским (сильный акцент и неправильное произношение), 15 годами опыта в десятке проектов, обремененный семьей – вдруг решил найти работу в Западной Европе.

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