2차원 직선과 직선 교차 (Intersecting line and line)

직선을 다음과 같이 표현 한다.

두개의 직선이 만나므로 아래 식으로 시작하여 풀이 된다.

같은 벡터에 대해서 내적을 하면 0이 되는 관계를 이용한다.

먼저 s에 대해서 정리하고

다음 t에 대해서 정리한다.

d₁^⊥: d₁의 수직 성분
d₂^⊥: d₂의 수직 성분

그리고 s, t에 대해 정리된 식을 모아보면 다음과 같다.

아래의 경우 두 직선은 평행한 상태가 된다.

그리고 아래 3가지 경우에 따라서 s, t값의 범위를 확인하여
교차 검사를 진행하면 된다.

1. 직선의 경우(시작과 끝이 무한대)
    s, t는 무한대

2. 선분의 경우
    d가 단위 벡터의 경우
    0 <= s <= l₁, 0 <= t <= l₂
     (l_1,l₂:각 선분의 길이)

    d가 단위 벡터가 아닐 경우 (P_end - P_start)
    0 <= s <= 1, 0 <= t <= 1
    (P_start, P_end:선분의 시작점과 끝점)

3. 광선의 경우
    0 <= s, 0 <= t

두 번째 방법으로는 선분의 s, t범위를 이용하여 구하는 방법이 된다.

첫번째 교차 방법에서 사용했던 식을 가져와서 사용한다.

먼저 2개의 직선 r₁, r₂에 대해서 다음과 같이 나타낸다.

그리고 d를 단위 벡터가 아닌 직선의 끝점과 시작점의 차이로 나타낸다.

이렇게 해서 s, t에 대한 식을 다시 정리하면

식을 간략히 하기 위해 아래과 같이 정의하고 다시 식을 정리하면

s식의 분모를 t식의 분모와 동일하게 만들기 위해 아래 정의를 이용한다.

최종적으로 아래 식과 같이 정리 된다.

이제 교차 여부를 검사 하면 한다.

f의 값이 0이 되면 두 직선은 평행 상태가 된다.

평행이 아닐 경우에는 s, t값의 범위를 검사한다.

이 방법에서는 방향 벡터 d를 직선의 끝점과 시작점의 차를 이용하므로
선분의 경우 s, t는 아래를 만족 해야 한다.
0 <= s <= 1, 0 <= t <= 1

그러므로 아래 조건을 통과 하면 교차 상태가 된다.

s의 경우
if f > 0 then
   if d < 0 or d > f then no_intersect
else
   if d > 0 or d < f then no_intersect

t의 경우
if f > 0 then
   if e < 0 or e > f then no_intersect
else
   if e > 0 or e < f then no_intersect

참고자료
Real-Time Rendering 2판