Jump to content
  • Advertisement
Sign in to follow this  
GuyCalledFrank

parallel BSP tree traverse

This topic is 2510 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How is it possible to make BSP tree traversal run in N threads?
More concretely, I have a task, described by such pseudocode:


node
{
plane
bounding_sphere
leafData*
};

array sortedDataToRender;

processNode node
{
if (node.bounding_sphere in frustum)
{
if (node is leaf) sortedDataToRender.push_back(node);
if (camera.pos behind node.plane)
{
if (node.right) processNode node.right
if (node.left) processNode node.left
}
else
{
if (node.left) processNode node.left
if (node.right) processNode node.right
}
}
}

This code achieves 2 aims:
- no need to check is object in frustum if its parent node is not;
- free back-to-front/front-to-back sorting.

There are potentially thousands of leaf nodes may exist.
Splitting planes for each node are generated as shortest axis-aligned planes dividing AABB of objects on two parts; they are always go through AABB's center

But this code is very branchy and recursive, I just cant understand how to make it more flat and parallelable.

Share this post


Link to post
Share on other sites
Advertisement
You need a thread pool that processes tasks thrown at it, and some thread-local container to temporarily store the results.


void processNode(node, pool, data_to_render)
{

if (left node needs processing)
left_future = future(processNode, left, pool, data_to_render);

if (node is accepted)
data_to_render.add(node) // add to thread-local storage

if (right node needs processing)
processNode(right, tasks, data_to_render)

// wait for the left node
while (!left_future.ready())
pool.help_process_tasks();
}

// ...

thread_pool pool;
thread_local_container data_to_render;
processNode(root, pool, data_to_render);

data = data_to_render.merge();


This translation is reasonably direct, but requires a possibly not-insignificant amount of waiting on futures/barriers.

So rather than having the processNode() function do the waiting, you could give each task an explicit barrier against which to signal their completion, and the instigator of the traversal could wait until that barrier counts down to zero. Here you'd only be waiting in one place, rather than holding up each thread at various times.

You might also want to search the web for parallel merge sort implementations. They solve a very similar problem.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!