Как справиться с точным обнаружением столкновений с поворотом?

8

У кого-нибудь есть идеи, как добиться идеального обнаружения столкновений с помощью ротационных пикселей с помощью растровых изображений в Android? Или вообще по этому вопросу? В настоящее время у меня есть пиксельные массивы, но я не знаю, как управлять ими на основе произвольного числа градусов.

вьюжный
источник

Ответы:

11

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

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

Впоследствии, если необходима проверка столкновения с идеальным пикселем, то наиболее важным моментом является то, что вы должны выполнить эту проверку в том же месте . Это можно сделать, взяв каждый пиксель из спрайта A, применив серию преобразований, чтобы поместить их в локальное пространство спрайта B, а затем проверьте, не сталкивается ли он с каким-либо пикселем в этой позиции на спрайте B. Столкновение происходит, когда оба пикселя проверено непрозрачно.

Итак, первое, что вам нужно, это построить мировую матрицу для каждого из спрайтов. Возможно, в Интернете есть учебники, в которых вы узнаете, как их создать, но в основном это должно быть объединение нескольких более простых матриц в следующем порядке:

Translation(-Origin) * Scale * Rotation * Translation(Position)

Полезность этой матрицы заключается в том, что путем умножения точки в локальном пространстве - и, например, если вы получаете пиксели с использованием метода, подобного bitmap.getPixelAt(10,20)10,20, определяется в локальном пространстве - соответствующая мировая матрица переместит ее в мировое пространство:

LocalA * WorldMatrixA -> World
LocalB * WorldMatrixB -> World

И если вы инвертируете матрицы, вы также можете пойти в противоположном направлении, то есть преобразовать точки из мирового пространства в каждое из локальных пространств спрайта в зависимости от того, какую матрицу вы использовали:

World * InverseWorldMatrixA -> LocalA
World * InverseWorldMatrixB -> LocalB

Таким образом, чтобы переместить точку из локального пространства спрайта A в локальное пространство спрайта B , вы сначала трансформируете ее, используя мировую матрицу спрайта A, чтобы перевести ее в мировое пространство, а затем, используя матрицу обратного мира спрайта B , чтобы получить ее в Локальное пространство спрайта Б:

LocalA * WorldMatrixA -> World * InverseWorldMatrixB -> LocalB

После преобразования вы проверяете, попадает ли новая точка в границы спрайта B, и если это так, вы проверяете пиксель в этом месте, как вы это делали для спрайта A. Таким образом, весь процесс становится примерно таким (в псевдокоде и непроверенном) :

bool PixelCollision(Sprite a, Sprite B)
{
    // Go over each pixel in A
    for(i=0; i<a.Width; ++i)
    {
        for(j=0; j<a.Height; ++j)
        {
            // Check if pixel is solid in sprite A
            bool solidA = a.getPixelAt(i,j).Alpha > 0;

            // Calculate where that pixel lies within sprite B's bounds
            Vector3 positionB = new Vector3(i,j,0) * a.WorldMatrix * b.InverseWorldMatrix;

            // If it's outside bounds skip to the next pixel
            if(positionB.X<0 || positionB.Y<0 || 
               positionB.X>=b.Width || positionB.Y>=b.Height) continue;

            // Check if pixel is solid in sprite B
            bool solidB = b.getPixelAt(positionB.X, positionB.Y).Alpha > 0;

            // If both are solid then report collision
            if(solidA && solidB) return true;
        }
    }
    return false;
}
Дэвид Гувея
источник
1
Мне это нравится, потому что это элегантно, но использование таких матриц - умножение матрицы 3х3 на пиксель на кадр - приведет к довольно серьезным потерям производительности для любых, кроме самых маленьких, растровых изображений, особенно на большинстве устройств Android.
3Dave
2
@DavidLively Действительно, это будет, это дорогостоящий процесс в вычислительном отношении. И я думаю, что даже с учетом того, что матричные вычисления развернуты в регулярные вычисления с тригонометрией - возможно, не прибегая к масштабированию, если он не используется - он все равно будет примерно таким же. Могут быть и другие решения, но я не могу придумать ни одного. В конечном счете, лучшим решением было бы подумать, действительно ли пиксельное обнаружение столкновений действительно необходимо вообще. И некоторые игры, использующие идеальные столкновения по пикселям (например, первые игры Sonic), вместо этого превращают персонажей в ряд точек столкновения.
Дэвид Гувейа
хорошая точка зрения; Я ломаю голову, пытаясь найти альтернативное решение, которое не включает вычитание растровых изображений и поиск пиков. Вероятно, где-то есть возможность для бумаги. :) Мантра: оптимально против достаточного ... оптимально против достаточного ..
3Dave
Большое спасибо, это действительно отличное объяснение. В настоящее время у меня настроено обнаружение столкновений ограничивающего прямоугольника, и если это происходит, я проверяю перекрытие пикселей между двумя растровыми изображениями, но только в перекрывающемся прямоугольнике. Все это прекрасно работает и не слишком интенсивно использует процессор. Проблема возникает, когда я поворачиваю изображение. Сами пиксели не вращаются в растровом изображении. Я просто рисую повернутое изображение. Поэтому, когда я продолжаю проверять столкновение пикселей, он все еще использует старые пиксели. Мне нравится то, что вы сказали о сопоставлении пикселей с мировыми координатами. Это вполне может быть то, что мне нужно сделать. Спасибо!!!
DRiFTy
+1 Мне всегда было интересно, как работает алгоритм, спасибо @DavidGouveia
Вишну
2

