在 2D 中，如何查找三角形和 AABB 是否相交

Question

我正在为自定义的末日引擎编写物理引擎。

我的目的不是复制原始厄运的确切行为。

在厄运中，每个 "thing"（玩家、怪物等）都是一个轴对齐的边界框。我想保留它。

我已经有了一个适用于扇区的细分算法。

我已经有了一个可用的四叉树，使用扇形三角形的 AABB 框。

四叉树将 return 与给定 AABB（例如玩家）相交的候选列表。

我想要的：一种测试三角形是否与 2D 中的 AABB 相交的算法。

我能做的：将AABB 分成两个三角形，然后进行三角形-三角形相交检查。我能做什么：使用 "triangle vs aabb" 算法处理 3D 并将 "z" 设置为 0。我能做什么：

1/检查三角形的一点是否在AABB内。

2/ 检查 AABB 的中心是否在三角形内部（中心是更好的候选者以避免舍入问题）。

3/检查三角形的线段是否与AABB的线段相交。

我不想那样做，因为 : 我认为鉴于这种精确的情况，应该有一种更优化的方法来做到这一点。这恰恰是 GPU 必须经常面对的事情：查找三角形是否在视口内。我认为这个问题比其他任何问题都更容易解决。

请注意，情况可能更简单：我可以翻译所有内容，因此 AABB 从 (0,O) 开始。我可以调整所有内容的大小，所以问题就变成了： "how to determine if a triangle intersect [0,1][0,1]".

我已经做了一些研究但是：

1/ 大多数结果都是针对 3D 内容的。

2/ 奇怪的是，这是一个不常涉及的案例。即使在书中"game physics cookbook"也没有提到这个问题。

3/ 答案我发现很难，通用的，方式，与 SAT（分离轴定理）或等效的东西。

对于四叉树给出的每个候选三角形，我必须对很多 "thing"（玩家，怪物）每一帧进行此测试。

我还有最后一个选择，但我真的不知道从哪里开始，即使这是个好主意。这是我的想法的快速总结。

1/ 因为 gpu 已经有了所有这些三角形。

2/ 因为它可以大规模并行化。

3/因为，通过固定成本，不会有额外成本。

=> 询问 gpu。

但我不知道该怎么做。沟通 cpu/gpu 会有成本，但是是固定成本（1 或 100.000 件东西的成本大致相同）。我宁愿避免这种解决方案（但由于网站要求我说出我的想法，所以我正在谈论它）。

请注意，这是我在此网站上的第一条消息。请注意，英语不是我的母语。请注意，现在是 3:32 am（晚上）。请注意，我无法在明天之前大致相同的时间回答（实际上每天都是如此）。

感谢阅读，提前感谢您的回答。

Answer 1

这是我的尝试。原则上你总是可以测试段相交，但如果你想节省浮点运算，有些情况下你可以走捷径。 AABB 将平面划分为九个区域（左上、上、右上、左、内、右、左下、下和右下）。如果你只看三角形的点所在的区域，你可能能够确定交叉点必须或不能发生。但是，有些情况不能在此基础上做出决定，因此有必要退回到几何交集。这是我的代码，我认为是正确的（例如，所有基于区域的测试都已明确定义），尽管我没有进行彻底测试。它相当长，但大部分是按位运算，所以实际上应该很快。入口点是函数intersects，main函数中有一个例子

#include <math.h>
#include <stdio.h>

#define EPSILON 1e-6

typedef struct AABB {
    float x0, y0, x1, y1;
} AABB;

typedef struct Point {
    float x, y, z;
} Point;

typedef struct Triangle {
    Point p1, p2, p3;
} Triangle;

// Naming assumes (0, 0) is top-left corner
typedef enum Region {
    TOP_LEFT     = 1 << 0,
    TOP          = 1 << 1,
    TOP_RIGHT    = 1 << 2,
    LEFT         = 1 << 3,
    INSIDE       = 1 << 4,
    RIGHT        = 1 << 5,
    BOTTOM_LEFT  = 1 << 6,
    BOTTOM       = 1 << 7,
    BOTTOM_RIGHT = 1 << 8
} Region;

