"Andrew Clinton" <ajc### [at] uwaterlooca> wrote:
> Have you looked at the patch that I posted to povray.unofficial.patches a
> little while ago?  I implemented the KD-tree from Vlastimil Havran's
> thesis.  Unfortunately I chose to call it a BSP-tree rather than the
> KD-tree, because it seems to be referred to as BSP-tree in other
> raytracers.  I haven't had time to look at your patch yet, but the
> performance is very sensitive to the way in which the tree is constructed.
>  I chose to use the cost function from the thesis to choose splitting
> points along with a depth bound based on the size of the scene, which
> seems to give good performance for most cases.
>
> I've done some work on improving the previous patch to work on meshes and
> fix some bugs (and better comment the code) but haven't had time to
> prepare and test the patch yet.
>
> I will have a look at your code as soon as I have time.

Hi Andrew,
 I had actually noticed that posting in unofficial.patches, but since it was
referring to a BSP tree, I'll admit, I didn't even look at it. My purpose
with porting my kd-tree code into POV-Ray was actually for a learning
experience -- I'm hopeing to use POV-Ray as a base for my Ph.D. research,
so I need familiarity with the codebase.

 I also used the cost function to pick the splitting planes, but I didn't
actually use the depth bound based on the size of the scene. Instead, I
just split until I can't split anymore.

 But, that all said, I've now downloaded and taken a look at your patch.
You're really going to want to look at my kd-tree code. I ran your KD-Tree
on SPD-Rings30 and the results were less than stellar, unfortunately. This
scene contains 567,302 frame level and zero infinite objects. Just to build
the KD-Tree took just shy of a minute using your code -- and just shy of 5
seconds using mine. Trace took about 28 seconds with yours, 24 with mine --
rendering a 400x400 A0.3 image. And lastly, yours required a peak of just
shy of 1.3 gigabytes of RAM for ray tracing (1,273,673,629 bytes to be
exact) whereas my version required just shy of 600 megabytes (581,196,285
bytes to be exact).

-Daniel Neilson

Post a reply to this message