GPU Bound. Как перенести на видеокарту все и немножко больше. Анимации

Когда-то давно, было огромным событием появления на GPU блока мультитекстурирования или hardware transformation & lighting (T&L). Настройка Fixed Function Pipeline была магическим шаманством. А те кто умел включать и использовать расширенные возможности конкретных чипов через D3D9 API hacks, считали себя познавшими дзен. Но время шло, появились шейдеры. Сначала, сильно лимитированные как по функционалу, так и по длине. Далее все больше возможностей, больше инструкций, больше скорость выполнения. Появился compute (CUDA, OpenCL, DirectCompute), и область применения мощностей видеокарт стала стремительно расширяться.

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

Ууууу, опять анимации. Про это уже сто раз написано и описано. Что там сложного? Пакуем матрицы костей в буфера/текстурки, и используем для скиннига в вертекс шейдере. Это было описано еще в GPU Gems 3 (Chapter 2. Animated Crowd Rendering). И реализовано в недавней Unite Tech Presentation. А можно ли по-другому?

Технодемка от Unity

Много хайпа, но так ли круто на самом деле? На хабре есть статья, где подробно описано, как сделана и работает скелетная анимация в данной технодемке. Параллельные джобы это все хорошо, мы их не рассматриваем. Но надо выяснить, что и как там, с точки зрения рендера.

В масштабной битве сражаются две армии, каждая состоящая… из одного типа юнита. Слева скелеты, справа рыцари. Разнообразие так себе. Каждый юнит состоит из 3-х LOD (~300, ~1000, ~4000 вершин на каждый), и на вертекс влияют всего 2 кости. Система анимаций состоит из всего 7 анимаций на каждый тип юнита (напомню, что их аж 2). Анимации не блендятся, а переключаются дискретно из простого кода, который исполняется в job'ax, на которые делается акцент в презентации. Никакой стейт машины нет. Когда у нас два типа меша, то и рисовать всю эту толпу можно за два instanced draw call. Скелетная анимация, как я уже писал, основана на технологии описанной в далеком 2009 году.
Новаторски? Хм… Прорыв? Эм… Подходит для современных игр? Ну, разве что, соотношением фпс к количеству юнитов хвастаться.

Основные недостатки данного подхода (пребейк матриц в текстуры):

1. Зависимость от фреймрейта. Захотели в два раза больше кадров анимации — пожалуйте в два раза больше памяти.
2. Отсутствие блендинга анимаций. Их конечно можно сделать, но в шейдере скиннига будет образовываться сложная каша из логики блендинга.
3. Отсутствие привязки к Unity Animator стейт машине. Удобный инструмент для настройки поведения персонажа, который можно подключить к любой системе скинннига, но в нашем случае, по причине пункта 2, все становится очень сложно (представьте как блендить вложенные BlendTree).

GPAS

GPU Powered Animation System. Название только что придумал.
К новой системе анимаций предъявлялось несколько требований:

1. Быстро работать (ну понятно). Нужно анимировать десятки тысяч различных юнитов.
2. Быть полным (или почти) аналогом системы анимцаии Unity. Если там анимация выглядит так, то и в новой системе должно выглядеть точно также. Возможность переключения между built-in CPU и GPU системами. Это необходимо часто для отладки. Когда анимации «глючат», то переключением в классический аниматор можно понять: это глюки новой системы, или стейтмашины/самой анимации.
3. Все анимации настраиваются в Unity Animator. Удобный, проверенный, а главное готовый к использованию, инструмент. Мы будем строить велосипеды в другом месте.

Переосмыслим подготовку и запекание анимаций. Матрицы мы использовать не будем. Современные видеокарты хорошо работают с циклами, нативно поддерживают int помимо float, так что мы будем работать с кейфреймами как на CPU.

Рассмотрим пример анимации в юнити Animation Viewer:



Видно, что кейфреймы заданы отдельно для позиции, масштаба и вращения. Для каких-то костей надо их много, для каких-то всего несколько, а для тех костей, что не анимируются отдельно, просто задан начальный и конечный кейфрейм.