// Find the region in which a point is with respect to the AABB
Region aabb_region(const AABB* aabb, const Point* point) {
    if (point->x < aabb->x0) {
        if (point->y < aabb->y0) {
            return TOP_LEFT;
        } else if (point->y > aabb->y1) {
            return BOTTOM_LEFT;
        } else {
            return LEFT;
        }
    } else if (point->x > aabb->x1) {
        if (point->y < aabb->y0) {
            return TOP_RIGHT;
        } else if (point->y > aabb->y1) {
            return BOTTOM_RIGHT;
        } else {
            return RIGHT;
        }
    } else {
        if (point->y < aabb->y0) {
            return TOP;
        } else if (point->y > aabb->y1) {
            return BOTTOM;
        } else {
            return INSIDE;
        }
    }
}

// 1: There is intersection
// 0: There may or may not be intersection
int regions_intersect_2(Region r1, Region r2) {
    if ((((r1 | r2) & INSIDE) != 0) ||
        ((r1 | r2) == (LEFT | RIGHT)) ||
        ((r1 | r2) == (TOP | BOTTOM))) {
        return 1;
    } else {
        return 0;
    }
}

// 1: There is intersection
// 0: There may or may not be intersection
// -1: There is no intersection
// Does not check cases already covered by regions_intersect_2
int regions_intersect_3(Region r1, Region r2, Region r3) {
    Region r23 = r2 | r3;
    switch (r1) {
    case TOP_LEFT:
        if (r23 == (BOTTOM | RIGHT) ||
            r23 == (BOTTOM | TOP_RIGHT) ||
            r23 == (RIGHT | BOTTOM_LEFT)) {
            return 1;
        } else if ((r23 & (TOP_LEFT | LEFT | BOTTOM_LEFT)) == r23 ||
                   (r23 & (TOP_LEFT | TOP | TOP_RIGHT)) == r23) {
            return -1;
        }
    case TOP:
        if (r23 == (LEFT | BOTTOM_RIGHT) ||
            r23 == (RIGHT | BOTTOM_LEFT)) {
            return 1;
        } else if ((r23 & (TOP_LEFT | TOP | TOP_RIGHT)) == r23) {
            return -1;
        }
    case TOP_RIGHT:
        if (r23 == (BOTTOM | LEFT) ||
            r23 == (BOTTOM | TOP_LEFT) ||
            r23 == (LEFT | BOTTOM_RIGHT)) {
            return 1;
        } else if ((r23 & (TOP_RIGHT | RIGHT | BOTTOM_RIGHT)) == r23 ||
                   (r23 & (TOP_RIGHT | TOP | TOP_LEFT)) == r23) {
            return -1;
        }
    case LEFT:
        if (r23 == (TOP | BOTTOM_RIGHT) ||
            r23 == (BOTTOM | TOP_RIGHT)) {
            return 1;
        } else if ((r23 & (TOP_LEFT | LEFT | BOTTOM_LEFT)) == r23) {
            return -1;
        }
    case RIGHT:
        if (r23 == (TOP | BOTTOM_LEFT) ||
            r23 == (BOTTOM | TOP_LEFT)) {
            return 1;
        } else if ((r23 & (TOP_RIGHT | RIGHT | BOTTOM_RIGHT)) == r23) {
            return -1;
        }
    case BOTTOM_LEFT:
        if (r23 == (TOP | RIGHT) ||
            r23 == (TOP | BOTTOM_RIGHT) ||
            r23 == (RIGHT | TOP_LEFT)) {
            return 1;
        } else if ((r23 & (BOTTOM_LEFT | LEFT | TOP_LEFT)) == r23 ||
                   (r23 & (BOTTOM_LEFT | BOTTOM | BOTTOM_RIGHT)) == r23) {
            return -1;
        }
    case BOTTOM:
        if (r23 == (LEFT | TOP_RIGHT) ||
            r23 == (RIGHT | TOP_LEFT)) {
            return 1;
        } else if ((r23 & (BOTTOM_LEFT | BOTTOM | BOTTOM_RIGHT)) == r23) {
            return -1;
        }
    case BOTTOM_RIGHT:
        if (r23 == (TOP | LEFT) ||
            r23 == (TOP | BOTTOM_LEFT) ||
            r23 == (LEFT | TOP_RIGHT)) {
            return 1;
        } else if ((r23 & (BOTTOM_RIGHT | RIGHT | TOP_RIGHT)) == r23 ||
                   (r23 & (BOTTOM_RIGHT | BOTTOM | BOTTOM_LEFT)) == r23) {
            return -1;
        }
    default:
        return 0;
    }
    return 0;
}

