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

На правах рукописи

4/

005048083

Суравикин Артем Юрьевич

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

Специальность 05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

и >!ПЙ 2013

Омск - 2012

005048083

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»

кандидат физико-математических наук, доцент Коробицын Виктор Викторович

Вшивков Виталий Андреевич

доктор физико-математических наук, профессор Институт вычислительной математики и математической геофизики СО РАН, зав. лабораторией

Давыдов Максим Николаевич

кандидат физико-математических наук, Институт гидродинамики им. Л.А. Лаврентьева СО РАН, научный сотрудник

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кемеровский государственный университет»

Научный руководитель: Официальные оппоненты:

Защита состоится 15 января 2013 г. в 15 часов на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук (ИВМиМГ СО РАН) по адресу 630090, г. Новосибирск, проспект академика. Лаврентьева, 6, тел. (383)330-71-59.

С диссертацией можно ознакомиться в библиотеке ИВМиМГ СО РАН.

Автореферат разослан 11 декабря 2012 г.

Ученый секретарь диссертационного совета д.ф-м.н.

Сергей Борисович Сорокин

Общая характеристика работы

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

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

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

Изначально SPH использовался для моделирования процессов, происходящих в звездах [5]. затем его стали применять для расчета течений несжимаемой жидкости со свободной поверхностью [6], деформации при соударениях [2j, газодинамики взрывов [1]. Авторы [3] используют данный метод для моделирования цунами и оползней. В [4] описано моделирование обрушения столба воды в лабораторном эксперименте и водосброса на речной дамбе. Исследования и способы усовершенстовования самого метода сглаженных частиц в применении к течениям несжимаемых жидкостей приводятся в [4. 7] В этих работах особое внимание уделяется вычислению сил давления, котсь рые позволяют сохранять несжимаемость жидкости при больших временных шагах интегрирования.

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

вычислений на многопроцессорных и многоядерных системах. Отдельно от таких систем стоят технологии GPGPU — вычисления общего назначения па графических процессорах (General Purpose GPU computations). В частности компания NVIDIA поддерживает архитектуру CUDA, обеспечивающую программирование массивно параллельных программ на GPU. Программируемые графические адаптеры вызывают особый интерес у исследователей тем, что современные графические процессоры обладают высокой теоретической производительностью и высокой пропускной способностью памяти устройства за счет параллелизма.

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

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

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

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

Для достижения поставленной цели необходимо было решить следующие задачи:

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

2. Разработать метод визуализации жидкости, обеспечивающий возможность расчета с учетом прозрачности изображения жидкости, смоделированной методом частиц.

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

Основные положения, выносимые на защиту:

1. Реализация алгоритма SPH на графическом процессоре позволяет увеличить производительность вычислений в 73-103 раза по сравнению с центральным процессором.

2. В двумерном случае для течений с низкими числами Рейнольдса при использовании метода SPH абсолютная погрешность не превышает 0,001г,

где г — радиус частицы. Относительная погрешность не превышает 0,5%. В двумерных задачах с обрушением столба жидкости погрешность не превышает 4% с учетом погрешности измерения времени в реальном эксперименте. В трехмерном случае погрешность метода SPH не превышает 9% в задачах с обрушением столба жидкости.

3. Размещение частиц жидкости для начальных и граничных условий в виде однородной сетки с шагом s = 1.15/г при h « 1,728179г позволяет получить требуемую плотность жидкости.

Научная новизна:

1. Впервые предложена реализация метода PCISPH на CUDA с полной процедурой вычислений на GPU.

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

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

4. Предложен новый алгоритм формирования изоловерхности облака частиц на основе октодеревьев.

Практическая и научная значимость работы:

1. Реализованная программа моделирования движения жидкости обеспечивает ускорение процесса исследования течений жидкости за счет применения GPU в расчетах.

2. Представлен ряд параллельных алгоритмов для моделирования движения жидкости с реализацией на GPU.

3. Реализованные алгоритмы используются в качестве учебного материала при обучении студентов ОмГУ специальности 230101 по дисциплине «Архитектура и программирование вычислительных систем».

Апробация работы. Основные положения диссертации были изложены в виде докладов на Межвузовской научно-практической конференции «Информационные технологии и автоматизация управления» (Омск, 2009); XLVIII Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2010); Международной конференции «Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления» (Москва, 2010); на семинарах кафедры вычислительных систем ОмГУ.

Публикации. Результаты диссертации опубликованы в 9 работах, из них 2 статьи в журнале из списка, рекомендованного ВАК.

Структура и объем диссертации. Диссертация состоит из введения 4 глав, заключения, списка литературы и приложения. Общий объем составляет 135 страниц, содержит 18 рисунков, 11 таблиц. Библиографический список насчитывает 94 наименования.

Содержание работы

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

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

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

п

в -- -------+н-! > а<|

Н1 Н2 нз : ; Н4

ГТП ь,

Рис. 1: Схема эксперимента обрушения дамбы: вид сверху и вид сбоку

В работе создается модель эксперимента обрушения столба жидкости в резервуаре с препятствием (рис. 1). При моделировании несжимаемых жидкостей методом сглаженных частиц используется модель слабосжимаемой жидкости, движение которой описывается уравнениями Навье—Стокса:

^ = + V • + (1)

дг р

д-1 = -рУ-у. (2)

т

Здесь р — плотность, V {ух,иу,у2) — скорость жидкости в некоторой точке, р — давление, и — коэффициент кинематической вязкости, ¥езЛ — внешние силы, приведенные к единице массы. Для учета силы тяжести примем Ретг = Давление р для слабосжимаемой жидкости с жесткостью к и 7 = 7 в точке с плотностью р можно получить с помощью уравнения состояния:

