• Алгоритм Дугласа-Пекера

    Предисловие


    Не так давно пришлось поработать с упрощением полигональной цепи (процесс, позволяющий уменьшить число точек полилинии). В целом, данный тип задач очень распространен при обработке векторной графики и при построении карт. В качестве примера можно взять цепь, несколько точек которой попадают в один и тот же пиксель – очевидно, что все эти точки можно упростить в одну. Некоторое время назад я практически ничего не знал об этом от слова «совсем», в связи с чем, пришлось в быстром темпе восполнять необходимый багаж знаний по этой теме. Но каково было мое удивление, когда в интернете я не нашел достаточно полных руководств по этому вопросу… Мне приходилось отрывками искать информацию с совершенно разных источников и, после проведенного анализа, выстраивать все в общую картину. Занятие не из самых приятных, если честно. Поэтому мне хотелось бы написать цикл статей, посвященных алгоритмам упрощения полигональной цепи. Как раз-таки начать я решил с наиболее популярного алгоритма Дугласа-Пекера.


    Читать дальше →
  • Пишем на Rust + CUDA C

    • Tutorial

    Всем привет!

    В данном руководстве хочу рассказать как подружить CUDA C/С++ и Rust. И в качестве примера напишем небольшую программу на Rust для вычисления скалярного произведения векторов, вычисление скалярного произведения будет производиться на GPU с использованием CUDA C.

    Кому интересно под кат!
    Читать дальше →
  • Простое объяснение алгоритмов поиска пути и A*

    • Перевод
    image

    Часть 1. Общий алгоритм поиска


    Введение


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

    Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.

    Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.
    Читать дальше →
  • «Галоп пикселя — часть пятая» — Анимация персонажей. Ходьба

    • Tutorial


    «Галоп пикселя», часть I — базовые понятия, этапы взросления, прикладные упражнения (линк)
    «Галоп пикселя», часть II — перспектива, цвет, анатомия и прикладные упражнения (линк)
    «Галоп пикселя», часть III — Анимация (линк)
    «Галоп пикселя», часть IV — Анимация света и тени (линк)
    «Галоп пикселя», часть V — Анимация персонажей. Ходьба (линк)

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

    Сегодняшняя публикация станет очередной, и возможно даже поворотной вехой в нашем повествовании. Наконец-то мы подошли к созданию полноценной анимации персонажей. Двумя предыдущими главами мы охватили анимацию света и тени, а также анимацию неподвижных персонажей (idle-animation) без ярко выраженных действий. Но сегодня наши персонажи пойдут, а в следующей части даже побегут, завоевав то, что уже давно их по праву рождения. Ещё один плодородный регион. И пройдут ещё одну точку, которая ознаменует окончание базового цикла. Наши пиксели наконец-то станут живыми.

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


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

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

    В этой статье я подробно опишу алгоритм, который у меня получился в результате использования идеи «заметающей прямой» для построения триангуляции Делоне на плоскости. В нем есть несколько идей, которые я нигде не встречал, когда читал статьи про триангуляцию.
    Возможно, кто-то тоже найдет их необычными. Я постараюсь сделать все в лучших традициях и включить в рассказ следующие вещи: описание используемых структур данных, описание шагов алгоритма, доказательство корректности, временные оценки, а также сравнение с итеративным алгоритмом, использующим kD-дерево.
    Читать дальше →
  • hellOGL: OpenGL hello world

    • Tutorial
    Сегодня я покажу, как открыть окно и создать контекст OpenGL. Это на удивление непростая задача, OpenGL до сих пор не имеет официальных кроссплатформенных средств создания контекста, поэтому будем опираться на сторонние библиотеки (в данном случае GLFW и glad). В интернете уже очень много подобных hello world, но всё, что я видел, мне не нравится: или оно очень навороченное, или картинки в примерах уж очень примитивные (либо и то, и другое!). Большое спасибо всем авторам, но я выкачу очередной туториал :)

    Сегодня мы отрисуем вот такое:


    Читать дальше →
  • Виртуальная машина своими руками

    • Tutorial
    Иногда в голову приходит какая-то мысль избавиться от которой очень сложно. Такое произошло и со мной.

    Я решил создать виртуальную машину (VM), учитывая то, что на тот момент у меня не было идей, мне показалось, что это прекрасная мысль. Если вы заинтересовались, то вперёд под кат!
    Читать дальше →
  • Нечёткий мир шума Перлина

    • Перевод
    image

    Что такое шум Перлина?


    Шум Перлина придуман в 1983 году Кеном Перлином (получившим за это достижение премию Американской Академии кинематографических искусств и наук). Видите ли, в те времена все стремились к фотореализму, но его всегда не хватало. Кен Перлин придуман этот алгоритм шума, чтобы избавиться от жалкого «компьютерного» внешнего вида 3D-моделей. Шум — это генератор случайных чисел в компьютерной графике. Это случайный неструктурированный паттерн, он полезен в тех случаях, когда требуется источник подробных деталей, недостающих в очевидной структуре1. Шум Перлина — это многомерный алгоритм, используемый в процедурной генерации, текстурах, генерации рельефа, генерации карт, генерации поверхностей, генерации вершин, и так далее, и тому подобное.
    Читать дальше →
    • +25
    • 8,2k
    • 5
  • Равномерное распределение точек в треугольнике

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


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

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


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

    Однако в этом посте мы рассмотрим интересное и важное расширение последовательностей с низким расхождением на произвольный треугольник.
    Читать дальше →
  • Неожиданная эффективность квазислучайных последовательностей

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


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

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

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

    Какое-то время назад этот пост был выложен на главной странице Hacker News. Можете прочитать там его обсуждение.
    Читать дальше →
    • +90
    • 14,7k
    • 7
  • Шум Перлина, процедурная генерация контента и интересное пространство

    • Перевод
    Наверно худшее, что случилось в области процедурной генерации контента (если считать, что это действительно область процедурной генерации контента, в чём я уверен не полностью) — это шум Перлина. Шум Перлина невероятно хорошо подходит (по крайней мере, если не приглядываться слишком внимательно) для генерации интересных ландшафтов. В сабреддите /r/proceduralgeneration недели не проходит без того, чтобы кто-нибудь не опубликовал «систему процедурной генерации», которая оказывается визуализированным разными цветами шумом Перлина. (За время написания этой статьи появилось два таких поста!)


    Я не хочу унизить шум Перлина. Это невероятно полезный для процедурной генерации инструмент, ставший точкой входа в эту область для множества людей, в том числе и меня. Но в то же время он очень сбивает с толку, потому что подразумевает, что процедурная генерация намного проще, чем это есть на самом деле. Большинство еженедельных постов о «системах процедурной генерации» в /r/proceduralgeneration исчезают без следа, когда их авторы обнаруживают, что следующий шаг в процедурной генерации гораздо сложнее. Истина в том, что шум Перлина стал своего рода счастливой случайностью. Он отлично подходит для генерации интересных ландшафтов, но на то нет систематических или повторяемых причин.
    Читать дальше →
    • +30
    • 5,3k
    • 6
  • Reflective Shadow Maps: Часть 1

    • Перевод
    image

    Привет, Хабр! Представляю вашему вниманию перевод статьи «Reflective Shadow Maps» автора Eric Polman.

    Reflective Shadow Maps (RSM) (отражающие карты теней) ― это алгоритм, расширяющий “простые” shadow map. Алгоритм учитывает свет, рассеянный после первого попадания на поверхность (diffuse). Это означает, что кроме прямого освещения, вы получаете непрямое освещение. В данной статье я разберу алгоритм из официальной статьи, чтобы объяснить его по-человечески. Я также кратко расскажу о shadow mapping.
    Читать дальше →
    • +23
    • 2,5k
    • 9
  • Введение в программирование: простой 3D-шутер с нуля за выходные, часть 1

    • Tutorial
    Этот текст предназначен для тех, кто только осваивает программирование. Основная идея в том, чтобы показать этап за этапом, как можно самостоятельно сделать игру à la Wolfenstein 3D. Внимание, я совершенно не собираюсь соревноваться с Кармаком, он гений и его код прекрасен. Я же целюсь совсем в другое место: я использую огромную вычислительную мощность современных компьютеров для того, чтобы студенты могли создавать забавные проекты за несколько дней, не погрязая в дебрях оптимизации. Я специально пишу медленный код, так как он существенно короче и просто понятнее. Кармак пишет 0x5f3759df, я же пишу 1/sqrt(x). Мы преследуем разные цели.

    Я убеждён, что хороший программист получается только из того, кто кодит дома в своё удовольствие, а не только просиживает штаны на парах в университете. В нашем университете программистов учат на бесконечной череде всяких библиотечных каталогов и прочей скукоте. Брр. Моя цель — показать примеры проектов, которые интересно программировать. Это замкнутый круг: если интересно делать проект, то человек проводит над ним немало времени, набирается опыта, и видит вокруг ещё больше интересного (оно же стало доступнее!), и снова погружается в новый проект. Это называется проектное обучение, вокруг сплошной профит.

    Простыня получилась длинная, поэтому я разбил текст на две части:


    Выполнение кода из моего репозитория выглядит вот так:


    Это не законченная игра, но только заготовка для студентов. Пример законченной игры, написанной двумя первокурсниками, смотрите во второй части.
    Читать дальше →
  • Введение в программирование: простой 3D-шутер с нуля за выходные, часть 2

    • Tutorial
    Продолжаем разговор про 3Д шутер за выходные. Если что, то напоминаю, что это вторая половина:


    Как я и говорил, я всеми силами поддерживаю желание в студентах делать что-то своими руками. В частности, когда я читаю курс лекций по введению в программирование, то в качестве практических занятий я оставляю им практически полную свободу. Ограничений только два: язык программирования (С++) и тема проекта, это должна быть видеоигра. Вот пример одной из сотен игр, которые сделали мои студенты-первокурсники:


    К сожалению, большинство студентов выбирает простые игры типа 2Д платформеров. Я пишу эту статью для того, чтобы показать, что создание иллюзии трёхмерного мира ничуть не сложнее клонирования марио броз.
    Читать дальше →
  • Читаем QR код

    • Tutorial
    Иногда возникают такие ситуации, когда нужно прочитать QR код, а смартфона под рукой нет. Что же делать? В голову приходит лишь попробовать прочитать вручную. Если кто-нибудь сталкивался с такими ситуациями или кому просто интересно как же читается QR код машинами, то данная статья поможет вам разобраться в этой проблеме.

    В статье рассмотрены базовые особенности QR кодов и методика дешифрирования информации без использования вычислительных машин.

    Иллюстраций: 14, символов: 8 510.
    Читать дальше →
  • Псевдо Lens Flare

      Привет, Хабр! Представляю вашему вниманию перевод статьи «Pseudo Lens Flare» автора John Chapman.

      image

      Lens flare (блики на линзах) ― это фотографический артефакт, возникающий при рассеивании и преломлении света в системе линз. Хотя он является артефактом, существует множество поводов использовать lens flare в компьютерной графике:

      • он увеличивает воспринимаемую яркость и видимый динамический диапазон изображения.
      • lens flare часто встречается на фотографиях, поэтому его отсутствие может бросаться в глаза
      • он может играть важную роль в стилистике или драматизме, или может быть частью геймплея в играх (представьте блики, ослепляющие игрока)

      Традиционно lens flare в realtime реализовывался с помощью технологий, основанных на спрайтах. Хотя спрайты дают легко контролируемые и очень реалистичные результаты, они должны быть размещены явно и требуют данные окклюзии для корректного отображения. Здесь я опишу простой и относительно дешевый screen space эффект, который создает псевдо lens flare из входного color buffer. Он не основан на физике, поэтому результат немного отличается от фотореалистичного, но его можно использовать в комбинации с (или как замену) традиционными sprite-based эффектами.
      Читать дальше →
    • Композиция против наследования, паттерн Команда и разработка игр в целом


        Дисклеймер: По-моему, статья об архитектуре ПО не должна и не может быть идеальной. Любое описанное решение может покрывать необходимый одному программисту уровень недостаточно, а другому программисту — слишком усложнит архитектуру без надобности. Но она должна давать решение тем задачам, которые поставила перед собой. И этот опыт, вместе со всем остальным багажом знаний программиста, который обучается, систематизирует информацию, оттачивает новыки, и критикует сам себя и окружающих — этот опыт превращается в отличные програмные продукты. Статья будет переключаться между художественой и технической частью. Это небольшой эксперимент и я надеюсь, что он будет интересным.
        — Слушай, я тут придумал отличную идею игры! — гейм-дизайнер Вася был взъерошен, а глаза — красные. Я ещё попивал кофе и холиварил на Хабре, чтобы убить время перед стенд-апом. Он выжидательно посмотрел на меня, пока я закончу писать в комментариях человеку, в чем он не прав. Вася знал, что пока справедливость не восторжествует, а правда не будет защищена — смысла продолжать со мной разговор нету. Я дописал последнее предложение и перевел на него взгляд.

        — В двух словах — маги с маной могут кастовать заклинания, а воины могут сражаться в близком бою и тратить выносливость. И маги и воины могут двигаться. Да, там ещё можно будет грабить корованы, но это уже следующей версии сделаем, короче. Покажешь прототип после стенд-апа, окей?

        Он убежал по своим гейм-дизайнерским делам, а я — открыл IDE.
        Читать дальше →
      • 3blue1brown и MIT на русском

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

          Ровно год назад мы — небольшое сообщество — собрались, чтобы переводить на русский самые крутые образовательные курсы, что есть в открытом доступе (например, физика Уолтера Левина). Без денег — просто интерес. И сегодня мы к вам — с надеждой, что вам понравится, что мы делаем.

          Вместо КДПВ — озвученное нами видео 3blue1brown (да-да, мы договорились о переводе с автором самых крутых на Youtube видео про математику-физику-информатику).

          Читать дальше →
        • JSON API – работаем по спецификации

            В последнее время веб-разработка разделилась. Теперь мы все не full-stack программисты — мы фронтендеры и бэкендеры. А самое сложное в этом, как и везде, это проблема взаимодействия и интеграции.

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

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


            Читать дальше →