Содержание

1. Резюме
2. Введение
3. Обход лучей по принципу Разделяй и Властвуй
4. Наш алгоритм
   1. Фильтрация лучей
   2. Сегментация треугольников
   3. Пересечение треугольников
   4. Упорядоченный обход
5. Результаты
6. Выводы и дальнейшая работа
7. Благодарности
8. Перечень ссылок

1. Резюме

Недавно было представлено новое семейство алгоритмов динамической трассировки лучей по принципу разделяй и властвуй. При этом подходе сегментация примитивов выполняется на лету в процессе трассировки лучей, что позволяет избавиться от необходимости использовать ускоряющую структуру. Мы представляем новый метод обхода лучей на основе данного принципа. Он эффективно работает с некогерентными лучами и использует преимущества SSE и AVX инструкций CPU. Наш алгоритм позволяет добиться заметного повышения производительности по сравнению с аналогичными существующими решениями и способен соперничать с мощными статичными трассировщиками лучами.

2. Введение

Трассировщик лучей обычно состоит из двух частей: обход лучей и построение ускоряющей структуры. Визуализация полностью динамических сцен с помощью трассировки лучей является довольно сложной задачей, так как для каждого кадра ускоряющая структура должна быть построена заново или обновлена. Данной теме посвящено множество исследований [WMG*09].

Keller и Wächter [KW11] недавно предложили концептуально новый элегантный подход: трассировка лучей по принципу разделяй и властвуй (РИВ). Его основная идея заключается во внедрении этапа сегментации примитивов в алгоритм обхода лучей. Таким образом, потребность в использовании ускоряющей структуры отпадает. К сожалению, многие детали работы алгоритма и результаты измерения его производительности авторами предоставлены не были. На сегодняшний день единственная опубликованная полная реализация принадлежит Mora [Mor11]. В ней сегментация примитивов выполняется по типу kd-дерева, без использования при этом высококачественной эвристики площади поверхности (англ. surface area heuristic, SAH) [Hav00].

В этой статье мы предлагаем новый алгоритм обхода по принципу РИВ, основанный на базовом методе Keller и соавторов. В целом, наш подход более эффективен, чем метод Mora, и он использует мощь нового набора инструкций AVX (Advanced Vector Extensions), представленного в микроархитектуре Intel Sandy Bridge. Мы оптимизировали наш метод для работы с некогерентными лучами, потому что большинство лучей, сгенерированных визуализатором, который использует алгоритм трассировки лучей, основанный на методах Монте-Карло (например, трассировка путей, фотонные карты), обладают слабой когерентностью или не обладают ею совсем. Метод не только повышает производительность физически-точной визуализации, но также и упрощает общую архитектуру трассировщика.

3. Обход лучей по принципу Разделяй и Властвуй

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

Входами алгоритма являются множество лучей и множество примитивов, с которыми эти лучи требуется пересечь. В начале каждого шага обхода мы определяем, какие лучи пересекают ограничивающий параллелепипед (англ. bounding box), описанный вокруг примитивов. Эта процедура называется фильтрацией лучей, а лучи, которые пересекли параллелепипед — активными лучами. Затем мы решаем, следует ли продолжить сегментацию примитивов или непосредственно вычислить их пересечения с активными лучами. Если мы выполнили сегментацию примитивов, то мы рекурсивно вызываем функцию обхода полученных подмножеств.

4. Наш алгоритм

Ключевой частью алгоритма обхода является сегментация примитивов. Kd-деревья строятся с использованием пространственной сегментации, в то время как BVH в основном используют сегментацию объектов. Важная особенность сегментации объектов и её отличие от пространственной сегментации заключается в том, что результатом деления списка примитивов будут непересекающиеся подсписки. BVH лучше подходят для использования в динамических сценах, так как могут быть построены в разы быстрее kd-деревьев и потребляют меньше памяти, являясь более простыми структурами [Wal07]. Поэтому в нашем алгоритме обхода, мы решили использовать сегментацию объектов.

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

