Задание 4: Симуляция водной поверхности на основе численного решения уравнения мелкой воды.

Начало: 26 ноября 2012
Конец: 17 декабря 2012 23:59

Авторы: Владимир Фролов, Алексей Игнатенко

Описание задания

Необходимо написать программу, симулирующую поведение водной поверхности и визуализирующую результат в 3D.



Рисунок 1. Пример выполненного задания.

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

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

  • Получить навыки реализации физических моделей для компьютерной графики. Работа с алгоритмами численных решений уравнений в частных производных.
  • Получить навыки практической работы с алгоритмами реалистичной компьютерной графики (доп. часть.).
  • Изучить начала программирования на GPU и работу с OpenGL3/4 (доп. часть.)

Обязательная часть (10 баллов)

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


Рисунок 2. Пример реализации задания (текстура на полу не входит в обязательную часть)

Требования к программе

  • Минимум три различных объекта в сцене, под водой.
    • Пол считается за 1 отдельный объект
    • Стенки “бассейна” считаются за 1 отдельный объект
  • Минимум один источник света в сцене.
  • Наличие пола.
  • Реалистичное освещение водной поверхности (что подразумевает корректное вычисление нормали).
  • Вода должна быть прозрачной.
  • Управление программой должно быть реализовано как минимум следующим образом:
    • WASD - движение камеры
    • мышка - поворот сцены при зажатой левой кнопки мыши или камера как в шутерах.
    • F1, F2, F3 - смена камер если реализовано несколько фиксированных положений.
    • F5 - пауза симуляции (если реализована реалистичная визуализация на CPU)
    • F6 - реалистичная визуализация (если реализована реалистичная визуализация на CPU)
    • Правая кнопка мыши - добавление возмущающих объектов если реализовано.
    • стрелочки - управление лодкой если реализовано.

Пожалуйста соблюдайте установленные требования. Баллы будут снижены если требования не будут выполнены.

Требования к симуляции

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

Дополнительная часть

  • Текстуры на объектах (+1).
  • Отражения (при наличии окружения над водой либо при взгляде из под воды): (+2)
  • Преломления (от +2 до +4) (от +4 до +8 если реализовано на GPU). Максимальный балл ставится только за корректную реализацию на основе трассировки лучей.
  • Каустики (До +16):
    • Внимание! Каустики должны зависеть от текущей формы поверхности воды. То есть должны быть следствием преломления света через рассчитанную водную поверхность. За фейковые каустики сделанные в виде простой проективной текстуры ставится не более 1 балла!
    • Некорректные, но правдоподобные каустики (+1)
    • Корректные каустики на дне (от +2 до +4) (От +4 до +8 если реализовано на GPU)
    • Корректные каустики на дне + стенах бассейна (+6) (+12 если реализовано на GPU)
    • Корректные каустики на произвольных объектах (от +6 до +8) (+12 до +16 если реализовано на GPU) Засчитывается (+6/+12) если дно неплоское.
    • Максимальный балл за каждый из пунктов ставится только если реализована фильтрация текстуры, в которую собираются фотоны. Рекомендуется использовать медианный фильтр. Баллы за каустики различных типов не складываются.
  • Окружение надводное (от +1 до +4)
    • Максимальный балл ставится только за насыщенное объектами (например ландшафт + деревья + скайбокс) окружение, реализованными с высокой степенью реалистичности.
  • Корректное взаимодействие симуляции с рельефом окружающего берега (+2).
    • Волны должны корректно отражаться от всех границ берега (как от стены). Берег должен иметь нетривиальные (непрямоугольные и неугловатые) участки. Если таких участков нет, ставится только +1 балл.
  • Водоросли, рыбы, ракушки и другие подводные объекты в виде отдельных моделей (от +1 до +2)
  • Визуализация детальной поверхности дна (микрорельеф) - песок, камни, растительность. (от +1 до +3) (от +2 до +6 на GPU при использовании Parallax Occlusion Mapping (POM) или любой другой техники отображения детальных поверхностей - например тесселяции). Про Parallax Occlusion Mapping и трассировку лучей вы можете прочитать в задании предыдущего года. Его же вы сможете использовать для трассировки лучей при реализации преломлений.
  • Визуализация возмущающих объектов - капли дождя, лодка, плавающая по воде, и. т.д (от +1 до +4).
  • Реалиcтичность и приятный внешний вид (+1).
  • Интерактивность - возможность кликать мышкой, добавляя возмущения или управлять лодкой на воде (от +1 до +2). Уточнение для случая работы с мышкой: максимум баллов ставится только если возмущающие объекты появляются в месте, на которое указывает мышка.
  • Управление камерой - (от +1 до +2).
  • Несколько камер (как минимум 1 под водой, минимум 3 камеры) - переключение обязательно реализовать по клавишам F1,F2,F3.... (+1).

