How to Handle Corners in Segment Intersection Checks

user_7713512 0
Viewed 49

I am creating a ray-casting simulation that uses ray-segment intersection checks. On the corners where two segments meet the code determines there is no intersection.

I have tried extending the segments a small distance but this causes other issues with the simulation. What can I do in this situation?

The code for the intersection check:

struct Point {
    double x, y;
}

std::unique_ptr<Point> Ray::cast(const Boundary& wall) const {
    const double x1 = wall.a.x;
    const double y1 = wall.a.y;
    const double x2 = wall.b.x;
    const double y2 = wall.b.y;

    const double x3 = pos.x;
    const double y3 = pos.y;
    const double x4 = pos.x + dir.x;
    const double y4 = pos.y + dir.y;

    const double den = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    if (den == 0) {
        return nullptr;
    }

    const double t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / den;
    const double u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / den;

    if ((t > 0.0f && t < 1.0f) && u > 0.0f) {
        return std::make_unique<Point>(x1 + t * (x2 - x1), y1 + t * (y2 - y1));
    }
    else {
        return nullptr;
    }
}

Intersection Failure:

img

game-physics math c++
2 Answers

You need to include equal to checks for when the float is zero:

if ((t >= 0.0f && t <= 1.0f) && u >= 0.0f) {
user_15634800

One standard answer is to define the question in terms of points’ relationship to the ray being cast. It is known how to partition the plane into non-overlapping regions that are “left of”, “right of”, and optionally “on” a line. (The last is optional because you can arbitrarily include it in one of the other two.) Then a ray hits a line segment if the two endpoints are in different regions.

user_85862270
Related