Pontifícia Universidade de Católica do Rio Grande do Sul

Faculdade de Informática

Computação Gráfica



Detecção de Colisão entre Segmentos de Reta

Em primeiro lugar é necessário diferencia Cálculo e Detecção de colisão entre objetos.
Cálculo de Colisão significa determinar, através de equações ou de algum algoritmo iterativo a região(ponto, reta, plano, volume) de colisão entre dois objetos.
Detecção de Colisão significa determinar, se existe ou não colisão entre dois objetos.

A seguir é apresentado um algoritmo para detecção de colisão entre dois segmentos de reta.
 

Uso de Envelopes

Para acelerar o processo de deteção de colisão, em primeiro lugar deve-se utilizar um envelope retangular que englobe um dos segmentos de reta e testar este envelope contra os dois pontos extremos do outro segmento de reta.
Estes teste tem o objetivo de determinar a IMPOSSIBILIDADE de existência da colisão, nuca de confirmar se ela existe. Na figura 1,  por exemplo, os testes determinarão que os extrremos de uma das retas não está dentro do envelope da outra.

Figura 1 - Uso de Envelopes Descartando Colisão entre Segmentos de Reta

É importante notar que os testes com os envelopes devem ser realizados tomando-se o envelope de uma das retas contra os vértices da outra e vice-versa. Na figura 2, por exemplo o teste esquerda informaria que poder haver uma colisão entre as retas, mas o teste da direita, descarta esta possibilidade.
 

Figura 2 - Duplo teste com Envelopes

Determinação da Intersecção

Existem casos, entretanto em que o testes com envelopes não é conclusivo, exigindo um teste matemático mais efetivo. Para estes casos, deve-se calcular de que lado os pontos extremos de uma reta estão em relação a outra. Se ambos os pontos estiverem do mesmo lado, não há intereseção. Da mesma forma que o exemplo anteriro, este teste tem que ser feito tomando-se os pontos de uma das retas e testandos-os contra a outra e vice-versa.

Tomando o caso da figura 3, pode-se saber de que lado da reta CD estão os pontos A e B através do seguinte algoritmo:

1) Cria-se um vetor que represente a reta CD:

        VCD = D-C

2) Cria-se um vetor de C até A:

        VAC  =  A - C

3) Cria-se um vetor entre C até B:

        VBC  =  B - C

4) Faz-se o produto vetorial entre VCD e VAC e entre VCD e VBC:

        N1 = VCD x VAC

        N2 = VCD x VBC

5) Toma-se as componentes Z dos produtos vetoriais (N1 e N2). Se estas componentes tiverem mesmo sinal, então os pontos A e B estão do mesmo lado da reta CD; se forem diferentes, estão em lados diferentes.



Figura 3 -



Note que o mesmo processo deve ser repetido tomando AB como a reta e C e D como os pontos a serem testados.
 

Produto Vetorial

O produto vetorial entre dois vetores V1 e V2 é um vetor VN, perpendicular ao plano definido po V1 e V2.
O cálculo deste protudo pode ser efeito através da seguinte fórmula:
 N.x = V1.y * V2.z - V1.z * V2.y
 N.y = V1.z * V2.x - V1.x * V2.z
 N.z = V1.x * V2.y - V1.y * V2.x