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 раз.



Вот код обработки, с которым была получена картинка выше:


Еще немного шаманства понадобилось для придания жидкости более «объемного» вида с затемнением в верхнем левом углу и для отрисовки контура. Вот так выглядит финальный вариант, с блендингом 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?