선형대수와 기하학 — 한 줄 한 줄 직접 구현

화면의 물체를 마우스로 클릭해서 고르는 피킹(picking), 총알이 벽에 맞았는지 판정하는 충돌(collision). 이 실용적인 기능들은 전부 세 가지 기하 교차 위에 서 있습니다. 이 페이지에서는 무게중심 좌표 점-삼각형 판정, 레이-평면 교차, 레이-구 교차(이차방정식)를 수식의 유도부터 코드 한 줄, 부동소수 엡실론 하나까지 파고듭니다. 겉보기엔 짧은 함수들이지만, 그 안에 선형대수(2×2 역행렬, 내적)와 해석기하(레이 방정식, 판별식)가 촘촘하게 들어 있습니다.

0. 레이(Ray) — 모든 피킹의 출발점

세 함수 중 둘이 레이(ray, 반직선)를 인자로 받습니다. 그래서 레이가 무엇인지부터 확실히 잡고 갑니다. 레이는 시작점(origin) 하나와 방향(dir) 하나로 정의되는, 한쪽으로만 무한히 뻗는 화살표입니다.

#pragma once
#include "Vec3.h"
#include <cmath>

struct Ray {
    Vec3 origin;   // 레이가 시작하는 점 (예: 카메라 위치)
    Vec3 dir;      // 레이가 나아가는 방향 (보통 정규화된 단위벡터)
};
// 레이 위의 점: P(t) = origin + t * dir   (t >= 0 인 앞쪽만 유효)

레이 방정식 P(t) = origin + t · dir을 그림으로

이 한 줄이 이 페이지 전체의 심장입니다. t는 "방향으로 얼마나 멀리 갔는가"를 나타내는 스칼라(실수 하나)입니다. 머릿속에 이렇게 그려 보세요. origin에 발을 딛고 서서 dir이 가리키는 쪽을 바라봅니다. t를 0에서부터 서서히 키우면, 그 점 P(t)가 origin에서 출발해 dir 방향으로 스르륵 미끄러져 나갑니다.

• t = 0 → P = origin (출발점, 카메라 바로 앞)
• t = 1 → P = origin + dir (dir이 단위벡터라면 정확히 1만큼 전진)
• t = 5 → 방향으로 5만큼 떨어진 점
• t < 0 → 레이의 뒤쪽. 카메라 등 뒤라서 화면에 안 보이므로 교차로 인정하지 않습니다.

그래서 모든 교차 함수의 목표는 결국 하나로 요약됩니다. "레이가 도형과 만나는 그 순간의 t 값을 구하는 것." t만 알면 hit = origin + dir * t로 부딪힌 좌표를 즉시 복원할 수 있고, 여러 물체 중 t가 가장 작은 것이 카메라에서 가장 가까워 실제로 클릭된 물체가 됩니다.

1. 점-삼각형 판정 — 무게중심 좌표(barycentric)

무엇을 만드나: 어떤 점 p가 삼각형 abc의 내부에 있는지 참/거짓으로 판정합니다.

왜 필요한가: 3D 모델은 결국 삼각형 덩어리입니다. 레이가 어떤 평면과 만나는 점을 구했더라도, 그 점이 실제 삼각형 조각 안인지 아니면 삼각형을 벗어난 허공인지를 가려야 진짜 피킹이 완성됩니다. 무게중심 좌표는 그 판정을 내적 몇 번으로 끝내는 표준 기법이고, 덤으로 텍스처 좌표·색·법선을 삼각형 안에서 부드럽게 보간(interpolation)하는 값까지 그대로 내어 줍니다.

1. 삼각형의 한 꼭짓점 a를 기준으로 두 변 벡터 v0 = c-a, v1 = b-a와 대상 벡터 v2 = p-a를 만든다.
2. 다섯 개의 내적 d00, d01, d11, d20, d21을 구한다 (2×2 연립방정식의 계수들).
3. 분모 denom = d00·d11 - d01·d01을 구한다 (2×2 행렬식). 0에 가까우면 퇴화 삼각형이므로 실패.
4. 무게중심 좌표 u, v를 크라메르 공식으로 푼다.
5. u ≥ 0, v ≥ 0, u+v ≤ 1이면 내부 (엡실론 여유 포함).

