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

Поскольку у нас есть доступ к исходному коду, мы можем изучить исходники рендерера, чтобы понять, что он делает, однако это довольно объёмная часть движка, а пути рендеринга сильно зависят от контекста, поэтому проще будет исследовать чистый низкоуровневный API (иногда заглядывая в код, чтобы заполнить пробелы).

В последнее время стали популярны ретроспективы классических игр, но очень редко вспоминают о классических инструментах разработки. Мне удалось побеседовать с Тимом Суини о первой версии Unreal Editor, или UnrealEd.

BSP и заблуждения: «Нам нужно написать свой редактор»

Дэвид Лайтбоун: Спасибо, что нашли время поговорить со мной, Тим! Давайте начнём с ранних дней Unreal Editor. Я читал, что Джеймс Шмальц, создатель Epic Pinball, показал вам игру, над которой работал, и когда вы увидели её, то предложили создать для неё редактор. Всё верно?

Тим Суини: Точно! Его вдохновила игра Bullfrog Magic Carpet. Джеймс — безумно талантливый разработчик, но он писал код только на языке ассемблера, он не хотел учить C. [смеётся] Таким образом, он написал на чистом ассемблере этот 3D-движок, который рендерил фон рельефа и игровые объекты. Он не хотел создавать редактор, поэтому вручную изготовил BSP-дерево и поместил на этот рельеф капсулу. Когда я увидел это, я сказал: «Нет-нет-нет, Джеймс, Джеймс… нужно делать совсем не так». [смеётся]

Наша компания создаёт, продвигает и продаёт статический анализатор кода PVS-Studio для C/C++ программистов. Однако, наше взаимодействие с клиентами не ограничивается исключительно продажей им лицензий на продукт PVS-Studio. Например, мы занимаемся некоторыми контрактными работами. В силу NDA обычно рассказать о них мы не можем, да и интересного рассказа не получится. Названия проектов, в которых мы принимаем участие, тоже ничего не скажут большинству наших читателей. Но в этот раз, название как раз говорит о многом. Мы поработали вместе с компанией Epic Games над проектом Unreal Engine. Об этом и будет наш рассказ.

Для начала позвольте мне пожаловаться, что «greeble» — ужасное слово, которое нужно изгнать из словаря.

Ну, сняв камень с души, перейдём к объяснениям. Greeble — это мелкие повторяющиеся детали, добавляемые к модели, чтобы придать ей ощущение масштаба и определённой эстетики. Гриблы стали популярны благодаря классическим научно-фантастическим фильмам, в которых «моделью» часто была физическая скульптура:


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

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

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

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

Часть 1. Знакомство с Marching cubes

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

Вот пример из No Man’s Sky: видео.

Аналогичная техника применяется для отображения изображений с МРТ, metaball-ов и для вокселизации рельефа.

В этой части я расскажу о технике создания разрушаемого рельефа Marching Cubes, а в более общем применении — для создания плавного граничного меша твёрдого объекта. В этой статье мы начнём с рассмотрения двухмерной техники, затем трёхмерной, а в третьей части рассмотрим Dual Contouring. Dual Contouring — это более совершенная техника, создающая тот же эффект.

Из этого туториала вы научитесь писать геометрический шейдер для генерации травинок из вершин входящего меша и использовать тесселяцию для управления плотностью травы.

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

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

В прошлой статье мы рассказали про динамические QR коды, которые записывали на VHS кассеты. Эпидемия PCM зацепила и меня, так что пришло время поковырять этот формат.

Все более или менее знающие Python разработчики знают про такую жуткую вещь как GIL. Глобальный блокировщик всего процесса до тех пор пока Python выполняется в одном из потоков. Он даёт потоко-защищённость методами сравнимыми с садизмом, поскольку любая неявная блокировка в многопоточном приложении смерти подобна, всё что опиралось на параллельное выполнение, умирает в мучениях, раз за разом натыкаясь на блокировку GIL.
Известно что по сей день из-за этого скорбного факта программисты на C++ используют Python-обёртки по большей части лишь в однопоточных приложениях, а программисты на Python пытаются всех убедить, что им и так неплохо живётся.
Казалось бы, если поток порождён в C++, он не знает ни о каком GIL, используй Python без блокировок и радуйся. Радость разработчика однако закончится уже на втором потоке запросившем область глобальных переменных без блокировки.
Однако есть путь ведущий к светлому будущему!
Этот путь был изначально в таком языке как Perl, он же поддерживается в Си-API языка Python и я ума не приложу почему подобный механизм не включен в один из стандартных модулей Python! Способ по сути сводит использование различных под-интерпретаторов Python в разных потоках, причём используя свой GIL для каждого(!!!) без всякого шаманства и магии, просто последовательно вызвав несколько функций и стандартного набора Си-API языка Python!

Пока в мире распознавания объектов обучают десятки и даже сотни зарекомендовавших себя архитектур искусственных нейронных сетей (ИНС), разогревая планету мощными видеокарточками и создавая «панацею» для всех задач компьютерного зрения, мы в Smart Engines твердо идем по исследовательскому пути, предлагая новые эффективные архитектуры ИНС для решения конкретных задач. Сегодня мы расскажем про ХафНет – новый способ поиска точек схода на изображениях.

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

