무게중심 보간

무게중심 보간은 삼각형의 세 꼭짓점 값을 섞어 안쪽 한 점의 값을 만들어 냅니다. 점이 어느 꼭짓점에 가까울수록 그 꼭짓점의 값이 많이 섞입니다. 그래픽 카드는 삼각형을 칠할 때 화면의 칸마다 색과 좌표를 이렇게 채웁니다. 수치해석에서는 여러 점을 모두 지나는 곡선을 구하는 한 방식을 같은 이름으로 부릅니다.

상세

이 절은 무게중심 보간이 무엇을 받아 무엇을 내놓는지, 섞는 몫을 어떻게 재는지를 다룹니다. 꼭짓점이 (0, 0) · (4, 0) · (0, 4) 인 삼각형 하나를 끝까지 계산해 보며 확인합니다.

넣는 것은 세 가지입니다. 삼각형 꼭짓점 셋의 위치, 꼭짓점마다 붙은 값, 값을 구하려는 점의 위치입니다. 나오는 것은 그 점의 값 하나입니다. 값이 여럿이면 같은 몫으로 하나씩 따로 섞습니다.

꼭짓점에만 값이 있는 삼각형

보간은 값을 띄엄띄엄만 알 때 그 사이 값을 만들어 내는 계산입니다. 무게중심 보간은 그 사이가 선분이 아니라 삼각형 안쪽일 때 씁니다.

3D 모델의 겉면은 삼각형을 이어 붙여 만듭니다. 꼭짓점에는 위치 말고도 여러 값이 붙습니다. 색이 가장 쉬운 예입니다.

법선도 꼭짓점에 붙는 값입니다. 표면이 어느 쪽을 향하는지 가리키는 화살표로, 빛이 얼마나 비치는지 계산할 때 씁니다. 방향만 뜻하므로 길이는 1 로 맞춰 둡니다.

텍스처 좌표도 꼭짓점에 붙습니다. 표면에 그림을 붙일 때 그림의 어느 점이 이 꼭짓점에 오는지 적은 값입니다.

문제는 화면입니다. 삼각형 하나가 화면에서 칸 수백 개를 덮어도 값은 꼭짓점 세 곳에만 있습니다. 안쪽 칸의 값은 누군가 만들어 내야 합니다.

가장 쉬운 방법은 삼각형 전체를 한 꼭짓점의 값으로 칠하는 것입니다. 이것을 플랫 셰이딩이라고 합니다. 둥근 공도 삼각형마다 한 색이라 깎은 보석처럼 각져 보입니다. 무게중심 보간은 안쪽 칸마다 세 값을 섞어 색이 삼각형을 가로질러 고르게 바뀌게 합니다.

넓이로 재는 세 몫

섞는 비율을 정하려면 점이 꼭짓점마다 얼마나 가까운지를 재야 합니다. 이 비율은 넓이로 잽니다.

꼭짓점이 A · B · C 인 삼각형 안에 점 P 가 있으면 P 와 꼭짓점을 이어 작은 삼각형 셋으로 나눌 수 있습니다. 꼭짓점의 맞은편 작은 삼각형이란 그 꼭짓점을 끼지 않은 작은 삼각형입니다. A 의 맞은편은 P·B·C 입니다. A 의 몫은 P·B·C 의 넓이를 전체 넓이로 나눈 값입니다.

B 의 맞은편은 A·P·C, C 의 맞은편은 A·B·P 입니다. B 와 C 의 몫도 같은 식으로 맞은편 작은 삼각형의 넓이에서 얻습니다.

P 가 A 에 다가가면 맞은편 삼각형 P·B·C 가 커집니다. 가까운 꼭짓점일수록 몫이 큰 까닭입니다. P 가 A 에 닿으면 P·B·C 가 전체와 같아져 A 의 몫은 1, 나머지는 0 입니다. P 가 B 와 C 를 잇는 변 위에 있으면 P·B·C 의 넓이가 0 이라 A 의 몫도 0 입니다.

작은 삼각형 셋을 합치면 전체 삼각형이 됩니다. 세 몫을 더하면 늘 1 인 까닭입니다.

