"Разпоточить" анимацию

[Igors]

Добрый день

Есть N character'ов (персонажей), для каждого базовая модель в памяти, 2 и более character'а могут ее шарить. Также для каждого есть временный файл (тоже может шариться). Проигрывание анимации - перед отрисовкой кадра выполняется загрузка всех char

- открыть временный файл и загрузить из него данные
- пересчитать геометрию в буферах рисования
- закрыть файл

Профайлер показывает что узким местом оказывается пересчет геометрии. Это связано с тем что загружается "скелет" по которому уже модифицируется базовая модель. Скелет занимает примерно 8К на кадр. Сохранение же всей геометрии (дабы избежать расчетов) займет примерно 1М на кадр для картинок в аттаче, а для др моделей может быть и больше. Словом, отпихнуться от расчетов не удается.

Сейчас все исполняется в главной нитке. Как задействовать все вычислительные мощности?

Спасибо

[Racheengel]

Перечитал 3 раза... Ничего не понял
В чем проблема? Как раскидать расчеты по потокам? Или как вынести расчеты на GPU или что там еще под рукой?
Мне кажется, что на самом деле тут имеется несколько проблем, просто архитектура анимации настолько непрозрачна, что трудно сформулировать хотя бы одну (кроме того, что все работает медленно).
В общем, надо бить на подзадачи и тогда уже смотреть...

[Bepec]

Нет, тут нужно только одно решение для десятка проблем

PS очередная тема "решите все проблемы одной строкой" от Igors.

[Igors]

Перечитал 3 раза... Ничего не понял
В чем проблема? Как раскидать расчеты по потокам? Или как вынести расчеты на GPU или что там еще под рукой?
Мне кажется, что на самом деле тут имеется несколько проблем, просто архитектура анимации настолько непрозрачна, что трудно сформулировать хотя бы одну (кроме того, что все работает медленно).
В общем, надо бить на подзадачи и тогда уже смотреть...

Начальник (мелкий) сказал бы примерно так

Да меня не <волнует> что там: CPU, GPU или вообще <templаte> с бугра. Делайте/формулируйте/разбивайте что хотите, но чтобы через неделю 100 char'ов хоть как-то ходили (а не стояли по минуте как сейчас), а 2-3 char'а вообще "летали" (60 fps) вот на этой машине.

[Racheengel]

Я бы первым делом переписал модуль вычислений так, чтобы он параллелился на несколько потоков.
Еще бы посмотрел в сторону SSE-инструкций, они могут очень хорошо поднять производительность.
Уверен, что есть еще варианты

[Igors]

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

Классика советского кино

Лейтенант, а ты немецкий танк вблизи видел?

Код

C++ (Qt)
  /**@brief Return the cross product between this and another vector 
   * @param v The other vector */
	SIMD_FORCE_INLINE btVector3 cross(const btVector3& v) const
	{
#if defined(BT_USE_SSE_IN_API) && defined (BT_USE_SSE)
		__m128	T, V;
 
		T = bt_pshufd_ps(mVec128, BT_SHUFFLE(1, 2, 0, 3));	//	(Y Z X 0)
		V = bt_pshufd_ps(v.mVec128, BT_SHUFFLE(1, 2, 0, 3));	//	(Y Z X 0)
 
		V = _mm_mul_ps(V, mVec128);
		T = _mm_mul_ps(T, v.mVec128);
		V = _mm_sub_ps(V, T);
 
		V = bt_pshufd_ps(V, BT_SHUFFLE(1, 2, 0, 3));
		return btVector3(V);
#elif defined(BT_USE_NEON)
		float32x4_t T, V;
		// form (Y, Z, X, _) of mVec128 and v.mVec128
		float32x2_t Tlow = vget_low_f32(mVec128);
		float32x2_t Vlow = vget_low_f32(v.mVec128);
		T = vcombine_f32(vext_f32(Tlow, vget_high_f32(mVec128), 1), Tlow);
		V = vcombine_f32(vext_f32(Vlow, vget_high_f32(v.mVec128), 1), Vlow);
 
		V = vmulq_f32(V, mVec128);
		T = vmulq_f32(T, v.mVec128);
		V = vsubq_f32(V, T);
		Vlow = vget_low_f32(V);
		// form (Y, Z, X, _);
		V = vcombine_f32(vext_f32(Vlow, vget_high_f32(V), 1), Vlow);
		V = (float32x4_t)vandq_s32((int32x4_t)V, btvFFF0Mask);
 
		return btVector3(V);
#else
		return btVector3(
			m_floats[1] * v.m_floats[2] - m_floats[2] * v.m_floats[1],
			m_floats[2] * v.m_floats[0] - m_floats[0] * v.m_floats[2],
			m_floats[0] * v.m_floats[1] - m_floats[1] * v.m_floats[0]);
#endif
	}
 

И во сколько раз это ускоряет?

[Old]

Да меня не <волнует> что там: CPU, GPU или вообще <templаte> с бугра. Делайте/формулируйте/разбивайте что хотите, но чтобы через неделю 100 char'ов хоть как-то ходили (а не стояли по минуте как сейчас), а 2-3 char'а вообще "летали" (60 fps) вот на этой машине.

Ну как бы 100 чаров бегали еще 1997 году в Quake2. На современном железе без задержек мы бы их вообще не увидили.
Наверное дело в самом "пересчете геометрии". Вы что там делаете?

[Racheengel]

