[osg-users] Using Kd-tree for spatial data

Robert Osfield robert.osfield at gmail.com
Fri Sep 5 01:22:23 PDT 2008

HI Maruti,

On Fri, Sep 5, 2008 at 9:11 AM, maruti borker <slimshadymaruti at gmail.com> wrote:
> But when i went through the discussion, i found out that only geomety in the
> leaves have seperate kd-tree and not a single kd-tree for the whole scene.
> Correct me if i am wrong.

The use of KdTree on drawable leaves only is done to provide a good
balance between efficiency of intersection test and flexibility.  For
instance the system we have now handles whole scene with moving parts,
if you had a single KdTree you'd need to recompute it all the time.
Also a well balanced scene graph will be spatially distributed so will
the hierarchical bounding volumes that help intersection tests.

Jumping to KdTree for the whole scene graph is technically possible,
but you'll need to build the KdTree yourself, and in terms of
performance vs flexibility tradeoff's is not good, it's a lot of
effort for little gain in performance.


More information about the osg-users mailing list