Hi,
There is definitely something fishy going on. With the attached
extremely simple testcase (only 2 triangles, without any transform) and
the normal osgpick example I indeed get no intersections at locations
where there definitely should be some.
I think I've tracked this down to the fact that the triangles are
aligned with the coordinate system axes, so the Y-planes defined by the
bounding box are the same as the triangle planes. This results in
intersection noise as, depending on numerical errors, the intersection
found might be just outside the ray interval. Your museum scene's walls
have the same problem, which is why you're getting those missing
intersections.
Attached is an updated src/osgUtil/LineSegmentIntersector.cpp, which
solves this for now by allowing the found intersection point to be a
tiny bit beyond the end point of the segment. It also replaces the
triangle intersection code with something that I can actually understand
as the currect version is completely untransparent to me (and a
surprising large amount of code for something so basic). I don't
consider this a replacement as of yet as there are some things not
completely equivalent to the current code (the r1, r2, r3 output
parameters are not set). But maybe you find it useful for now.
Paul
GMD GammerMaxyandex.ru wrote:
I decided my issue. I removed the code from the file. (as was the case
previously in 2.5.2). The problem disappeared! Make it please in the next
version.
LineSegmentIntersector.cpp
removed the code from the file: line 290 ..
double epsilon = 1e-8;
if ((s-e).length()<epsilon)
{
osg::Vec3d delta_e_end = _end - e;
osg::Vec3d delta_s_start = _start - s;
double scale = 0.001;
s += (delta_s_start * scale);
e += (delta_e_end * scale);
}
code version 2.5.2:
s = _start;
e = _end;
The problem disappeared! Make it please in the next version.
28.07.08, 22:44, "GMD GammerMaxyandex.ru" <[EMAIL PROTECTED]>:
> Here is the small example, where described problem appeares. Example is
modified example of osgpick (chenged code which returns name of object and osg
scene). To see this problem you must go in the deep of room (way is showen in
00.jpeg). Then you need make several clicks in different positions (movements
bitween positions must be small) and you will see that cursor often falls throught
the object over which cursor is (possible positions is showen on 11.jpg). There is
two archives in attachement (with textures and without them). Code is in
osgpick.zip file which taken from example osgpick. I hope this is enough to
illustrate described problem. And I think it will be not good if this error
appeares in this release (2.6.0).
> Thanks, Max.
> files:
> (download: enter number, click green button)
> http://narod.ru/disk/1711280000/osgpick.zip.html
> http://narod.ru/disk/1711073000/00.JPG.html
> http://narod.ru/disk/1711279000/11.JPG.html
> http://narod.ru/disk/1712663000/museum_with_textures.zip.html
> Thanks, Max.
> 28.07.08, 10:47, "GMD GammerMaxyandex.ru" <[EMAIL PROTECTED]>:
> > Ok, I'll make small example and show where problem occures. I'll try do
this today.
> > 28.07.08, 00:33, "sherman wilcox" <[EMAIL PROTECTED]>:
> > > Can you make a small and simple prototype that *reliably* reproduces
> > > the problem? You have a better chance of getting help that way.
> > > On Sun, Jul 27, 2008 at 2:50 AM, GMD GammerMaxyandex.ru
> > > <[EMAIL PROTECTED]> wrote:
> > > > Some offers of OSG 2.6.0( problems with new version).
> > > > Let's wait with OSG 2.6.0 release. I asked this because I found a
problem with osgUtil::LineSegmentIntersector function.
> > > > In OSG v 2.5.5 version of OSG function
viewer->computeIntersections(x,y, hlist) works very strange - when cursor movements over
object is short it(cursor) falls throught the object and function returns name of object which
is behind current(object over which cursor is). In earlyer(less 2.5.2) versions of OSG this
error has never appeared. How can I solve this problem in this(2.5.5) version of OSG?
> > > > It is necessary to solve the problem until OSG 2.6.0 release.
> > > > Thanks in advance. Best regards, Max.
> > > > _______________________________________________
> > > > osg-users mailing list
> > > > [email protected]
> > > >
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
> > > >
> > > _______________________________________________
> > > osg-users mailing list
> > > [email protected]
> > >
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Geode {
UniqueID Geode_136
DataVariance STATIC
nodeMask 0xff
cullingActive TRUE
num_drawables 1
Geometry {
DataVariance DYNAMIC
StateSet {
UniqueID StateSet_137
DataVariance STATIC
rendering_hint DEFAULT_BIN
renderBinMode INHERIT
GL_CULL_FACE ON
GL_LIGHTING ON
0xba1 ON
Material {
DataVariance STATIC
ColorMode OFF
ambientColor 1 1 1 1
diffuseColor 1 1 1 1
specularColor 0 0 0 1
emissionColor 0 0 0 1
shininess 0
}
}
useDisplayList TRUE
useVertexBufferObjects FALSE
PrimitiveSets 1
{
DrawArrays TRIANGLES 0 6
}
VertexArray Vec3Array 6
{
-1 10 0
1 10 0
-1 10 1
-1 -10 0
1 -10 0
-1 -10 1
}
}
}
/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
*
* This library is open source and may be redistributed and/or modified under
* the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
* (at your option) any later version. The full license is in LICENSE file
* included with this distribution, and on the openscenegraph.org website.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* OpenSceneGraph Public License for more details.
*/
#include <osgUtil/LineSegmentIntersector>
#include <osg/Geometry>
#include <osg/Notify>
#include <osg/io_utils>
#include <osg/TriangleFunctor>
#include <osg/KdTree>
#include <osg/Timer>
#include <osg/Math>
using namespace osgUtil;
namespace LineSegmentIntersectorUtils
{
struct TriangleIntersection
{
TriangleIntersection(unsigned int index, const osg::Vec3& normal, float r1, const osg::Vec3* v1, float r2, const osg::Vec3* v2, float r3, const osg::Vec3* v3):
_index(index),
_normal(normal),
_r1(r1),
_v1(v1),
_r2(r2),
_v2(v2),
_r3(r3),
_v3(v3) {}
unsigned int _index;
const osg::Vec3 _normal;
float _r1;
const osg::Vec3* _v1;
float _r2;
const osg::Vec3* _v2;
float _r3;
const osg::Vec3* _v3;
};
typedef std::multimap<float,TriangleIntersection> TriangleIntersections;
struct TriangleIntersector
{
osg::Vec3 _s;
osg::Vec3 _d;
int _index;
float _ratio;
bool _hit;
TriangleIntersections _intersections;
TriangleIntersector()
{
_index = 0;
_ratio = 0.0f;
_hit = false;
}
void set(const osg::Vec3d& start, osg::Vec3d& end, float ratio=FLT_MAX)
{
_hit=false;
_index = 0;
_ratio = ratio;
_s = start;
_d = end - start;
}
inline void operator () (const osg::Vec3& v1,const osg::Vec3& v2,const osg::Vec3& v3, bool treatVertexDataAsTemporary)
{
// XXX shouldn't _hit be set to false before the test?
//printf("operator():\n");
//printf("... v1 = %.6f, %.6f, %.6f\n", v1.x(), v1.y(), v1.z());
//printf("... v2 = %.6f, %.6f, %.6f\n", v2.x(), v2.y(), v2.z());
//printf("... v3 = %.6f, %.6f, %.6f\n", v3.x(), v3.y(), v3.z());
++_index;
if (v1==v2 || v2==v3 || v1==v3) return;
osg::Vec3 n = (v2 - v1) ^ (v3 - v1);
// Find intersection of ray with plane defined by triangle
double denom = _d * n;
//printf("... denom = %.12lf\n", denom);
if (osg::absolute(denom) < 1.0e-8)
{
// Ray and triangle parallel
return;
}
double t = - ((_s - v1) * n) / denom;
//printf("... t = %.12lf\n", t);
if (t < 0.0 || t > 1.000001)
{
// Intersection point outside of ray segment
return;
}
// Intersection point
osg::Vec3 ip = _s + _d * t;
// Check if intersection point is within triangle
if ( ((v2 - v1) ^ (ip - v1)) * n < 0.0)
return;
if ( ((v3 - v2) ^ (ip - v2)) * n < 0.0)
return;
if ( ((v1 - v3) ^ (ip - v3)) * n < 0.0)
return;
n.normalize();
// XXX What the heck are r1, r2 and r3?
double r1, r2, r3;
r1 = r2 = r3 = 0.0;
if (treatVertexDataAsTemporary)
{
_intersections.insert(std::pair<const float,TriangleIntersection>(t, TriangleIntersection(_index-1,n,r1,0,r2,0,r3,0)));
}
else
{
_intersections.insert(std::pair<const float,TriangleIntersection>(t, TriangleIntersection(_index-1,n,r1,&v1,r2,&v2,r3,&v3)));
}
_hit = true;
}
};
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// LineSegmentIntersector
//
LineSegmentIntersector::LineSegmentIntersector(const osg::Vec3d& start, const osg::Vec3d& end):
_parent(0),
_start(start),
_end(end)
{
}
LineSegmentIntersector::LineSegmentIntersector(CoordinateFrame cf, const osg::Vec3d& start, const osg::Vec3d& end):
Intersector(cf),
_parent(0),
_start(start),
_end(end)
{
}
LineSegmentIntersector::LineSegmentIntersector(CoordinateFrame cf, double x, double y):
Intersector(cf),
_parent(0)
{
switch(cf)
{
case WINDOW : _start.set(x,y,0.0); _end.set(x,y,1.0); break;
case PROJECTION : _start.set(x,y,-1.0); _end.set(x,y,1.0); break;
case VIEW : _start.set(x,y,0.0); _end.set(x,y,1.0); break;
case MODEL : _start.set(x,y,0.0); _end.set(x,y,1.0); break;
}
}
Intersector* LineSegmentIntersector::clone(osgUtil::IntersectionVisitor& iv)
{
if (_coordinateFrame==MODEL && iv.getModelMatrix()==0)
{
osg::ref_ptr<LineSegmentIntersector> lsi = new LineSegmentIntersector(_start, _end);
lsi->_parent = this;
return lsi.release();
}
// compute the matrix that takes this Intersector from its CoordinateFrame into the local MODEL coordinate frame
// that geometry in the scene graph will always be in.
osg::Matrix matrix;
switch (_coordinateFrame)
{
case(WINDOW):
if (iv.getWindowMatrix()) matrix.preMult( *iv.getWindowMatrix() );
if (iv.getProjectionMatrix()) matrix.preMult( *iv.getProjectionMatrix() );
if (iv.getViewMatrix()) matrix.preMult( *iv.getViewMatrix() );
if (iv.getModelMatrix()) matrix.preMult( *iv.getModelMatrix() );
break;
case(PROJECTION):
if (iv.getProjectionMatrix()) matrix.preMult( *iv.getProjectionMatrix() );
if (iv.getViewMatrix()) matrix.preMult( *iv.getViewMatrix() );
if (iv.getModelMatrix()) matrix.preMult( *iv.getModelMatrix() );
break;
case(VIEW):
if (iv.getViewMatrix()) matrix.preMult( *iv.getViewMatrix() );
if (iv.getModelMatrix()) matrix.preMult( *iv.getModelMatrix() );
break;
case(MODEL):
if (iv.getModelMatrix()) matrix = *iv.getModelMatrix();
break;
}
osg::Matrix inverse;
inverse.invert(matrix);
osg::ref_ptr<LineSegmentIntersector> lsi = new LineSegmentIntersector(_start * inverse, _end * inverse);
lsi->_parent = this;
return lsi.release();
}
bool LineSegmentIntersector::enter(const osg::Node& node)
{
return !node.isCullingActive() || intersects( node.getBound() );
}
void LineSegmentIntersector::leave()
{
// do nothing
}
void LineSegmentIntersector::intersect(osgUtil::IntersectionVisitor& iv, osg::Drawable* drawable)
{
osg::Vec3d s(_start), e(_end);
if ( !intersectAndClip( s, e, drawable->getBound() ) ) return;
//printf("LineSegmentIntersector::intersect(drawable=0x%08x)\n", drawable);
//printf("... _start = %.6f, %.6f, %.6f\n", _start.x(), _start.y(), _start.z());
//printf("... _end = %.6f, %.6f, %.6f\n", _end.x(), _end.y(), _end.z());
//printf("... bound = <%.6f, %.6f, %.6f> -> <%.6f, %.6f, %.6f>\n",
//drawable->getBound().xMin(), drawable->getBound().yMin(), drawable->getBound().zMin(),
//drawable->getBound().xMax(), drawable->getBound().yMax(), drawable->getBound().zMax());
//printf("... s = %.6f, %.6f, %.6f\n", s.x(), s.y(), s.z());
//printf("... e = %.6f, %.6f, %.6f\n", e.x(), e.y(), e.z());
if (iv.getDoDummyTraversal()) return;
double epsilon = 1e-8;
if ((s-e).length()<epsilon)
{
//printf("... adjusting intersection points\n");
osg::Vec3d delta_e_end = _end - e;
osg::Vec3d delta_s_start = _start - s;
double scale = 0.001;
s += (delta_s_start * scale);
e += (delta_e_end * scale);
}
osg::KdTree* kdTree = iv.getUseKdTreeWhenAvailable() ? dynamic_cast<osg::KdTree*>(drawable->getShape()) : 0;
if (kdTree)
{
osg::KdTree::LineSegmentIntersections intersections;
intersections.reserve(4);
if (kdTree->intersect(s,e,intersections))
{
// osg::notify(osg::NOTICE)<<"Got KdTree intersections"<<std::endl;
for(osg::KdTree::LineSegmentIntersections::iterator itr = intersections.begin();
itr != intersections.end();
++itr)
{
osg::KdTree::LineSegmentIntersection& lsi = *(itr);
// get ratio in s,e range
double ratio = lsi.ratio;
// remap ratio into _start, _end range
double remap_ratio = ((s-_start).length() + ratio * (e-s).length() )/(_end-_start).length();
Intersection hit;
hit.ratio = remap_ratio;
hit.matrix = iv.getModelMatrix();
hit.nodePath = iv.getNodePath();
hit.drawable = drawable;
hit.primitiveIndex = lsi.primitiveIndex;
hit.localIntersectionPoint = _start*(1.0-remap_ratio) + _end*remap_ratio;
// osg::notify(osg::NOTICE)<<"KdTree: ratio="<<hit.ratio<<" ("<<hit.localIntersectionPoint<<")"<<std::endl;
hit.localIntersectionNormal = lsi.intersectionNormal;
hit.indexList.reserve(3);
hit.ratioList.reserve(3);
if (lsi.r0!=0.0f)
{
hit.indexList.push_back(lsi.p0);
hit.ratioList.push_back(lsi.r0);
}
if (lsi.r1!=0.0f)
{
hit.indexList.push_back(lsi.p1);
hit.ratioList.push_back(lsi.r1);
}
if (lsi.r2!=0.0f)
{
hit.indexList.push_back(lsi.p2);
hit.ratioList.push_back(lsi.r2);
}
insertIntersection(hit);
}
}
return;
}
osg::TriangleFunctor<LineSegmentIntersectorUtils::TriangleIntersector> ti;
ti.set(s,e);
drawable->accept(ti);
if (ti._hit)
{
//printf("... ti._hit is set\n");
osg::Geometry* geometry = drawable->asGeometry();
for(LineSegmentIntersectorUtils::TriangleIntersections::iterator thitr = ti._intersections.begin();
thitr != ti._intersections.end();
++thitr)
{
// get ratio in s,e range
double ratio = thitr->first;
// remap ratio into _start, _end range
double remap_ratio = ((s-_start).length() + ratio * (e-s).length() )/(_end-_start).length();
LineSegmentIntersectorUtils::TriangleIntersection& triHit = thitr->second;
Intersection hit;
hit.ratio = remap_ratio;
hit.matrix = iv.getModelMatrix();
hit.nodePath = iv.getNodePath();
hit.drawable = drawable;
hit.primitiveIndex = triHit._index;
hit.localIntersectionPoint = _start*(1.0-remap_ratio) + _end*remap_ratio;
// osg::notify(osg::NOTICE)<<"Conventional: ratio="<<hit.ratio<<" ("<<hit.localIntersectionPoint<<")"<<std::endl;
hit.localIntersectionNormal = triHit._normal;
if (geometry)
{
osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray());
if (vertices)
{
osg::Vec3* first = &(vertices->front());
if (triHit._v1)
{
hit.indexList.push_back(triHit._v1-first);
hit.ratioList.push_back(triHit._r1);
}
if (triHit._v2)
{
hit.indexList.push_back(triHit._v2-first);
hit.ratioList.push_back(triHit._r2);
}
if (triHit._v3)
{
hit.indexList.push_back(triHit._v3-first);
hit.ratioList.push_back(triHit._r3);
}
}
}
insertIntersection(hit);
}
}
}
void LineSegmentIntersector::reset()
{
Intersector::reset();
_intersections.clear();
}
bool LineSegmentIntersector::intersects(const osg::BoundingSphere& bs)
{
// if bs not valid then return true based on the assumption that an invalid sphere is yet to be defined.
if (!bs.valid()) return true;
osg::Vec3d sm = _start - bs._center;
double c = sm.length2()-bs._radius*bs._radius;
if (c<0.0) return true;
osg::Vec3d se = _end-_start;
double a = se.length2();
double b = (sm*se)*2.0;
double d = b*b-4.0*a*c;
if (d<0.0) return false;
d = sqrt(d);
double div = 1.0/(2.0*a);
double r1 = (-b-d)*div;
double r2 = (-b+d)*div;
if (r1<=0.0 && r2<=0.0) return false;
if (r1>=1.0 && r2>=1.0) return false;
// passed all the rejection tests so line must intersect bounding sphere, return true.
return true;
}
bool LineSegmentIntersector::intersectAndClip(osg::Vec3d& s, osg::Vec3d& e,const osg::BoundingBox& bb)
{
// 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.xMin()) return false;
if (s.x()>bb.xMax()) return false;
if (s.x()<bb.xMin())
{
// clip s to xMin.
s = s+(e-s)*(bb.xMin()-s.x())/(e.x()-s.x());
}
if (e.x()>bb.xMax())
{
// clip e to xMax.
e = s+(e-s)*(bb.xMax()-s.x())/(e.x()-s.x());
}
}
else
{
if (s.x()<bb.xMin()) return false;
if (e.x()>bb.xMax()) return false;
if (e.x()<bb.xMin())
{
// clip s to xMin.
e = s+(e-s)*(bb.xMin()-s.x())/(e.x()-s.x());
}
if (s.x()>bb.xMax())
{
// clip e to xMax.
s = s+(e-s)*(bb.xMax()-s.x())/(e.x()-s.x());
}
}
// 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.yMin()) return false;
if (s.y()>bb.yMax()) return false;
if (s.y()<bb.yMin())
{
// clip s to yMin.
s = s+(e-s)*(bb.yMin()-s.y())/(e.y()-s.y());
}
if (e.y()>bb.yMax())
{
// clip e to yMax.
e = s+(e-s)*(bb.yMax()-s.y())/(e.y()-s.y());
}
}
else
{
if (s.y()<bb.yMin()) return false;
if (e.y()>bb.yMax()) return false;
if (e.y()<bb.yMin())
{
// clip s to yMin.
e = s+(e-s)*(bb.yMin()-s.y())/(e.y()-s.y());
}
if (s.y()>bb.yMax())
{
// clip e to yMax.
s = s+(e-s)*(bb.yMax()-s.y())/(e.y()-s.y());
}
}
// 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.zMin()) return false;
if (s.z()>bb.zMax()) return false;
if (s.z()<bb.zMin())
{
// clip s to zMin.
s = s+(e-s)*(bb.zMin()-s.z())/(e.z()-s.z());
}
if (e.z()>bb.zMax())
{
// clip e to zMax.
e = s+(e-s)*(bb.zMax()-s.z())/(e.z()-s.z());
}
}
else
{
if (s.z()<bb.zMin()) return false;
if (e.z()>bb.zMax()) return false;
if (e.z()<bb.zMin())
{
// clip s to zMin.
e = s+(e-s)*(bb.zMin()-s.z())/(e.z()-s.z());
}
if (s.z()>bb.zMax())
{
// clip e to zMax.
s = s+(e-s)*(bb.zMax()-s.z())/(e.z()-s.z());
}
}
// osg::notify(osg::NOTICE)<<"clampped segment "<<s<<" "<<e<<std::endl;
// if (s==e) return false;
return true;
}
_______________________________________________
osg-users mailing list
[email protected]
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
