광선 교차 판정

광선 교차 판정은 쏘아 보낸 직선이 물체에 맞는지 가려냅니다. 맞았다면 얼마나 날아가서 맞았는지도 셉니다. 레이 트레이싱은 화면의 점마다 이 직선을 쏘아 처음 맞은 물체를 찾습니다. 그래서 화면 한 장을 그리는 데 이 판정이 수백만 번 넘게 돕니다.

쉽고 빠른 이해

광선 교차 판정은 「이 직선이 이 삼각형에 맞나」에 답합니다. 눈에서 화면의 한 점을 지나 쏜 직선이 의자 다리의 삼각형 하나에 맞으면, 그 점에는 의자 다리가 보입니다.

레이 트레이싱은 화면의 점마다 무엇이 보이는지를 이 답으로 정합니다. 그림자도 같은 판정으로 냅니다. 바닥에서 전등 쪽으로 직선을 쏘아 중간에 무언가 맞으면 그 바닥은 그늘입니다.

1. 직선을 출발점과 방향으로 적고, 얼마나 날아갔는지를 숫자 하나로 셉니다
2. 평면이나 구를 나타내는 식에 그 직선을 넣어 맞는 거리를 풉니다. 답이 없으면 빗나간 것입니다
3. 맞은 것이 여럿이면 가장 가까운 것을 고릅니다

판정 한 번은 곱셈과 덧셈 몇십 번이라 가볍습니다. 그런데 광선 수에 물체 수를 곱한 만큼 돌리면 감당이 안 됩니다. 그래서 맞을 리 없는 물체를 미리 걸러 주는 구조와 함께 씁니다. 계산 오차 때문에 방금 떠난 면에 다시 맞는 문제도 따로 막아야 합니다.

보통 게임은 화면을 그릴 때 이 판정을 쓰지 않습니다. 삼각형을 하나씩 화면에 비춰 그리는 래스터화로 그립니다. 그림자나 반사만 광선으로 보탭니다.

상세

이 절은 광선을 숫자로 적는 법부터 봅니다. 그다음 평면 · 구 · 삼각형 · 상자 넷과 광선의 교차를 숫자로 따라갑니다. 끝으로 맞은 것이 여럿일 때 고르는 법, 계산 오차가 만드는 문제, 이 판정을 쓰는 곳과 안 쓰는 곳을 짚습니다.

광선과 적중

레이 트레이싱은 눈에서 화면의 점 하나를 지나는 직선을 쏘아 그 점의 색을 정하는 그리기 방식입니다. 이 직선을 광선이라고 부릅니다. 광선이 처음 맞은 물체가 그 점에 보이는 물체입니다. 광선이 무엇에 맞았는지 모르면 그 점에 칠할 색을 정할 수 없습니다.

광선이 물체에 맞는 것을 적중이라고 부릅니다. 광선 교차 판정은 광선 하나와 물체 하나를 받아 적중인지 아닌지를 돌려줍니다. 적중이면 그 지점까지 얼마나 날아갔는지도 함께 돌려줍니다.

입체 모델은 대개 작은 삼각형 수천에서 수만 개를 이어 붙여 만듭니다. 그래서 판정의 상대는 대부분 삼각형입니다. 구나 상자처럼 식이 간단한 도형도 판정할 수 있어서 아래에서 함께 봅니다.

광선을 식으로 적기

광선은 출발점 하나와 방향 하나로 정해집니다. 출발점을 o, 방향을 d 라고 씁니다. 둘 다 x, y, z 세 값으로 된 벡터입니다.

광선 위의 점은 출발점에서 방향으로 얼마만큼 갔는지로 적습니다. 그 양을 t 라고 두면 점은 o + t·d 입니다. t·d 는 방향 d 의 x, y, z 값에 각각 t 를 곱한 벡터입니다. 출발점이 (0, 0, 0), 방향이 (0, 0, 1) 인 광선에서 t 가 3 인 점은 (0, 0, 3) 입니다.

방향의 길이를 1 로 맞춰 두면 t 가 곧 출발점에서의 거리입니다. 그래서 「얼마나 가서 맞았나」를 t 하나로 셉니다.

t 가 음수인 점은 출발점 뒤에 있습니다. 광선은 앞으로만 날아가므로 t 가 음수인 적중은 버립니다. 판정이 내는 답은 둘입니다. 적중했는지와 t 가 얼마인지입니다.

평면과의 교차

