Улучшение производительности raytracer

Я пишу сравнительно простой трассировщик raytracer/path в D (http://dsource.org/projects/stacy), но даже при полной оптимизации все еще нужно несколько тысяч процессорных циклов на луч. Есть ли что-нибудь еще, что я могу сделать, чтобы ускорить его? В общем, знаете ли вы о хороших оптимизациях/более быстрых подходах к трассировке лучей?

Изменить: это то, что я уже делаю.

Код уже работает с высокой параллелью Временные данные
структурированы с использованием кэша, а также согласованы с 16b
Экран, разделенный на 32x32-плитки
Целевой массив устроен таким образом, что все последующие пиксели в плитке являются последовательными в памяти
Выполняются основные оптимизации графика сцены
- Общие комбинации объектов (CSG плоскости плоскости, как и в коробках) заменяются преоптимизированными объектами
Структура вектора, способная воспользоваться поддержкой автоматической векторизации GDC.
Последующие удары по лучу обнаруживаются с помощью ленивой оценки; это предотвращает ненужные вычисления для CSG
Треугольники не поддерживаются и не приоритетны. Только простые примитивы, а также операции с CSG и основные свойства материала.
Ограничение поддерживается

Ответ 1

Типичное улучшение скорости растрирования первого порядка - это своего рода схема пространственного разбиения. Основываясь только на странице вашего проекта, кажется, вы этого не сделали.

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

Многое зависит от сложности объектов, которые вы представляете, внутреннего дизайна (т.е. разрешаете локальные преобразования, ссылочные копии объектов, неявных поверхностей и т.д.), а также насколько точны вы пытаетесь быть. Если вы пишете глобальный алгоритм освещения с неявными поверхностями, компромиссы могут быть немного разными, чем если вы пишете базовый raytracer для объектов сетки или что-то еще. Я не смотрел ваш дизайн подробно, поэтому я не уверен, что, если таковые имеются, из вышесказанного, о котором вы уже думали.

Как и любой процесс оптимизации производительности, вам сначала нужно будет измерить, где вы на самом деле тратите время, а затем улучшаете вещи (алгоритмически по предпочтению, затем код bumming по необходимости)

Ответ 2

Одна вещь, которую я узнал с помощью своего трассировщика лучей, заключается в том, что многие старые правила больше не применяются. Например, многие алгоритмы трассировки лучей проводят много испытаний, чтобы получить "ранний" расчетно-дорогостоящий расчет. В некоторых случаях я обнаружил, что было намного лучше исключить дополнительные тесты и всегда выполнять расчет до завершения. Арифметика быстро развивается на современной машине, но предсказание пропущенных ветвей дорого. У меня получилось что-то вроде 30% -ного ускорения на моем тесте пересечения лучей-полигонов, переписав его с минимальными условными ветвями.

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

Иерархические ограничивающие объемы очень помогают, но я, наконец, собрал kd-дерево и получил ОГРОМНОЕ увеличение скорости. Конечно, для построения дерева есть затраты, которые могут сделать его непозволительным для анимации в реальном времени.

Следите за узкими местами синхронизации.

У вас есть профиль, чтобы быть уверенным, чтобы сосредоточить свое внимание в нужном месте.

Ответ 3

Есть ли что-то еще, что я могу сделать, чтобы ускорить его?

D, в зависимости от реализации и компилятора, обеспечивает хорошую производительность. Поскольку вы не объяснили, какие методы трассировки лучей и оптимизации вы используете уже, я не могу вам помочь.

Следующим шагом будет запуск анализа времени в программе и перекодировка наиболее часто используемого кода или самого медленного кода, чем наибольшее влияние на производительность в сборке.

В общем, проверьте ресурсы в этих вопросах:

Мне очень нравится идея использования графической карты (массового параллельного компьютера) для выполнения некоторой части работы.

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

Ответ 4

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

Это действительно зависит от ваших требований. Одна из простейших оптимизаций - просто уменьшить количество отражений/преломлений, которые может пройти любой конкретный луч, но затем вы начинаете проигрывать "идеальный результат".

Raytracing также является "смущающей параллелью" , поэтому, если у вас есть ресурсы (например, многоядерный процессор), вы может смотреть на вычисление нескольких пикселей параллельно.

Кроме того, вам, вероятно, просто нужно будет профилировать и выяснить, что именно занимает так долго, а затем попытаться оптимизировать это. Это обнаружение пересечения? Затем работайте над оптимизацией кода для этого и т.д.

Ответ 5

Некоторые предложения.

Использовать ограничивающие объекты для сбоя быстро.
Спроектируйте сцену на первом шаге (как это делают обычные графические карты) и используйте raytracing только для подсчета света.
Распараллеливать код.

Ответ 6

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

Отобразить сцену на графическом процессоре, а затем загрузить обратно. Это даст вам первое попадание лучей/сцены на скорости GPU. Если у вас нет много отражающих поверхностей в сцене, это уменьшит большую часть вашей работы до простого старого рендеринга. Рендеринг CSG на GPU, к сожалению, не совсем прост.

Прочитайте исходный код PovRay для вдохновения.:)

