[osg-users] Further Design Question: KDTree

Paul Melis paul at science.uva.nl
Wed Jul 16 09:02:57 PDT 2008


Robert Osfield wrote:
> 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.
>   
Right, but this does depend on the KD-tree implementation a bit as well. 
A line of sight intersection check can be special cased compared to a 
general intersection traversal.

Paul
> Robert.
> _______________________________________________
> osg-users mailing list
> osg-users at lists.openscenegraph.org
> http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
>   




More information about the osg-users mailing list