Исследование алгоритмов моделирования и визуализации жидких и газообразных сред
Изучение проблемы визуализации жидких сред в компьютерной графике. Применение уравнений Навье-Стокса для задач нефотореалистичного рендеринга. Математическое моделирование поверхности бумаги. Использование метода Лагранжа для дискретной системы частиц.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 14.11.2014 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://allbest.ru
Содержание
Введение
1. Обзор существующих решений рассматриваемой задачи или ее модификаций
1.1 Шум Перлина
1.1.1 История появления
1.1.2 Алгоритм
1.1.3 Применение
1.2 Применение уравнений Навье-Стокса для задач нефотореалистичного рендеринга
1.2.1 Алгоритм
1.2.2 Моделирование поверхности бумаги
1.2.3 Математическая модель
1.3 Интерактивное моделирование дыма
1.3.1 Математическая модель
1.3.2 Движение плотностей
1.3.3 Наличие источников плотности
1.3.4 Диффузия
1.3.5 Движение плотности по полю скоростей
1.3.6 Решение уравнения для скоростей
2. Моделирование системой частиц
2.1 Схема работы системы частиц. Визуализация объемных данных текстурами и Ray-tracing
3. Исследование и построение решения задачи
3.1 Математическая модель
3.1.1 Уравнения Навье-Стокса
3.1.2 Метод Лагранжа
3.1.3 Метод Эйлера
3.1.4 Граничные условия
4. Схема работы программного решения. CUDA реализация алгоритмов
Список литературы
Введение
В настоящее время одна из наиболее интригующих проблем в компьютерной графике - это моделирование жидких и газообразных сред. Во многих областях потребность в инструменте подобного рода очень высока. В киноиндустрии необходимо убедительно мимикрировать (подражать) внешнему виду и поведению таких сред как: дым, вода и огонь.
Программное обеспечение, используемое художниками и дизайнерами, также может выиграть от использования физического моделирования для имитации традиционных техник, как рисование акварелью или маслеными красками.
Еще одно потенциальное приложение - это синтез текстур, так как многие текстуры получаются в результате воздействия жидкостей на какую-либо поверхность, например, таким образом можно получить эрозию.
В последнее время подобное моделирование получило широкое распространение и в геофизике, в частности, при моделировании предсказания погоды. И, конечно, моделирование жидких сред важно для различных инженерно прикладных задач. Во многих инженерных пакетах программного обеспечения существуют готовые решения для гидродинамических симуляций.
Распространенное мнение в научном сообществе, что уравнение Навье-Стокса хороши для моделирования движения жидкостей. Это подтверждают большое количество научных работ, учебников и статей, публикующихся в разных областях, но которые, тем не менее, используют численное решение уравнения Навье-Стокса как основу моделирования.
Какой численный метод использовать на практике зависит во много от задачи и доступных вычислительных мощностей.
Большинство инженерных задач требуют от симуляции точных значений различных физических величин, на основе которых принимаются решения о надежности, производительности и т.д.
Визуальное представление решения («форма» потока) обычно вторичной важности в таких приложениях.
С другой стороны в компьютерной графике наибольший интерес вызывают именно «форма» и поведение среды, а физическая точность вторична, а во многих случаях вообще не важна.
В идеале необходимо предоставить пользователю набор интерактивных инструментов, который бы позволил ему легко внедрить моделирование и визуализацию таких сред в собственное приложение.
Исторически так сложилось, что ранние модели сред (воды, дыма, огня) были основаны на внешнем виде, а не на физической симуляции. Потоки жидких и газообразных сред моделировались простыми примитивами, комбинация которых позволяла анимировать системы частиц [1, 3] или простую геометрию, такую как листья [4].
Визуальная насыщенность повысилась с появлением функции турбулентности [5], и долгое время такой подход был очень распространен в виду того, что функция турбулентности периодична в пространстве и времени и легко совместима с существующими методами текстурирования. Этот подход использовался во многих фильмах в 80-х - 90-х годах: «Трон», «Король Лев» и др.
Однако у такого подхода есть существенный недостаток - полное отсутствие взаимодействия с пользователем и внешней средой.
Первые модели, использовавшие уравнения Навье-Стокса, были реализованы для двумерного случая [6] и использовали решение уравнения Пуассона для создания анимации двумерной жидкости.
Однако этот подход был ограничен двумерным случаем, и авторы отмечали неустойчивость симуляции.
Дальнейшие исследования продолжили Kass и Miller в [7], где они предложили линеаризовать систему мелкой воды для моделирования жидкостей.
Эта тема получила продолжение в работе [8], где применили эту модель для моделирования течения акварельной краски по холсту.
Эта реализация использовалась в кино в 1998 году в фантастической мелодраме Винсента Уорда «Куда приводят мечты» («What Dreams May Come»). Фильм был удостоен премии «Оскар» за лучшие визуальные эффекты.
В 1999 году в [9] был предложен вычислительно простой, легкий в интеграции и устойчивый при любых параметрах метод моделирования динамики жидких сред.
В виду этих достоинств, данный метод, получивший распространенное название Stable Fluids, стал широко применим в различных интерактивных приложений, прежде всего игровых, и повлек за собой целый поток исследований:
1. условия, использование графических По использованию различных схем Back Projection алгоритма [11],
2. По использованию разных схем дискретизации и численных методов [12]
3. По использованию различных граничных условий [10]
4. По расширению применимости: для оригинального двумерного алгоритма был предложен трехмерный аналог [13]
5. Прочие модификации данного подхода: сложные граничные процессоров для ускорения и т.д.
В настоящее время Stable Fluids можно считать, де-факто, образцом, с которым все сравнивают новые результаты исследований в области моделирования и визуализации жидких и газообразных сред.
Постановка задачи: Необходимо разработать библиотеку, позволяющую проводить моделирование течения жидкостей и распространения газов в реальном времени в двумерном и трехмерном случаях.
Библиотека должна позволять загружать любую сцену, внутри которой в дальнейшем планируется проводить симуляцию, и в этой сцене устанавливать источник жидкости или газа, генерирующий в заданном направлении частицы среды.
Библиотека должна позволять устанавливать большое количество физических параметров моделирования, позволяющих найти компромисс между интерактивностью моделирования и визуализацией и качеством синтезируемого изображения.
моделирование визуализация компьютерный графика
1. Обзор существующих решений рассматриваемой задачи или ее модификаций
1.1 Шум Перлина
1.1.1 История появления
Изначально спецэффекты в кино были полностью под контролем художника и режиссера. Все, что не снималось на камеру, а добавлялось на этапе монтажа, необходимо было добавлять в каждый кадр.
Работа эта была ручная и занимала колоссальное количество человеко-часов. Очень быстро стало понятно, что можно использовать вычислительные возможности ЭВМ для того, чтобы упростить эту задачу.
Использование компьютерной графики позволило привнести в киноиндустрию нечто новое и удивить зрителей необычными технологиями. TRON был первым проектом с солидной порцией компьютерных спецэффектов.
Вместе с тем, компьютерная графика того времени (80ые годы) выглядела искусственно гладко и однообразно.
С этой проблемой столкнулся Ken Perlin во время работы над фильмом TRON. Недовольный неестественностью синтезируемых кадров Ken Perlin стал искать способ разнообразить получаемое изображение.
В TRON были использованы не полигоны, а подход, именуемый Constructive solid geometry (CSG), при котором все объекты моделировались как логические комбинации математических примитивов, таких как сферы, эллипсы, цилиндры и другие простые формы.
Это подтолкнуло Ken Perlin'a искать решение в текстурировании объема, а не поверхностей. В 1983 году Perlin предложил простую псевдослучайную функцию для заполнения объема.
Примеры моделирования CSG
|
Логическое Объединение |
Логическое Вычитание |
Логическое Пересечение |
Ключевым преимуществом его подхода перед традиционным текстурированием, доступным в современном графическом процессоре, являются:
1. Экономия памяти: все получаемые текстуры синтезируются, они не требуют места для хранения, что особенно критично для трехмерных текстур.
2. Больший период повторения.
3. Позволяет использовать четырехмерный шум, в то время как поддержка четырехмерных текстур отсутствует.
4. Качество фильтрации существенно выше, благодаря интерполяции более высокого порядка:
|
Традиционное текстурирование |
Использование функции Perlin'a |
Основные требования, которые предъявлялись к функции шума Perlina при разработке:
1. Внешне производит впечатление шума.
2. Контролируема: при передаче одинаковых параметров, возвращает одинаковые значения.
Случайная функция Perlin'a позволяла заполнить все трехмерное пространство. Срез значений этой функции показан на рисунке.
Она обладала еще несколькими интересными свойствами:
1. Периодичность в пространстве
2. Нулевое математическое ожидание
3. Отсутствие слишком высоких или слишком низких частот
Наличие такой функции позволило продвинуться дальше.
Сам по себе шум был не очень интересен, но его использование в сочетании с математическими выражениями позволило создавать интересные текстуры.
1.1.2 Алгоритм
Шум Перлина - это отображение из пространства Rn в R. В настоящий момент наиболее распространенными значениями n являются {1, 2, 3, 4}.
Шум ограничен в частотной области - практически вся его энергия, если рассмотреть шум как сигнал, сконцентрирована в малой частотной области. Высокие частоты, проявляющие себя как маленькие детали, и низкие частоты вносят небольшой вклад в общую энергию. Внешне это выглядит как белый шум после свертки с ядром Гаусса.
|
Алгоритм Шума Перлина достаточно простой, рассмотрим его для пространства R2: |
||
|
1. Алгоритм использует регулярную сетку 2. Для входной точки P определяются окружающие ее точки, лежащие на сетке. Таких точек 2n т.е. 4 для R2 3. Для каждой точки Qi i={1,2,3,4}, лежащей на сетке: a. Выбирается псевдослучайный вектор градиент G. b. Вычисляется скалярное произведение D = G * (P - Qi) 4. Получили Di i={1,2,3,4}, которые можно проинтерполировать: a. Вычисляются веса для S-curve интерполяции (3t2 - 2t3) в [15] b. В дальнейшем в [14] была предложена другая формула для S-curve коэффициентов: 6t5 - 15t4 + 10t3. Это вызвано тем, что вторая производная в верхней формуле не равна нулю при t = {0, 1}. Это вызывает видимые разрывы в освещении геометрии, вершины которой были сдвинуты, используя шумовую функцию (displacement mapping). c. 2n-1 линейные интерполяции. |
||
Для быстрого вычисления псевдослучайных градиентов был предложен следующий алгоритм:
1. Заранее рассчитывается 2 таблицы (в каждой таблице n записей):
a. Таблица случайных целых чисел P, в которой перемешаны числа от 0..(n-1)
b. Таблиц случайных градиентов G
c. В оригинальной работе n = 256
2. Для узла с целочисленными координатами {i,j,k} градиент можно вычислить по формуле:
grad_vec = G[ (i + P[ (j + P[k]) mod n ] mod n ]
Такой подход был изменен в [14], где было предложено отказаться от таблицы случайных векторов G. Вместо этого Perlin предложил использовать 12 векторов, которые подобраны так, чтобы избежать корреляции между ними и координатными осями. Предложенные вектора направлены из центра куба [-1, 1]3 в стороны вершин.
1.1.3 Применение
В природе многие явления обладают свойством самоподобия. Используя этот факт можно смоделировать интересные поверхности с помощью шума Перлина. Рассмотрим следующий пример:
1. Пусть дана функция noise(x)
2. Рассмотрим линейную комбинацию:
3. Такая функция (BM означает Brownian Motion) выглядит уже гораздо лучше: проиллюстрируем это на графиках
|
a |
b |
c |
|
|
d |
e |
f |
Данная таблицы представляет функцию Перлина на разных частотах a-e - первые 5 октав, f - результирующая Brownian Motion функция
4. Аналогично можно получить функцию турбулентности:
5. Используя различные комбинации функций можно получать различные материалы:
1.2 Применение уравнений Навье-Стокса для задач нефотореалистичного рендеринга
1.2.1 Алгоритм
Интересное применение уравнениям гидродинамики было дано в [8]. Авторы предложили использовать уравнение «мелкой воды» для имитации различных техник рисования. Схема работы данного метода достаточно проста:
1. Изображение разбивается на отдельные области
2. Генерируется набор слоев для каждой области
3. Для каждого слоя отдельно от остальных запускается процесс имитации течения жидкости, который рассчитывает распределение пигмента
4. Для получения окончательного результата слои накладываются друг на друга с помощью модели Кубелки-Мунка
В качестве входных данных в этом процессе принимаются параметры, которые отражают физические свойства бумаги, пигментов и др. Также при имитации используется маска мокрых областей для определения границы области, где вода может растекаться свободно.
1.2.2 Моделирование поверхности бумаги
Анизотропность бумаги моделируется созданием в каждой точке случайным образом заданных определяющих направлений (волокон) с помощью шума Перлина, что позволяет достичь реалистичной симуляции наложения акварельных красок на бумагу. Движение жидкости в каждой точке потока описывается системой нелинейных дифференциальных уравнений Навье-Стокса, сведенных к системе уравнений «мелкой воды».
Каждый слой имитируется с использованием 3х-уровневой модели:
· Уровень растекания воды (shallow-water layer), где вода с пигментом течет по поверхности бумаги по тем областям, которые помечены маской влажных участков. В процессе течения вода поднимает с поверхности бумаги пигмент и течет вместе с ним, перенося его на другое место. На этом уровне важны такие параметры, как скорость и давление воды, концентрация красителя и наклон (градиент высоты) бумаги.
· Уровень передвижения пигмента (pigment deposition layer), где пигмент осаждается на бумагу и всплывает обратно (по законам процессов адсорбции и десорбции)
· Капиллярный уровень (capillary layer), где вода впитывается в бумагу и распределяется в ней, происходит имитация движения воды по порам бумаги. Это позволяет маске влажных участков бумаги увеличиваться в размере.
Каждый пигмент перемещается между уровнем течения воды и уровнем перемещения пигмента посредством осаждения и всплытия. На осаждение и всплытие влияют свойства конкретного пигмента, такие как: густота (density), красящая способность (staining power) и уровень зернистости (granularity).
Функция капиллярного слоя состоит в том, чтобы позволять распространяться маске мокрой области благодаря капиллярному течению воды через поры бумаги. Существенные величины на этом слое - это:
· насыщенность водой бумаги, определяется как отношение объема воды к общему объему
· способность впитывания воды, определяется как объем воды, который еще может впитать бумага
1.2.3 Математическая модель
Движение жидкости в каждой точке потока полностью описывается системой нелинейных дифференциальных уравнений Навье-Стокса (уравнений «мелкой воды»). В двумерном случае для несжимаемых жидкостей, эти уравнения могут быть записаны в следующем виде:
Рассмотрим условия, которым должно удовлетворять поведение воды для достижения реалистичного эффекта:
1. Течение должно быть ограничено так, чтобы вода оставалась в пределах маски мокрой области.
2. Избыток воды в какой-то области должен вызывать течение воды из этой области в соседние и приводить к равновесию концентраций.
3. Течение должно периодически ослабляться, чтобы не допустить колебательных волн.
4. Течение должно искажаться из-за неровностей бумаги, что вызывает появление прожилок, параллельных направлению течения.
5. Локальные изменения должны носить глобальный характер (например, добавление воды в некоторую область должно отразиться на всей имитации).
6. Должно быть течение воды по направлению к краям для достижения эффекта их затемнения.
Уравнения Навье-Стокса переходят в уравнения «мелкой» воды. Решение этих уравнений дает необходимые значения вектора скорости (u, v). Данная система решается методом Эйлера.
Для численного решения использовалась следующая дискретная схема:
Перенос красителя на уровне растекания воды зависит от локальной скорости движения жидкости, которая рассчитывается на первом этапе имитации.
На каждом шаге какая-то часть красителя адсорбируется уровнем осаждения красителя, а другая путем десорбции возвращается обратно в раствор.
Этот процесс описывается с помощью трех переменных: интенсивность адсорбции, интенсивность десорбции и грануляция. Последняя переменная определяет, как толщина и структура бумаги влияют на десорбцию красителя.
Маска влажных областей бумаги может медленно расширятся за счет присутствия внутри бумаги капиллярных потоков. В отличие от уровня растекания, здесь поток воды обусловлен капиллярными эффектами.
На каждом шаге должно быть выполнено уравнение неразрывности
.
С этой целью на каждом шаге выполняется процедура релаксации дивергенции, которая перераспределяет жидкость в соседние клетки до тех пор, пока дивергенция не станет меньше заданного значения е.
Так как вычислительная сложность алгоритма весьма высока, а размер сетки для моделирования в данной задаче совпадает с размером обрабатываемого изображения, то скорость работы приложения была далека от интерактивной. Тем не менее, метод успешно себя зарекомендовал и был использован в киноиндустрии.
1.3 Интерактивное моделирование дыма
Хотя уравнения Навье-Стокса физически точны, на практике они не использовались для интерактивных приложений. Перелом произошел, когда в [12] был предложен вычислительно простой алгоритм для моделирования движения газа в двумерном случае.
Представленный алгоритм был продолжением работ [9, 10] и отличался стабильностью при любом выборе параметров. Это позволяло делать существенно меньше итераций при численном решении, что и обусловило высокую экономичность данного подхода.
1.3.1 Математическая модель
В этой статье автор представляет простое и быстрое приложение для реализации динамики жидкости для компьютерных игр.
|
(a) |
||
|
(b) |
Математически состояние жидкости в любой момент времени моделируется как поле скоростей (задается функция, которая определяет для каждой точки пространства вектор скорости). Для того, чтобы лучше понять это, достаточно представить комнату с воздухом (множеством частичек - молекул). Каждая частичка имеет скорость, которая может изменяться в зависимости от внешних условий: наличие батареи (источник тепла), присутствие сквозняка в комнате и др.
Например, скорость воздуха вблизи обогревателя будет в основном направлена вверх, так как теплый воздух легче холодного. Распределение скоростей внутри комнаты очевидно также сложно, как описание распределения скоростей частиц дыма, поднимающегося вверх от зажженной сигареты, или движение частиц пыли в воздухе.
Уравнения Навье-Стокса - точно описывают эволюцию поля скоростей с течением времени. При данных скоростях и силах уравнение говорит, как точно скорости будут изменяться через бесконечно малый промежуток времени. Уравнение вверху записано в компактной векторной форме. Очень грубо можно сказать, что изменение скоростей происходит из-за 3х величин, стоящих справа от знака равенства.
Но поле скоростей само по себе не слишком интересно, пока оно не начнет двигать какие-то объекты (частицы дыма, пыль или листья). Движение этих объектов вычисляется преобразованием скоростей вокруг объекта в телесные силы.
Легкие объекты обычно просто двигаются по полю скоростей, так сказать, текут вдоль скоростей. В случае с дымом чересчур дорого моделировать каждую частичку по отдельности, поэтому они заменяются на плотности.
Для этого вводится непрерывная функция, которая показывает, сколько дыма находится в каждой точке пространства. Обычно значения изменяются от одного до нуля. Эволюцию поля плотностей сквозь поле скоростей тоже можно описать математическим уравнением (нижнее уравнение), которое похоже на уравнение сверху. На самом деле, внизу более простое уравнение, чем сверху, так как оно линейное относительно плотности.
Математическое представление уравнений для жидкости полезно только, когда размышляешь о жидкости в общем.
На практике, конечно, нам необходимо конечное представление нашей жидкости. Обычный подход - это разбить все исследуемое пространство на равномерную сетку.
Здесь будет рассмотрен простой для описания случай равномерной двумерной сетки, хотя ничего из описанного ниже не ограничивается этим упрощением. Пространство разбивается на сетку, по каждой оси на N+2 ячейки.
Первый и последний столбцы и первая и последняя строчки отводятся для граничных условий. Считается, что плотность и скорости постоянны в каждой отдельно взятой ячейке.
Базовая структура решения следующая: начинаем с некоторых заданных значений для плотности и скоростей, затем постоянно обновляем их согласно событиям, которые происходят в окружающей среде. Считается, что между каждым циклом симуляции проходит время dt.
1.3.2 Движение плотностей
Базовая структура решения уравнения для плотности. В каждый момент времени происходит 3 действия (в уравнении они находятся справа от знака равенства)
Как сказано выше, сначала будет описано решение уравнения плотности, двигающейся сквозь поле скоростей, которое не меняется во времени. В уравнении плотности (внизу) какое-либо изменение плотности может произойти по трем причинам, описанным справа от знака равенства тремя выражениями.
Первое слагаемое говорит, что плотность должна двигаться по полю скоростей, второе - плотность может подвергаться диффузии, т.е. рассеиваться со временем, и третье - плотность может увеличиваться из-за присутствия источников плотности (например, сигарета - источник дыма). Обсуждение этих трех причин изменения плотности будет идти в обратном порядке.
1.3.3 Наличие источников плотности
Это условие легко реализуемо. Мы предполагаем, что источник задан в некотором массиве s[]. В моей программе этот массив заполняется при движении пользователем мыши. Далее через каждый момент времени dt из этого массива часть плотности переходит в основной массив.
1.3.4 Диффузия
Второй шаг - это диффузия. Диффузия происходит со скоростью diff (когда diff > 0 плотность будет распространяться по соседним клеткам). Рассмотрим, что происходит в отдельной ячейке.
Будем считать, что ячейка обменивается только с 4 соседями, как это показано на рисунке. Таким образом, клетка теряет плотность, так как отдает ее 4-м соседям, но, в то же время, плотность увеличится засчет притока от соседей.
Возможная реализация функции диффузии - это простое вычисление этих изменений в каждой клетке нашей сетки и добавление их с некоторым коэффициентом (скорость диффузии diff) к существующим значениям. Но, к сожалению, такая реализация будет плохо работать. Для больших значений параметра diff значения плотности начинают осцелировать, уходят в бесконечность, и процесс симуляции ломается. Такое поведение - это главный признак нестабильности метода. Главная идея стабильного метода следующая: результирующие плотности должны быть таковы, чтобы, если их прокрутить назад во времени, они бы привели к нашим начальным данным.
Это линейная система с неизвестным .
Можно построить матрицу для этой системы и затем просто вызвать процедуру обращения матрицы. Однако, решать эту систему таким способом неудобно, так как матрица разряженная (лишь небольшое количество ее элементов не равно нулю).
Поэтому будет использоваться простая итеративная техника обращения матрицы. Самый простой итеративный метод, который хорошо работает на практике, - это метод Гаусса-Зейделя.
1.3.5 Движение плотности по полю скоростей
Последняя составляющая уравнения описывает движение плотности по полю скоростей. Можно было бы, как и на шаге диффузии, получить линейную систему и решить ее методом Гаусса-Зейделя. Однако, полученные линейные уравнения будут зависеть от скоростей, и это сильно усложнит решение. Есть способ эффективнее.
Ключевая идея этого метода следующая: рассмотрим каждую ячейку, как частичку, обладающую неким свойством (свойством плотности) и способную это свойство переносить.
Тогда достаточно промоделировать движение каждой частички по полю скоростей. Но тут возникнет проблема, что придется производить обратное преобразование от частичек к сетке значений. Это уже не так просто сделать.
Гораздо проще проследить из какой клетки (на самом деле, из каких клеток) пришла частичка, т.е. следить за ее движением в противоположную полю скоростей сторону.
Количество плотности, которое эта частичка перенесет, получается просто в результате линейной интерполяции 4-х ближайших соседей из ее стартовой позиции.
Этот шаг получил название Back Projection, а метод Semi-Lagrangian за переход от метода Эйлера к модели Лагранжа.
1.3.6 Решение уравнения для скоростей
Рассмотрим, что из себя представляет уравнение скоростей. Скорость в каждый момент времени изменяется, также как и плотность, по 3 причинам: присутствие внешних сил, которые увеличивают скорости, диффузия и движение поля.
Первые 2 причины ничем не отличаются от случая для плотностей.
Третья причина для скоростей с первого взгляда может показаться непонятной и не рассмотренной еще, но, если ее интерпретировать как факт, что поле скоростей движется вдоль себя, то она точно так же, как и первые две, сводится к решению рассмотренным выше способом. Есть только одно небольшое добавление.
Поле скоростей должно удовлетворять следующему требованию: она должно сохранять массы переносимых им частиц (это требование берется из условия, что жидкость несжимаема).
Каждое поле скоростей можно разложить на сумму несжимаемого поля (поля, сохраняющего массу) и градиентного поля.
Таким образом, для того чтобы получить несжимаемое поле скоростей, нам достаточно вычесть из нашего текущего поля градиентное поле.
Не вдаваясь в детали, можно сказать, что решение этой проблемы связано с решением линейной системы уравнений, называемой уравнение Пуассона. Эта система разряжена, поэтому можно использовать метод Гаусса-Зейделя для ее решения.
В [12] описана реализация предложенного метода для современных ЦПУ и для процессоров, в которых отсутствует АЛУ для вычислений с плавающей точкой. Данный метод быстро доказал свою состоятельность, получив практическое распространение в таких программных продуктах как Maya и 3dMax, в компьютерных играх и других приложениях. Вслед за [12], активизировались исследования в этой области, многие из которых взяли за основу изложенный подход.
2. Моделирование системой частиц
В статье [20] был впервые представлен метод для моделирования таких природных феноменов, как облака, вода, дым, огонь и др., используя системы частиц.
От привычных методов представления данных при синтезе изображений система частиц отличается по трем причинам.
Во-первых, объект представляется не набором примитивов, таких как полигоны или патчи (параметрически заданные поверхности), которые определяют границу поверхности, а как некоторое облако простых частиц, которые определяют его объем.
Во-вторых, система частиц - это нестатичная сущность: частицы двигаются во времени, изменяют свою форму, «рождаются» новые частицы, а старые «умирают».
В-третьих, объект, представленный системой частиц, недетерминированный, т.е. его форма не фиксирована, неопределенна до конца. Случайные процессы, происходящие вокруг, могут изменять эту форму и тем самым влиять на внешний вид объекта. Примеры: дым, огонь.
При моделировании таких феноменов система частиц имеет ряд преимуществ перед классическими, ориентированными на использование поверхностей, техниками.
Во-первых, частица (пока будем представлять ее, как просто точку в трехмерном пространстве) гораздо более простой примитив, чем полигон. Система частиц - это самая простая форма представления поверхности. Эта простота выливается в экономию вычислительного времени, и потому можно обрабатывать большую базу примитивов и получать более детальные изображения при синтезе.
Так как частица очень проста, то легко моделировать такие эффекты, как размытие при движении (motion blur) быстро движущихся объектов для удаления временного алиасинга.
Второе преимущество заключается в том, что определение модели процедурное и может контролироваться генерацией случайных чисел (можно использовать тот же шум Перлина). Таким образом, получить высоко детализованную модель не требует затрат человеческого времени на дизайн.
В этом плане такой подход существенно выигрывает по сравнению с системами, где моделируются поверхности. По этой же причине она может адаптивно менять уровень детализации, чтобы наиболее успешно балансировать производительность и качество, в зависимости от набора текущих параметров.
Это чем-то похоже на фракталы, когда приближаясь к системе частиц, мы можем добавлять больше деталей. Еще одним достоинством системы частиц является то, что она позволяет моделировать «живые» объекты, которые изменяются во времени.
Такую сложную динамику объекты состоящие из поверхностей моделировать не позволяют.
Идея моделирования поверхностей, как набора частиц, не нова. Пятнадцать лет назад, в самых ранних компьютерных видеоиграх взрывающиеся космические корабли были представлены большим количеством маленьких светящихся точек, которые наполняли экран.
Такие точечные источники использовались в компьютерной графике в основном в симуляторах полетов. Однако более ранние публикации, чем статья [20], редки.
2.1 Схема работы системы частиц. Визуализация объемных данных текстурами и Ray-tracing
Историческая эволюция в этой области породила богатое наследие. Даже самые простые методы, которые использовали шумовые функции, тем не менее, на практике были успешно использованы в крупных коммерчески успешных проектах, чем и зарекомендовали себя как полезный инструмент.
С появлением шумовой функции Перлина стал возможен синтез сложных детализированных текстур. Дальнейшее развитие естественным образом приводит нас к физическому моделированию (пусть и упрощенному) как к средству достижения большего реализма.
Оба подхода Лагранжа и Эйлера обладают своими сильными и слабыми сторонами.
Метод Эйлера позволяет построить решение уравнений Навье-Стокса, но ограничен неким объемом в пространстве. Кроме того как любой сеточный метод ему присущи артефакты дискретизации.
Метод Лагранжа с другой стороны этими недостатками не обладает, но с помощью него очень сложно считать частные производные, необходимые для решения уравнений. В моей работе я предлагаю использовать комбинацию сеточного решения уравнения гидродинамики, систему частиц для визуализации и шумовые функции для предания большей детализированности.
3. Исследование и построение решения задачи
3.1 Математическая модель
В моей работе для моделирования жидких и газообразных сред я выбрала гибридный подход, в котором сочетаются решения уравнений для скоростей на трехмерной сетке и визуализация среды системой частиц. Точного решения система уравнений Навье-Стокса для интерактивных приложений не требуется. Ниже рассмотрим эту систему с точки зрения требований предъявляемых игровыми приложениями.
3.1.1 Уравнения Навье-Стокса
Представим, что мы моделируем жидкость, как систему частиц. Каждая частица - это маленький шарик воды, который имеет массу m, объем V и скорость .
Чтобы проинтегрировать систему вперед во времени, необходимо обрисовать действия сил на каждую частицу.
Второй закон Ньютона как раз говорит нам, как частицы ускоряются и откуда возникает движение.
|
D/D - Производная Лагранжа |
||
|
Рассмотрим, какие силы действуют на наши частицы |
||
|
Во-первых, в системе присутствует гравитация, т.е. на частицу действует сила тяжести. Во-вторых, области высокого давления давят на области с низким давлением. Нас интересует общая сила, действующая на частицу, потому что, например, если давление по всем направлениям одинаково, то общая сила будет равна 0. На самом деле, важны только те ситуации, когда с одной стороны частицы давление больше, чем с другой. В этом случае частица начинает двигаться в сторону, где давление ниже. Т.е. нас интересует изменение силы, которое проще всего посчитать, взяв отрицательный градиент давления. Также необходимо проинтегрировать по всему объему, что проще всего сделать домножив все выражение на V. В-третьих, возникает еще одна сила из-за вязкости нашей жидкости. Вязкие жидкости пытаются противостоять деформации. Эту силу можно рассматривать как некоторую силу, которая пытается заставить частицу двигаться со средней скоростью окружающего потока, т.е. она пытается минимизировать разницу в скорости между частицой и близлежащими к ней частицами. Дифференциальный оператор, который вычисляет как далеки значения в некоторой области - это лапласиан. Вот откуда появляется третье слагаемое в нашем уравнении. Далее нам также необходимо проинтегрировать по всему объему и домножить на µ - динамический коэффцифиент вязкого трения. |
||
|
Разделим обе части уравнения на V. |
||
|
И затем разделим на плотность с. |
||
В данной системе принимают участие следующие величины:
V -- вектор скорости,
t -- время,
µ -- коэффициент кинематической вязкости, с -- плотность,
P -- давление,
f -- вектор плотности массовых сил,
l -- характерный размер
Re - число Рейнольдса -- безразмерное соотношение, которое определяет стабильность системы
Если рассмотреть одномерный случай, то не сложно убедиться на сколько Re важный параметр:
- в предельном случае, когда отсутствует диффузия (м=0), то изменение скорости по полю скоростей можно условно изобразить как показано на рисунке
Уравнение вырождается в
Как видно из графиков, процесс симуляции быстро ломается.
- в другом придельном случае, когда мы рассматриваем только диффузию и уравнение вырождается в
Такое уравнение ведет себя устойчиво.
Это подталкивает нас к выводу, что для устойчивого моделирования необходима составляющая диффузии.
3.1.2 Метод Лагранжа
Метод Лагранжа (названный так по имени французского математика) - это метод, с которым вы, наверняка, все хорошо знакомы. Он рассматривает пространство как систему частиц.
Каждая точка жидкости или твердого тела рассматривается как отдельная частичка со своими координатами и некоторой скоростью.
Вы можете даже думать о каждой частичке, как будто это молекула. В общем, ничего удивительного здесь нет.
Симуляция твердых тел всегда обычно производится по методу Лагранжа, с дискретным набором частичек обычно соединенных в сеть.
3.1.3 Метод Эйлера
Метод Эйлера (названный так по имени швейцарского математика) использует другой подход, который обычно применяется для жидкостей. Вместо отслеживания каждой частички, мы следим за фиксированными точками в пространстве и смотрим, как величины, характеризующие жидкость (такие, как плотность, скорость, температура и др.) измеренные в тех точках изменяются во времени.
Жидкость, вероятно, протекая мимо тех точек вносит вклад одного вида изменений (например, течет теплая жидкость, а за ней холодная, температура в каждой фиксированной точке пространства уменьшается, хотя температура каждой отдельной частички не изменяется) В добавлении переменные жидкости могут изменяться во времени, внося вклад другого вида изменений которые могут быть измерены в фиксированной точке (температура в фиксированной точке пространства может уменьшаться в то время как жидкость повсюду остывает)
Численно, подход Лагранжа соответствует системе частиц (с или без соединения между самими частицами), а подход Эйлера соответствует использованию фиксированной сетки, которая не изменяется в пространстве даже в то время, как жидкость протекает через нее.
3.1.4 Граничные условия
Замкнутый куб: Это самый простой вариант задания граничных условий. Периодические: Быстрое преобразование Фурье. Произвольные: Вокселизация
4. Схема работы программного решения. 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
Размещено на Allbest.ru
...Подобные документы
Лазерные средства отображения информации. Особенности сопряжения имитационной модели Matlab-Simulink и программное обеспечение визуализации. Возможности средств разработки виртуальных миров, использующих VRML, для визуализации моделирования системы.
курсовая работа [1,6 M], добавлен 01.12.2014Характеристика автоматической системы управления технологическим процессом жидких и газообразных сред, необходимость и методика ее реконструкции. Техническое описание средств измерений АСУ ЖГС и системы обработки информации, их совершенствование.
дипломная работа [1,3 M], добавлен 11.03.2011Значение вербальных и знаковых информационных моделей для исследования объектов, процессов, явлений. Роль метода формализации в процессе создания компьютерной модели. Использование программы AutoCAD для трехмерного моделирования и визуализации объекта.
курсовая работа [866,5 K], добавлен 08.01.2015Основные этапы математического моделирования. Метод Эйлера как наиболее простой численный метод решения обыкновенных дифференциальных уравнений. Написание компьютерной программы, которая позволит изучать графики системы дифференциальных уравнений.
курсовая работа [1,9 M], добавлен 05.01.2013Трехмерное моделирование: улучшение алгоритмов рендеринга и просчета трехмерных изображений. Обоснование выбора алгоритмов. Выбор языка программирования и среды разработки. Структура данных и программного комплекса. Системные требования для работы.
курсовая работа [263,8 K], добавлен 24.06.2009Рассмотрение и характеристика специфических особенностей 3D Studio MAX - единственного программного комплекса моделирования, визуализации и анимации объектов, разработанный фирмой Autodesk. Ознакомление с общим представлением о трехмерной графике.
дипломная работа [1,5 M], добавлен 17.07.2017Исследование метода математического моделирования чрезвычайной ситуации. Модели макрокинетики трансформации веществ и потоков энергии. Имитационное моделирование. Процесс построения математической модели. Структура моделирования происшествий в техносфере.
реферат [240,5 K], добавлен 05.03.2017Использование расширения MATLAB - Simulink как системы математического моделирования. Электроэнергетическое направление системы - пакет Sim Power Systems, методом моделирования решающий задачи электроэнергетики. Структура и функциональные компоненты.
курсовая работа [1,5 M], добавлен 09.10.2014Понятия "рендеринг" и "моделинг" в компьютерной графике. Физические основы процесса визуализации. Проблема освещения и видимости объектов. Однотонная закраска многоугольников и закраска Гуро. Заполнение контура грани. Основные недостатки метода Гуро.
курсовая работа [75,8 K], добавлен 27.02.2011Обзор средств компьютерного имитационного моделирования по созданию веб-приложения для визуализации имитационных моделей. Система имитационного моделирования AnyLogic, Arena, SimuLab. Серверная, клиентская часть. Модель работы отдела банка и участка цеха.
дипломная работа [3,3 M], добавлен 25.05.2015Анализ существующих стандартов образовательных сред в системах адаптивного компьютерного обучения. Краткая характеристика и оценка состояния рассматриваемой проблемы. Стандарты и спецификации ЭО. Обоснование выбранного метода направления исследования.
научная работа [8,3 K], добавлен 29.01.2009Наглядное представление массивов различной информации в компьютерной графике. Типы визуализации: схематическая, концептуальная, стратегическая, графическая, комбинированная. Виды сравнения данных: покомпонентное, позиционное, временное, частотное.
контрольная работа [1,4 M], добавлен 20.12.2015Разработка пользовательского интерфейса. Характеристика процесса покадрового рендеринга графики. Ознакомление с архитектурой программного приложения. Анализ системы визуализации – сложной, продуманной структуры для предоставления информации пользователю.
дипломная работа [7,8 M], добавлен 10.07.2017Применение систем визуализации показателей качества воды. Принципы создания информационных систем, их назначение, цели и требования к ним. Разработка сайта и возможности CMS Joomla. Построение модели информационной системы с помощью CASE-технологий.
дипломная работа [2,5 M], добавлен 12.08.2017Разработка модулей для автоматического развертывания виртуальных сред и технология их резервного копирования. Схемы сетевого взаимодействия виртуальных сред и их состав (настройка гостевых операционных систем и служб) для каждого из специалистов.
дипломная работа [3,7 M], добавлен 06.03.2013Характеристика UML как унифицированного графического языка моделирования для описания, визуализации, проектирования и документирования объектно-ориентированных систем. Диаграмма программного обеспечения, деятельности, последовательности и реализации UML.
курсовая работа [439,9 K], добавлен 05.06.2014Этапы развития моделирования явлений, процессов, объектов, устройств и систем. Примеры математического, имитационного и физического построения. Воспроизведение транспортных систем городов с помощью программы для визуализации транспортной схемы VISUM.
реферат [29,5 K], добавлен 16.12.2010Исследование конечно-разностных методов решения краевых задач путем моделирования в среде пакета Micro-Cap V. Оценка эффективности и сравнительной точности этапов получения решений методом математического, аналогового моделирования и численными расчетами.
курсовая работа [324,3 K], добавлен 23.06.2009Рзработка библиотеки, которая позволит моделировать динамику частиц в трехмерной графики. Выбор средств и методов разработки. Варианты моделирования систем частиц. Моделирование на вершинном шейдере. Диаграммы класса Particle System и PSBehavior.
курсовая работа [4,4 M], добавлен 07.02.2016Ректификация как процесс разделения жидких и парожидкостных смесей путем многократного частичного испарения жидкости и конденсации паров, определение необходимого оборудования, математическое описание. Алгоритм решения задачи, схема автоматизации.
курсовая работа [978,2 K], добавлен 04.05.2014
