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