Работа уже опубликована на arXiv и сегодня будет представлена на конференции SIGBOVIK в формате аудиозаписи. В этом посте мы поделимся с вами результатами нашего эксперимента. Мотивация и детали реализации также под катом.

Я выложил на Github новый проект A Simple GPU Hash Table.

Это простая хэш-таблица для GPU, способная обрабатывать в секунду сотни миллионов вставок. На моём ноутбуке с NVIDIA GTX 1060 код вставляет 64 миллиона случайно сгенерированных пар ключ-значение примерно за 210 мс и удаляет 32 миллиона пар примерно за 64 мс.

То есть скорость на ноутбуке составляет примерно 300 млн вставок/сек и 500 млн удалений/сек.

Таблица написана на CUDA, хотя ту же методику можно применить к HLSL или GLSL. У реализации есть несколько ограничений, обеспечивающих высокую производительность на видеокарте:

• Обрабатываются только 32-битные ключи и такие же значения.
• Хэш-таблица имеет фиксированный размер.
• И этот размер должен быть равен двум в степени.

Для ключей и значений нужно зарезервировать простой разграничивающий маркер (в приведённом коде это 0xffffffff).

Всем привет.

Есть такая задача – проверить, являются ли два графа изоморфными друг другу. Т.е., говоря по-простому, узнать, являются ли оба эти графа «одним и тем же» графом, но с разной нумерацией вершин и, в случае задания графов графически, с разным их пространственным расположением. Решение этой задачи не является таким уж очевидным, как может кому-то показаться на первый взгляд: даже для небольших графов взгляд на их графическое представление не всегда даст однозначный ответ. См., например, рисунок в той же Вики: ru.wikipedia.org/wiki/Изоморфизм_графов#Пример.

Ну как, очевидно?

А есть и более сложная задача: поиск в некотором «большом» графе всех подграфов, изоморфных некоторому другому графу «поменьше». Это еще более «темный лес». То есть, конечно, не совсем темный, но задача, согласитесь, не самая простая.

Итак, что же мы имеем?

Собственный софт-процессор на ПЛИС с компилятором языка высокого уровня или Песнь о МышЕ — опыт адаптации компилятора языка высокого уровня к стековому процессорному ядру.

Распространенной проблемой для софт-процессоров является отсутствие средств разработки для них, особенно, если их система команд не является подмножеством команд одного их популярных процессорных ядер. Разработчики в этом случае вынуждены будут решать эту проблему. Прямым её решением является создание компилятора языка ассемблера. Однако в современных реалиях не всегда удобно работать на Ассемблере, так как в процессе развития проекта может изменяться система команд в связи, например, с изменившимися требованиями. Поэтому задача легкой реализации компилятора языка высокого уровня (ЯВУ) для софт-процессора является актуальной.

Компилятор языка Python — Uzh представляется легким и удобным инструментарием для разработки программного обеспечения для софт-процессоров. Инструментарий определения примитивов и макросов как функций целевого языка позволяет критичные места реализовывать на ассемблере процессора. В данной работе рассмотрены основные моменты адаптации компилятора для процессоров стековой архитектуры.

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

Прошлые части цикла «Введение в SSD» поведали читателю про историю появления SSD-накопителей, интерфейсы взаимодействия с ними и популярные форм-факторы. Четвёртая часть расскажет о хранении данных внутри накопителей.

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

Получилось примерно так:



Под катом будет еще, берегите трафик.

Это обзор функциональности, появившейся в Pillow 5.2: применение трехмерных таблиц поиска (3D lookup tables, 3D LUT) для трансформации цвета. Эта техника широко распространена в обработке видео и 3D-играх, однако мало графических библиотек могли похвастаться 3D LUT трансформациями до этого.

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

from PIL import Image, ImageFilter

def washout(r, g, b):
    h, s, v = _rgb_to_hsv(r, g, b)
    if 0.3 < h < 0.7:
        s = 0
    return _hsv_to_rgb(h, s, v)

im = Image.open('./Puffins.jpg')
im = im.filter(ImageFilter.Color3DLUT.generate(17, washout))

Функция, полностью написанная на Пайтоне, применяется к 16,6-мегапиксельной картинке за 75ms.

Работа с изображениями и так ресурсоемка, поэтому я обожаю алгоритмы, которые позволяют убрать сложность от входных параметров. Пять лет назад я реализовал в Pillow гауссово размытие, работающее за одинаковое время для любого радиуса. Не так давно я рассказал как можно уменьшить изображение за константное время с минимальной потерей качества. Сегодня я покажу для каких задач можно применять 3D LUT, какие у нее ограничения и похвастаюсь достигнутой производительностью в Pillow-SIMD.

Для меня эти две модели очень похожи, однако у них нет очевидных характеристик, по которым можно было бы измерить их сходство. У этих моделей разное количество вершин, рёбер и полигонов, они разного размера, к тому же по-разному повёрнуты в пространстве, и у обеих одинаковые трансформации (Положение = [0,0,0], Вращение в радианах = [0,0,0], Масштаб = [1,1,1]). Как определить их подобие?

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

В статье очень подробно объясняется, как работают Zip-файлы и схема сжатия: LZ77-сжатие, алгоритм Хаффмана, алгоритм Deflate и прочее. Вы узнаете историю развития технологии и посмотрите довольно эффективные примеры реализации, написанные с нуля на С. Исходный код лежит тут: hwzip-1.0.zip.