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

Question

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

Редактировать: это то, что я уже делаю.

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Вы должны зарегистрироваться, чтобы сосредоточить свое внимание в нужном месте.

Answer 3

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

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

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

В общем, ознакомьтесь с ресурсами по следующим вопросам:

• Литература и учебные пособия по написанию трассировщика лучей
• Кто-нибудь знает действительно хорошую книгу о Рэй Тракинг?
• Компьютерная графика: трассировка лучей и программирование 3D-рендеринга
• трассировка лучей с помощью CUDA

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

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

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

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

http://graphics.tu -bs.de / публикации / 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 для определения быстрого (не очень точного, но хорошо, что вы не можете иметь все), если я попал в многоугольник, очень хорошо работает с SSE и выше.

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

Answer 8

Вы могли бы

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

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

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

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

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

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

Answer 9

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

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