Хотя ответ Дэвида Гувейя звучит правильно, это не лучшее решение с точки зрения производительности. Есть несколько важных оптимизаций, которые вам нужно сделать:

  1. Разберитесь и избегайте ненужных проверок, проверяя сначала простым столкновением окружности: чтобы получить центр и радиус ваших спрайтов в любом вращении, получите координаты минимумов и максимумов x и y всех 4 (уже повернутых) вершин: затем вы можете построить замыкание круга в спрайте

    центр = max_x-min_x / 2, max_y-min_y / 2

    радиус = max (max_x-min_x, max_y-min_y)

  2. теперь у вас должно быть не слишком много кандидатов для проверки путем растеризации уже преобразованных (повернутых) изображений, в основном с использованием простого аффинного алгоритма наложения текстур . По сути, вы отслеживаете 4 строки на растеризованный спрайт: 2 строки, идущие от вершины a до следующих вершин вашего повернутого блока (b и c) 2 линии, идущие в «растровом пространстве» от вершины u1 / v1 до следующих вершин u2 / v2 и u3 / v3: Примечание: я погуглил это изображение, и оно показывает треугольник, ваши прямоугольники - это всего лишь два треугольника. Для этого алгоритма жизненно важно рисовать горизонтальные линии (именно поэтому он называется « растеризатор »), чтобы избежать «дырок» внутри растрового изображения из-за ошибок округления. Вычисляя строки по алгоритму Брезенхэмадля каждого пикселя требуется только 4 сложения и 4 сравнения (а иногда и два дополнительных, в зависимости от наклона). Вы пишете свой собственный многоугольный текстурный картограф, но без дорогостоящей (и сложной для оптимизации) 3D-коррекции. аффинное наложение текстур

  3. Вы можете легко уменьшить разрешение битовых карт столкновений (например, в 2 раза) и сэкономить еще больше времени. проверка столкновения на половине разрешения должна быть незаметной.

  4. Если вы используете ускорение графики, можно использовать какую-то проверку буфера с HW-ускорением (трафарет?), Чтобы избежать кодирования растеризатора самостоятельно.

Основная проблема: Java не очень быстро обращается к растровым данным, хранящимся в 2D-массиве. Я бы рекомендовал хранить данные в одномерном массиве, чтобы избежать хотя бы одной проверки indexOutOfBounds для каждого доступа. Также используйте измерения степени 2 (например, 64x64, 128x128 и т. Д. Таким образом, вы можете вычислить смещение с помощью сдвига битов, а не умножения). Вы также можете оптимизировать второй доступ к текстуре, чтобы выполнить его, только если первый имеет значение! = 0 (прозрачный)

Все эти проблемы были решены в программных средствах рендеринга, было бы полезно изучить исходный код

Питер Паркер
источник