Позиция — Vector3, кватернион — Vector4, масштаб — Vector3. Структура кейфрейма у нас будет одна общая (для упрощения), так что нам нужно 4 float, чтобы уместить любой из вышеперечисленных типов. Еще нам надо InTangent и OutTangent для правильной интерполяции между кейфреймами согласно кривизны. Ах да, и нормализированное время не забыть:

struct KeyFrame
{
	float4 v;
	float4 inTan, outTan;
	float time;
};

Для получения всех кейфреймов используем AnimationUtility.GetEditorCurve().
Также, мы должны запомнить имена костей, так как надо будет сделать ремап костей анимации в кости скелета (а они могут не совпадать) на этапе подготовки гпу данных.

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

Теперь интересное. Анимация скелета на GPU.

Подготавливаем большой («количество анимированных скелетов» Х «количество костей в склете» Х «эмпирический коэффициент максимального количества блендов анимаций») буффер. В нем будем хранить позицию, вращение и масштаб кости в данный момент анимации. И для всех запланированных анимированных костей в этом кадре запускаем compute shader. Каждый thread выполняет анимацию своей кости.

Каждый кейфрейм, вне зависимости к какой величине он пренадлежит (Translate, Rotation, Scale), интерполируется абсолютно одинаково (поиск линейным перебором, да простит меня Кнут):

void InterpolateKeyFrame(inout float4 rv, int startIdx, int endIdx, float t)
{
	for (int i = startIdx; i < endIdx; ++i)
	{
		KeyFrame k0 = keyFrames[i + 0];
		KeyFrame k1 = keyFrames[i + 1];

		float lerpFactor = (t - k0.time) / (k1.time - k0.time);
		if (lerpFactor < 0 || lerpFactor > 1)
			continue;

		rv = CurveInterpoate(k0, k1, lerpFactor);
		break;
	}
}

Кривая представляет собой cubic Bezier curve, так что функция интерполяции будет следующая:

float4 CurveInterpoate(KeyFrame v0, KeyFrame v1, float t)
{
	float dt = v1.time - v0.time;
	float4 m0 = v0.outTan * dt;
	float4 m1 = v1.inTan * dt;

	float t2 = t * t;
	float t3 = t2 * t;

	float a = 2 * t3 - 3 * t2 + 1;
	float b = t3 - 2 * t2 + t;
	float c = t3 - t2;
	float d = -2 * t3 + 3 * t2;

	float4 rv = a * v0.v + b * m0 + c * m1 + d * v1.v;
	return rv;
}

Посчитали локальную позу (TRS) кости. Далее, отдельным compute shader'ом, сблендим все нужные анимации для данной кости. Для этого у нас есть буффер с индексами анимаций и весами каждой анимации в финальном бленде. Эту информацию мы получаем из стейт машины. Ситуация BlendTree внутри BlendTree решается так. Например есть такое дерево:



BlendTree Walk будет иметь вес 0.35, Run — 0.65. Соответственно, финальная позиция костей должна определяться 4-мя анимациями: Walk1, Walk2, Run1 и Run2. Их веса будут иметь значения (0.35 * 0.92, 0.35 * 0.08, 0.65 * 0.92, 0.65 * 0.08) = (0.322, 0.028, 0.598, 0.052) соответственно. Следует отметить, что сумма весов всегда должна быть равна еденице, не то волшебные баги обеспечены.

«Сердце» функции блендинга:

float bw = animDef.blendWeight;
			
BoneXForm boneToBlend = animatedBones[srcBoneIndex];
float4 q = boneToBlend.quat;
float3 t = boneToBlend.translate;
float3 s = boneToBlend.scale;

if (dot(resultBone.quat, q) < 0)
	q = -q;

resultBone.translate += t * bw;
resultBone.quat += q * bw;
resultBone.scale += s * bw;

Теперь можно перевести в матрицу трансформации. Стоп. Про иерархию костей забыли совсем.
По данным из скелета строим массив индексов, где ячейка с индексом кости содержит индекс своего parent'a. В root записываем -1.

Пример:

float4x4 animMat = IdentityMatrix();
float4x4 mat = initialPoses[boneId];

