Недавно, на хабрахабре была опубликована статья, целиком и полностью посвященная диаграммам Вороного. В статье автор подробно описывает алгоритм Форчуна, применяемый для построения Диаграммы Вороного за O(n*log(n)). Стоит отметить, что описание этого алгоритма не раз появлялось в рунете, в то время как о других алгоритмах (с той же асимптотикой) рассказано ровным счетом ничего. Данная статья исправляет это недоразумение, а также является отличным дополнением к уже опубликованному ранее материалу.

Ниже я расскажу о алгоритме 'разделяй и властвуй' построения диаграммы Вороного за O(n*log(n)), а также, основываясь на своем практическом опыте, о по-настоящему крутых штуках, в которых это применимо. Вообще, алгоритмы типа 'разделяй и властвуй' являются своего рода классикой программирования (думаю, про сортировку данным методом слышал каждый программист), хорошо параллелятся и легко читаются (если, конечно, знать основную идею алгоритма).

Тема Аллокаторов частенько всплывает на просторах интернета: действительно, аллокатор — эдакий краеугольный камень, сердце любого приложения. В этой серии постов я хочу в подробностях рассказать о одном весьма занимательном и именитом аллокаторе — JeMalloc, поддерживаемый и развиваемый Facebook и используемый, например, в bionic[Android] lib C.

В сети мне не удалось найти каких-либо подробностей, полностью раскрывающих душу данного аллокатора, что по итогу сказалось на невозможности сделать какие-либо выводы о применимости JeMalloc при решении той или иной задачи. Материала вышло очень много и, дабы читать его было не утомительно, начать предлагаю с основ: Базовых Структур Данных используемых в JeMalloc.

Под катом рассказываю о Pairing Heap и Bitmap Tree, формирующих фундамент JeMalloc. На данном этапе я не затрагиваю тему многопоточности и Fine Grained Locking, однако, продолжая серию постов, обязательно расскажу про эти вещи, ради которых, собственно, и создается разного рода Экзотика, в частности и та, что описывается ниже.

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

«Мы начинаем разработку новой игры, и нам нужна классная вода. Такую сможешь?»


, — cпросили меня. «Да не вопрос! Конечно, смогу», — ответил я, но голос предательски задрожал. «А, еще и на Unity?», — и мне стало понятно, что впереди очень много работы.

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

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

Уравнения движения

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

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

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

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

Всем привет. Все кто хоть немного разбирался в теме OpenGL знают, что существует большое количество статей и курсов по этой теме, но многие не затрагивают современный API, а часть из них вообще рассказывают про glBegin и glEnd. Я постараюсь охватить некоторые нюансы нового API начиная с 4-й версии. Ссылка на вторую часть статьи

Привет, Хабр!

Как законодатели мод по теме Unity на российском рынке предлагаем вам почитать интересное исследование о практическом использовании алгоритма WFC (Wave Function Collapse), построенного по образу и подобию известного принципа квантовой механики и очень удобного при процедурной генерации уровней в играх. Ранее на Хабре уже публиковался подробный рассказ об этом алгоритме. Автор сегодняшней статьи Мариан Кляйнеберг рассматривает алгоритм в контексте трехмерной графики и генерации бесконечного города. Приятного чтения!

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

А что же в играх?

Допустим, появилась необходимость использовать Color Dodge смешивание для системы частиц или UI-художник сделал красивую графику для игрового интерфейса, но некоторые его элементы используют какой-нибудь Soft Light. А может, вам понадобилось подвергнуть трёхмерный объект Divide-смешиванию, чтобы получить эффект прямиком из кинокартин Линча?



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

Почти 10 лет назад я прочитал статью Макса Тегмарка, гениального физика и философа, и нашел в ней ответы на многие вопросы, которые мучали меня всю жизнь. Статья потрясающая, месяца два я ходил под впечатлением от нее. К сожалению, это лонгрид, к тому же на английском. Поэтому я решил даже не перевести ее – перевод все равно оказался бы слишком длинным для Хабр, но хотя бы изложить основную идею в том порядке, как мне это кажется логичным, и убрав излишние детали (да простит меня Макс!)

