> 
> I just sorted the points along each axis, and repeatedly split the point 
> sets. It seems quite efficient (splitting the first axis consists of 
> little more than dividing an integer by 2), and the result should be as 
> close to perfectly balanced as you can get. Solving this problem is one 
> reason I haven't done a KD-tree for finite-sized objects yet...I'll have 
> to look up that thesis. Got a reference?

In fact, even with points you may be better off with *not* splitting on
the median of the points.  The issue arises when your set of points is not
homogeneous - in these cases, your application (eg. the nearest neighbour
search for photons) may perform better when you split at a different point
that minimizes the cost of this operation.  Vlastimil Havran's thesis
describes this very well (IMHO, see link from other post).  So the 
perfectly balanced tree may not be the most efficient at rendering time.

For supporting finite-sized objects the key is to develop a cost function
that minimizes the cost of intersecting a ray with the KD-tree node.  See
chapter 4 for more info on this.

Andrew

Post a reply to this message

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

"Andrew Clinton" <ajc### [at] uwaterlooca> wrote:
> What are you planning on researching for your Ph.D? :)

 Still deciding (I've just finished my first 8 months), though I'm 98%
certain it'll be in the area of ray tracing non-static scenes.

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

 When I was first developing my kd-tree codebase I was actually encountering
a problem with infinite recursion when trying to split the objects A & B as
you decribe. What was happening is that I was constantly finding the same
splitting plane level after level until I either killed the process or ran
out of memory -- since I don't have a depth bound on my tree. My 'fix' was
to split only when I could find a splitting plane that had at least one
object on either side of the plane (or to split when I could construct a
sensible empty leaf). I can't help but wonder if you're encountering a
similar problem, but that since you have a depth bound it just means that
you're filling out the tree rather than hitting infinite recursion.

 My codebase has changed sufficiently since then, though, that I wonder if I
no longer have that problem... See the use of the emptyLeafs parameter for
Build_KD_Tree and Find_Splitting_Plane -- I should be able to use that
parameter to prevent splits in the same place in consecutive levels.

 I certainly agree that being able to split those types of object sets would
be very beneficial.

> 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?!)

 Had you mixed up A & B for some of these? You mention below that there's an
incorrect result for my version (A) on the last two, but you put the note
beside the timing for your patch (B).

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

 Ack! Thank you for pointing that out. I can't believe that I didn't even
notice that one. It would appear that my patch isn't doing shadows
correctly with the radiosity calculations. Odd, since it does them
correctly on all the SPD scenes... Well, there goes any hope at doing any
real work today... ;)

-Daniel Neilson

Post a reply to this message

"Daniel Neilson" <dneilson@here;here.is:cs.ualberta.ca> wrote:
> > 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)
>
>  Ack! Thank you for pointing that out. I can't believe that I didn't even
> notice that one. It would appear that my patch isn't doing shadows
> correctly with the radiosity calculations. Odd, since it does them
> correctly on all the SPD scenes... Well, there goes any hope at doing any
> real work today... ;)

 That was easy. Fixed it. Just comment out all lines of the form "if
(shadow_flag) return true;" in Intersect_KD_Tree(). Seems that povray
doesn't use a bounded intersection test for shadow rays for some reason
that I won't claim to understand.

-Daniel

Post a reply to this message

>  Had you mixed up A & B for some of these? You mention below that there's an
> incorrect result for my version (A) on the last two, but you put the note
> beside the timing for your patch (B).
> 

I'm sorry, I did have A and B mixed up.  A == My patch, B == Your patch,
in the above post.

Post a reply to this message

In article <web.4096804366fba342302f86c60@news.povray.org>,
 "Daniel Neilson" <dneilson@here;here.is:cs.ualberta.ca> wrote:

> "Andrew Clinton" <ajc### [at] uwaterlooca> wrote:
> > What are you planning on researching for your Ph.D? :)
> 
>  Still deciding (I've just finished my first 8 months), though I'm 98%
> certain it'll be in the area of ray tracing non-static scenes.

In that case, you may want to look at BKD-trees. They're like KD trees, 
but easier to modify without completely rebuilding the tree.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/

Post a reply to this message