while (boneId >= 0)
{
	BoneXForm b = blendedBones[boneId];
	float4x4 xform = MakeTransformMatrix(b.translate, b.quat, b.scale);
	animMat = mul(animMat, xform);

	boneId = bonesHierarchyIndices[boneId];
}

mat = mul(mat, animMat);
resultSkeletons[id] = mat;

Вот, в принципе и все основные моменты просчета и блендинга анимаций.

GPSM

GPU Powered State Machine (вы правильно угадали). Система анимаций, описанная выше, прекрасно работала бы с Unity Animation State Machine, но в таком случае все усилия станут бесполезны. При возможностях просчета десятков (если не сотен) тысяч анимаций в кадр, UnityAnimator не вытянет и тысячи одновременно работающих стейт машин. Хм…
Что представляет собой стейт машина в Unity? Это замкнутая система состояний и переходов, которая управляется простыми численными свойствами. Каждая стейт машина работает независимо друг от друга, и по одному и тому же набору входных данных. Постойте-ка. Это же идеальная задача для GPU и compute shader'ов!

Baking phase

Сначала нам надо собрать и разместить в GPU friendly структуры все данные стейт машины. А это: состояния (states), переходы (transitions) и параметры (parameters).
Все эти данные размещаются в линейные буфера, и адресуются по индексам.
Каждый compute thread считает свою стейт машину. AnimatorController предоставляет интерфейс ко всем нужным внутренним структурам стейт машины.

Основные структуры стейт машины:

struct State
{
	float speed;
	int firstTransition;
	int numTransitions;
	int animDefId;
};

struct Transition
{
	float exitTime;
	float duration;
	int sourceStateId;
	int targetStateId;
	int firstCondition;
	int endCondition;
	uint properties;
};

struct StateData
{
	int id;
	float timeInState;
	float animationLoop;
};

struct TransitionData
{
	int id;
	float timeInTransition;
};

struct CurrentState
{
	StateData srcState, dstState;
	TransitionData transition;
};

struct AnimationDef
{
	uint animId;
	int nextAnimInTree;
	int parameterIdx;
	float lengthInSec;
	uint numBones;
	uint loop;
};

struct ParameterDef
{
	float2 line0ab, line1ab;
	int runtimeParamId;
	int nextParameterId;
};

struct Condition
{
	int checkMode;
	int runtimeParamIndex;
	float referenceValue;
};

• State содержит скорость с которой проигрывается состояние, и индексы условий прехода в другие согласно стейт машине.
• Transition содержит индексы состояния «из» и «в». Время перехода, время выхода и ссылку на массив условий входа в это состояние.
• CurrentState — это runtime data block с данными о текущем состояние стейт машины.
• AnimationDef содержит описание анимации со ссылками на другие, связанные с ней, по BlendTree.
• ParameterDef — это описание параметра управляющего поведением стейт машины. Line0ab и Line1ab — это коэффициенты уравнения прямых, для определения веса анимации по значению параметра. Отсюда:
  
  
  
• Condition — спецификация условия для сравнения runtime значения параметра и reference value.

Runtime Phase

Главный цикл каждой стейт машины можно отобразить с помощью следующего алгоритма:



В Unity animator 4 типа параметров: float, int, bool и trigger (которая bool). Всех их мы представим как float. При настройке условий есть возможность выбрать один из шести типов сравнения. If == Equals. IfNot == NotEqual. Так что мы будем использовать только 4. Индекс оператора передаем в поле checkMode структуры Condition.

for (int i = t.firstCondition; i < t.endCondition; ++i)
{
	Condition c = allConditions[i];
	float paramValue = runtimeParameters[c.runtimeParamIndex];
	switch (c.checkMode)
	{
	case 3:	if (paramValue < c.referenceValue) return false;
	case 4:	if (paramValue > c.referenceValue) return false;
	case 6:	if (abs(paramValue - c.referenceValue) > 0.001f) return false;
	case 7:	if (abs(paramValue - c.referenceValue) < 0.001f) return false;
	}
}
return true;

Чтобы начать переход, необходимо, чтобы все условия были true. Странные case labels — это просто (int)AnimatorConditionMode. Interruption logic это хитрая логика прерывания и откатывания перехода.