Начальные условия представляют собой жидкость, которая заполняет прямоугольный параллелепипед размерамиахЬхк. Для всех точек жидкости в данном объеме скорость V = 0, плотность р = 1000^ = р0.

Граничные условия задаются областью Г2, в которой проводится моделирование. Область Ü представляет собой прямоугольный параллелепипед размерами А х В х Я. В этой области находится параллелепипед П0 размерами а0 х Ь0 х h0. На границах Г = <ЭП и Г0 = 9i20 заданы следующие условия:

vlrur0 = 0, р|гиг, = Ра-

Дискретизация функции /(г) в области П методом сглаженных частиц (SPH) состоит из двух последовательных аппроксимаций: аппроксимация ядром (3) и аппроксимация частицами (4), в результате которых для вычисления значения функции в некоторой точке заданной области достаточно вычислить взвешенную сумму известных значений.

/(г)« J f{v')W{\v-v'\,h)ck'. (3)

ад

/(г,) « J^/faOWflri-rjU), Ni = {j:\n- (4)

j

Здесь Vj = — объем соседней частицы j. Таким образом, метод SPH позволяет аппроксимировать сплошную среду конечным набором частиц. Сглаживающая функция-ядро W обладает следующими свойствами:

JW(r - г', h)dr' = 1, lim W{г - г', /г) = ¿(г - г').

п

Здесь ö — дельта-функция Дирака, а параметр h называется длиной сглаживания, при этом И7(г - г', Л) = 0 при |г - r'| > kh, где к зависит от функции W, а kh определяет ненулевую область сглаживающей функции, так называемую область поддержки. В работе в качестве ядра используется следующая функция:

иЪЛЩ = к°и ■{}- lR2 + " iH4 ПР" 0 < л < 2, ()

[ и иначе. w

Здесь R = I, к%и в двумерном случае равно ^ в трехмерном gjäjjj,, длина сглаживания равна 2 h [9]. ж

При моделировании слабосжимаемой жидкости методом сглаженных частиц уравнение неразрывности (2) заменяют формулой вычисления плотности частицы г:

je Л'. j

Сила давления, которая входит в уравнение движения, определяется по формуле

где j — соседи частицы г.

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

j e.\'i

Fri.,c =; pV2v т. i>j(v, - v.)Vrir,,. (7)

j

Во второй главе описывается модификация метода сглаженных частиц для моделирования несжимаемых жидкостей, метод PCISPH (Predictive-Corrective Incompressible SPH), особенности его реализации па архитектуре CUDA, а также особенности постановки начальных и обработки граничных условий при использовании CUDA.

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

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

рГг = Рг-Ро (рис. 2).

Авторы метода PCISPH [7| предложили вычислять давление частицы г на каждой итерации алгоритма исходя из отклонения плотности жидкости от ро в данной точке:

Pi = &{Pl - Ро),

где

6 = -1-Р = At2m2-

Р (>:, Vir„ • v Vll i; + £, (VWl3 • vu-;)) p

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

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

На каждой итерации происходит суммирование значения давления: р, =

Pi+Pi- ,

Сила давления вычисляется по формуле (6), используя в качестве давления значение р1} полученное на текущей итерации.

• Начало.

\ J. Получение F: j----—*

maxp. i, iM^ghbori, F, Fwa.

2. Получение у* н x*

шгхр. i*, neighbor«

3. Вычисление ; /n.;U>умости и давлстпп* :

%*, neighbors, р

4. Вычисление сил лаадашя : .

5. Вычислена max.<fW) I $

•-.к'-: KiKv,'....

; 6. ИшъЧрироЬЯтю V H X : 1

Конец ;

Рис. 2: Схема алгоритма PCISPH. Слева от каждого шага показаны массивы, из которых производятся чтение данных, а справа — массивы, в которые производится запись па данном шаге.

Поело получения значений сил производится численное интегрирование уравнений движения методом Эйлера.

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

Хеширование в методе SPH используется для снижения трудоемкости поиска соседей каждой частицы с 0(N2), где N - количество частиц, до 0(с?, Лг), где с,п — среднее количество соседей. Снижение достигается за счет того, что пространство моделирования представляется в виде однородной циклической сетки, при этом каждой частице ставится в соответствие номер ячейки этой сетки.

Значение хеш-функции частицы вычисляется параллельно для каждой частицы и является результатом вычисления выражений:

hash(r) = hzdrd" + h ul: + lf\ ha = rl^JjkHi mod

cell '

где a — перечисление координат x; у; 2, rmin — минимально возможные координаты частицы в данном эксперименте, г, — позиция г-й частицы, cell — размер ячейки, d — вектор, содержащий размерности хеш-таблицы,'причем каждый его компонент <Р равен некоторой степени 2. Оператор mod — остаток от целочисленного деления номера ячейки на количество ячеек по пространственной оси а.

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

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

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

Параграф 2.3 посвящен реализации начальных и граничных условий моделирования жидкости на CUDA.

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

При формировании начальных условий необходимо, чтобы плотность жидкости, представленная в виде сетки, была равна р0. Для этого установим соотношение между длиной сглаживания h, радиусом частицы г и промежутком между частицами s. Установив соотношение h = 1,15s для получения оптимального количества соседей (в трехмерном случае, 56) частицы, составим отношение между h и г, раскрыв SPH-анпроксимацию функции плотности:

V(r) (6WLiu(s, 1.15s) + 12WIAu{V2s, 1.15s) + 1.15s)+

+6Wun(2s, 1.15s) + 24WLiu{V5s, 1.15s)) = 1,

(8)

В результате получим h « 1,728179г.

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

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

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

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

Для каждой частицы в отдельном С1ГОА-ядре необходимо создать виртуальную частицу, если плоскость границы пересекает область сглаживания частицы, то есть расстояние от реальной частицы до границы г < кк, где к — длина сглаживания. Созданную частицу помещаем но адресу Л' + г, где г — индекс обрабатываемой реальной частицы. Если г > кк, то в ячейку Л' + г запишем частицу с позицией, которая выходит за пределы эксперимента. Таким образом, несуществующая частица будет отброшена на этане хеширования.

При создании г-й частицы сначала перебираются все плоскости препятствий, для которых г < кк. Расстояние от частицы до плоскости находим по формуле гр1ат = п ■ х т Д, затем уточняется, попадает ли частица в прямоугольную область границы по формулам:

Если неравенства (10) и (11) выполняются, то частица попадает в область, и для нее необходимо создать виртуальные частицы. Позиция виртуальной частицы «за плоскостью» вычисляется как

а скорость vt, = — V; для условия нескольжения.

В третьей главе описаны три способа визуализации течения жидкостей:

1. Метод сглаженных частиц.

2. Метод движущихся тетраэдров.

3. Метод движущихся кубов на основе октодеревьев.

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

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

(9) (10) (П)

х„ = х,- — 2г • п,

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

Параграф 3.2 посвящен извлечению изоповерхности с помощью геометрических шейдеров методом движущихся тетраэдров (Marching Tetrahedra).

Алгоритм визуализации состоит из двух частей: создание скалярного поля из массива частиц и создание аппроксимации поверхности по скалярному полю.

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

Параграф 3.3 описывает визуализацию скалярного поля на основе ок-тодеревьев с помощью CUDA. Визуализация скалярного поля в данном разделе проводится в два этапа: создание восьмеричного дерева (октодерева) и построение на его основе изоповерхности методом движущихся кубов. Классическим способом использования восьмеричных деревьев па графическом процессоре является создание их на центральном процессоре последовательным образом и копирование его представления на графический процессор для последующей визуализации. В нашем случае дерево создается с помощью параллельного алгоритма полностью на GPU, центральный процессор занимается лишь управлением памятью. Для создания изоповерхности вершины узлов-ячеек октодерева помечаются как внешние либо как внутренние, создавая таким образом границу, по которой проходит изоноверхность.

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

1. Расчет ограничивающего параллелепипеда.

2. Создание ключей узлов дерева и их сортировка.

3. Поиск и подсчет уникальных ключей.

4. Расчет адресов узлов октодерева.

5. Создание массивов узлов на уровне листьев и ниже.

6. Поиск соседей для каждого узла.

7. Создание вершин и ребер для узлов дерева.

Затем происходит извлечение изоповерхности из октодерева. Для отображения изоповерхности необходимо создать вершинный буфер и буфер индексов. Создание каждого буфера разделяется на два этапа анал огично созданию массивов элементов октодерева — подсчет адресов элементов и заполнение буферов. При создании вершинного буфера производится линейная интерполяция между координатами вершин узлов октодерева по изозначению.

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

В качестве двумерных экспериментов были взяты плоское течение Ку-этта и моделирование обрушения столба жидкости на плоскости. Сравнение реализации с теоретическими расчетами для течения Куэтта показало, что погрешность вычисления скорости не превышает 0,5%. При моделировании обрушения столба жидкости погрешность не превышает 4% с учетом погрешности при измерении времени в исходном эксперименте.

Двумерный метод PCISPH был реализован на центральном и графическом процессорах для сравнения производительности и для удобства отладки на CPU. Замеры времени выполнения одного шага моделирования показали, что с увеличением количества частиц реализация алгоритма на CPU становится более эффективной, чем реализация на CPU. При использовании 13897 частиц реализация на графическом процессоре требует в среднем 0,756 мкс для обработки одной частицы, что в 103 раза быстрее, чем одноиоточная реализация на центральном процессоре.

При уменьшении размера частиц увеличивается точность моделирования, но также увеличивается число требуемых итераций для корректного вычисления силы давления. При радиусе частицы 0,15 м в случае ударов время выполнения одного шага моделирования на CPU составляет 1200-1594 мс, а на GPU — до 15 -25 мс.

Рис. 3: Сравнение результатов моделирования с экспериментом (датчики высоты HI и Н4)

Апробация реализации трехмерного метода сглаженных частиц произведена с помощью моделирования эксперимента обрушения столба жидкости в пространстве. Изначально данный эксперимент был проведен в Морском Исследовательском Институте Нидерландов (Maritime Research Institute Netherlands, MARIN). Этот эксперимент можно рассматривать как упрощенную модель течения воды по палубе корабля. Вода может нанести серьезные повреждения кораблю, грузу и персоналу, поэтому важно расчитывать характер ее движения и силу воздействия воды на груз. В эксперименте датчики считывают высоту воды в 4 точках (рис. 1). Сравнение экспериментальных значений высот жидкости с результатами моделирования (рис. 3 и 4) показывает, что характер всплесков жидкости о препятствие и стенки совпадает, но данные моделирования отстают но времени от экспериментальных примерно

Рис. 4: Сравнение результатов моделирования с экспериментом (датчики высоты Н2 и НЗ)

на 9%, что может быть связано с потерей энергии при сжатии жидкости либо из-за неточности интегрирования.

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

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

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

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

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

1. Зубов А.Д., Лебедев A.M. Метод сглаженных частиц SPH для расчетов газодинамических задач со сферической и цилиндрической симметриями // Вопросы атомной науки и техники. Серия: Математическое моделирование физических процессов. 2009. Вып. 1. С. 19-28.

2. Моделирование высокоскоростного соударения методом гладких частиц / Блажевич Ю.В.. Иванов В.Д.. Петров И.Б. [и др.] // Матем. моделирование. 1999. Т. 11, .№1. С. 88-100.

3. Хвостова O.E., Куркин A.A. Математическое моделирование оползневых цунами методом частиц // Вестник БГТУ им. В.Г. Шухова. 2009. №4. С. 96-100.

4. Lee E.-S., Violeau D., Issa R., Ploix S. Application of weakly compressible and truly incompressible SPH to 3-D water collapse in waterworks // Journal of Hydraulic Research. 2010. Vol. 48 Extra Issue. P. 50-60.

5. Monaghan J. Smoothed Particle Hydrodynamics // Annu. Rev. Astron. Astrophys. 1992. Vol. 30. P. 543-574.

G. Monaghan J. Simulating Free Surface Flows with SPH // Journal of Computational Physics. 1994. Vol. 110. P. 399-406.

7. Solenthaler В., Pajarola R. Predictive-Corrective Incompressible SPH // SIGGRAPH'09: ACM SIGGRAPH 2009 papers. New York, 2009. P. 1-6.

8. Liu G., Liu M. Smoothed Particle Hydrodynamics: A Meshfree Particle Method. Singapore: World Scientific, 2003. 473 p.

9. Liu M., Liu G. Smoothed Particle Hydrodynamics (SPH): an Overview and Recent Developments / / Archives of computational methods in engineering. Vol. 17(1). 2010. P. 25-76.

Публикации автора по теме диссертации

В научных журналах, рекомендованных ВАК:

1. Суравикин Л.Ю.; Коробицын В.В. Построение изоповерхпости па основе октодеревьев для визуализации потока жидкости /7 Вестник Омского университета. 2010. Выи. i. С. 164-167.

2. Суравикин А.Ю. Реализация метода SPH на CUDA для моделирования несжимаемых жидкостей /7 Наука и образование: электронное научно-техническое издание. 2012. WJ [Электронный ресурс]. URL: http://technomag.edu.ru/doc/423582.litml (дата обращения: 12.08.2012).

В других изданиях:

3. Суравикин А.Ю. Алгоритм визуализации потоков жидкости па современных графических процессорах // Информационные технологии и автоматизация управления: матер, межвуз. науч.-практ. конф. ОмГТУ, 20-24 апреля 2009 г. Омск: Изд-во ОмГТУ, 2009. С. 78-80.

4. Суравикин А.Ю., Коробицын В.В. Визуализация скалярного поля на основе динамического построения изоповерхпости /'/ Математические структуры и моделирование. Омск, 2009. Вып. 20. С. 121-133.

5. Суравикин. А.Ю. Использование технологий GPGPU для решения задачи SAXPY /7 Материалы XLVIII Международной научной студенческой конференции «Студент и технический прогресс»: Информационные технологии. Новосибирск: Новосиб. гос. ун-т, 2010. С. 302.

6. Суравикин А.Ю. Формирование модели изоповерхпости но скалярному полю /7 Проблемы обработки и защиты информации. Книга 2. Анализ графической и текстовой информации. Омск: ООО «Полиграфический центр КАН», 2010. С. 94-113.

7. Suravikin A.Y. Korobitsin V.V. Octree-based generation of fluid stream surface // Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления. Труды Международной конференции «Numerical geometry, grid generation and high performance computing (NUMGRID2010)». ВЦ им. A.A. Дородницына РАН, 11-13 октября 2010 г. Москва. 2010. С. 33-40.

8. Суравикин А.Ю. Коробицын В.В. Оценка производительности связывания CUDA с графическими API па примере задачи SAXPY // Математические структуры и моделирование. Омск, 2010. Выи. 21. С. 96-103.

9. Суравикин А.Ю. Система моделирования несжимаемой жидкости: за-явл. 07.02.2012; опубл. 26.03.2012. Реестр программ для ЭВМ, регистрационный №2012612960. С. 1.

Подписано в печать 04.12.2012г. Формат 60x84 1\16 Усл. печ. л. 1 Объем 16 стр. Тираж 100 экз. Заказ № 368 Отпечатано ООО «Омега Принт» 630090, г. Новосибирск, пр. Ак.Лаврентьева,6

Введение

1 Обзор метода сглаженных частиц

1.1 Исследование метода сглаженных частиц.

1.2 Основные обозначения.

1.3 Общая постановка задачи.

1.3.1 Уравнение движения.

1.3.2 Начальные и граничные условия.

1.4 Аппроксимация функций методом сглаженных частиц

1.4.1 Аппроксимация ядром производной функции.

1.4.2 Аппроксимация частицами

1.5 Дискретизация уравнений Навье—Стокса.

1.5.1 Вычисление давления.

1.5.2 Вычисление силы вязкости.

1.5.3 Сила поверхностного натяжения.

1.5.4 ХЭРН-коррекция движения частиц.

1.5.5 Численное интегрирование

1.6 Обобщенная схема работы метода сглаженных частиц.

1.7 Выводы к первой главе

2 Параллельная реализация метода сглаженных частиц

2.1 Метод РС1ЭРН.

2.2 Параллельная реализация метода сглаженных частиц с помощью США.

2.2.1 Взаимодействие частиц и хеширование

2.2.2 Вычисление производных величин.

2.2.3 Хранение данных и численное интегрирование.

2.2.4 Получение результатов

2.2.5 Выравнивание памяти и не-соа1еБсес1 доступ.

2.2.6 Об устойчивости метода сглаженных частиц.

2.3 Начальные и граничные условия.

2.3.1 Расположение частиц при инициализации.

2.3.2 Виртуальные частицы . . . .'.

2.3.3 Расчет столкновений частицы с твердой границей

2.3.4 Создание виртуальных частиц на графическом процессоре

2.4 Выводы ко второй главе.

3 Алгоритмы визуализации

3.1 Создание изображения жидкости в экранном пространстве

3.1.1 Рендер сфер.

3.1.2 Сглаживание карты глубины.

3.1.3 Расчет нормалей.

3.1.4 Расчет освещения.

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

3.2 Генерация изоповерхности с помощью геометрических шейдеров

3.2.1 Настройка по адресам (8иагг1^).

3.2.2 Изоповерхность.

3.2.3 Инициализация.

3.2.4 Вершинный шейдер

3.2.5 Геометрический шейдер.

3.2.6 Результаты моделирования.

3.3 Визуализация скалярного поля на основе октодеревьев с помощью CUDA.

3.3.1 Описание алгоритма и соглашения.

3.3.2 Построение октодерева.

3.3.3 Извлечение изоповерхности из октодерева.

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

3.4 Выводы к третьей главе.

4 Применение инструмента для моделирования

4.1 Примеры решений задач на плоскости.

4.1.1 Плоское течение Пуазейля.

4.1.2 Плоское течение Куэтта.

4.1.3 Обрушение столба жидкости на плоскости

4.2 Моделирование эксперимента в пространстве.

4.2.1 Эксперимент с обрушением столба жидкости.

4.3 Выводы к четвертой главе.

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

Для решения задач подобного типа применяется математическое моделирование с использованием компьютерной техники, которая ускоряет расчеты (персональные компьютеры, кластеры, суперкомпьютеры). В начале 2000-х годов появилась возможность программировать графические процессоры, которые быстро развивались и достигли уровня, когда их стало возможным использовать для решения трудоемких вычислительных задач за счет массивной параллельности, то есть большого количества потоковых процессоров. Наша работа посвящена созданию параллельного алгоритма и его реализации на графических процессорах с помощью технологии С1ША.

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

Основные задачи работы:

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

2. Разработать метод визуализации жидкости, обеспечивающий возможность расчета с учетом прозрачности изображения жидкости, смоделированной методом частиц.

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

Научная новизна.

1. Впервые предложена реализация метода PCISPH на CUDA с полной процедурой вычислений на GPU.

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

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

4. Предложен новый алгоритм формирования изоповерхности облака частиц на основе октодеревьев.

Научно-практическая значимость работы.

1. Реализованная программа моделирования движения жидкости обеспечивает ускорение процесса исследования течений жидкости за счет применения GPU в расчетах.

2. Представлен ряд параллельных алгоритмов для моделирования движения жидкости с реализацией на GPU.

3. Реализованные алгоритмы используются в качестве учебного материала при обучении студентов ОмГУ специальности 230101 по дисциплине «Архитектура и программирование вычислительных систем».

Апробация работы. Основные положения диссертации были изложены в виде докладов на Межвузовской научно-практической конференции «Информационные технологии и автоматизация управления» (Омск, 2009); XLVIII Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2010); Международной конференции «Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления» (Москва, 2010).

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

Основные положения, выносимые на защиту:

1. Реализация алгоритма SPH на графическом процессоре позволяет увеличить производительность вычислений в 73-103 раза по сравнению с центральным процессором.

2. В двумерном случае для течений с низкими числами Рейнольдса при использовании метода SPH абсолютная погрешность не превышает 0, 001г. где г — радиус частицы. Относительная погрешность не превышает 0,5%. В двумерных задачах с обрушением столба жидкости погрешность не превышает 4% с учетом погрешности измерения времени в реальном эксперименте. В трехмерном случае погрешность метода ЭРН не превышает 9% в задачах с обрушением столба жидкости.

3. Размещение частиц жидкости для начальных и граничных условий в виде однородной сетки с шагом 5 = 1.15/г при Н ~ 1, 728179г позволяет получить требуемую плотность жидкости.

Работа соответствует специальности 05.13.18 — Математическое моделирование, численные методы и комплексы программ, поскольку (в скобках указаны пункты паспорта специальности):

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

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

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

Личный вклад автора. Все выносимые на защиту результаты получены автором лично.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и 2 приложений. Общий объем диссертации составляет 135 страниц. Библиографический список насчитывает 94 наименования.

4.3 Выводы к четвертой главе

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

1 = 0

Рис. 4.6: Результаты моделирования обрушения столба жидкости на плоскости

1,000

1.000

0.496 0.496 0496

4--.+

0,403

НЗ

0,161

0,744

1 248

К НО

Н1 Н2 НЗ Н4 А,- к I ' Л

1 0,161 ,

Н4

-С -У

I 228

0,550

Рис 4.7. Схема эксперимента обрушения дамбы вид сверху и вид сбоку.

О 176

0,161.

0,176

Р6-Р5*-'

Р8 Р7гК

Л Р4-1—: 0,0205

0,040 рч-ь-—:

0,161 0,040

Р2-Н--:

0,040

Р1+- 0,0205

0,403

Рис 4.8. Схема эксперимента обрушения дамбы тело и датчики давления.

Н1 (эксп ) Н4 (эксп ) -Н1 (мод) - Н4 (мод )

Рис 4.9 Сравнение результатов моделирования с экспериментом (датчики высоты Н1 и Н4)

Рис. 4.10: Сравнение результатов моделирования с экспериментом (датчики высоты Н2 и НЗ)

Заключение

В работе был описан и реализован на СиБА метод сглаженных частиц, который использовался для моделирования несжимаемых жидкостей, описаны 3 способа визуализации жидкости. Основные результаты работы:

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

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

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

1. Афанасьев К.Е. Численное моделирование течений жидкости со свободными границами методами SPH и MPS // Вычислительные технологии. 2006. С. 26-44.

2. Боресков A.B. Основы CUDA Электронный ресурс]. URL: http://steps3d.narod.ru/tutorials/cuda-tutorial.html (дата обращения: 15.06.2012).

