План того, что тут будет появляться:
- Классический воксель-маршинг
- Гибридный, с СДФ внутри вокселей
- Ускорение с помощью мипмэпа
- Ускорение с помощью джамп-флуда
Предполагаю, что вы уже знакомы с алгоритмом реймаршинга, если нет, посмотрите видео
Классический воксель-маршинг
В отличие от реймаршинга, в котором длина шага зависит от расстояния до ближайшего объекта, тут пространство делится на кубические ячейки, как тетрадь в клетку. И каждый шаг вдоль луча происходит от вокселя к вокселю. Шагнув в воксель мы проверяем, полный он или пустой. И если полный — останавливаемся, мы уткнулись в объект, можно дальше не маршировать.
Чтобы разобраться, как работает трёхмерный воксель-маршинг, лучше начать с двумерного. А круче всего — вообще с одномерного.
Вот оно, наше двумерное пространство. Мы пустим луч из точки 0, пусть камера будет там. Луч полетит вправо, будет лететь, пока не найдёт заполненный воксель отрезок.
Недописанный скетч для 2д случая
Ускорение с помощью SDF-текстуры
Более простой и, кажется, более надёжный способ — заранее сделать карту вокселей. Каждый пустой воксель в ней будет знать расстояние до ближайшего не пустого.
Посчитать можно с помощью джамп-флудинга.
Если раньше мы двигались по лучу не дальше, чем на один воксель, теперь можем проверять SDF текстуру и, если до ближайшего вокселя далеко, шагать смелее.
Например, у этой картинки
вот такой СДФ:
На самом деле я использую 2д текстуру для его хранения. Чтобы это получилось, я разрезаю объёмную карту на горизонтальные слои в один воксель и кладу их слева направо. Получается текстура высотой voxSize и шириной voxSize²
Это не <hr>, это узкая картинка
Как видите, вы почти ничего не видите. Слишком мелко. Если призумить кусочек, будет так:
