Christopher James Huff <cja### [at] earthlinknet> wrote:
> >  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?

Hi there,
 Vlastimil's thesis can be found at:
http://www.mpi-sb.mpg.de/~havran/DISSVH/phdthesis.html

 However, I wouldn't count on using it to tell you how to efficiently code a
kd-tree build routine.  It's extremely light on implementation details.
There's one sentence in section 4.9 that suggests that he may have
implemented his kd-tree in a manner similar to how I implemented mine --
but I've no clue exactly how he did it.

-Daniel Neilson

Post a reply to this message