В процессе решения некоторой задачи, я наткнулся на одно интересное свойство триангуляции ДелонеЧитать полностью »
Рубрика «триангуляция Делоне»
Об одном интересном свойстве триангуляции Делоне
2024-07-13 в 10:45, admin, рубрики: Алгоритмы, диаграмма Вороного, доказательство, математика, триангуляция Делоне
Метод конечных элементов своими руками
2024-02-09 в 13:30, admin, рубрики: МКЭ, прочность, сопромат, триангуляция Делоне
Библиотека ttf2mesh — преобразование TrueType шрифтов в сетку
2020-05-14 в 14:06, admin, рубрики: C, MESH, open source, svg, Wavefront obj, графический дизайн, Дизайн игр, компьютерная графика, построение графов, Программирование, Работа с 3D-графикой, триангуляция Делоне, шрифтыМногим известна проблема трёхмерной графики — отсутствие легковесных кроссплатформенных решений в вопросе вывода текста.
Большинство реализаций позволяет использовать выбранный шрифт в виде текстуры. Публикуемая библиотека ttf2mesh реализует другой способ — она преобразует векторные символы TrueType шрифта в сеточные объекты. Это позволяет выводить текст в виде набора треугольников.
Такой подход имеет как важные преимущества, так и недостатки. Сложность описываемой далее задачи и созерцание великолепных форм шрифтового дизайна доставили массу удовольствия при разработке. Надеюсь, и Вам понравится.
Процедурная генерация многоэтажных 3D-подземелий
2019-12-20 в 4:25, admin, рубрики: roguelike, unity, алгоритм A*, процедурная генерация уровней, разработка игр, триангуляция Делоне
В последнее время я играл в несколько roguelike, поэтому решил попробовать написать собственный процедурный генератор подземелий. Существует множество способов решения этой задачи, и я выбрал алгоритм автора TinyKeep, описанный здесь. Я расширил этот алгоритм, чтобы он работал в 3D и мог создавать многоэтажные подземелья.
Код примера выложен в репозитории Github. Для демонстрации я использую Unity3D, но эти концепции, разумеется, применимы к любому другому движку.
Два измерения
Сначала мне нужно написать алгоритм для двух измерений. В целом он работает так же, как алгоритм TinyKeep, но имеет отличия для создания более интересных уровней.
Сцена для этого примера называется Dungeon2D. Код для него находится в папке Scripts2D.
Алгоритм
Мир разделён в виде прямоугольной сетки. Я предполагаю, что 1 единицы будет достаточно для обозначения коридора. В полной игре 1 единица измерения Unity может соответствовать например 5 метрам. Для сетки я выбрал размер 30×30.Читать полностью »
Как использовать диаграммы Вороного для управления ИИ
2019-07-22 в 11:17, admin, рубрики: алгоритм Форчуна, Алгоритмы, Диаграммы Вороного, Дизайн игр, искусственный интеллект, искусственный интеллект в играх, поиск пути в графе, разработка игр, триангуляция Делоне
Какой маршрут будет самым безопасным, где больше всего врагов и где ближайшая аптечка? Все эти часто встречающиеся задачи о пространственных связях можно эффективно решать при помощи математических разбиений под названием «диаграммы Вороного». Из этого поста вы узнаете, как анализировать игровые карты и получать информацию, обеспечивающую реализм и успех искусственного интеллекта.
Пространственные отношения
Пространственное отношение — это любая информация, описывающая, как связан один объект в пространстве с другим. Примеры: расстояние между ними, площадь покрываемого каждым из них пространства и пересечение этих площадей, количество таких объектов, расположенных в одной области.
Такие отношения постоянно используются в видеоиграх и могут предоставлять очень полезную информацию ИИ, а также самому игроку.
У Вороного есть ответ
Диаграмма Вороного описывает пространственное отношение между близко расположенными точками или их их ближайшими соседями. Это множество соединённых многоугольников, полученных из точек или локаций. Каждая линия «области» Вороного находится посередине между двумя точками.
Читать полностью »
Равномерное распределение точек в треугольнике
2019-02-23 в 7:37, admin, рубрики: квазислучайность, математика, Работа с векторной графикой, распределение точек, треугольники, триангуляция ДелонеБольшинство двухмерных квазислучайных методов рассчитано на сэмплирование в единичном квадрате. Однако в компьютерной графике также очень важны треугольники. Поэтому я описал простой метод прямого построения для равномерного покрытия последовательностью точек треугольника произвольной формы.
Рисунок 1. Новый прямой метод построения открытой (бесконечной) квазислучайной последовательности с низким расхождением в треугольнике произвольной формы и размера. На рисунке показаны распределения точек в пятнадцати случайных треугольниках для первых 150 точек.
Краткий обзор
Последовательности с низким расхождением (low discrepancy), равномерно сэмплирующие/заполняющие квадрат, активно изучались почти сотню лет. БОльшую часть этих квазислучайных последовательностей можно расширить до прямоугольников простым растягиванием, не сильно повредив при этом расхождению.
Однако в этом посте мы рассмотрим интересное и важное расширение последовательностей с низким расхождением на произвольный треугольник.
Читать полностью »
Как я создавал карты континентов для своей игры
2018-11-21 в 8:02, admin, рубрики: svg, диаграмма Вороного, Дизайн игр, процедурная генерация карт, разработка игр, симуляция климата, триангуляция Делоне
Часть 1. SVG и системы координат
До недавнего времени размеры карт в моей игре Dragons Abound были фиксированными и несколько недетерминированными. Я считал их «региональными» — не картами всего мира, но его значительными частями, такими например, как западное побережье США или часть Европы. Меня вполне устраивал этот масштаб, но я хотел немного поэкспериментировать с игрой, чтобы посмотреть, смогу ли я генерировать карты целого мира (или хотя бы большего размера). Но прежде чем я приступлю к этому, давайте немного поговорим о картах фэнтези-миров.
Мир — это большое пространство. Большинство карт фэнтезийных «миров» даже близко не походят на истинный размер. Возьмём, например, Средиземье, в котором происходит действие «Властелина колец»:
Хоть и кажется, что на ней запечатлён огромный мир, на самом деле Средиземье создано на основе Европы.
Читать полностью »
Снимаем «4D видео» с помощью depth-сенсора и триангуляции Делоне
2017-07-17 в 14:42, admin, рубрики: c++, Алгоритмы, никакой императивной скверны, никто не читает теги, Программирование, С++, с++11, сенсоры, трёхмерная графика, триангуляция, триангуляция Делоне
Привет! Это заметка о небольшом хобби-проекте, которым я занимался в свободное время. Я расскажу, как с помощью несложных алгоритмов превращать карты глубины от depth-сенсоров в забавный вид контента — динамические 3D сцены (их ещё называют 4D video, volumetric capture или free-viewpoint video). Моя любимая часть в этой работе — алгоритм триангуляции Делоне, который позволяет превращать разреженные облака точек в плотную полигональную сетку. Приглашаю всех, кому интересно почитать про алгоритмы, самописные велосипеды на C++11, и, конечно же, посмотреть на трёхмерных котиков.
Для затравки: вот что получается при использовании RealSense R200: skfb.ly/6snzt (подождите несколько секунд для загрузки текстур, а затем используйте мышку, чтобы поворачивать сцену). Под катом есть ещё!
Обладатели лимитированных тарифов, будьте осторожны. В статье много разных изображений и иллюстраций.
Читать полностью »
Генерирование полигональных карт для игр
2017-02-26 в 8:01, admin, рубрики: voronoi, Алгоритмы, диаграмма Вороного, процедурная генерация, разработка игр, триангуляция Делоне, шум перлина, метки: voronoi, диаграмма вороного, триангуляция делонеЯ хотел научиться генерировать интересные игровые карты, которые не обязательно были бы реалистичными, а также попробовать техники, с которыми раньше не работал. Обычно я создаю карты с другой структурой. Что можно сделать с тысячей полигонов вместо миллиона тайлов? Отчётливо различимые игроком области могут быть полезны для геймплея: местоположения городов, места квестов, территории для захвата или колонизации, ориентиры, точки поиска пути, зоны с разной сложностью и т.д. Я генерировал карты с помощью полигонов, а затем растеризировал их вот в такие карты:
Во многих процедурных генераторах карт, в том числе и некоторых моих предыдущих проектах, для генерирования карты высот используются функции шума (midpoint displacement, фракталы, diamond-square, шум Перлина и т.д.). Здесь я их не применял. Вместо неё я использовал структуру графов для моделирования элементов, определяемых ограничениями геймплея (высота, дороги, течение рек, места квестов, типы монстров) и функции шума для моделирования того, что не ограничивается геймплеем (форма побережья, расположение рек и деревьев).
Читать полностью »