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
/* -*-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.
*/
#ifndef OSGUTIL_INTERSECTIONVISITOR
#define OSGUTIL_INTERSECTIONVISITOR 1
#include <osg/NodeVisitor>
#include <osg/Drawable>
#include <osgUtil/Export>
#include <list>
namespace osgUtil
{
// forward declare to allow Intersector to reference it.
class IntersectionVisitor;
/** Pure virtual base class for implementing custom intersection technique.
* To implement a specific intersection technique on must override all
* the pure virtue methods, concrete examples of how to do this can be seen in
* the LineSegmentIntersector. */
class Intersector : public osg::Referenced
{
public:
enum CoordinateFrame
{
WINDOW,
PROJECTION,
VIEW,
MODEL
};
enum IntersectionLimit
{
NO_LIMIT,
LIMIT_ONE_PER_DRAWABLE,
LIMIT_ONE,
LIMIT_NEAREST
};
Intersector(CoordinateFrame cf=MODEL):
_coordinateFrame(cf),
_intersectionLimit(NO_LIMIT),
_disabledCount(0) {}
void setCoordinateFrame(CoordinateFrame cf) { _coordinateFrame = cf; }
CoordinateFrame getCoordinateFrame() const { return _coordinateFrame; }
void setIntersectionLimit(IntersectionLimit limit) { _intersectionLimit = limit; }
IntersectionLimit getIntersectionLimit() const { return _intersectionLimit; }
virtual Intersector* clone(osgUtil::IntersectionVisitor& iv) = 0;
virtual bool enter(const osg::Node& node) = 0;
virtual void leave() = 0;
virtual void intersect(osgUtil::IntersectionVisitor& iv, osg::Drawable* drawable) = 0;
virtual void reset() { _disabledCount = 0; }
virtual bool containsIntersections() = 0;
inline bool disabled() const { return _disabledCount!=0; }
inline void incrementDisabledCount() { ++_disabledCount; }
inline void decrementDisabledCount() { if (_disabledCount>0) --_disabledCount; }
inline bool reachedLimit() { return _intersectionLimit == LIMIT_ONE && containsIntersections(); }
protected:
CoordinateFrame _coordinateFrame;
IntersectionLimit _intersectionLimit;
unsigned int _disabledCount;
};
/** Concrete class for passing multiple intersectors through the scene graph.
* To be used in conjunction with IntersectionVisitor. */
class OSGUTIL_EXPORT IntersectorGroup : public Intersector
{
public:
IntersectorGroup();
/** Add an Intersector. */
void addIntersector(Intersector* intersector);
typedef std::vector< osg::ref_ptr<Intersector> > Intersectors;
/** Get the list of intersector. */
Intersectors& getIntersectors() { return _intersectors; }
/** Clear the list of intersectors.*/
void clear();
public:
virtual Intersector* clone(osgUtil::IntersectionVisitor& iv);
virtual bool enter(const osg::Node& node);
virtual void leave();
virtual void intersect(osgUtil::IntersectionVisitor& iv, osg::Drawable* drawable);
virtual void reset();
virtual bool containsIntersections();
protected:
Intersectors _intersectors;
};
/** InteresectionVisitor is used to testing for intersections with the scene, traversing the scene using generic osgUtil::Intersector's to test against the scene.
* To implement different types of intersection techniques, one implements custom versions of the osgUtil::Intersector, and then
* pass the constructed intersector to the IntersectionVisitor.*/
class OSGUTIL_EXPORT IntersectionVisitor : public osg::NodeVisitor
{
public:
/** Callback used to implement the reading of external files, allowing support for paged databases to be
* integrated with IntersectionVisitor. A concrete implementation can be found in osgDB.
* Note, this loose coupling approach is required as osgUtil is independent from osgDB where the file reading
* is implemented, and osgDB itself is dependent upon osgUtil so a circular dependency would result from
* tighter integration.*/
struct ReadCallback : public osg::Referenced
{
virtual osg::Node* readNodeFile(const std::string& filename) = 0;
};
IntersectionVisitor(Intersector* intersector=0, ReadCallback* readCallback=0);
META_NodeVisitor(osgUtil, IntersectionVisitor)
virtual void reset();
/** Set the intersector that will be used to intersect with the scene, and to store any hits that occur.*/
void setIntersector(Intersector* intersector);
/** Get the intersector that will be used to intersect with the scene, and to store any hits that occur.*/
Intersector* getIntersector() { return _intersectorStack.empty() ? 0 : _intersectorStack.front().get(); }
/** Get the const intersector that will be used to intersect with the scene, and to store any hits that occur.*/
const Intersector* getIntersector() const { return _intersectorStack.empty() ? 0 : _intersectorStack.front().get(); }
/** Set whether the intersectors should use KdTrees when they are found on the scene graph.*/
void setUseKdTreeWhenAvailable(bool useKdTrees) { _useKdTreesWhenAvailable = useKdTrees; }
/** Set whether the intersectors should use KdTrees.*/
bool getUseKdTreeWhenAvailable() const { return _useKdTreesWhenAvailable; }
void setDoDummyTraversal(bool dummy) { _dummyTraversal = dummy; }
bool getDoDummyTraversal() const { return _dummyTraversal; }
/** Set the read callback.*/
void setReadCallback(ReadCallback* rc) { _readCallback = rc; }
/** Get the read callback.*/
ReadCallback* getReadCallback() { return _readCallback.get(); }
/** Get the const read callback.*/
const ReadCallback* getReadCallback() const { return _readCallback.get(); }
void pushWindowMatrix(osg::RefMatrix* matrix) { _windowStack.push_back(matrix); _eyePointDirty = true; }
void pushWindowMatrix(osg::Viewport* viewport) { _windowStack.push_back(new osg::RefMatrix( viewport->computeWindowMatrix()) ); _eyePointDirty = true; }
void popWindowMatrix() { _windowStack.pop_back(); _eyePointDirty = true; }
osg::RefMatrix* getWindowMatrix() { return _windowStack.empty() ? 0 : _windowStack.back().get(); }
const osg::RefMatrix* getWindowMatrix() const { return _windowStack.empty() ? 0 : _windowStack.back().get(); }
void pushProjectionMatrix(osg::RefMatrix* matrix) { _projectionStack.push_back(matrix); _eyePointDirty = true; }
void popProjectionMatrix() { _projectionStack.pop_back(); _eyePointDirty = true; }
osg::RefMatrix* getProjectionMatrix() { return _projectionStack.empty() ? 0 : _projectionStack.back().get(); }
const osg::RefMatrix* getProjectionMatrix() const { return _projectionStack.empty() ? 0 : _projectionStack.back().get(); }
void pushViewMatrix(osg::RefMatrix* matrix) { _viewStack.push_back(matrix); _eyePointDirty = true; }
void popViewMatrix() { _viewStack.pop_back(); _eyePointDirty = true; }
osg::RefMatrix* getViewMatrix() { return _viewStack.empty() ? 0 : _viewStack.back().get(); }
const osg::RefMatrix* getViewMatrix() const { return _viewStack.empty() ? 0 : _viewStack.back().get(); }
void pushModelMatrix(osg::RefMatrix* matrix) { _modelStack.push_back(matrix); _eyePointDirty = true; }
void popModelMatrix() { _modelStack.pop_back(); _eyePointDirty = true; }
osg::RefMatrix* getModelMatrix() { return _modelStack.empty() ? 0 : _modelStack.back().get(); }
const osg::RefMatrix* getModelMatrix() const { return _modelStack.empty() ? 0 : _modelStack.back().get(); }
/** Set the reference eye point that is used for nodes that require an eye point to position themselves, such as billboards.*/
void setReferenceEyePoint(const osg::Vec3& ep) { _referenceEyePoint = ep; _eyePointDirty = true; }
/** Get the reference eye point.*/
const osg::Vec3& getReferenceEyePoint() const { return _referenceEyePoint; }
/** Set the coordinate frame of the reference eye point.*/
void setReferenceEyePointCoordinateFrame(Intersector::CoordinateFrame cf) { _referenceEyePointCoordinateFrame = cf; }
/** Get the coordinate frame of the reference eye point.*/
Intersector::CoordinateFrame getReferenceEyePointCoordinateFrame() const { return _referenceEyePointCoordinateFrame; }
/** Get the eye point in the local coordinate frame a given traversal point.*/
virtual osg::Vec3 getEyePoint() const;
enum LODSelectionMode
{
USE_HIGHEST_LEVEL_OF_DETAIL,
USE_EYE_POINT_FOR_LOD_LEVEL_SELECTION
};
/** Set the LOD selection scheme.*/
void setLODSelectionMode(LODSelectionMode mode) { _lodSelectionMode = mode; }
/** Get the LOD selection scheme.*/
LODSelectionMode getLODSelectionMode() const { return _lodSelectionMode; }
/** Get the distance from a point to the eye point, distance value in local coordinate system.
* This is calculated using the pseudo-EyePoint (above) when doing LOD calculcations. */
virtual float getDistanceToEyePoint(const osg::Vec3& pos, bool withLODScale) const;
public:
virtual void apply(osg::Node& node);
virtual void apply(osg::Geode& geode);
virtual void apply(osg::Billboard& geode);
virtual void apply(osg::Group& group);
virtual void apply(osg::LOD& lod);
virtual void apply(osg::PagedLOD& lod);
virtual void apply(osg::Transform& transform);
virtual void apply(osg::Projection& projection);
virtual void apply(osg::Camera& camera);
protected:
inline bool enter(const osg::Node& node) { return _intersectorStack.empty() ? false : _intersectorStack.back()->enter(node); }
inline void leave() { _intersectorStack.back()->leave(); }
inline void intersect(osg::Drawable* drawable) { _intersectorStack.back()->intersect(*this, drawable); }
inline void push_clone() { _intersectorStack.push_back ( _intersectorStack.front()->clone(*this) ); }
inline void pop_clone() { if (_intersectorStack.size()>=2) _intersectorStack.pop_back(); }
typedef std::list< osg::ref_ptr<Intersector> > IntersectorStack;
IntersectorStack _intersectorStack;
bool _useKdTreesWhenAvailable;
bool _dummyTraversal;
osg::ref_ptr<ReadCallback> _readCallback;
typedef std::list< osg::ref_ptr<osg::RefMatrix> > MatrixStack;
MatrixStack _windowStack;
MatrixStack _projectionStack;
MatrixStack _viewStack;
MatrixStack _modelStack;
osg::Vec3 _referenceEyePoint;
Intersector::CoordinateFrame _referenceEyePointCoordinateFrame;
LODSelectionMode _lodSelectionMode;
mutable bool _eyePointDirty;
mutable osg::Vec3 _eyePoint;
};
}
#endif
/* -*-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/TexMat>
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;
protected:
TriangleIntersection& operator = (const TriangleIntersection&) { return *this; }
};
typedef std::multimap<float,TriangleIntersection> TriangleIntersections;
struct TriangleIntersector
{
osg::Vec3 _s;
osg::Vec3 _d;
float _length;
int _index;
float _ratio;
bool _hit;
bool _limitOneIntersection;
TriangleIntersections _intersections;
TriangleIntersector()
{
_length = 0.0f;
_index = 0;
_ratio = 0.0f;
_hit = false;
_limitOneIntersection = 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;
_length = _d.length();
_d /= _length;
}
inline void operator () (const osg::Vec3& v1,const osg::Vec3& v2,const osg::Vec3& v3, bool treatVertexDataAsTemporary)
{
++_index;
if (_limitOneIntersection && _hit) return;
if (v1==v2 || v2==v3 || v1==v3) return;
osg::Vec3 v12 = v2-v1;
osg::Vec3 n12 = v12^_d;
float ds12 = (_s-v1)*n12;
float d312 = (v3-v1)*n12;
if (d312>=0.0f)
{
if (ds12<0.0f) return;
if (ds12>d312) return;
}
else // d312 < 0
{
if (ds12>0.0f) return;
if (ds12<d312) return;
}
osg::Vec3 v23 = v3-v2;
osg::Vec3 n23 = v23^_d;
float ds23 = (_s-v2)*n23;
float d123 = (v1-v2)*n23;
if (d123>=0.0f)
{
if (ds23<0.0f) return;
if (ds23>d123) return;
}
else // d123 < 0
{
if (ds23>0.0f) return;
if (ds23<d123) return;
}
osg::Vec3 v31 = v1-v3;
osg::Vec3 n31 = v31^_d;
float ds31 = (_s-v3)*n31;
float d231 = (v2-v3)*n31;
if (d231>=0.0f)
{
if (ds31<0.0f) return;
if (ds31>d231) return;
}
else // d231 < 0
{
if (ds31>0.0f) return;
if (ds31<d231) return;
}
float r3;
if (ds12==0.0f) r3=0.0f;
else if (d312!=0.0f) r3 = ds12/d312;
else return; // the triangle and the line must be parallel intersection.
float r1;
if (ds23==0.0f) r1=0.0f;
else if (d123!=0.0f) r1 = ds23/d123;
else return; // the triangle and the line must be parallel intersection.
float r2;
if (ds31==0.0f) r2=0.0f;
else if (d231!=0.0f) r2 = ds31/d231;
else return; // the triangle and the line must be parallel intersection.
float total_r = (r1+r2+r3);
if (total_r!=1.0f)
{
if (total_r==0.0f) return; // the triangle and the line must be parallel intersection.
float inv_total_r = 1.0f/total_r;
r1 *= inv_total_r;
r2 *= inv_total_r;
r3 *= inv_total_r;
}
osg::Vec3 in = v1*r1+v2*r2+v3*r3;
if (!in.valid())
{
OSG_WARN<<"Warning:: Picked up error in TriangleIntersect"<<std::endl;
OSG_WARN<<" ("<<v1<<",\t"<<v2<<",\t"<<v3<<")"<<std::endl;
OSG_WARN<<" ("<<r1<<",\t"<<r2<<",\t"<<r3<<")"<<std::endl;
return;
}
float d = (in-_s)*_d;
if (d<0.0f) return;
if (d>_length) return;
osg::Vec3 normal = v12^v23;
normal.normalize();
float r = d/_length;
if (treatVertexDataAsTemporary)
{
_intersections.insert(std::pair<const float,TriangleIntersection>(r,TriangleIntersection(_index-1,normal,r1,0,r2,0,r3,0)));
}
else
{
_intersections.insert(std::pair<const float,TriangleIntersection>(r,TriangleIntersection(_index-1,normal,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;
lsi->_intersectionLimit = this->_intersectionLimit;
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;
lsi->_intersectionLimit = this->_intersectionLimit;
return lsi.release();
}
bool LineSegmentIntersector::enter(const osg::Node& node)
{
if (reachedLimit()) return false;
return !node.isCullingActive() || intersects( node.getBound() );
}
void LineSegmentIntersector::leave()
{
// do nothing
}
void LineSegmentIntersector::intersect(osgUtil::IntersectionVisitor& iv, osg::Drawable* drawable)
{
if (reachedLimit()) return;
osg::Vec3d s(_start), e(_end);
if ( !intersectAndClip( s, e, drawable->getBound() ) ) return;
if (iv.getDoDummyTraversal()) return;
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_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_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);
ti._limitOneIntersection = (_intersectionLimit == LIMIT_ONE_PER_DRAWABLE || _intersectionLimit == LIMIT_ONE);
drawable->accept(ti);
if (ti._hit)
{
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();
if ( _intersectionLimit == LIMIT_NEAREST && !getIntersections().empty() )
{
if (remap_ratio >= getIntersections().begin()->ratio )
break;
else
getIntersections().clear();
}
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_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;
if (_intersectionLimit == LIMIT_NEAREST && !getIntersections().empty())
{
double ratio = (sm.length() - bs._radius) / sqrt(a);
if (ratio >= getIntersections().begin()->ratio) 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& bbInput)
{
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.
// Precision of double is between 15 and 17 significant numerical digits, thus epsilon conservative value
// might be 1e-13 or 1e-14.
const double epsilon = 1e-13;
bb_min.x() -= fabs(bb_min.x()) * epsilon;
bb_max.x() += fabs(bb_max.x()) * epsilon;
bb_min.y() -= fabs(bb_min.y()) * epsilon;
bb_max.y() += fabs(bb_max.y()) * epsilon;
bb_min.z() -= fabs(bb_min.z()) * epsilon;
bb_max.z() += fabs(bb_max.z()) * epsilon;
// epsilonStart and epsilonEnd makes sure that we will not miss intersections because of numerical floating point precision
// in the cases when length of line segment is very small compared to value of s and e
const double esLength = (e-s).length();
const double epsilonStart = osg::maximum(osg::maximum(s.x(), s.y()), s.z()) / esLength * epsilon;
const double epsilonEnd = osg::maximum(osg::maximum(e.x(), e.y()), e.z()) / esLength * epsilon;
// 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;
if (s.x()<bb_min.x())
{
// clip s to xMin.
s = s+(e-s)*((bb_min.x()-(s.x()*(1.+epsilon)))/(e.x()-s.x())-epsilonStart);
}
if (e.x()>bb_max.x())
{
// clip e to xMax.
e = s+(e-s)*((bb_max.x()-(s.x()*(1.-epsilon)))/(e.x()-s.x())+epsilonEnd);
}
}
else
{
if (s.x()<bb_min.x()) return false;
if (e.x()>bb_max.x()) return false;
if (e.x()<bb_min.x())
{
// clip s to xMin.
e = s+(e-s)*((bb_min.x()-(s.x()*(1.+epsilon)))/(e.x()-s.x())-epsilonEnd);
}
if (s.x()>bb_max.x())
{
// clip e to xMax.
s = s+(e-s)*((bb_max.x()-(s.x()*(1.-epsilon)))/(e.x()-s.x())+epsilonStart);
}
}
// 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;
if (s.y()<bb_min.y())
{
// clip s to yMin.
s = s+(e-s)*((bb_min.y()-(s.y()*(1.+epsilon)))/(e.y()-s.y())-epsilonStart);
}
if (e.y()>bb_max.y())
{
// clip e to yMax.
e = s+(e-s)*((bb_max.y()-(s.y()*(1.-epsilon)))/(e.y()-s.y())+epsilonEnd);
}
}
else
{
if (s.y()<bb_min.y()) return false;
if (e.y()>bb_max.y()) return false;
if (e.y()<bb_min.y())
{
// clip s to yMin.
e = s+(e-s)*((bb_min.y()-(s.y()*(1.+epsilon)))/(e.y()-s.y())-epsilonEnd);
}
if (s.y()>bb_max.y())
{
// clip e to yMax.
s = s+(e-s)*((bb_max.y()-(s.y()*(1.-epsilon)))/(e.y()-s.y())+epsilonStart);
}
}
// 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;
if (s.z()<bb_min.z())
{
// clip s to zMin.
s = s+(e-s)*((bb_min.z()-(s.z()*(1.+epsilon)))/(e.z()-s.z())-epsilonStart);
}
if (e.z()>bb_max.z())
{
// clip e to zMax.
e = s+(e-s)*((bb_max.z()-(s.z()*(1.-epsilon)))/(e.z()-s.z())+epsilonEnd);
}
}
else
{
if (s.z()<bb_min.z()) return false;
if (e.z()>bb_max.z()) return false;
if (e.z()<bb_min.z())
{
// clip s to zMin.
e = s+(e-s)*((bb_min.z()-(s.z()*(1.+epsilon)))/(e.z()-s.z())-epsilonEnd);
}
if (s.z()>bb_max.z())
{
// clip e to zMax.
s = s+(e-s)*((bb_max.z()-(s.z()*(1.-epsilon)))/(e.z()-s.z())+epsilonStart);
}
}
// OSG_NOTICE<<"clampped segment "<<s<<" "<<e<<std::endl;
// if (s==e) return false;
return true;
}
osg::Texture* LineSegmentIntersector::Intersection::getTextureLookUp(osg::Vec3& tc) const
{
osg::Geometry* geometry = drawable.valid() ? drawable->asGeometry() : 0;
osg::Vec3Array* vertices = geometry ? dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray()) : 0;
if (vertices)
{
if (indexList.size()==3 && ratioList.size()==3)
{
unsigned int i1 = indexList[0];
unsigned int i2 = indexList[1];
unsigned int i3 = indexList[2];
float r1 = ratioList[0];
float r2 = ratioList[1];
float r3 = ratioList[2];
osg::Array* texcoords = (geometry->getNumTexCoordArrays()>0) ? geometry->getTexCoordArray(0) : 0;
osg::FloatArray* texcoords_FloatArray = dynamic_cast<osg::FloatArray*>(texcoords);
osg::Vec2Array* texcoords_Vec2Array = dynamic_cast<osg::Vec2Array*>(texcoords);
osg::Vec3Array* texcoords_Vec3Array = dynamic_cast<osg::Vec3Array*>(texcoords);
if (texcoords_FloatArray)
{
// we have tex coord array so now we can compute the final tex coord at the point of intersection.
float tc1 = (*texcoords_FloatArray)[i1];
float tc2 = (*texcoords_FloatArray)[i2];
float tc3 = (*texcoords_FloatArray)[i3];
tc.x() = tc1*r1 + tc2*r2 + tc3*r3;
}
else if (texcoords_Vec2Array)
{
// we have tex coord array so now we can compute the final tex coord at the point of intersection.
const osg::Vec2& tc1 = (*texcoords_Vec2Array)[i1];
const osg::Vec2& tc2 = (*texcoords_Vec2Array)[i2];
const osg::Vec2& tc3 = (*texcoords_Vec2Array)[i3];
tc.x() = tc1.x()*r1 + tc2.x()*r2 + tc3.x()*r3;
tc.y() = tc1.y()*r1 + tc2.y()*r2 + tc3.y()*r3;
}
else if (texcoords_Vec3Array)
{
// we have tex coord array so now we can compute the final tex coord at the point of intersection.
const osg::Vec3& tc1 = (*texcoords_Vec3Array)[i1];
const osg::Vec3& tc2 = (*texcoords_Vec3Array)[i2];
const osg::Vec3& tc3 = (*texcoords_Vec3Array)[i3];
tc.x() = tc1.x()*r1 + tc2.x()*r2 + tc3.x()*r3;
tc.y() = tc1.y()*r1 + tc2.y()*r2 + tc3.y()*r3;
tc.z() = tc1.z()*r1 + tc2.z()*r2 + tc3.z()*r3;
}
else
{
return 0;
}
}
const osg::TexMat* activeTexMat = 0;
const osg::Texture* activeTexture = 0;
if (drawable->getStateSet())
{
const osg::TexMat* texMat = dynamic_cast<osg::TexMat*>(drawable->getStateSet()->getTextureAttribute(0,osg::StateAttribute::TEXMAT));
if (texMat) activeTexMat = texMat;
const osg::Texture* texture = dynamic_cast<osg::Texture*>(drawable->getStateSet()->getTextureAttribute(0,osg::StateAttribute::TEXTURE));
if (texture) activeTexture = texture;
}
for(osg::NodePath::const_reverse_iterator itr = nodePath.rbegin();
itr != nodePath.rend() && (!activeTexMat || !activeTexture);
++itr)
{
const osg::Node* node = *itr;
if (node->getStateSet())
{
if (!activeTexMat)
{
const osg::TexMat* texMat = dynamic_cast<const osg::TexMat*>(node->getStateSet()->getTextureAttribute(0,osg::StateAttribute::TEXMAT));
if (texMat) activeTexMat = texMat;
}
if (!activeTexture)
{
const osg::Texture* texture = dynamic_cast<const osg::Texture*>(node->getStateSet()->getTextureAttribute(0,osg::StateAttribute::TEXTURE));
if (texture) activeTexture = texture;
}
}
}
if (activeTexMat)
{
osg::Vec4 tc_transformed = osg::Vec4(tc.x(), tc.y(), tc.z() ,0.0f) * activeTexMat->getMatrix();
tc.x() = tc_transformed.x();
tc.y() = tc_transformed.y();
tc.z() = tc_transformed.z();
if (activeTexture && activeTexMat->getScaleByTextureRectangleSize())
{
tc.x() *= static_cast<float>(activeTexture->getTextureWidth());
tc.y() *= static_cast<float>(activeTexture->getTextureHeight());
tc.z() *= static_cast<float>(activeTexture->getTextureDepth());
}
}
return const_cast<osg::Texture*>(activeTexture);
}
return 0;
}
_______________________________________________
osg-submissions mailing list
[email protected]
http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegraph.org