가장 쉬운 상대는 끝없이 펼쳐진 평면입니다. 평면은 그 면에 수직인 화살표 하나와 숫자 하나로 적습니다. 이 화살표가 법선입니다. 이 문서에서는 법선을 n 으로 씁니다.

평면 식에는 내적이라는 계산이 들어갑니다. 두 벡터의 x, y, z 값을 짝지어 곱한 뒤 더하는 계산입니다. (1, 2, 0) 과 (3, 0, 5) 의 내적은 1×3 + 2×0 + 0×5 = 3 입니다.

이 문서에서는 내적도 n·p 처럼 가운뎃점으로 씁니다. 가운뎃점 양쪽이 둘 다 벡터면 내적입니다. 한쪽이 숫자면 앞의 t·d 처럼 벡터의 각 값에 그 숫자를 곱한다는 뜻입니다.

평면은 n·p 가 어떤 숫자 k 와 같은 점 p 의 모임입니다. 법선이 (0, 0, 1) 이고 k 가 10 이면 z 가 10 인 점이 전부 이 평면에 듭니다. 바닥에서 높이 10 에 깔린 유리판 한 장을 떠올리면 됩니다.

광선의 점 o + t·d 를 p 대신 넣으면 n·(o + t·d) = k 입니다. 내적은 괄호 안의 덧셈에 하나씩 나눠 걸 수 있습니다. 곱해진 숫자 t 는 밖으로 꺼낼 수 있습니다. 그래서 식은 n·o + t(n·d) = k 가 됩니다.

이것을 t 에 대해 풀면 t = (k − n·o) / (n·d) 입니다. 출발점 (0, 0, 0), 방향 (0, 0, 1) 인 광선이면 n·o 는 0, n·d 는 1 이라서 t 는 10 입니다.

계산 결과에 따라 판정은 셋 중 하나로 갈립니다.

방향이 (1, 0, 0) 인 광선은 n·d 가 0 이라 높이 10 의 평면과 영영 안 만납니다. 출발점이 (0, 0, 20) 이고 방향이 (0, 0, 1) 이면 t 가 −10 이 나옵니다. 평면이 광선 뒤쪽에 있다는 뜻입니다.

구와의 교차

구는 중심 c 에서 거리가 반지름 r 인 점들의 모임입니다. 광선의 점을 이 조건에 넣으면 t 에 대한 이차방정식이 나옵니다. 근이 몇 개냐가 곧 판정입니다.

이차방정식의 근이 몇 개인지는 판별식으로 압니다. 근의 공식에서 제곱근 안에 든 값입니다. 이 값이 음수면 근이 없습니다. 0 이면 근이 하나, 양수면 둘입니다.

숫자로 따라가 봅니다. 출발점 (0, 0, 0), 방향 (0, 0, 1) 인 광선과, 중심이 (0, 0, 10) 이고 반지름이 2 인 구입니다. 광선 위의 점은 (0, 0, t) 이고 중심까지 거리는 t 와 10 의 차이입니다.

이 거리가 2 가 되는 t 는 8 과 12 입니다. 8 은 광선이 구에 들어가는 점입니다. 12 는 뒤로 빠져나오는 점입니다. 눈에 보이는 것은 앞쪽 표면이라서 작은 근 8 을 고릅니다.

출발점이 구 안에 있으면 작은 근이 음수로 나옵니다. 들어가는 점이 출발점 뒤에 있는 것입니다. 그때는 큰 근이 적중입니다.

삼각형과의 교차

삼각형 판정은 두 물음으로 나뉩니다. 첫째는 광선이 삼각형이 놓인 평면에 맞는지입니다. 둘째는 맞은 점이 삼각형 안쪽인지입니다. 첫 물음은 앞에서 본 평면 판정입니다.

둘째 물음에는 무게중심 좌표를 씁니다. 삼각형의 꼭짓점을 A, B, C 라고 하면, 같은 평면 위의 점 P 는 P = A + u·(B − A) + v·(C − A) 로 적을 수 있습니다. A 에서 출발해 B 쪽으로 u 만큼, C 쪽으로 v 만큼 간 점이라는 뜻입니다.

여기에 w = 1 − u − v 를 하나 더 둡니다. 셋을 다시 모으면 P 는 w·A + u·B + v·C 가 됩니다. 세 값은 P 가 각 꼭짓점에 얼마나 가까운지를 나타내는 비율입니다.

u, v, w 가 모두 0 이상이면 P 는 삼각형 안에 있습니다. 하나라도 음수면 P 는 그 꼭짓점의 맞은편 변 바깥으로 나가 있습니다. 판정은 이 부호 셋만 보면 됩니다.

