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

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

On Tuesday 22 March 2005 22:10, Andrew Clinton wrote:
> 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)).
>
Very good. Thanks for the infomation. 

> 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.
>
Yes, another interesting idea. We could even get along with 256 
booleans in a bitfield and let the hash compute the bit index. 

> 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 
>
Of course. But as this bitfield is stored in one consecutive area in the ray 
data structure, the reset operation is basically a 
  memset(bitfield,0,size);
Especially when combining it with the hash approach introduced by you above, 
the reset for a 256-entry hash is setting 8 integers (with 32bit each) to 0. 
Really cheap. And especially it fits nicely into the cache. 

>  Anyways, the user can
> always be able to store more geometry by going and buying more RAM...
>
Sure. 
But for example I myself cannot go and buy more RAM for the >=25-node P4 HT 
cluster I have access to... Each of these boxes has 1Gb, so the total is 25Gb
which means the cluster can store a lot more scene information than one box. 

Concerning scenes with huge amounts of data: Being able to handle them 
has been a design goal right from the beginning. (Because I am doing these 
planet topography renders: E.g. the easiest way for a flight on Mars would be 
to simply load the complete scene information -- which is 2.4Gb... Currently 
I am handling that with a POVRay-hack which loads only parts of the image 
into RAM -- but it is such a crude hack that I do not dare to publish the 
patch and it requires knowledge of the required area in advance.)

PRIMITIVES
----------

I'm currently making my way through PBRT (not in-depth, yet). 
I like the simplicity in design of their interface for Primitives. 
However, I would do things a little different: 

- All objects live in object coordinates and are instanced for the scene. 
  I.e. all things seen in the scene are "instance primitives". This way one 
  can eliminate one transformation for each instance. 

- There are special parametric transformations which allow e.g. to have 
  1000 objects in a line without instancing them 1000 times. 
  The first problem is how to identify these in an accelerator (e.g. using 
  a pointer and an index mentioned earler by me) but I failed to think up 
  an efficient and simple way to handle that for arbitrary depths. 
  So, I'd suggest to instead use own accelerators for these parametric 
  transformations. The advantage is that the mentioned "objects-in-a-line" 
  trafo could internally do an O(1)-like acceleration in case the objects' 
  AABBs do not overlap much. 

- CSG seems to naturally fit into the framework by using CSG difference 
  and CSG intersection primitives. This would directly allow use of BVH 
  bounding. 
  Andrew, since you are the expert for that: How would you suggest to 
  introduce CSG with Kd-tree bounding when starting with the known 
  "Primitive" from PBRT?
  (I would like to do CSG with just about anything which can possibly be 
  given an inside and an outside, much like POVRay.)
  (BTW, it seems that one could easily allow the user to do a special type of 
  bounding on certain primitives thereby giving an opportunity to compensate 
  for the performance loss at shells7.pov using BSP...)

Another question: Does anybody know a good way to prevent self-shadowing 
(other than the usual min. epsilon depth.)

Regards,
Wolfgang