[osg-submissions] KDTree : intersection

[Robert Osfield]

Hi Adrian,

I've just do a review of your changes, I now understand what the
optimization do - basically improve the intersectAndClip function.
The changes are a bit awkward and miss a few opportunities to optimize
further.  The awkward part come from passing dir and invDir as
parameters, but I can't see anywhere in the code where you are
actually modifying them.  Reflecting on the code it looks like we
needn't ever modify them, so dir is in fact just IntersectKdTree::_d,
something that is already precomuted, its only the invDir you are
adding.  Moving invDir into the IntersectKdTree as a member would
allow us to avoid passing the dir and invDir as a parameters
completely.

The optimization comes by reordering the maths i.e

My original code:

            s = s+(e-s)*(bb.xMin()-s.x())/(e.x()-s.x());

You new code:

            s += dir*(bb.xMin()-s.x())*invDir.x();

If we reoder then we have:

           s += _dir_invDiv_x * (bb.xMin()-s.x());

Where _dir_invDiv_x = _d/_d.x();

If this makes sense then we can port the code across to use this method.

Robert.