Уменьшите вычисления во время Raytracing

Question

Я написал свой собственный 3D Game Engine (это заняло у меня год), и я хотел создать Raytracer, который будет работать на моем процессоре (не на GPU!!)

На данный момент процесс трассировки лучей упрощен следующим образом:

1. Приведите луч для каждого выходного пикселя.
2. Если текущий луч попадает на объект, установите цвет выходного пикселя на "белый"
3. В противном случае установите его на черный

Чтобы увеличить скорость трассировщика лучей, я добавил сферическую ограничивающую рамку для каждой сущности. Если текущий луч пересекает ограничивающую рамку, он будет запускать тесты пересечения с каждым треугольником сущности.

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

В результате у меня уходит более 5 минут на рендеринг объекта (1920x1080) с примерно 10000 полигонов, и я думаю, что это не то, что я хочу.

Есть ли способ уменьшить количество треугольников, которые мне нужно проверить?

Привет, Финн

Answer 1

Есть ли способ уменьшить количество треугольников, которые мне нужно проверить?

Да.

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

Вы можете уменьшить это до среднего O(log(n)) время, используя объемные kd-деревья или ограничивающие иерархии томов для хранения ваших треугольников. Лично я предпочитаю kd-деревья, но любой подход работает. Обратите внимание, что BVH обычно лучше работает в анимационных сценах.

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

AbstractScene - базовый класс для всех типов сцен. Большая часть кода взаимодействует только с AbstractScene поля и методы.

KDScene - производный класс, который реализует сцену в виде дерева kd.

BVHScene - производный класс, который реализует сцену как BVH.

NaiveScene - производный класс, который реализует сцену в виде списка треугольников.

Существуют также другие ускоряющие структуры, такие как сетки (также известные как воксели).