4.1 Фильтрация лучей

Фильтрация лучей предназначена для определения списка активных лучей, которые пересекают заданный выровненный по осям ограничивающий параллелепипед (англ. axis-aligned bounding box, AABB). Изначально данный список содержит все лучи, и на каждом шаге обхода рекурсивно фильтруется. Фильтрация может быть выполнена на ходу путём сортировки списка для его разделения на части, содержащие активные и неактивные лучи. В этом случае активные лучи будут расположены в начале списка и для их идентификации достаточно знать смещение к концу списка.

Мы храним лучи в единственном непрерывном массиве. Так как наш метод должен одновременно трассировать миллионы лучей, занимаемый ими объём памяти существенен. Это влияет не только на требования к доступному объёму памяти, но и на скорость.

Луч определяется точкой начала, вектором направления, интервалом [0, tmax], который задаёт отрезок линии, и идентификатором (ID). Общий размер луча — 32 байта, что соответствует одному регистру AVX или двум регистрам SSE. Большинство алгоритмов трассировки предварительно вычисляют вектор, обратный вектору направления луча, однако это неприменимо к нашему методу, так как больший размер структуры данных луча снижает производительность.

Mora [Mor11] фильтрует лучи, сортируя элементы вспомогательного массива ID, чтобы избежать перестановки структур самих лучей, которые имеют намного большие размеры. Такой подход предпочтителен при работе с когерентными лучами и небольшими массивами, однако для массивов некогерентных лучей, размер которых превышает размер кэша, такой подход недостаточно хорош. Количество промахов кэша (англ. cache miss) из-за произвольного обращения к памяти может быть существенно уменьшено за счёт использования предварительной программной загрузки, но кэш-память при этом всё-равно расходуется впустую. CPU предварительно загружает целые строки кэша (обычно 64 байта), которые превышают размер одного луча. Если используются не все лучи, помещённые в строку кэша, то окажется, что половина данных загружена зря.

Мы решаем эти проблемы за счёт перестановки самих лучей в исходном массиве. В данном случае объёмы перемещаемых данных существенно превышают те, что использовались в предыдущем методе, но при этом дополнительная информация не требуется, а кэш используется крайне эффективно. Так как доступ к лучам всегда выполняется линейно, то запускаемая автоматически аппаратная загрузка эффективна. Лучи могут быть быстро скопированы в блоки по 32 (с использованием AVX) или 16 байт (с использованием SSE). Данный подход к фильтрации наилучшим образом подходит для некогерентных лучей, при работе с которыми он повышает скорость обхода как минимум на 25%.

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

Наборы инструкций SIMD позволяют ускорить фильтрацию за счёт параллельной обработки нескольких пересечений лучей с параллелепипедами. В нашей реализации мы одновременно пересекаем 4 луча при использовании SSE и 8 лучей при использовании AVX. Перед этим информация, хранящаяся в луче, должна быть организована в виде структуры массивов (англ. structure-of-arrays, SoA). Мы вновь используем подходящую для SIMD организацию данных луча, чтобы быстро переместить значения с помощью SIMD-инструкций перетасовки.

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

4.2 Сегментация треугольников

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

Алгоритмы сегментации работают только с AABB, но не с самими треугольниками. Мы заранее рассчитываем AABB и помещаем в отдельный массив, чтобы избежать их повторного вычисления и оптимизировать использование кэша. Мы ускоряем вычисления с участием AABB за счёт их хранения в подходящем для SIMD 32-байтовом формате: минимальная и максимальная границы (которые являются 3D векторами) дополнены до 16 байт, поэтому они могут быть напрямик загружены в регистры SSE.

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

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

При некоторых разбиениях мы используем SAH сегментацию, которая обычно позволяет добиться меньшей стоимости пересечения, но выполняется медленнее. Мы применяем алгоритм SAH binning [Wal07] с 32 корзинами, который работает намного быстрее, чем точный подход [Hav00, WBS07] и выдаёт почти настолько же хорошие результаты.

