Interseção de linha com o retângulo AABB?

De preferência sem usar qualquer tipo de loop, pois isso será usado em um jogo.

Desejo cruzar uma linha com um retângulo de tamanho arbitrário. Mas também desejo que o ponto de intersecção seja retornado.

É possível, eu fiz um pouco de googling, mas ainda não deu certo.

A linha é definida usando (x1, y1, x2, y2). O retângulo também tem esses dois pontos.

Eu recomendaria simplesmente fazer uma verificação de interseção de segmento de linha de segmento de linha em cada segmento de linha (borda) que compõe o retângulo. Aqui está um algoritmo de detecção de interseção de segmento de linha que escrevi há muito tempo, extraído de um dos meus antigos projetos XNA:

// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection) { intersection = Vector2.Zero; Vector2 b = a2 - a1; Vector2 d = b2 - b1; float bDotDPerp = bX * dY - bY * dX; // if b dot d == 0, it means the lines are parallel so have infinite intersection points if (bDotDPerp == 0) return false; Vector2 c = b1 - a1; float t = (cX * dY - cY * dX) / bDotDPerp; if (t < 0 || t > 1) return false; float u = (cX * bY - cY * bX) / bDotDPerp; if (u < 0 || u > 1) return false; intersection = a1 + t * b; return true; } 

Vou deixar de inserir cada borda no método acima e coletar os resultados como um exercício para o leitor 🙂


Editar 1 ano depois, agora eu fui para a universidade e fiz um curso de Gráficos:

Dê uma olhada no algoritmo de Cohen-Sutherland para fazer isso de forma eficiente quando você tem um grande conjunto de linhas onde a maioria não intercepta o retângulo. Ele usa uma grade de 9 segmentos e você coloca cada ponto final da linha em uma região da referida grade:

grade

Usando isso, podemos dizer se não haverá interseções de linha:

grade com linhas

Por exemplo, aqui o CD não irá cruzar o retângulo (mostrado em vermelho na primeira imagem), pois C e D estão na linha superior e nem AB . Para aqueles onde a linha pode cruzar o retângulo, temos que tentar as interseções de linha de linha.

A forma como as seções são numeradas / rotuladas nos permite simplesmente fazer x AND y != 0 (onde x e y são os labels das seções para cada um dos pontos finais da linha) para determinar se não haverá interseção.

Usar este método significa que temos muitas, muitas interseções de linhas de linha que aceleram a coisa toda massivamente.