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

Contents

 

 

1 Аннотация

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

 

2 Введение

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

Исторически так сложилось, что ранние модели сред (воды, дыма, огня) были основаны на внешнем виде, а не на физической симуляции. Потоки жидких и газообразных сред моделировались простыми примитивами, комбинация которых позволяла анимировать системы частиц [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 можно считать, де-факто, образцом, с которым все сравнивают новые результаты исследований в области моделирования и визуализации жидких и газообразных сред. 

3 Постановка задачи

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

4 Обзор существующих решений рассматриваемой задачи или ее модификаций

4.1 Шум Перлина

4.1.1 История появления

Изначально спецэффекты в кино были полностью под контролем художника и режиссера. Все, что не снималось на камеру, а добавлялось на этапе монтажа, необходимо было добавлять в каждый кадр. Работа эта была ручная и занимала колоссальное количество человеко-часов. Очень быстро стало понятно, что можно использовать вычислительные возможности ЭВМ для того, чтобы упростить эту задачу. Использование компьютерной графики позволило привнести в киноиндустрию нечто новое и удивить зрителей необычными технологиями. TRON был первым проектом с солидной порцией компьютерных спецэффектов. Вместе с тем, компьютерная графика того времени (80ые годы) выглядела искусственно гладко и однообразно. С этой проблемой столкнулся Ken Perlin во время работы над фильмом TRON. Недовольный неестественностью синтезируемых кадров Ken Perlin стал искать способ разнообразить получаемое изображение.

В TRON были использованы не полигоны, а подход, именуемый Constructive solid geometry (CSG), при котором все объекты моделировались как логические комбинации математических примитивов, таких как сферы, эллипсы, цилиндры и другие простые формы.

Логическое Объединение	Логическое Вычитание	Логическое Пересечение
	Примеры моделирования CSG

 

Это подтолкнуло Ken Perlin'a искать решение в текстурировании объема, а не поверхностей. В 1983 году Perlin предложил простую псевдослучайную функцию для заполнения объема. Ключевым преимуществом его подхода перед традиционным текстурированием, доступным в современном графическом процессоре, являются:

1. Экономия памяти: все получаемые текстуры синтезируются, они не требуют места для хранения, что особенно критично для трехмерных текстур.
2. Больший период повторения.
3. Позволяет использовать четырехмерный шум, в то время как поддержка четырехмерных текстур отсутствует.
4. Качество фильтрации существенно выше, благодаря интерполяции более высокого порядка:

Традиционное текстурирование	Использование функции Perlin'a

 

Основные требования, которые предъявлялись к функции шума Perlina при разработке:

1. Внешне производит впечатление шума.
2. Контролируема: при передаче одинаковых параметров, возвращает одинаковые значения.

Случайная функция Perlin'a позволяла заполнить все трехмерное пространство. Срез значений этой функции показан на рисунке. Она обладала еще несколькими интересными свойствами: Периодичность в пространстве Нулевое математическое ожидание Отсутствие слишком высоких или слишком низких частот Наличие такой функции позволило продвинуться дальше.

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

4.1.2 Алгоритм

Шум Перлина – это отображение из пространства Rn в R. В настоящий момент наиболее распространенными значениями n  являются {1, 2, 3, 4}.

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

Алгоритм Шума Перлина достаточно простой, рассмотрим его для пространства R2:
Алгоритм использует регулярную сетку Для входной точки P определяются окружающие ее точки, лежащие на сетке. Таких точек 2n т.е. 4 для R2 Для каждой точки Qi i={1,2,3,4}, лежащей на сетке: Выбирается псевдослучайный вектор градиент G. Вычисляется скалярное произведение D = G * (P - Qi) Получили Di i={1,2,3,4}, которые можно проинтерполировать: Вычисляются веса для S-curve интерполяции (3t2 – 2t3) в [15] В дальнейшем в [14] была предложена другая формула для S-curve коэффициентов: 6t5 - 15t4 + 10t3. Это вызвано тем, что вторая производная в верхней формуле не равна нулю при t = {0, 1}. Это вызывает видимые разрывы в  освещении геометрии, вершины которой были сдвинуты, используя шумовую функцию (displacement mapping). 2n-1 линейные интерполяции.

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

1. Заранее рассчитывается 2 таблицы (в каждой таблице n записей):
1. Таблица случайных целых чисел P, в которой перемешаны числа от 0..(n-1)
2. Таблиц случайных градиентов G
3. В оригинальной работе n = 256
2. Для узла с целочисленными координатами {i,j,k} градиент можно вычислить по формуле: grad_vec = G[ (i + P[ (j + P[k]) mod n ] mod n ]
3. Такой подход был изменен в [14], где было предложено отказаться от таблицы случайных векторов G. Вместо этого Perlin предложил использовать 12 векторов, которые подобраны так, чтобы избежать корреляции между ними и координатными осями. Предложенные вектора направлены из центра куба [-1, 1]3 в стороны вершин.

4.1.3 Применение

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

1. Пусть дана функция noise(x)
2. Рассмотрим линейную комбинацию:
3. Такая функция (BM означает Brownian Motion) выглядит уже гораздо лучше: проиллюстрируем это на графиках

a	b	c	d	e	f
Данная таблицы представляет функцию Перлина на разных частотах a-e – первые 5 октав, f – результирующая Brownian Motion функция

4. Аналогично можно получить функцию турбулентности:
5. Используя различные комбинации функций можно получать различные материалы:

 

4.2 Применение уравнений Навье-Стокса для задач нефотореалистичного рендеринга

4.2.1 Алгоритм

Интересное применение уравнениям гидродинамики было дано в [8]. Авторы предложили использовать уравнение «мелкой воды» для имитации различных техник рисования. Схема работы данного метода достаточно проста:

1. Изображение разбивается на отдельные области
2. Генерируется набор слоев для каждой области
3. Для каждого слоя отдельно от остальных запускается процесс имитации течения жидкости, который рассчитывает распределение пигмента
4. Для получения окончательного результата слои накладываются друг на друга с помощью модели Кубелки-Мунка