Комментарии 27
Недостаток, который пришёл в голову на первый взгляд: надо ввести ограничение на минимальный угол между лучами. Иначе, в случае наличия окружности (помимо прямых рёбер), производительность может получиться ниже, чем в случае изначального метода.
За счёт того, что окружность обычно рисуется большим количеством маленьких отрезков (треугольники, в случае 3D), которые будут иметь очень много "углов".
Лучше просто уменьшить количество "сторон" в окружностях. Хотя бы для расчетов.
Для окружности достаточно взять всего 2 точки, определяемые касательными к окружности из точки обзора. Их придётся менять при сдвиге точки, но для этих расчётов не критично. Это в целом привычная практика по-разному обрабатывать окружности и полигоны, и хотя в рендеринге окружность тоже полигон, в модели она может оставаться идеальной окружностью.
Я в подобной задаче отказался от чисто математического подхода. Взял геометрию 2D-сцены и спроецировал в одномерный Z-буфер, показывающий расстояние от центра персонажа до ближайшего препятствия. Минус, конечно же, теряется точность как на рисунке 3, но для модели освещения мне этого вполне хватило, имхо, мы не ядерные реакции считаем, да и я не такой любитель математики, как Вы :)
Не могли бы Вы пояснить момент про проецирование 2Д-сцены в 1-мерный Z-буфер?.. Как именно трансформировалось R^2 -> R^1?
Представьте как 3D-сцена попадает в 2-мерный Z-буфер, и положите одну из координат строго равной нолю.
При желании можно написать вершинный шейдер, который будет переводить (х, у) в полярные координаты, (r, phi) и использовать r как глубину. (Хотя у меня есть подозрение, что люди не заморачиваются и просто рисуют в 4 камеры с углом обзора 90 градусов каждая)
Я здесь описывал https://habrahabr.ru/post/204782/, вкратце, переводим грани объектов в полярные координаты и интерполируем в буфер.
Можно еще проще. Рендерить в текстуру стенки, и шейдером выводить источники света. Но тут проблема с толщиной стенок, если она слишком тонкая и радиус света большой, можно просветить. Как-то делал такой вариант https://www.youtube.com/watch?v=Z3hEsH6iqys, отвечал KoMaTo3
Эффективный расчёт области видимости...
Для десятков или сотен NPC отрисовывать в бекбуффер очень накладно получится. Тем более, что такой рендеринг это просто "базовый алгоритм" из статьи, где каждый фрагмент (пиксель) получает свой луч.
Я не писал ничего про область видимости, а дополнил комментарий выше (от KoMaTo3), просто комментарий удалить или перенесли нельзя после добавления. Успел только в конце дописать кому это адресовано. Потом понял, что дописал фигню и уже не смог редактировать. Так и знал, что минусовать начнут.
А можно ничего не считать и не генерить — ведь это всего-лишь визуализация, реальные рассчеты видимости делаются иначе. Для отрисовки достаточно просто вытягивать геометрию препятствий в шейдере + маскировать через stencil-буфер — все будет работать как надо и максимально быстро.
Внезапно узнал, что twitch удаляет записи через 14 дней. Печально, можно было посмотреть процесс создания такого эффекта. Записал демку того, что получилось:
Зеленое — поле видимости, желтое — частичное скрытие (т.е. можно достаточно просто рендерить разные виды препятствий).
Геометрия препятствия — по сути 4 полигона с нулевой площадью вокруг квадратной «дыры» в центре. В шейдер передается положение «глаза» и геометрия препятствий просто тянется по направлению от «глаза» на какое-то большое расстояние, заведомо больше, чем дальность видимости. Препятствия рисуются с отключенным Color buffer с заполнением Stencil buffer разными числами. Последним рендерится геометрия поля видимости с автомаскировкой по Stencil buffer. Со стороны кода нужно только обновлять положение «глаза», все остальное делает GPU.
Зеленое — поле видимости, желтое — частичное скрытие (т.е. можно достаточно просто рендерить разные виды препятствий).
Геометрия препятствия — по сути 4 полигона с нулевой площадью вокруг квадратной «дыры» в центре. В шейдер передается положение «глаза» и геометрия препятствий просто тянется по направлению от «глаза» на какое-то большое расстояние, заведомо больше, чем дальность видимости. Препятствия рисуются с отключенным Color buffer с заполнением Stencil buffer разными числами. Последним рендерится геометрия поля видимости с автомаскировкой по Stencil buffer. Со стороны кода нужно только обновлять положение «глаза», все остальное делает GPU.
Ого. Я с помощью глубины делал — но у меня "источник" был только один. Рисовал объекты уровня на глубине 0, а у четырёхугольников-теней две вершины имели z=-1, и такой четырёхугольник "перекрывал" все другие объекты. маленькое видео
Раньше я тоже делал с помощью буфера глубины (с отключенным Color buffer):
В видео подменяю материал, чтобы было видно как вытягивается геометрия — это делалось на CPU. Вытянутая геометрия рисуется первой и немного выше по Z, чем геометрия поля зрения.
В том видео, что выше — все делается уже на GPU. Каждое препятствие выглядит примерно вот так:
В центре дыра, по периметру 4 полигона, внешние вертексы расскрашены в белый цвет, внутренние в черный — это используется как маркер для того, чтобы различить в шейдере, что нужно тянуть. На картинке полигоны видимы, на самом деле их перед экспортом в движок нужно ставить максимально близко (но без слияния) к внутреннему краю. Размер внутреннего пустого «квадрата» — 1х1, чтобы в движке можно было проще подгонять под любой размер препятствия. Ну и в шейдере просто считается разница между «глазом» и каждым вертексом, нормализуется и смещается на большую дистанцию. Интенсивность смещения берется из цвета вертекса. Получается достаточно неплохо и, самое главное, быстро.
В видео подменяю материал, чтобы было видно как вытягивается геометрия — это делалось на CPU. Вытянутая геометрия рисуется первой и немного выше по Z, чем геометрия поля зрения.
В том видео, что выше — все делается уже на GPU. Каждое препятствие выглядит примерно вот так:
В центре дыра, по периметру 4 полигона, внешние вертексы расскрашены в белый цвет, внутренние в черный — это используется как маркер для того, чтобы различить в шейдере, что нужно тянуть. На картинке полигоны видимы, на самом деле их перед экспортом в движок нужно ставить максимально близко (но без слияния) к внутреннему краю. Размер внутреннего пустого «квадрата» — 1х1, чтобы в движке можно было проще подгонять под любой размер препятствия. Ну и в шейдере просто считается разница между «глазом» и каждым вертексом, нормализуется и смещается на большую дистанцию. Интенсивность смещения берется из цвета вертекса. Получается достаточно неплохо и, самое главное, быстро.
Грубая оптимизация, которую я когда-то делал, имела под собой основу не сектор, а 3 треугольника. Это допускалось постановкой задачи и позволяло сильно упростить систему до взаимодействия треугольников и точек/линий — просчитывать каждый раз окружность не всегда удобно, да и медленней.
Мне в голову сразу приходит реализация определения области видимости с использованием метод заметающей прямой:
1) Отсортировать все вершины граней препятствий по часовой стрелке
2) Двигать заметающую прямую по кругу вокруг NPC — отслеживать ближайшую грань препятствий
3) на каждом участке до следующей вершины определять зону видимости в этой части сектора (по расположению ближайшей грани относительно сектора видимости: либо полный кусочек сектора, либо обрезанный гранью)
В результате должна получиться область видимости.
Оценка эффективности — O(N*log(N)), где N — количество вершин препятствий около NPC (можно предварительную выборку сделать ограничивающим прямоугольником).
Мне пока не доводилось решать задачу определения области видимости, могу что-то упускать.
Вы не рассматривали такой алгоритм, и если да — то чем не подходит?
1) Отсортировать все вершины граней препятствий по часовой стрелке
2) Двигать заметающую прямую по кругу вокруг NPC — отслеживать ближайшую грань препятствий
3) на каждом участке до следующей вершины определять зону видимости в этой части сектора (по расположению ближайшей грани относительно сектора видимости: либо полный кусочек сектора, либо обрезанный гранью)
В результате должна получиться область видимости.
Оценка эффективности — O(N*log(N)), где N — количество вершин препятствий около NPC (можно предварительную выборку сделать ограничивающим прямоугольником).
Мне пока не доводилось решать задачу определения области видимости, могу что-то упускать.
Вы не рассматривали такой алгоритм, и если да — то чем не подходит?
Есть странный эффект, если в демо по ссылке https://legends2k.github.io/2d-fov/ поместить персонажа в вершину какого — либо угла не выпуклого многоугольника, то области видимости смещается внутрь препятствия.
Подскажите пожалуйста начинающиму программисту:
Это реализованно на двухмерном массиве?
Если это массив то как мы пускаем луч? по формуле? или метод есть какой?
И как именно проверяется пересечение лучей?
Буду очень благодарен ибо инфу очень сложно добыть.
Спасибо!
Это реализованно на двухмерном массиве?
Если это массив то как мы пускаем луч? по формуле? или метод есть какой?
И как именно проверяется пересечение лучей?
Буду очень благодарен ибо инфу очень сложно добыть.
Спасибо!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Эффективный расчёт области видимости и линии взгляда в играх