Как использовать многоядерность ЦП для обхода квадродерева, построенного на основе модели точечного облака

Кто-нибудь может помочь мне предложить методы оптимизации многопоточной обхода моего квадер дерева для ускорения процесса обнаружения еще больше? Спасибо.

Самое простое описание этой проблемы — это как обойти квадер дерево, используя несколько потоков.

Следующая фигура — это модель квадер дерева моей проблемы:

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

Следующее — это подробное описание моего сценария применения:

У меня есть 3D-объект, такой как чашка, изначально смоделированный в Blender и сохраненный в формате OBJ. Поверхность этого объекта была выборочно обработана для создания облака точек, состоящего из общего числа точек, которое является кратным четырем, скажем, N точек. Мне нужно использовать эту чашку для обнаружения столкновения с другим объектом, например, столом.

Если чашка и стол сталкиваются, это означает, что существует пересечение между моделью облака точек и 3D-моделью стола. Моя задача — идентифицировать точки в облаке точек, которые находятся в пересеченной зоне.

Алгоритм обнаружения столкновений, который я использую, должен быть очень быстрым, исполняясь на частоте около 1000 Гц, что означает, что у меня есть около 1 мс, чтобы определить точки, участвующие в столкновении.

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

Вот обзор процесса, который я использовал:

1.Облако точек было сгруппировано, группируя каждые четыре ближайшие соседние точки в один кластер, создавая в итоге N/4 кластеров. 

2.Самая ближайшая точка к геометрическому центру этих четырех точек была выбрана как родительская точка.

3.Эти родительские точки затем были аналогично сгруппированы в группы по четыре, и этот процесс повторялся, пока на верхнем уровне не осталась кластер из одной точки.

4.Через эти шаги было построено квадер дерево.

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

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

2. Если на верхнем уровне есть столкновение, рекурсивно проверьте его дочерние кластеры на столкновения, пока не будут достигнуты самые нижние кластеры, идентифицируя все точки, участвующие в столкновении.

Для реализации я использую очередь FIFO Q для управления узлами следующим образом:

1. Начните с того, чтобы поместить кластер верхнего уровня (topLevelCluster) в очередь.

2. Извлеките передний кластер из очереди и проверьте его на столкновение. Если он сталкивается, и он не на нижнем уровне, поместите все его дочерние кластеры в конец очереди.

3. Повторяйте, пока очередь не опустеет.

В настоящее время этот алгоритм выполняется на одном ядре. Я ищу способ реализовать этот алгоритм обхода многопоточно. Моя система — Windows 10 x64 с ЦП AMD 7950X на 16 ядер.

Я протестировал многопоточную версию, используя boost::lockfree::queue от Boost, которая хорошо работает в сценариях с высокой пропускной способностью, таких как миллионы точек, заняла около 80-100 мс на одном ядре и около 10 мс при использовании 8 ядер.

Тем не менее, с меньшими наборами данных, такими как десятки тысяч точек, улучшение с 8 ядрами не так существенно (строит время с примерно 3-5 мс на обход до примерно 1-2 мс).

Я также попробовал подход грубой силы, разделив исходное облако точек на 8 групп через гауссовское выборочное распределение, затем создав восемь отдельных квадер деревьев, каждое из которых обрабатывалось одним из восьми ядер. Этот метод показал значительное увеличение производительности, почти в 8 раз быстрее. Но этот подход является крайним средством.

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

Вот упрощенная версия моего многопоточного псевдокода:

void processQueue(int thread_id, boost::lockfree::queue<ClusterC*>& Q)
{
    ClusterC* c=NULL;
    
    while (!Q.empty())
    {
        if (Q.pop(c))
        {
            if(isCollide(c))
            {
                if (c->getLevel() == BottomLevel)
                {
                    processPointData(thread_id);
                }
                else
                {
                    for (auto& child : c->getChildClusters())
                    {
                        Q.push(child.get());
                    }
                }
            }
        }
    }
}


void collisionQueryMT()
{
    BS::thread_pool pool(16);
    boost::lockfree::queue<ClusterC*> Q(80000);

    Q.push(topLevelCluster); // Добавить верхний кластер

    for (int i = 0; i < NUM_THREADS; ++i)
    {
        pool.detach_task(std::bind(processQueueMT, i, std::ref(Q)));
    }

    pool.wait();
}