Постоянное использование SAH при сегментации не обязательно приводит к максимально возможной производительности трассировки лучей, так как вычислительная стоимость его расчёта может превысить стоимость расчёта пересечения луча. Мы решаем данную проблему путём адаптивного выбора между SAH и медианной сегментацией. На каждом шаге разбиения выполняется сравнение отношения количества активных лучей к количеству текущих треугольников с заданным пороговым значением. Если отношение превышает порог, то выбирается SAH сегментация. В противном случае используется медианная сегментация. Мы эмпирическим путём выяснили, что наилучшие результаты достигаются при величине отношения количества лучей к количеству треугольников, лежащем в пределах от 1 до 2.

4.3 Пересечение треугольников

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

В нашем методе используется специальное представление треугольников для сохранения пространства памяти и полосы пропускания. Полезным свойством AABB треугольника является возможность его задания с помощью 6 вершинных координат: минимальные и максимальные координаты вершины для каждой оси. В дополнительном массиве мы храним отсутствующую информацию для каждого треугольника. Эта вспомогательная структура данных содержит 3 оставшиеся вершинные координаты и 32-битное целое, в котором кодируется исходный порядок координат, необходимый для восстановления вершин треугольника.

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

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

4.4 Упорядоченный обход

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

Существенное положительное влияние на скорость трассировки оказывает обход с близи вдаль спереди назад для первичных лучей. Тем не менее, для некогерентных лучей данный подход не даёт существенного улучшения. Мы определяем порядок обхода с помощью очень простого подхода, использованного в пакетном трассировщике Wald и других [WBS07]. Вначале мы находим ось, на которой два дочерних параллелепипеда наиболее удалены. Затем мы берём знак направления первого активного луча на этой оси и выбираем первого потомка в соответствующем направлении.

5. Результаты

Оценка производительности проводилась на двух разных системах: на Intel Core i7-960 (Nehalem, 4 ядра, 8 потоков, 3.2 ГГц, 8 Мб L3 кэш) с 24 Гб ОЗУ (трёхканальный режим работы), и на Intel Core i7-2600 (Sandy Bridge, 4 ядра, 8 потоков, 3.4 ГГц, 8 Мб L3 кэш) с 8 Гб ОЗУ (двухканальный режим работы).

Мы сравнили наш метод с высокооптимизированным статическим трассировщиком лучей, использующим ускоряющую структуру multi-BVH (MBVH) [WBB08]. Мы построили MBVH, используя те же схемы сегментации, которые применяются в нашем методе. Вплоть до 16K треугольников мы разбивали с использованием binned SAH. В случае большего количества треугольников, применялся метод медианной сегментации.

Мы тестировали алгоритмы, используя трассировку путей по методу Монте-Карло с 1 и 8 отражениями (количество отражений определяет максимальную глубину трассировки луча). Лучи были бесконечной длины, для них выполнялся поиск ближайшей точки пересечения. Метод русской рулетки не использовался.

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

Таблица 1 демонстрирует показатели производительности в миллионах лучей в секунду. Замеры времени для метода MBVH не учитывают время построения ускоряющей структуры. Однако даже в этом случае в большинстве ситуаций наш метод по-прежнему вполне конкурентоспособен. Например, при визуализации сцены CONFERENCE ROOM с помощью трассировки путей с 8 отражениями, MBVH исполняется всего на 12% быстрее в одном потоке на i7-960. Тем не менее, разница более заметна при многопоточном исполнении, особенно для сцены HAIRBALL, которую где наш метод обрабатывает в 4 раза медленнее.

Другим важным наблюдением является то, что AVX предоставляет заметный прирост скорости по сравнению с SSE. Предыдущие исследования показали, что AVX позволяет ускорить трассировку первичных лучей примерно на 50% [Áfr11]. Для рассеянных лучей трассировка по нашему методу при использовании AVX происходит на 0-47% быстрее, чем при использовании SSE. Хорошее ускорение достигается и при обходе MBVH: 15-31%.

