Hello,

I had a quick look at the beta source, even though I can't compile it on 
my Linux machine, and wondered, whether the code for building the BSP-
tree could be parallelized. As far as I understand the code, building the 
left and the right cell of a node simultaneously would be safe (perhaps 
the parametre "BBOX& cell" is a minor problem).
My idea is to create a pool of worker threads. Instead of recursing by 
simply calling

BuildRecursive(/*...*/);

we could assign the task to a non-busy worker thread, if there is one.

pseudo-code:
//split left cell
//[...]

if(worker_pool.worker_available())
{
  worker_pool.assign_task(BuildRecursive, /*parametres*/);
}
else
{
  BuildRecursive(/*...*/);
}

//the same for the other cell

The main thread would have to wait for all worker threads to finish. If 
one thread has finished before another, the other one will assign a new 
task to it.

Please correct me if I am wrong about this. I have not looked at the 
threading code.

Regarads
Lukas

Post a reply to this message

Lukas Winter wrote:
> Hello,
> 
> I had a quick look at the beta source, even though I can't compile it on 
> my Linux machine, and wondered, whether the code for building the BSP-
> tree could be parallelized. As far as I understand the code, building the 
> left and the right cell of a node simultaneously would be safe (perhaps 
> the parametre "BBOX& cell" is a minor problem).
> My idea is to create a pool of worker threads. Instead of recursing by 
> simply calling

You cannot predict the depth of any subtree, which makes it rather expensive.

	Thorsten

Post a reply to this message

Am Sun, 24 Feb 2008 15:17:55 +0100 schrieb Thorsten Froehlich:

> 
> You cannot predict the depth of any subtree, which makes it rather
> expensive.
> 
> 	Thorsten

This is true. However, if one thread is finished with its subtree before 
another it will get a new task as soon as the other one tries to recurse. 
But even if we do not reassign tasks to threads like this building in 
parallel would be faster. I would try to implement this if the unix 
source was also released. Unfortunately I do not own a copy of Visual 
Studio.

Post a reply to this message

Lukas Winter wrote:
> This is true. However, if one thread is finished with its subtree before 
> another it will get a new task as soon as the other one tries to recurse. 
> But even if we do not reassign tasks to threads like this building in 
> parallel would be faster. I would try to implement this if the unix 
> source was also released. Unfortunately I do not own a copy of Visual 
> Studio.

Well, your idea certainly is possible (even though recall it is a binary 
tree and building requires lots of memory), but as Chris said earlier, we 
are not looking for new feature implementations right now. We are still 
looking for people to work on the various open issues and incomplete 
features... ;-)

	Thorsten

Post a reply to this message

Lukas Winter wrote:
> Hello,
> 
> I had a quick look at the beta source, even though I can't compile it on 
> my Linux machine, and wondered, whether the code for building the BSP-
> tree could be parallelized.

Find me a scene that has not been artificially contrived for this 
example where building the BSP takes a significant amount of time 
compared to the total render.

For clarity, let's define significant as 5% or more of a render which 
lasts at least 5 minutes.

While it's certainly possible, I think parallelizing the photon shooting 
would be much more important :)

-- 
...Ben Chambers
www.pacificwebguy.com

Post a reply to this message

Am Mon, 25 Feb 2008 19:11:36 -0800 schrieb Chambers:
> 
> Find me a scene that has not been artificially contrived for this
> example where building the BSP takes a significant amount of time
> compared to the total render.
> 
I have not checked the newest beta yet but I think there are few scenes 
where it takes very long, you are right. I still find the possibility 
very interesting ;)
> 
> While it's certainly possible, I think parallelizing the photon shooting
> would be much more important :)

I didn't know that this is still on the todo list.

Post a reply to this message

Lukas Winter wrote:
> I didn't know that this is still on the todo list.

It's not per se, though the implementation there is just a first pass and
needs more work. Currently it runs one thread per light source (IIRC),
meaning if you have fewer light sources than CPU cores, you've got idle cycles.

-- Chris

Post a reply to this message

Thorsten Froehlich wrote:
> Well, your idea certainly is possible (even though recall it is a binary 
> tree and building requires lots of memory), but as Chris said earlier, we 
> are not looking for new feature implementations right now. We are still 
> looking for people to work on the various open issues and incomplete 
> features... ;-)

Yes, but it *is* an interesting problem, is it not? <grin>

-- Chris

Post a reply to this message

Lukas Winter wrote:
> I had a quick look at the beta source, even though I can't compile it on 
> my Linux machine

NB, that problem is now solved.

-- Chris

Post a reply to this message

Chris Cason wrote:
> Thorsten Froehlich wrote:
>> Well, your idea certainly is possible (even though recall it is a binary 
>> tree and building requires lots of memory), but as Chris said earlier, we 
>> are not looking for new feature implementations right now. We are still 
>> looking for people to work on the various open issues and incomplete 
>> features... ;-)
> 
> Yes, but it *is* an interesting problem, is it not? <grin>

Well, splitting the tree is rather trivial, the overhead in the tight code 
might be too costly.

	Thorsten

Post a reply to this message