КОМПЬЮТЕРНАЯ ГРАФИКА
У л :
ОКТО-ДЕРЕВЬЯ СО МНОЖЕСТВЕННЫМИ ССЫЛКАМИ В ПРИМЕНЕНИИ К РЕАЛИЗАЦИИ ФОТОННЫХ КАРТ И КЭША
ОСВЕЩЕННОСТИ НА GPU. *
© 2014 г. В.А. Фролов1, A.A. Харламов2, В.А. Галактионов1, К.А. Востряков2
1 ИПМ им. М.В.Келдыша РАН
125047 Москва, Миусская пл., 4 2
127018 Москва, ул. Двинцев 12 E-mail: vfrolov@graphics.cs.msu.ru, akharlamov@nvidia.com, vlgal@gin.kcldysh.ru,
kvostryakov@nvidia. com Поступила в редакцию 17.01.2014
В данной статье предлагается эффективный и исключительно простой алгоритм построения окто-дерева со множественными ссылками на графических процессорах (GPU). Предлагаемый алгоритм построения дерева состоит из 4 шагов, использует линейные структуры данных и только 2 базовых операции параллельного программирования - параллельное добавление элементов в буфер и параллельную сортировку.
1. ВВЕДЕНИЕ
Окто-дерево является достаточно популярной структурой данных для геометрического поиска в силу своей регулярности и относительно небольшой глубины. Классическое окто-дерево рекурсивно разбивает трехмерное пространство на 8 частей, сохраняя в узлах ссылки на объекты, которые целиком находятся внутри узла. Окто-дерево с множественными ссылками представляет из себя модификацию классического варианта, в котором все ссылки хранятся только в листьях и на каждый объект ссылаются все листья, имеющие с данным объектом геометрическое пересечение. Этот факт позволяет реализовать поиск в дереве без использования рекурсии или стэка, поскольку для поиска всех объектов, включающих заданную точку трехмерного пространства достаточно спуститься от корня дерева к листу; каждый лист уже содержит список объектов, которые нужно перебирать последовательно.
*Работа поддержана грантами РФФИ № 12-0100560, РФФИ 13-01-00454 и стипендией президента РФ СП-4053.2013.5.
2. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ
Традиционный подход к построению окто-деревьев с множественными ссылками наиболее часто используется в технике кэширования освещенности [1]. Алгоритм позволяет добавлять новые элементы в дерево, постепенно достраивая его. При добавлении новые элементы спускаются вниз по дереву во все узлы, с которыми они имеют геометрическое пересечение. Фактически, этот подход эквивалентен классическому алгоритму построения окто-дерева сверху-вниз с той лишь разницей, что элементы могут добавляться в дерево постепенно. Такой подход обладает рядом определенных недостатков:
1. Иерархическое представление окто-дерева. При параллельной реализации возникают такие трудности как:
(а) Сложность управления памятью, поскольку при разбиении любого узла в общем случае неизвестно сколько дублированных ссылок окажется в дочерних узлах.
(Ь) Сложность максимизации иаралеллиз-ма, т.к. невозможно начать строить следующий уровень дерева пока недостро-ен предыдущий. Причем неважно строится ли дерево сверху вниз или снизу вверх.
2. Дорогостоящая операция вставки одного объекта, поскольку при вставке объекта происходит спуск по дереву ко всем листьям, с которыми он имеет пересечение. Во время такого спуска объект обходит множество нелистовых узлов, вычисляя с ними пересечение и инициируя лишние операций обращения к памяти.
3. Параллельная вставка нескольких объектов в окто-дерево даже при реализации на центральном процессоре может стать неэффективной при возникновении ситуации, в которой различные потоки пытаются добавлять объекты в один и тот же листовой узел. Справедливости ради следует отметить, что для этой проблемы существует решение на основе атомарных операций [2].
По этой причине для GPU используются алгоритмы, обладающие иной природой.
2.1. Построение окто-дерева па GPIJ
Алгоритмы построения окто-деревьев на GPU используют факт взаимосвязанности окто-дерева и трехмерной Z-кривой, которая получается в результате вычисления Z-индекса (или кода Мортона [3]). Зафиксируем некоторую глубину дерева 'к'. Не ограничивая общности, предположим, что имеется такой набор точек в трехмерном пространстве, что в каждый узел построенного в будущем окто-дерева попадет не более одной точки. Если вычислить для точек коды Мортона и затем отсортировать точки по этим кодам, мы получим массив, эквивалентный окто-дереву, где в каждом листе хранится ровно по одному элементу (одной точке). Выполняя далее поиск в трехмерном пространстве в произвольной точке (x,v,z), мы вычисляем ее код Мортона и, применив бинарный поиск для полученного кода Мортона (ZInxed(x, у, z)), находим листовой узел окто-дерева, в который попала точка (х, у, z).
В работе [4] было впервые замечено соответствие между Z-кривой и окто-деревом и использовано свойство отбрасывания младших битов Z-индекса для получения идентификаторов старших узлов. Окто-дерево в [4] представлялось набором массивов Ll..Lk, размером 8i элементов для каждого уровня глубиной i (т.е. несуществующие узлы хранились в памяти на регулярной сетке). Вопрос хранения каких-либо элементов данных в окто-дереве в работе [4] не рассматривается. Таким образом, построенное окто-дерево не может быть использовано непосредственно для пространственного поиска элементов, а может только отвечать на вопрос имеются ли искомые элементы в некотором объеме или нет.
В работе [5] окто-дерево было использовано для построения поверхности из набора точек при помощи алгоритма марширующих кубов. Алгоритм построения использовал серию из параллельных операций уплотнения и сортировки. В отличие от работы [4], Zhou и др. сохраняют только существенные узлы в памяти, а также сохраняют списки точек на всех уровнях дерева. При этом, в [5] было замечено, что имея отсортированный массив точек по их Z-индексу в узле, достаточно сохранять лишь 2 смещения, обозначающих начало и конец последовательности точек для данного узла в отсортированном массиве. Причем при переходе от уровня к на уровень к-1 это свойство сохраняется и точки пересортировывать не нужно. Достаточно пересчитать указатели соответствующие началу и концу последовательности .
Если в рассмотренных ранее работах только отдельные уровни дерева строились параллельно, то в работе [6] был предложен метод, использующий массивный параллелизм GPU при построении всего дерева. Основная идея алгоритма заключается в том, чтобы пронумеровать все узлы дерева при помощи индексов таким образом, чтобы индекс родительского узла всегда являлся префиксом по отношению к индексам его дочерних узлов, рассматривая индексы как битовые строки. Тогда отсортированный массив индексов будет эквивалентен дереву. Следует отметить, что это свойство префиксов кодов Мортона было описано ранее в работе [4].
В предложенных ранее подходах построения
окто-дерева в качестве ассоциированных объектов использовались точки - элементы, не имеющие размера. Так как каждая точка при этом условии попадает не более чем в 1 лист, это позволяло использовать тот факт, что искомые элементы данных всегда лежат последовательно в отсортированном по их Z-индексам массиве [5]. Однако, в случае элементов, имеющих размер, это условие нарушается, поскольку один и тот же элемент может попасть в несколько узлов. Для решения этой проблемы мы используем окто-деревья с множественными ссылками и предложенный нами алгоритм построения таких деревьев на GPU.
2.2. Множественные ссылки
В работе [7] впервые высказана идея построения ускоряющей структуры на GPU при помощи сортировки индексов ссылок (а не индексов центров объектов) на основе разреженной сетки. Размер ячейки в [7] был в 2 раза больше размера самого большого объекта, что гарантирует возникновение не более 8 ссылок на каждый объект. Каждая ссылка, таким образом, может быть записана в заранее отведенную для нее ячейку памяти, а общий размер массива ссылок - 8*N где N - число объектов. Такое ограничение размера ячейки может негативно сказаться на скорости поиска при разных размерах объектов (кэш освещенности является одним из таких случаев), поскольку метод вынужденно выбирает размер ячейки сетки в соответствии с самым большим объектом.
2.3. Фотонные карты на GPIJ
Фотонные карты на GPU - довольно популярная тема для исследований. Одна из основных трудностей при реализации фотонных карт -эффективное построение ускоряющих структур для последующего поиска ближайших фотонов.
В работе [8] алгоритм фотонных карт был впервые реализован на GPU. Аппаратные ограничения GPU того времени не позволяли производить запись в произвольную область памяти, что создавало целый ряд проблем при реализации ускоряющих структур на GPU. В [8] предложено 2 метода построения ускоряющих структур на основе регулярной сетки. Первый метод основан на сортировке фотонов по номеру воксела,
в который он попадает. После чего при помощи бинарного поиска находился первый фотон в отсортированном массиве фотонов и формировался список индексов. Второй метод использует аппаратные возможности на основе буфера трафарета и является болеее быстрым, но позволяет сохранять ограниченное число фотонов на каждый воксел. Недостатком обоих методов из работы [8] является высокий расход памяти.
В работе [9] был предложен эффективный алгоритм построения kd-деревьев с учетом эвристики VVH [10] и алгоритм поиска к-ближайших фотонов. Алгоритм из работы [9] изначально ориентирован на построения kd-дерева над множеством полигонов. Он использует 2 различных подхода в зависимости от количества примитивов в узле и хранит данные в динамических списках на GPU. Алгоритм [9] сложен в реализации и, кроме того, расходует больше памяти, чем его CPU аналог. Производительность поиска k-ближайших фотонов при этом низкая вследствие итеративного поиска оптимального радиуса сбора.
В [11] в целях упрощения алгоритма построения и повышения его эффективности был предложен подход на основе предрассчитанного kd-дерева и сортировки ндексов фотонов на CPU при помощи механизма быстрых списков. Алгоритм построения результирующей структуры имеет линейную сложность. Среди недостатков данного подхода следует отметить необходимость априорного знания о геометрии сцены (на основе которого предрассчитывается kd-дерево) и копирование данных между CPU и GPU.
В [12] для ускорения сбора осве
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.