[osg-submissions] KDTree : intersection

[Robert Osfield]

Hi Adrian,

I have gone for the precompute the _d_invX, _d_invY,  _d_invZ, this is
now checked in to SVN.

Robert.

On Wed, Jul 16, 2008 at 8:54 AM, Adrian Egli OpenSceneGraph (3D)
<3dhelp at gmail.com> wrote:
> 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
> _______________________________________________
> osg-submissions mailing list
> osg-submissions at lists.openscenegraph.org
> http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegraph.org
>
>