Преобразование моделей «на лету» — нередкая практика в симуляции физики деформаций, а также в играх с динамически генерируемым и изменяемым контентом. В таких случаях удобно применять методы процедурного редактирования и создания геометрии. Последние часто позволяют сэкономить заветные байты при передаче подгружаемых из сети данных. Кроме того — это весело!

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

Есть класс задач, которые нельзя ускорить за счёт оптимизации алгоритмов, а ускорить надо. В этой практически тупиковой ситуации к нам на помощь приходят разработчики процессоров, которые сделали команды, позволяющие выполнять операции на большим количеством данных за одну операцию. В случае x86 процессоров это инструкции сделанные в расширениях MMX, SSE, SSE2, SSE3, SSE4, SSE4.1, SSE4.2, AVX, AVX2, AVX512.

В качестве «подопытного кролика» я взял следующую задачу:

Есть неупорядоченный массив arr с числами типа uint16_t. Необходимо найти количество вхождений числа v в массив arr.

Классическое решение, работающее за линейное время выглядит так:

int64_t cnt = 0;
for (int i = 0; i < ARR_SIZE; ++i)
    if (arr[i] == v)
        ++cnt;

В таком виде бенчмарк показывает следующие результаты:

------------------------------------------------------------
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_Count                   2084 ns       2084 ns     333079

Под катом я покажу как его ускорить в 5+ раз.

Всем день добрый! Это статья о том, как профайлить Unity игры на Android с Android Studio. Я расскажу о том, как настроить Android Studio и получить максимальное кол-во данных. Вопросы анализа и выводов на основе полученного результата находятся вне рамок данной статьи.

Всем привет! Меня зовут Гриша, и я основатель CGDevs. Математика – очень крутой инструмент при разработке игр. Но если скажем без понимания векторов и матриц обойтись в принципе сложно, то алгоритмы триангуляций не столь обязательная вещь, но с помощью них решается достаточно большое количество интересных задач. Сегодня хотелось бы поговорить про достаточно важный инструмент в вычислительной геометрии, такой как триангуляции и их применение в игровой индустрии. Кроме того, я написал порт и немного обёрток великолепной библиотеки Triangle.Net для Unity. Если интересно – добро пожаловать под кат. Ссылка на гитхаб прилагается.

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

Мне не очень нравится подход с voxelized / marching cubes при рендеринге воды (см. например, рендеринг симуляции жидкости в Blender). Когда объём воды находится в том же масштабе, что и используемая для рендеринга сетка, движение получается заметно дискретным. Эту проблему можно решить, увеличив разрешение сетки, но для тонких струй на относительно длинные расстояния в реальном времени это просто непрактично, потому что сильно влияет на время выполнения и занимаемую память. (Есть прецедент использования разреженных воксельных структур, улучшающий ситуацию. Но я не уверен, насколько хорошо это работает для динамических систем. Кроме того, это это не тот уровень сложности, с которым я бы хотел работать.)

Первой альтернативой, которую я исследовал, были меши экранного пространства Мюллера (Müller’s Screen Space Meshes). В них используется рендеринг частиц воды в буфер глубин, его сглаживание, распознавание соединённых фрагментов похожей глубины и построение из результата меша с помощью marching squares. Сегодня этот способ, вероятно, уже стал более применимым, чем в 2007 году (поскольку теперь мы можем создавать меш в compute-шейдере), но он всё равно связан с бОльшим уровнем сложности и затрат, чем бы мне хотелось.

В конце концов я нашёл презентацию Саймона Грина с GDC 2010 «Screen Space Fluid Rendering For Games». Она начинается точно так же, как и Screen Space Meshes: с рендеринга частиц в буфер глубин и его сглаживания. Но вместо построения меша получившийся буфер используется для затенения и композитинга жидкости в основной сцене (с помощью записи глубины явным образом.) Именно такую систему я и решил реализовать.