Продолжу монолог.
Light Radiance - текущий алгоритм
Снял видел объясняющее как работает Light Spread алгоритм в MineCraft. Честно сказать, я до этого не совсем правильно представлял как он работает))
Все LightPoint'ы добавляются в очередь и равномерно рассеиваются. Когда одна LightPoint встречается с другой, то рассеивание прекращается. По этой причине для максимальной производительности необходимо добавить в очередь все LightPoint'ы сцены (А это сотни тысяч). И многопоточность нельзя использовать т.к. используется только одна очередь.
Light Gathering
Можно вычислять свет лишь для блоков, граничащих с твердыми блоками или содержащими в себе траву или что-то подобное. На рисунке эти блоки выделены красным.
Вот видео показывающие работу такого алгоритма.
Плюсы такого метода:
- Можно вообще не выделять память на хранение освещение. Разве какие-то ускоряющие структуры создать.
- Легко распараллеливается.
Но есть и серьезные недостатки:
Метод Light Spread в посещенные ячейки записывает освещение, поэтому алгоритм второй раз в одну и тужу ячейку не зайдет. И вообще не зайдет в ячейку, в которой уже есть свет, который больше текущего.
Можно создавать массив в который записывать посещенные вершины. Думаю, можно 1 bit на вершину. Но этот массив придется каждый раз чистить.
Пока не представляю сколько времени займет такой алгоритм, но памяти он экономил бы много.
Задача в общем-то сводится к графу, каждая вершина которого содержит\не содержит свет и имеет уровень прозрачности (воздух, вода, непрозрачный).
Вот и надо обойти все соседние вершины и собрать с них свет.
Может у кого-то есть идеи как это можно ускорить или не хранить посещенные вершины?
Правильный Global Illumination
Ray Tracing
Мне парой кажется, что нормальный Global Illumination будет не медленнее, чем тот Light Gathering.
Можно Indirect Lighting вычислять не для всей сцены, а для куска карты, вокруг игрока.
На карте 256x256x256 есть ~230тыс блоков, для которых надо вычислить свет.
Для сбора света из hemi-cube размером 64 нужно 12288 луча, это не так и много.
int faceArea = 64 * 64;
int halfFaceArea = faceArea / 2;
int hemiCubeArea = (halfFaceArea * 4) + faceArea; // = 12288
Для hemi-sphere возможно еще меньше. Конечно длинна луча 64 это не очень много. Будут проблемы в длинный коридорах, когда луч от одной стены не достает до другой и думает, что он ушел в небо.
И того.
12.288 лучей * 230.000 ячеек = 2.826.240.000. Почти 3 миллиарда лучей - очень огромное число. И это только для одного bounce.
Если бы можно было вычисление света разделить на несколько кадров. Сначала 1й bounce, потом 2й bounce. Еще можно сделать, чтобы за кадр пускался только каждый десятый луч, типа сначала четные, потом нечетные.
Было бы терпимо, если бы свет полностью перевычислялся за 0.5 - 1 секунду.
Но вряд ли даже за минуту можно пустить такое кол-во лучей.
LVP
Можно при изменении геометрии пересчитывать сферические гармоники.
Тогда освещение нужно будет собирать с ячеек, которые попали внутрь объема сферической гармоники.
Если я вообще правильно понимаю смысл сферических гармоник.
Но я понятия не имею сколько времени нужно на перерасчет сферических гармоник.
Список видимых ячеек
Просто для каждой ячейки хранить список видимых ячеек. Для многих ячеек такой список будет одинаковым или почти одинаковым, поэтому можно будет хорошо сжать. Собрать освещение из готового списка ячеек - самое простое.
Но этот список надо еще вычислить и сжать. Как вычислить, сколько времени это займет - тоже вопрос.