Назад в библиотеку   Портал магистров

Повышение производительности методов реконструкции поверхности за счет применения параллельных вычислений.

Автор:А.С. Резниченко, М.В. Привалов
Источник: Інформаційні управляючі системи та комп’ютерний моніторинг (ІУСКМ–2013) / Матерiали IV мiжнародної науково–технiчної конференцiї студентiв, аспiрантiв та молодих вчених. — Донецьк, ДонНТУ — 2013, Том 1.

Аннотация

А. С. Резниченко, М. В. Привалов Повышение производительности методов реконструкции поверхности за счет применения параллельных вычислений. Выполнен обзор и анализ популярных алгоритмов, используемых для реконструкции поверхности, а также путей ускорения расчетов за счет распараллеливания. Рассмотрены  перспективы применения GPGPU вычислений для ускорения  расчетов.

Ключевые слова: реконструкция поверхности, триангуляция, алгоритм «марширующие кубы», распараллеливание.

 

Постановка проблемы. Проблема  реконструкции (визуализации) поверхности, заданной различными способами возникает во многих областях математики, физики, медицины [1]:

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

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

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

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

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

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

Цель работы – повышение производительность ресурсоёмких алгоритмов реконструкции поверхности за счет выделения в них трудоёмких независимых задач и их распараллеливания.

Анализ литературы. Основными алгоритмами, которые применяются при восстановлении поверхностей, являются:

- алгоритмы отбрасывания лучей [2];

- алгоритмы триангуляции [3];

- алгоритм марширующих кубов [4];

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

Алгоритмы триангуляции менее ресурсоёмки, при этом имеются быстрые даже в однопоточном варианте реализации. Одним из примеров такой реализации является алгоритм построения триангуляции Делоне, описанный в работе [5], который на персональном компьютере средней мощности (Core2Quad 2,83ГГц, 8Гб ОЗУ) позволяет выполнить триангуляцию поверхности из 100000 точек за 8 секунд.

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

Описание алгоритма. Согласно [4], алгоритм состоит из двух основных стадий. Первая стадия: построение неявной функции F: D>R, где  D принадлежит  R³ -окрестность поверхности. Функция  F  представляет собой оценку расстояния от любой точки из D до поверхности. Вторая стадия: триангуляция поверхности нулевого уровня функции F при помощи алгоритма марширующих кубов.

Для построения оценки расстояния мы, ассоциируем с каждой точкой набора {x₁,…,x_n} ориентированную касательную плоскость Tp(x_i) , которую можно найти при помощи метода главных компонент, примененного к k ближайшим соседям точки x_i. Вычисление функции расстояния осуществляется по формуле:

 

F(p) = (p-o_i)n_i ,                                    (1)

 

где  o_i  – ближайший к p  «центр» касательной плоскости (центроид  k ближайших соседей), а  n_i– соотвестсвующая ему нормаль.

Алгоритм «Марширующие кубы», можно разбить на два этапа:

1. Разбиение области G пространства R³ на конечное множество ячеек, поиск ячеек пересекаемых искомой поверхностью.

2. Аппроксимация поверхности в найденных ячейках.

Две эти подзадачи являются независимыми. Рассмотрим их подробнее.

Первый этап.

Основные проблемы этого этапа заключается в следующем [4]:

1. Разбить область G на ячейки.

2. Выбрать ячейки, которые пересекаются с искомой поверхностью.

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

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

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

Форма ячейки в алгоритме «Марширующие кубы» - параллелепипед. Однако это не единственно возможный вариант. Форма ячейки определяет дальнейшую триангуляцию ячейки. Причем, если вершина ячейки находится вне объема ограниченного искомой поверхностью, то значение этого бита 0, иначе - 1. Тогда количество разных типов триангуляции будет 2^N. Отсюда видно, что использовать в качестве ячейки, например, икосаэдр не оптимально.

Итак, допустим, что область G уже разбита на ячейки. Тогда главной проблемой становится поиск ячеек пересекаемых искомой поверхностью. Пусть С - множество ячеек, тогда C_v - множество ячеек пересекаемых поверхностью F(P)=v. Тогда можно считать, что поверхность пересекает ячейку, если существуют такие P₁ и P₂ - вершины ячейки, что:

 

F(p₁) <v< F(p₂),                                                  (2)

 

Это условие выполняется, когда выполняется:

 

Min_i F(p_i) <v< Max_j F(p_j),                                     (3)

 

где p_i и p_j - вершины ячейки.

Таким образом, проблема свелась к следующему: из множества ячеек C выбрать подмножество C_v ячеек, удовлетворяющих условию (3).