Ответ 7

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

еще несколько советов от меня - не используйте методы почтового ящика, в документах иногда обсуждается, что они недостаточно масштабируются с фактической архитектурой из-за подсчета накладных расходов - не используйте BSP/Octtrees, они относительно медленны. - не использовать графический процессор для Raytracing, он слишком медленный для продвинутых эффектов, таких как отражение и тени, преломление и картирование фотонов и т.д. (я использую его только для затенения, но это мой пиво)

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

И, конечно же, для действительно хорошей производительности вам нужно использовать очень SSE-код (с конечно же, не слишком много переходов), но не для того, чтобы "хорошая" производительность (например, речь здесь примерно о 10-15%) компилятор- intrinsics enougth для реализации ваших вещей SSE.

И некоторые приличные документы о некоторых алгоритмах, о которых я говорил:

"Быстрая перевязка с луком/осевой границей - тесты перекрытия с использованием лучей" (очень быстрый очень хороший паралелизуемый (SSE) тест AABB-Ray) (заметьте, код в документе не весь код, просто Google для названия бумаги, вы его найдете)

http://graphics.tu-bs.de/publications/Eisemann07RS.pdf

"Деформируемые сцены трассировки лучей с использованием динамических иерархий томов объема"

http://www.sci.utah.edu/~wald/Publications/2007///BVH/download//togbvh.pdf

если вы знаете, как работает вышеприведенный алгоритм, это гораздо больший алгоритм:

"Использование предварительно вычисленных треугольных кластеров для ускоренной трассировки лучей в динамических сценах"

http://garanzha.com/Documents/UPTC-ART-DS-8-600dpi.pdf

Я также использую pluecker-test для определения быстрого (не точного, но хорошо, вы не можете иметь все), если я нахожусь на полигоне, очень хорошо работает с SSE и выше.

Итак, я пришел к выводу, что существует так много замечательных статей о стольких тем, которые относятся к raytracing (как построить быстрые, эффективные деревья и как затенять (модели BRDF) и т.д. и т.д.), это это действительно удивительная и интересная область "экспериментирования", но у вас также должно быть много свободного времени, потому что это так сложно, но забавно.

Ответ 8

Мой первый вопрос: пытаетесь ли вы оптимизировать трассировку одного неподвижного экрана, или это о оптимизации трассировки нескольких экранов для вычисления анимации?

Оптимизация для одного кадра - это одно, если вы хотите вычислить последовательные кадры в анимации, есть много нового, о чем нужно подумать/оптимизировать.

Ответ 9

Вы могли

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

гораздо больше - но это были те предложения, о которых я мог сразу подумать. Другими словами:

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

"Обход пакетов" означает, что вы используете инструкции SIMD для вычисления 4 параллельных скаляров, каждый из собственных лучей для прохождения иерархии (обычно это горячая точка), чтобы выжать большую производительность из аппаратного обеспечения.

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

Использование кривой области на плитке позволяет уменьшить среднее расстояние между пикселями между пикселями и, следовательно, вероятность того, что ваша производительность зависит от кеша.