Hello,
I think that I have some idea that may speed up renders, BUT i'm still 
"lame" in Pov code, so following ideas might seem very stupid :-/ is so - 
please tell me ;)

I see that using photons and/or radiosity (both - with big count/spacing) 
terrible slows down render.

If I understood corretly - each photons is saved, and most important 
function needs to check if there is a photon that hits some (x,y,z) point 
(with some tollerance ofcourse).

Let's discuss this problem in 2-D version - photons shining on plane (on 
line) :

12345678 = x
-------- plane y=0

**-*----

there are 2 photons, and bin-tree (in 3d - octall-tree) stors them in 
format :

is there any photon in 1..4 ? etc...

    root
    / \  
  1-4  5-8(no)
 /   \
1-2  2-3(no)
/ \
*  *

is this correct ?

If so, then searching this tree (for large numbers of photons, like 80 MB 
ram) tooks so much time and slows down *render* time (I know that photon-
shooting is ofcourse bigger fot bigger count).

So, any algrithm that will be able to 
a) remember (x,y,z) point
b) tell is ther some point in (x,y,z) - (x+e,y+e,z+e) area

that will be faster then current implementation - will speed up rendering ?

If so - I have some promising ideas to test :)

Any opinions, suggestions are welcomed, I want to do somthing for POV but  
need Yours help :P

-- 
#macro g(U,V)(.4*abs(sin(9*sqrt(pow(x-U,2)+pow(y-V,2))))*pow(1-min(1,(sqrt(
pow(x-U,2)+pow(y-V,2))*.3)),2)+.9)#end#macro p(c)#if(c>1)#local l=mod(c,100
);g(2*div(l,10)-8,2*mod(l,10)-8)*p(div(c,100))#else 1#end#end light_source{
y 2}sphere{z*20 9pigment{function{p(26252423)*p(36455644)*p(66656463)}}}//M

Post a reply to this message

In article <Xns### [at] 204213191226>, "Rafal 'Raf256' Maj"
<raf### [at] raf256com> wrote:

> there are 2 photons, and bin-tree (in 3d - octall-tree) stors them in

How did you guess this?  Surely not from the source code...

Photons are stored in a kd-tree and radiosity data is stored in an oct-tree.

>    root
>     / \
>   1-4  5-8(no)
>  /   \
> 1-2  2-3(no)
> / \
> *  *

Unless this is an extremly simplified example, this looks very much like a
binary tree to me.  Both, kd-trees and oct-trees, are fairly advanced data
structures compared to simple binary trees.

Apart from that you may want to do some profiling before you jump to the
conclusion that the tree searchs are slow rather than more frequently used
code (such a the priority queue for photons).  If there is any benefit from
using an oct-tree for photons may sound like an interesting question, but
without a very good understanding of photons that is not easy to answer, let
alone implement.


    Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

"Thorsten Froehlich" <tho### [at] trfde> wrote in
news:3ddd4070$1@news.povray.org 

>> there are 2 photons, and bin-tree (in 3d - octall-tree) stors them in
> How did you guess this?  Surely not from the source code...

This technique is used in most 3d Engines (i.e. in Quake-2)

> Photons are stored in a kd-tree and radiosity data is stored in an
> oct-tree. 

What's the difference beetwen them ? In shortcut, if You can explain 
please.
 
>>    root
>>     / \
>>   1-4  5-8(no)
>>  /   \
>> 1-2  2-3(no)
>> / \
>> *  *
> Unless this is an extremly simplified example, this looks very much
> like a binary tree to me.  Both, kd-trees and oct-trees, are fairly
> advanced data structures compared to simple binary trees.

I was quesing that for 1d surfaces we use bin-tress, and for 2d-surfaces 
simmilar structure, but each parent have 4 childs. And for 3 directions - 8 
childs. 

> Apart from that you may want to do some profiling before you jump to
> the conclusion that the tree searchs are slow rather than more
> frequently used code (such a the priority queue for photons).  If
> there is any benefit from using an oct-tree for photons may sound like
> an interesting question, but without a very good understanding of
> photons that is not easy to answer, let alone implement.

I found in help :
 The keyword gather allows you to specify how many photons are gathered at
 each point during the regular rendering step.
so I was wrong, more photons are gathered during render also.

One uf my ideas was to generate standart texture (image-map) during 
shooting, and just lay it on may texture of collecting object.

I will try to do this for plane - to warm up with patching POV.
Idea is simple, is stored surfaced photon is saved to hdd in <x,z> foramat.
Test scene is somthing like :
  plane{y,0} sphere{..glass.. photons { refract 1 target } }
Then, my program generates .bmp texture basing on data saved during 
shooting. In final step - i render image with no photons, but using 
image_map on plane instead.

I hope it would bring a big difference in speed, and that it could be used 
to speed up other shapes in next versions



-- 
#macro g(U,V)(.4*abs(sin(9*sqrt(pow(x-U,2)+pow(y-V,2))))*pow(1-min(1,(sqrt(
pow(x-U,2)+pow(y-V,2))*.3)),2)+.9)#end#macro p(c)#if(c>1)#local l=mod(c,100
);g(2*div(l,10)-8,2*mod(l,10)-8)*p(div(c,100))#else 1#end#end light_source{
y 2}sphere{z*20 9pigment{function{p(26252423)*p(36455644)*p(66656463)}}}//M

