Um objeto tem uma posição e um vetor de velocidade. Normalmente, apenas a posição é usada para verificar se dois objetos colidem, o que é problemático para objetos em movimento muito rápido, pois pode acontecer que o objeto se mova tão rápido que fica na frente do primeiro objeto na primeira verificação de colisão e atrás dele na a segunda verificação de colisão.

Agora também há verificações de colisão com base em linhas, nas quais você verifica apenas se o vetor de movimento de cada objeto se cruza com a caixa delimitadora do outro. Isso pode ser visto como uma expansão de um ponto. Isso só funciona se o objeto em movimento rápido for realmente pequeno.

Então, minha ideia é, em vez de expandir um ponto, por que não expandir um retângulo? Isso resulta em um hexágono.

Agora, até agora tudo bem. Mas como eu realmente verifico se dois hexágonos desse tipo se cruzam? Observe que estes são hexágonos muito específicos.

Pergunta do bônus : É possível calcular onde exatamente (ou melhor, depois de quanto tempo) a colisão ocorreu? Isso pode ser muito útil para detectar o que realmente aconteceu, como onde e com quanto poder e para simular como eles se moviam no tempo entre a colisão e o final do quadro.

A solução é realmente mais simples do que o esperado. O truque é usar a subtração de Minkowski antes da sua técnica hexagonal.

Aqui estão seus retângulos A e B, com suas velocidades vAe vB. Observe que, vAe vBna verdade não são velocidades, elas são a distância percorrida durante um quadro.

Agora substitua o retângulo B por um ponto P e o retângulo A pelo retângulo C = A + (- B), que possui dimensões a soma das dimensões de A e B. As propriedades de adição de Minkowski indicam que ocorre colisão entre o ponto e o novo retângulo se e somente se ocorrer colisão entre os dois retângulos originais:

Mas se o retângulo C se move ao longo do vetor vAe o ponto P se move ao longo do vetor vB, uma simples mudança no quadro de referência nos diz que é o mesmo que se o retângulo C ainda estivesse e o ponto P se movia ao longo do vetor vB-vA:

Você pode usar uma fórmula simples de interseção de segmento de caixa para dizer onde ocorre a colisão no novo quadro de referência.

O último passo é voltar ao quadro de referência apropriado. Apenas divida a distância percorrida pelo ponto até a interseção circundada pelo comprimento do vetor vB-vAe você obterá um valor stal que 0 < s < 1. A colisão acontece no momento em s * Tque Té a duração do seu quadro.

Comentário por madshogo :
Uma enorme vantagem dessa técnica sobre a da resposta do próprio Beast é que, se não houver rotação, a "subtração de Minkowski" A + (- B) pode ser calculada uma vez para todos os timestados subsequentes !

Assim, o único algoritmo que leva tempo em todo este (soma Minkowski, complexidade O (mn) , onde m é o número de vértices de um e n o número de vértices em B ) pode ser usado apenas uma vez, tornando eficaz de detecção de colisão um constante- problema de tempo!

Mais tarde, você pode jogar fora a soma depois de ter certeza de que A e B estão em diferentes partes da sua cena (do seu quadtree?) E não colidirão mais.

Por outro lado, o método de Beast exige muitos cálculos a cada etapa do tempo.

Além disso, para retângulos alinhados ao eixo, A + (- B) pode ser calculado de maneira muito mais simples do que computando todas as somas, vértice por vértice. Apenas expanda A adicionando a altura de B à sua altura e a largura de B à sua largura (metade de cada lado).

Mas tudo isso funciona apenas se A e B não estão girando e se ambos são convexos. Se houver rotação ou se você usar formas côncavas, deverá usar volumes / áreas varridos.
fim do comentário

Primeiro de tudo, no caso de retângulos alinhados ao eixo, a resposta de Kevin Reid é a melhor e o algoritmo é o mais rápido.

Segundo, para formas simples, use velocidades relativas (como visto abaixo) e o teorema do eixo separador para detecção de colisão. Ele vai dizer se uma colisão acontece no caso de movimento linear (sem rotação). E se houver rotação, você precisará de um pequeno intervalo de tempo para que seja preciso. Agora, para responder à pergunta:

Como saber no caso geral se duas formas convexas se cruzam?

Vou lhe dar um algoritmo que funciona para todas as formas convexas e não apenas hexágonos.

Suponha que X e Y são duas formas convexas. Eles cruzam se e somente se tiverem um ponto em comum, ou seja, existe um ponto x ∈ X e um ponto y ∈ Y tal que x = y . Se você considerar o espaço como um espaço vetorial, isso significa dizer x - y = 0 . E agora chegamos a esse negócio de Minkowski:

A soma Minkowski de X e Y é o conjunto de todos os x + y para x ∈ X e Y ∈ Y .

Um exemplo para X e Y

X, Y e sua soma de Minkowski, X + Y

Supondo que (-Y) é o conjunto de todos -y para y ∈ Y , dado o parágrafo anterior, X e Y se cruzam se e somente se X + (-Y) contiver 0 , ou seja, a origem .

