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

[<ajc...@en...>]

> 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. 
> 

I think we could probably get away with an even simpler hash table.  For
example, just use a fixed-size table (eg. 256 entries), and allow for some small
number of re-intersection tests (in this case, maybe around 1/128 of tests would
have a collision).  This would be really simple to implement, fast, and uses
little space while getting most of the benefit of other data structures.

> 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. 
> 

The problem with using boolean values for this purpose is that we need some way
to reset them once the ray intersections have been completed for a single ray (I
thought about this before when working on the POV-Ray patch).  This is possible
but it will require an auxiliary storage for the list of primitives, so that we
can go back and reset the booleans when the ray is completed.

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

I remember reading somewhere that for a good accelerator, the number of cells
"stabbed" by a ray will be something like O(n^(1/3)) (cube root).  If we only
get the first intersection, its probably more like O(log(n)).  So I'd imagine
that in almost all cases there will be less than ~256 objects intersected by the
ray, for scenes that fit in memory.

> <Splitting the scene information>
> 

This is an interesting question and it should require more investigation. 
However, I'm still concerned that this type of scene splitting will be overkill
in almost all cases.  It would be much better to have good support for
instancing, geometry/texture caching, and procedurals so that the user can
actively control the memory use of their scene.  Anyways, the user can always be
able to store more geometry by going and buying more RAM...

Andrew



----------------------------------------
This mail sent through www.mywaterloo.ca