Блог

Я запускаю n потоков, чтобы распределить рабочую нагрузку по проверке и отслеживанию столкновений между частицами в симуляции. Я по глупости пытался создать глобальный вектор и emplace_back из нескольких потоков одновременно индексы частиц сталкивающихся частиц (из массива частиц). Это приводит к конфликтам, когда потоки пытаются выполнить запись в один и тот же вектор. Мое текущее решение заключается в том, что всякий раз, когда я хочу отслеживать результаты из нескольких потоков, мне нужно определить новый std::vector<vector> myVectorSet(numberOfThreads) , а затем объединить все эти векторы, когда потоки имеют all .join()ed .

Есть ли более элегантный способ?

То, что вы ищете, — это метод, который обычно называют островами столкновений (см. Раздел оптимизации внизу страницы).

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

Существует так много разных способов справиться с этим, хотя для моего физического движка я использую простую функцию IslandInsert() в конце обнаружения узкой фазы столкновения (когда столкновение было фактически обнаружено первым). Используя простой std::unordered_map, вы можете сопоставить указатели вашего коллайдера с островным объектом и, используя простую логику, создавать свои острова по мере обнаружения столкновений. Примеры: Physx-3.4 и Bullet

Вот несколько фрагментов из моего движка, чтобы продемонстрировать возможную реализацию процедуры построения острова

 /* from the header, here are the containers used:
    std::vector<std::shared_ptr<struct Island>> Islands;
    std::unordered_map<class RigidBody*,std::shared_ptr<struct Island>> IslandLookup;
*/

void Solver::IslandInsert(Manifoldamp; m)
{
    enum
    {
        NO_ISLANDS_NO_STATICS,
        A_HAS_ISLAND = 1,
        B_HAS_ISLAND = 1 << 1,
        A_STATIC = 1 << 2,
        B_STATIC = 1 << 3,
    };
    totalContactCount  = m.cd.contactCount;
      manifoldCount;
    auto itA = IslandLookup.find(m.bodyA);
    auto itB = IslandLookup.find(m.bodyB);
    unsigned flag = 0;
    flag |= unsigned(itA != IslandLookup.end());
    flag |= unsigned(itB != IslandLookup.end()) << 1;
    flag |= unsigned(m.bodyA->physType == 0) << 2;
    flag |= unsigned(m.bodyB->physType == 0) << 3;
    switch(flag)
    {
    case NO_ISLANDS_NO_STATICS:    // no islands exist for this pair
        (IslandLookup[m.bodyB] = IslandLookup[m.bodyA] = NEW_ISLAND)->AddManifold(m);
        break;
    case A_STATIC:    // no islands exist and A is static
        (IslandLookup[m.bodyB] = NEW_ISLAND)->AddManifold(m);
        break;
    case B_STATIC:    //no islands exist and B is static
        (IslandLookup[m.bodyA] = NEW_ISLAND)->AddManifold(m);
        break;
    case A_STATIC | B_STATIC:    // both were static, so no islands should exist and this shouldn't even get here.
        throw "??";
        break;
    case A_HAS_ISLAND:    //only bodyA has an island and neither were static
        (IslandLookup[m.bodyB] = itA->second)->AddManifold(m);
        break;
    case A_HAS_ISLAND | B_STATIC:    //only bodyA has an island and B is static
        itA->second->AddManifold(m);
        break;
    case B_HAS_ISLAND:    //only bodyB has an island and neither were static
        (IslandLookup[m.bodyA] = itB->second)->AddManifold(m);
        break;
    case B_HAS_ISLAND | A_STATIC:    //only bodyB has an island and A is static
        itB->second->AddManifold(m);
        break;
    case A_HAS_ISLAND | B_HAS_ISLAND:    //both have an island, merge the two
        if(itA->second == itB->second)
        {
            itA->second->AddManifold(m);
        }
        else if(itA->second->bodyCount > itB->second->bodyCount)
        {
            itB->second->MergeInto(itA->second)->AddManifold(m);
            Util::VectorRemove(Islands, itB->second);
            IslandLookup[m.bodyB] = itA->second;
        }
        else
        {
            itA->second->MergeInto(itB->second)->AddManifold(m);
            Util::VectorRemove(Islands, itA->second);
            IslandLookup[m.bodyA] = itB->second;
        }
        break;
    case A_HAS_ISLAND | B_HAS_ISLAND | A_STATIC:    //both have an island, except A is static so A can't have an island...
        throw "??";
        break;
    case A_HAS_ISLAND | B_HAS_ISLAND | B_STATIC:    //both have an island, except B is static so B can't have an island...
        throw "??";
        break;
    case A_HAS_ISLAND | B_HAS_ISLAND | A_STATIC | B_STATIC:    //both have an island, except both are static and neither can have an island...
        throw "??";
        break;
    default: throw "??";
    }
}
// The following lines are methods used in the previous function

