> 
> 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.
> 

What are you planning on researching for your Ph.D? :)

>  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).

I've now taken a closer look at your code.  I'm guessing that the reason
you are seeing this difference in performance is that we are using
different termination criteria for the construction.  When I build the
tree, I will split even when there is no clean separation.  So if there are two
objects (A and B) where A straddles the splitting plane but B is on one
side, I'll still try to subdivide these to separate out a cell that
contains only B as well as a cell with both.  This would explain the
larger memory use for the scene you were testing.  I think that my method
should be more efficient in performance for scenes with overlapping
objects as long as the memory hit is not too large.  Of course I've just
hypothesized this after looking at both the sets of code, so I'm not sure.
 Stopping the subdivision whenever there is no clean separation (like I
think you are doing) would probably give more stable memory use.

As for overall performance, I've tried rendering a few scenes with both
patches and found mine to have better performance for most of the standard
scenes that I've tried.  Unfortunately I don't have enough memory to try
all the scenes that you've listed but here are some of the results:

A = your patch (-UV -UL +UK)
B = my patch (+MM2)

rings15:
A: 16s parse, 71s trace
B: 11s parse, 81s trace

lattice20:
A: 10s parse, 33s trace
B: 9s parse, 43s trace

tree15:
A: 19s parse, 13s trace
B: 19s parse, 25s trace

patio-radio:
A: 0s parse, 100s trace
B: 0s parse, 96s trace (wrong result?!)

stackertransp:
A: 8s parse, 27s trace
B: 8s parse, 22s trace (wrong result?!)

I received incorrect output from your patch for the last two tests, let me
know if you can verify or if I've set things up wrong.  The problem could
be related to the ray flags bug (see my post in povray.unofficial.patches)

I've run the tests with my current code which I'll post shortly at:
povplace.addr.com/bsppov101.tar.gz

Andrew

Post a reply to this message