Qual é a maneira mais rápida de verificar se dois AABBs em movimento se cruzam?

Eu tenho dois AABBs que estão se movendo. Qual é a maneira mais rápida de verificar se eles se cruzam sob um quadro?

Ao mover, não quero apenas verificar com o método usual de interseção de retângulos, quero dizer algum tipo de teste simples e fácil de varredura que só retorna um valor booleano, sem tempo de acerto ou qualquer outra coisa.

O que eu acho é simplesmente fazer assim:

Mas esse hexágono é bastante complexo e não sei como calcular uma interseção AABB - Polígono. Existe talvez uma maneira mais fácil?

Qualquer linguagem de programação que você mais gosta, eu posso facilmente portá-la.

Obrigado.

Use a soma de Minkowski

Uma boa maneira de resolver esse problema é considerar a interseção entre uma linha de movimento ( v ) traduzida para a origem ( v ' ) e a soma de Minkowski de A girada 180 graus na origem ( A' ) e seus obstáculos (apenas B neste caso): a' ⊕ B .

Na figura a seguir, coloco A smack-dab na origem de um sistema de coordenadas arbitrário. Isso simplifica a compreensão, pois girar A em 180 graus resulta em A ' e v traduzidos para a origem igual a v' .

A soma de Minkowski é o retângulo verde, e os pontos de interseção de um A móvel e um B estacionário podem ser encontrados através da interseção da linha AABB . Esses pontos são marcados com os círculos azuis.

Na figura a seguir, uma origem diferente foi usada e os mesmos pontos de interseção foram encontrados.

Vários AABBs em movimento

Para fazer isso funcionar para dois AABBs que se movem de maneira linear durante um período específico, você subtrai o vetor de velocidade de B do vetor de velocidade de A e o utiliza como segmento de linha para a interseção linha-AABB.

Pseudo-código

def normalize(aabb):
    return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2),
            y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2),

def rotate_about_origin(aabb):
    return normalize({x1: -aabb.x1, x2: -aabb.x2
                      y1: -aabb.y1, y2: -aabb.y2})

# given normalized aabb's
def minkowski_sum(aabb1, aabb2):
    return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2,
            y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2}

def get_line_segment_from_origin(v):
    return {x1: 0, y1: 0, x2: v.x, y2: v.y}

def moving_objects_with_aabb_intersection(object1, object2):
    A = object1.get_aabb()
    B = object2.get_aabb()

    # get A'⊕B
    rotated_A = rotate_about_origin(A)
    sum_aabb = minkowski_sum(rotated_A, B)

    # get v'
    total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity())
    line_segment = get_line_segment_from_origin(total_relative_velocity)

    # call your favorite line clipping algorithm
    return line_aabb_intersection(line_segment, sum_aabb)

Resposta à colisão

Dependendo da jogabilidade, você realizaria uma detecção de colisão mais refinada (talvez os AABBs contenham malhas) ou avançaria para a próxima fase: resposta à colisão.

Quando há uma colisão, o algoritmo de interseção de linha AABB retornará 1 ou 2 pontos de interseção, dependendo de A terminar o movimento dentro de B ou passar por ele, respectivamente. (Isso está descontando os casos degenerados em que A roça B ao longo de seus lados ou em um de seus respectivos cantos.)

De qualquer maneira, o primeiro ponto de interseção ao longo do segmento de linha é o ponto de colisão. Você o traduziria de volta à posição correta no sistema de coordenadas mundiais (o primeiro círculo azul claro na segunda foto ao longo do original v , chame-o de p ) e depois decida (por exemplo, para colisões elásticas refletindo v ao longo da colisão normal em p ) qual será a posição real de A no final do quadro ( At + 1 ).

Se houver mais do que apenas 2 colisores, isso ficará um pouco mais complexo, pois você também deseja detectar a colisão para a segunda parte refletida de v .

OBB - Caixa delimitadora orientada. Aqui está um tutorial

Efetivamente, uma caixa delimitadora alinhada com o vetor Velocity do objeto A como o eixo y (para cima). Sua largura e altura podem ser calculadas pelos pontos inicial e final do objeto A. Em seguida, você o compara com o AABB do objeto B (tratando-o como um OOBB) e com o seu ouro.

Se você está apenas procurando um teste rápido de interseção para ver se eles poderiam se cruzar, você pode criar um AABB que rodeie o AABB do objeto A nas posições inicial e final. Se um AABB não interceptar com esse AABB abrangente, não haverá interseção; No entanto, isso pode levar a falsos positivos, portanto você deve usá-lo apenas como teste preliminar.

Você não precisa de OOBs e não precisa usar a detecção de colisão com intervalo de tempo. Basta usar o teste AABB normal, consulte este link . Em essência, ele faz exatamente o que você tem em seu diagrama: o AABB em movimento é "varrido" do ponto inicial ao ponto final e então é usado para a detecção de colisão contra outros AABBs estáticos.

Se você está preocupado que esse teste varrido seja mais caro porque retorna um "tempo de impacto", acho que você está otimizando prematuramente.

Informações mais detalhadas sobre testes de varredura podem ser encontradas no excelente livro: Detecção de colisão em tempo real de Christer Ericson.

Você precisará primeiro decompor o movimento em etapas menores e usar essas informações para calcular um AABB de alto nível. Se os grandes AABBs se cruzarem, você poderá verificar as etapas menores para ser mais preciso.

Estimar se pode ou não ter ocorrido uma colisão verificando o AABB (ou OOBB) usando apenas as posições inicial e final pode perder colisões se um dos objetos estiver girando rapidamente e for mais longo em uma dimensão do que em outra.

Para calcular uma estimativa mais precisa do AABB, decomponha o movimento em etapas menores e, usando apenas o AABB inicial (não a malha do objeto), gire o AABB (agora apenas uma caixa, não alinhada ao eixo), pois o objeto giraria e se moveria a cada degrau. Os pontos máximo e mínimo de cada eixo fornecerão o AABB que encerra todo o movimento do objeto.

Se houver uma interseção com o AABB maior, você poderá usar os AABBs menores que já foram calculados para determinar onde a colisão pode ter sido. Para cada um dos AABBs menores que se cruzam com o outro objeto, você pode fazer a detecção de interseção de malha mais cara.

Você terá que decompor o movimento em etapas menores. Por exemplo:

Você deseja decompor o movimento usando o componente maior (neste caso, o eixo X) e, em seguida, verifique a colisão em cada etapa.

Isso pode parecer muito caro, mas leve em consideração que um objeto que se move mais rapidamente do que sua própria largura a cada ciclo será extremamente rápido, portanto esse cenário não é tão comum quanto você imagina.

Você também deve usar velocidades relativas para a verificação de colisão, para que um AABB seja "estático" e o outro se mova a uma velocidade de sua própria velocidade, menos a velocidade da "estática".

A maneira mais rápida de ver se eles podem se cruzar é apenas expandir o AABB em movimento com a velocidade.

por exemplo, o AABB está se movendo para a direita com 0,1 x / quadro, então você o estende para que a borda esquerda permaneça a mesma e a borda direita fique mais 0,1. Então você pode verificar com o novo AABB. Se falso, então não há colisão. (retorno antecipado e preciso para pequenas velocidades).

Então você pode verificar se o fim e o início do AABB do objeto em movimento se cruzam. se verdadeiro, então retorne verdadeiro.

Caso contrário, você precisa verificar se a diagonal cruza o ABB estático.

Isso envolve obter as coordenadas da diagonal em que x = borda esquerda da estática e borda direita ver se y está dentro da parte inferior e superior. (repita o contrário)