3. Боресков A.B. Разработка и отладка шейдеров. СПб.: БХВ-Петербург, 2006. 488 с.

4. Глинских В.Н., Эпов М.И., Лабутин И.Б. Моделирование диаграмм электромагнитного каротажа на графических процессорах // Вычислительные технологии, 2008. Т. 13, № 6.

5. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998. 703 с.

6. Зубов А.Д., Лебедев A.M. Метод сглаженных частиц SPH для расчетов газодинамических задач со сферической и цилиндрической симметриями // Вопросы атомной науки и техники. Серия: Математическое моделирование физических процессов. 2009. Вып. 1. С. 19.

7. Калиткин H.H. Численные методы. СПб.: БХВ-Петербург, 2011. 592 с.

8. Калгин K.B. Реализация алгоритмов с мелкозернистым параллелизмом на графических ускорителях // Сибирский журнал вычислительной математики, 2011. Т.14. С. 59-70.

9. Кнут Д. Искусство программирования. Сортировка и поиск. М.: Вильяме, 2009. Т. 3. 824 с.

10. Курант Р., Фридрихе К., Леви Г. О разностных уравнениях математической физики // УМН. 1941. № 8. С. 125-160.

11. Куркин A.A., Авербух E.JL, Хвостова O.E. Математическое моделирование оползневых процессов методом сглаженных частиц // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток: ДВГУ, 2010. С.53-54.

