Re: [Ray-devel] Splitting scenery, network, SPL

[Wolfgang W. <ww...@gm...>]

<News>

Seems like I finally got the first version of the C++-like SPL grammar 
(see src/spl/grammar.yy). It spent much more time than I thought on that. 
Special SPL-features (like nice specification of blend maps) still need to 
be added but are generally unlikely to make difficulties (i.e. introduce 
s/r or r/r conflicts) as long as they are prefixed by a reserved word 
(like "map"). 

I'll now push forward the SPL compiler. 

On Friday 18 March 2005 02:43, Andrew Clinton wrote:
> > It seems to me that the natural way which remains is to store a list of
> > intersected primitives in the ray. The downside is that this sort of
> > thing depends a bit on the accelerator used (BVH does not need mail
> > box numbers, I guess...)
>
> Yes, a list would work but It will scale poorly if the ray needs to test a
> lot of primitives (need to test everything in the list on each
> intersection). That's why I mentioned we might want to do it with a hash
> table.
>
I wanted to make the point about storing the information in the _ray_. 

Which data structure to choose here is an interesting question. 
Direct storage in the primitive is of course the fastest way. 

Using a tree or hash requires dynamic resizing of this structure which 
is slow, however usind chunked allocation will fix that. 
Another way might be to associate a "cost" with intersection calculation 
and only store a fixed number of tested objects: Those which cost most. 

Another idea would be to give each primitive a serial number in the 
range 0..N-1 (with N being the number of primitives) and using a 
per-coroutine bitfield indexed with the primitive serial number to store 
the information. Memory consumption would be fixed to N/8 bytes 
per coroutine (or per simultanious ray). However, the information 
would not be cache-local and probably waste memory, although being 
faster (algorithically) than a hash. 

How many such (already intersected) objects do we have to expect need to 
be stored for one ray?

<Splitting the scene information>

I think, CSG could be split among several computers, if we transfer the CSG 
root and (maybe) first few levels to all computers and subsequent trees to 
different boxes. This works if we store a description about which computer 
has the required information at the place where a subtree was cut off. 
However, this is a bit more complicated than just passing rays. 

Another interesting thing one tends to overlook is now to make "instancing" 
work with splitting scene iformation and CSG. Kilauea (without CSG) could 
simply make sure that one box has all instances of a given object. 
This, however, undermines equal load balancing. 

For CSG, it is even harder. The easy solution is (of course) to give each box 
a copy. 


As a general consideration, the Kilauea people have correctly pointed out 
that moving rays is better than moving geometry because geometry 
can be huge. This is the "only" reason why I am considering it. 
However, the problem is that if geometry does not only consist of triangles, 
it is impossible to know in advance how to split it so that all boxes will 
be finished at the same time. (Otherwise that half of the boxes which got 
the isosurface is still busy while all those with just triangles are idle and 
cannot help.)

This, it seems, does not happen when moving geometry (on-demand loading) 
because all computers would process rays as long as there are rays to 
compute. However, loading and possibly re-loading (if it is too large to fit 
into memory of one box and hence has to be cached) the geometry eats up 
a lot of time and bandwidth. Furthermore, the server(s) tend(s) to get the 
bottleneck. 

So, the interesting question is, if there is an easy way to combine these 
two ways. 

Cheers,
Wolfgang