숫자로 따라가 봅니다. 꼭짓점이 A = (0, 0, 5), B = (4, 0, 5), C = (0, 4, 5) 인 삼각형은 높이 5 의 평면에 누워 있습니다. B − A 는 (4, 0, 0), C − A 는 (0, 4, 0) 이라서 u 는 x 를 4 로 나눈 값, v 는 y 를 4 로 나눈 값입니다. 방향이 (0, 0, 1) 인 광선 두 줄기를 쏩니다.

두 광선 모두 t 가 5 인 지점에서 평면에 닿습니다. 첫째 광선은 세 값이 모두 양수라 삼각형 안에 맞았습니다. 둘째 광선은 w 가 음수입니다. A 의 맞은편 변, 곧 B 와 C 를 잇는 빗변 바깥에 닿았다는 뜻입니다.

판정의 순서를 그림으로 모으면 이렇습니다. 어느 물음에서든 「아니오」가 나오면 빗나감으로 끝납니다.

flowchart TD
    S["광선 하나와 삼각형 하나"] --> P{"광선이 평면과 나란한가"}
    P -->|예| M["빗나감"]
    P -->|아니오| T{"t 가 0 이상인가"}
    T -->|아니오| M
    T -->|예| B{"u, v, w 가 모두 0 이상인가"}
    B -->|아니오| M
    B -->|예| H["적중, t 와 u, v 를 돌려준다"]

위 순서는 평면을 먼저 구하고 그다음 u 와 v 를 구합니다. 가장 널리 쓰는 묄러-트럼보어 알고리즘은 평면 식을 따로 만들지 않습니다. o + t·d 와 A + u·(B − A) + v·(C − A) 가 같다고 놓습니다. 그리고 t, u, v 세 값을 연립방정식 하나로 한 번에 풉니다.

이 방식은 삼각형마다 법선을 미리 구해 저장해 둘 필요가 없습니다.

판정이 돌려준 u 와 v 는 색을 칠할 때 다시 쓰입니다. 꼭짓점마다 색이 붙어 있으면, 적중점의 색은 세 꼭짓점의 색을 w, u, v 비율로 섞어 구합니다. 이렇게 섞는 계산이 무게중심 보간입니다.

같은 방법으로 섞는 값에는 텍스처 좌표도 있습니다. 텍스처 좌표는 삼각형 위의 점이 표면에 입힐 그림의 어디를 가져다 쓰는지 적은 값입니다.

상자와의 교차

가속 구조는 맞을 리 없는 물체를 미리 걸러 내는 구조입니다. 물체를 상자로 감싸 둡니다. 광선이 빗나간 상자는 그 안을 보지 않습니다. 광선 하나가 상자를 여러 개 거쳐야 삼각형에 닿으므로 상자 판정도 그만큼 자주 돕니다.

이 상자는 대개 모서리가 x, y, z 축과 나란한 것을 씁니다. 이런 상자가 AABB(Axis-Aligned Bounding Box, 축 정렬 경계 상자)입니다.

AABB 는 꼭짓점 두 개만 알면 정해집니다. x, y, z 가 모두 가장 작은 꼭짓점 하나와 모두 가장 큰 꼭짓점 하나입니다. 아래 예시의 상자라면 (2, −1, −1) 과 (4, 1, 1) 입니다.

AABB 는 두꺼운 판 세 장이 겹친 공간으로 볼 수 있습니다. x 가 최솟값과 최댓값 사이인 판, y 가 그 사이인 판, z 가 그 사이인 판입니다. 두 평면 사이에 낀 이 판 모양 공간을 슬랩이라고 부릅니다.

슬랩 테스트는 슬랩을 축마다 하나씩 따지는 계산입니다. 축 하나에서는 광선이 슬랩에 들어가는 t 와 나오는 t 를 구합니다. 앞의 평면 계산을 슬랩의 두 면에 한 번씩 하면 됩니다.

세 축의 들어가는 t 가운데 가장 큰 값이 상자에 들어서는 때입니다. 세 슬랩 모두에 들어가 있어야 상자 안이기 때문입니다. 같은 이유로 나오는 t 가운데 가장 작은 값이 상자를 벗어나는 때입니다. 들어서는 때가 벗어나는 때보다 늦으면 광선은 상자를 비껴갑니다.