Реализация алгоритмов на CPU или GPU

  • Если у вас нет возможности (и/или желания) выполнять задание с использованием API OpenGL3/4, вы можете реализовать некоторые из эффектов (каустики, преломления, POM, тени) используя трассировку лучей на CPU (смотрите описания 4-ых заданий прошлых лет).
  • Симуляция является достаточно простой в вычислительном плане и ее можно реализовывать на CPU даже в реальном времени. Однако в предоставленном вам примере вам будет гораздо проще сделать ее на GPU, вписав формулу в нужное место.
    • Вы можете сделать кнопки (или опции по клавишам F5 и F6) "пауза" и "реалистичная визуализация", если хотите реализовать реалистичные преломления и каустики на CPU. Но время расчета изображения не должно превышать 10 секунд на среднестатистической машине.

Описание алгоритма симуляции

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



$  \frac{\partial h}{\partial t} + \frac{\partial (uh)}{\partial x} +  \frac{\partial (uh)}{\partial y}  = 0  $
$  \frac{\partial (uh)}{\partial t} + \frac{\partial (u^2h + 1/2gh^2)}{\partial x} + \frac{\partial (uvh)}{\partial y}  = 0  $
$  \frac{\partial (vh)}{\partial t} + \frac{\partial (uvh)}{\partial x} + \frac{\partial (v^2h + 1/2gh^2)}{\partial y}  = 0  $

Рисунок 3. Уравнение мелкой воды.

Где:

h - значения высоты поверхности воды

u, v - горизонтальные скорости распространения волны по x и по y

g - константа ускорения свободного падения




При этом условии из закона неразрывности следует, что вертикальные скорости в жидкости малы, вертикальные градиенты давления близки к нулю, а горизонтальные градиенты вызываются неровностью поверхности жидкости и горизонтальные скорости одинаковы по всей глубине. При интегрировании по вертикали вертикальные скорости уходят из уравнений [wiki].
Поскольку курс компьютерной графики не включает в себя численное моделирование, мы предоставим вам готовую разностную схему которая решает уравнение мелкой воды. Однако интересующиеся могут изучить как именно получается ее вывод по следующим 2 ссылкам [1_water.pdf, 2_shallow_water_2010.pdf] а также иной многочисленной литературе по данной тематике.

Конечная разностная схема выглядит так:

$  H_{next}[i,j]=(1-\omega)*H_{prev}+\omega*\frac{H_{curr}[i,j+1]+H_{curr}[i,j-1]+H_{curr}[i+1,j]+H_{curr}[i-1,j]}{4} $
Рисунок 4.

Где:
Hcurr, Hprev и Hnext - значения высоты поверхности воды соответственно на текущем, предыдущем и следующем шагах.
i,j - индексы ячеек двумерной регулярной сетки.
ω - дословно "параметр релаксации". Его значение должно быть больше 1 но меньше 2.
Рекомендуем присвоить омега значение стремящееся к двойке слева (например 1.985).

