[osg-users] Further Design Question: KDTree
Paul Melis
paul at science.uva.nl
Wed Jul 16 08:37:43 PDT 2008
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
>
More information about the osg-users
mailing list