Pull to refresh
  • by relevance
  • by date
  • by rating

Ошибка в формуле проверки условия Делоне

ProgrammingImage processingMathematics
Sandbox

Введение


Ранним воскресным утром я уже третий день сидел за отладкой программы для триангуляции результата лазерного сканирования. Лазерный скан представляет из себя набор трехмерных точек. В результате работы программы нужно объединить точки в непересекающиеся полигоны, таким образом создав модель поверхности. Функцию за функцией я пересчитывал на листочке и, наконец, добрался до функции проверки выполнения условия Делоне. По всей видимости, ошибка затаилась где-то в ней. При детальном разборе оказалось, что формула, указанная в огромном количестве книг про триангуляцию Делоне, не всегда дает верный результат. Подробности под катом.


Читать дальше →
Total votes 36: ↑31 and ↓5 +26
Views22.7K
Comments 23

Генерирование полигональных карт для игр

Game developmentAlgorithms
Translation
Я хотел научиться генерировать интересные игровые карты, которые не обязательно были бы реалистичными, а также попробовать техники, с которыми раньше не работал. Обычно я создаю карты с другой структурой. Что можно сделать с тысячей полигонов вместо миллиона тайлов? Отчётливо различимые игроком области могут быть полезны для геймплея: местоположения городов, места квестов, территории для захвата или колонизации, ориентиры, точки поиска пути, зоны с разной сложностью и т.д. Я генерировал карты с помощью полигонов, а затем растеризировал их вот в такие карты:

image

Во многих процедурных генераторах карт, в том числе и некоторых моих предыдущих проектах, для генерирования карты высот используются функции шума (midpoint displacement, фракталы, diamond-square, шум Перлина и т.д.). Здесь я их не применял. Вместо неё я использовал структуру графов для моделирования элементов, определяемых ограничениями геймплея (высота, дороги, течение рек, места квестов, типы монстров) и функции шума для моделирования того, что не ограничивается геймплеем (форма побережья, расположение рек и деревьев).
Читать дальше →
Total votes 100: ↑99 and ↓1 +98
Views45.1K
Comments 9

Снимаем «4D видео» с помощью depth-сенсора и триангуляции Делоне

ProgrammingC++Algorithms
Sandbox


Привет Хабр! Это заметка о небольшом хобби-проекте, которым я занимался в свободное время. Я расскажу, как с помощью несложных алгоритмов превращать карты глубины от depth-сенсоров в забавный вид контента — динамические 3D сцены (их ещё называют 4D video, volumetric capture или free-viewpoint video). Моя любимая часть в этой работе — алгоритм триангуляции Делоне, который позволяет превращать разреженные облака точек в плотную полигональную сетку. Приглашаю всех, кому интересно почитать про алгоритмы, самописные велосипеды на C++11, и, конечно же, посмотреть на трёхмерных котиков.

Для затравки: вот что получается при использовании RealSense R200: skfb.ly/6snzt (подождите несколько секунд для загрузки текстур, а затем используйте мышку, чтобы поворачивать сцену). Под катом есть ещё!
Обладатели лимитированных тарифов, будьте осторожны. В статье много разных изображений и иллюстраций.
Читать дальше →
Total votes 89: ↑88 and ↓1 +87
Views17.7K
Comments 34

Как я создавал карты континентов для своей игры

Game developmentGame design
Translation
image

Часть 1. SVG и системы координат


До недавнего времени размеры карт в моей игре Dragons Abound были фиксированными и несколько недетерминированными. Я считал их «региональными» — не картами всего мира, но его значительными частями, такими например, как западное побережье США или часть Европы. Меня вполне устраивал этот масштаб, но я хотел немного поэкспериментировать с игрой, чтобы посмотреть, смогу ли я генерировать карты целого мира (или хотя бы большего размера). Но прежде чем я приступлю к этому, давайте немного поговорим о картах фэнтези-миров.

Мир — это большое пространство. Большинство карт фэнтезийных «миров» даже близко не походят на истинный размер. Возьмём, например, Средиземье, в котором происходит действие «Властелина колец»:


Хоть и кажется, что на ней запечатлён огромный мир, на самом деле Средиземье создано на основе Европы.
Читать дальше →
Total votes 55: ↑54 and ↓1 +53
Views33.8K
Comments 3

Равномерное распределение точек в треугольнике

Vector graphicsMathematics
Translation
Большинство двухмерных квазислучайных методов рассчитано на сэмплирование в единичном квадрате. Однако в компьютерной графике также очень важны треугольники. Поэтому я описал простой метод прямого построения для равномерного покрытия последовательностью точек треугольника произвольной формы.