// 점-삼각형 (무게중심)
inline bool pointInTriangle(const Vec3& p, const Vec3& a, const Vec3& b, const Vec3& c) {
    Vec3 v0 = c - a, v1 = b - a, v2 = p - a;
    float d00 = dot(v0, v0), d01 = dot(v0, v1), d11 = dot(v1, v1),
          d20 = dot(v2, v0), d21 = dot(v2, v1);
    float denom = d00 * d11 - d01 * d01;
    if (std::fabs(denom) < 1e-8f) return false;   // 퇴화(선·점) 삼각형
    float inv = 1 / denom;
    float u = (d11 * d20 - d01 * d21) * inv,
          v = (d00 * d21 - d01 * d20) * inv;
    const float eps = 1e-5f;
    return (u >= -eps) && (v >= -eps) && (u + v <= 1 + eps);
}

시그니처 한 조각씩

bool pointInTriangle(const Vec3& p, const Vec3& a, const Vec3& b, const Vec3& c). 반환 타입 bool은 "내부냐 아니냐"라는 예/아니오 질문의 답이라 자연스럽습니다. 네 인자 모두 const Vec3&인 이유는 두 가지입니다. 참조(&)는 Vec3(12바이트) 값을 통째로 복사하지 않고 원본을 가리키게 해 복사 비용을 없애고, const는 "이 함수는 넘어온 점·꼭짓점을 절대 건드리지 않는다"는 약속입니다. 판정만 하고 원본을 바꾸지 않으므로 const가 정확한 의도 표현입니다. inline은 헤더에 정의를 두어 여러 .cpp에 include돼도 중복 정의 링크 오류가 나지 않게 합니다.

1단계: 기준점 하나로 좌표계를 세운다

Vec3 v0 = c-a, v1 = b-a, v2 = p-a; — 꼭짓점 a를 원점으로 삼고, 거기서 다른 점들을 향하는 화살표를 만드는 과정입니다. 기하학적으로 그려 보면, a에 압정을 꽂고 그 지점에서 b로 향하는 변 v1, c로 향하는 변 v0이라는 두 개의 기저(축)를 세운 것입니다. 그리고 v2는 같은 원점 a에서 우리가 판정하려는 점 p로 향하는 화살표입니다.

핵심 아이디어: 삼각형 내부의 어떤 점 p든, a를 기준으로 하면 p - a = u · v0 + v · v1, 즉 "두 변을 각각 u배, v배 섞으면 도달한다"고 쓸 수 있습니다. 이 u, v가 바로 무게중심 좌표입니다. 우리가 할 일은 이 u, v를 역으로 풀어내는 것뿐입니다.

2단계: 다섯 내적의 의미 — 연립방정식으로 만들기

풀어야 할 식은 v2 = u · v0 + v · v1인데, 이건 벡터(3성분) 방정식이라 미지수 2개(u,v)에 비해 식이 많아 보입니다. 표준 트릭은 양변에 v0과 v1을 각각 내적해서 스칼라 방정식 2개로 압축하는 것입니다. 내적은 벡터를 축에 사영(투영)한 길이라, 이렇게 하면 벡터 방정식이 깔끔한 2×2 연립방정식으로 바뀝니다.

• v2·v0 = u(v0·v0) + v(v1·v0) → d20 = u·d00 + v·d01
• v2·v1 = u(v0·v1) + v(v1·v1) → d21 = u·d01 + v·d11

그래서 코드의 다섯 내적 각각은 정확히 아래 계수·상수입니다.

3단계: 분모 denom = 2×2 행렬식, 그리고 역행렬

위 연립방정식을 행렬로 쓰면 [[d00, d01],[d01, d11]] · [u,v]ᵀ = [d20, d21]ᵀ 꼴입니다. 이 2×2 계수 행렬을 뒤집어(역행렬) 곱하면 u,v가 나옵니다. 2×2 역행렬 공식은 1/(ad−bc) · [[d, −b],[−c, a]]인데, 여기서 ad − bc가 바로 행렬식(determinant)이고, 우리 경우엔 denom = d00·d11 − d01·d01입니다.

