Nicolas Calimet <pov### [at] freefr> wrote:
: 	Go on, go on Nathan !

  The warning about memory consumption should not be taken lightly.

  Let me try to approximate the memory consumption of this kind of tree:

  1) Besides the data, a tree node will need at least two pointers
(one for reflection and another for refraction). Three if you have to
be able to go upwards in the tree. Since I don't know if its necessary,
let's just say that you need two pointers per node. One pointer takes
(in most systems) 4 bytes, so 8 bytes of extra data is needed per node.

  2) If every node is allocated from memory some extra memory is needed
by the operating system to handle the allocated block. However, since we
are only adding to the tree and we don't have to remove, we can quite easily
"allocate" nodes from an array, thus saving this needed extra memory.
  However, it needs to be a dynamic array and thus needs temporarily extra
memory when the array gets full and has to be expanded. Since this temporary
extra memory needed is heavily dependant on the algorithm used and is just
that, ie. temporary, let's just forget it.

  3) So what kind of data do we need in each node? At least we need the
color of that node, and a color needs three color components. Color components
are usually handled as floats in povray for practical reasons (we can't use,
for example, a byte per component since the destination file format may need
more than 8 bits per color component, eg. 16 bits).
  We also need some depth information in order to be able to make depth
blurring. This could be the distance between the origin of the ray and the
point this node is representing. One float suffices here.
  We also need a reflection amount, ie. how much is taken from the color
of the point itself and how much from the reflection (exactly what the
'reflection' in the 'finish' block does). Another float for this.
  We also need the refraction amount for the same purpose. Another float.

  So we have 6 floats for the data of a node. In most systems a float type
takes 4 bytes so it makes 24 bytes.
  Adding the two pointers in the node we get a total of 32 bytes per node.

  4) How many nodes will there be in the tree?
  At the first recursion level (ie. the rays shot from the camera) the number
of nodes is exactly the number of rays sent from the camera.
  If we are not using antialiasing, the number if easy: It's exactly the
number of pixels in the image.
  What happens if we are using antialiasing? This is more problematic. Do
we just create one node per pixel or do we create one node per ray?
  To get an accurate result I think we need a node per every ray sent since
although they are sent in almost the same direction they may hit the scene
very far away from each other (eg. at the border of an object; one ray hits
the object, other ray misses the object and hits whatever was behind it,
which can be thousands of units away).
  So how many pixels need antialiasing in an average scene? It depends
heavily in the scene used. It could vary from 10% to more than 50%.
  Let's just make a compromise and say that 25% of the pixels need
antialiasing. By default 8 extra rays are sent for the antialiasing calculation
so the total number of rays sent is:
  nodes1 = pixels+pixels*0.25*8

  5) How many nodes will be generated in subsequent recursions?
  Again, it depends on the scene. If there are no reflections nor transparent
objects, then none.
  But since the whole point of this tree was to calculate blurred reflection
(and refraction) let's suppose there are reflecting and refracting objects.
  How many percent of the screen will be covered by reflecting/refracting
objects? I don't know. Let's just take a wild (and nice) guess and say
that 20% (in the worst cases it may be even 100% if we have slightly reflecting
walls, floors, etc).
  If there's only one reflecting object (which doesn't reflect itself) then
the amount of extra nodes is only 20% of the nodes in the first recursion.
However, most scenes are more complex than that. There may be many reflecting
objects and even refracting and reflecting ones (like glass).
  So let's take both cases separately:

  5.1) If there are only reflecting objects and no refraction then the
amount of nodes doesn't explode, although we still have many of them.
  Now here kicks in the max trace level. Let's just take the default of 5
(althought this may not be enough if the objects are very reflective and
they reflect each other).
  The number of nodes in the second recursion level will then be:
  nodes2 = nodes1*0.2

  Let's suppose that about 10% of the reflected rays hit another reflecting
object. This means that the number of nodes in the third recursion will be:
  nodes3 = nodes2*0.1

  The general formula for all nodes in recursion level 4 and subsequent will
then be:
  nodes4 = nodes3*(1.1^(reclevel-3)) = nodes3*1.21

  The total number of nodes for 5 recursion levels will then be:
  total = nodes1+nodes2+nodes3+nodes4

  Now, nodes1 depends on the resolution of the image. What resolution could
we use? I think we can't restrict ourselves to a too low resolution since
that would limit too much. I think that a resolution of 1024x768 could be
good to effectively test the memory consumption.
  So: nodes1 = 1024*768+1024*768*0.25*8 = 2359296
      nodes2 = 2359296*0.2 = 471859
      nodes3 = 471859*0.1 = 47185
      nodes4 = 47185*1.21 = 57093
      total = 2935433 nodes


  5.2) If we have a glass object the number of nodes will be much higher.
  In the first recursion level 20% of the rays will hit the glass object and
they will generate two objects (one for reflection and the other for
refraction). If we suppose that the glass object is the only
reflecting/refracting object in the scene then the reflected rays will only
cause one extra node. The refracting rays will, however, hit the glass
object again and cause two more nodes, and so on.
  At recursion level 2 there will be:
  nodes2 = 2*nodes1*0.2

  Half of those will create two new nodes each, so at recursion level 3 we
have:
  nodes3 = 2*nodes2/2 = nodes2

  In general we will have:
  nodes3 = (reclevel-2)*nodes2

  total = nodes1+nodes2+nodes3

  So: nodes1 = 2359296
      nodes2 = 943718
      nodes3 = 3*943718 = 2831155
      total = 6134169

  If we had used more than one glass sphere, the total number of nodes would
have been a lot higher.

  So since each node took 32 bytes of memory, in the first case the tree
will take 93933856 bytes = 89.5 Megabytes.
  In the second case it will take 196293408 bytes = 187 Megabytes.

  Those 100-200 Megabytes are out from the memory usable by the rest of the
scene so using very complex scenes may not be possible.
  And note that I used very nice suppositions. If the scene had several glass
objects or the recursion level was higher than 5, the memory consumption could
easily go to Gigabytes. I also used rather small percents; if the
reflecting/refracting objects took more screen space the memory consumption
would increase accordingly.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message