12. Ландау Л.Д., Лифшиц Е.М. Теоретическая физика: в 10 т. Гидродинамика. М.: Физматлит, 2006. T.VI. 736 с.

13. Минаков А.В. Численное моделирование течений вязкой несжимаемой жидкости с подвижными границами: дис. . канд. физ.-мат. наук. Красноярск, 2008. 190 с.

14. Моделирование фрагментации в жидких средах методом сглаженных частиц (Smoothed Particle Hydrodynamics) / Воробьёв А.П., Кривенцев В.И., Lin Q. и др.] // Известия вузов. Ядерная Энергетика. 2008. №1. С. 85-94.

15. Рубцова В.П. Двумерное численное моделирование процессов физики взрыва и удара методом SPH на основе решения задачи Римана: автореф. дис. . канд. техн. наук. М., 2001. 15 с.

16. Самонов В.Е. Математическое моделирование движения тонкого слоя жидкости под действием поверхностных сил: дис. . канд. физ.-мат. наук. Ставрополь, 2003. 143 с.

17. Сивухин Д.В. Общий курс физики: в 5 т. Электричество. М.: Физматлит, 2004. Т.З. 656 с.

18. Суравикин А.Ю., Коробицын В.В. Визуализация скалярного поля на основе динамического построения изоповерхности // Математические структуры и моделирование. Омск: ООО «УниПак», 2009. Вып. 20. С. 121-133.

19. Суравикин А.Ю. Использование технологий GPGPU для решения задачи SAXPY // Материалы XLVIII Международной научной студенческой конференции «Студент и технический прогресс»: Информационные технологии. Новосибирск: Новосиб. гос. ун-т, 2010. С. 302.

20. Суравикин А.Ю., Коробицын В.В. Оценка производительности связывания CUDA с графическими API на примере задачи SAXPY // Математические структуры и моделирование. Омск: «Омское книжное издательство», 2010. Вып. 21. С. 96-103.

21. Суравикин А.Ю., Коробицын В.В. Построение изоповерхности на основе октодеревьев для визуализации потока жидкости // Вестник Омского университета. 2010. Вып. 4. С. 164-167.

22. Суравикин А.Ю. Система моделирования несжимаемой жидкости: заявл. 07.02.2012; опубл. 26.03.2012. Реестр программ для ЭВМ, регистрационный №2012612960. С. 1.

23. Суравикин А.Ю. Формирование модели изоповерхности по скалярному полю // Проблемы обработки и защиты информации. Книга 2. Анализграфической и текстовой информации. Омск: ООО «Полиграфический центр КАН», 2010. С. 94-113.

24. Тутубалин А. Использование видеокарт для вычислений. Статьи. Электронный ресурс]. URL: http://www.gpgpu.ru/articles (дата обращения: 15.06.2012).

25. Франк A.M. Дискретные модели несжимаемых жидкостей. М.: Физмат-лит, 2001. 224 с.

26. Фролов В. Введение в технологию CUDA // Компьютерная графика и мультимедиа. 2008. Вып №6(1). Электронный ресурс]. URL: http://cgm.computergraphics.ru/issues/issuel6/cuda (дата обращения: 15.06.2012).

27. Фролова Ю.Ф., Коробицын В.В. Моделирование динамики флюидов на графическом процессоре // Математические структуры и моделирование. Омск: ООО «УниПак», 2009. Вып. 20. С. 52-73.

28. AMD Accelerated Parallel Processing (APP) SDK (formerly ATI Stream) Электронный ресурс]. URL: http://developer.amd.com/sdks/AMDAPPSDK/Pages/default.aspx (дата обращения: 15.06.2012).

29. Bajaj С. L., Bernardini F., Xu G. Automatic reconstruction of surfaces and scalar fields from 3d scans // Proceedings of SIGGRAPH'95. 1995. P. 109118.

30. Becker M., Teschner M. Weakly compressible SPH for free surface flows Eurographics/ACM SIGGRAPH Symposium on Computer Animation 2007, P. 1-8.

31. Bergen G. Collision Detection in Interactive 3D Environments. San Francisco: Morgan Kaufmann Publishers. 2004. 298 p.

32. Bourke P. Polygonising a Scalar Field / P. Bourke Электронный ресурс]. URL: http://local.wasp.uwa.edu.au/ pbourke/geometry/polygonise/ (дата обращения: 5.10.2009).

33. Brown P. Lichtenbelt B. ARBgeometryshader4. Электронный ресурс]. URL: http://www.opengl.org/registry/specs/ARB/geometry shader4.txt (дата обращения: 15.06.2012).

34. CUDA С Programming Guide Электронный ресурс]. URL: http://developer.download.nvidia.eom/compute/DevZone/docs/html/C/ doc/CUDACProgrammingGuide.pdf (дата обращения: 15.06.2012).

35. CUDA Toolkit 4.2 CUBLAS Library Электронный ресурс] URL: http://developer.download.nvidia.com/compute/DevZone/docs/html/ CUDALibraries/doc/CUBLASLibrary.pdf (дата обращения: 15.06.2012).

36. Desbrun M., Gascuel M-P. Smoothed Particles: A new paradigm for animating highly deformable bodies // Computer Animation and Simulation. Heidelberg: Springer-Verlag, 1996. P. 61-76.

37. Duvanenko V.J. Parallel In-Place N-bit-Radix Sort — Dr. Dobb's Journal Электронный ресурс]. URL: http://drdobbs.com/high-performance-computing/226600004 (дата обращения: 15.06.2012).

38. Duvanenko V.J. Parallel In-Place Radix Sort Simplified — Dr. Dobb's Journal Электронный ресурс]. URL: http://drdobbs.com/high-performance-computing/229000734 (дата обращения: 15.06.2012).

39. Eberly D.H. Game Physics. San Francisco: Morgan Kaufmann Publishers. 2004. 836 p.

40. Fang J., Parriaux A., Rentschler M. Improved SPH methods for simulating free surface flows of viscous fluids. Applied Numerical Mathematics. Vol. 59. Issue 2, February 2009. P. 251-271.

41. Gingold R., Monaghan J. 1977 Smoothed particle hydrodynamics: theory and application to non-spherical stars Mon. Not. R. Astron. Soc. Vol. 181. P. 375-389.

42. Goddeke D. GPGPU-Basic Math Tutorial Электронный ресурс]. URL: http://www.mathematik.uni-dortmund.de/goeddeke/gpgpu/tutorial.html (15.06.2012).

43. Golub G.H., Van Loan C.F. Matrix Computations, 3rd edition. London: The Johns Hopkins University Press. 1996. 694 p.

44. GPGPU Электронный ресурс]. URL: http://en.wikipedia.org/wiki/GPGPU (дата обращения: 15.06.2012).

45. GPU gems 3 / eds. H. Nguyen. 2008. Электронный ресурс]. URL: http://developer.nvidia.com/content/gpu-gems-3 (15.06.2012).

46. Harris M., CUDA Fluid Simulation in NVIDIA PhysX // SIGGRAPH Asia 2008. Электронный ресурс]. URL: http://sa08.idav.ucdavis.edu/CUDAphysxfluids.Harris.pdf (дата обращения: 15.06.2012).

47. Harris M., Goddeke D. General-Purpose Computation on Graphics Hardware. Электронный ресурс]. URL: http://gpgpu.org (дата обращения: 15.06.2012).

48. Hart E. NVIDIA OpenGL SDK Guide Электронный ресурс]. URL: http://developer.download.nvidia.com/SDK/10.5/opengl/OpenGL SDKGuide.pdf (дата обращения: 15.06.2012).

49. Helluy P. A Portable Implementation of the Radix Sort Algorithm in OpenCL. 2011. Электронный ресурс]. URL: http://hal.archives-ouvertes.fr/docs/00/59/67/30/PDF/ocl-radix-sort.pdf (дата обращения: 15.06.2012).

50. Hickey R. Callbacks in С++ Using Template Functors. 1994. Электронный ресурс]. URL: http://www.tutok.sk/fastgl/callback.html (дата обращения: 15.06.2012).

51. Hoberock J., Bell N. Thrust: С++ Template Library for CUDA. 2010. Электронный ресурс]. URL: http://code.google.eom/p/thrust/ (дата обращения: 15.06.2012).

52. Hoberock J., Bell N. Thrust library usage examples. 2010. URL: http: //thrust.googlecode.com/files/examples-vl.2.zip (дата обращения: 15.06.2012).

53. Kilgard M.J., Biermann R., Cornish D. ARBpixelbufferobject. Электронный ресурс] URL: http://www.opengl.org/registry/specs/ARB/pixelbufferobject.txt (дата обращения: 15.06.2012).

54. Kipfer P., Westermann R. Improved GPU Sorting // GPU Gems 2: Programming Techniques for High-Performance Graphics and GeneralPurpose Computation. Taunton: Addison—Wesley, 2005. P. 733-746.

55. Lee E.-S., Moulinec C., Xu R. и др. Comparisons of weakly compressible and truly incompressible algorithms for the SPH mesh free particle method // Journal of Computational Physics. Vol. 227. 2008. P. 8417-8436.

56. Liu G., Liu M. Smoothed Particle Hydrodynamics: A Meshfree Particle Method. Singapore: World Scientific. 2003. 473 p.

57. Liu M., Liu G. Smoothed Particle Hydrodynamics (SPH): an Overview and Recent Developments // Archives of computational methods in engineering, Vol. 17(1). 2010. P. 25-76.

58. Lorensen W., Cline H. Marching cubes: a high resolution 3D surface construction algorithm // Computer Graphics. 1987. Vol. 21, N. 4. P. 163— 169.

59. Lucy L. A numerical approach to the testing of the fission hypothesis Astron. J. 1977. Vol. 82. P. 1013-1024.

60. Martin J.C., Moyce W.J. Part IV. Collapse of Free Liquid Columns on a Rigid Horizontal Plane // Philosophical Transactions of the Royal Society of London. 1952. Vol. 244. P. 312-324.

61. Monaghan J.J. An introduction to SPH. Comput. Phys. Comm. 1988. Vol. 48. P. 89-96.

62. Monaghan J.J. Smoothed Particle Hydrodynamics. Annu. Rev. Astron. Astrophys. 1992. Vol. 30. P. 543-574.

63. Monaghan J.J. Simulating Free Surface Flows with SPH. Journal of Computational Physics. 1994. Vol. 110. P. 399-406.

64. Monaghan J.J. Smoothed particle hydrodynamics. Reports on Progress in Physics. 2005. Vol. 68. P. 1703-1759.

65. Morris J., Fox P., Zhu Y. Modeling Low Reynolds Number Incompressible Flows Using SPH // Journal of Computational Physics. 1997. Vol. 136(1). P. 214-226.

66. Miiller M., Charypar D., Gross M. Particle-Based Fluid Simulation for Interactive Applications / Proceedings of 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2003. P. 154-159.

67. Newman T.S. A survey of the marching cubes algorithm // Computers & Graphics. 2006. Vol. 30, N. 5. P. 854-879.

68. OpenCL Электронный ресурс]. URL: http://developer.nvidia.com/opencl (дата обращения: 15.06.2012).

69. Paris S., Kornprobst P., Tumblin J., Durand F. Bilateral Filtering: Theory and Applications // Foundations and Trends in Computer Graphics and Vision. 2008. Vol. 4, N. 1. P. 1-78.

70. Pawasauskas J. Volume Visualization With Ray Casting // CS563 — Advanced Topics in Computer Graphics (1997). Электронный ресурс]. URL: http: / / web.cs. wpi .edu / matt / courses / cs563/ talks / powwie/pi / ray-cast.htm (дата обращения: 15.06.2012).

71. Persson E. 3D. Электронный ресурс]. URL: http://www.humus.name/index.php?page=3D (дата обращения: 15.06.2012).

72. Platinga S. Certified Algorithms for Implicit Surfaces. Электронный ресурс] . URL: http://cs.nyu.edu/exact/pap/mesh/vegter/platingaThesis.pdf (дата обращения: 15.06.2012).

73. Satish N., Harris M., Garland M. Designing Efficient Sorting Algorithms for Manycore GPUs // Proceedings of IEEE International Parallel and Distributed Processing Symposium 2009 (IPDPS 2009). P. 1-10.

74. Segal M., Akeley K. The OpenGL Graphics System: A Specification (Version 3.2) Электронный ресурс]. URL: http://www.opengl.org/registry/doc/glspec32. core. 20091207.pdf (дата обращения: 15.06.2012).

75. Solenthaler В., Pajarola R. Predictive-Corrective Incompressible SPH / SIGGRAPH'09: ACM SIGGRAPH 2009 papers. New York. 2009. P. 1-6.

76. The Khronos Group Электронный ресурс]. URL: http://www.khronos.org/ (дата обращения: 15.06.2012).

77. Weinert К., Surmann Т., Mehnen J. Parallel surface reconstruction // Proceedings of the 5th European Conference on Genetic Programming. 2002. P. 93-102.

78. Wilhelms J., Gelder A.V. Octrees for faster isosurface generation // ACM Trans. Graph. 1992. Vol. 11, N. 3. P. 201-227.

79. Yildiz M., Rook R., Suleman A. SPH with the multiple boundary tangent method // International Journal for Numerical Methods in Engineering:

80. Электронный журнал. 2008. Vol. 77. P. 1416-1438. Электронный ресурс. URL: http://dx.doi.org/10.1002/nme.2458 (дата обращения: 15.06.2012).

81. Zhang М. Simulation of surface tension in 2D and 3D with smoothed particle hydrodynamics method // Journal of Computational Physics. Vol. 229. 2010. P. 7238-7259.

82. Highly Parallel Surface Reconstruction / Zhou K., Gong M. Huang X. и др.]. 2008. [Электронный ресурс]. URL: http://www.kunzhou.net/2008/MSR-TR-2008-53.pdf (дата обращения: 15.06.2012).