В 2D, как найти, пересекаются ли треугольник и AABB

Question

Я кодирую физический движок для пользовательского движка дум.

Я не ставлю себе целью воспроизвести точное поведение оригинальной гибели.

В думе каждая "вещь" (игрок, монстры и т. Д.) Является ограничивающим прямоугольником, ориентированным по оси.Я хочу сохранить это.

У меня уже есть работающий алгоритм тесселяции для секторов.

У меня уже есть рабочее дерево квадрантов, использующее блоки AABB с треугольниками секторов.

Квадратное дерево вернет список кандидатов на пересечение с заданной AABB (игрок, например).

Что я хочу: алгоритм для проверки того, что треугольник пересекает AABB в 2D.

Что я могу сделать: разбить AABB на два треугольника, затем выполнить проверку пересечения треугольник-треугольник.Что я могу сделать: использовать алгоритм «треугольник против aabb», работающий с 3D, и установить «z» на 0. Что я могу сделать:

1 / проверить, находится ли точка треугольника внутри AABB.

2 / проверьте, находится ли центр AABB внутри треугольника (центр - лучший кандидат, чтобы избежать проблем с округлением).

3 / проверьте, пересекает ли отрезок прямой треугольникасегмент AABB.

Я не хочу этого делать, потому что: я думаю, что, учитывая эту конкретную ситуацию, должен быть более оптимизированный способ сделать это.Это как раз то, с чем часто приходится сталкиваться графическому процессору: найти треугольник внутри области просмотра.Я думаю, что этот вопрос, более чем любой другой вопрос, был решен до чертиков.

Обратите внимание, что ситуация может быть еще проще: я могу перевести все, чтобы AABB начинался с (0, O).Я могу изменить размер всего, поэтому возникает вопрос: «Как определить, пересекается ли треугольник [0,1] [0,1]».

Я уже провел некоторые исследования, но:

1 /большинство результатов для 3D вещей.

2 / это, как ни странно, не часто освещаемый случай.Даже в книге «Кулинарная книга по физике игры» этот вопрос не упоминается.

3 / answers Я нашел, что это сложный, общий способ, с SAT (теорема об оси разделения) или эквивалентный материал.

Мне придется пройти этот тест для большого количества «штук» (игрока, монстра) на каждом кадре для каждого потенциального треугольника, заданного квадродеревом.

Есть еще один вариант, который у меня есть, но я действительно не знаю, с чего начать, или даже если это хорошая идея.Вот краткое изложение того, что у меня на уме.

1 /, поскольку в gpu уже есть все эти треугольники.

2 /, поскольку он массивно распараллелен.

3/ as, пройдя фиксированную стоимость, дополнительных затрат не будет.

=> спросите у gpu.

Но я не знаю, как это сделать.Коммуникационный процессор / GPU будет иметь стоимость, но фиксированную стоимость (примерно 1 или 100 000 штук будет стоить примерно столько же).Я предпочитаю избегать этого решения (но поскольку веб-сайт просит меня высказать идеи, которые у меня были, я об этом говорю).

Обратите внимание, что это мое первое сообщение на этом веб-сайте.Обратите внимание, что английский не мой родной язык.Обратите внимание, что сейчас, прямо здесь, сейчас 3:32 утра (ночью).Обратите внимание, что я не смогу ответить до завтра примерно в тот же час (и это действительно так для каждого дня).

Спасибо за чтение, заранее спасибо за ответы.

Answer 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.

См. В Rextester