The simplest description of this problem is how to traverse a quadtree using multiple threads.

The following figure is the quadtree model of my problem：

My algorithm does not need to traverse all leaf nodes from top to bottom, but only needs to traverse nodes that meet the conditions. In other words, if some branches do not meet the requirements, they will be discarded at the beginning. If I evenly distribute all branches to multiple cores, if some branches are discarded, it will cause a waste of CPU threads. Is there any way to make the traversal of the quadtree call all cores evenly?

The following is a detailed description of my application scenario:

I have a 3D object, such as a cup, originally modeled in Blender and saved in OBJ format. The surface of this object has been sampled to create a point cloud consisting of a total number of points that are a multiple of four, let’s say N points. I need to use this cup for collision detection against another object, such as a table.

If the cup and the table collide, it means there is an intersection between the point cloud model and the table’s 3D model. My task is to identify the points in the point cloud that are within the intersected area.

The collision detection algorithm I am using needs to be very fast, executing at approximately 1000Hz, which means I have about 1ms to identify the points involved in a collision.

To avoid checking each of the N points individually, I’ve built a quadtree and a hierarchy of bounding spheres. This algorithm can quickly discard non-colliding regions, rapidly narrowing down the query area to find the set of colliding points.

Here’s an overview of the process I used:

1.The point cloud was clustered by grouping every four nearest neighbor points 
into one cluster, creating a total of N/4 clusters. 

2.The point closest to the geometric center of these four points was chosen as 
the parent point.

3.These parent points were then similarly clustered into groups of four, and this 
process was repeated until a single-point cluster remained at the top level.

4.A quadtree was constructed through these steps.

After building the quadtree, a bounding sphere (sphere center and radius) was computed for each cluster at each level.
With the quadtree and bounding spheres prepared, the collision detection process can be significantly simplified, allowing for quick identification of the collision points as follows:

1.Initially, check if the single-point cluster at the top level collides (i.e., 
if the distance from the sphere’s center to the table is less than its radius). 
If there’s no collision, only one check is needed.  

2.If there’s a collision at the top level, recursively check its child clusters for 
collisions until the bottom-most clusters are reached, identifying all points 
involved in the collision.

For implementation, I use a FIFO queue Q to manage the nodes as follows:

1.Start by pushing the top-level cluster (topLevelCluster) into the queue.

2.Pop the front cluster from the queue and check for collision. If it collides, 
and it's not at the bottom level, push all its child clusters to the end of the 
queue.

3.Repeat until the queue is empty.

Currently, this algorithm is executed on a single core. I’m looking to implement this traversal algorithm in a multithreaded manner. My system is Windows 10 x64 with an AMD 7950X 16-core CPU.

I have tested the multithreaded version using Boost’s boost::lockfree::queue, which performs well with high data throughput scenarios like millions of points, taking around 80-100ms on a single core and about 10ms with 8 cores.

However, with smaller datasets like tens of thousands of points, the improvement with 8 cores isn’t as significant (only reducing the time from about 3-5ms per traversal to about 1-2ms).

I also tried a brute-force approach by dividing the original point cloud into 8 groups through Gaussian sampling, then creating eight separate quadtrees, each processed by one of the eight cores. This method showed a significant performance increase, nearly 8x faster. But this approach is a last resort.

Is there a better way to perform parallel traversal of my quadtree to greatly speed up the detection process?

Here’s the simplified version of my multithreading pseudocode:

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();
}

Can anyone suggest methods to optimize the multi-threaded traversal of my quadtree to accelerate the detection process even further? Thanks.