기하학적 직관: 이 행렬식은 두 변 v0, v1이 만드는 평행사변형 넓이의 제곱과 같습니다(코시-슈바르츠). 두 변이 같은 방향으로 붙어버리면(삼각형이 찌그러져 선분/점이 되면) 넓이가 0 → denom = 0이 됩니다. 이걸 퇴화(degenerate) 삼각형이라 부릅니다. if (std::fabs(denom) < 1e-8f) return false;는 "면적이 사실상 없어서 내부라는 개념 자체가 성립하지 않고, 곧이어 1/denom이 무한대로 폭발할" 상황을 미리 막는 안전장치입니다.

4단계: 크라메르 공식으로 u, v 뽑기

inv = 1/denom을 한 번만 계산해 두고 두 번 곱합니다(나눗셈이 곱셈보다 느리므로 나눗셈 1회로 줄이는 작은 최적화). 역행렬을 상수 벡터 [d20,d21]에 곱한 결과가 다음 두 줄입니다.

• u = (d11·d20 − d01·d21) · inv
• v = (d00·d21 − d01·d20) · inv

구조를 보면 u는 첫 열을 상수로 바꾼 행렬식을, v는 둘째 열을 바꾼 행렬식을 전체 행렬식으로 나눈 크라메르 공식(Cramer's rule) 그대로입니다. 나오는 u, v는 각각 "변 v0(=a→c) 방향으로 얼마, 변 v1(=a→b) 방향으로 얼마"라는 비율입니다.

5단계: 판정 조건이 왜 곧 "삼각형 내부"인가

남은 세 번째 무게중심 좌표를 w = 1 − u − v라 하면, 점의 위치는 세 꼭짓점의 가중 평균 p = w·a + v·b + u·c로 표현됩니다(세 무게가 합 1). 세 무게가 전부 0 이상일 때에만 점이 삼각형이라는 "울타리" 안에 갇힙니다. 이걸 u,v로 옮기면 정확히 세 조건이 됩니다.

• u >= -eps — c 쪽 무게가 음수가 아님 (변 ab 바깥으로 안 나감)
• v >= -eps — b 쪽 무게가 음수가 아님 (변 ac 바깥으로 안 나감)
• u + v <= 1 + eps — 남은 무게 w = 1−u−v ≥ 0, 즉 변 bc 바깥으로 안 나감

세 조건은 각각 삼각형의 세 변이 그은 경계선 하나씩에 대응합니다. 그림으로 보면, u=0 선, v=0 선, u+v=1 선 이 세 직선이 만드는 삼각형 영역 안에 (u,v)가 들어오면 참입니다. eps = 1e-5f의 여유를 준 이유는, 점이 변 위에 정확히 걸릴 때 부동소수 오차로 u가 -0.0000001처럼 살짝 음수가 나와 엣지에 있는 점이 억울하게 탈락하는 것을 막기 위함입니다. 살짝 넉넉하게 잡아 경계를 포함시킵니다.

2. 레이-평면 교차 — t = n·(p0−origin) / (n·dir)

무엇을 만드나: 레이가 무한 평면(법선 n, 평면 위의 한 점 p0로 정의)과 만나는지, 만난다면 그 t를 tOut에 담아 돌려줍니다.

왜 필요한가: 바닥·벽 같은 평평한 면과의 충돌, 그리고 삼각형 피킹의 1단계가 바로 이 레이-평면 교차입니다. 삼각형은 결국 평면의 한 조각이므로, "먼저 평면과 어디서 만나는지 t를 구하고 → 그 교점을 무게중심 판정으로 삼각형 안인지 확인"하는 2단 구조가 표준입니다.

// 레이-평면: 법선 n, 평면 위의 점 p0
inline bool rayPlane(const Ray& ray, const Vec3& n, const Vec3& p0, float& tOut) {
    float denom = dot(n, ray.dir);
    if (std::fabs(denom) < 1e-6f) return false;         // 레이가 평면과 평행
    float t = dot(n, p0 - ray.origin) / denom;
    if (t < 0) return false;                            // 교점이 레이 뒤쪽
    tOut = t;
    return true;
}

시그니처: 왜 float& tOut인가

앞 세 인자는 pointInTriangle과 같은 이유로 const ...&(복사 없음 + 불변 약속)입니다. 마지막 float& tOut만 const가 없는 참조인데, 이건 출력 매개변수입니다. C++에는 "성공/실패(bool)와 결과값(t)을 동시에 반환"하는 문법이 마땅치 않아, bool은 반환값으로, 실제 t는 참조 인자에 써서 돌려주는 관용구를 씁니다. 호출 측은 float t; if (rayPlane(ray, n, p0, t)) { ...t 사용... }처럼 씁니다. false일 땐 tOut을 건드리지 않으므로, 반드시 true를 확인한 뒤에만 t를 읽어야 합니다.

수식 유도: 평면 방정식에 레이를 대입

수학적 의미: 법선 n과 평면 위 한 점 p0로 정의되는 평면 위의 점 P는 n·(P − p0) = 0을 만족합니다. "p0에서 P로 가는 화살표가 법선과 수직"이라는 뜻으로, 이것이 평면의 정의입니다. 여기에 레이 위의 점 P = origin + t·dir을 그대로 대입합니다.

• n·(origin + t·dir − p0) = 0
• n·(origin − p0) + t·(n·dir) = 0 (내적은 분배됨)
• t = −n·(origin − p0) / (n·dir) = n·(p0 − origin) / (n·dir)

코드 t = dot(n, p0 - ray.origin) / denom이 마지막 줄 그대로입니다. 부호를 예쁘게 하려고 −(origin−p0)를 (p0−origin)으로 바꿔 썼을 뿐 같은 식입니다.

분모 denom = n·dir의 기하학적 의미와 0 처리

기하학적 직관: 분모 n·dir은 레이 방향이 법선 쪽으로 얼마나 기울었는가입니다. 레이가 평면을 정면으로 뚫으면 이 값의 크기가 크고, 평면을 스치듯 나란히 진행하면 dir이 법선과 거의 수직이 되어 n·dir ≈ 0이 됩니다. 나란한(평행) 레이는 평면과 영원히 안 만나거나(평면 밖) 무한히 겹쳐(평면 위) 교점이 하나로 정해지지 않습니다. 그래서 if (std::fabs(denom) < 1e-6f) return false;로 평행에 가까운 경우를 먼저 걸러내야 바로 다음 줄 / denom이 0에 가까운 수로 나누며 t가 폭발하는 참사를 막습니다. 나눗셈을 하기 전에 분모를 검사하는 순서가 중요합니다.

통과한 뒤 if (t < 0) return false;는 앞서 본 레이 규칙 그대로입니다. 교점이 나오긴 했지만 t가 음수라면 그 점은 레이의 뒤쪽(카메라 등 뒤)이라 화면·전방 판정에서 제외합니다.

3. 레이-구 교차 — 이차방정식과 판별식

무엇을 만드나: 레이가 중심 center, 반지름 radius인 구와 만나는지, 만난다면 처음 부딪히는 표면의 t를 돌려줍니다.

왜 필요한가: 구는 물체를 감싸는 경계 볼륨(bounding sphere)으로 널리 쓰여, "일단 구에라도 맞았나?"를 싸게 물어보는 broad phase(3절 아래 성능 콜아웃)의 대표 도형입니다. 또 이 유도 방식(레이 방정식을 도형 방정식에 대입 → 이차방정식)은 레이-실린더, 레이-타원체 등으로 그대로 확장되는, 레이트레이싱의 원형(原型) 패턴입니다.

1. 레이 원점에서 구 중심으로 향하는 벡터 oc = origin − center를 만든다.
2. 이차방정식 a·t² + b·t + c = 0의 계수 a, b, c를 내적으로 구한다.
3. 판별식 disc = b² − 4ac를 계산. 음수면 실근이 없어 교차 안 함.
4. 두 근 t0(작은 근), t1(큰 근)을 구한다.
5. t0이 앞쪽이면 그것이 첫 표면. 아니면 t1(레이가 구 내부에서 시작한 경우).

// 레이-구 (이차방정식): 중심 center, 반지름 radius
inline bool raySphere(const Ray& ray, const Vec3& center, float radius, float& tOut) {
    Vec3 oc = ray.origin - center;
    float a = dot(ray.dir, ray.dir);
    float b = 2 * dot(oc, ray.dir);
    float c = dot(oc, oc) - radius * radius;
    float disc = b * b - 4 * a * c;
    if (disc < 0) return false;                         // 실근 없음 → 안 맞음
    float sq = std::sqrt(disc);
    float t0 = (-b - sq) / (2 * a);                     // 가까운(작은) 근
    float t1 = (-b + sq) / (2 * a);                     // 먼(큰) 근
    if (t0 > 1e-4f)      { tOut = t0; return true; }    // 앞쪽 표면
    else if (t1 > 1e-4f) { tOut = t1; return true; }    // 시작점이 구 내부
    return false;
}

수식 유도: 구 방정식에 레이를 대입

수학적 의미: 중심 center, 반지름 r인 구의 표면 점 P는 "중심까지 거리가 정확히 r", 즉 |P − center|² = r²을 만족합니다. 거리 대신 거리 제곱을 쓰는 이유는 제곱근을 피해 식을 깔끔한 다항식으로 만들기 위함입니다. 여기에 P = origin + t·dir을 대입하고 oc = origin − center로 묶으면,

• |oc + t·dir|² = r²
• (dir·dir)·t² + 2(oc·dir)·t + (oc·oc − r²) = 0 (제곱을 내적으로 전개)

이건 t에 대한 이차방정식 a·t² + b·t + c = 0입니다. 코드의 세 줄이 각 계수와 1:1로 대응합니다.

판별식 disc = b² − 4ac이 말해 주는 것

이차방정식의 판별식은 실근의 개수를 결정하고, 여기서는 그것이 레이가 구를 몇 번 통과하는가와 정확히 같습니다. 그림으로 보면 레이가 구를 관통할 때 들어가는 점·나오는 점 두 곳을 찍는 것이 자연스럽죠.

• disc < 0 → 실근 없음 → 레이가 구를 완전히 빗나감. 코드에서 즉시 return false.
• disc = 0 → 중근 하나 → 레이가 구를 스치듯 접함(접선).
• disc > 0 → 서로 다른 두 근 → 레이가 구를 뚫고 지나감(입구·출구 두 점).

if (disc < 0) return false;로 못 맞은 경우를 먼저 쳐내는 이유는 두 가지입니다. 불필요한 std::sqrt 호출(비교적 비쌈)을 아끼고, 무엇보다 음수의 제곱근(NaN)이 나오는 것을 막습니다.

두 근 t0, t1의 기하학적 의미

근의 공식 t = (−b ± √disc) / (2a)에서 a > 0(길이 제곱이라 항상 양수)이므로, −를 쓴 t0이 항상 t1보다 작습니다. 레이 방향으로 보면 t0이 먼저(가까이) 만나는 점, t1이 나중(멀리) 만나는 점입니다. 보통 우리가 원하는 건 눈에 보이는 앞면이므로 작은 근 t0을 우선합니다.

마지막 분기가 이 페이지에서 가장 미묘한 부분입니다.

• t0 > 1e-4f → t0이 레이 앞쪽에 있음 → 구의 앞면 표면. 이걸 씁니다.
• 아니고 t1 > 1e-4f → t0은 뒤(음수)인데 t1은 앞 → 레이 시작점이 구 안에 있어 입구는 등 뒤, 나가는 출구만 앞에 있는 상황. 그 출구 t1을 씁니다.
• 둘 다 앞쪽이 아니면 → 구 전체가 레이 뒤쪽 → false.

문턱값을 0이 아니라 1e-4f(아주 작은 양수)로 둔 이유는 표면 자기 교차(self-intersection) 방지입니다. 표면에서 새 레이를 쏘는 반사·그림자 계산에서, 부동소수 오차로 시작점이 표면 바로 안쪽에 걸리면 t가 거의 0인 "자기 자신"을 맞았다고 착각합니다. 살짝 앞선 지점부터 유효로 쳐서 이 얼룩(acne)을 막습니다.

4. 피킹에 실제로 써 보기

세 함수를 만들었으니 가장 흔한 쓰임인 구 하나 피킹을 봅니다. 마우스로 만든 레이 pickRay가 씬의 구를 맞혔는지 확인하고, 맞은 월드 좌표까지 복원합니다.

Ray  pickRay = /* 마우스 클릭에서 만든 레이 (origin, dir) */;
Vec3 spherePos { 0, 1, 0 };
float t;

if (raySphere(pickRay, spherePos, 0.5f, t)) {
    Vec3 hit = pickRay.origin + pickRay.dir * t;   // P(t) 로 부딪힌 점 복원
    // hit 좌표에 마커를 찍거나, 이 물체를 "선택됨"으로 표시
}

핵심은 마지막 줄입니다. 교차 함수는 거리 t 하나만 돌려주고, 그걸 레이 방정식 hit = origin + dir · t에 다시 넣어 실제 3D 좌표를 얻습니다. 0절에서 강조한 P(t)가 여기서 되살아납니다. 여러 물체를 훑을 때는 각 물체의 t를 비교해 가장 작은 t를 가진 물체가 진짜 선택된 것입니다(앞에 있는 것이 뒤를 가리므로).

int   picked = -1;
float best = 1e30f;                 // 아주 큰 값으로 시작
for (int i = 0; i < count; ++i) {
    float t;
    if (raySphere(pickRay, spheres[i].pos, spheres[i].r, t) && t < best) {
        best = t;                  // 더 가까운 후보 갱신
        picked = i;
    }
}
// picked != -1 이면 spheres[picked] 가 실제로 클릭된 물체

5. 성능: broad phase → narrow phase 2단 구조

구체적으로 이 페이지 함수로 매핑하면, raySphere가 전형적인 broad phase입니다. 구 교차는 내적 몇 번이라 매우 싸서, 수천 개 물체를 순식간에 훑어 "맞을 가능성 있는" 후보만 남깁니다. 그 다음, 남은 후보 물체의 실제 메시에 대해 rayPlane + pointInTriangle 조합으로 삼각형 하나하나를 검사하는 것이 narrow phase입니다. 대부분의 물체가 1단계에서 걸러지므로 비싼 삼각형 검사는 정말 필요한 곳에만 들어갑니다.

더 큰 씬에서는 broad phase 자체를 공간 분할 자료구조(BVH, 옥트리, 균일 그리드)로 가속해, 후보 목록을 만드는 비용마저 O(물체 수)에서 O(log) 수준으로 낮춥니다. 하지만 그 바닥에 깔린 원리는 언제나 이 페이지에서 만든 레이-구·레이-삼각형 교차입니다.

6. 실무: DirectXMath / DirectXCollision

지금까지는 원리를 손으로 확인하려고 Vec3와 dot으로 직접 짰습니다. 실제 프로젝트에서는 Windows SDK에 포함된 DirectXMath(SIMD 가속)와 그 위의 DirectXCollision.h (검증된 충돌 헬퍼)를 쓰는 것이 표준입니다. 우리가 유도한 수식이 그 안에서 그대로 돌아가고 있음을 아는 것이 이 페이지의 진짜 목적입니다.

#include <DirectXMath.h>
#include <DirectXCollision.h>
using namespace DirectX;

XMVECTOR O = XMLoadFloat3(&rayOriginF3);   // origin 로드
XMVECTOR D = XMLoadFloat3(&rayDirF3);      // dir 로드 (정규화된 것)

BoundingSphere sphere({0,1,0}, 0.5f);      // center, radius
float dist = 0.0f;
if (sphere.Intersects(O, D, dist)) {       // raySphere 와 동일한 역할
    XMVECTOR hit = XMVectorMultiplyAdd(D, XMVectorReplicate(dist), O); // O + D*dist
    // dist 가 우리 t, hit 가 부딪힌 좌표
}

sphere.Intersects(O, D, dist)는 우리가 3절에서 손으로 유도한 이차방정식·판별식·두 근 선택 로직을 SIMD로 최적화해 캡슐화한 것입니다. dist가 우리의 t이고, O + D*dist로 교점을 복원하는 것도 P(t)=origin+t·dir 그대로입니다. 이제 이 함수가 내부에서 무엇을 하는지 정확히 알기 때문에, 결과가 이상할 때(자기 교차, 카메라가 물체 내부 등) 어디를 의심할지 바로 감이 옵니다.