이렇게 얻은 세 몫 (a, b, c) 을 P 의 무게중심 좌표라고 부릅니다. 꼭짓점 셋에 a · b · c 만큼의 무게를 올려놓으면 그 무게들이 균형을 이루는 점이 P 입니다. 이름이 여기서 왔습니다. 삼각형의 무게중심, 곧 꼭짓점과 맞은편 변의 가운데를 이은 선 셋이 만나는 점에서는 세 몫이 모두 3분의 1 입니다.

넓이를 구하는 식

평면 위 삼각형의 넓이는 꼭짓점 좌표만으로 구합니다. 두 변을 방향과 길이를 가진 화살표, 곧 벡터로 봅니다. 꼭짓점 p 에서 q 로 가는 변과 p 에서 r 로 가는 변입니다.

외적은 두 벡터가 만드는 평행사변형의 넓이를 주는 연산입니다. 삼각형은 이 평행사변형을 대각선으로 반 자른 모양입니다. 두 변 벡터의 외적이 삼각형 넓이의 두 배인 까닭입니다.

area2(p, q, r) = (q.x - p.x) * (r.y - p.y)
               - (q.y - p.y) * (r.x - p.x)

이 값은 p → q → r 이 시계 반대 방향으로 돌면 양수, 시계 방향이면 음수입니다. 몫을 구할 때는 나눗셈 하나로 두 배가 지워지므로 두 배인 채로 써도 됩니다.

예제 삼각형에 대 봅니다. A = (0, 0), B = (4, 0), C = (0, 4) 이고 P = (1, 1) 입니다. 각 몫은 해당 꼭짓점을 P 로 바꿔 넣은 넓이를 전체 넓이로 나눈 값입니다.

area2(A, B, C)   // 16
area2(P, B, C)   // 8  → a = 0.5
area2(A, P, C)   // 4  → b = 0.25
area2(A, B, P)   // 4  → c = 0.25

세 몫을 더하면 1 입니다. P 는 A 에 가장 가까우므로 A 의 몫이 가장 큽니다.

몫으로 값을 섞는 식

몫을 얻으면 섞기는 곱셈 셋과 덧셈 둘입니다. 꼭짓점 값을 fA · fB · fC 로 두면 P 의 값은 a·fA + b·fB + c·fC 입니다.

예제 삼각형의 꼭짓점에 밝기 10 · 20 · 30 이 붙어 있다고 칩니다. 앞에서 구한 몫을 넣습니다.

f = 0.5*10 + 0.25*20 + 0.25*30   // 17.5

색처럼 성분이 여럿인 값은 성분마다 같은 몫으로 섞습니다. 빨강 · 초록 · 파랑을 따로 계산하는 식입니다. 몫은 위치만으로 정해지므로 점 하나에 한 번만 구하면 됩니다.

이 식은 선형 보간을 두 점에서 세 점으로 늘린 것입니다. 선분 위에서 두 끝값을 거리 비로 섞듯이 삼각형 안에서는 세 꼭짓점 값을 넓이 비로 섞습니다.

부호로 가르는 안과 밖

넓이 식은 부호를 가집니다. P 가 삼각형 바깥으로 나가면 몫 가운데 하나 이상이 음수가 됩니다.

P = (3, 3) 을 넣으면 b 와 c 는 0.75, a 는 −0.5 입니다. a 가 음수라는 것은 P 가 A 의 맞은편 변, 곧 B 와 C 를 잇는 변 너머에 있다는 뜻입니다. 세 몫이 모두 0 이상인지만 보면 점이 삼각형 안에 있는지 가를 수 있습니다.

몫이 음수인 채로 섞으면 꼭짓점 값의 범위를 벗어난 값이 나옵니다. 아는 값의 바깥을 짚어 내는 이런 계산은 외삽이라고 따로 부릅니다. 무게중심 보간은 몫이 모두 0 이상인 안쪽에서만 씁니다.

그래픽 카드가 삼각형을 칠하는 순서