Post a reply to this message

In article <Xns### [at] 204213191226>, "Rafal 'Raf256' Maj"
<raf### [at] raf256com> wrote:

>> Photons are stored in a kd-tree and radiosity data is stored in an
>> oct-tree.
>
> What's the difference beetwen them ? In shortcut, if You can explain
> please.

From an data structure perspective an oct-tree is a special case of an
unbalanced three dimensional kd-tree (3d-tree).  The oct-tree in POV-Ray is
consequently implemented as a linked structure.  The kd-tree used by photons
uses an array as storage and is balanced.

>> Unless this is an extremly simplified example, this looks very much
>> like a binary tree to me.  Both, kd-trees and oct-trees, are fairly
>> advanced data structures compared to simple binary trees.
>
> I was quesing that for 1d surfaces we use bin-tress, and for 2d-surfaces
> simmilar structure, but each parent have 4 childs. And for 3 directions - 8
> childs.

That is the basic concept, but it isn't all that simple.

Essentially, a kd-tree does not have to separate space in a symmetric manner
while an oct-tree does exactly that.  One major difference for the
implementation is the already noted design decision of using an array or a
linked structure.  There are space and efficiency tradeoffs.

And example of an oct-tree:
<http://www.npac.syr.edu/copywrite/pcw/node279.html>

An example of a two dimensional kd-tree (a 2d-tree):
<http://www-hpcc.astro.washington.edu/faculty/marios/papers/perform/node3.ht
ml>

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

"Thorsten Froehlich" <tho### [at] trfde> wrote in
news:3ddd5f51@news.povray.org 

[...]

Thank You, and most important for me thing, will making very fast structure 
to hold 3d points improve speed of photons? i also think that adding 
trace() function to it may improve isosurfaces.

IMHO *VERY* much objects can be optimies in speed in cost of memory.

Is this prototype correct (to be usefull for photons, media, isosurfaces) :

class cSomeArray() {
  // ...
  cSomeArray();
  ~cSomeArray();
  void AddPoint(DBL x,DBL y,DBL z);  
  void* PointInside(DBL x,DBL y,DBL z, DBL epsilon=1e-3);
  tPoint Trace(DBL x1,DBL y1,DBL z1, DBL x2,DBL y2,DBL z2);
}

Array will be optimise for fast reading from it by cost of writing and 
memory usage

-- 
#macro g(U,V)(.4*abs(sin(9*sqrt(pow(x-U,2)+pow(y-V,2))))*pow(1-min(1,(sqrt(
pow(x-U,2)+pow(y-V,2))*.3)),2)+.9)#end#macro p(c)#if(c>1)#local l=mod(c,100
);g(2*div(l,10)-8,2*mod(l,10)-8)*p(div(c,100))#else 1#end#end light_source{
y 2}sphere{z*20 9pigment{function{p(26252423)*p(36455644)*p(66656463)}}}//M

Post a reply to this message

"Rafal 'Raf256' Maj" <raf### [at] raf256com> wrote in 
news:Xns### [at] 204213191226

> also think that adding 
> trace() function to it may improve isosurfaces.

...by pre-counting it into mesh, or as above into structure made from 3d 
points. While using simple 3d array is nonsense because even 500x500x500 
will almost totaly eat up memory, using structures that inteligently save 
lit areas might be usefull for some situations.

If we ignore trace() function, the solution for 1D is a modiffied binary 
tree :

0        32   48   64
         /-------\ /\  this shape will be saved +/- in format :

area 0..32 is totaly empty

area 32..64 is complicated:
  area 32..48 is toatly lit, shape L-border 
     in point 32 with normal __ , texture __ etc
  area 48-64 is complicated:
    area 48..56 is LIT, with R-border in 56 with normal __ etc
  [...]

So each parent has 2 childs, each child can be :
- pointer to actual child structure
- information that child area is 100% empty
- information that child area is 100% LIT

plus - some extra informations for borders like normals (maybe pigments)  

Ofcourse final version will should be much more sufisticated to get reale 
speed improvment

-- 
#macro g(U,V)(.4*abs(sin(9*sqrt(pow(x-U,2)+pow(y-V,2))))*pow(1-min(1,(sqrt(
pow(x-U,2)+pow(y-V,2))*.3)),2)+.9)#end#macro p(c)#if(c>1)#local l=mod(c,100
);g(2*div(l,10)-8,2*mod(l,10)-8)*p(div(c,100))#else 1#end#end light_source{
y 2}sphere{z*20 9pigment{function{p(26252423)*p(36455644)*p(66656463)}}}//M

Post a reply to this message

Rafal 'Raf256' Maj <raf### [at] raf256com> wrote:
>   void* PointInside(DBL x,DBL y,DBL z, DBL epsilon=1e-3);

  This is completely unrelated to the issue in question, but as you are
wanting to make a good object-oriented implementation, I would like to
note that 'void*' is usually against OO principles and extremely rarely,
if at all, needed in a well-designed OO program. (I have never used it
in my programs, that's for sure.)
  (Of course if you are doing this as a POV-Ray patch, you might need to
use it in some places, as the POV-Ray source is still basically C, where
using 'void*' is more common.)

  By the way, isn't that a rather large value for epsilon? Such large value
can introduce visible artifacts.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message