Скелетная анимация в первый раз

Введение

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

Что я использовал?

• MSVS 2013 Professional — это моя основная IDE
• Qt Creator — при помощи этого я писал программу для редактирования анимации
• Qt 5.1 — как GUI для редактора анимации
• SDL 2 — ввод/вывод команд и отображения графики в конечной программе(где и должна происходить анимация)
• OpenGL 2.1 — для отображения графики
• GLEW — для подключения расширений OpenGL
• Boost — для использования таймера
• Protobuf Google — Для сохранения в файлы анимации
• С++ — ЯП на котором я все и делал

С чего начать?

Я решил что для начала мне нужно определить структуры, и мне будет так легче понять как они должны затем работать.
Для начала покажу мои #define’ы:

#define M_PI 3.1415926535 #define M_PI_2 M_PI/2 #define M_PI_3 M_PI/3 #define M_PI_4 M_PI/4 #define RAD1 M_PI/180.0f #define DEG1 180.0f/M_PI #define RAD2DEG(rad) rad*DEG1 #define DEG2RAD(deg) deg*RAD1  #define MAX_CHILDREN_COUNT		10 #define MAX_KEYFRAME_COUNT		20 

и вот к таким структурам я в итоге пришёл:

Joint — это сустав

	typedef struct _Joint 	{ 		//inheritanse 		_Joint*		root;		/* Pointer to root element. All elements have it. */ 		_Joint*		parent;		/* Pointer to parent */  		//simple joints variables 		float		x, y;			/* Position */ 		float		angle;		/* Angle of rotate. In radians!!! */ 		uint8_t		level;	/* Level of hierarchy. Root have 0, next level +1 */  		float		dX, dY;		/* Default Position */ 		float		dAngle;		/* Default Angle */  		float		aX, aY;		/* Animation Position */ 		float		aAngle;		/* Animation Angle */  		//children 		uint8_t		childCount;      /* Number of children */ 		_Joint*		child[MAX_CHILDREN_COUNT];	/* Array of children */  		//index 		uint16_t	indexCount;		/* Last number for index. Only Root have the var. */ 		uint16_t	index;			/* Unique index of joint */  	} S_Joint; 

dX, dY, dAngle — Это значения по умолчанию. Углы я решил хранить в радианах, от 0 до 6.28. И с этим у меня потом возникло куча проблем. Но об этом немного позже.
aX, aY, aAngle — Это параметры анимации. Они обозначают наколько кадр уже интерполировался. Тоесть прошедшая анимация записывается именно в них. Например анимация длится 900 ms(TIME), сейчас происходит 450 ms(NOW), но анимация не может оновляться каждую милисекунду, поэтому если раньше было допустим 400 ms, а щас 450, и интерполируем X и представим, что есть 2 ключа в первом X = 50(KEY1), во втором 100(KEY2), то конечное значение X считаю так:
_Joint.x += (KEY2 - KEY1) / TIME * NOW - _Joint.aX;
_Joint.aX = (KEY2 - KEY1) / TIME * NOW;
22,3 += (100-50) / 900 * 450 - 22,3
22,3 — Это X кости с учетом того что когда время (NOW) было равно 0, то X, тоже был равен нулю

KeyData и Keyframe — это структуры именно для анимации

 	typedef struct _KeyData 	{ 		float x, y, angle; 	} S_KeyData;  	typedef struct _Keyframe 	{ 		S_KeyData	data;	/* data of Joint */ 		uint16_t	time;		/* ~32 sec.(32768 ms) is maximum time for animation. Only Root have it */ 		uint16_t	index;		/* Index of joint, which we want interpolate */  		_Keyframe*	parent; 		uint8_t		childCount;		/* Number of children */ 		_Keyframe*	child[MAX_CHILDREN_COUNT];  	} S_Keyframe; 

Я долго думал, как можно организовать поиск костей для интерполяции. Поиск в дереве довольно затранный процесс для анимации на мой взгляд. У меня в голове было 2 решения. Первое решение, это использовать идексы для обозначения ветвей и это немного бы ускорило поиск, т.к. это была бы обычная адресация. Но выбрал я второе решение. На мой взгляд обновить дерево целиком куда проще и быстрее чем какие-то яего отдельные части. Очень просто, представим у нас есть главная кость, которая имеет по 10 детей, которые в свою очередь имеют ещё по 5. В итоге у нас всего 51 кость(кстати рутовый сустав у меня не видим вообще, изменение его x и y привдит к изменению положения всего обьекта).
Нам понадобится 10 циклов по 5 итераций, тоесть всего 50 итераций. И в итоге получим 51 интерполяцию при обновлении всего дерева. В противном случае, если мы используем поиск кости, то для поиска последней добавленной кости потребуется 50 итераий, для предпоследней 49 и так далее, в сумме куда больше чем обновление всего дерева. _Keyframe имеющий индекс 0, хранит время этой анмации, все его дети имеют параметр времени 0.

Animation — хранит список ключей

	typedef struct _Animation 	{ 		uint8_t keyNumber; 		uint8_t keyCount; 		S_Keyframe* key[MAX_KEYFRAME_COUNT]; 	} S_Animation; 

keyNumber — это индекс проигрываемой анимации, по умолчанию равен нулю. Все ключи анимации хранятся в массиве key, в хронологическом порядке. Все способы реализации, создания удаления структур и добавления в них новых обьектов я скрою чтоб бы не нагромождать тут много кода. Но покажу функции для самой анимации.

bool  doAnimation(S_Joint *root, S_Animation *anim, uint16_t time) { 	if (!root) return false; 	if (!anim) return false;  	bool timeOut = true;  	for (int i = 0; i < anim->keyCount; i++) 	{ 		if (time < anim->key[i]->time)	//search keyframes for interpolation 		{                         //первая анимация 1200, следующая 2400, 2400-1200=1200 			uint16_t mtime = anim->key[i]->time - anim->key[i - 1]->time;                        //nowTime is 1560, mtime = 1200(ERROR), 1560 - 1200(last key)=360(realtime) 			uint16_t nowTime = time - anim->key[i - 1]->time;   			if (i != anim->keyNumber)	//вот для чего нужен keyNumber, мы определили что перешли к следуюшему ключу 			{ 				setDefaultAnimTree(root);		//set to 0.0 animation changes(aX,yX,aAngle) 			} 			anim->keyNumber = i;			//устанавливаем номер анимации  			doInterpolate(root, anim->key[i - 1], anim->key[i], mtime, nowTime); 			timeOut = false; 			break; 		} 	} 	 	if (timeOut == true) 	{ 		setDefaultTree(root);	//если время истекло то обнуляем значение всех костей до дефолтных 	}  	return timeOut; } 

Когда функция возвращает true, то таймер сбрасывется на ноль.(boost::timer)

И заключительная функция:

void doInterpolate(S_Joint* root, S_Keyframe* key1, S_Keyframe* key2, uint16_t time, uint16_t nowTime) { 	if (root->index != key2->index) return;  	float x = (key2->data.x - key1->data.x) / time * nowTime; //так анимция уже должна измениться для этого времени 	float y = (key2->data.y - key1->data.y) / time * nowTime; 	float angle = (key2->data.angle - key1->data.angle) / time * nowTime;  	root->x += x - root->aX;	//root->aX - это те изменения анимации которые мы уже имеем, вычитаем их из тех что должны быть 	root->y += y - root->aY; 	root->angle += angle - root->aAngle;  	root->aX = x;	//изменения которые должны у нас быть, они уже есть в x,y,angle 	root->aY = y; 	root->aAngle = angle; 	         //рекурсивно обнавляем дальше все кости 	for (int i = 0; i < root->childCount; i++)	 	{ 		doInterpolate(root->child[i], key1->child[i], key2->child[i], time, nowTime); 	} } 

Вот такая скелетная анимация и работает она довольно не плохо. Туча проблем возникла на этапе создания программы в Qt, и самая первая это движения костей мышью, да и вообще движение костей. Длина вращения кости по кругу 6.28, тоесть 2*Pi или 360 градусов. Но получается движения происходит лишь в одну сторону. Если мы получаем допустим при расчётах 4.47, но хотим движение в другую сторону, впринципи можем сделать так:
4,47-6.28=-1,81
Вроде движение в другую сторону. Но это очень не удобно. так же я пробовал искать оптимальный путь до цели вращения. Если мы представим допустим наша позиция 1,57(A), цель наша 5.57(B), то:

negAngle = B-A; posAngle = (B-6.28)-A; if(fabs(posAngle) > fabs(negAngle)) { /*Выбираем меньшее*/ } 

Но, оптимальный путь нужен не всегда. Поэтому это тоже не совсем подходит. Я вот подумаю над двумя вариантами решения этих проблем. Первый вариант — это расчитвать строгую интерполяцию. Тоесть ключём будет являться именно кость в анимации. Второй способ это задавать ключём только движение, ничего более. Но по правде говоря я попал в тупик и не знаю, что делать дальше. Программа Qt работает с относительным успехом, но сама анимация вроде не плоха, но пока я писал GUI редактор я понимал её неэффективность и громоздкость. Как вообще пределать скелетную анимацию к физике(я горю желанием присоединения к Box2d), но как сделать это не имею ни малейшего представления. Я решил порлностью все переделать, но хочу услышать советы, критику, что и как я сделал неправильно. Ещё раз повторю, это моя система, сделана не по примеру, это мой взгляд на скелетную анимаию, не судите строго. Спасибо за внимание!