[osg-users] Finding the edge of a frustum, or intersection with the edge of a frustum

[Brad Colbert]

Hi,

I thought I would post my solution for finding the intersection of circles with a rectangle.  Used to test were circles are intersecting the edge of my Ortho projection.


Code:
bool isPointOnSegment(const osg::Vec3d& p1, const osg::Vec3d& p2, const osg::Vec3d& point)
{
    // First test that the point is co-linear
    osg::Vec3d v1 = p2 - p1;
    osg::Vec3d v2 = point - p1;

    // Cross product
    double z = v1.x() * v2.y() - v1.y() * v2.x();

    if(z)
        return false;

    // Dot product will tell us if it's between the points
    double dp1 = v1 * v1;
    double dp2 = v1 * v2;

    // On end
    if((dp1 == 0) || (dp1 == dp2))
        return true;

    // On Segment
    else if((dp1 > 0.0) && (dp2 < dp1))
        return true;

    return false;
}

//
template <typename T> int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}
std::list<osg::Vec3d> findLineCircleIntersections(const osg::Vec3d& p1, const osg::Vec3d& p2, const osg::Vec3d& center, const double r)
{
    std::list<osg::Vec3d> points;
    double dx, dy, A, B, C, dis, t;

    dx = p2.x() - p1.x();
    dy = p2.y() - p1.y();

    A = dx * dx + dy * dy;
    B = 2 * (dx * (p1.x() - center.x()) + dy * (p1.y() - center.y()));
    C = (p1.x() - center.x()) * (p1.x() - center.x()) +
        (p1.y() - center.y()) * (p1.y() - center.y()) -
        r * r;

    dis = B * B - 4 * A * C;

    if(dis < 0.0)
    {
        // No intersection
    }
    else
    {
        // Two solutions.
        double t1 = (float)((-B - sqrt(dis)) / (2 * A));
        double t2 = (float)((-B + sqrt(dis)) / (2 * A));

        double x1 = p1.x() + t2 * dx;
        double y1 = p1.y() + t2 * dy;
        osg::Vec3d point1(x1, y1, p1.z());

        if (dis == 0.0) // Tangent
        {
            // Validate
            if(isPointOnSegment(p1, p2, point1))
                points.push_back(point1);
        }
        else if (dis > 0.0)
        {
            double x2 = p1.x() + t1 * dx;
            double y2 = p1.y() + t1 * dy;
            osg::Vec3d point2(x2, y2, p1.z());

            // Two intersections
            if(isPointOnSegment(p1, p2, point1))
                points.push_back(osg::Vec3d(x1,y1,p1.z()));
            if(isPointOnSegment(p1, p2, point2))
                points.push_back(osg::Vec3d(x2,y2,p1.z()));
        }
    }

    return points;
}

std::list<osg::Vec3d> findRectangleCircleIntersections(const osg::Vec3d& s1p1, const osg::Vec3d& s1p2,
                                                       const osg::Vec3d& s2p1, const osg::Vec3d& s2p2,
                                                       const osg::Vec3d& s3p1, const osg::Vec3d& s3p2,
                                                       const osg::Vec3d& s4p1, const osg::Vec3d& s4p2,
                                                       const osg::Vec3d& center, const double r)
{
    std::list<osg::Vec3d> points;

    std::list<osg::Vec3d> s1points = findLineCircleIntersections(s1p1, s1p2, center, r);
    points.insert(points.end(), s1points.begin(), s1points.end());

    std::list<osg::Vec3d> s2points = findLineCircleIntersections(s2p1, s2p2, center, r);
    points.insert(points.end(), s2points.begin(), s2points.end());

    std::list<osg::Vec3d> s3points = findLineCircleIntersections(s3p1, s3p2, center, r);
    points.insert(points.end(), s3points.begin(), s3points.end());

    std::list<osg::Vec3d> s4points = findLineCircleIntersections(s4p1, s4p2, center, r);
    points.insert(points.end(), s4points.begin(), s4points.end());

    return points;
}




Cheers,
Brad

------------------
Read this topic online here:
http://forum.openscenegraph.org/viewtopic.php?p=76910#76910