5 October 2015

Metaballs без шейдеров + физика жидкостей

Development of mobile applicationsC#
Как-то раз возник у меня диспут с хабраюзером 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?

Tags:графикаигрышейдерыненормальное программированиеmetaballsфизика
Hubs: Development of mobile applications C#
+17
18.8k 100
Comments 11
Popular right now
Senior Mobile Developer
from 210,000 to 300,000 ₽ТензорRemote job
Программист Unity
from 70,000 to 180,000 ₽Wild ForestRemote job
Unity-разработчик на VR- и AR-проекты
from 60,000 ₽JetStyleЕкатеринбургRemote job
Разработчик C#
from 170,000 ₽TennisiМоскваRemote job
Lead Mobile Developer (Android)
from 200,000 to 250,000 ₽UpTeam Inc.Санкт-Петербург