Второй этап. Пространство разбивается на ячейки, и отбираются только те ячейки, в которых надо производить аппроксимацию. Таким образом, задачей второго этапа является аппроксимация поверхности в одной ячейке. Наиболее оптимальный способ аппроксимации – триангуляция [4]. Необходимо определить, сколько способов триангуляции имеет параллелепипед. Пусть имеется 8-битовый индекс. Тогда сопоставим каждой вершине один бит в индексе. Причем, если вершина ячейки находится вне объема ограниченного искомой поверхностью, то значение этого бита 0, иначе - 1. Тогда количество разных типов триангуляции будет 2⁸=256.

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

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

• вычисление идентификаторов точек;
• переупорядочение точек;
• выделение вокселей сетки;
• вычисление шаблонов ячеек;
• генерация треугольников.

Так как эти задачи предполагают однотипные операции над большим количеством данных, то распараллелить их было бы достаточно хорошо, используя даже вычислительные системы, относящиеся к классу SIMD. К таким системам относятся современные графические ускорители [6]. Для наиболее универсального ускорения расчетов с использованием GPGPU предлагается вариант  распараллеливания  алгоритма с применением OpenCL, что позволит применять ускорители nVidia, AMD и Intel. Использование графических ускорителей при решении данной задачи аргументируется тем, что выполнение расчётов с использованием графического ядра дает хорошие результаты в алгоритмах, использующих параллельную обработку больших массивов данных. В нашем случае отношение числа арифметических инструкций, которые придется исполнять при построении поверхности, достаточно велико по отношению к числу обращений к памяти, что обычно даёт лучшие результаты при реализации с применением GPGPU вычислений.

Алгоритм должен содержать следующие шаги:

1. Реализация ускоряющей структуры, для входного набора данных.
2. Восстановление поля нормалей.
3. Вычисление оценки расстояний.
4. Нахождение поверхности нулевого уровня оценки расстояния (алгоритм «марширующих кубов»).

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

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

Хорошая реализация параллельного алгоритма поиска касательной приведена в работе [7]:

1. Получить из глобальной памяти обрабатываемую точку.

2. Определить целочисленные координаты вокселя (x,y,z).

3. Выполнить выборку индексов точек вокселя (x,y,z) и его соседей.

4. Скопировать точки с полученными индексами в локальную память и отсортировать точки по возрастанию расстояния.

5. Выбрать из локальной памяти координаты ближайших точек.

6. Вычислить центроид и поместить его в выходной буфер.

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

Для вычисления оценки расстояния предлагается помещать центроиды  в ускоряющую структуру, что позволяет использовать следующую параллельную схему:

1. Получить из глобальной памяти обрабатываемую точку.

2. Определить целочисленные координаты вокселя (x,y,z).

3. Найти ближайший центроид и соответствующую ему нормаль.

4. Вычислить оценку расстояния.

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

Следует отметить, что, несмотря на свою популярность и широкое применение, алгоритм марширующих кубов имеет существенный недостаток: на достаточно простых участках поверхности он выполняет слишком большое количество разделений. Например, на поверхности, которая может быть аппроксимирована с помощью 440 полигонов, классический алгоритм может сгенерировать порядка 67000 [8]. Это подчеркивает выигрыш в производительности от распараллеливания, но также говорит о необходимости улучшения базового алгоритма.

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

 

Список литературы

1. Сравнительный анализ методов интерактивной триангуляции сеточных функций/ Интернет-ресурс. - Режим доступа: www/URL: http://cgm.computergraphics.ru/content/view/63#_ - Загл. с экрана.
2. Volume ray casting / Интернет-ресурс. – Режим доступа: www/URL: http://en.wikipedia.org/wiki/Volume_ray_casting - Загл. с экрана.
3. А. В. Скворцов Триангуляция Делоне и её применение. – Томск: Изд-во Томского ун-та, 2002. – 128с.
4. Lorensen, W. E., And Cline, H. E. 1987. Marching cubes: A highresolution 3d surface construction algorithm. In Proceedings of SIG-GRAPH’87, 163–169.
5. V. Domiter, B. Zalik Sweep-line algorithm for constrained Delaunay triangulation / Int. Journal of Geographical Information Science, Vol. 22, No. 4, April 2008. – P. 449-462.
6. NVIDIA Corporation. NVIDIA CUDA Compute Uni?ed Device Architecture Programming Guide. Version 3.2.2010.
7. GPU-алгоритм восстановления поверхности из облака точек/Интернет-ресурс.-URL: http://nano.msu.ru/files/conferences/GPU-2010-05/abstracts.pdf
8. S. Schaefer, J. Warren, Dual Marching Cubes: Primal Contouring of Dual Grids / PG '04 Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, 2004. – P.70-76.