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

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

4.2.2 Моделирование поверхности бумаги

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

Каждый слой имитируется с использованием 3х-уровневой модели:

• Уровень растекания воды (shallow-water layer), где вода с пигментом течет по поверхности бумаги по тем областям, которые помечены маской влажных участков. В процессе течения вода поднимает с поверхности бумаги пигмент и течет вместе с ним, перенося его на другое место. На этом уровне важны такие параметры, как скорость и давление воды, концентрация красителя и наклон (градиент высоты) бумаги.
• Уровень передвижения пигмента (pigment deposition layer), где пигмент осаждается на бумагу и всплывает обратно (по законам процессов адсорбции и десорбции)
• Капиллярный уровень (capillary layer), где вода впитывается в бумагу и распределяется в ней, происходит имитация движения воды по порам бумаги. Это позволяет маске влажных участков бумаги увеличиваться в размере.

 

 

Каждый пигмент перемещается между уровнем течения воды и уровнем перемещения пигмента посредством осаждения и всплытия. На осаждение и всплытие влияют свойства конкретного пигмента, такие как: густота (density),  красящая способность (staining power) и уровень зернистости (granularity).

Функция капиллярного слоя состоит в том, чтобы позволять распространяться маске мокрой области благодаря капиллярному течению воды через поры бумаги. Существенные величины на этом слое – это:

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

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

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

Рассмотрим условия, которым должно удовлетворять поведение воды для достижения реалистичного эффекта:

1. Течение должно быть ограничено так, чтобы вода оставалась в пределах маски мокрой области.
2. Избыток воды в какой-то области должен вызывать течение воды из этой области в соседние и приводить к равновесию концентраций.
3. Течение должно периодически ослабляться, чтобы не допустить колебательных волн.
4. Течение должно искажаться из-за неровностей бумаги, что вызывает появление прожилок, параллельных направлению течения.
5. Локальные изменения должны носить глобальный характер (например, добавление воды в некоторую область должно отразиться на всей имитации).
6. Должно быть течение воды по направлению к краям для достижения эффекта их затемнения.

Уравнения Навье-Стокса переходят в уравнения «мелкой» воды. Решение этих уравнений дает необходимые значения вектора скорости (u, v). Данная система решается методом Эйлера.

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

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

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

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

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

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

 

4.4 Интерактивное моделирование дыма.

Хотя уравнения Навье-Стокса физически точны, на практике они не использовались для интерактивных приложений. Перелом произошел, когда в [12] был предложен вычислительно простой алгоритм для моделирования  движения газа в двумерном случае. Представленный алгоритм был продолжением работ [9, 10] и отличался стабильностью при любом выборе параметров. Это позволяло делать существенно меньше итераций при численном решении, что и обусловило высокую экономичность данного подхода. 

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

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

	(a)
	(b)

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

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

Математическое представление уравнений для жидкости полезно только, когда размышляешь о жидкости в общем. На практике, конечно, нам необходимо конечное представление нашей жидкости. Обычный подход – это разбить все исследуемое пространство на равномерную сетку. Здесь будет рассмотрен простой для описания случай равномерной двумерной сетки, хотя ничего из описанного ниже не ограничивается этим упрощением. Пространство разбивается на сетку, по каждой оси на N+2 ячейки.

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

4.4.2 Движение плотностей

Базовая структура решения уравнения для плотности. В каждый момент времени происходит 3 действия (в уравнении они находятся справа от знака равенства)

 

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

4.4.3 Наличие источников плотности

Это условие легко реализуемо. Мы предполагаем, что источник задан в некотором массиве s[]. В моей программе этот массив заполняется при движении пользователем мыши. Далее через каждый момент времени dt из этого массива часть плотности переходит в основной массив.

4.4.4 Диффузия

Второй шаг - это диффузия. Диффузия происходит со скоростью diff (когда diff > 0 плотность будет распространяться по соседним клеткам). Рассмотрим, что происходит в отдельной ячейке. Будем считать, что ячейка обменивается только с 4 соседями, как это показано на рисунке. Таким образом, клетка теряет плотность, так как отдает ее 4-м соседям, но, в то же время, плотность увеличится засчет притока от соседей.

Возможная реализация функции диффузии – это простое вычисление этих изменений в каждой клетке нашей сетки и добавление их с некоторым коэффициентом (скорость диффузии diff) к существующим значениям. Но, к сожалению, такая реализация будет плохо работать. Для больших значений параметра diff значения плотности начинают осцелировать, уходят в бесконечность, и процесс симуляции ломается. Такое поведение – это главный признак нестабильности метода. Главная идея стабильного метода следующая: результирующие плотности должны быть таковы, чтобы, если их прокрутить назад во времени, они бы привели к нашим начальным данным.

Это линейная система с неизвестным . Можно построить матрицу для этой системы и затем просто вызвать процедуру обращения матрицы. Однако, решать эту систему таким способом неудобно, так как матрица разряженная (лишь небольшое количество ее элементов не равно нулю). Поэтому будет использоваться простая итеративная техника обращения матрицы. Самый простой итеративный метод, который хорошо работает на практике, - это метод Гаусса-Зейделя.

4.4.5 Движение плотности по полю скоростей

Последняя составляющая уравнения описывает движение плотности по полю скоростей. Можно было бы, как и на шаге диффузии, получить линейную систему и решить ее методом Гаусса-Зейделя. Однако, полученные линейные уравнения будут зависеть от скоростей, и это сильно усложнит решение. Есть способ эффективнее. Ключевая идея этого метода следующая: рассмотрим каждую ячейку, как частичку, обладающую неким свойством (свойством плотности) и способную это свойство переносить. Тогда достаточно промоделировать движение каждой частички по полю скоростей. Но тут возникнет проблема, что придется производить обратное преобразование от частичек к сетке значений. Это уже не так просто сделать. Гораздо проще проследить из какой клетки (на самом деле, из каких клеток) пришла частичка, т.е. следить за ее движением в противоположную полю скоростей сторону. Количество плотности, которое эта частичка перенесет, получается просто в результате линейной интерполяции 4-х ближайших соседей из ее стартовой позиции. Этот шаг получил название Back Projection, а метод Semi-Lagrangian за переход от метода Эйлера к модели Лагранжа.

4.4.6 Решение уравнения для скоростей

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