И во сколько раз это ускоряет?

Да это как раз фигня, один вектор симдом не ускорить
Но наверняка там где-нибудь есть какой-нибудь огромный цикл, выполняющий что-то простенькое над парой массивов - вот тогда симд и выстрелит) (да, на таком "танке" я катался )

[Igors]

Да это как раз фигня,

Позвольте напомнить что "фигня у коня" может быть очень большой

Но наверняка там где-нибудь есть какой-нибудь огромный цикл, выполняющий что-то простенькое над парой массивов - вот тогда симд и выстрелит) (да, на таком "танке" я катался )

Есть конечно, только вот данные идут совсем не подряд (см ниже)

Наверное дело в самом "пересчете геометрии". Вы что там делаете?

1) Пересчет вертексов по матрицам костей, обычное взвешивание (не dual Q). Код из либы, там кстати есть и GPU реализация
2) Расчет фейсетных нормалей
3) Расчет вертексных нормалей по фейсетным

Пункт 2 "весит" несколько больше, но все 3 масштабятся плохо, и, разумеется, необходим порядок 1-2-3

[Old]

2) Расчет фейсетных нормалей
3) Расчет вертексных нормалей по фейсетным

Как я понимаю, сначала вы рассчитываете нормаль фейса, а потом с ее помощью нормали всех вертексов ее образующих.
Возможно стоит попробовать нарезать задачи по фейсам. Рабочие нитки забирают исходные данные по фейсу, а возвращают уже готовые вертексные нормали. Т.е. считают и 2 и 3 пункт для каждого фейса.

[Igors]

Как я понимаю, сначала вы рассчитываете нормаль фейса, а потом с ее помощью нормали всех вертексов ее образующих.

Пример

F[0] = (0, 1, 2)  // фейс 0 ссылается на вертексы 0, 1, 2 (эти индексы хранятся в фейсе)
F[1] = (3, 1, 0)
...
F[100] = (4, 5, 1)

// тогда нормаль к вертексу 1 будет нормированной суммой нормалей всех фейсов куда он входит
VN[1] = (FN[0] + FN[1] + FN[100]).normalized();  

Чтобы объединить 2 и 3 нужно приставить лок к каждому VN В общем, давно известно что такие гадости не масштабятся, они для этого слишком малы.

Подход "вот самое узкое место, давайте его параллелить" очевиден, но редко удачен. Часто, как в данном случае, это место просто "не параллелится". Но ведь можно взять др кластер..

[Old]

Подход "вот самое узкое место, давайте его параллелить" очевиден, но редко удачен.

А это самое узкое место?

Часто, как в данном случае, это место просто "не параллелится".

Часто "это не параллелится" в привычном виде, если посмотреть на алгоритм с другой стороны или выбрать другой, то все может замечательно распараллелится.

А как параллелится расчет фейсовых нормалей? Вроде должен спокойно: разделить все фейсы на несколько групп и отдать каждую своему потоку.
А затем уже используя эти результаты также считать вертексные нормали.

[Igors]

А как параллелится расчет фейсовых нормалей? Вроде должен спокойно: разделить все фейсы на несколько групп и отдать каждую своему потоку.

Насколько я помню именно с этим тренировался "дружок", и КПД был не очень, хотя фейсов у него был лимон. А тут тех фейсов 50К, будет вообще печально. Типовая ситуевина, задачи слишком малы чтобы бандура успела разогнаться

Часто "это не параллелится" в привычном виде, если посмотреть на алгоритм с другой стороны или выбрать другой, то все может замечательно распараллелится.

Ага, напр если есть N char'ов - то почему бы не обсчитывать их всеми нитками? Просто у каждого должен быть свой буфер рисования. Правда тут неясно что делать если N меньше или соразмеримо с числом ниток

[Old]

Насколько я помню именно с этим тренировался "дружок", и КПД был не очень, хотя фейсов у него был лимон. А тут тех фейсов 50К, будет вообще печально. Типовая ситуевина, задачи слишком малы чтобы бандура успела разогнаться

Не знаю кто такой "дружок" и что у него было с лимоном фейсов, но нужно делать так, что бы "бандура не успевала останавливаться".
Я бы завел пул потоков, например, на восемь рабочих ниток. Дальше нарезал бы задания на части, например, по 1000 фейсов (мало - по 5000 или 10000). Считаем все фейсовые нормали, затем также нарезаем задания для вертексных нормалей.

Дальше можно попробовать кешировать геометрию для просчитанного кадра. Если положение бонов очередного чара совпадает с уже расчитанным, то используем ее. Положения костей для определенных кадров у одинаковых чаров будет совпадать, значит будут попадания в кеш кадров.

[Igors]

Я бы завел пул потоков, например, на восемь рабочих ниток. Дальше нарезал бы задания на части, например, по 1000 фейсов (мало - по 5000 или 10000). Считаем все фейсовые нормали, затем также нарезаем задания для вертексных нормалей.

"parallel for" по умолчанию (static) само это делает

Дальше можно попробовать ...

Если еще чего-то параллелить - то нет смысла считать нормали параллельно, это будет только мешать

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

Такое совпадение теоретически возможно, но почти наверняка юзер будет задействовать разные кадры из одного и того же файла (напр 3 картинки в стартовом посте = 3 копии шарят один файл). И не факт что будут "клоны" шарящие 1 файл. В общем, случай случай слишком частный чтобы с ним возиться