Для численного решения уравнения мелкой воды при помощи разностной схемы вам прежде всего вам необходимо завести 3 массива (если вы пишете симуляцию на СPU то достаточно будет только 2 массивов) - A,B,C. На каждом k-ом шаге симуляции в массиве A будут хранится значения Hprev высоты с шага k-2 симуляции, в массиве B - значения высоты Hcurr с шага k-1. На каждом шаге необходимо получать новые значения высоты - "C[i,j] = F(A,B,i,j)" при помощи разностной схемы, после чего производить циклическую перестановку ссылок - "rotate(A,B,C)".

Алгоритм симуляции будет выглядеть на псевдокоде следующим образом:

procedure Water_Sim() is
  type Array2D is array (positive range <>, positive range <>) of float;
  SIM_SIZE : constant integer := 256;      
  A,B,C,T  : access Array2D;  
begin
  A := new Array2D(1..SIM_SIZE, 1..SIM_SIZE);
  B := new Array2D(1..SIM_SIZE, 1..SIM_SIZE);  
  C := new Array2D(1..SIM_SIZE, 1..SIM_SIZE);  
  while(true): -- main rendering loop
    -- simulation step
    --
    for (i,j) in [0..SIM_SIZE, 0..SIM_SIZE]:
      C[i,j] := F(A,B,i,j);
    end for;
 
           DrawWaterSurface(C);
 
    -- rotate(A,B,C)
    --
         T := A;
    A := B;
    B := C;
    C := T;
  end while;
  -- free A,B,C if needed
  --
 
end Water_Sim;

Функция F должна вычислять значение Hnext высоты на k-ом шаге на основе значений k-1 ого и k-2-ого шагов по указанной разностной схеме (рис. 4).

Подсказки:

  1. Для освещения водной поверхности рекомендуется использовать модель Блина-Фонга.
  2. Также не забудьте рассчитать нормаль к поверхности.
  3. Прозрачность в OpenGL3/4 работает так же как и в более ранних версиях.
  4. Чтобы рисовать точки, линии или треугольники без использования геометрических шейдеров, вы по прежнему можете передавать GL_POINTS, GL_TRIANGLES или GL_LINES в функции glDrawElements или glDrawArrays.
  5. Посмотрите описание 4 и 5 заданий прошлых лет, возможно вам удастся почерпнуть некоторую полезную информацию о библиотеке OpenGL3/4.
  6. Алгоритм Parallax Occlusion Mapping (POM) хорошо известен в литературе, а также вы можете почерпнуть его идею из 4-ого задания прошлого года.
  7. Если у вас есть возможность, тестируйте ваши программы на видеокартах разных производителей прежде чем посылать архив с заданием. Компиляторы GLSL различных производителей имеют некоторый расширенный функционал, не описанный в стандарте GLSL. Поэтому шейдер, который успешно скомпилился на NVIDIA может не заработать на AMD и наоборот.

Фотонные карты и трассировка лучей:

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

При этом алгоритм можно условно разделить на 2 шага.

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

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

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

  1. Сгенерировать N фотонов из источника света.
  2. Пересечь все фотоны (как лучи) с поверхностью воды как с плоскостью. Поскольку возмущения на поверхности воды малые, их можно не учитывать при вычисления точки пересечения поверхности воды и луча.
  3. Преломить лучи используя закон Снеллиуса через поверхность воды. При расчете преломления необходимо использовать точную нормаль к поверхности воды в точке пересечения луча с поверхность. В отличие от предыдущего шага здесь нельзя считать что поверхность воды полоская.
  4. Пересечь полученные лучи с поверхностью дна (в простейшем случае плоскость).
  5. Выполнить визуализацию полученной фотонной карты напрямую (простое аккумулирование цветов попавших фотонов, при помощи ‘сплаттинга’ дисками или точками) либо на основе оценки по k ближайшим фотонам.

Вы можете почерпнуть некоторую полезную информацию тут - [13].