x 가 2~4, y 와 z 가 −1~1 인 상자에 출발점이 (0, 0, 0) 인 광선 두 줄기를 쏩니다. 두 광선 모두 방향의 z 값이 0 이라서 z 슬랩 안에 처음부터 끝까지 머뭅니다. 그래서 표에서는 z 를 뺍니다.

첫째 광선은 y 값이 0 인 채로 날아가니 y 슬랩을 벗어나는 일이 없습니다. 그래서 x 슬랩에 들어서는 t 2 가 곧 상자에 들어서는 때입니다.

둘째 광선은 t 가 1 일 때 이미 y 슬랩을 벗어납니다. 그런데 x 슬랩에는 t 가 2 일 때야 들어섭니다. 두 슬랩에 함께 머무는 때가 없으니 상자를 비껴갑니다.

가장 가까운 적중 고르기

장면에는 물체가 많아서 광선 하나가 여러 물체에 적중할 수 있습니다. 눈에 보이는 것은 그중 t 가 가장 작은 것입니다. 이 적중을 최근접 적중이라고 부릅니다.

그래서 판정은 t 의 상한을 들고 다닙니다. 상한은 처음에 끝없이 멀게 둡니다. 적중을 찾을 때마다 그 t 로 줄입니다. 그 뒤의 판정에서 t 가 상한보다 크면 적중이어도 버립니다.

상한은 가속 구조에서도 쓰입니다. 광선이 상자에 들어서는 t 가 상한보다 크면 그 상자 안의 어떤 적중도 이미 찾은 것보다 멉니다. 그 상자는 열어 볼 필요가 없습니다.

광선을 쏘는 목적이 다르면 멈추는 때도 다릅니다. 바닥의 한 점이 그늘인지 알려면 그 점에서 전등 쪽으로 광선을 쏩니다. 이 광선을 그림자 광선이라고 부릅니다.

그림자 광선은 가장 가까운 적중이 필요 없습니다. 중간에 무엇이든 하나 맞으면 그늘이므로 거기서 멈춥니다. 상한은 전등까지의 거리로 둡니다. 전등 너머에 있는 물체는 빛을 가리지 않기 때문입니다.

계산 오차와 자기 교차

컴퓨터는 소수를 부동소수점으로 적습니다. 담을 수 있는 자릿수가 정해져 있어서 계산마다 아주 작은 오차가 남습니다.

이 오차는 광선이 물체 표면에서 출발할 때 문제가 됩니다. 앞에서 본 그림자 광선이 그렇습니다. 출발점이 표면보다 아주 조금 안쪽으로 계산되면, 광선이 방금 떠난 그 면에 t 가 0 에 가까운 값으로 다시 적중합니다. 이것이 자기 교차입니다.

그림자 광선에서 자기 교차가 나면 빛을 받는 면이 자기 자신에 가려 그늘로 판정됩니다. 화면에는 밝아야 할 표면에 검은 점과 줄무늬가 흩뿌려집니다. 이 얼룩을 그림자 여드름이라고 부릅니다.

막는 법은 둘입니다. t 의 하한을 0 대신 아주 작은 양수로 두거나, 출발점을 법선 방향으로 조금 띄워 놓습니다. 어느 쪽이든 띄우는 양은 장면의 크기에 맞춰 정합니다. 너무 작으면 얼룩이 남습니다. 너무 크면 맞닿은 두 물체 사이의 그림자가 사라집니다.

복잡도

판정 한 번은 장면이 얼마나 크든 곱셈과 덧셈 몇십 번으로 끝납니다. 그래서 광선 하나와 물체 하나의 판정은 O(1) 입니다. O(1) 은 입력이 커져도 비용이 일정하다는 뜻입니다.

비용을 키우는 것은 횟수입니다. 장면에 삼각형이 n 개 있고 광선 하나를 그 전부와 판정하면 판정이 n 번 돕니다. 비용이 n 에 비례해 늘어나므로 O(n) 입니다.

화면이 가로 1920 점, 세로 1080 점이면 광선이 약 207만 개입니다. 삼각형이 100만 개라면 한 장에 약 2조 번을 판정해야 합니다. 반사와 그림자를 보려고 광선을 더 쏘면 그만큼 또 늘어납니다.

이 횟수를 줄이는 가속 구조의 대표는 BVH(Bounding Volume Hierarchy, 경계 볼륨 계층)입니다. 경계 볼륨은 상자처럼 물체를 감싸는 도형을 넓게 이르는 말입니다. BVH 는 큰 상자 안에 작은 상자를 담는 식으로 상자를 여러 층 쌓습니다. 삼각형은 맨 아래 층의 상자에 듭니다.

