Исследование алгоритмов моделирования и визуализации жидких и газообразных сред

 Каждое поле скоростей можно разложить на сумму несжимаемого поля (поля, сохраняющего массу) и градиентного поля.

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

Не вдаваясь в детали, можно сказать, что решение этой проблемы связано с решением линейной системы уравнений, называемой уравнение Пуассона. Эта система разряжена, поэтому можно использовать метод Гаусса-Зейделя для ее решения.

4.4.7 Выводы

В [12] описана реализация предложенного метода  для современных ЦПУ и для процессоров, в которых отсутствует АЛУ для вычислений с плавающей точкой. Данный метод быстро доказал свою состоятельность, получив практическое распространение в таких программных продуктах как Maya и 3dMax, в компьютерных играх и других приложениях. Вслед за [12], активизировались исследования в этой области, многие из которых взяли за основу изложенный подход.

4.5 Моделирование системой частиц

В статье [20] был впервые представлен метод для моделирования таких природных феноменов, как облака, вода, дым, огонь и др., используя системы частиц. От привычных методов представления данных при синтезе изображений система частиц отличается по трем причинам. Во-первых, объект представляется не набором примитивов, таких как полигоны или патчи (параметрически заданные поверхности), которые определяют границу поверхности, а как некоторое облако простых частиц, которые определяют его объем. Во-вторых, система частиц – это нестатичная сущность: частицы двигаются во времени, изменяют свою форму, «рождаются» новые частицы, а старые «умирают». В-третьих, объект, представленный системой частиц, недетерминированный, т.е. его форма не фиксирована, неопределенна до конца. Случайные процессы, происходящие вокруг, могут изменять эту форму и тем самым влиять на внешний вид объекта. Примеры: дым, огонь.

При моделировании таких феноменов система частиц имеет ряд преимуществ перед классическими, ориентированными на использование поверхностей, техниками. Во-первых, частица (пока будем представлять ее, как просто точку в трехмерном пространстве) гораздо более простой примитив, чем полигон. Система частиц – это самая простая форма представления поверхности. Эта простота выливается в экономию вычислительного времени, и потому можно обрабатывать большую базу примитивов и получать более детальные изображения при синтезе. Так как частица очень проста, то легко моделировать такие эффекты, как размытие при движении (motion blur) быстро движущихся объектов для удаления временного алиасинга. Второе преимущество заключается в том, что определение модели процедурное и может контролироваться генерацией случайных чисел (можно использовать тот же шум Перлина).  Таким образом, получить высоко детализованную модель не требует затрат человеческого времени на дизайн. В этом плане такой подход существенно выигрывает по сравнению с системами, где моделируются поверхности. По этой же причине она может адаптивно менять уровень детализации, чтобы наиболее успешно балансировать производительность и качество, в зависимости от набора текущих параметров. Это чем-то похоже на фракталы, когда приближаясь к системе частиц, мы можем добавлять больше деталей. Еще одним достоинством системы частиц является то, что она позволяет моделировать «живые» объекты, которые изменяются во времени. Такую сложную динамику объекты состоящие из поверхностей моделировать не позволяют.

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

4.5.1 Схема работы системы частиц

 

 

 

 

 

 

 

 

 

 

 

Обзор моделирования системой частич

Визуализация объемных данных

Tекстурами

Ray-tracing

Системой частич

Выводы

Историческая эволюция в этой области породила богатое наследие. Даже самые простые методы, которые использовали шумовые функции, тем не менее, на практике были успешно использованы в крупных коммерчески успешных проектах, чем и зарекомендовали себя как полезный инструмент. С появлением шумовой функции Перлина стал возможен синтез сложных детализированных текстур. Дальнейшее развитие естественным образом приводит нас к физическому моделированию (пусть и упрощенному) как к средству достижения большего реализма. Оба подхода Лагранжа и Эйлера обладают своими сильными и слабыми сторонами. Метод Эйлера позволяет построить решение уравнений Навье-Стокса, но ограничен неким объемом в пространстве. Кроме того как любой сеточный метод ему присущи артефакты дискретизации. Метод Лагранжа с другой стороны этими недостатками не обладает, но с помощью него очень сложно считать частные производные, необходимые для решения уравнений. В моей работе я предлагаю использовать комбинацию сеточного решения уравнения гидродинамики, систему частиц для визуализации и шумовые функции для предания большей детализированности.

 

Исследование и построение решения задачи

Математическая модель

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

Уравнения Навье-Стокса

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

	D/D – Производная Лагранжа
	Рассмотрим, какие силы действуют на наши частицы
	Во-первых, в системе присутствует гравитация, т.е. на частицу действует сила тяжести. Во-вторых, области высокого давления давят на области с низким давлением. Нас интересует общая сила, действующая на частицу, потому что, например, если давление по всем направлениям одинаково, то общая сила будет равна 0. На самом деле, важны только те ситуации, когда с одной стороны частицы давление больше, чем с другой. В этом случае частица начинает двигаться в сторону, где давление ниже. Т.е. нас интересует изменение силы, которое проще всего посчитать, взяв отрицательный градиент давления. Также необходимо проинтегрировать по всему объему, что проще всего сделать домножив все выражение на V. В-третьих, возникает еще одна сила из-за вязкости нашей жидкости. Вязкие жидкости пытаются противостоять деформации. Эту силу можно рассматривать как некоторую силу, которая пытается заставить частицу двигаться со средней скоростью окружающего потока, т.е. она пытается минимизировать разницу в скорости между частицой и близлежащими к ней частицами. Дифференциальный оператор, который вычисляет как далеки значения в некоторой области – это лапласиан.  Вот откуда появляется третье слагаемое в нашем уравнении. Далее нам также необходимо проинтегрировать по всему объему и домножить на µ – динамический коэффцифиент вязкого трения.
	Разделим обе части уравнения на V.
	И затем разделим на плотность ρ.

 

 

 

В данной системе принимают участие следующие величины:

V — вектор скорости,

t — время,

µ — коэффициент кинематической вязкости, ρ — плотность,

P — давление,

 f — вектор плотности массовых сил,

 l — характерный размер

Re - число Рейнольдса — безразмерное соотношение, которое определяет стабильность системы

Если рассмотреть одномерный случай, то не сложно убедиться на сколько Re важный параметр:

- в предельном случае, когда  отсутствует диффузия (μ=0), то изменение  скорости по полю скоростей  можно условно изобразить как  показано на рисунке

Уравнение вырождается в …

Как видно из графиков, процесс симуляции быстро ломается.

- в другом придельном случае, когда мы рассматриваем только  диффузию и уравнение вырождается  в …

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

 

Метод Лагранжа

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

Метод Эйлера

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

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

Граничные условия

Замкнутый куб

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

Периодические

Быстрое преобразование Фурье.

Произвольные

Вокселизация

Описание практической части

Схема работы программного решения

CUDA реализация алгоритмов

CUDA

CUDA представляет собой программно-аппаратный стек, позволяющий рассматривать видеокарты серии Nvidia 8xxx и старше, как сопроцессор к основному процессору (device).

Рис.1 Архитектура современной видеокарты.

 

Архитектура современной видеокарты устроена, как показано на рисунке 1. В ней можно выделить крупный блок, который называется TPC (Texture Processor Cluster). Условно можно считать, что разные видеокарточки отличаются друг от друга только количеством TPC. TPC состоит из двух крупных модулей – SM (Streaming Multiprocessor). В каждом SM-модуле 8 вычислительных процессоров – SP (Streaming Processor), которые умеют выполнять простые арифметические инструкции (MAD, MUL, MOV и т.д.), и один SFU (Special Function Unit), который умеет вычислять сложные функции (SIN, COS, EXP, LOG и др.).

Все потоки группируются по 32 потокав так называемые. Внутри warp'а потоки работают в режиме SIMD, но разные warp'ы могут исполнять разные инструкции. Поэтому GPU нельзя охарактеризовать, как классическую SIMD-ахитектуру. Warp'ы могут группироваться на более высоком уровне в блоки для того, чтобы использовать общую разделяемую память и иметь возможность синхронизоваться.

Традиционно сложилось, что GPU используют арифметику с плавающей точкой и поддерживают float32 IEEE стандарт вычислений. В дальнейшем ожидается появление поддержки вычислений double-арифметики, что существенно расширит класс задач, для которых CUDA применима.

С точки зрения программиста CUDA – это расширение синтаксиса языка C. Специальными служебными словами помечаются функции:

• функция вызывается и исполняется на CPU - __host__,
• функция вызывается на CPU, исполняется на GPU - __global__,
• функция вызывается и исполняется на GPU - __device__.

Для переменных действует схожее правило.

CUDA-программы компилируются специальным компилятором nvcc, который разделяет код на GPU и CPU составляющие. CPU код передается стандартному компилятору (gcc, IntelC и др.), а GPU код обрабатывается дальше.

 

Заключение 

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

[1] W. T. Reeves. Particle Systems. A Technique for Modeling a Class of Fuzzy Objects.

ACM Computer Graphics (SIGGRAPH’83), 17(3):359–376, July 1983.

 

[2] M. Shinya and A. Fournier. “Stochastic Motion - Motion Under the Influence of Wind”.

In Proceedings of Eurographics ‘92, pages 119–128, September 1992.

 

[3] K. Sims. “Particle Animation and Rendering Using Data Parallel Computation”.

ACM Computer Graphics (SIGGRAPH ’90), 24(4):405–413, August 1990.

 

[4] J. Wejchert and D. Haumann. “Animation Aerodynamics”.

ACM Computer Graphics (SIGGRAPH ’91), 25(4):19–22, July 1991.

 

[5] D. Ebert, K. Musgrave, D. Peachy, K. Perlin, and S. Worley.

“Texturing and Modeling: A Procedural Approach”. AP Professional, 1994.

 

[6] L. Yaeger and C. Upson. “Combining Physical and Visual Simulation. Creation of the Planet Jupiter for the Film 2010”. ACM Computer Graphics (SIGGRAPH ’86), 20(4):85–93, August 1986.

 

[7] M. Kass and G. Miller. Rapid, “Stable Fluid Dynamics for Computer Graphics”.

ACM Computer Graphics (SIGGRAPH’90), 24(4):49–57, August 1990.

 

[8] Cassidy J. Curtis Sean E. Anderson Joshua E. Seims Kurt W. Fleischery David H. Salesin “Computer-Generated Watercolor”

ACM Computer Graphics (SIGGRAPH’1997)

 

[9] J. Stam, "Stable Fluids",

ACM Computer Graphics SIGGRAPH'99 Conference Proceedings, Annual Conference Series, 121-128

 

 [10] J. Stam, "A Simple Fluid Solver based on the FFT",

Journal of Graphics Tools, Volume 6, Number 2, 2001, 43-52

 

[11] Selle, A., R. Fedkiw, B. Kim, Y. Liu, and J. Rossignac. 2007. "An Unconditionally Stable MacCormack Method." Journal of Scientific Computing

 

[12] J. Stam, "Real-Time Fluid Dynamics for Games".

Proceedings of the Game Developer Conference, March 2003

 

[13] K. Crane, I. Llamas, S. Tariq ”Real-Time Simulation and Rendering of 3D Fluids”,

GPUGems 3, Addison-Wesley, 2007

 

[14] K. Perlin, “Improving Noise”, ACM Computer Graphics Siggraph 2002

 

[15] K. Perlin. 1985. “An Image Synthesizer”.

In Computer Graphics (Proceedings of ACM SIGGRAPH 85), 24. 3

 

[16] K. Perlin, “Making Noise”,

Proceedings of the Game Developer Conference, 1999

 

[17] K. Perlin., ACM SIGGRAPH’84 conference, course in "Advanced Image Synthesis."

 

[18] S. Green, “Implementing Improved Perlin Noise”, GPU GEMS 2, Ch26, Addison-Wesley, 2005

[19] Wei Li, Zhe Fan, Xiaoming Wei, Arie Kaufman “Flow Simulation with Complex Boundaries”, GPU GEMS 2, Ch47, Addison-Wesley, 2005

[20] William T. Reeves Lucasfilm Ltd “Particle Systems—a Technique for Modeling a Class of Fuzzy Objects” ACM Computer Graphics Siggraph 1983 Volume 2 ,  Issue 2  (April 1983) Pages: 91 - 108