与AABB矩形线交叉？

Question

优选地,不使用任何类型的循环,因为这将在游戏中使用.

我希望将一条线与一个任意大小的矩形相交.但我也希望返回交叉点[s].

这是可能的,我做了一些谷歌搜索,但仍然没有解决.

该线使用(x1,y1,x2,y2)定义.矩形也有这两点.

Answer 1

我建议简单地在构成矩形的每个线段(边缘)上进行线段线段交叉检查.这是我很久以前写过的线段交叉检测算法,从我的一个旧XNA项目中挖掘出来:

// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection)
{
    intersection = Vector2.Zero;

    Vector2 b = a2 - a1;
    Vector2 d = b2 - b1;
    float bDotDPerp = b.X * d.Y - b.Y * d.X;

    // if b dot d == 0, it means the lines are parallel so have infinite intersection points
    if (bDotDPerp == 0)
        return false;

    Vector2 c = b1 - a1;
    float t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
    if (t < 0 || t > 1)
        return false;

    float u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
    if (u < 0 || u > 1)
        return false;

    intersection = a1 + t * b;

    return true;
}

我将把每个边输入上面的方法并将结果作为练习收集给读者:)

编辑1年后,我已经上大学并完成了图形课程:

当你有一大堆不与矩形相交的线条时,看一下Cohen-Sutherland算法可以有效地做到这一点.它使用9段网格,并将该行的每个端点放置在所述网格的区域中:

使用这个,我们可以判断是否没有任何线交叉点:

例如,这里CD不会将矩形(在第一个图像中以红色显示)与两个相交,C并且D位于顶行,也不会AB.对于线可能与矩形相交的线,我们必须尝试线 - 线交叉点.

它们对部分进行编号/标记的方式允许我们简单地x AND y != 0(在哪里x和y是每个线的端点的部分的标签)来确定是否不存在交叉点.

使用这种方法意味着我们必须有许多,更少的线路交叉点,这大大加快了整个事物的速度.