Metaballs без шейдеров + физика жидкостей
Как-то раз возник у меня диспут с хабраюзером ZimM по поводу безшейдерного 2D движка: я утверждал, что для простых 2D игр шейдеры не обязательны, почти все эффекты можно сделать спрайтами, его же позиция была обратной. Я не раз в уме возвращался к этому спору и придумывал задачи, не реализуемые на первый взгляд без шейдеров, и именно решение одной такой задачи и привело к созданию игры, где игрок управляет жидкостью наклоном телефона.
Теория
Как можно догадаться по заголовку, задача состояла в рисовании жидкостей с помощью metaballs. Суть этой технологии — в нахождении множества точек, находящихся не далее некоторого расстояния от центра любого из мета-шаров — «капель», составляющих жидкость (точнее смотрите на wiki). Есть много разных вариантов их отрисовки, в т.ч и на CSS. Самый простой и эффективный метод сводится к тому, чтобы нарисовать окружности с обратно-квадратичной прозрачностью и в полученной картинке отбросить зоны с прозрачностью меньше 0.5, а оставшиеся закрасить одним цветом.
На этом скриншоте из XScreenSaver MetaBalls видно, что пересекающиеся окружности образуют достаточно качественные «спайки» и выглядят органично в местах множественного наложения. В этом скринсейвере не выполнялась фильтрация зон, но современное оборудование вполне может с этим справиться.
В первую очередь я начал думать как бы делал metaballs на шейдерах: сначала в вершинный шейдер передаем по четыре вершины для каждого Metaball, формируем из них квадрат с текстурными координатами, затем в пиксельном шейдере рисуем либо готовую текстуру, либо результат обратно-квадратичной функции:
vec2 pos = texCoord.xy - vec2(0.5,0.5);
color.a = 0.25/dot(pos,pos);
Результат работы пишем в буфер и обрабатываем еще раз пиксельным шейдером с discard если альфа меньше 0.5 и покраской или текстурой для остальных значений. Конечно, надо будет подобрать коэффициенты и может немного «украшательств» в финальном шейдере.
Практика
А вот без шейдеров тот же подход, но на CPU выглядит сомнительно: создаем в памяти буфер, например, 1024х1024xRGBA, проходим по массиву с «каплями» жидкости и для каждого в квадрате со сторонами R*2+1 расставляем коэффициенты по формуле обратного квадрата расстояния от центра. Ну и затем пробегаем по готовому буферу и вычищаем RGBA значения, имитируя discard, закрашиваем сплошные зоны, а затем этот буфер отсылаем видеокарте. Выходит при радиусе R = 20 и 40 «каплях» надо каждый кадр делать 67240 вычислений + 1048576 итераций по массиву пикселей с дополнительной обработкой. Это не говоря о пересылке текстуры в 4Мб в видеопамять и надежде на частоту 60fps на мобильных устройствах.
Я ради эксперимента реализовал такую схему и получил тормоза даже на десктопном компьютере. Да еще и результат выглядел откровенно слабо: ступенчатые края, равномерный цвет заливки, слишком геометрично достоверные «спайки». Заодно я допустил классическую ошибку premature optimization — попробовал все операции делать с целочисленными координатами, что может и дало прирост скорости, но плохо сказалось на качестве и добавило «дерганность» в движение жидкости.
Именно размышления о целочисленный расчетах натолкнули меня на мысль, что я пошел не тем путем: возложил на CPU слишком много, хотя можно было часть работы перенести на GPU. Верным решением оказалось… уменьшение текстуры в несколько раз! Но теперь я решил использовать тот же самый эффект, который Valve использует для шрифтов и граффити — Signed Distance Field Alpha Magnification. Для тех, кто не сталкивался с этой технологией, в двух словах принцип такой: увеличение картинки не ухудшает качество зон с градиентами, т.е. если есть плавный переход от значения 0.0 до 1.0 то промежуток внутри него будет сохранять свою форму при любом масштабе, как на этой картинке:
Детальнее можно почитать тут.
В случае с жидкостями я сделал буфер 256х256 и оставил градиент на границе каждой «капли», немного масштабировав альфу — упрощенно, все ниже изначального значения 0.4 отбрасывается, выше 0.6 заполняется сплошным цветом, а там где был переход от 0.4 до 0.6, теперь переход от 0.0 до 1.0 (на деле, там ипользуется кубическая функция, см. код ниже). Радиус каждой «капли» я уменьшил до 5 пикселей, таким образом на каждый кадр пришлось 4840 вычислений и 65536 пикселей в буфере размером 256Кб. Такое уменьшение нагрузки позволило перейти на floating-point операции с довольно высокой точностью — для каждой «капли» обрабатывается регион в 11х11 пикселей и для каждого пикселя вычисляется расстояние до точной координаты «капли», а не до пикселя в центре региона. Результат отправляется на видеокарту через glTexSubImage2D с ALPHA_TEST в 0.5. GPU обрезает край капли визуально достаточно аккуратно, даже при масштабировании текстуры с жидкостью в 4-8 раз.
Вот код обработки, с которым была получена картинка выше:
for (int i = 0; i < m_metaballs.Length; i++)
{
int minX = (int)Math.Floor(m_metaballs [i].Position.X - s_radius);
int minY = (int)Math.Floor(m_metaballs [i].Position.Y - s_radius);
int maxX = (int)Math.Ceiling(m_metaballs [i].Position.X + s_radius);
int maxY = (int)Math.Ceiling(m_metaballs [i].Position.Y + s_radius);
for (int y = minY; y < maxY; y++)
for (int x = minX; x < maxX; x++)
{
float dist =
(x - m_metaballs[i].Position.X) * (x - m_metaballs[i].Position.X) +
(y - m_metaballs[i].Position.Y) * (y - m_metaballs[i].Position.Y);
if (dist < s_radiusSqrd)
{
dist = 1.0f - (dist * s_iradiusSqrd);
int value = (int)(dist * dist * 256.0f);
int index = (x + y * s_fieldWidth) * 4;
m_field[index + 3] = (byte)NormalizeInt(m_field[index + 3] + value, 0, 255);
// shift from top left
int v = (int)((Math.Abs(x - minX) + Math.Abs(y - minY)) * 32.0f);
// middle value
m_field[index + 1] = (byte)NormalizeInt((m_field[index + 0] + v) /2, 0, 255);
// max value
m_field[index + 0] = (byte)NormalizeInt(Math.Max(m_field[index + 0], v), 0, 255);
// metaball index
m_field[index + 2] = (byte)(i + 1);
}
}
}
for (int i = 0; i < m_field.Length; i += 4)
{
int a = m_field [i + 3];
if (a > 40)
{
float na = a / 255.0f + 0.4f;
na = (na * na * na);
if (na > 0.8f)
na = 0.8f;
float nx = m_field [i + 0] / 32.0f;
if (nx > 4)
nx = 4;
float ny = m_field [i + 1] / 32.0f;
if (ny > 4)
ny = 4;
m_field [i + 0] = (byte)(25 * na + 30 * nx + 5 * ny);
m_field [i + 1] = (byte)(100 * na + 30 * nx + 10 * ny);
m_field [i + 2] = (byte)(150 * na + 30 * nx + 5 * ny);
m_field [i + 3] = (byte)(255 * na);
}
}
Еще немного шаманства понадобилось для придания жидкости более «объемного» вида с затемнением в верхнем левом углу и для отрисовки контура. Вот так выглядит финальный вариант, с блендингом GL_ONE/GL_ONE_MINUS_SRC_ALPHA:
Если присмотреться, то ближе к краю видно не идеальное качество шейдинга из-за низкого разрешения текстуры. Это можно было бы исправить, сделав всю жидкость одноцветной, но я решил оставить этот эффект, чтобы получить более динамичную картинку.
Физика
В целом, жидкости получились визуально более-менее нормальными и тогда мне захотелось таки сделать из игры головоломку, на подобие Teeter. Я иногда использую в играх движок Farseer (порт Box2D на C#), потому когда нашел блог тов. QuantumYeti очень обрадовался и через какое-то время смог запустить его код. Все было бы хорошо, но жидкости просачивались сквозь мельчайшие щели между объектами и утекали за экран. В качестве быстрого фикса я набросал патч к движку, который к каждой вершине выпуклого полигона добавляет небольшое смещение по вектору нормали. Это решило большую часть проблем, потому я отдал прототип левел дизайнеру и ждал результата. Через несколько недель левел дизайнер начал жаловаться, что простые элементы обрабатываются относительно нормально, а вот на сложных кривых и на острых углах жидкость может застрять навсегда.
Это не казалось большой проблемой и походило просто на временный баг. Я копнул немного в код тов. QuantumYeti и понял, что все там довольно плохо, ведь это был скорее proof of concept, а не рабочий движок для жидкостей: сомнительная логика выполнения, константы в коде, хранение временных переменных в классе с публичными полями и прочие косяки. Но самое главное, логика столкновений с объектами была очень условная и не подходила для нашей задачи — при попадании частиц жидкости вовнутрь объекта их скорость обнулялась и они телепортировались в направлении вектора нормали к поверхности. Если при этом частица попадала в другой объект, то зависала навсегда и внешние силы и вязкость жидкости на нее больше не действовали. Частицы также считались точечными телами и для коллизий использовался метод TestPoint, потому они могли просачиваться в щели. Простые патчи тут не помогали, да и мой хак с увеличением объектов усугубил ситуацию, потому я решил перейти на другой движок физики.
Выбор пал на liquidfun, а точнее, на его полный C# порт sharpbox2d. Движок этот сделан ребятами из Google, достаточно хорош внутри, дает приятную скорость и динамику движения жидкостей. Порт на C# оказался чуточку хуже и в целом не законченным — он компилировался, но не работал, т.к. часто использовался Java подход, когда функция меняет экземпляр класса, но он не помечен словами ref или out и если при портировании превратился в struct, то логика работы нарушается. Я взялся за исправление этих проблем и через день имел рабочую версию движка (p.s. могу выложить в git, если кому-то она нужна), а затем адаптировал всю игру для работы с ним. Все было бы хорошо, но левел дизайнер поведение жидкости в новом движке охарактеризовал как «кусок теста, ползающий по намасленным стенкам». Какое-то время я игрался с параметрами, пока не понял, что толку от этого не будет — физически точный и качественный этот движок не позволял мне получить нужные параметры вязкости и плотности, которые в прототипе от QuantumYeti были выставлены «на глаз», вшитыми константами и приближенными формулами.
На этот момент я уже довольно хорошо разобрался с физикой жидкостей и мог условно понимать, как должны работать коллизии и почему предыдущий вариант не работал. В основу лег метод ray casting во время движения частицы. Несколько дней ушло на переделку одного маленького метода, но в целом конечный вариант меня устроил — жидкости больше не просачиваются, не прилипают к стенам и не прекращают внутренние движения, когда соприкасаются с объектами.
RayCastInput input = new RayCastInput();
input.Point1 = particle.oldPosition;
input.Point2 = newPosition;
input.MaxFraction = 1.0f;
RayCastOutput output = new RayCastOutput();
/// ... skipped ...
if (fixture.RayCast(out output, ref input, c))
{
Vector2 n = output.Normal;
Vector2 p = (1 - output.Fraction) * input.Point1 + output.Fraction * input.Point2 + PUSHBACK * n;
Vector2 v = (p - particle.position);
float ax = moveVector.X - v.X;
float ay = moveVector.Y - v.Y;
float fdn = ax * n.X + ay * n.Y;
antiGravity -= n * fdn;
}
В ходе перебора всех фигур, с которыми есть (или будут в следующем кадре) пересечения, я формирую вектор antiGravity, направленный противоположно вектору движения.
Мой код FluidSystem.cs с некоторой зачисткой, но с неймспейсом, логикой и комментариями первого автора доступен тут: runserver.net/temp/FluidSystem.cs
Возможно, кто-то захочет использовать его в своих проектах или просто довести до ума и добавить к какому-либо движку.
Последним штрихом в физике стало добавление движущихся объектов — они могут начать пересекаться с жидкостью сами, а не в результате движения частиц, потому ray casting тут не совсем подходит и пришлось использовать изначальный подход автора с методом TestPoint и точечными проверками. Тут появились кое-какие баги, но для этого проекта они уже оказались не существенными.
В целом, можно сказать, что весь проект родится из костылей и на них же и держится — шейдерная графика без шейдеров, физика жидкости без жидкостного движка, патчи и заплатки вместо рефакторинга. Но с другой стороны, если что-то неплохое вышло из забавного спора и желания сделать то, что обычными методами не реализуемо — pourquoi pas?
