Уменьшение временной сложности O(n²) алгоритма Ray Casting

Я написал алгоритм приведения лучей на основе стандартных алгоритмов. Точка пересечения вычисляется с помощью алгоритма Меллера-Трумбора (который сократил время выполнения примерно на 350 % по сравнению с более простым алгоритмом).

В целом выполняются следующие шаги:

1. Для каждого треугольника выстрелите лучом от источника света к треугольнику.
2. Проверьте, есть ли другие треугольники, которые пересекаются с лучом. Получите тот, у которого минимальное расстояние до источника луча (т.е. источника света).
3. Осветите тот, который находится на минимальном расстоянии (установите затененный = false для треугольника)

Мне не нужны разные вариации штриховки; треугольники должны содержать информацию только в том случае, если они вообще затенены или нет (логическое значение).

Проблема в том, что для шага 2 мне нужно выполнить проверку пересечения для всех треугольников в сцене. Другими словами, временная сложность равна O(n²). Однако я читал, что можно использовать алгоритм луча с временной сложностью O (log n).

У меня есть несколько идей по сокращению времени выполнения. Например, я мог бы исключить из расчета все треугольники с большим расстоянием до источника света, чем тот, на который направлен луч, что могло бы сократить время выполнения на 50 %. Но сложность по-прежнему будет O(n²), и это не сильно поможет при обработке больших объемов данных.

Например, использование алгоритма трассировки лучей на сцене с числом 100 000 по-прежнему возможно, но занимает около 10 минут, и это количество будет экспоненциально увеличиваться, когда сцена состоит из большего количества треугольников.

Есть ли способ уменьшить временную сложность до более низкого класса сложности без фундаментального изменения способа работы алгоритма?

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

Я экспериментировал с разным количеством разделов и подразделов, и результаты сильно различались, но в большинстве случаев приведение лучей работает значительно лучше. Универсальной оптимальной конфигурации не существует, поэтому есть смысл попробовать разные числа для разных объектов/сцен. В моем случае 4/2 (деление комнаты на 4*4*4 граничных блока, содержащих 2*2*2 подблока в каждом, т.е. 64 блока с 8 внутренними блоками в каждом), 5/2 и 6/2 обычно работают хорошо, хотя для некоторых объектов лучше всего работает неиерархическое разбиение (например, 10/0).

Количество требуемых тестов пересечения луча и треугольника может быть уменьшено до 97% (может быть, больше), но более высокие уровни разделения делают создание граничных боксов / AABB довольно дорогостоящим. При хорошей конфигурации программа работает до 4 раз быстрее, чем решение без граничных томов. Лучшая производительность лучше видна на сценах с большим количеством треугольников (более 10000).

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