Рисунок 1. Новый прямой метод построения открытой (бесконечной) квазислучайной последовательности с низким расхождением в треугольнике произвольной формы и размера. На рисунке показаны распределения точек в пятнадцати случайных треугольниках для первых 150 точек.

Краткий обзор


Последовательности с низким расхождением (low discrepancy), равномерно сэмплирующие/заполняющие квадрат, активно изучались почти сотню лет. БОльшую часть этих квазислучайных последовательностей можно расширить до прямоугольников простым растягиванием, не сильно повредив при этом расхождению.

Однако в этом посте мы рассмотрим интересное и важное расширение последовательностей с низким расхождением на произвольный треугольник.
Читать дальше →
Total votes 37: ↑37 and ↓0 +37
Views7.7K
Comments 0

Неожиданная эффективность квазислучайных последовательностей

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


Рисунок 1. Сравнение различных квазислучайных последовательностей с низким расхождением. Заметьте, что предлагаемая мной $R$-последовательность создаёт более равномерно распределённые точки, чем все остальные методы. Более того, все остальные методы требуют тщательного подбора базовых параметров, а в случае неправильного подбора приводят к вырожденности (например справа вверху)

Рассматриваемые в статье темы

  • Последовательности с низким расхождением в одном измерении
  • Методы с низким расхождением в двух измерениях
  • Расстояние упаковки
  • Множества с многоклассовым низким расхождением
  • Квазислучайные последовательности на поверхности сферы
  • Квазипериодический тайлинг плоскости
  • Маски дизеринга в компьютерной графике

Какое-то время назад этот пост был выложен на главной странице Hacker News. Можете прочитать там его обсуждение.
Читать дальше →
Total votes 90: ↑90 and ↓0 +90
Views18.4K
Comments 7

Алгоритм триангуляции Делоне методом заметающей прямой

ProgrammingAlgorithms
Tutorial
Доброго времени суток!

В этой статье я подробно опишу алгоритм, который у меня получился в результате использования идеи «заметающей прямой» для построения триангуляции Делоне на плоскости. В нем есть несколько идей, которые я нигде не встречал, когда читал статьи про триангуляцию.
Возможно, кто-то тоже найдет их необычными. Я постараюсь сделать все в лучших традициях и включить в рассказ следующие вещи: описание используемых структур данных, описание шагов алгоритма, доказательство корректности, временные оценки, а также сравнение с итеративным алгоритмом, использующим kD-дерево.
Читать дальше →
Total votes 25: ↑25 and ↓0 +25
Views30.8K
Comments 19

Как использовать диаграммы Вороного для управления ИИ

Game developmentAlgorithmsGame designArtificial Intelligence
Translation
image

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



Пространственные отношения


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

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



У Вороного есть ответ


Диаграмма Вороного описывает пространственное отношение между близко расположенными точками или их их ближайшими соседями. Это множество соединённых многоугольников, полученных из точек или локаций. Каждая линия «области» Вороного находится посередине между двумя точками.
Читать дальше →
Total votes 40: ↑40 and ↓0 +40
Views10.9K
Comments 9

Процедурная генерация многоэтажных 3D-подземелий

Game developmentUnity3D
Translation
image

В последнее время я играл в несколько roguelike, поэтому решил попробовать написать собственный процедурный генератор подземелий. Существует множество способов решения этой задачи, и я выбрал алгоритм автора TinyKeep, описанный здесь. Я расширил этот алгоритм, чтобы он работал в 3D и мог создавать многоэтажные подземелья.

Код примера выложен в репозитории Github. Для демонстрации я использую Unity3D, но эти концепции, разумеется, применимы к любому другому движку.

Два измерения


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

Сцена для этого примера называется Dungeon2D. Код для него находится в папке Scripts2D.

Алгоритм


Мир разделён в виде прямоугольной сетки. Я предполагаю, что 1 единицы будет достаточно для обозначения коридора. В полной игре 1 единица измерения Unity может соответствовать например 5 метрам. Для сетки я выбрал размер 30×30.
Читать дальше →
Total votes 46: ↑46 and ↓0 +46
Views11.5K
Comments 6

Библиотека ttf2mesh — преобразование TrueType шрифтов в сетку

Open sourceWorking with 3D-graphicsCGraphic designGame design

Многим известна проблема трёхмерной графики — отсутствие легковесных кроссплатформенных решений в вопросе вывода текста.


Большинство реализаций позволяет использовать выбранный шрифт в виде текстуры. Публикуемая библиотека ttf2mesh реализует другой способ — она преобразует векторные символы TrueType шрифта в сеточные объекты. Это позволяет выводить текст в виде набора треугольников.


image


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

Читать дальше →
Total votes 34: ↑34 and ↓0 +34
Views4K
Comments 15