GPU(Graphics Processing Unit, 그래픽 처리 장치)는 삼각형을 그릴 때 이 계산을 칸마다 되풀이합니다. 이 소절은 그 흐름을 그림으로 보이고, 그림에 나오는 단계 이름을 먼저 풉니다.

셰이더는 GPU 에서 도는 작은 프로그램입니다. 그리는 과정의 몇몇 단계를 개발자가 직접 짠 코드로 채우게 해 줍니다.

정점 셰이더는 꼭짓점마다 한 번 도는 셰이더입니다. 정점은 꼭짓점의 그래픽스 용어입니다. 꼭짓점의 화면 위치와 색 같은 값을 내보냅니다.

래스터화는 삼각형을 화면의 칸으로 쪼개는 단계입니다. 삼각형이 어느 칸을 덮는지 고르는 일입니다.

프래그먼트는 래스터화가 쪼갠 칸 하나입니다. 칸마다 한 번 도는 셰이더가 프래그먼트 셰이더입니다. 그 칸의 최종 색을 정합니다.

flowchart TD
    V["정점 셰이더가 꼭짓점마다 색 · 좌표를 내보낸다"] --> R["래스터화가 삼각형이 덮는 칸을 고른다"]
    R --> B["칸마다 세 몫을 구한다"]
    B --> I["세 몫으로 꼭짓점 값을 섞는다"]
    I --> F["프래그먼트 셰이더가 섞인 값을 받는다"]

무게중심 보간은 래스터화 바로 뒤에서 돕니다. 칸 한가운데의 세 몫을 구해 꼭짓점 값을 섞습니다. 프래그먼트 셰이더는 꼭짓점 값이 아니라 이렇게 섞인 값을 받습니다.

몫을 칸마다 처음부터 구하지는 않습니다. 몫은 화면에서 옆 칸으로 한 칸 옮길 때마다 늘 같은 양만큼 늘거나 줍니다. 수학으로 말하면 화면 좌표 x · y 의 일차식입니다. 첫 칸의 몫을 구해 두면 다음 칸은 덧셈 한 번으로 얻습니다.

원근이 몫을 틀어 놓는 문제

화면에서 잰 넓이 비는 화면과 나란히 놓인 삼각형에서만 맞습니다. 바닥처럼 비스듬히 누운 삼각형에서는 어긋납니다.

원근 투영은 멀리 있는 것을 작게 그리는 투영입니다. 바닥에 고른 간격으로 그은 줄은 화면에서 가까운 쪽 간격이 넓고 먼 쪽 간격이 좁게 보입니다. 화면 넓이 비로 섞으면 이 좁아짐을 모릅니다.

이 탓에 바닥 무늬가 먼 쪽에서 늘어집니다. 삼각형 이음매에서는 꺾여 보입니다.

바로잡으려면 꼭짓점마다 카메라에서 얼마나 먼지를 알아야 합니다. 원근 투영을 거친 꼭짓점은 이 값을 w 라는 숫자로 하나씩 가집니다. w 는 깊이에 비례해서 카메라에서 멀수록 커집니다.

w 는 클립 좌표의 넷째 성분입니다. 클립 좌표는 원근 투영이 x · y · z 에 w 를 하나 더 붙여 적은 네 성분 좌표입니다. 화면 좌표는 x 와 y 를 w 로 나눠 얻습니다. 먼 것이 작게 그려지는 것이 이 나눗셈 때문입니다.

보정은 값과 1 을 각각 w 로 나눠 섞은 뒤, 앞의 것을 뒤의 것으로 나눕니다.

f = (a·fA/wA + b·fB/wB + c·fC/wC)
  / (a/wA + b/wB + c/wC)

분자는 값을 w 로 나눠 섞은 것입니다. 분모는 1 을 w 로 나눠 섞은 것입니다. 화면 좌표가 w 로 나눈 값이듯, 같은 w 로 나눈 값은 화면에서 고르게 변합니다. 화면 넓이 비로 섞어도 틀어지지 않는 까닭입니다.

마지막에 분자를 분모로 나누면 w 로 나눈 효과가 풀립니다. 3D 공간에서 고르게 섞은 값이 돌아옵니다. 이 계산이 원근 보정 보간입니다.

