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

问题描述 投票：1回答：1

我正在为自定义厄运引擎做物理引擎。

我不打算复制原始厄运的确切行为。

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

我已经有了一个工作的tesselation算法的行业。

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

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

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

我能做什么：将AABB分成两个三角形，然后进行三角形 - 三角形交叉检查。我能做什么：使用“三角形与aabb”算法一起使用3D并将“z”设置为0.我能做什么：

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

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

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

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

请注意，情况可以更简单：我可以翻译所有内容，以便AABB从（0，O）开始。我可以调整一切，所以问题变成：“如何确定三角形是否与[0,1] [0,1]相交”。

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

1 /大部分结果都是3D内容。

2 /这是一个不常见的案例。甚至在书中的“游戏物理食谱”中也没有提到这个问题。

3 /答案我发现了SAT（分离轴定理）或同等的东西，它是硬的，通用的方式。

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

我有一个最后的选择，但我真的不知道从哪里开始，或者即使这是一个好主意。以下是我脑海中的快速总结。

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

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

3 /，通过固定成本，没有额外费用。

=>问一下gpu。

但我不知道该怎么做。通信cpu / gpu将有一个成本，但是固定成本（对于1或100.000件事情，它的成本大致相同）。我更愿意避免这种解决方案（但是当网站要求我说出我的想法时，我正在谈论它）。

请注意，这是我在本网站上的第一条消息。请注意，英语不是我的母语。请注意，就在这里，现在是凌晨3点32分（在夜晚）。请注意，我将在大约同一时间之前无法回答（实际上每天都是如此）。

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

c algorithm 2d intersection aabb
1个回答
1
投票

这是我的尝试。原则上，您始终可以测试段交叉，但是如果要保存浮点运算，则有时可以使用快捷方式。 AABB将平面划分为九个区域（左上，上，右上，左，内，右，左下，下和右下）。如果您只是查看三角形点落入的区域，您可以确定必须或不能进行交叉。然而，有些情况不能在此基础上决定，并且必须回到几何交叉点。这是我的代码，我认为是正确的（因为，所有基于区域的测试都已明确定义），尽管我没有彻底测试。它相当长，但大多数是按位运算，所以它实际上应该非常快。入口点是函数intersects，主函数中有一个例子。

#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

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.