После того как мы обновили состояние стейт машины и прокрутили time stamp'ы на delta t кадра, пора подготовить данные про то, какие анимации следует считать в этом кадре, и соответствующие веса. Этот этап пропускается, если моделька юнита не в кадре (Frustum culled). Зачем нам считать анимации того, чего не видно? Пробегаемся по blend tree source state, по blend tree destination state, добавляем все анимации из них, а веса считаем по нормализированному времени перехода из source в destination (времени пребывания в transition). C подготовленными данными в дело вступает GPAS, и считает анимации для каждой анимированной сущности в игре.

Из логики управления юнитами поступают параметры управления стейт машиной. Например надо включить бег, устанавливаем параметр CharSpeed, а правильно настроенная стейт машина плавно сблендит анимации перехода из «ходьбы» в «бег».

Естественно, что полной аналогии c Unity Animator не получилось. Внутренние принципы работы, если они не описаны в документации, приходилось реверсить и делать аналог. Некоторый функционал еще не доделан (может быть и не будет). Например BlendType в BlendTree поддерживается только 1D. Сделать другие типы, в принципе, не сложно, просто это сейчас не нужно. Нет animation event'ов, так как надо делать readback c GPU, а «правильный» readback будет отставать на несколько кадров, что не всегда приемлемо. Но тоже можно.

Рендер

Рендер юнитов осуществляется с помощью инстансинга. По SV_InstanceID, в вертексном шейдере, получаем матрицы всех костей которые влияют на вертекс, и трансформируем его. Абсолютно ничего необычного:

float4 ApplySkin(float3 v, uint vertexID, uint instanceID)
{
	BoneInfoPacked bip = boneInfos[vertexID];
	BoneInfo bi = UnpackBoneInfo(bip);

	SkeletonInstance skelInst = skeletonInstances[instanceID];
	int bonesOffset = skelInst.boneOffset;

	float4x4 animMat = 0;
	for (int i = 0; i < 4; ++i)
	{
		float bw = bi.boneWeights[i];
		if (bw > 0)
		{
			uint boneId = bi.boneIDs[i];
			float4x4 boneMat = boneMatrices[boneId + bonesOffset];
			animMat += boneMat * bw;
		}
	}
	float4 rv = float4(v, 1);
	rv = mul(rv, animMat);
	return rv;
}

Итоги

Быстро ли все это хозяйство работает? Явно медленнее, чем семплинг текстурки с матрицами, но, все же, кое-какие цифры я могу показать (GTX 970).

Вот 50000 стейтмашин:



Вот 280000 анимированных костей:



Разработка и отладка всего этого настоящая боль. Куча буферов и смещений. Куча компонентов и их взаимодействия. Бывало руки опускались, когда бъешься несколько дней о проблему головой, а найти, в чем неполадка, не можешь. Особенно «приятно», когда на тестовых данных все работает как надо, а в реальной «боевой» ситуации нет, да проскочит какой-то глюк анимации. Несоответствия работы стейтмашин Unity и своей, тоже не сразу видны. В общем, если решите сделать у себя аналог, то я вам не завидую. Собственно, вся разработка под GPU она такая, чего жаловаться.

P.S. Хочется кинуть камень в огород разработчиков Unite TechDemo. У них на сцене большое количество одинаковых моделей руин и мостов, а они никак не оптимизировали их отрисовку. Вернее они попытались, поставив галочку «static». Только вот, в 16 битные индексы не запихнешь много геометрии (три раза хаха, 2017 год) и ничего не объеденилось, так как модели высокополигональные. Я проставил всем шейдерам «Enable Instancing», и снял галку «Static». Ощутимого буста не произошло, но, блин, вы же технодемку делаете, боретесь за каждый фпс. Нельзя так лажать.



P.P.S. Во все времена игры были, в основном, CPU bound, т.е. CPU не успевал за GPU. Слишком много логики и физики. Пренося часть игровой логики с CPU на GPU, мы разгружаем первый и нагружаем второй, т.е. делаем ситуацию GPU bound более вероятной. Отсюда и название статьи.