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