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

Привет, Хабр!

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

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

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

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

1. Делаем вызов отрисовки с NULL вместо Vertex Buffer, указываем 6 вершин, а количество частиц передаем как количество инстансов.

2. Внутри 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. То есть, мы всегда посылаем на отрисовку все частицы, образующие линки между базовыми точками, а рисуем мы их или отбрасываем, решаем после. 

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

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

1. Псевдослучайный кандидат: Каждая частица на основе своего стабильного particleID выбирает базовую точку из массива. Это гарантирует равномерное распределение частиц для линков по всем базовым точкам.

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

3. Эффект выживания: Так как количество частиц огромно, среди миллионов слепых попыток всегда найдутся тысячи тех, у которых случайно выбранная точка оказалась рядом.

4. Утилизация разрушенных связей: Алгоритм постоянно находится в ситуации, когда количество активных связей невелико по сравнению с неактивными. Выглядит как фатальный недостаток, если бы не одно но: нам все равно надо заполнять экран частицами. В игре базовые точки – это звезды, состоящие из частиц, а пространство между ними – космическая пыль. Так что, когда мы принимаем решение не делать частицу элементом связи, ее позиция считается по другому алгоритму, формируя игровое пространство.

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

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;
}

Буду рад обсудить в комментариях ваши варианты реализации этого эффекта!