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