광선은 맨 위 상자부터 맞은 상자만 열어 그 안으로 내려갑니다. 빗나간 상자는 안을 통째로 건너뜁니다. 이렇게 상자를 따라 내려가는 과정이 광선 순회입니다. 그래서 상자 판정 수십 번과 삼각형 판정 몇 번으로 끝나는 때가 많습니다.

O(log n) 은 물체가 두 배가 될 때 비용이 한 단계씩만 늘어난다는 뜻입니다. 상자끼리 크게 겹치면 광선이 여러 갈래를 함께 내려가야 해서 다시 O(n) 에 가까워집니다.

쓰는 곳과 안 쓰는 곳

레이 트레이싱 말고도 「이 방향으로 가면 무엇이 있나」를 묻는 곳이면 이 판정이 돕니다. 게임에서 마우스로 가리킨 물체를 고르는 피킹이 그렇습니다. 총알이 무엇에 맞았는지 가리는 계산도 같습니다. 게임 엔진과 물리 엔진은 이런 물음을 레이캐스트라는 이름의 기능으로 내놓습니다.

화면을 그리는 계산 칩은 GPU(Graphics Processing Unit, 그래픽 처리 장치)입니다. 레이 트레이싱을 지원하는 GPU 는 대개 상자 판정과 삼각형 판정을 맡는 전용 회로를 갖고 있습니다. 구처럼 삼각형이 아닌 도형은 프로그래머가 판정 코드를 직접 써서 넘깁니다. 이 코드를 교차 셰이더라고 부릅니다.

실시간 게임이 화면을 그리는 기본 방식인 래스터화는 이 판정을 쓰지 않습니다. 래스터화는 방향이 반대입니다. 삼각형을 하나씩 화면에 비춰 그 삼각형이 덮는 점들을 찾습니다.

광선 교차 판정은 화면의 점에서 출발해 삼각형을 찾습니다. 그래서 그림자와 반사처럼 「이 점에서 저쪽을 보면 무엇이 있나」를 물어야 하는 효과에 강합니다. 화면은 래스터화로 그리고 그림자나 반사만 광선으로 보태는 방식도 흔히 씁니다.

관련 항목

광선 교차 판정이 속하는 상위 분류

레이 트레이싱 · 그래픽스 · 렌더링 · 계산 기하학 · 충돌 감지

광선 교차 판정의 상대 도형

삼각형 · 폴리곤 메시 · 평면 방정식 · 바운딩 스피어 · 경계 상자 · AABB · OBB

판정 계산에 쓰는 수학 도구

벡터 · 내적 · 외적 · 법선 · 판별식 · 무게중심 좌표 · 연립방정식 · 크라메르 공식

도형마다 이름 붙은 판정 알고리즘

묄러-트럼보어 알고리즘 · 슬랩 테스트 · 워터타이트 교차 판정 · 레이 마칭

판정 횟수를 줄이는 가속 구조

가속 구조 · BVH · k-d 트리 · 옥트리 · 균일 격자 · 광선 순회 · 표면적 휴리스틱

판정 결과를 받는 레이 트레이싱 셰이더

최근접 히트 · 교차 셰이더 · 최근접 적중 셰이더 · 임의 적중 셰이더 · 미스 셰이더 · 광선 생성 셰이더 · 셰이더 바인딩 테이블

광선 교차 판정을 쓰는 광선의 종류

광선 · 1차 광선 · 그림자 광선 · 반사 광선 · 굴절 광선

판정 결과로 계산하는 빛 효과

그림자 · 반사 · 굴절 · 전역 조명 · 패스 트레이싱 · 앰비언트 오클루전

적중점의 값을 구하는 보간과 셰이딩

무게중심 보간 · 셰이딩 · 텍스처 좌표 · 법선 보간

판정에서 계산 오차가 일으키는 문제

부동소수점 · 자기 교차 · 그림자 여드름 · 수치 안정성 · 엡실론

광선 교차 판정을 게임에서 부르는 기능

레이캐스트 · 피킹 · 히트스캔 · 물리 엔진 · 게임 엔진

광선 교차 판정과 맞세워지는 그리기 방식

래스터화 · 깊이 버퍼 · 깊이 테스트 · 하이브리드 렌더링

판정을 하드웨어로 돌리는 GPU 와 API

GPU · RT 코어 · Vulkan · Direct3D 12 · DXR