직선과 다각형의 교차점 구하기

렌더링 할 때 삼각형이 일반적으로 많이 사용되지만, 직선과 다각형의 교차점을 찾는 문제 역시 많이 사용되므로 알아볼만 하다. n 개의 정점을 가지는 닫힌 다각형(Closed polygon)과 다각형이 포함되는 평면을 다음 그림과 같이 정의하고 직선과 평면의 교차점 찾기를 이용하여 p를 먼저 찾는다.

 

 

 

 

평면과의 교차점 p를 찾았으면 그 점이 다각형 안에 있는지 밖에 있는지만 판단하면 된다. 여기서부터는 2D로 생각해도 되므로 다각형과 점 p를 xy/xz/yz 평면 중 한 곳으로 projection한다. 이 때 다각형을 사영(projection)했을 때 면적이 제일 큰 평면을 선택하면 된다. 면적을 제일 크게 만드는 평면을 고르는 방법은 평면의 법선벡터에서 절대값이 가장 큰값에 대응되는 좌표 성분은 건너뛰고 나머지를 2차원 좌표로 사용하면 된다. 예를 들어 평면의 법선이 (0.5, -1, 0)일 때 y성분을 없애고 xz평면에 사영시켜야 면적이 최대화 된다. 

 

 

이제 2D공간에서 점p가 다각형 안쪽에 위치하는지 바깥쪽에 위치하는지 판단하기 위해 Crossing Test를 수행해보자.

 

 

 

 

점 p 에서 임의의 광선(간단하게 +x 방향으로 쏜다고 생각해도 된다.)을 쏘았을 때 다각형의 에지와 홀수번 만나면 점은 내부에 있다. 대신에 이렇게 검사하는 방식은 다각형이 self-intersection이 없는 경우에만 유효하다.

 

 

검사를 쉽게 하기 위해, 점 p를 원점으로 이동시키고 그만큼 다각형도 이동시킨 후 에지와 x축과의 교차점 개수를 찾는 문제로 살짝 바꿔보자.

 

 

• 만약 다각형 에지의 양끝 y-좌표가 같은 부호라면 그 에지는 x-축과 만나지 않는다.
• 다각형 에지의 양끝 y-좌표가 다른 부호라면 에지는 x-축과 만나므로
  • 만약 다각형 에지의 양끝 x-좌표가 모두 양수 라면 교차점 개수를 1개 증가시킨다.
  • 다각형 에지의 양끝 x-좌표가 다른 부호라면 에지와 x-축과의 교차점을 계산하여 양수인 경우에만 교차점 개수를 1개 증가시킨다.
• 총 교차점 개수가 홀수라면 점 p는 다각형 내부에 위치하고 짝수라면 외부에 위치한다.

 

 

 

[참고] Real-time rendering. Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman.