In article <pan### [at] uwaterlooca>,
 "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.

Heh...so I'm not the only one. I constructed a BSP tree to make the 
voronoi pattern more efficient, and only later (when I decided to use 
the data structure that made photons so efficient) found that the type 
of BSP tree I created was called a KD-tree. My implementation is nicely 
general, and can be used for anything that needs to handle a large 
number of points, but it is restricted to points.


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

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