// Check if a segment intersects with the AABB
// Does not check cases already covered by regions_intersect_2 or regions_intersect_3
int segment_intersects(const AABB* aabb, const Point* p1, const Point* p2, Region r1, Region r2) {
    // Skip if intersection is impossible
    Region r12 = r1 | r2;
    if ((r12 & (TOP_LEFT | TOP | TOP_RIGHT)) == r12 ||
        (r12 & (BOTTOM_LEFT | BOTTOM | BOTTOM_RIGHT)) == r12 ||
        (r12 & (TOP_LEFT | LEFT | BOTTOM_LEFT)) == r12 ||
        (r12 & (TOP_RIGHT | RIGHT | BOTTOM_RIGHT)) == r12) {
        return 0;
    }
    float dx = p2->x - p1->x;
    float dy = p2->y - p1->y;
    if (fabsf(dx) < EPSILON || fabs(dy) < EPSILON) {
        // Vertical or horizontal line (or zero-sized vector)
        // If there were intersection we would have already picked it up
        return 0;
    }
    float t = (aabb->x0 - p1->x) / dx;
    if (t >= 0.f && t <= 1.f) {
        return 1;
    }
    t = (aabb->x1 - p1->x) / dx;
    if (t >= 0.f && t <= 1.f) {
        return 1;
    }
    t = (aabb->y0 - p1->y) / dy;
    if (t >= 0.f && t <= 1.f) {
        return 1;
    }
    t = (aabb->y1 - p1->y) / dy;
    if (t >= 0.f && t <= 1.f) {
        return 1;
    }
    return 0;
}

int intersects(const AABB* aabb, const Triangle* triangle) {
    // Find plane regions for each point
    Region r1 = aabb_region(aabb, &triangle->p1);
    Region r2 = aabb_region(aabb, &triangle->p2);
    Region r3 = aabb_region(aabb, &triangle->p3);
    // Check if any pair of regions implies intersection
    if (regions_intersect_2(r1, r2) ||
        regions_intersect_2(r1, r3) ||
        regions_intersect_2(r2, r3)) {
        return 1;
    }
    // Check if the three regions imply or forbid intersection
    switch (regions_intersect_3(r1, r2, r3)) {
    case 1:
        return 1;
    case -1:
        return 0;
    }
    // Check segment intersections
    if (segment_intersects(aabb, &triangle->p1, &triangle->p2, r1, r2)) {
        return 1;
    } else if (segment_intersects(aabb, &triangle->p1, &triangle->p3, r1, r3)) {
        return 1;
    } else if (segment_intersects(aabb, &triangle->p2, &triangle->p3, r2, r3)) {
        return 1;
    }
    return 0;
}

int main(int argc, char* argv[]) {
    AABB aabb = {
        /* x0 = */ 2.f,
        /* y0 = */ 1.f,
        /* x1 = */ 5.f,
        /* y1 = */ 6.f };
    Triangle triangle = {
        {1.f, 0.f}, {2.f, 2.f}, {2.f, -3.f}
    };
    int inter = intersects(&aabb, &triangle);
    printf("Intersects: %s.\n", inter ? "yes" : "no");
    return 0;
}

输出：

Intersects: yes.

See it in Rextester

在 2D 中，如何查找三角形和 AABB 是否相交

In 2D, how to find if a triangle and an AABB intersect

c

algorithm

2d

intersection

aabb