Запросить ресурс о алгоритме быстрой трассировки лучей

Question

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

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

Я сделал следующее:

1. Используйте самый быстрый из известных мне луч-треугольник .

2. Используйте Octree. (Из Gem 1, 4.10. 4.11).

3. Использование Эффективный и надежный алгоритм пересечения Рэй-Бокса , который используется в алгоритме octree.

Это быстрее, чем раньше, когда я применил эти лучшие алгоритмы, но я считаю, что это может быть быстрее. Не могли бы вы пролить свет на любые возможные места, которые могли бы сделать это быстрее?

Спасибо.

Answer 1

Место, где можно задать эти вопросы: ompf2.com . Форум с темами о трассировке в реальном времени (хотя и не в реальном времени)

Answer 2

Форум OMPF - правильное место для этого вопроса, но так как я здесь сегодня ...

Не используйте пересечение лучей / блоков для обхода OctTree. Вы можете использовать его для корневого узла дерева, но это все. Как только вы знаете расстояние до входа и выхода корневого блока, вы можете вычислить расстояния до плоскостей разбиения x, y и z - плоскостей, которые делят блок. Если расстояние до передней и задней части равно f и b соответственно, то вы можете определить, какие дочерние узлы блока будут поражены, проанализировав расстояния f, b, x, y, z. Вы также можете определить порядок прохождения дочерних узлов и полностью отклонить многие из них.

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

Кроме того, поскольку он становится рекурсивным, вам понадобятся расстояния входа и выхода для дочерних узлов. Эти расстояния выбираются из набора (f, b, x, y, z), который вы уже вычислили.

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

Answer 3

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

Однако для действительно высокоскоростной трассировки лучей вам необходимо воспользоваться:

• Связные пакеты лучей
• Frusta
• SIMD

Я бы посоветовал вам начать с " Ray Tracing Animated Scenes с использованием Coherent Grid Traversal ". Это простой пример такого современного подхода. Вы также можете перейти по ссылкам, чтобы увидеть, как эти идеи применяются к деревьям K-d и BVH.

На этой же странице вы также можете ознакомиться с разделом «Состояние дел в анимированных сценах с трассировкой лучей».

Другим замечательным набором ресурсов являются все публикации SIGGRAPH за эти годы. Это очень конкурентная конференция, поэтому эти статьи, как правило, первоклассные.

Наконец, если вы хотите использовать существующий код, проверьте страницу проекта для OpenRT .

Answer 4

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

1. Представить систему портала
2. Переместите вычисления в графический процессор и воспользуйтесь преимуществами параллельных вычислений
3. В последнее время довольно популярной тенденцией в трассировке лучей является Иерархия ограничивающих объемов

Answer 5

Полезный ресурс, который я видел, - это журнал графических инструментов . В зависимости от ваших сцен, другой BVH может быть более подходящим, чем октри.

Кроме того, если вы еще не смотрели свое выступление с помощью профилировщика, вам следует. Shark отлично работает на OSX, и я получил хорошие результаты с Very Sleepy на Windows.