Результаты также показывают, что традиционная процедура обхода лучей лучше масштабируется на несколько потоков, чем обход по принципу РИВ. Тогда как MBVH масштабируется сверхлинейно с увеличением количества ядер, наш метод в некоторых случаях масштабируется сублинейно. Странно, но i7-2600 обычно масштабируется хуже, чем более старые i7-960, возможно, из-за своей немного худшей системы памяти. Для одной из сцен, и SSE, и AVX версии трассировщика на i7-2600 работают даже медленнее, чем его SSE версия на i7-960. Ускорения от применения многопоточности сильно зависит от сцены: на i7-960 оно составило 3.4-4.9 раз, и на i7-2600 — 1.8-5.3 раз. Сублинейное масштабирование говорит о том, что пропускная способность памяти является основным узким местом в обеспечении производительности.

Наиболее трудоёмкой частью нашего алгоритма является фильтрация лучей. Для сцены CONFERENCE ROOM, 70% времени трассировки занимает фильтрация лучей, 19% — пересечение с треугольниками и 11% — сегментация треугольников. В таких случаях простейшая схема реализации многопоточности довольно эффективна, так как сегментация слабо влияет на общую производительность. Тем не менее, для сложных сцен, таких как HAIRBALL, влияние сегментации на производительность более заметно: 37% — фильтрация, 25% — пересечение, 38% — сегментация (обратите внимание, что треугольников почти в 4 раза больше, чем лучей).

По сравнению с методом Mora, наш подход более эффективно фильтрует лучи, использует более качественную сегментацию объектов, более широко задействует возможности SIMD, и оптимизирован для некогерентных лучей. При исполнении в однопоточном режиме на CPU с чуть более высокими тактовыми частотами, для сцены CONFERENCE ROOM наш SSE код работает в 1.3-1.5 раз быстрее, а код AVX — в 2.2 раза быстрее. Расходы памяти при использовании метода аналогичны. Имея на входе R лучей, T треугольников и N потоков, наш метод использует 32R+(48+4N)T байт, в то время как для метода Mora данный показатель равен 36R+(40+4N)T байт (не считая размер стека и данных о пересечении).

6. Выводы и дальнейшая работа

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

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

7. Благодарности

Данная работа проводилась при поддержке POSDRU/107/1.5/S/76841 и OTKA K-719922 (Венгрия).

8. Перечень ссылок

• [Áfr11] ÁFRA A. T.: Improving BVH ray tracing speed using the AVX instruction set. In EG 2011 — Posters (Llandudno, UK, 2011), Eurographics Association, pp. 27-28. 3
• [Hav00] HAVRAN V.: Heuristic Ray Shooting Algorithms. PhD thesis, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, November 2000. 1, 2
• [KW11] KELLER A., WÄCHTER C.: Efficient ray tracing without auxiliary acceleration data structure. High-Performance Graphics 2011 (Poster) (2011). 1
• [Mor11] MORA B.: Naive ray-tracing: A divide-and-conquer approach. ACM Transactions on Graphics 30, 5 (October 2011), 117:1-117:12. 1, 2
• [Wal07] WALD I.: On fast construction of SAH-based bounding volume hierarchies. In Proceedings of the 2007 IEEE/EG Symposium on Interactive Ray Tracing (2007), pp. 33-40. 2
• [WBB08] WALD I., BENTHIN C., BOULOS S.: Getting rid of packets — Efficient SIMD single-ray traversal using multibranching BVHs. In Proceedings of the 2008 IEEE/EG Symposium on Interactive Ray Tracing (2008), pp. 49-57. 3
• [WBS07] WALD I., BOULOS S., SHIRLEY P.: Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Transactions on Graphics 26, 1 (January 2007), 6:1-6:18. 2, 3
• [WMG*09] WALD I., MARK W. R., GÜNTHER J., BOULOS S., IZE T., HUNT W., PARKER S. G., SHIRLEY P.: State of the art in ray tracing animated scenes. Computer Graphics Forum 28, 6 (2009), 1691-1722. 1