void Island::AddManifold(Manifoldamp; m)
{
    bodies.emplace(m.bodyA, 0);
    bodies.emplace(m.bodyB, 0);
    manifolds.emplace_back(amp;m);
    bodyCount = unsigned(bodies.size());
    contactCount  = m.cd.contactCount;
}

std::shared_ptr<Island> Island::MergeInto(std::shared_ptr<Island> other)
{
    for(Manifold* m : manifolds)
        other->AddManifold(*m);
    manifolds.clear();
    bodies.clear();
    contactCount = 0;
    bodyCount = 0;
    return other;
}

 

Кроме того, есть два других тривиально распараллеливаемых раздела большинства традиционных итерационных решателей.

1. Обнаружение столкновений — Поскольку обычно существует только доступ для чтения во время обнаружения столкновений в широкой и узкой фазах, вы можете распараллелить процесс, назначив диапазоны коллайдеров для тестирования для каждого потока или пары коллайдеров для узкой фазы. Для вставки в контейнеры потребуется простой мьютекс и блокировка для этой области, но это две дополнительные строки кода.
2. Обновление коллайдера — предполагая, что у вас есть решение о столкновении в широкой фазе, геометрию обычно необходимо обновлять каждый кадр (т. Е. ограничивающие рамки, выровненные по оси, или ограничивающие сферы). В зависимости от вашей реализации, это может потребовать от вас также обновить геометрию коллайдера. Этот процесс также легко распараллеливается путем определения диапазонов коллайдеров для каждого потока для обновления.

Это звучит как классическая проблема чтения / записи. Вам понадобится блокировка (для взаимного исключения) и, возможно, переменная условия для управления синхронизацией доступа к глобальному вектору. Посмотрите здесь, чтобы начать:

Параллельное моделирование физики — это целая область сама по себе. Короче говоря, вам нужно найти способ разбить вашу задачу на n заданий одинакового размера. Каждое задание может представлять собой часть физического пространства, где вы можете запускать все свои симуляции изолированно от остальных, а затем осуществлять перекрестную связь только между потоками на границах пространства.

Допустим, вы моделируете 2d-коробку, полную эластичных снарядов. Я мог бы разбить поле на сетку 4×4 и передать каждое подпространство одному потоку для вычисления одной итерации моделирования. Работа со снарядами, которые пересекают границы сетки, является сложной проблемой. Вы могли бы заставить каждый поток разрешать эти частицы на своих северной и западной границах, но там существует неограниченное количество проблем; что мне делать, если частицы 0, 1 и 2 и находятся в контакте. 0 находится в одной ячейке сетки, 2 — в другой, а 1 находится на границе между ними? В подобных случаях вы хотите иметь возможность передавать права собственности на частицы, чтобы все три из них обрабатывались одним потоком.

Как? Ну, вот почему это целая отдельная область. Там много материала. Можете ли вы уточнить, какую sim-карту вы используете? Возможно, вам лучше использовать что-то вроде Open Dynamics Engine или аналогичный инструмент физического моделирования с открытым исходным кодом.