Hi Robert,
thanks for patching the problem. Your fix is a nice solution (and readable, as
you say). Anyway, from the point of robustness, it is not as strong as my
solution. If I would have more time, it would be very interesting to try to
create models to demonstrate the problems. But regular users will probably
never see them. So, for lack of time, I think your solution is a good one and
sufficient for everyday use. We can use it untill somebody would need even more
robust approach and provides the testing models.
> your changes [...] also have the bug that the line segment
> length can grown outwards from the original start and end points.
This is intentional solution to be sure about floating computation robustness.
At the same time, it does not complicate the code and growing out of start and
end points does not affect the collision routines in any harmful way. But I
might overlook something. Anyway, clipping it to start and end points follows
your design approach and robustness level that you target.
Thanks for fixing it. It was on my priority list, so I am happy.
John
On Monday 02 of September 2013 10:42:39 Robert Osfield wrote:
> Hi John,
>
> I have just done a review of your changes and feel that they more
> convoluted than is necessary and also have the bug that the line segment
> length can grown outwards from the original start and end points.
>
> What I have just tried out is changing the code to use a fixed epsilon, but
> have the intersection ratio along the line segment computed with an epsilon
> offset that either pushes the computed intersection with the bounding box
> outwards back towards the original line segment end. I have also added
> clamping to prevent the line segment ends from migrating outwards. The
> code is much simpler, faster and easier to read and I believe should be
> more robust. The only part I think that is something that might need
> revision is the epsilon we choose, I've gone for 1e-13 as you did, but it
> really needs testing against problem data.
>
> Changes are now checked into svn/trunk.
>
> Cheers,
> Robert.
>
> Index: src/osgUtil/LineSegmentIntersector.cpp
> ===================================================================
> --- src/osgUtil/LineSegmentIntersector.cpp (revision 13735)
> +++ src/osgUtil/LineSegmentIntersector.cpp (working copy)
> @@ -244,7 +244,6 @@
> osg::ref_ptr<LineSegmentIntersector> lsi = new
> LineSegmentIntersector(_start, _end);
> lsi->_parent = this;
> lsi->_intersectionLimit = this->_intersectionLimit;
> - lsi->_epsilon = this->_epsilon;
> return lsi.release();
> }
>
> @@ -279,7 +278,6 @@
> osg::ref_ptr<LineSegmentIntersector> lsi = new
> LineSegmentIntersector(_start * inverse, _end * inverse);
> lsi->_parent = this;
> lsi->_intersectionLimit = this->_intersectionLimit;
> - lsi->_epsilon = this->_epsilon;
> return lsi.release();
> }
>
> @@ -486,18 +484,11 @@
> osg::Vec3d bb_min(bbInput._min);
> osg::Vec3d bb_max(bbInput._max);
>
> - // expand the extents of the bounding box by the epsilon to prevent
> numerical errors resulting in misses.
> - bb_min.x() -= _epsilon;
> - bb_min.y() -= _epsilon;
> - bb_min.z() -= _epsilon;
> - bb_max.x() += _epsilon;
> - bb_max.y() += _epsilon;
> - bb_max.z() += _epsilon;
> + double epsilon = 1e-13;
>
> // compate s and e against the xMin to xMax range of bb.
> if (s.x()<=e.x())
> {
> -
> // trivial reject of segment wholely outside.
> if (e.x()<bb_min.x()) return false;
> if (s.x()>bb_max.x()) return false;
> @@ -505,13 +496,15 @@
> if (s.x()<bb_min.x())
> {
> // clip s to xMin.
> - s = s+(e-s)*(bb_min.x()-s.x())/(e.x()-s.x());
> + double r = (bb_min.x()-s.x())/(e.x()-s.x()) - epsilon;
> + if (r>0.0) s = s + (e-s)*r;
> }
>
> if (e.x()>bb_max.x())
> {
> // clip e to xMax.
> - e = s+(e-s)*(bb_max.x()-s.x())/(e.x()-s.x());
> + double r = (bb_max.x()-s.x())/(e.x()-s.x()) + epsilon;
> + if (r<1.0) e = s+(e-s)*r;
> }
> }
> else
> @@ -521,21 +514,22 @@
>
> if (e.x()<bb_min.x())
> {
> - // clip s to xMin.
> - e = s+(e-s)*(bb_min.x()-s.x())/(e.x()-s.x());
> + // clip e to xMin.
> + double r = (bb_min.x()-e.x())/(s.x()-e.x()) - epsilon;
> + if (r>0.0) e = e + (s-e)*r;
> }
>
> if (s.x()>bb_max.x())
> {
> - // clip e to xMax.
> - s = s+(e-s)*(bb_max.x()-s.x())/(e.x()-s.x());
> + // clip s to xMax.
> + double r = (bb_max.x()-e.x())/(s.x()-e.x()) + epsilon;
> + if (r<1.0) s = e + (s-e)*r;
> }
> }
>
> // compate s and e against the yMin to yMax range of bb.
> if (s.y()<=e.y())
> {
> -
> // trivial reject of segment wholely outside.
> if (e.y()<bb_min.y()) return false;
> if (s.y()>bb_max.y()) return false;
> @@ -543,13 +537,15 @@
> if (s.y()<bb_min.y())
> {
> // clip s to yMin.
> - s = s+(e-s)*(bb_min.y()-s.y())/(e.y()-s.y());
> + double r = (bb_min.y()-s.y())/(e.y()-s.y()) - epsilon;
> + if (r>0.0) s = s + (e-s)*r;
> }
>
> if (e.y()>bb_max.y())
> {
> // clip e to yMax.
> - e = s+(e-s)*(bb_max.y()-s.y())/(e.y()-s.y());
> + double r = (bb_max.y()-s.y())/(e.y()-s.y()) + epsilon;
> + if (r<1.0) e = s+(e-s)*r;
> }
> }
> else
> @@ -559,21 +555,22 @@
>
> if (e.y()<bb_min.y())
> {
> - // clip s to yMin.
> - e = s+(e-s)*(bb_min.y()-s.y())/(e.y()-s.y());
> + // clip e to yMin.
> + double r = (bb_min.y()-e.y())/(s.y()-e.y()) - epsilon;
> + if (r>0.0) e = e + (s-e)*r;
> }
>
> if (s.y()>bb_max.y())
> {
> - // clip e to yMax.
> - s = s+(e-s)*(bb_max.y()-s.y())/(e.y()-s.y());
> + // clip s to yMax.
> + double r = (bb_max.y()-e.y())/(s.y()-e.y()) + epsilon;
> + if (r<1.0) s = e + (s-e)*r;
> }
> }
>
> // compate s and e against the zMin to zMax range of bb.
> if (s.z()<=e.z())
> {
> -
> // trivial reject of segment wholely outside.
> if (e.z()<bb_min.z()) return false;
> if (s.z()>bb_max.z()) return false;
> @@ -581,13 +578,15 @@
> if (s.z()<bb_min.z())
> {
> // clip s to zMin.
> - s = s+(e-s)*(bb_min.z()-s.z())/(e.z()-s.z());
> + double r = (bb_min.z()-s.z())/(e.z()-s.z()) - epsilon;
> + if (r>0.0) s = s + (e-s)*r;
> }
>
> if (e.z()>bb_max.z())
> {
> // clip e to zMax.
> - e = s+(e-s)*(bb_max.z()-s.z())/(e.z()-s.z());
> + double r = (bb_max.z()-s.z())/(e.z()-s.z()) + epsilon;
> + if (r<1.0) e = s+(e-s)*r;
> }
> }
> else
> @@ -597,14 +596,16 @@
>
> if (e.z()<bb_min.z())
> {
> - // clip s to zMin.
> - e = s+(e-s)*(bb_min.z()-s.z())/(e.z()-s.z());
> + // clip e to zMin.
> + double r = (bb_min.z()-e.z())/(s.z()-e.z()) - epsilon;
> + if (r>0.0) e = e + (s-e)*r;
> }
>
> if (s.z()>bb_max.z())
> {
> - // clip e to zMax.
> - s = s+(e-s)*(bb_max.z()-s.z())/(e.z()-s.z());
> + // clip s to zMax.
> + double r = (bb_max.z()-e.z())/(s.z()-e.z()) + epsilon;
> + if (r<1.0) s = e + (s-e)*r;
> }
> }
>
> On 27 August 2013 10:32, PCJohn <[email protected]> wrote:
> > Hi Robert,
> >
> > following our discussion on osg-users, I created a patch for
> > LineSegmentIntersector floating point precision. As always, the
> > implementation
> > revealed more potential precision problems. In short, there are three
> > sources
> > of potential precision problems: it is the bounding box, it is the start
> > and
> > it is the end point. All of them are accompanied by epsilon to be sure
> > that we
> > did not miss any intersections. See attached sources based on today svn.
> >
> > I attached IntersectionVisitor as I removed epsilon from public interface
> > - it
> > was not in stable OSG release and I feel like this should be rather
> > internal
> > constant set in a way based on float or double precision on the target
> > platform
> > and I would rather did not expose it to the user. The user might get
> > confused
> > by the meaning of it, break the things by wrong values, and the
> > intersector
> > should work correctly without the need to change or specify the value from
> > outside.
> >
> > John
> > _______________________________________________
> > osg-submissions mailing list
> > [email protected]
> >
> > http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegrap
> > h.org
_______________________________________________
osg-submissions mailing list
[email protected]
http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegraph.org
