2

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

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

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

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

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

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

我想要的是：一种算法来测试三角形是否与二维的 AABB 相交。

我能做的：将AABB分成两个三角形，然后进行三角形-三角形相交检查。我能做什么：使用 3D 的“三角形 vs aabb”算法并将“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 分（深夜）。请注意，我将无法在明天之前大致相同的时间回答（实际上每天都是如此）。

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

4

1 回答 1

2

这是我的尝试。原则上你总是可以测试线段相交，但如果你想保存浮点运算，在某些情况下你可以走捷径。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.

在 Rextester 中查看

于 2019-04-17T13:35:39.990 回答