[osg-submissions] KDTree : intersection

[James Killian]

FYI

1>..\..\..\OpenSceneGraph\src\osg\KdTree.cpp(108) : warning C4018: '<=' : 
signed/unsigned mismatch



James Killian
----- Original Message ----- 
From: "Robert Osfield" <robert.osfield at gmail.com>
To: "OpenSceneGraph Submissions" <osg-submissions at lists.openscenegraph.org>
Sent: Wednesday, July 16, 2008 6:08 AM
Subject: Re: [osg-submissions] KDTree : intersection


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