Блог

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

Я не стремлюсь воспроизвести точное поведение исходного doom.

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

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

У меня уже есть рабочее квадратичное дерево, использующее поля 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 / ответы, которые я нашел, идут жестким, общим путем, с помощью SAT (теорема об оси разделения) или эквивалентного материала.

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

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

1 / поскольку в графическом процессоре уже есть все эти треугольники.

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

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

=> спросите графический процессор.

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

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

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

Вот моя попытка. В принципе, вы всегда можете проверить пересечения сегментов, но если вы хотите сохранить операции с плавающей запятой, есть случаи, когда вы можете использовать короткий путь. 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) amp; 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 amp; (TOP_LEFT | LEFT | BOTTOM_LEFT)) == r23 ||
                   (r23 amp; (TOP_LEFT | TOP | TOP_RIGHT)) == r23) {
            return -1;
        }
    case TOP:
        if (r23 == (LEFT | BOTTOM_RIGHT) ||
            r23 == (RIGHT | BOTTOM_LEFT)) {
            return 1;
        } else if ((r23 amp; (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 amp; (TOP_RIGHT | RIGHT | BOTTOM_RIGHT)) == r23 ||
                   (r23 amp; (TOP_RIGHT | TOP | TOP_LEFT)) == r23) {
            return -1;
        }
    case LEFT:
        if (r23 == (TOP | BOTTOM_RIGHT) ||
            r23 == (BOTTOM | TOP_RIGHT)) {
            return 1;
        } else if ((r23 amp; (TOP_LEFT | LEFT | BOTTOM_LEFT)) == r23) {
            return -1;
        }
    case RIGHT:
        if (r23 == (TOP | BOTTOM_LEFT) ||
            r23 == (BOTTOM | TOP_LEFT)) {
            return 1;
        } else if ((r23 amp; (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 amp; (BOTTOM_LEFT | LEFT | TOP_LEFT)) == r23 ||
                   (r23 amp; (BOTTOM_LEFT | BOTTOM | BOTTOM_RIGHT)) == r23) {
            return -1;
        }
    case BOTTOM:
        if (r23 == (LEFT | TOP_RIGHT) ||
            r23 == (RIGHT | TOP_LEFT)) {
            return 1;
        } else if ((r23 amp; (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 amp; (BOTTOM_RIGHT | RIGHT | TOP_RIGHT)) == r23 ||
                   (r23 amp; (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 amp; (TOP_LEFT | TOP | TOP_RIGHT)) == r12 ||
        (r12 amp; (BOTTOM_LEFT | BOTTOM | BOTTOM_RIGHT)) == r12 ||
        (r12 amp; (TOP_LEFT | LEFT | BOTTOM_LEFT)) == r12 ||
        (r12 amp; (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 amp;amp; t <= 1.f) {
        return 1;
    }
    t = (aabb->x1 - p1->x) / dx;
    if (t >= 0.f amp;amp; t <= 1.f) {
        return 1;
    }
    t = (aabb->y0 - p1->y) / dy;
    if (t >= 0.f amp;amp; t <= 1.f) {
        return 1;
    }
    t = (aabb->y1 - p1->y) / dy;
    if (t >= 0.f amp;amp; 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, amp;triangle->p1);
    Region r2 = aabb_region(aabb, amp;triangle->p2);
    Region r3 = aabb_region(aabb, amp;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, amp;triangle->p1, amp;triangle->p2, r1, r2)) {
        return 1;
    } else if (segment_intersects(aabb, amp;triangle->p1, amp;triangle->p3, r1, r3)) {
        return 1;
    } else if (segment_intersects(aabb, amp;triangle->p2, amp;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(amp;aabb, amp;triangle);
    printf("Intersects: %s.n", inter ? "yes" : "no");
    return 0;
}
 

Вывод:

 Intersects: yes.
 

Посмотрите это в Rext Tester