Как я могу быстро создать подписанные поля расстояния (2D) в режиме реального времени?

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

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

Существуют некоторые статьи для различных методов, которые должны быть жизнеспособными в средах реального времени, таких как методы для преобразований расстояния Чамфера и преобразования на основе диаграмм-приближений Вороного (как это предлагается в этой презентации разработчиком Pixeljunk Shooter ), но Мне (и, таким образом, можно предположить, что многие другие люди) действительно очень трудно использовать их, так как они обычно длинные, в основном раздутые с математикой и не очень алгоритмичные в своих объяснениях.

Какой алгоритм вы бы предложили для создания полей расстояний в реальном времени (выгодно для графического процессора), особенно с учетом качества получаемых полей расстояний?

Так как я ищу фактическое объяснение / учебное пособие, а не ссылку на просто еще одну статью или слайд, этот вопрос получит вознаграждение, как только он будет иметь право на один :-).

Вот почему мне нужно сделать это в режиме реального времени:

Если вам необходимо предварительно вычислить эти SDF для больших 2D-сред (например, для большой карты типа Terraria), это будет означать, что вы принимаете довольно большие накладные расходы на пространство хранения (и время генерации карты) в пользу реализации более сложный алгоритм, который достаточно быстр для генерации SDF в реальном времени.

Например, сравнительно небольшая карта с 1000 * 256 (ширина * высота) с размером плитки 10 * 10 пикселей и, следовательно, с общими размерами 10000 * 2560 пикселей, уже обойдется вам примерно в 2 мегабайта, если вы выберете относительно маленький Разрешение SDF 128x128, при условии, что вы храните только значения расстояния от 0 до 255.

Очевидно, что это может быстро стать слишком много, и это накладные расходы, которые я не хочу иметь.

Есть что-то еще:

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

Каталин Зима объясняет, как добиться динамических 2D теней в своей статье - и он использует поле расстояния со знаком (из того, что я могу сказать, это просто причудливое имя для буфера теней в этом контексте). Его метод действительно нуждается в графическом процессоре, и его реализация как есть не самая лучшая (его частота ниже 60 Гц при 20 лампах на моей машине, у моей - около 500 ламп); что и следовало ожидать, поскольку он предпочитал ясность кода по скорости.

Реализация

Именно так, как он реализовал:

1. Визуализируйте все заклинатели теней в текстуру.
2. Рассчитайте расстояние до центра источника света для каждого пикселя и присвойте это значение RGB непрозрачных пикселей.
3. Искажите изображение так, чтобы оно представляло, как трехмерная камера видела эти пиксели.
4. Раздавите изображение до размера 2xN, используя необычный размер, описанный в его статье (обычный размер не сработает).
5. Изображение 2xN теперь является вашим полем расстояния со знаком для всех четырех квадрантов света (помните, что один квадрант - это, в основном, единая камера с углом обзора 90 градусов).
6. Визуализируйте карту освещения.
7. Размыть карту освещения (в зависимости от расстояния от источника света), чтобы получить мягкие тени.

Моя последняя реализация была (каждый шаг был одним шейдером):

1. Do (1).
2. Do (2) и (3) .
3. Do (4). Его реализация очень медленная: если вы можете попробовать использовать GPGPU для этого. Я не мог использовать GPGPU (XNA), поэтому я сделал следующее:
   • Настройте сетку, в которой первые N / 2 столбцы представляли собой N / 2 квадратов с ТОЧНОЙ позицией ТОЧНО (охватывающей первый столбец конечного буфера), но с разными координатами текстуры (то же самое для вторых N / 2 столбцов)
   • Отключите тестирование глубины на GPU.
   • Используйте функцию смешивания пикселей MIN.
4. Do (6) и (7).

Это довольно изобретательно: это в основном прямой перевод того, как тени обрабатываются в 3D в 2D.

Ловушки

Основная проблема заключается в том, что некоторые объекты не должны быть затенены: в моем примере я писал клон Liero (черви в реальном времени) и поэтому не хотел, например, чтобы черви игроков были затенены (по крайней мере один на экране каждого игрока). Все, что я сделал для этих «специальных» объектов, это перерисовал их в качестве последнего шага. Ирония заключалась в том, что большинство объектов не были затенены (черви, пейзаж на переднем плане), поэтому здесь возникает проблема с перерисовкой.