예제에서 꼭짓점 C 만 두 배 멀다고 칩니다. wA 와 wB 는 1, wC 는 2 입니다. 밝기는 앞과 같은 10 · 20 · 30 입니다.

num = 5 + 5 + 7.5/2        // 13.75
den = 0.5 + 0.25 + 0.25/2  // 0.875
f   = num / den            // 15.71

보정한 C 의 몫은 분모에 들어간 C 의 항을 분모 전체로 나눈 값입니다.

c' = (0.25/2) / 0.875   // 약 0.14

C 의 몫이 0.25 에서 약 0.14 로 줄었습니다. 값도 17.5 에서 15.71 로 내려갔습니다.

몫이 주는 까닭은 가까운 쪽이 화면에서 부풀려 그려지기 때문입니다. 화면에서 C 쪽으로 4분의 1 들어간 점도 3D 에서는 그만큼 C 에 다가가 있지 않습니다. 3D 에서 C 에 덜 다가가 있으니 C 의 몫이 줄어듭니다.

화면에는 칸마다 색과 함께 깊이 값도 적어 둡니다. 물체가 겹치면 칸마다 깊이를 견줘 앞에 있는 것만 남기기 때문입니다.

이 깊이 값은 원근 보정을 거치지 않습니다. 이미 w 로 나눈 값이라 화면에서 고르게 변합니다. 화면 넓이 비로 곧장 섞습니다.

셰이더 언어는 변수마다 섞는 방식을 고르게 합니다. 원근 보정 보간, 화면 넓이 비로 섞기, 섞지 않고 한 꼭짓점 값 쓰기 셋이 흔한 선택지입니다. 변수 선언 앞에 붙이는 이 표시를 보간 한정자라고 합니다.

광선 추적에서의 쓰임

광선 추적은 눈에서 광선을 쏘아 무엇에 맞는지 따라가며 그리는 방법입니다. 광선이 삼각형에 맞았는지 가리는 광선 교차 판정은 맞은 점의 무게중심 좌표를 함께 돌려줍니다.

그 몫으로 맞은 점의 색 · 법선 · 텍스처 좌표를 섞습니다. 식은 앞의 a·fA + b·fB + c·fC 와 같습니다.

이때는 원근 보정이 필요 없습니다. 몫을 화면이 아니라 3D 공간의 삼각형 위에서 구했기 때문입니다.

계산량

점 하나의 비용은 삼각형 크기와 무관합니다. 넓이 셋을 구해 나누면 몫이 나옵니다. 값 하나를 섞는 데는 곱셈 셋과 덧셈 둘이 듭니다.

아래 표의 O(1) · O(k) 는 빅오 표기법입니다. 입력이 커질 때 비용이 어떤 꼴로 늘어나는지 나타냅니다. O(1) 은 입력과 무관하게 일정하다는 뜻입니다. O(k) 는 k 에 비례한다는 뜻입니다.

칸이 많은 큰 삼각형도 칸 하나의 비용은 같습니다. 전체 비용은 덮는 칸 수에 비례합니다.

한결같은 기울기의 한계

무게중심 보간은 삼각형 안에서 값을 한결같은 기울기로만 바꿉니다. 꼭짓점 값을 높이로 세워 보면 이 말이 그림으로 보입니다.

삼각형을 바닥에 눕히고 꼭짓점마다 값만큼 막대를 세웁니다. 막대 끝 세 점은 평평한 판 하나를 정합니다. 무게중심 보간으로 얻는 안쪽 값은 그 판의 높이입니다. 판은 꼭짓점보다 높이 솟지 않으므로 삼각형 안쪽에 꼭짓점보다 밝은 점이 생길 수 없습니다.

이 성질은 빛을 계산할 때 드러납니다. 꼭짓점에서 밝기를 계산해 두고 안쪽은 섞기만 하는 방식을 구로 셰이딩이라고 합니다. 반짝이는 하이라이트가 삼각형 한가운데에만 떨어지는 경우를 봅니다. 꼭짓점 어디에도 안 걸렸으니 세 꼭짓점의 밝기는 모두 어둡게 나옵니다. 그 셋을 섞은 결과에도 하이라이트는 없습니다.

