[osg-users] Further Design Question: KDTree

[Paul Melis]

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

Paul

Paul Melis wrote:
> Just a note on this topic...
>
> Adrian Egli OpenSceneGraph (3D) wrote:
>> I understand your comment really well, and w.r.t. to building 
>> performance
>> this is true. for all paged database the building performance is much 
>> more
>> important then the intersection check. Especially for terrain rendering.
> I haven't looked in detail what splitting method the current KD-tree 
> implementation uses, but the "binning algorithm" in section 3 of [1] 
> seems to provide quite a good trade-off between tree quality and build 
> time, while being fairly simple to implement. They basically use a 
> clever coarse-grained SAH evaluation for the upper part of the tree 
> and switch to full SAH for nodes with a small number of primitives. 
> The "parallel" in the title does not apply to that section, although 
> the authors have gone quite far in doing parallel tree building.
>
> And if low build times is really the main goal for the intersection 
> structure, especially for paged databases, then an alternative 
> structure to a KD-tree might be worth exploring. Bounding volume 
> hierarchies are awefully fast to construct, at the cost of having some 
> problems with models containing wildly different sized primitives. But 
> even for the latter problem solutions are beginning to emerge, e.g. 
> the edge volume heuristic ([2]).
>
> [1] "Highly parallel fast kd-tree construction for interactive  ray 
> tracing of dynamic scenes" (kesen.huang.googlepages.com/Intel-EG07.pdf)
> [2] "The Edge Volume Heuristic - Robust Triangle Subdivision for 
> Improved BVH Performance"
>
> In case any students are looking for an interesting topic, I suspect 
> trying out the different options would make for a great master's 
> thesis...
>
> Paul
>
>> The question is how we can design the kdTree build for most 
>> application working
>> with max performance. Either we reimplement a second, third, .. 
>> kdTree class or we use the
>> BuildOptions for the decision how the tree should be constructed.
>> For each application it can be different, event for different 
>> geometries we can have different builds.
>> Actually we have a new member in osgDB::Registry to define the 
>> KdTreeBuilder with it's option and
>> the kdTree prototype. If we assume that each user can has he's own 
>> kdTree, then the option
>> would no longer be needed, because we can handle the different 
>> techniques in the kdTree
>> subclasses. So should we think this way, or should we think in 
>> combination. We could
>> use our own inherited kdTree classes for own modifications, and we 
>> could implement in the default
>> kdTree class some common building techniques. May the user can handle 
>> the building by a simple enumeration
>> in the buidling option, like  { FAST_BUILD ,  
>> CENTER_TOPOLOGY_ALIGNED  , ...    , SAH , ..  }
>> or what would be best design ?
>> i am aware of the real time openGL rendering, and for what we use the 
>> line intersection check. and i am also aware
>> that each kdTree tuning is 'overhead' for current applications. but 
>> may for collision checks, and so on, we can get
>> better performance linearly to the kdTree perf win in each 
>> optimisation we do.
>>
>> /adrian
>>
>>
>> 2008/7/16 Robert Osfield <robert.osfield at gmail.com 
>> <mailto:robert.osfield at gmail.com>>:
>> Hi Adrian,
>>
>> I have just done a review of your latest KdTree, and now understand
>> the optimization - it's actually one I considered too, but didn't
>> implement out of concern of build performance.  Your results suggest
>> the the new bb compute code adds a further 50% in build time over the
>> previous technique, you don't mention the performance figures.   A 50%
>> hit on build time is not good news for people who are paging
>> databases.   The performance improvement on intersection also needs to
>> be put in the context of how the
>> IntersectionVisitor/
>>
>>     LineSegmenetIntersector are used typically, as the
>>     costs of scene graph traversal typically swap that of KdTree 
>> traversal
>>     so a 50% improvement in KdTree might only give us 5% improvement, 
>> alas
>>     the build time is far less swamped by scene graph traversal.
>>
>>     I think the best one could do to try and balance things for 
>> different
>>     usages - would be to either have different KdTree subclasses or have
>>     different build/intersect algorithms that are chosen by KdTree
>>     options.  Note, we already have a KdTree::BuildOptions object 
>> that is
>>     passed into the build option already - this could be used to provide
>>     hints on whether quick builds vs slower builds that optimize
>>     intersections should be preferred.
>>
>>     Robert.
>>
>>     On Wed, Jul 16, 2008 at 8:46 AM, Adrian Egli OpenSceneGraph (3D)
>>     <3dhelp at gmail.com <mailto:3dhelp at gmail.com>> wrote:
>>     > Hi Robert,
>>     >
>>     > This morning i was about 1hour in train, and reviewed again the
>>     kdTree
>>     > implementation. Yesterday i wrote that the kdTree has some
>>     strange behaviour
>>     > when triangles have equal center points. yes this is still true,
>>     and we can
>>     > (as you told) ignore such bad geometries. but one thing i worked
>>     out is that
>>     > the kdTree isn't oriented to the geometry topology, assume we
>>     have a torus
>>     > like box, then the bounding boxes are far away from a optional
>>     kdTree-based
>>     > bounding box hierarchy. for line intersection checks this is not
>>     as bad as
>>     > it sounds, but for further more complex checks, like polytop
>>     intersection,
>>     > haptic rendering this will turn in a more expensive overhead. so
>>     i propose
>>     > to use the latest code, with the ADRIAN_DIVIDE_BB_FIX define
>>     switch on.
>>     >
>>     > to compare the kdTree, performance, nodes, leafs, i added some
>>     statistics to
>>     > the code: #define VERBOSE_OUTPUT_TREE_INFO
>>     >
>>     > the building time still fast enough, but of course no for free
>>     :-(, the tree
>>     > is smaller. he is not just smaller, it's more correct w.r.t
>>      kdTree spatial
>>     > datastructure / bounding hierarchy.
>>     >
>>     > adrian
>>     >
>>
>>
>>
>> -- 
>> ********************************************
>> Adrian Egli
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> osg-users mailing list
>> osg-users at lists.openscenegraph.org
>> http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org 
>>
>>   
>
> _______________________________________________
> osg-users mailing list
> osg-users at lists.openscenegraph.org
> http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
>