Как делать фотонные карты в реальном времени на GPU:

Если вы собираетесь реализовывать фотонные карты на GPU, следующие рекомендации могут быть вам полезны:

  1. Чтобы протрассировать N фотонов, удобно запускать на отрисовку N точек, выполняя трассировку полностью в вершинном шейдере. Поскольку возмущения водной поверхности малые, вы можете определять точку пересечения луча и поверхности как пересечение луча и плоскости. Но при расчете преломления вы обязательно должны брать корректно-рассчитанную нормаль.
  2. Чтобы выполнить сбор освещенности на GPU, вы можете просто рисовать фотоны точками, аккумулируя цвет в текстуру. При этом:
    1. текстура может быть как непосредственно натянута на модель, на которую проецируются каустики.
    2. Текстура может быть полноэкранной (Эта техника позволит вам сделать каустики на произвольных объектах, но качество может быть хуже). В этом случае рекомендуется делать ее меньшего разрешения чем экранное и обязательно фильтровать.
    3. Фильтрация текстуры в любом случае рекомендуется.
  3. Для того чтобы правильно реализовать аккумулирование цвета в текстуру на GPU вам потребуется включить аддитивный (glBlendFunc(GL_ONE,GL_ONE)) альфа-блендинг и рендерить попавшие фотоны как точки в эту текстуру.
  4. Вы также можете использовать возможность OpenGL 4.3 - вычислительные шейдеры, реализуя алгоритм трассировки на них. Для того чтобы акумулировать цвет в текстуру в этом случае вам понадобится функциональность OpenGL4 "imageAtomicAdd": http://www.opengl.org/sdk/docs/manglsl/xhtml/imageAtomicAdd.xml

Эта техника позволит вам сделать каустики на произвольных объектах. Подробнее о каустиках и трассировке лучей в [12].

Работа с OpenGL3/4 и предоставляемый пример

Вместе с примером [sw_template] к данному заданию мы прилагаем набор простых примеров работы с OpenGL3/4 [gl_sdk] который возможно поможет вам в реализации вашего задания. Вы также можете исследовать интернет на предмет примеров работы с OpenGL3/4. Особенно советуем Вам посетить эти 3 сылки:

Предоставляемый вам шаблон программы помимо тривиального отображения поверхности воды и пола реализует основной цикл симуляции и циклическую перестановку ссылок. Вычисления вида С[i,j] = F(A,B,i,j) реализованы через операцию рендеринга в текстуру и рисования полноэкранного прямоугольника. Это стандартная схема реализации вычислений общего назначения (GPGPU) через графические API. Также можно было бы использовать OpenGL Compute Shaders. Однако они появились только в OpenGL 4.3, для которого нужно не забыть поставить специальный драйвер.
По нажатию правой кнопки мышки по центру водной поверхности добавляется небольшое возмущение. Для того чтобы симуляция заработала вам необходимо модифицировать шейдер WaterSimStep.frag, вписав в него разностную схему.

Материалы для выполнения задания

[1] http://google.ru
[2] 1_water.pdf
[3] 2_shallow_water_2010.pdf
[4] [sw_template]
[5] [gl sdk]
[6] [gl_brief.pdf]
[7] http://steps3d.narod.ru/
[8] http://nopper.tv
[9] http://www.gamedev.ru/code/forum/?id=138435
[10] http://courses.graphicon.ru/main/imagesynt/2011/assigns/assign4
[11] http://courses.graphicon.ru/main/imagesynt/2010/assigns/assign4
[12] http://graphics.cs.ucf.edu/caustics/
[13] http://ray-tracing.ru

Пример реализации

Задание (рис. 2) получило бы 10 баллов за обязательную часть, +1 за текстуры, +1 за интерактивность, +1 за реализованное управление камерой и +1 за приятный внешний вид. Итого: 14 баллов.

Критерии оценки и правила оформления задания

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

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

© Лаборатория компьютерной графики при ВМиК МГУ