[osg-users] Further Design Question: KDTree

Robert Osfield robert.osfield at gmail.com
Wed Jul 16 08:44:22 PDT 2008

On Wed, Jul 16, 2008 at 4:37 PM, Paul Melis <paul at science.uva.nl> wrote:
> By the way, I just took a quick look at the current KD-tree implementation.
> Am I seeing misreading the code or do tree nodes currently store a full
> bounding box instead of just the appropriate split plane and its value on
> the split axis?
> Intersection also seems to do a test against a bounding box...

It stores a full bounding box.  I did experiment with just testing the
central splits but didn't get any conclusive improvement, and in quite
a few cases worse performance.

Storing full bounding box does effectively mean that its binary BVH.

I do expect we'll be do better than the current implementation in SVN,
as we all learn more about optimizing this type of operation.
Consider what we have as flag in sand marking out territory, but the
fort is far from complete yet.

Context is absolutely crucial as well.  Optimizing KdTree further will
be up against a law of diminishing returns, as the main bottleneck
that most users will see is the intersection traversal
cost/intersection hit recording, focusing on KdTree implementation is
ignoring what is now the biggest bottleneck in getting further
significant performance improvement.


More information about the osg-users mailing list