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

Вот важная новость с фронта ИИ: 0xf0x 1 минуту назад Рендеринг миллионов динамических связей: O(1) вместо O(N²) (но это не точно) Простой 4 мин 0 3D-графика * Разработка игр * Программирование * Кейс Привет, Хабр! В предыдущей публикации про рендеринг космического окружения в игре 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 = { 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 }; return float4(float2(iID % gX, floor(iID / gX))/float2(gX,gY), map); }Исходя из instanceID, позицию частицы мы можем рассчитывать или загружать любым способом. Базовые точкиВ рамках демонстрации или VFX базовые точки (те, между которыми мы проводим линии) можно рассчитать прямо в шейдере. Если нужен доступ к их координатам на CPU – есть два варианта.

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

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

Событие, по словам экспертов, усилит конкуренцию в сфере ИИ.