그래서 흔히 밝기 대신 법선을 섞습니다. 밝기는 칸마다 새로 계산합니다. 이 방식이 퐁 셰이딩입니다. 섞은 법선은 길이가 1 보다 짧아지므로 칸마다 길이를 1 로 다시 맞춥니다.

이음매도 문제가 됩니다. 이웃한 두 삼각형은 공유하는 변에서 값이 같습니다. 그런데 값이 변하는 기울기는 삼각형마다 달라서 변을 넘을 때 꺾입니다. 밝기가 고르게 변하는 면에서 이 꺾임이 줄무늬처럼 눈에 띄기도 합니다.

다른 보간과 견주기

몇 점을 섞느냐와 어떤 모양 위에서 섞느냐로 갈립니다.

격자에 값이 고르게 놓인 이미지나 텍스처는 네모 칸이라 쌍선형 보간을 씁니다. 점이 아무렇게나 흩어진 곳은 먼저 점들을 삼각형으로 이어 놓고 무게중심 보간을 씁니다.

같은 생각은 차원을 올려도 이어집니다. 3차원에서는 꼭짓점 넷인 사면체를 쓰고 몫도 넷이 됩니다. 넓이 대신 부피로 잽니다.

같은 이름의 다른 뜻

수치해석에서 말하는 무게중심 보간은 삼각형과 무관합니다. 직선 위의 점 n 개를 모두 지나는 다항식을 구하는 다항식 보간을 빠르게 계산하는 한 방식입니다.

라그랑주 보간은 다항식 보간의 기본 꼴입니다. 점마다 그 점에서만 1 이고 나머지 점에서는 0 인 다항식을 만들어, 점의 값을 곱해 더합니다. 이대로 계산하면 값 하나를 구할 때마다 곱셈이 n² 번 정도 듭니다.

무게중심 형식은 점의 위치에만 달린 수 n 개를 한 번 구해 둡니다. 값을 구할 위치가 정해지면 이 수로 점마다 몫을 만듭니다. 그 뒤로는 값 하나에 n 번 정도의 계산이면 됩니다.

결과는 「몫을 곱해 더하고 몫의 합으로 나눈」 꼴입니다. 그래픽스의 a·fA + b·fB + c·fC 도 몫의 합으로 나눈 꼴로 볼 수 있습니다. 세 몫의 합이 1 이라 나눗셈이 보이지 않을 뿐입니다. 꼴이 같아 같은 이름이 붙었습니다. 다만 수치해석 쪽은 그래픽스와 달리 몫이 음수가 될 수 있습니다.

관련 항목

무게중심 보간이 속하는 상위 분류

보간 · 그래픽스 · 렌더링 · 수치해석

무게중심 보간을 이루는 수학 도구

무게중심 좌표 · 외적 · 벡터 · 볼록 결합 · 아핀 결합 · 에지 함수

무게중심 보간이 거치는 그리기 단계

그래픽스 파이프라인 · 정점 셰이더 · 래스터화 · 프래그먼트 · 프래그먼트 셰이더 · 셰이더 · GPU

무게중심 보간으로 섞는 정점 속성

정점 속성 · 정점 · 정점 색 · 법선 · 텍스처 좌표 · 깊이값 · 배리잉 · 메시

원근 아래에서 몫을 바로잡는 보정

원근 보정 보간 · 원근 투영 · 클립 좌표 · 동차 좌표 · 보간 한정자 · 아핀 텍스처 매핑

무게중심 보간과 맞세워지는 다른 보간

선형 보간 · 쌍선형 보간 · 최근접 이웃 보간 · 구면 선형 보간 · 외삽

무게중심 보간을 쓰는 셰이딩과 광선 계산

플랫 셰이딩 · 구로 셰이딩 · 퐁 셰이딩 · 광선 추적 · 광선 교차 판정 · 묄러-트럼보어 알고리즘

같은 이름을 쓰는 다항식 보간

다항식 보간 · 라그랑주 보간 · 뉴턴 보간 · 룽게 현상 · 체비쇼프 노드 · 빅오 표기법