[osg-submissions] KDTree : intersection

[Adrian Egli OpenSceneGraph (3D)]

Hi Robert,

this make sense. the code is not only reordering it's also more robust. e.x
- s.x can be zero. it means that s.x == e.x , so we can assume that invDir.x
== 0.0 doesn't destroy our math :-)

have a look at.......

bool KdTree::intersect(const osg::Vec3& start, const osg::Vec3& end,
LineSegmentIntersections& intersections) const
{
    ...
    osg::Vec3 dir(end-start);

     const osg::Vec3 invDir(
            dir.x() != 0.0f ? 1.0f/dir.x() : 0.0f,
            dir.y() != 0.0f ? 1.0f/dir.y() : 0.0f,
            dir.z() != 0.0f ? 1.0f/dir.z() : 0.0f
        );


if you would prefere a member variable, then we can change it. but take care
about the fix

_dir_invDiv_x = d.x() == 0.0f ? osg::Vec3f(0.0f,0.0f,0.0f) :  _d/_d.x();
_dir_invDiv_y = d.y() == 0.0f ? osg::Vec3f(0.0f,0.0f,0.0f) :  _d/_d.y();
_dir_invDiv_z = d.z() == 0.0f ? osg::Vec3f(0.0f,0.0f,0.0f) :  _d/_d.z();


****************************************************************************************************

SORRY: i just posted a second kdTree.cpp fix, may we can do this invDir
change in the latest kdTree.cpp




****************************************************************************************************2008/7/15
Robert Osfield <robert.osfield at gmail.com>:

> 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.
> _______________________________________________
> osg-submissions mailing list
> osg-submissions at lists.openscenegraph.org
>
> http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegraph.org
>



-- 
********************************************
Adrian Egli
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscenegraph.org/pipermail/osg-submissions-openscenegraph.org/attachments/20080716/294ff151/attachment.htm>