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