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 <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>>:
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)
<[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> 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@lists.openscenegraph.org
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
_______________________________________________
osg-users mailing list
osg-users@lists.openscenegraph.org
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