Observação lateral: por que escrevo X + (-Y) em vez de X - Y ? Bem, porque em matemática há uma operação chamada diferença de Minkowski de A e B, que às vezes é escrita X - Y, mas não tem nada a ver com o conjunto de todos os x - y para x ∈ X e y ∈ Y (o verdadeiro Minkowski diferença é um pouco mais complexa).

Então, gostaríamos de calcular a soma de Minkowski de X e -Y e descobrir se ela contém a origem. A origem não é especial em comparação com qualquer outro ponto; portanto, para descobrir se a origem está dentro de um determinado domínio, usamos um algoritmo que pode nos dizer se algum ponto específico pertence a esse domínio.

A soma de Minkowski de X e Y tem uma propriedade legal, que é se X e Y são convexos, então X + Y também é. E descobrir se um ponto pertence a um conjunto convexo é muito mais fácil do que se esse conjunto não fosse (conhecido por ser) convexo.

Não podemos calcular todos os x - y para x ∈ X e y ∈ Y porque há uma infinidade desses pontos x e y , então, esperançosamente, já que X , Y e X + Y são convexos, podemos apenas usar os pontos "mais externos" que definem as formas X e Y , que são seus vértices, e obteremos os pontos mais externos de X + Y e também mais alguns.

Esses pontos adicionais são "cercados" pelos pontos mais externos de X + Y, para que não contribuam para definir a forma convexa recém-obtida. Dizemos que eles não definem o " casco convexo " do conjunto de pontos. Então, o que fazemos é nos livrar deles em preparação para o algoritmo final que nos diz se a origem está dentro do casco convexo.

O casco convexo de X + Y. Removemos os vértices "internos".

Portanto, temos

Um primeiro algoritmo ingênuo

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

Os loops obviamente têm complexidade O (mn), onde m e n são o número de vértices de cada forma. O minkoswkiconjunto contém no máximo elementos mn . O convexHullalgoritmo tem uma complexidade que depende do algoritmo usado e você pode apontar para O (k log (k)) em que k é o tamanho do conjunto de pontos; portanto, no nosso caso, obtemos O (mn log (mn) ) . O containsalgoritmo tem uma complexidade que é linear com o número de arestas (em 2D) ou faces (em 3D) do casco convexo, portanto depende realmente de suas formas iniciais, mas não será maior que O (mn) .

Vou deixar você procurar no google pelo containsalgoritmo para formas convexas, é bem comum. Posso colocá-lo aqui se tiver tempo.

Mas estamos fazendo a detecção de colisões, para que possamos otimizar muito

Originalmente, tínhamos dois corpos A e B se movendo sem rotação durante um intervalo de tempo dt (pelo que posso ver olhando suas fotos). Vamos chamar v _A e v _B as respectivas velocidades de A e B , que são constantes durante nosso timestep de duração dt . Temos o seguinte:

e, como você mostra nas fotos, esses corpos varrem áreas (ou volumes, em 3D) à medida que se movem:

e eles acabam como A ' e B' após o timestep.

Para aplicar nosso algoritmo ingênuo aqui, precisaríamos apenas calcular os volumes varridos. Mas não estamos fazendo isso.

No quadro de referência de B , B não se move (duh!). E A tem uma certa velocidade em relação a B que você obtém ao calcular v _A - v _B (você pode fazer o inverso, calcular a velocidade relativa de B no quadro de referência de A ).

Da esquerda para a direita: velocidades no quadro de referência base; velocidades relativas; computando velocidades relativas.

Por respeito B tão imóvel em seu próprio quadro de referência, você só tem que calcular o volume que A varre através de como ele se move durante dt com sua relativa velocidade v _A - v _B .

Isso diminui o número de vértices a serem usados ​​no cálculo da soma de Minkowski (às vezes bastante).

Outra possível otimização é no ponto em que você calcula o volume varrido por um dos corpos, digamos A. Você não precisa traduzir todos os vértices que compõem A. Somente aqueles que pertencem às arestas (faces em 3D) cujas exterior normal "face" a direção da varredura. Certamente você já percebeu isso quando calculou suas áreas varridas pelos quadrados. Você pode dizer se um normal está na direção da varredura usando seu produto escalar com a direção da varredura, que deve ser positiva.

A última otimização, que não tem nada a ver com sua pergunta sobre interseções, é realmente útil no nosso caso. Ele usa as velocidades relativas mencionadas e o chamado método do eixo de separação. Certamente você já sabe disso.

Suponha que você conheça os raios de A e B em relação aos seus centros de massa (ou seja, a distância entre o centro de massa e o vértice mais distante), assim:

Uma colisão pode ocorrer somente se é possível que o círculo delimitadora de uma encontram a de B . Vemos aqui que ele não vai, ea maneira de dizer ao computador que é calcular a distância C _B para I como na imagem a seguir e certifique-se que é maior do que a soma dos raios de A e B . Se for maior, sem colisão. Se for menor, colisão.

Isso não funciona muito bem com formas bastante longas, mas no caso de quadrados ou outras formas semelhantes, é uma heurística muito boa excluir a colisão .

