Рендеринг миллионов динамических связей: O(1) вместо O(N²) (но это не точно)

0xf0x5 часов назад

Рендеринг миллионов динамических связей: O(1) вместо O(N²) (но это не точно)

Уровень сложностиПростойВремя на прочтение4 минОхват и читатели4.1K3D-графика*Разработка игр*Программирование*КейсПривет, Хабр!

В предыдущей публикации про рендеринг космического окружения в игре The 13th Sign, я обещал рассказать про то, как мы рисуем частицами персонажей. Задача уже решена и статья скоро будет, но в процессе разработки я наткнулся на кое-что не менее интересное. Под катом, конечно же, трюк – бесплатных пирожных в математике не бывает.

Представьте: вам нужно отрендерить миллионы частиц, которые динамически соединяются светящимися линиями, образуя красивую «нейросетевую» структуру (см. видео). Базовые точки, к которым привязаны линии, анимированы, связь образуется только при расстоянии ниже заданного порога и пропадает при его превышении.

Классический подход «в лоб» – честно искать ближайших соседей. Но это приводит нас в ад алгоритмической сложности O(N²). Считать это на CPU – медленно. Строить акселерирующие структуры (Spatial Hashing, BVH-деревья итд) нет смысла – базовые точки движутся, причем произвольным образом. Варианты основанные на Voronoise и подобных клеточных структурах предполагают большее число выборок (проверка всех соседних клеток) и не дадут базовой точке вылететь за границы клетки. Кроме того, точки будут иметь равномерное распределение, а нам такой вариант не подходит.

Перед тем как перейти к алгоритму, немного о том как вообще рендерятся частицы.

• Делаем вызов отрисовки с NULL вместо Vertex Buffer, указываем 6 вершин, а количество частиц передаем как количество инстансов.
• Внутри Vertex Shaderберем vertexID и исходя из него строим два треугольника. float4 getGridInst(uint vID, uint iID, int gX,int gY){    float2 map[6] = { 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 };    return float4(float2(iID % gX, floor(iID / gX))/float2(gX,gY), map[vID % 6]); }

Исходя из instanceID, позицию частицы мы можем рассчитывать или загружать любым способом.

Базовые точки

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

Если нужен доступ к их координатам на CPU – есть два варианта. Если точек не очень много и они помещаются в лимит constant buffer, лучше использовать его. Если нет - есть structured buffer, который лишен таких ограничений.

Формировать этот буфер можно как на CPU так и с помощью Compute Shader.

Когда буфер сформирован, надо получить координаты базовой точки, но не для одного particleID, а для целой пачки, количество частиц в которой рассчитывается как  TotalParticlesCount / basePointsCount. То есть, мы всегда посылаем на отрисовку все частицы, образующие линки между базовыми точками, а рисуем мы их или отбрасываем, решаем после. 

Стохастический отбор пар

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

• Псевдослучайный кандидат: Каждая частица на основе своего стабильного particleID выбирает базовую точку из массива. Это гарантирует равномерное распределение частиц для линков по всем базовым точкам.
• Дистанционный фильтр (Критерий выживания): В шейдере рассчитывается расстояние между текущей базовой точкой и случайно выбранной точкой. Если расстояние больше заданного порога — связь считается «разрушенной». Можно схлопнуть вершины в ноль, выкинуть частицу за экран или использовать другим образом.
• Эффект выживания: Так как количество частиц огромно, среди миллионов слепых попыток всегда найдутся тысячи тех, у которых случайно выбранная точка оказалась рядом.
• Утилизация разрушенных связей: Алгоритм постоянно находится в ситуации, когда количество активных связей невелико по сравнению с неактивными. Выглядит как фатальный недостаток, если бы не одно но: нам все равно надо заполнять экран частицами. В игре базовые точки – это звезды, состоящие из частиц, а пространство между ними – космическая пыль. Так что, когда мы принимаем решение не делать частицу элементом связи, ее позиция считается по другому алгоритму, формируя игровое пространство.

Полный код функции (базовый вариант)

float hashIQ(uint x){x = (x << 13U) ^ x;x = x (x x * 15731U + 789221U) + 1376312589U;    return float(x & 0x7fffffffU) / 2147483647.0;}

float3 MetaLinks(uint particleID){//чтобы не перегружать статью, посчитаем 14 точек прямо в шейдере//в рабочем варианте в шейдер придет уже готовый буфер    #define basePointsCount 14    float3 basePoints[basePointsCount];

    for (uint i = 0; i < basePointsCount; i++)    {        float3 random3 = float3(hashIQ(i), hashIQ(i 5), hashIQ(i 3)) * 2 - 1;        basePoints[i] = noise(random3 * (112 + time.y / 1000.));        // тут noise - любая функция распределения    }//основная часть

    uint partriclesPerLink = TotalParticlesCount / basePointsCount;    float link = (particleID % partriclesPerLink ) / (float) partriclesPerLink ;    float3 pos = basePoints[particleID % basePointsCount];    float3 pos2 = basePoints[hashIQ(particleID) * (basePointsCount - 1)];    float dst= distance(pos, pos2);    dst=step(0.5, pow(.3 / dst, 12));    pos = lerp(pos, pos2, link * dst);    return pos;}

Буду рад обсудить в комментариях ваши варианты реализации этого эффекта!Теги:• шейдеры
• gpu
• vertex shader
• стохастика
• оптимизация
• vfx
• hlsl
• процедурная графикаХабы:• 3D-графика
• Разработка игр
• Программирование