O teorema do eixo de separação aplicado a B e o volume varrido por A , no entanto, informa se a colisão ocorre. A complexidade do algoritmo associado é linear com a soma dos números de vértices de cada forma convexa, mas é menos mágico quando chega a hora de realmente lidar com a colisão.

Nosso novo e melhor algoritmo que usa interseções para ajudar a detectar colisões, mas ainda não é tão bom quanto o teorema do eixo separador para dizer se uma colisão acontece

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}

Eu não acho que usar o 'hexágono' seja tão útil. Aqui está um esboço de uma maneira de obter colisões exatas para retângulos alinhados ao eixo:

Dois retângulos alinhados ao eixo se sobrepõem se e somente se os intervalos de coordenadas X se sobrepõem e os intervalos de coordenadas Y se sobrepõem. (Isso pode ser visto como um caso especial do teorema do eixo separador.) Ou seja, se você projetar os retângulos nos eixos X e Y, reduziu o problema a duas interseções linha-linha.

Calcule o intervalo de tempo no qual as duas linhas em um eixo se cruzam (por exemplo, começa no tempo (separação atual dos objetos / velocidade relativa dos objetos que se aproxima)) e faça o mesmo no outro eixo. Se esses intervalos de tempo se sobrepuserem, o primeiro tempo dentro da sobreposição será o tempo de colisão.

Eu não acho que exista uma maneira fácil de calcular a colisão de polígonos com mais lados que um retângulo. Eu o dividiria em formas primitivas como linhas e quadrados:

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

Observe como ignoro o estado inicial de cada objeto, pois isso deveria ter sido verificado durante o cálculo anterior.

Teorema do Eixo Separado

O teorema do eixo separado diz "Se pudermos encontrar um eixo no qual duas formas convexas não se cruzam, as duas formas não se cruzam" ou mais praticável para a TI:

"Duas formas convexas somente se cruzam se elas se cruzam em todos os eixos possíveis."

Para retângulos alinhados por eixo, existem exatamente 2 eixos possíveis: x e y. Mas o teorema não se limita aos retângulos, pode ser aplicado a qualquer forma convexa, apenas adicionando os outros eixos nos quais as formas podem se cruzar. Para obter mais detalhes sobre o tópico, consulte este tutorial pelo desenvolvedor do N: http://www.metanetsoftware.com/technique/tutorialA.html#section1

Implementado, fica assim:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Os eixos podem ser representados como vetores normalizados.

Um intervalo é uma linha unidimensional. O início deve ser definido no menor ponto projetado, e o final no maior ponto projetado.

Aplicando-o ao retângulo "varrido"

O hexágono na questão é produzido "varrendo" o AABB do objeto. A varredura adiciona exatamente um eixo de colisão possível a qualquer forma: o vetor de movimento.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

Até aí tudo bem, agora já podemos verificar se os dois hexágonos se cruzam. Mas fica ainda melhor.

Esta solução funcionará para quaisquer formas convexas (por exemplo, triângulos) e quaisquer formas convexas varridas (por exemplo, octógonos varridos). No entanto, quanto mais complexa a forma, menos eficaz ela será.

Bônus: Onde a mágica acontece.

Como eu disse, os únicos eixos adicionais são os vetores de movimento. O movimento é o tempo multiplicado pela velocidade; portanto, em certo sentido, eles não são apenas eixos espaciais, são eixos tempo-espaciais.

Isso significa que podemos derivar o tempo em que a colisão poderia ter acontecido a partir desses dois eixos. Para isso, precisamos encontrar a interseção entre as duas interseções nos eixos de movimento. Antes de podermos fazer isso, precisamos normalizar os dois intervalos, para que possamos compará-los.

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

Quando fiz essa pergunta, eu meio que aceitei o compromisso de que haverá alguns falsos positivos raros com esse método. Mas eu estava errado, ao verificar essa interseção de tempo, podemos testar se a colisão "realmente" aconteceu e podemos resolver esses falsos positivos com ela:

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

Se você perceber algum erro nos exemplos de código, avise-me, ainda não o implementei e, portanto, não pude testá-lo.

Contanto que as áreas varridas estejam fechadas (sem lacunas no limite formado pelas arestas), o seguinte funcionará (basta reduzir seus testes de colisão para linha-linha e ponto-ret / ponto-tri):

1. Suas bordas se tocam? (colisões linha a linha) Verifique se alguma linha da borda de uma área varrida cruza com qualquer linha da borda da outra área varrida. Cada área varrida possui 6 lados.

2. O pequeno está dentro do grande? (Use formas alinhadas ao eixo (ponto retângulo e ponto tri)) Reoriente (gire) as áreas varridas para que a maior seja alinhada ao eixo e teste se a menor é interna (testando se há algum canto ( deve ser tudo ou nenhum) está dentro da área de varredura alinhada ao eixo). Isso é feito decompondo seu hex em tris e rects.

O teste que você faz primeiro depende da probabilidade de cada um (faça o que mais ocorre primeiro).

Você pode achar mais fácil usar um círculo delimitador varrido (cápsula em vez de hexadecimal) porque é mais fácil dividi-lo em dois semicírculos e um retângulo quando estiver alinhado ao eixo. ..Eu vou deixar você desenhar a solução