서비스
///
교육 철학
코칭 / 과외 / 멘토링
B2B 서비스(광고)
Unity, Unreal 외주 개발
개발 커뮤니티
프로그래밍 기초
게임 엔진 & 그래픽스
게임 수학 & 알고리즘
시스템 & 네트워크
Youtube
Archive
///
📐

기하학의 기본 요소(Geometric Primitives)

삼각형 인간, 삼각형 인간.
삼각형 인간은 입자 인간을 싫어해.
둘이 싸우면 삼각형이 이기지.
삼각형 인간.
— They Might Be Giants, 「Particle Man」(1990)
이 장에서는 기하학적 기본 도형을 일반적인 관점에서 살펴본 다음, 개별 도형을 구체적으로 알아봅니다.
•
9.1절에서는 기하학적 기본 도형을 표현할 때 알아야 할 일반적인 원리를 설명합니다.
•
9.2~9.7절에서는 중요한 기본 도형 여러 가지를 다룹니다. 각 도형의 표현 방법과 전통적으로 알려진 성질 및 연산을 살펴보고, 그 과정에서 C++ 코드도 몇 가지 제시합니다.

9.1 표현 기법 (Representation Techniques)

먼저 기하학적 모양을 기술하는 주요 전략을 간단히 살펴보겠습니다. 하나의 기본 도형에 이 기법 중 하나 이상을 적용할 수 있으며, 어떤 기법이 유용한지는 상황에 따라 달라집니다.
음함수 형식(implicit form) 으로 물체를 기술하려면, 도형에 속하는 모든 점에서는 참이고 나머지 모든 점에서는 거짓인 불리언 함수 f(x,y,z)f(x,y,z)를 정의하면 됩니다. 예를 들어 다음 방정식은 원점을 중심으로 하는 단위 구의 표면 위에 있는 모든 점에서 참입니다.
단위 구의 음함수 표현
x2+y2+z2=1x^2+y^2+z^2=1
이미 알고 있을 법한 대표적인 예는 원뿔곡선입니다. 원뿔곡선은 원뿔과 평면의 교차로 만들어지는 2차원 도형입니다. 원, 타원, 포물선, 쌍곡선이 여기에 속하며, 모두 표준적인 음함수 형식 Ax2+Bxy+Cy2+D=0Ax^2+Bxy+Cy^2+D=0으로 기술할 수 있습니다.
메타볼(metaballs) [7]은 액체나 유기적인 모양을 표현하는 음함수 기법입니다. 부피는 경계가 흐릿한 여러 개의 ‘공’으로 정의합니다. 각각의 공은 중심으로부터의 거리에 따라 3차원 스칼라 밀도 함수를 정의합니다. 거리가 0일 때 밀도가 가장 높고, 거리가 커질수록 값은 낮아집니다.
공간의 임의의 점에서 각 공이 만드는 밀도를 모두 더하면 전체 밀도 함수를 정의할 수 있습니다. 메타볼의 핵심은 밀도가 0이 아닌 어떤 임계값을 넘는 영역을 액체나 유기체의 부피로 삼는 데 있습니다. 다시 말해, 공 하나만 있을 때 실제 부피의 바깥으로도 뻗어나가는 ‘흐릿한’ 영역이 각 공의 주변에 있습니다.
공 두 개 이상이 가까워지면 이 흐릿한 영역들이 서로를 보강합니다. 그 결과 공 사이에 매끄러운 고체 부피의 ‘연결부’가 나타납니다. 각 공이 따로 있었다면 그곳에는 고체가 없었을 것입니다. 마칭 큐브(marching cubes) 알고리즘 [43]은 임의의 음함수 표현을 다각형 메시 같은 표면 표현으로 바꾸는 대표적인 기법입니다.
모양을 기술하는 또 다른 일반적인 전략은 매개변수 형식(parametric form) 입니다. 여기서도 기본 도형을 함수로 정의합니다. 다만 이번에는 공간 좌표가 함수의 입력이 아니라 출력입니다. 간단한 2차원 예부터 시작하겠습니다. tt에 관한 두 함수를 다음과 같이 정의합니다.
단위 원의 매개변수 표현
x(t)=cos⁡2πt,y(t)=sin⁡2πt.x(t)=\cos 2\pi t,\qquad y(t)=\sin 2\pi t.
인수 tt를 매개변수(parameter) 라고 하며, 이는 사용하는 좌표계와 독립적입니다. tt가 0에서 1까지 변하면 점 (x(t),y(t))(x(t),y(t))가 우리가 기술하는 모양의 윤곽선을 따라 움직입니다. 이 예에서는 원점을 중심으로 하는 단위 원을 그립니다(그림 9.1).
그림 9.1
그림 9.1. 매개변수로 표현한 원.
매개변수를 [0,1][0,1] 범위로 정규화하면 편리할 때가 많지만, tt의 범위는 원하는 대로 정해도 됩니다. 자주 쓰는 또 다른 범위는 [0,l][0,l]이며, 여기서 ll은 기본 도형의 길이를 나타내는 어떤 측정값입니다.
함수가 매개변수 하나로 표현되면 일변수(univariate) 함수라고 합니다. 일변수 함수는 1차원 모양, 즉 곡선을 따라갑니다. 매개변수 곡선은 13장에서 더 자세히 설명합니다. 매개변수를 여러 개 사용할 수도 있습니다. 이변수(bivariate) 함수는 두 매개변수를 받으며, 보통 변수 이름으로 ss와 tt를 씁니다. 이변수 함수는 선 대신 표면을 그립니다.
마지막 표현 방법은 더 좋은 이름이 떠오르지 않아 직접적인 형식(straightforward forms) 이라고 부르기로 했습니다. 가장 중요하고 눈에 띄는 정보를 직접 담는, 도형마다 따로 마련한 방법들을 통틀어 이르는 말입니다. 예를 들어 선분은 양 끝점을 제시하면 됩니다. 구는 중심과 반지름을 알려주는 것이 가장 간단한 설명입니다. 사람이 직접 다루기에는 이런 형식이 가장 쉽습니다.
표현 방법과 관계없이, 각 기하학적 기본 도형에는 고유한 자유도(degrees of freedom) 가 있습니다. 이는 해당 대상을 모호함 없이 기술하는 데 필요한 최소한의 ‘정보 조각’ 수입니다. 같은 도형인데도 어떤 표현은 다른 표현보다 숫자를 더 많이 사용한다는 점이 흥미롭습니다.
하지만 이렇게 ‘추가로’ 들어가는 숫자는 언제나 도형을 매개화하는 과정에 중복이 있기 때문에 생깁니다. 벡터의 길이를 1로 제한하는 것처럼 적절한 제약을 두면 이 중복을 없앨 수 있습니다. 예를 들어 평면 위 원의 자유도는 3입니다. 중심 위치 (xc,yc)(x_c,y_c)에 두 개, 반지름 rr에 한 개가 필요합니다.
매개변수 형식에서는 이 변수들이 그대로 드러납니다.
중심과 반지름이 임의로 주어진 원의 매개변수 표현
x(t)=xc+rcos⁡2πt,y(t)=yc+rsin⁡2πt.x(t)=x_c+r\cos 2\pi t,\qquad y(t)=y_c+r\sin 2\pi t.
반면 일반적인 원뿔곡선의 방정식, 즉 음함수 형식은 Ax2+Bxy+Cy2+D=0Ax^2+Bxy+Cy^2+D=0으로 계수가 네 개입니다. 일반적인 원뿔곡선의 식을 다음 형태로 변형할 수 있다면 그것이 원임을 알 수 있습니다.
중심과 반지름이 임의로 주어진 원의 음함수 표현
(x−xc)2+(y−yc)2=r2.(x-x_c)^2+(y-y_c)^2=r^2.
💡
원문 계산식 점검 · 일반 원뿔곡선 식에는 선형항도 필요하다
PDF 316~318페이지는 일반 원뿔곡선의 식을 Ax2+Bxy+Cy2+D=0Ax^2+Bxy+Cy^2+D=0으로 제시합니다. 그러나 임의의 위치로 이동한 원뿔곡선까지 표현하려면 일반적으로 다음 형태가 필요합니다.
Ax2+Bxy+Cy2+Dx+Ey+F=0.Ax^2+Bxy+Cy^2+Dx+Ey+F=0.
원문 식에는 xx와 yy의 선형항이 빠져 있습니다. 예를 들어 중심이 (2,3)(2,3)이고 반지름이 1인 원은 x2+y2−4x−6y+12=0x^2+y^2-4x-6y+12=0이므로 선형항을 생략할 수 없습니다. 원의 자유도가 중심 두 성분과 반지름의 세 개라는 설명은 맞습니다.

9.2 직선과 레이 (Lines and Rays)

이제 구체적인 기본 도형을 살펴보겠습니다. 그중에서도 가장 기본적이고 중요한 도형일 법한 직선형 구간부터 시작합니다. 세 가지 기본 유형을 알아보고 용어도 분명히 하겠습니다. 고전 기하학에서는 다음과 같이 정의합니다.
•
직선(line) 은 양방향으로 무한히 뻗습니다.
•
선분(line segment) 은 두 끝점을 갖는, 직선의 유한한 일부입니다.
•
반직선(ray) 은 시작점이 있고 한 방향으로 무한히 뻗는 직선의 ‘절반’입니다.
컴퓨터 과학과 계산 기하학에서는 이 정의가 조금씩 달라지기도 합니다. 이 책은 직선과 선분에는 고전적인 정의를 사용하지만, ‘레이(ray)’의 정의는 조금 바꿔서 사용합니다.
•
레이는 방향이 있는 선분입니다.
따라서 이 책에서 레이는 시작점과 끝점을 가집니다. 레이는 위치, 유한한 길이, 그리고 길이가 0이 아니라면 방향도 정의합니다. 레이는 선분의 두 끝을 구별한 것일 뿐이며, 레이로 무한한 직선을 정의할 수도 있습니다. 그래서 레이는 계산 기하학과 그래픽스에서 근본적으로 중요하며, 이 절에서도 주로 레이를 다룹니다.
레이는 점 하나가 시간에 따라 공간을 쓸고 지나간 결과라고 생각할 수 있습니다. 비디오 게임에는 레이가 어디에나 있습니다. 대표적인 예가 레이 트레이싱(raytracing)이라는 렌더링 전략입니다. 이름 그대로 광자의 경로를 나타내는 레이를 사용합니다. AI에서는 적이 플레이어를 볼 수 있는지 알아내기 위해 환경 안으로 ‘시선’ 레이를 쏩니다.
많은 사용자 인터페이스 도구도 마우스 커서 아래에 어떤 물체가 있는지 알아내기 위해 레이 트레이싱을 사용합니다. 게임 속 공중에서는 총알과 레이저가 끊임없이 날아다니며, 무엇에 명중했는지 판단하려면 레이가 필요합니다. 그림 9.2는 직선, 선분, 레이를 비교합니다.
그림 9.2
그림 9.2. 직선, 선분, 레이.
이 절의 나머지 부분에서는 2차원과 3차원에서 직선과 레이를 표현하는 여러 방법을 살펴봅니다. 9.2.1절에서는 아주 중요한 매개변수 형식을 비롯해 레이를 표현하는 간단한 방법을 설명합니다. 9.2.2절에서는 2차원의 무한한 직선을 정의하는 특별한 방법들을 다룹니다. 9.2.3절에서는 한 표현을 다른 표현으로 변환하는 예를 몇 가지 제시합니다.

9.2.1 레이

레이를 정의하는 가장 명백한 방법, 즉 ‘직접적인 형식’은 두 점을 사용하는 것입니다. 레이의 시작점과 끝점이며, 각각 porg\mathbf p_{\mathrm{org}}와 pend\mathbf p_{\mathrm{end}}로 표시하겠습니다(그림 9.3).
그림 9.3
그림 9.3. 시작점과 끝점으로 레이 정의하기.
매개변수 형식은 이와 조금밖에 다르지 않지만 매우 중요합니다.
벡터 표기법으로 쓴 레이의 매개변수 정의
p(t)=p0+td.(9.1)\mathbf p(t)=\mathbf p_0+t\mathbf d.\tag{9.1}
레이는 p(0)=p0\mathbf p(0)=\mathbf p_0에서 시작합니다. 따라서 p0\mathbf p_0는 레이의 위치 정보를, ‘델타 벡터’ d\mathbf d는 길이와 방향 정보를 담습니다. 매개변수 tt를 정규화된 범위 [0,1][0,1]로 제한하므로, 레이는 그림 9.4처럼 p(1)=p0+d\mathbf p(1)=\mathbf p_0+\mathbf d에서 끝납니다.
그림 9.4
그림 9.4. 매개변수로 레이 정의하기.
각 좌표에 대해 별도의 스칼라 함수를 쓸 수도 있습니다. 다만 벡터 형식이 더 간결하고, 차원 수에 관계없이 같은 방정식을 사용할 수 있다는 장점도 있습니다. 예를 들어 2차원 레이는 다음 두 스칼라 함수로 정의합니다.
2차원 레이의 매개변수 정의
x(t)=x0+tΔx,y(t)=y0+tΔy.x(t)=x_0+t\Delta x,\qquad y(t)=y_0+t\Delta y.
일부 교차 검사에서는 식 (9.1)을 조금 변형해서, 단위벡터 d^\hat{\mathbf d}를 사용하고 매개변수 tt의 정의역을 [0,l][0,l]로 바꿉니다. 여기서 ll은 레이의 길이입니다.
💡
레이의 t는 시간인가, 거리인가?
레이의 식 p(t)=p0+td\mathbf p(t)=\mathbf p_0+t\mathbf d에서 tt의 뜻은 우리가 정한 약속에 달려 있습니다. 총구가 (2,1)(2,1)이고 이번 프레임에 총알이 (8,4)(8,4)까지 이동한다면 d=(6,3)\mathbf d=(6,3)입니다. 이때 t=0.5t=0.5는 경로의 절반인 (5,2.5)(5,2.5)를 뜻합니다. ‘0.5초’나 ‘0.5미터’가 아닙니다.
반대로 d\mathbf d를 정규화한 d^\hat{\mathbf d}를 쓰고 p(s)=p0+sd^\mathbf p(s)=\mathbf p_0+s\hat{\mathbf d}로 나타내면 ss는 공간상의 거리입니다. 이 두 방식을 섞어 쓰면 최대 사거리와 충돌 시점이 잘못 계산되기 쉽습니다.
추가 설명 도해
추가 애니메이션. 같은 시작점과 끝점을 잇는 레이 위를 t=0→1t=0\to1로 이동합니다. 하단 수치는 실제 좌표입니다. 원문 그림을 대체하지 않는 직접 제작 보조 자료.

9.2.2 2차원 직선의 특별한 표현

이번에는 무한한 직선을 기술하는 특별한 방법들을 좀 더 살펴보겠습니다. 이 방법들은 2차원에만 적용됩니다. 3차원에서는 비슷한 기법으로 평면을 정의하며, 이는 9.5절에서 설명합니다. 2차원 레이에는 본질적으로 네 개의 자유도, 즉 x0,y0,Δx,Δyx_0,y_0,\Delta x,\Delta y가 있지만, 무한한 직선의 자유도는 두 개뿐입니다.
대부분의 독자는 기울기-절편 형식(slope-intercept form) 에 익숙할 것입니다. 2차원의 무한한 직선을 나타내는 음함수 표현입니다.
기울기-절편 형식
y=mx+y0.(9.2)y=mx+y_0.\tag{9.2}
기호 mm은 전통적으로 직선의 기울기를 나타냅니다. 기울기는 세로 변화량(rise)을 가로 변화량(run)으로 나눈 비율입니다. 위로 rise만큼 이동할 때 오른쪽으로 run만큼 이동한다는 뜻입니다(그림 9.5). yy절편은 직선이 yy축과 만나는 곳으로, 식 (9.2)에서 y0y_0로 표시한 값입니다.
뒤에서 혼동하지 않도록 여기서는 전통적으로 쓰는 변수 bb를 쓰지 않았습니다. x=0x=0을 대입하면 직선이 y=y0y=y_0에서 yy축과 만난다는 사실이 분명해집니다.
그림 9.5
그림 9.5. 직선의 기울기와 yy절편.
기울기-절편 형식을 보면 무한한 직선에 실제로 자유도가 두 개 있음을 쉽게 확인할 수 있습니다. 하나는 회전, 다른 하나는 평행이동에 해당합니다. 아쉽게도 수직선의 기울기는 무한대이므로 이 형식으로 표현할 수 없습니다. 수직선의 음함수 표현은 x=kx=k입니다. 수평선은 문제가 없습니다. 기울기가 0이기 때문입니다.
이 특이점은 다음처럼 조금 다른 음함수 형식을 사용하면 피할 수 있습니다.
2차원 무한 직선의 음함수 정의
ax+by=d.(9.3)ax+by=d.\tag{9.3}
대부분의 자료에서는 ax+by+d=0ax+by+d=0을 사용합니다. 그 형식의 dd는 이 책의 식과 부호가 반대입니다. 이 책에서는 항이 더 적고 dd의 기하학적 의미도 더 직관적이라고 생각하므로 식 (9.3)의 형식을 사용합니다.
벡터 n=[a,b]\mathbf n=[a,b]를 두면 식 (9.3)을 벡터 표기로 쓸 수 있습니다.
벡터 표기법으로 쓴 2차원 무한 직선의 음함수 정의
p⋅n=d.(9.4)\mathbf p\cdot\mathbf n=d.\tag{9.4}
이 형식은 계수를 세 개 사용하지만 2차원 무한 직선의 자유도는 두 개라고 했으므로, 어떤 중복이 있음을 알 수 있습니다. 방정식 양변에 임의의 상수를 곱할 수 있다는 점에 주목하겠습니다. 따라서 일반성을 잃지 않고 n\mathbf n의 길이를 자유롭게 선택할 수 있습니다. n\mathbf n을 단위벡터로 두면 편리할 때가 많습니다. 그러면 그림 9.6처럼 n\mathbf n과 dd에 흥미로운 기하학적 의미가 생깁니다.
그림 9.6
그림 9.6. 수직 벡터와 원점으로부터의 거리로 직선 정의하기.
n\mathbf n은 직선에 수직인 단위벡터이고, dd는 원점에서 직선까지의 부호 있는 거리(signed distance) 입니다. 이 거리는 직선에 수직인 방향, 즉 n\mathbf n과 평행한 방향으로 잽니다. 부호 있는 거리라는 말은, 원점에서 볼 때 직선이 법선이 가리키는 쪽에 있으면 dd가 양수라는 뜻입니다.
dd가 커지면 직선은 n\mathbf n 방향으로 움직입니다. 적어도 식 (9.4)처럼 dd를 등호 오른쪽에 둘 때는 그렇습니다. 전통적인 형식처럼 dd를 왼쪽으로 옮기고 오른쪽을 0으로 두면 dd의 부호가 뒤집히므로 앞의 설명도 반대가 됩니다.
n\mathbf n은 직선의 ‘방향’을, dd는 위치를 기술합니다. 위치를 나타내는 또 다른 방법은 직선 위의 점 q\mathbf q를 주는 것입니다. 직선 위에는 당연히 무한히 많은 점이 있으므로 그중 어느 점을 사용해도 됩니다(그림 9.7).
그림 9.7
그림 9.7. 수직 벡터와 직선 위의 한 점으로 직선 정의하기.
직선을 정의하는 마지막 방법은 두 점 q\mathbf q와 r\mathbf r을 잇는 선분의 수직이등분선 으로 정의하는 것입니다(그림 9.8). 이것은 실제로 직선의 가장 오래된 정의 중 하나입니다. 주어진 두 점에서 같은 거리에 있는 모든 점의 집합이라는 뜻입니다.
그림 9.8
그림 9.8. 선분의 수직이등분선으로 직선 정의하기.

9.2.3 표현 사이의 변환

레이나 직선을 여러 표현 기법 사이에서 변환하는 예를 몇 가지 살펴보겠습니다. 가능한 조합을 전부 다루지는 않습니다. 앞에서 배운 무한 직선에 관한 기법은 2차원에만 적용된다는 점을 기억하겠습니다.
두 점으로 정의한 레이를 매개변수 형식으로 바꾸려면 다음과 같이 합니다.
p0=porg,d=pend−porg.\mathbf p_0=\mathbf p_{\mathrm{org}},\qquad \mathbf d=\mathbf p_{\mathrm{end}}-\mathbf p_{\mathrm{org}}.
반대로 매개변수 형식을 두 점 형식으로 바꾸는 방법은 다음과 같습니다.
porg=p0,pend=p0+d.\mathbf p_{\mathrm{org}}=\mathbf p_0,\qquad \mathbf p_{\mathrm{end}}=\mathbf p_0+\mathbf d.
매개변수 형식의 레이가 주어지면 이 레이를 포함하는 직선의 음함수 표현을 구할 수 있습니다.
a=dy,b=−dx,d=xorgdy−yorgdx.(9.5)a=d_y,\qquad b=-d_x,\qquad d=x_{\mathrm{org}}d_y-y_{\mathrm{org}}d_x.\tag{9.5}
음함수 형식의 직선을 기울기-절편 형식으로 바꾸려면 다음과 같이 합니다.
m=−a/b,y0=d/b.(9.6)m=-a/b,\qquad y_0=d/b.\tag{9.6}
음함수 형식에서 ‘법선과 거리’ 형식으로의 변환은 다음과 같습니다.
n^=[a b]a2+b2,distance=da2+b2.\hat{\mathbf n}=\frac{[a\ b]}{\sqrt{a^2+b^2}},\qquad \mathrm{distance}=\frac{d}{\sqrt{a^2+b^2}}.
법선과 직선 위의 한 점이 주어진 경우, 법선과 거리 형식으로 바꾸려면 다음 식을 사용합니다.
distance=n^⋅q.\mathrm{distance}=\hat{\mathbf n}\cdot\mathbf q.
이는 n^\hat{\mathbf n}이 단위벡터라고 가정한 식입니다.
마지막으로 수직이등분선 형식을 음함수 형식으로 변환할 때 원문에서는 다음 식을 사용합니다.
a=qy−ry,b=rx−qx,d=q+r2⋅[a b]=q+r2⋅[qy−ryrx−qx]=(qx+rx)(qy−ry)+(qy+ry)(rx−qx)2=(qxqy−qxry+rxqy−rxry)+(qyrx−qyqx+ryrx−ryqx)2=rxqy−qxry.\begin{aligned} a&=q_y-r_y,\\ b&=r_x-q_x,\\ d&=\frac{\mathbf q+\mathbf r}{2}\cdot[a\ b] =\frac{\mathbf q+\mathbf r}{2}\cdot[q_y-r_y\quad r_x-q_x]\\ &=\frac{(q_x+r_x)(q_y-r_y)+(q_y+r_y)(r_x-q_x)}{2}\\ &=\frac{(q_xq_y-q_xr_y+r_xq_y-r_xr_y)+(q_yr_x-q_yq_x+r_yr_x-r_yq_x)}{2}\\ &=r_xq_y-q_xr_y. \end{aligned}
💡
원문 계산식 점검 · 제시된 마지막 식은 수직이등분선이 아니라 두 점을 지나는 직선이다
PDF 324페이지의 a=qy−ry, b=rx−qx, d=rxqy−qxrya=q_y-r_y,\ b=r_x-q_x,\ d=r_xq_y-q_xr_y는 점 q\mathbf q와 r\mathbf r을 모두 지나는 직선의 식입니다. 이 계수를 ‘수직이등분선’ 변환식으로 사용하면 안 됩니다.
수직이등분선의 법선은 두 점을 잇는 벡터와 평행해야 합니다. m=(q+r)/2\mathbf m=(\mathbf q+\mathbf r)/2라고 하면 올바른 식 한 가지는 다음과 같습니다.
n=r−q,d=n⋅m,p⋅n=d. \mathbf n=\mathbf r-\mathbf q,\qquad d=\mathbf n\cdot\mathbf m,\qquad \mathbf p\cdot\mathbf n=d.
성분으로는 a=rx−qx, b=ry−qy, d=(rx2+ry2−qx2−qy2)/2a=r_x-q_x,\ b=r_y-q_y,\ d=(r_x^2+r_y^2-q_x^2-q_y^2)/2입니다. 예를 들어 q=(0,0),r=(2,0)\mathbf q=(0,0),\mathbf r=(2,0)이면 올바른 수직이등분선은 x=1x=1입니다. 원문의 식을 그대로 쓰면 y=0y=0이 나옵니다.

9.3 구와 원 (Spheres and Circles)

구(sphere)는 주어진 점에서 일정한 거리만큼 떨어진 모든 점의 집합으로 정의하는 3차원 도형입니다. 구의 중심에서 표면 위의 한 점까지의 거리를 반지름(radius) 이라고 합니다. 구를 직접적으로 표현하는 방법은 중심 c\mathbf c와 반지름 rr을 기술하는 것입니다.
구는 단순하기 때문에 계산 기하학과 그래픽스에 자주 등장합니다. 구와의 교차를 계산하는 식이 간단하므로, 충돌할 가능성이 없는 대상을 빠르게 제외하는 단순 배제(trivial rejection) 에는 경계 구(bounding sphere)를 자주 사용합니다. 또 하나 중요한 점은 구를 회전해도 차지하는 범위가 변하지 않는다는 것입니다.
따라서 단순 배제에 경계 구를 사용할 때, 구의 중심이 물체의 원점이라면 물체의 방향은 무시해도 됩니다. 경계 상자(9.4절 참고)에는 이런 성질이 없습니다.
구의 음함수 형식은 ‘중심에서 주어진 거리만큼 떨어진 모든 점의 집합’이라는 정의에서 곧바로 나옵니다. 중심이 c\mathbf c이고 반지름이 rr인 구의 음함수 표현은 다음과 같습니다.
벡터 표기로 쓴 구의 음함수 정의
∥p−c∥=r.(9.7)\|\mathbf p-\mathbf c\|=r.\tag{9.7}
여기서 p\mathbf p는 구의 표면 위 임의의 점입니다. 구 내부의 점도 식을 만족하게 하려면 ==을 ≤\le로 바꾸어야 합니다. 식 (9.7)은 벡터 표기를 사용하므로 2차원에서도 원의 음함수 정의로 사용할 수 있습니다. 더 흔히 보는 형식은 벡터 표기를 성분으로 풀어 쓰고 양변을 제곱한 것입니다.
원과 구의 음함수 정의
(x−cx)2+(y−cy)2=r2(2차원 원).(9.8)(x-c_x)^2+(y-c_y)^2=r^2\qquad\text{(2차원 원)}.\tag{9.8}
(x−cx)2+(y−cy)2+(z−cz)2=r2(3차원 구).(9.9)(x-c_x)^2+(y-c_y)^2+(z-c_z)^2=r^2\qquad\text{(3차원 구)}.\tag{9.9}
원이나 구에서는 지름(diameter), 즉 한 점에서 정확히 반대편 점까지의 거리와 원주(circumference), 즉 원을 한 바퀴 도는 거리에도 관심이 있을 수 있습니다. 초등 기하학은 이 값들뿐 아니라 원의 넓이, 구의 겉넓이, 구의 부피를 구하는 공식도 제공합니다.
D=2r(지름),C=2πr=πD(원주),A=πr2(원의 넓이),S=4πr2(구의 겉넓이),V=43πr3(구의 부피).\begin{aligned} D&=2r&&\text{(지름)},\\ C&=2\pi r=\pi D&&\text{(원주)},\\ A&=\pi r^2&&\text{(원의 넓이)},\\ S&=4\pi r^2&&\text{(구의 겉넓이)},\\ V&=\frac43\pi r^3&&\text{(구의 부피)}. \end{aligned}
미적분을 좋아하는 독자라면, 원의 넓이를 rr에 대해 미분하면 원주가 나오고 구의 부피를 미분하면 겉넓이가 나온다는 점이 흥미로울 것입니다.

9.4 경계 상자 (Bounding Boxes)

경계 부피로 흔히 쓰는 또 다른 간단한 기본 도형은 경계 상자(bounding box)입니다. 경계 상자는 축에 정렬되어 있을 수도 있고 임의의 방향을 향할 수도 있습니다. 축 정렬 경계 상자(axially aligned bounding box) 는 각 면이 주축에 수직이어야 한다는 제약이 있습니다. 보통 약어 AABB 로 부릅니다.
3차원 AABB는 각 면이 좌표평면 중 하나와 평행한 간단한 육면체입니다. 반드시 정육면체일 필요는 없으며, 길이·너비·높이가 각각 달라도 됩니다. 그림 9.9는 간단한 3차원 물체 몇 개와 각 물체의 축 정렬 경계 상자를 보여줍니다.
그림 9.9
그림 9.9. 3차원 물체와 각각의 AABB.
또 하나 자주 쓰는 약어는 OBB(oriented bounding box), 즉 방향이 있는 경계 상자입니다. 이 절에서 OBB를 많이 다루지 않는 이유는 두 가지입니다. 첫째, 축 정렬 경계 상자는 만들기도 사용하기도 더 쉽습니다. 하지만 더 중요한 이유는, OBB를 단순히 방향이 부여된 AABB로 생각할 수 있기 때문입니다.
모든 경계 상자는 어떤 좌표계에서는 AABB입니다. 실제로 좌표축들이 상자의 면에 수직인 좌표계라면 어느 것이든 됩니다. 즉 AABB와 OBB의 차이는 상자 자체에 있는 것이 아니라, 그 경계 상자와 정렬된 좌표계에서 계산하느냐에 있습니다.
예를 들어 월드 안 물체마다 물체 공간 기준 AABB를 저장한다고 하겠습니다. 물체 공간에서 연산할 때 이 경계 상자는 AABB입니다. 하지만 월드 공간이나 직립 공간에서 계산할 때는 같은 상자가 OBB입니다. 월드의 축에 대해 ‘비스듬히’ 놓여 있을 수 있기 때문입니다.
이 절은 3차원 AABB를 중심으로 설명하지만, 대부분의 내용은 세 번째 차원을 빼기만 하면 2차원에도 곧바로 적용할 수 있습니다.
이어지는 네 소절에서는 AABB의 기본 성질을 다룹니다. 9.4.1절에서는 사용할 표기법과 AABB의 표현 방법을 소개합니다. 9.4.2절에서는 점들의 집합을 감싸는 AABB를 구하는 방법을 설명합니다. 9.4.3절에서는 AABB와 경계 구를 비교합니다. 9.4.4절에서는 변환된 AABB를 감싸는 AABB를 만드는 방법을 보여줍니다.

9.4.1 AABB 표현하기

AABB의 중요한 속성과 그 값을 가리킬 때 사용할 표기법을 소개하겠습니다. AABB 안의 점들은 다음 부등식을 만족합니다.
xmin⁡≤x≤xmax⁡,ymin⁡≤y≤ymax⁡,zmin⁡≤z≤zmax⁡.x_{\min}\le x\le x_{\max},\qquad y_{\min}\le y\le y_{\max},\qquad z_{\min}\le z\le z_{\max}.
특별히 중요한 두 꼭짓점은 다음과 같습니다.
pmin⁡=[xmin⁡ ymin⁡ zmin⁡],pmax⁡=[xmax⁡ ymax⁡ zmax⁡].\mathbf p_{\min}=[x_{\min}\ y_{\min}\ z_{\min}],\qquad \mathbf p_{\max}=[x_{\max}\ y_{\max}\ z_{\max}].
중심점 c\mathbf c는 다음과 같습니다.
c=(pmin⁡+pmax⁡)/2.\mathbf c=(\mathbf p_{\min}+\mathbf p_{\max})/2.
‘크기 벡터’ s\mathbf s는 pmin⁡\mathbf p_{\min}에서 pmax⁡\mathbf p_{\max}로 향하는 벡터이며, 상자의 너비·높이·길이를 담습니다.
s=pmax⁡−pmin⁡.\mathbf s=\mathbf p_{\max}-\mathbf p_{\min}.
상자의 ‘반지름 벡터’ r\mathbf r를 사용할 수도 있습니다. 이는 크기 벡터 s\mathbf s의 절반이며, c\mathbf c에서 pmax⁡\mathbf p_{\max}로 향하는 벡터로 해석할 수 있습니다.
r=pmax⁡−c=s/2.\mathbf r=\mathbf p_{\max}-\mathbf c=\mathbf s/2.
AABB를 모호함 없이 정의하려면 pmin⁡,pmax⁡,c,s,r\mathbf p_{\min},\mathbf p_{\max},\mathbf c,\mathbf s,\mathbf r라는 다섯 벡터 중 두 개만 있으면 됩니다. s\mathbf s와 r\mathbf r의 조합만 제외하면 어느 쌍이든 사용할 수 있습니다. 상황에 따라 더 유용한 표현이 있지만, 이 책에서는 pmin⁡\mathbf p_{\min}과 pmax⁡\mathbf p_{\max}를 사용하기를 권합니다.
실제로는 s,c,r\mathbf s,\mathbf c,\mathbf r보다 이 두 값이 훨씬 더 자주 필요하기 때문입니다. 물론 이 두 값으로 나머지 세 벡터를 계산하는 일도 매우 빠릅니다. C에서는 코드 9.1 같은 구조체로 AABB를 나타낼 수 있습니다.
struct AABB3 { Vector3 min; Vector3 max; };
C++
복사
코드 9.1. AABB를 기술하는 가장 직접적인 방법.

9.4.2 AABB 계산하기

점들의 집합에 대한 AABB를 구하는 과정은 간단합니다. 먼저 최솟값과 최댓값을 ‘무한대’, 또는 실제로 만날 어떤 수보다도 충분히 큰 값으로 초기화합니다. 그다음 점 목록을 순회하면서 각 점을 포함하도록 필요할 때마다 상자를 늘립니다.
void AABB3::empty() { min.x = min.y = min.z = FLT_MAX; max.x = max.y = max.z = -FLT_MAX; } void AABB3::add(const Vector3 &p) { if (p.x < min.x) min.x = p.x; if (p.x > max.x) max.x = p.x; if (p.y < min.x) min.y = p.y; if (p.y > max.x) max.y = p.y; if (p.z < min.x) min.z = p.z; if (p.z > max.x) max.z = p.z; }
C++
복사
코드 9.2. 유용한 AABB 함수 두 개. 위 코드는 제공된 원문 그대로이며, 축 비교 부분의 정정은 보충 설명에 따로 제시합니다.
AABB 클래스에는 이를 돕는 함수 두 개를 정의하는 경우가 많습니다. 첫 번째 함수는 AABB를 ‘비우고’, 두 번째는 필요하면 AABB를 확장해서 점 하나를 넣습니다. 코드 9.2가 그 예입니다.
이제 점들의 집합으로 경계 상자를 만들려면 다음 코드를 사용할 수 있습니다.
// 점 목록 const int N; Vector3 list[N]; // 먼저 상자를 비운다. AABB3 box; box.empty(); // 각 점을 상자에 추가한다. for (int i = 0; i < N; ++i) { box.add(list[i]); }
C++
복사
코드 9.3. 점들의 집합에 대한 AABB 계산하기.
💡
원문 계산식 점검 · AABB의 y와 z는 같은 축끼리 비교해야 한다
PDF 327페이지 코드 9.2는 y,zy,z를 검사하면서 비교 대상에 min.x와 max.x를 사용합니다. 그대로 쓰면 잘못된 AABB가 나올 수 있습니다. add 함수의 올바른 형태는 다음과 같습니다.
void AABB3::add(const Vector3 &p) { if (p.x < min.x) min.x = p.x; if (p.x > max.x) max.x = p.x; if (p.y < min.y) min.y = p.y; if (p.y > max.y) max.y = p.y; if (p.z < min.z) min.z = p.z; if (p.z > max.z) max.z = p.z; }
C++
복사
코드 9.3의 const int N;은 실제 점 개수가 들어갈 자리를 나타내는 예시입니다. 그대로는 초기화되지 않은 상수이므로, 컴파일하는 코드에서는 실제 상수로 초기화하거나 컨테이너의 크기를 사용해야 합니다.

9.4.3 AABB와 경계 구 비교

많은 상황에서 AABB와 경계 구 중 하나를 선택할 수 있습니다. 경계 구와 비교할 때 AABB에는 두 가지 주요 장점이 있습니다.
첫째, 점들의 집합에 대한 최적의 AABB를 구하는 알고리즘은 구현하기 쉽고 선형 시간에 실행할 수 있습니다. 최적의 경계 구를 구하는 일은 훨씬 어렵습니다. 경계 구를 계산하는 알고리즘은 O’Rourke [52]와 Lengyel [42]에 설명되어 있습니다.
둘째, 실제로 등장하는 많은 물체에서는 AABB가 물체를 더 꼭 맞게 감싸므로 단순 배제에 더 유리합니다. 물론 경계 구가 더 좋은 물체도 있습니다. 물체 자체가 구라고 생각해 보겠습니다! 최악의 경우 AABB의 부피는 경계 구 부피의 두 배에 조금 못 미치지만, 경계 구가 좋지 않을 때는 정말 심하게 좋지 않을 수 있습니다. 예를 들어 전신주를 감싸는 경계 구와 AABB를 생각해 보겠습니다.
구의 근본적인 문제는 모양을 정하는 자유도가 반지름 하나뿐이라는 데 있습니다. AABB의 자유도는 길이·너비·높이의 세 개입니다. 따라서 다양한 모양의 물체에 보통 더 잘 맞출 수 있습니다. 그림 9.10의 물체 대부분은 AABB가 경계 구보다 작습니다. 예외는 오른쪽 위의 별 모양으로, 이 경우 경계 구가 AABB보다 조금 작습니다.
아래쪽 소총 두 개의 AABB를 보면, AABB가 물체의 방향에 매우 민감하다는 것을 알 수 있습니다. 소총의 크기는 같고 방향만 다릅니다. 반면 경계 구의 크기는 같습니다. 경계 구는 물체의 방향에 영향을 받지 않기 때문입니다.
그림 9.10
그림 9.10. 여러 물체의 AABB와 경계 구.
물체가 자유롭게 회전할 수 있다면 AABB의 장점 일부는 줄어들 수 있습니다. 더 꼭 맞는 부피(OBB)와 간결하고 빠른 표현(경계 구) 사이에는 본질적인 절충 관계가 있습니다. 어떤 경계 도형이 가장 좋은지는 응용 상황에 크게 좌우됩니다.

9.4.4 AABB 변환하기

때로는 AABB를 한 좌표계에서 다른 좌표계로 변환해야 합니다. 예를 들어 물체 공간의 AABB가 있고, 이를 월드 공간의 AABB로 바꾸려 한다고 하겠습니다. 물체 공간 AABB는 월드 공간에서 보면 사실상 OBB와 같습니다(9.4절 참고). 이론적으로는 물체 자체의 월드 공간 AABB를 직접 계산할 수도 있습니다.
하지만 여기서는 물체의 모양 정보, 예를 들어 꼭짓점이 천 개인 삼각형 메시가 이미 물체 공간에서 계산해 둔 AABB보다 복잡하다고 가정합니다. 그래서 월드 공간의 AABB를 얻기 위해 물체 공간 AABB를 변환합니다.
변환 결과는 물체가 회전했다면 반드시 축에 정렬되어 있지는 않습니다. 물체를 비틀었다면 반드시 상자 모양이지도 않습니다. 그래도 이렇게 ‘변환된 AABB’를 감싸는 AABB를 구하는 편이, 아주 단순한 물체를 제외하고는 변환된 물체 전체에서 새 AABB를 구하는 것보다 빠릅니다.
AABB의 꼭짓점은 여덟 개뿐이기 때문입니다. 어쩌면 변환 결과를 NNAABNNB, 즉 ‘꼭 축에 정렬되어 있지는 않고, 꼭 상자이지도 않은 경계 도형’이라고 불러야 할지도 모르겠습니다.
변환된 AABB를 감싸는 AABB를 계산할 때 원래의 pmin⁡\mathbf p_{\min}과 pmax⁡\mathbf p_{\max}만 변환해서는 충분하지 않습니다. 그렇게 하면 xmin⁡>xmax⁡x_{\min}>x_{\max}처럼 잘못된 경계 상자가 나올 수 있습니다. 새 AABB를 계산하려면 여덟 꼭짓점을 모두 변환한 다음, 그 여덟 점을 감싸는 AABB를 만들어야 합니다.
변환에 따라 다르지만, 대개는 원래 경계 상자보다 큰 상자가 됩니다. 예를 들어 2차원에서 45도 회전하면 경계 상자의 크기가 상당히 커집니다(그림 9.11).
그림 9.11
그림 9.11. 변환된 상자를 감싸는 AABB.
그림 9.11의 원래 AABB인 파란 상자와, 회전된 AABB만을 사용해 계산한 새 AABB인 오른쪽의 가장 큰 빨간 상자를 비교해 보겠습니다. 새 AABB는 거의 두 배 크기입니다. 반면 회전된 AABB 대신 회전된 물체에서 직접 AABB를 구할 수 있다면, 원래 AABB와 크기가 거의 같다는 점에 주목하겠습니다.
알고 보면 AABB의 구조를 활용해 새 AABB를 더 빠르게 만들 수 있습니다. 실제로 여덟 꼭짓점을 모두 변환하고 그 점들로 새 AABB를 구성할 필요는 없습니다.
3차원 점을 3×33\times3 행렬로 변환할 때 어떤 일이 일어나는지 잠깐 복습하겠습니다. 벡터와 행렬을 곱하는 방법을 잊었다면 4.1.7절을 참고하겠습니다.
[x′ y′ z′]=[x y z][m11m12m13m21m22m23m31m32m33];[x'\ y'\ z']=[x\ y\ z] \begin{bmatrix}m_{11}&m_{12}&m_{13}\\m_{21}&m_{22}&m_{23}\\m_{31}&m_{32}&m_{33}\end{bmatrix};
x′=m11x+m21y+m31z,y′=m12x+m22y+m32z,z′=m13x+m23y+m33z.x'=m_{11}x+m_{21}y+m_{31}z,\qquad y'=m_{12}x+m_{22}y+m_{32}z,\qquad z'=m_{13}x+m_{23}y+m_{33}z.
원래 경계 상자는 xmin⁡,xmax⁡,ymin⁡,…x_{\min},x_{\max},y_{\min},\ldots에 저장되어 있고, 새 경계 상자는 xmin⁡′,xmax⁡′,ymin⁡′,…x'_{\min},x'_{\max},y'_{\min},\ldots에 계산한다고 가정하겠습니다. 예로 xmin⁡′x'_{\min}을 더 빠르게 구하는 방법을 보겠습니다. 즉 원래 여덟 꼭짓점 중 임의의 점 [x,y,z][x,y,z]에 대해 다음 값의 최솟값을 찾으려는 것입니다.
m11x+m21y+m31z.m_{11}x+m_{21}y+m_{31}z.
우리의 과제는 변환 뒤 xx값이 가장 작아지는 꼭짓점을 찾는 것입니다. 전체 합을 최소화하는 요령은 세 곱을 각각 따로 최소화하는 데 있습니다. 첫 번째 곱 m11xm_{11}x를 보겠습니다. 이 곱을 최소화하려면 xx에 xmin⁡x_{\min}과 xmax⁡x_{\max} 중 무엇을 대입해야 할까요?
분명히 m11>0m_{11}>0이면 더 작은 값인 xmin⁡x_{\min}을 쓰는 편이 곱도 작습니다. 반대로 m11<0m_{11}<0이면 xmax⁡x_{\max}를 쓰는 편이 작습니다. 편리하게도 xmin⁡′x'_{\min}을 계산할 때 둘 중 어느 것을 사용하든, xmax⁡′x'_{\max}을 계산할 때는 나머지 값을 사용하면 됩니다.
이 과정을 행렬의 아홉 원소 각각에 적용합니다.
코드 9.4는 이 기법을 보여줍니다. Matrix4x3 클래스는 모든 아핀 변환을 나타낼 수 있는 4×34\times3 변환 행렬입니다. 행벡터에 작용하는 4×44\times4 행렬에서 맨 오른쪽 열이 [0,0,0,1]T[0,0,0,1]^T라고 가정한 형태입니다.
void AABB3::setToTransformedBox(const AABB3 &box, const Matrix4x3 &m) { // 마지막 행에서 시작한다. 이는 평행이동 부분, // 즉 변환 후 원점의 위치다. min = max = getTranslation(m); // 행렬 원소 아홉 개를 각각 살펴 새 AABB를 계산한다. if (m.m11 > 0.0f) { min.x += m.m11 * box.min.x; max.x += m.m11 * box.max.x; } else { min.x += m.m11 * box.max.x; max.x += m.m11 * box.min.x; } if (m.m12 > 0.0f) { min.y += m.m12 * box.min.x; max.y += m.m12 * box.max.x; } else { min.y += m.m12 * box.max.x; max.y += m.m12 * box.min.x; } if (m.m13 > 0.0f) { min.z += m.m13 * box.min.x; max.z += m.m13 * box.max.x; } else { min.z += m.m13 * box.max.x; max.z += m.m13 * box.min.x; } if (m.m21 > 0.0f) { min.x += m.m21 * box.min.y; max.x += m.m21 * box.max.y; } else { min.x += m.m21 * box.max.y; max.x += m.m21 * box.min.y; } if (m.m22 > 0.0f) { min.y += m.m22 * box.min.y; max.y += m.m22 * box.max.y; } else { min.y += m.m22 * box.max.y; max.y += m.m22 * box.min.y; } if (m.m23 > 0.0f) { min.z += m.m23 * box.min.y; max.z += m.m23 * box.max.y; } else { min.z += m.m23 * box.max.y; max.z += m.m23 * box.min.y; } if (m.m31 > 0.0f) { min.x += m.m31 * box.min.z; max.x += m.m31 * box.max.z; } else { min.x += m.m31 * box.max.z; max.x += m.m31 * box.min.z; } if (m.m32 > 0.0f) { min.y += m.m32 * box.min.z; max.y += m.m32 * box.max.z; } else { min.y += m.m32 * box.max.z; max.y += m.m32 * box.min.z; } if (m.m33 > 0.0f) { min.z += m.m33 * box.min.z; max.z += m.m33 * box.max.z; } else { min.z += m.m33 * box.max.z; max.z += m.m33 * box.min.z; } }
C++
복사
코드 9.4. 변환된 AABB 계산하기.
💡
회전된 AABB를 또 감쌀 때 생기는 빈 공간
보스의 칼처럼 길쭉한 물체는 실제 모양보다 AABB 안의 빈 공간이 훨씬 클 수 있습니다. 이 경우 AABB 겹침은 ‘정밀 충돌 검사를 해야 한다’는 후보 판정입니다. 곧바로 명중 판정으로 사용하면 칼에 닿지 않았는데 맞았다고 나올 수 있습니다.
원본 메시에서 AABB를 다시 계산하면 더 꼭 맞지만 꼭짓점을 모두 확인해야 합니다. 이미 계산해 둔 물체 공간 AABB를 변환해 새 AABB를 얻으면 빠르지만 느슨해질 수 있습니다. 본문의 그림 9.11은 바로 이 비용과 정확한 감싸기 사이의 차이를 보여줍니다.
추가 설명 도해
추가 애니메이션. 회전하는 길쭉한 물체를 축 정렬 상자가 감쌉니다. 물체의 크기는 일정하지만 상자의 너비·높이와 빈 공간은 계속 바뀝니다.

9.5 평면 (Planes)

평면은 3차원 공간 안에 있는 평평한 2차원 부분공간입니다. 평면은 비디오 게임에서 매우 자주 쓰는 도구이며, 이 절의 개념은 특히 유용합니다. 유클리드라면 받아들였을 법한 평면의 정의는 2차원 무한 직선의 수직이등분선 정의와 비슷합니다. 주어진 두 점에서 같은 거리에 있는 모든 점의 집합이라는 것입니다.
정의가 비슷하다는 사실은 3차원의 평면과 2차원의 무한 직선이 많은 성질을 공유한다는 점을 암시합니다. 예를 들어 둘 다 공간을 두 개의 ‘반공간(half-space)’으로 나눕니다.
이 절에서는 평면의 기본 성질을 다룹니다. 9.5.1절에서는 평면 방정식을 사용해 평면을 음함수로 정의하는 방법을 보여줍니다. 9.5.2절에서는 세 점으로 평면을 정의하는 방법을 설명합니다. 9.5.3절에서는 정확히 같은 평면 위에 있지 않을 수도 있는 점들의 집합에 ‘가장 잘 맞는’ 평면을 구합니다. 9.5.4절에서는 점에서 평면까지의 거리를 계산합니다.

9.5.1 평면 방정식: 평면의 음함수 정의

9.2.2절에서 2차원 무한 직선을 기술한 기법과 비슷한 방법으로 평면을 나타낼 수 있습니다. 평면의 음함수 형식은 다음 평면 방정식 을 만족하는 모든 점 p=(x,y,z)\mathbf p=(x,y,z)로 주어집니다.
ax+by+cz=d(스칼라 표기),p⋅n=d(벡터 표기).(9.10)\begin{aligned} ax+by+cz&=d&&\text{(스칼라 표기)},\\ \mathbf p\cdot\mathbf n&=d&&\text{(벡터 표기)}. \end{aligned}\tag{9.10}
벡터 형식에서는 n=[a,b,c]\mathbf n=[a,b,c]입니다. n\mathbf n을 알면 평면 위에 있다고 알려진 아무 점에서나 dd를 계산할 수 있습니다.
대부분의 자료는 평면 방정식을 ax+by+cz+d=0ax+by+cz+d=0으로 제시합니다. 이는 dd의 부호를 뒤집는 효과가 있습니다. 9.2.2절에서 등호 한쪽에 dd를 두기를 선호한다고 설명한 이유가 여기에도 적용됩니다. 경험상 이 책의 형식은 항과 마이너스 기호를 줄여 주며, dd를 기하학적으로 더 직관적으로 해석할 수 있게 해 줍니다.
벡터 n\mathbf n은 평면에 수직이므로 평면 법선(plane normal) 이라고 부릅니다. 흔히 단위 길이로 정규화하지만 반드시 그럴 필요는 없습니다. 단위 길이를 가정할 때는 모자 기호를 붙여 n^\hat{\mathbf n}으로 씁니다. 법선은 평면의 방향을, dd는 위치를 정합니다.
법선이 단위벡터이면 d는 법선 방향으로 측정한 원점에서 평면까지의 부호 있는 거리를 정합니다. dd를 늘리면 평면이 법선 방향, 즉 앞쪽으로 미끄러져 갑니다. d>0d>0이면 원점은 평면 뒤쪽에 있고, d<0d<0이면 앞쪽에 있습니다. 이는 식 (9.10)처럼 dd를 등호 오른쪽에 둔다고 가정한 설명입니다.
dd가 왼쪽에 있는 표준 동차 형식에서는 부호 규칙이 반대입니다.
n\mathbf n이 평면에 수직임을 확인해 보겠습니다. p\mathbf p와 q\mathbf q를 평면 위의 임의의 점이라 하면 둘 다 평면 방정식을 만족합니다. 두 점을 식 (9.10)에 대입하면 다음과 같습니다.
n⋅p=d,n⋅q=d,n⋅p=n⋅q,n⋅p−n⋅q=0,n⋅(p−q)=0.(9.11)\begin{aligned} \mathbf n\cdot\mathbf p&=d,\\ \mathbf n\cdot\mathbf q&=d,\\ \mathbf n\cdot\mathbf p&=\mathbf n\cdot\mathbf q,\\ \mathbf n\cdot\mathbf p-\mathbf n\cdot\mathbf q&=0,\\ \mathbf n\cdot(\mathbf p-\mathbf q)&=0. \end{aligned}\tag{9.11}
식 (9.11)의 기하학적 의미는 n\mathbf n이 q\mathbf q에서 p\mathbf p로 향하는 벡터에 수직이라는 것입니다(2.11절 참고). 평면 위의 어떤 두 점을 골라도 성립하므로, n\mathbf n은 평면 안의 모든 벡터에 수직입니다.
흔히 평면에는 ‘앞쪽’과 ‘뒤쪽’이 있다고 생각합니다. 보통 n\mathbf n이 가리키는 쪽이 평면의 앞쪽입니다. 즉 n\mathbf n의 머리에서 꼬리를 향해 바라보면 평면의 앞면을 보게 됩니다(그림 9.12).
그림 9.12
그림 9.12. 평면의 앞쪽과 뒤쪽.
앞에서 말했듯이 n\mathbf n의 길이를 1로 제한하면 유용한 경우가 많습니다. 평면 방정식 전체에 임의의 상수를 곱할 수 있으므로 일반성을 잃지 않고 그렇게 할 수 있습니다.

9.5.2 세 점으로 평면 정의하기

평면 위에 있으면서 한 직선 위에는 있지 않은 세 점을 주는 것도 평면을 정의하는 방법입니다. 한 직선 위의 점들, 즉 공선(collinear)인 점들로는 안 됩니다. 그 직선을 포함하는 평면이 무한히 많아 어느 평면을 뜻하는지 알 수 없기 때문입니다.
평면 위에 있다고 알려진 세 점 p1,p2,p3\mathbf p_1,\mathbf p_2,\mathbf p_3에서 n\mathbf n과 dd를 계산해 보겠습니다. 먼저 n\mathbf n을 구해야 합니다. 그런데 n\mathbf n은 어느 쪽을 향해야 할까요? 왼손 좌표계에서 흔히 쓰는 방법은 그림 9.13처럼 평면의 앞쪽에서 보았을 때 p1,p2,p3\mathbf p_1,\mathbf p_2,\mathbf p_3가 시계 방향으로 나열되어 있다고 가정하는 것입니다.
오른손 좌표계에서는 보통 반시계 방향이라고 가정합니다. 이 규칙을 따르면 어느 좌표계를 사용하든 식이 같아집니다.
그림 9.13
그림 9.13. 평면 위의 세 점으로 평면 법선 계산하기.
시계 방향 순서에 맞추어 두 벡터를 만듭니다. e\mathbf e라는 표기는 ‘변(edge)’ 벡터를 뜻합니다. 이 식이 삼각형의 평면 방정식을 구할 때 자주 등장하기 때문입니다. 인덱스가 이상해 보일 수도 있지만 잠깐만 살펴보겠습니다. 삼각형을 더 자세히 다루는 9.6.1절에서 사용할 인덱스입니다.
두 벡터의 외적은 수직 벡터 n\mathbf n을 주지만, 이 벡터가 반드시 단위 길이인 것은 아닙니다. 앞서 말했듯이 보통은 n\mathbf n을 정규화합니다. 이를 간결하게 정리하면 다음과 같습니다.
세 점을 포함하는 평면의 법선
e3=p2−p1,e1=p3−p2,n^=e3×e1∥e3×e1∥.(9.12)\mathbf e_3=\mathbf p_2-\mathbf p_1,\qquad \mathbf e_1=\mathbf p_3-\mathbf p_2,\qquad \hat{\mathbf n}=\frac{\mathbf e_3\times\mathbf e_1}{\|\mathbf e_3\times\mathbf e_1\|}.\tag{9.12}
점들이 한 직선 위에 있으면 e3\mathbf e_3와 e1\mathbf e_1이 평행하므로 외적이 0\mathbf0이 되고, 이를 정규화할 수 없습니다. 이 수학적 특이점은 공선인 점들로는 평면을 유일하게 정의할 수 없다는 기하학적 특이점과 정확히 일치합니다.
이제 n^\hat{\mathbf n}을 알았으므로 남은 일은 dd를 구하는 것뿐입니다. 세 점 중 하나와 n^\hat{\mathbf n}을 내적하면 쉽게 구할 수 있습니다.

9.5.3 세 점보다 많은 점들에 ‘가장 잘 맞는’ 평면

가끔은 세 개보다 많은 점들의 집합에서 평면 방정식을 구하고 싶을 수 있습니다. 가장 흔한 예는 다각형의 꼭짓점들입니다. 이 경우 꼭짓점은 다각형 둘레를 따라 시계 방향으로 나열되어 있다고 가정합니다. 순서가 중요한 이유는 앞면과 뒷면을 구별하고, 결과적으로 법선이 향할 방향을 정하기 때문입니다.
단순하게는 연속한 세 점을 임의로 골라 그 세 점으로 평면 방정식을 구할 수 있습니다. 그러나 고른 점들이 한 직선 위에 있거나 거의 한 직선 위에 있을 수 있습니다. 거의 공선인 경우도 수치 정확도가 나쁘므로 거의 같은 정도로 문제가 됩니다. 다각형이 오목하고 고른 세 점이 오목하게 꺾이는 부분을 이루어서 반시계 방향으로 돌 수도 있습니다.
그러면 법선이 잘못된 방향을 가리킵니다. 또는 수치 오차나 다각형 생성 방식 때문에 꼭짓점들이 모두 같은 평면에 있지 않을 수도 있습니다. 정말 원하는 것은 모든 점을 고려해 그 집합에 ‘가장 잘 맞는’ 평면을 계산하는 방법입니다. 다음 nn개의 점이 주어졌다고 하겠습니다.
p1=[x1 y1 z1],p2=[x2 y2 z2],⋮pn−1=[xn−1 yn−1 zn−1],pn=[xn yn zn].\begin{aligned} \mathbf p_1&=[x_1\ y_1\ z_1],\\ \mathbf p_2&=[x_2\ y_2\ z_2],\\ &\vdots\\ \mathbf p_{n-1}&=[x_{n-1}\ y_{n-1}\ z_{n-1}],\\ \mathbf p_n&=[x_n\ y_n\ z_n]. \end{aligned}
가장 잘 맞는 수직 벡터 n\mathbf n은 다음 식으로 주어집니다.
nn개의 점에서 가장 잘 맞는 평면 법선 계산하기
nx=(z1+z2)(y1−y2)+(z2+z3)(y2−y3)+⋯+(zn−1+zn)(yn−1−yn)+(zn+z1)(yn−y1),ny=(x1+x2)(z1−z2)+(x2+x3)(z2−z3)+⋯+(xn−1+xn)(zn−1−zn)+(xn+x1)(zn−z1),nz=(y1+y2)(x1−x2)+(y2+y3)(x2−x3)+⋯+(yn−1+yn)(xn−1−xn)+(yn+y1)(xn−x1).(9.13)\begin{aligned} n_x={}&(z_1+z_2)(y_1-y_2)+(z_2+z_3)(y_2-y_3)+\cdots\\ &+(z_{n-1}+z_n)(y_{n-1}-y_n)+(z_n+z_1)(y_n-y_1),\\ n_y={}&(x_1+x_2)(z_1-z_2)+(x_2+x_3)(z_2-z_3)+\cdots\\ &+(x_{n-1}+x_n)(z_{n-1}-z_n)+(x_n+x_1)(z_n-z_1),\\ n_z={}&(y_1+y_2)(x_1-x_2)+(y_2+y_3)(x_2-x_3)+\cdots\\ &+(y_{n-1}+y_n)(x_{n-1}-x_n)+(y_n+y_1)(x_n-x_1). \end{aligned}\tag{9.13}
n\mathbf n이 단위 길이여야 한다는 제약을 적용하려면 이 벡터를 정규화해야 합니다.
합 기호를 쓰면 식 (9.13)을 간결하게 표현할 수 있습니다. pn+1≡p1\mathbf p_{n+1}\equiv\mathbf p_1인 순환 인덱스를 사용하면 다음과 같습니다.
nx=∑i=1n(zi+zi+1)(yi−yi+1),ny=∑i=1n(xi+xi+1)(zi−zi+1),nz=∑i=1n(yi+yi+1)(xi−xi+1).\begin{aligned} n_x&=\sum_{i=1}^{n}(z_i+z_{i+1})(y_i-y_{i+1}),\\ n_y&=\sum_{i=1}^{n}(x_i+x_{i+1})(z_i-z_{i+1}),\\ n_z&=\sum_{i=1}^{n}(y_i+y_{i+1})(x_i-x_{i+1}). \end{aligned}
코드 9.5는 점들의 집합에 가장 잘 맞는 평면 법선을 계산하는 한 가지 구현입니다.
Vector3 computeBestFitNormal(const Vector3 v[], int n) { // 합을 0으로 초기화한다. Vector3 result = kZeroVector; // 마지막 꼭짓점을 '이전' 꼭짓점으로 삼아 시작한다. // 이렇게 하면 루프 안에서 if 문을 쓰지 않아도 된다. const Vector3 *p = &v[n - 1]; // 꼭짓점을 순회한다. for (int i = 0; i < n; ++i) { // '현재' 꼭짓점을 가리키는 포인터를 얻는다. const Vector3 *c = &v[i]; // 각 변에 해당하는 곱을 알맞게 누적한다. result.x += (p->z + c->z) * (p->y - c->y); result.y += (p->x + c->x) * (p->z - c->z); result.z += (p->y + c->y) * (p->x - c->x); // 다음 꼭짓점으로 간다. p = c; } // 결과를 정규화해서 반환한다. result.normalize(); return result; }
C++
복사
코드 9.5. 점들의 집합에 가장 잘 맞는 평면 법선 계산하기.
가장 잘 맞는 dd값은 각 점의 dd값을 평균하여 구할 수 있습니다.
가장 잘 맞는 평면의 dd값 계산하기
d=1n∑i=1n(pi⋅n)=1n(∑i=1npi)⋅n.d=\frac1n\sum_{i=1}^{n}(\mathbf p_i\cdot\mathbf n) =\frac1n\left(\sum_{i=1}^{n}\mathbf p_i\right)\cdot\mathbf n.
💡
원문 계산식 점검 · d의 위치와 단위 법선 조건
PDF 333페이지 설명 중 ‘dd를 등호 왼쪽에 두는 것을 선호한다’는 문장은 실제 식 p⋅n=d\mathbf p\cdot\mathbf n=d 및 같은 페이지의 뒷설명과 반대입니다. 이 책의 선택은 dd를 오른쪽 에 두는 것입니다. 또한 dd가 그대로 부호 있는 거리가 되려면 ∥n∥=1\|\mathbf n\|=1이어야 합니다. 그렇지 않으면 거리는 d/∥n∥d/\|\mathbf n\|입니다.
9.5.3의 법선 누적식은 순서가 있는 다각형에 사용하는 Newell 방식입니다. 원문에서 ‘best fit’이라고 부르지만, 임의의 순서 없는 점군에 대해 직교거리 제곱합을 최소화하는 최소제곱 평면과 일반적으로 같지는 않습니다. 이 코드에는 다각형 둘레 순서로 된 입력을 넣어야 합니다. 점이 너무 적거나 면적이 0인 입력은 정규화 전에 따로 처리해야 합니다.

9.5.4 점에서 평면까지의 거리

평면과 그 위에 있지 않은 점 q\mathbf q가 주어졌을 때, 평면에서 q\mathbf q까지의 거리를 계산하거나 적어도 점이 평면의 앞쪽인지 뒤쪽인지 판별하고 싶은 경우가 많습니다. 이를 위해 평면 위에서 q\mathbf q와 가장 가까운 점 p\mathbf p를 생각하겠습니다. p\mathbf p에서 q\mathbf q로 향하는 벡터는 분명히 평면에 수직입니다. 따라서 그림 9.14처럼 ana\mathbf n 형태입니다.
그림 9.14
그림 9.14. 점과 평면 사이의 거리 계산하기.
평면 법선 n^\hat{\mathbf n}이 단위벡터라고 가정하면 p\mathbf p에서 q\mathbf q까지의 거리, 따라서 평면에서 q\mathbf q까지의 거리는 바로 aa입니다. 이는 부호 있는 거리이므로 q\mathbf q가 평면 뒤쪽에 있으면 음수가 됩니다. 놀랍게도 p\mathbf p의 위치를 몰라도 aa를 구할 수 있습니다. 처음에 q\mathbf q를 정의한 식으로 돌아가 벡터 대수로 p\mathbf p를 제거해 보겠습니다.
평면에서 임의의 3차원 점까지의 부호 있는 거리 계산하기
p+an^=q,(p+an^)⋅n^=q⋅n^,p⋅n^+(an^)⋅n^=q⋅n^,d+a=q⋅n^,a=q⋅n^−d.(9.14)\begin{aligned} \mathbf p+a\hat{\mathbf n}&=\mathbf q,\\ (\mathbf p+a\hat{\mathbf n})\cdot\hat{\mathbf n}&=\mathbf q\cdot\hat{\mathbf n},\\ \mathbf p\cdot\hat{\mathbf n}+(a\hat{\mathbf n})\cdot\hat{\mathbf n}&=\mathbf q\cdot\hat{\mathbf n},\\ d+a&=\mathbf q\cdot\hat{\mathbf n},\\ a&=\mathbf q\cdot\hat{\mathbf n}-d. \end{aligned}\tag{9.14}
💡
평면 식을 ‘부호를 내놓는 함수’로 읽기
법선이 n^=(0,1,0)\hat{\mathbf n}=(0,1,0)이고 d=2d=2이면 평면은 y=2y=2입니다. 점 q=(4,5,−3)\mathbf q=(4,5,-3)를 넣으면 q⋅n^−d=5−2=3\mathbf q\cdot\hat{\mathbf n}-d=5-2=3이므로 평면 앞쪽으로 3만큼 떨어져 있습니다. q=(4,0,−3)\mathbf q=(4,0,-3)이면 값이 −2-2이므로 뒤쪽에 있습니다.
게임에서 발이 바닥 평면 위로 얼마나 떠 있는지 확인하거나, 카메라 절두체의 한 면 바깥에 물체가 있는지 판별할 때 같은 구조를 사용합니다. 단위 법선일 때만 그 값 자체가 거리입니다. 법선이 단위 길이가 아니면 다음 식으로 나눕니다.
signedDistance⁡(q)=q⋅n−d∥n∥.\operatorname{signedDistance}(\mathbf q)=\frac{\mathbf q\cdot\mathbf n-d}{\|\mathbf n\|}.

9.6 삼각형 (Triangles)

삼각형은 모델링과 그래픽스에서 근본적으로 중요합니다. 자동차나 사람 몸처럼 복잡한 3차원 물체의 표면은 많은 삼각형으로 근사합니다. 이렇게 연결된 삼각형들의 집합이 삼각형 메시(triangle mesh) 를 이루며, 10.4절에서 이를 다룹니다. 하지만 여러 삼각형을 다루는 방법을 배우기 전에 먼저 삼각형 하나를 다루는 방법부터 알아야 합니다.
이 절에서는 삼각형의 기본 성질을 다룹니다. 9.6.1절에서는 표기법과 기본 성질을 소개합니다. 9.6.2절에서는 2차원 또는 3차원 삼각형의 넓이를 구하는 여러 방법을 제시합니다. 9.6.3절에서는 무게중심 좌표 공간을 설명합니다. 9.6.5절에서는 삼각형에서 특별한 기하학적 의미를 갖는 점들을 다룹니다.

9.6.1 표기법

삼각형은 세 꼭짓점을 나열해서 정의합니다. 이 점들을 나열하는 순서는 중요합니다. 왼손 좌표계에서는 보통 삼각형 앞면에서 바라보았을 때 시계 방향으로 점을 나열합니다. 세 꼭짓점을 v1,v2,v3\mathbf v_1,\mathbf v_2,\mathbf v_3라고 부르겠습니다.
삼각형은 하나의 평면 위에 있으며, 그 평면의 방정식, 즉 법선 n\mathbf n과 원점까지의 거리 dd는 여러 응용에서 중요합니다. 평면에 대해서는 바로 앞에서 다루었고, 세 점으로 평면 방정식을 구하는 방법은 9.5.2절에서 설명했습니다.
내각, 시계 방향의 변 벡터, 변의 길이에 그림 9.15처럼 이름을 붙이겠습니다.
그림 9.15
그림 9.15. 삼각형의 각 요소에 이름 붙이기.
lil_i를 ei\mathbf e_i의 길이라고 하겠습니다. ei\mathbf e_i와 lil_i는 같은 인덱스의 꼭짓점 vi\mathbf v_i의 맞은편에 있다는 점에 주목하겠습니다. 이들은 다음과 같이 주어집니다.
변 벡터와 길이의 표기법
e1=v3−v2,l1=∥e1∥,e2=v1−v3,l2=∥e2∥,e3=v2−v1,l3=∥e3∥.\begin{aligned} \mathbf e_1&=\mathbf v_3-\mathbf v_2,&l_1&=\|\mathbf e_1\|,\\ \mathbf e_2&=\mathbf v_1-\mathbf v_3,&l_2&=\|\mathbf e_2\|,\\ \mathbf e_3&=\mathbf v_2-\mathbf v_1,&l_3&=\|\mathbf e_3\|. \end{aligned}
예로 이 표기법을 써서 사인 법칙과 코사인 법칙을 적어 보겠습니다.
사인 법칙
sin⁡θ1l1=sin⁡θ2l2=sin⁡θ3l3.\frac{\sin\theta_1}{l_1}=\frac{\sin\theta_2}{l_2}=\frac{\sin\theta_3}{l_3}.
코사인 법칙
l12=l22+l32−2l2l3cos⁡θ1,l22=l12+l32−2l1l3cos⁡θ2,l32=l12+l22−2l1l2cos⁡θ3.\begin{aligned} l_1^2&=l_2^2+l_3^2-2l_2l_3\cos\theta_1,\\ l_2^2&=l_1^2+l_3^2-2l_1l_3\cos\theta_2,\\ l_3^2&=l_1^2+l_2^2-2l_1l_2\cos\theta_3. \end{aligned}
삼각형의 둘레도 중요한 값인 경우가 많습니다. 세 변의 길이를 더하기만 하면 쉽게 구할 수 있습니다.
삼각형의 둘레
p=l1+l2+l3.p=l_1+l_2+l_3.

9.6.2 삼각형의 넓이

이 소절에서는 삼각형의 넓이를 구하는 여러 기법을 살펴봅니다. 가장 잘 알려진 방법은 밑변과 높이로 계산하는 것입니다. 그림 9.16의 평행사변형과 그 안의 삼각형을 보겠습니다.
그림 9.16
그림 9.16. 평행사변형 안에 들어 있는 삼각형.
고전 기하학에서 배웠듯이 평행사변형의 넓이는 밑변과 높이의 곱입니다. 그 이유는 2.12.2절에 설명되어 있습니다. 삼각형은 그 넓이의 정확히 절반을 차지하므로 다음과 같습니다.
삼각형의 넓이
A=bh/2.A=bh/2.
높이를 모른다면 세 변의 길이만 필요한 헤론의 공식(Heron’s formula) 을 사용할 수 있습니다. ss를 둘레의 절반, 즉 반둘레(semiperimeter)라고 하면 넓이는 다음과 같습니다.
삼각형 넓이에 대한 헤론의 공식
s=l1+l2+l32=p2,A=s(s−l1)(s−l2)(s−l3).s=\frac{l_1+l_2+l_3}{2}=\frac p2,\qquad A=\sqrt{s(s-l_1)(s-l_2)(s-l_3)}.
헤론의 공식은 3차원에도 손쉽게 적용할 수 있다는 점이 특히 흥미롭습니다.
높이나 변의 길이를 바로 알 수 없고 꼭짓점의 데카르트 좌표만 있는 경우가 많습니다. 물론 좌표로 변의 길이를 계산하면 되지만, 비교적 비용이 큰 이 계산을 피하고 싶은 상황도 있습니다. 꼭짓점 좌표만으로 넓이를 구할 수 있을지 알아보겠습니다.
우선 2차원 문제부터 풀어 보겠습니다. 기본 아이디어는 세 변 각각에 대해, 위쪽은 해당 변으로, 아래쪽은 xx축으로 둘러싸인 사다리꼴의 부호 있는 넓이를 계산하는 것입니다(그림 9.17). ‘부호 있는 넓이’란 변이 왼쪽에서 오른쪽으로 향하면 양수, 오른쪽에서 왼쪽으로 향하면 음수라는 뜻입니다. 삼각형의 방향이 어떻든 양수인 변이 적어도 하나, 음수인 변도 적어도 하나 있다는 점에 주목하겠습니다. 수직인 변의 넓이는 0입니다.
그림 9.17
그림 9.17. 변 벡터 ‘아래’의 넓이.
각 변 아래 넓이의 공식은 다음과 같습니다.
A(e1)=(y3+y2)(x3−x2)2,A(e2)=(y1+y3)(x1−x3)2,A(e3)=(y2+y1)(x2−x1)2.A(\mathbf e_1)=\frac{(y_3+y_2)(x_3-x_2)}2,\qquad A(\mathbf e_2)=\frac{(y_1+y_3)(x_1-x_3)}2,\qquad A(\mathbf e_3)=\frac{(y_2+y_1)(x_2-x_1)}2.
세 사다리꼴의 부호 있는 넓이를 합하면 삼각형 자체의 넓이를 얻습니다. 사실 같은 방법으로 변의 개수가 얼마든지 되는 다각형의 넓이를 구할 수 있습니다.
여기서는 삼각형의 꼭짓점을 시계 방향으로 나열한다고 가정합니다. 반대 순서로 나열하면 넓이의 부호가 뒤집힙니다. 이를 염두에 두고 사다리꼴 넓이를 더하면 삼각형의 부호 있는 넓이는 다음과 같습니다.
A=A(e1)+A(e2)+A(e3)=(y3+y2)(x3−x2)+(y1+y3)(x1−x3)+(y2+y1)(x2−x1)2=(y3x3−y3x2+y2x3−y2x2)+(y1x1−y1x3+y3x1−y3x3)+(y2x2−y2x1+y1x2−y1x1)2=−y3x2+y2x3−y1x3+y3x1−y2x1+y1x22=y1(x2−x3)+y2(x3−x1)+y3(x1−x2)2.\begin{aligned} A&=A(\mathbf e_1)+A(\mathbf e_2)+A(\mathbf e_3)\\ &=\frac{(y_3+y_2)(x_3-x_2)+(y_1+y_3)(x_1-x_3)+(y_2+y_1)(x_2-x_1)}2\\ &=\frac{\begin{aligned}&(y_3x_3-y_3x_2+y_2x_3-y_2x_2)\\&+(y_1x_1-y_1x_3+y_3x_1-y_3x_3)\\&+(y_2x_2-y_2x_1+y_1x_2-y_1x_1)\end{aligned}}2\\ &=\frac{-y_3x_2+y_2x_3-y_1x_3+y_3x_1-y_2x_1+y_1x_2}2\\ &=\frac{y_1(x_2-x_3)+y_2(x_3-x_1)+y_3(x_1-x_2)}2. \end{aligned}
이를 조금 더 단순하게 만들 수도 있습니다. 삼각형을 평행이동해도 넓이는 변하지 않는다는 사실을 이용합니다. 임의로 세로 방향 이동을 선택해서 모든 yy좌표에서 y3y_3를 빼 보겠습니다. 삼각형 일부가 xx축 아래로 내려가도 사다리꼴 합산 방법이 통하는지 궁금했다면, 이 이동 성질이 그렇다는 사실을 제대로 보여줍니다.
꼭짓점 좌표로 2차원 삼각형의 넓이 계산하기
A=y1(x2−x3)+y2(x3−x1)+y3(x1−x2)2=(y1−y3)(x2−x3)+(y2−y3)(x3−x1)+(y3−y3)(x1−x2)2=(y1−y3)(x2−x3)+(y2−y3)(x3−x1)2.(9.15)\begin{aligned} A&=\frac{y_1(x_2-x_3)+y_2(x_3-x_1)+y_3(x_1-x_2)}2\\ &=\frac{(y_1-y_3)(x_2-x_3)+(y_2-y_3)(x_3-x_1)+(y_3-y_3)(x_1-x_2)}2\\ &=\frac{(y_1-y_3)(x_2-x_3)+(y_2-y_3)(x_3-x_1)}2. \end{aligned}\tag{9.15}
3차원에서는 외적으로 삼각형의 넓이를 계산할 수 있습니다. 2.12.2절에서 두 벡터 a\mathbf a와 b\mathbf b의 외적 크기는 두 벡터를 두 변으로 삼는 평행사변형의 넓이와 같다고 배웠습니다. 삼각형의 넓이는 그것을 감싸는 평행사변형 넓이의 절반이므로 간단한 계산 방법을 얻습니다. 삼각형의 두 변 벡터 e1\mathbf e_1과 e2\mathbf e_2가 주어지면 넓이는 다음과 같습니다.
A=∥e1×e2∥2.(9.16)A=\frac{\|\mathbf e_1\times\mathbf e_2\|}{2}.\tag{9.16}
2차원 삼각형에 z=0z=0을 가정해 3차원으로 확장하면 식 (9.15)와 식 (9.16)이 동등하다는 점에 주목하겠습니다.
💡
원문 계산식 점검 · 부호 있는 넓이와 보통의 넓이
식 (9.15)은 꼭짓점 순서에 따라 부호가 달라지는 넓이이고, 외적의 크기 를 쓰는 식 (9.16)은 음수가 아닌 넓이입니다. 두 식이 같다는 본문 설명은 가정한 시계 방향에서 해석해야 합니다. 순서를 뒤집어도 비교하려면 식 (9.15)의 절댓값을 취해야 합니다.

9.6.3 무게중심 좌표 공간

우리는 분명 삼각형을 3차원에서 사용하지만, 삼각형의 표면은 한 평면에 놓이며 본질적으로 2차원 도형입니다. 3차원에서 임의의 방향으로 놓인 삼각형의 표면 위를 움직이기는 다소 번거롭습니다. 삼각형 표면과 연관되면서도 삼각형이 ‘살고 있는’ 3차원 공간과는 독립적인 좌표계가 있으면 좋겠습니다.
무게중심 좌표 공간(barycentric space) 이 바로 그런 좌표계입니다. 보간과 교차처럼 비디오 게임을 만들 때 생기는 많은 실용적인 문제를 무게중심 좌표로 해결할 수 있습니다. 여기서는 삼각형을 배경으로 소개하지만 적용 범위는 넓습니다. 실제로 13장의 3차원 곡선에서는 조금 더 일반적인 형태로 다시 만나게 됩니다.
삼각형이 놓인 평면의 모든 점은 꼭짓점들의 가중평균으로 표현할 수 있습니다. 이 가중치들을 무게중심 좌표(barycentric coordinates) 라고 부릅니다. 무게중심 좌표 (b1,b2,b3)(b_1,b_2,b_3)를 표준 3차원 공간으로 바꾸는 변환은 다음과 같이 정의합니다.
무게중심 좌표로부터 3차원 점 계산하기
(b1,b2,b3)≡b1v1+b2v2+b3v3.(9.17)(b_1,b_2,b_3)\equiv b_1\mathbf v_1+b_2\mathbf v_2+b_3\mathbf v_3.\tag{9.17}
물론 이는 벡터 몇 개의 선형 결합일 뿐입니다. 3.3.3절에서는 일반적인 데카르트 좌표도 기저벡터의 선형 결합으로 해석할 수 있음을 보였습니다. 하지만 무게중심 좌표와 일반적인 데카르트 좌표의 미묘한 차이는, 무게중심 좌표에서는 좌표의 합이 1이어야 한다는 제약입니다.
b1+b2+b3=1.b_1+b_2+b_3=1.
이 정규화 제약이 자유도 하나를 없앱니다. 따라서 좌표는 세 개지만 여전히 2차원 공간입니다.
b1,b2,b3b_1,b_2,b_3는 각 꼭짓점이 그 점에 기여하는 ‘기여도’ 또는 ‘가중치’입니다. 그림 9.18은 몇 가지 점과 그 무게중심 좌표의 예를 보여줍니다.
그림 9.18
그림 9.18. 무게중심 좌표의 예.
여기서 몇 가지를 관찰해 보겠습니다. 첫째, 삼각형의 세 꼭짓점은 무게중심 공간에서 아주 간단한 형태를 갖습니다.
(1,0,0)≡v1,(0,1,0)≡v2,(0,0,1)≡v3.(1,0,0)\equiv\mathbf v_1,\qquad (0,1,0)\equiv\mathbf v_2,\qquad (0,0,1)\equiv\mathbf v_3.
둘째, 어떤 꼭짓점의 맞은편 변에 놓인 모든 점은 그 꼭짓점에 대응하는 무게중심 좌표가 0입니다. 예를 들어 v1\mathbf v_1의 맞은편 변 e1\mathbf e_1을 포함하는 직선 위의 모든 점은 b1=0b_1=0입니다.
마지막으로, 삼각형 안의 점뿐 아니라 평면 위 모든 점을 무게중심 좌표로 나타낼 수 있습니다. 삼각형 안 점의 무게중심 좌표는 모두 [0,1][0,1] 범위에 있습니다. 바깥 점은 적어도 하나의 좌표가 음수입니다. 그림 9.19처럼 무게중심 좌표 공간은 원래 삼각형과 같은 크기의 삼각형들로 평면을 빈틈없이 나눕니다.
그림 9.19
그림 9.19. 무게중심 좌표는 평면을 삼각형들로 분할합니다.
무게중심 좌표를 생각하는 또 다른 방법도 있습니다. b3b_3를 버리면 (b1,b2)(b_1,b_2)를 보통의 2차원 (x,y)(x,y)좌표로 해석할 수 있습니다. 원점은 v3\mathbf v_3, xx축은 v1−v3\mathbf v_1-\mathbf v_3이고, 원문은 yy축을 v1−v2\mathbf v_1-\mathbf v_2라고 설명합니다. 식 (9.17)을 다시 정리하면 더 분명히 볼 수 있습니다.
(b1,b2)(b_1,b_2)를 보통의 2차원 좌표로 해석하기
(b1,b2,b3)≡b1v1+b2v2+b3v3≡b1v1+b2v2+(1−b1−b2)v3≡b1v1+b2v2+v3−b1v3−b2v3≡v3+b1(v1−v3)+b2(v2−v3).\begin{aligned} (b_1,b_2,b_3)&\equiv b_1\mathbf v_1+b_2\mathbf v_2+b_3\mathbf v_3\\ &\equiv b_1\mathbf v_1+b_2\mathbf v_2+(1-b_1-b_2)\mathbf v_3\\ &\equiv b_1\mathbf v_1+b_2\mathbf v_2+\mathbf v_3-b_1\mathbf v_3-b_2\mathbf v_3\\ &\equiv\mathbf v_3+b_1(\mathbf v_1-\mathbf v_3)+b_2(\mathbf v_2-\mathbf v_3). \end{aligned}
이 식을 보면 정규화 제약 때문에 좌표가 세 개여도 자유도는 두 개뿐이라는 사실이 매우 분명합니다. 무게중심 공간의 점을 좌표 두 개만으로 완전히 설명할 수 있는 것입니다. 실제로 이 좌표들이 기술하는 공간의 랭크는 ‘표본점’ 자체의 차원 수가 아니라 표본점의 개수에 달려 있습니다.
좌표의 합이 1이라는 제약 때문에 자유도의 수는 무게중심 좌표의 수보다 하나 적습니다. 예를 들어 표본점이 두 개라면 무게중심 좌표의 차원은 2이고, 이 좌표로 기술하는 공간은 1차원 공간인 직선입니다. 이 직선은 1차원의 직선, 즉 스칼라 보간일 수도 있고, 2차원이나 3차원 또는 더 높은 차원 공간 속의 직선일 수도 있습니다.
이 절에서는 표본점 세 개, 즉 삼각형의 세 꼭짓점과 무게중심 좌표 세 개가 있었으므로 2차원 공간인 평면이 나옵니다. 3차원 표본점 네 개가 있다면 무게중심 좌표로 3차원 점의 위치를 정할 수 있습니다. 무게중심 좌표가 네 개이면 세 개일 때의 ‘삼각형’ 공간 대신 ‘사면체’ 공간이 만들어집니다.
무게중심 좌표를 표준 데카르트 좌표로 바꾸려면 식 (9.17)을 적용해 꼭짓점의 가중평균을 계산하면 됩니다. 반대 방향, 즉 데카르트 좌표에서 무게중심 좌표를 계산하는 변환은 조금 더 어렵고 9.6.4절에서 다룹니다. 하지만 가볍게 읽는 독자라면 건너뛸 수도 있는 세부 계산에 깊이 들어가기 전에, 이제 기본 개념을 알았으니 무게중심 좌표가 유용한 곳을 몇 가지 짚고 넘어가겠습니다.
그래픽스에서는 텍스처 좌표, 색상, 표면 법선, 조명값 등의 매개변수를 꼭짓점마다 편집하거나 계산하는 일이 흔합니다. 그런 다음 삼각형 안의 임의의 위치에서 그 매개변수의 보간값이 필요할 때가 많습니다. 무게중심 좌표를 사용하면 이 작업이 쉽습니다. 먼저 관심 있는 내부 점의 무게중심 좌표를 구하고, 그 좌표를 가중치로 사용해 각 꼭짓점에 저장된 매개변수 값을 가중평균하면 됩니다.
또 다른 중요한 예는 교차 검사입니다. 레이와 삼각형의 교차를 검사하는 간단한 방법 하나는 레이가 삼각형을 포함하는 무한 평면과 만나는 점을 구한 다음, 그 점이 삼각형 안에 있는지 판단하는 것입니다. 여기서 설명한 기법으로 점의 무게중심 좌표를 구하면 쉽게 판단할 수 있습니다.
모든 좌표가 [0,1][0,1] 범위에 있으면 점은 삼각형 안에 있습니다. 그렇지 않으면 적어도 하나가 범위를 벗어나며 점은 삼각형 바깥에 있습니다. 계산한 무게중심 좌표를 계속 사용해 보간된 표면 속성을 얻는 일도 흔합니다. 예를 들어 어떤 지점에서 광원이 보이는지, 아니면 그림자 속에 있는지 알아내려고 레이를 쏜다고 하겠습니다.
그 레이가 모델의 삼각형 위 임의의 위치에 맞았습니다. 모델이 불투명하다면 광원은 보이지 않습니다. 하지만 모델이 투명도를 사용한다면 빛이 얼마나 차단되는지 판단하기 위해 해당 위치의 불투명도를 알아야 할 수 있습니다. 이 투명도는 대개 UV 좌표로 접근하는 텍스처 맵에 들어 있습니다.
텍스처 매핑은 10.5절에서 더 자세히 다룹니다. 교차 위치의 투명도를 가져오려면 그 점의 무게중심 좌표로 꼭짓점들의 UV를 보간합니다. 그런 다음 그 UV로 텍스처 맵의 텍셀을 가져와 표면의 해당 위치가 얼마나 투명한지 알아냅니다.
💡
무게중심 좌표를 색 섞는 비율로 생각하기
삼각형의 꼭짓점 색이 빨강, 초록, 파랑이고 내부 점의 무게중심 좌표가 (0.2,0.3,0.5)(0.2,0.3,0.5)라면, 그 점의 색은 빨강 20%, 초록 30%, 파랑 50%의 합입니다. 좌표 합이 1이므로 전체 비율이 100%가 됩니다. 같은 가중치를 UV, 높이, 조명값에도 적용할 수 있습니다.
위치 예로 v1=(0,0),v2=(6,0),v3=(0,4)\mathbf v_1=(0,0),\mathbf v_2=(6,0),\mathbf v_3=(0,4)라면 다음과 같습니다.
p=0.2(0,0)+0.3(6,0)+0.5(0,4)=(1.8,2).\mathbf p=0.2(0,0)+0.3(6,0)+0.5(0,4)=(1.8,2).
(−0.2,0.7,0.5)(-0.2,0.7,0.5)도 합이 1이므로 같은 평면의 점을 나타냅니다. 하지만 음수 좌표가 있으므로 삼각형 밖입니다. 따라서 ‘합이 1인지’와 ‘각 값이 0 이상인지’는 서로 다른 검사입니다. 부동소수점으로 경계를 검사할 때는 허용 오차의 크기를 장면 단위와 계산 경로에 맞추어 정해야 합니다.
추가 설명 도해
추가 도해. 삼각형 꼭짓점의 색과 내부 점의 세 가중치를 함께 표시합니다. 부분 삼각형의 넓이 비가 해당 꼭짓점의 가중치라는 본문 설명에 연결됩니다.
💡
원문 계산식 점검 · 두 번째 좌표축과 독립성
PDF 343페이지 설명의 두 번째 축 v1−v2\mathbf v_1-\mathbf v_2는 바로 아래 유도식과 맞지 않습니다. 원점을 v3\mathbf v_3에 두면 올바른 두 축은 v1−v3\mathbf v_1-\mathbf v_3와 v2−v3\mathbf v_2-\mathbf v_3입니다.
‘표본점 수에서 1을 뺀 값이 공간 차원’이라는 설명에는 표본점들이 아핀 독립이라는 조건이 필요합니다. 예를 들어 세 점이 한 직선 위에 있으면 평면이 아니라 직선만 만들고, 3차원의 네 점이 같은 평면 위에 있으면 3차원 공간 전체를 만들지 못합니다.

9.6.4 무게중심 좌표 계산하기

이제 데카르트 좌표에서 무게중심 좌표를 구하는 방법을 알아보겠습니다. 그림 9.20의 2차원 상황부터 시작합니다. 세 꼭짓점 v1,v2,v3\mathbf v_1,\mathbf v_2,\mathbf v_3와 점 p\mathbf p가 있고, 각 꼭짓점의 맞은편에 있는 세 ‘부분 삼각형’ T1,T2,T3T_1,T_2,T_3에도 이름을 붙였습니다. 이들은 곧 유용하게 쓰입니다.
그림 9.20
그림 9.20. 임의의 점 p\mathbf p의 무게중심 좌표 계산하기.
세 꼭짓점과 점 p\mathbf p의 데카르트 좌표는 알고 있습니다. 구할 것은 무게중심 좌표 b1,b2,b3b_1,b_2,b_3입니다. 따라서 미지수 세 개에 대해 방정식 세 개를 얻습니다.
b1x1+b2x2+b3x3=px,b1y1+b2y2+b3y3=py,b1+b2+b3=1.\begin{aligned} b_1x_1+b_2x_2+b_3x_3&=p_x,\\ b_1y_1+b_2y_2+b_3y_3&=p_y,\\ b_1+b_2+b_3&=1. \end{aligned}
이 연립방정식을 풀면 다음 결과가 나옵니다.
2차원 점의 무게중심 좌표 계산하기
b1=(py−y3)(x2−x3)+(y2−y3)(x3−px)(y1−y3)(x2−x3)+(y2−y3)(x3−x1),b2=(py−y1)(x3−x1)+(y3−y1)(x1−px)(y1−y3)(x2−x3)+(y2−y3)(x3−x1),b3=(py−y2)(x1−x2)+(y1−y2)(x2−px)(y1−y3)(x2−x3)+(y2−y3)(x3−x1).(9.18)\begin{aligned} b_1&=\frac{(p_y-y_3)(x_2-x_3)+(y_2-y_3)(x_3-p_x)}{(y_1-y_3)(x_2-x_3)+(y_2-y_3)(x_3-x_1)},\\ b_2&=\frac{(p_y-y_1)(x_3-x_1)+(y_3-y_1)(x_1-p_x)}{(y_1-y_3)(x_2-x_3)+(y_2-y_3)(x_3-x_1)},\\ b_3&=\frac{(p_y-y_2)(x_1-x_2)+(y_1-y_2)(x_2-p_x)}{(y_1-y_3)(x_2-x_3)+(y_2-y_3)(x_3-x_1)}. \end{aligned}\tag{9.18}
식 (9.18)을 자세히 보면 세 식의 분모가 모두 같습니다. 식 (9.15)에 따르면 삼각형 넓이의 두 배입니다. 게다가 각 무게중심 좌표 bib_i의 분자는 ‘부분 삼각형’ TiT_i 넓이의 두 배입니다. 즉 다음과 같습니다.
무게중심 좌표를 넓이의 비로 해석하기
b1=A(T1)/A(T),b2=A(T2)/A(T),b3=A(T3)/A(T).b_1=A(T_1)/A(T),\qquad b_2=A(T_2)/A(T),\qquad b_3=A(T_3)/A(T).
p\mathbf p가 삼각형 밖에 있어도 이 해석은 적용됩니다. 넓이 계산식은 꼭짓점이 반시계 방향으로 나열되면 음수를 내놓기 때문입니다. 세 꼭짓점이 한 직선 위에 있으면 삼각형이 퇴화(degenerate)하여 분모의 넓이가 0이 되므로 무게중심 좌표를 구할 수 없습니다.
3차원의 임의의 점 p\mathbf p에 대한 무게중심 좌표 계산은 2차원보다 복잡합니다. 이번에는 미지수가 세 개인데 방정식은 네 개입니다. p\mathbf p의 각 좌표마다 하나씩, 그리고 무게중심 좌표의 정규화 제약이 하나 더 있습니다. 따라서 앞에서처럼 연립방정식을 풀 수는 없습니다.
또 하나의 어려움은 p\mathbf p가 삼각형을 포함하는 평면 위에 있지 않을 수도 있다는 것입니다. 그러면 무게중심 좌표는 정의되지 않습니다. 우선은 p\mathbf p가 그 평면 위에 있다고 가정하겠습니다.
잘 통하는 요령 하나는 x,y,zx,y,z 중 하나를 버려 3차원 문제를 2차원 문제로 바꾸는 것입니다. 이는 삼각형을 세 좌표평면 중 하나로 투영하는 효과가 있습니다. 직관적으로 말하면 투영한 넓이가 원래 넓이에 비례하기 때문에 가능합니다.
그러면 어느 좌표를 버려야 할까요? 항상 같은 좌표를 버리면 안 됩니다. 삼각형이 투영 평면에 수직일 경우 투영된 점들이 한 직선 위에 놓이기 때문입니다. 거의 수직이면 부동소수점 정확도 문제가 생깁니다. 해결책은 투영된 삼각형의 넓이가 최대가 되도록 투영 평면을 선택하는 것입니다.
평면 법선을 살펴보고 절댓값이 가장 큰 성분의 좌표를 버리면 됩니다. 예를 들어 법선이 [0.267,−0.802,0.535][0.267,-0.802,0.535]라면 꼭짓점들과 p\mathbf p의 yy값을 버려 xzxz평면에 투영합니다. 코드 9.6은 임의의 3차원 점의 무게중심 좌표를 계산하는 방법을 보여줍니다.
bool computeBarycentricCoords3d( const Vector3 v[3], // 삼각형의 꼭짓점 const Vector3 &p, // 좌표를 구하려는 점 float b[3] // 계산한 무게중심 좌표를 여기에 반환 ) { // 먼저 시계 방향의 변 벡터 두 개를 구한다. Vector3 d1 = v[1] - v[0]; Vector3 d2 = v[2] - v[1]; // 외적으로 표면 법선을 계산한다. 표면 법선을 미리 계산한 // 경우가 많으므로 그때는 이 단계를 생략할 수 있다. // 정규화할 필요는 없지만, 미리 계산한 법선이 // 정규화되어 있어도 괜찮다. Vector3 n = crossProduct(d1, d2); // 법선의 가장 큰 성분을 찾아 투영 평면을 선택한다. float u1, u2, u3, u4; float v1, v2, v3, v4; if ((fabs(n.x) >= fabs(n.y)) && (fabs(n.x) >= fabs(n.z))) { // x를 버리고 yz 평면에 투영한다. u1 = v[0].y - v[2].y; u2 = v[1].y - v[2].y; u3 = p.y - v[0].y; u4 = p.y - v[2].y; v1 = v[0].z - v[2].z; v2 = v[1].z - v[2].z; v3 = p.z - v[0].z; v4 = p.z - v[2].z; } else if (fabs(n.y) >= fabs(n.z)) { // y를 버리고 xz 평면에 투영한다. u1 = v[0].z - v[2].z; u2 = v[1].z - v[2].z; u3 = p.z - v[0].z; u4 = p.z - v[2].z; v1 = v[0].x - v[2].x; v2 = v[1].x - v[2].x; v3 = p.x - v[0].x; v4 = p.x - v[2].x; } else { // z를 버리고 xy 평면에 투영한다. u1 = v[0].x - v[2].x; u2 = v[1].x - v[2].x; u3 = p.x - v[0].x; u4 = p.x - v[2].x; v1 = v[0].y - v[2].y; v2 = v[1].y - v[2].y; v3 = p.y - v[0].y; v4 = p.y - v[2].y; } // 분모를 계산하고 유효한지 확인한다. float denom = v1 * u2 - v2 * u1; if (denom == 0.0f) { // 잘못된 삼각형이다. 아마 넓이가 0일 것이다. return false; } // 무게중심 좌표를 계산한다. float oneOverDenom = 1.0f / denom; b[0] = (v4 * u2 - v2 * u4) * oneOverDenom; b[1] = (v1 * u3 - v3 * u1) * oneOverDenom; b[2] = 1.0f - b[0] - b[1]; // 성공 return true; }
C++
복사
코드 9.6. 3차원에서 무게중심 좌표 계산하기.
3차원 무게중심 좌표를 계산하는 또 다른 기법은 9.6.2절에서 설명한 외적을 이용한 삼각형 넓이 계산에 기반합니다. 삼각형의 두 변 벡터 e1,e2\mathbf e_1,\mathbf e_2가 주어지면 넓이를 ∥e1×e2∥/2\|\mathbf e_1\times\mathbf e_2\|/2로 구할 수 있었습니다. 전체 삼각형과 세 부분 삼각형의 넓이를 알면 무게중심 좌표도 계산할 수 있습니다.
다만 작은 문제가 하나 있습니다. 외적의 크기는 꼭짓점 순서에 민감하지 않습니다. 크기는 정의상 언제나 0 이상입니다. 삼각형 밖의 점에는 적어도 하나의 음수 무게중심 좌표가 필요하므로 이대로는 사용할 수 없습니다. 이 문제를 피할 방법을 찾아보겠습니다. 실제로 필요한 것은 꼭짓점이 ‘잘못된’ 순서로 나열되었을 때 음수가 나오도록 외적 벡터의 길이를 계산하는 방법인 것 같습니다. 알고 보면 내적을 사용해 아주 간단히 할 수 있습니다.
삼각형의 두 변 벡터의 외적을 c\mathbf c라고 하겠습니다. c\mathbf c의 크기는 삼각형 넓이의 두 배입니다. 단위 길이의 법선 n^\hat{\mathbf n}이 있다고 가정하겠습니다. n^\hat{\mathbf n}과 c\mathbf c는 모두 삼각형을 포함하는 평면에 수직이므로 서로 평행합니다.
다만 방향은 반대일 수 있습니다. 2.11.2절에서 두 벡터의 내적은 두 크기의 곱에 사이각의 코사인을 곱한 값이라고 배웠습니다. n^\hat{\mathbf n}은 단위벡터이고 두 벡터는 정확히 같은 방향 또는 정반대 방향을 향하므로 다음과 같습니다.
c⋅n^=∥c∥ ∥n^∥cos⁡θ=∥c∥(1)(±1)=±∥c∥.\begin{aligned} \mathbf c\cdot\hat{\mathbf n}&=\|\mathbf c\|\,\|\hat{\mathbf n}\|\cos\theta\\ &=\|\mathbf c\|(1)(\pm1)\\ &=\pm\|\mathbf c\|. \end{aligned}
이 결과를 2로 나누면 3차원 삼각형의 ‘부호 있는 넓이’를 구할 수 있습니다. 이 요령을 갖췄으니 각 무게중심 좌표 bib_i가 부분 삼각형 TiT_i의 넓이에 비례한다는 앞의 관찰을 적용할 수 있습니다. 먼저 관련된 모든 벡터에 그림 9.21처럼 이름을 붙이겠습니다.
그림 9.21
그림 9.21. 3차원에서 무게중심 좌표 계산하기.
그림 9.21처럼 각 꼭짓점 vi\mathbf v_i에서 p\mathbf p로 향하는 벡터를 di\mathbf d_i라고 합니다. 벡터들의 식을 정리하면 다음과 같습니다.
e1=v3−v2,d1=p−v1,e2=v1−v3,d2=p−v2,e3=v2−v1,d3=p−v3.\begin{aligned} \mathbf e_1&=\mathbf v_3-\mathbf v_2,&\mathbf d_1&=\mathbf p-\mathbf v_1,\\ \mathbf e_2&=\mathbf v_1-\mathbf v_3,&\mathbf d_2&=\mathbf p-\mathbf v_2,\\ \mathbf e_3&=\mathbf v_2-\mathbf v_1,&\mathbf d_3&=\mathbf p-\mathbf v_3. \end{aligned}
표면 법선도 필요하며, 다음처럼 구할 수 있습니다.
n^=e1×e2∥e1×e2∥.\hat{\mathbf n}=\frac{\mathbf e_1\times\mathbf e_2}{\|\mathbf e_1\times\mathbf e_2\|}.
이제 전체 삼각형을 간단히 TT라고 부르면, 전체 삼각형과 세 부분 삼각형의 넓이는 다음과 같습니다.
A(T)=((e1×e2)⋅n^)/2,A(T1)=((e1×d3)⋅n^)/2,A(T2)=((e2×d1)⋅n^)/2,A(T3)=((e3×d2)⋅n^)/2.\begin{aligned} A(T)&=((\mathbf e_1\times\mathbf e_2)\cdot\hat{\mathbf n})/2,\\ A(T_1)&=((\mathbf e_1\times\mathbf d_3)\cdot\hat{\mathbf n})/2,\\ A(T_2)&=((\mathbf e_2\times\mathbf d_1)\cdot\hat{\mathbf n})/2,\\ A(T_3)&=((\mathbf e_3\times\mathbf d_2)\cdot\hat{\mathbf n})/2. \end{aligned}
각 무게중심 좌표 bib_i는 A(Ti)/A(T)A(T_i)/A(T)입니다.
3차원에서 무게중심 좌표 계산하기
b1=A(T1)A(T)=(e1×d3)⋅n^(e1×e2)⋅n^,b2=A(T2)A(T)=(e2×d1)⋅n^(e1×e2)⋅n^,b3=A(T3)A(T)=(e3×d2)⋅n^(e1×e2)⋅n^.\begin{aligned} b_1&=\frac{A(T_1)}{A(T)}=\frac{(\mathbf e_1\times\mathbf d_3)\cdot\hat{\mathbf n}}{(\mathbf e_1\times\mathbf e_2)\cdot\hat{\mathbf n}},\\ b_2&=\frac{A(T_2)}{A(T)}=\frac{(\mathbf e_2\times\mathbf d_1)\cdot\hat{\mathbf n}}{(\mathbf e_1\times\mathbf e_2)\cdot\hat{\mathbf n}},\\ b_3&=\frac{A(T_3)}{A(T)}=\frac{(\mathbf e_3\times\mathbf d_2)\cdot\hat{\mathbf n}}{(\mathbf e_1\times\mathbf e_2)\cdot\hat{\mathbf n}}. \end{aligned}
n^\hat{\mathbf n}이 모든 분자와 분모에 쓰이므로 반드시 단위벡터일 필요는 없다는 점에 주목하겠습니다.
이 기법은 2차원으로 투영하는 방법보다 스칼라 연산을 더 많이 수행합니다. 하지만 분기가 없으며 SIMD 최적화에 더 유리합니다.
💡
원문 계산식 점검 · 방정식 수가 더 많다고 항상 풀 수 없는 것은 아니다
3차원 위치 세 성분과 정규화 제약을 합쳐 방정식이 네 개가 되어도, 점이 삼각형 평면에 정확히 놓이고 삼각형이 퇴화하지 않았다면 독립 방정식만 골라 일관되게 풀 수 있습니다. 본문에서 ‘앞에서처럼 풀 수 없다’는 설명은 2차원 식을 그대로 적용할 수 없다는 취지로 읽어야 합니다. 코드 9.6은 평면 위의 점이라는 전제에서 사용하며, 반환값 true만으로 원래 3차원 점이 삼각형 평면 위에 있다는 사실까지 검증하지는 않습니다.

9.6.5 특별한 점들

이 소절에서는 삼각형에서 특별한 기하학적 의미를 갖는 세 점을 다룹니다.
•
무게중심(center of gravity)
•
내심(incenter)
•
외심(circumcenter)
이 고전적인 계산을 소개하기 위해 『Graphics Gems』에 실린 Goldman의 글 [25]을 따릅니다. 각 점의 기하학적 의미와 작도 방법을 설명하고 무게중심 좌표를 제시합니다.
무게중심 은 삼각형을 그 점에서 받치면 완벽하게 균형을 이루는 점입니다. 중선들의 교점이기도 합니다. 중선(median)은 한 꼭짓점과 맞은편 변의 중점을 잇는 선입니다. 그림 9.22는 삼각형의 무게중심을 보여줍니다.
그림 9.22
그림 9.22. 삼각형의 무게중심.
무게중심은 세 꼭짓점 위치 벡터의 산술평균입니다.
cGrav=v1+v2+v33.\mathbf c_{\mathrm{Grav}}=\frac{\mathbf v_1+\mathbf v_2+\mathbf v_3}{3}.
무게중심 좌표는 다음과 같습니다.
(13,13,13).\left(\frac13,\frac13,\frac13\right).
무게중심은 도심(centroid) 이라고도 합니다.
내심 은 삼각형 안에서 세 변까지의 거리가 같은 점입니다. 삼각형에 내접하는 원의 중심이라서 내심이라고 부릅니다. 그림 9.23처럼 각의 이등분선들의 교점으로 작도합니다.
그림 9.23
그림 9.23. 삼각형의 내심.
내심은 다음 식으로 계산합니다.
cIn=l1v1+l2v2+l3v3p.\mathbf c_{\mathrm{In}}=\frac{l_1\mathbf v_1+l_2\mathbf v_2+l_3\mathbf v_3}{p}.
여기서 p=l1+l2+l3p=l_1+l_2+l_3는 삼각형의 둘레입니다. 따라서 내심의 무게중심 좌표는 다음과 같습니다.
(l1p,l2p,l3p).\left(\frac{l_1}{p},\frac{l_2}{p},\frac{l_3}{p}\right).
원문에서는 내접원의 반지름을 삼각형 넓이를 둘레로 나누어 구한다고 쓰고 다음 식을 제시합니다.
rIn=Ap.r_{\mathrm{In}}=\frac Ap.
내접원은 세 직선에 접하는 원을 찾는 문제의 해답입니다.
외심 은 세 꼭짓점에서 같은 거리에 있는 점입니다. 원문은 이를 삼각형 안의 점이라고 설명합니다. 삼각형에 외접하는 원의 중심이며, 각 변의 수직이등분선들의 교점으로 작도합니다. 그림 9.24는 삼각형의 외심을 보여줍니다.
그림 9.24
그림 9.24. 삼각형의 외심.
외심을 계산하려면 먼저 다음 중간값들을 정의합니다.
d1=−e2⋅e3,c1=d2d3,d2=−e3⋅e1,c2=d3d1,d3=−e1⋅e2,c3=d1d2,c=c1+c2+c3.\begin{aligned} d_1&=-\mathbf e_2\cdot\mathbf e_3,&c_1&=d_2d_3,\\ d_2&=-\mathbf e_3\cdot\mathbf e_1,&c_2&=d_3d_1,\\ d_3&=-\mathbf e_1\cdot\mathbf e_2,&c_3&=d_1d_2,\\ &&c&=c_1+c_2+c_3. \end{aligned}
이 중간값을 쓰면 외심의 무게중심 좌표는 다음과 같습니다.
(c2+c32c,c3+c12c,c1+c22c).\left(\frac{c_2+c_3}{2c},\frac{c_3+c_1}{2c},\frac{c_1+c_2}{2c}\right).
따라서 외심은 다음 식으로 주어집니다.
cCirc=(c2+c3)v1+(c3+c1)v2+(c1+c2)v32c.\mathbf c_{\mathrm{Circ}}=\frac{(c_2+c_3)\mathbf v_1+(c_3+c_1)\mathbf v_2+(c_1+c_2)\mathbf v_3}{2c}.
외접원의 반지름은 다음과 같습니다.
rCirc=(d1+d2)(d2+d3)(d3+d1)/c2.r_{\mathrm{Circ}}=\frac{\sqrt{(d_1+d_2)(d_2+d_3)(d_3+d_1)/c}}2.
외접원의 반지름과 외심은 세 점을 지나는 원을 찾는 문제를 해결합니다.
💡
원문 계산식 점검 · 내접원 반지름과 외심 위치
PDF 352페이지의 내접반지름 rIn=A/pr_{\mathrm{In}}=A/p에는 2가 빠져 있습니다. pp가 둘레이고 s=p/2s=p/2가 반둘레이므로 올바른 식은 다음과 같습니다.
rIn=2Ap=As.r_{\mathrm{In}}=\frac{2A}{p}=\frac As.
이유는 내심에서 세 변으로 수선을 내려 나눈 세 삼각형의 넓이를 합하면 A=12r(l1+l2+l3)=rp/2A=\tfrac12r(l_1+l_2+l_3)=rp/2이기 때문입니다. 변 길이 3,4,5인 직각삼각형은 넓이 6, 둘레 12이므로 내접반지름은 1입니다.
외심이 ‘삼각형 안’에 있다는 문장도 예각삼각형에만 해당합니다. 직각삼각형의 외심은 빗변의 중점이고, 둔각삼각형의 외심은 삼각형 밖에 있습니다. 모든 경우에 세 꼭짓점까지의 거리가 같다는 정의는 유지됩니다.

9.7 다각형 (Polygons)

이 절에서는 다각형을 소개하고, 다각형을 다룰 때 생기는 중요한 문제 몇 가지를 설명합니다. 다각형의 정확한 정의는 문맥에 따라 달라지는 경우가 많아 간단히 정의하기 어렵습니다. 일반적으로 다각형은 꼭짓점과 변으로 이루어진 평평한 도형입니다. 이어지는 소절에서는 다각형을 분류하는 여러 방법을 살펴봅니다.
9.7.1절에서는 단순 다각형과 복합 다각형의 차이를 설명하고 자기 교차 다각형도 언급합니다. 9.7.2절에서는 볼록 다각형과 오목 다각형의 차이를 다룹니다. 9.7.3절에서는 어떤 다각형이든 연결된 삼각형들로 바꿀 수 있음을 설명합니다.

9.7.1 단순 다각형과 복합 다각형

단순 다각형(simple polygon) 에는 ‘구멍’이 없지만, 복합 다각형(complex polygon) 에는 구멍이 있을 수 있습니다(그림 9.25). 단순 다각형은 둘레를 따라 꼭짓점을 순서대로 나열하면 기술할 수 있습니다. 왼손 좌표계에서는 보통 다각형 ‘앞면’에서 보았을 때 시계 방향으로 나열한다는 점을 기억하겠습니다. 단순 다각형은 복합 다각형보다 훨씬 자주 사용됩니다.
그림 9.25
그림 9.25. 단순 다각형과 복합 다각형.
그림 9.26처럼 ‘이음매(seam)’ 변을 한 쌍씩 추가하면 어떤 복합 다각형이든 단순 다각형으로 바꿀 수 있습니다. 오른쪽 확대 그림에서 보듯이 이음매마다 변 두 개를 추가합니다. 실제로는 두 변이 겹치지만, 확대 그림에서는 보이도록 떨어뜨려 놓았습니다. 다각형 둘레를 따라 변에 순서를 부여한다고 생각하면, 이음매를 이루는 두 변은 서로 반대 방향을 향합니다.
그림 9.26
그림 9.26. 이음매 변을 한 쌍씩 추가해 복합 다각형을 단순 다각형으로 바꾸기.
대부분의 단순 다각형에서는 변끼리 교차하지 않습니다. 변들이 교차한다면 자기 교차 다각형(self-intersecting polygon) 으로 봅니다. 그림 9.27이 그 예입니다.
그림 9.27
그림 9.27. 자기 교차 다각형.
대부분은 자기 교차 다각형이 생기지 않게 하거나, 생기면 단순히 거부하도록 구성하는 편이 더 쉽다고 느낍니다. 대개의 상황에서 이는 사용자에게 큰 부담을 주지 않습니다.

9.7.2 볼록 다각형과 오목 다각형

자기 교차가 없는 단순 다각형은 다시 볼록 또는 오목으로 분류할 수 있습니다. ‘볼록’을 엄밀하게 정의하기는 사실 다소 까다롭습니다. 다루기 난감한 퇴화 사례가 많기 때문입니다. 대부분의 다각형에서는 아래의 흔히 쓰는 정의들이 서로 동등합니다. 하지만 일부 퇴화 다각형은 한 정의로는 볼록, 다른 정의로는 오목으로 분류될 수 있습니다.
•
직관적으로 볼록 다각형(convex polygon) 에는 ‘움푹 들어간 곳’이 없습니다. 오목 다각형(concave polygon) 에는 움푹 들어간 꼭짓점이 적어도 하나 있으며, 이를 오목점(point of concavity)이라고 합니다(그림 9.28).
•
볼록 다각형 안의 임의의 두 점을 잇는 선분은 전부 다각형 안에 들어 있습니다. 오목 다각형에는 두 점 자체는 안에 있지만 두 점을 잇는 선분 일부가 밖으로 나가는 점의 쌍이 적어도 하나 있습니다.
•
볼록 다각형의 둘레를 따라 움직이면 모든 꼭짓점에서 같은 방향으로 돕니다. 오목 다각형에서는 어떤 곳에서는 왼쪽으로, 어떤 곳에서는 오른쪽으로 돕니다. 오목점에서는 반대 방향으로 돌게 됩니다. 이 설명은 자기 교차가 없는 다각형에만 적용됩니다.
앞에서 말했듯이 퇴화 사례가 끼어들면 비교적 명확해 보이는 이 정의들마저 흐려질 수 있습니다. 예를 들어 연속한 두 꼭짓점이 겹치거나, 변이 갔던 길을 되짚어 돌아오는 다각형은 어떨까요? 그런 다각형도 볼록하다고 해야 할까요? 실무에서는 다음과 같은 ‘정의’를 자주 사용합니다.
•
볼록 다각형에서만 작동하도록 만든 내 코드가 처리할 수 있다면 볼록입니다. ‘고장 나지 않았다면 고치지 말라’식 정의입니다.
•
볼록성을 검사하는 내 알고리즘이 볼록이라고 판단하면 볼록입니다. ‘알고리즘을 정의로 삼는’ 방식입니다.
지금은 이런 병적인 경우는 무시하고, 누구나 분명히 볼록 또는 오목하다고 동의할 예들을 보겠습니다. 그림 9.28에서 위쪽 오목 다각형에는 오목점이 하나 있습니다. 아래쪽 오목 다각형에는 다섯 개가 있습니다.
그림 9.28
그림 9.28. 볼록 다각형과 오목 다각형.
모든 오목 다각형은 볼록한 조각들로 나눌 수 있습니다. 기본 아이디어는 오목점, 즉 오목 꼭짓점(reflex vertex) 을 찾아 대각선을 추가함으로써 체계적으로 없애는 것입니다. O’Rourke [52]는 단순 다각형에 적용되는 알고리즘을 제시합니다. de Berg 외 [12]는 복합 다각형에도 적용되는 더 복잡한 방법을 보여줍니다.
다각형이 볼록인지 오목인지 어떻게 알 수 있을까요? 한 가지 방법은 꼭짓점 각도의 합을 살펴보는 것입니다. 꼭짓점이 nn개인 볼록 다각형을 생각하겠습니다. 볼록 다각형의 내각의 합은 (n−2)180∘(n-2)180^\circ입니다. 이를 보이는 서로 다른 방법이 두 가지 있습니다.
첫째, 꼭짓점 ii의 내각을 θi\theta_i라 하겠습니다. 볼록 다각형이라면 분명히 θi≤180∘\theta_i\le180^\circ입니다. 각 꼭짓점에서 ‘도는’ 양은 180∘−θi180^\circ-\theta_i입니다. 닫힌 다각형을 한 바퀴 돌면 당연히 한 회전, 즉 360∘360^\circ만큼 방향이 바뀝니다. 따라서 다음과 같습니다.
∑i=1n(180∘−θi)=360∘,n180∘−∑i=1nθi=360∘,−∑i=1nθi=360∘−n180∘,∑i=1nθi=n180∘−360∘,∑i=1nθi=(n−2)180∘.\begin{aligned} \sum_{i=1}^{n}(180^\circ-\theta_i)&=360^\circ,\\ n180^\circ-\sum_{i=1}^{n}\theta_i&=360^\circ,\\ -\sum_{i=1}^{n}\theta_i&=360^\circ-n180^\circ,\\ \sum_{i=1}^{n}\theta_i&=n180^\circ-360^\circ,\\ \sum_{i=1}^{n}\theta_i&=(n-2)180^\circ. \end{aligned}
둘째, 9.7.3절에서 보겠지만 꼭짓점이 nn개인 볼록 다각형은 항상 n−2n-2개의 삼각형으로 나눌 수 있습니다. 고전 기하학에 따르면 삼각형의 내각의 합은 180∘180^\circ입니다. 모든 삼각형의 내각의 합은 (n−2)180∘(n-2)180^\circ이며, 이 합은 다각형 자체의 내각의 합과도 같아야 합니다.
안타깝게도 내각의 합이 (n−2)180∘(n-2)180^\circ인 것은 볼록 다각형뿐 아니라 오목 다각형도 마찬가지입니다. 그렇다면 이것이 볼록성 판단에 무슨 도움이 될까요? 그림 9.29처럼 내적으로 외각과 내각 중 더 작은 쪽을 측정할 수 있습니다. 여기서 다각형 꼭짓점의 외각은 내각과 합해서 360∘360^\circ가 되는 각을 뜻합니다.
이것은 앞에서 말한 ‘회전각’과 같지 않습니다. 삼각형 꼭짓점에 대해 고전적으로 사용하는 외각의 정의와도 다르다는 점에 주목하겠습니다. 각 꼭짓점에서 내각과 외각 중 작은 각을 더하면, 볼록 다각형에서는 (n−2)180∘(n-2)180^\circ이고 오목 다각형에서는 그보다 작습니다.
그림 9.29
그림 9.29. 내적으로 다각형이 볼록인지 오목인지 판별하기.
코드 9.7은 각도의 합으로 다각형이 볼록인지 판단하는 방법을 보여줍니다.
bool isPolygonConvex( int n, // 꼭짓점 수 const Vector3 vl[], // 꼭짓점 배열을 가리키는 포인터 ) { // 합을 0라디안으로 초기화한다. float angleSum = 0.0f; // 다각형 둘레를 돌며 각 꼭짓점의 각도를 더한다. for (int i = 0; i < n; ++i) { // 변 벡터를 구한다. 처음과 마지막 꼭짓점에서는 // 주의해야 한다. 이 부분은 상당히 최적화할 수 있다. Vector3 e1; if (i == 0) { e1 = vl[n - 1] - vl[i]; } else { e1 = vl[i - 1] - vl[i]; } Vector3 e2; if (i == n - 1) { e2 = vl[0] - vl[i]; } else { e2 = vl[i + 1] - vl[i]; } // 정규화하고 내적을 구한다. e1.normalize(); e2.normalize(); float dot = e1 * e2; // 수치 오차로 생길 수 있는 범위 오류를 막아 주는 // '안전한' 함수를 사용해 더 작은 각도를 계산한다. float theta = safeAcos(dot); // 누적한다. angleSum += theta; } // 볼록하다고 가정했을 때 각도 합이 얼마여야 하는지 구한다. // pi 라디안 = 180도라는 점을 기억하자. float convexAngleSum = (float)(n - 2) * kPi; // 실제 합이 예상보다 작으면 오목하다. // 수치 오차를 고려해 작은 허용치를 둔다. if (angleSum < convexAngleSum - (float)n * 0.0001f) { // 오목하다. return false; } // 허용 오차 안에서 볼록하다. return true; }
C++
복사
코드 9.7. 각도의 합을 사용한 3차원 다각형 볼록성 검사. 함수 인수 목록 끝의 쉼표는 제공된 원문의 표기이며, 컴파일용 정정은 보충 설명에 제시합니다.
볼록성을 판단하는 또 다른 방법은 오목점인 꼭짓점을 찾는 것입니다. 하나도 없다면 다각형은 볼록합니다. 기본 아이디어는 각 꼭짓점이 같은 방향으로 돌아야 한다는 것입니다. 반대 방향으로 도는 꼭짓점은 오목점입니다. 변 벡터들의 외적으로 어느 방향으로 도는지 판단할 수 있습니다. 2.12.2절에서 보았듯이 왼손 좌표계에서는 두 벡터가 시계 방향으로 꺾일 때 외적이 관찰자 쪽을 향합니다.
‘관찰자 쪽’이라는 말은 다각형 법선이 정한 앞면에서 보고 있다고 가정한 것입니다. 이 법선을 처음부터 알지 못했다면 계산할 때 주의해야 합니다. 아직 볼록 여부를 모르므로 아무 세 꼭짓점이나 골라 법선을 구할 수는 없습니다. 이런 경우에는 9.5.3절에서 설명한 점들의 집합에 가장 잘 맞는 법선을 구하는 기법을 사용할 수 있습니다.
법선을 얻고 나면 각 꼭짓점을 검사하면서 인접한 시계 방향 변 벡터들로 그 꼭짓점의 법선을 계산합니다. 다각형 법선과 꼭짓점에서 계산한 법선을 내적하여 서로 반대 방향인지 판단합니다. 내적이 음수라서 반대 방향이라면 오목점을 찾은 것입니다.
2차원에서는 다각형이 3차원의 z=0z=0 평면에 있는 것처럼 다루고 법선을 [0,0,−1][0,0,-1]로 가정하면 됩니다. 어떤 볼록성 판정 방법에도 미묘한 어려움이 있습니다. Schorn과 Fisher [60]가 이 주제를 더 자세히 다룹니다.
💡
원문 계산식 점검 · 다각형 용어와 코드 표기
이 책은 ‘simple/complex’를 구멍의 유무에 따라 설명합니다. 다른 자료에서는 ‘simple’을 자기 교차가 없다는 뜻으로 사용하기도 하므로, 다른 라이브러리와 연결할 때는 그 라이브러리의 입력 조건을 확인해야 합니다. 이음매가 겹치는 다각형은 어떤 알고리즘에서 별도 처리가 필요합니다.
코드 9.7 함수 선언의 마지막 인수 뒤 쉼표는 C++ 문법에 맞지 않습니다. 다음처럼 끝 쉼표를 제거해야 합니다.
bool isPolygonConvex(int n, const Vector3 vl[]) { // 본문의 함수 몸체 }
C++
복사
연속한 꼭짓점이 같으면 길이 0인 변 벡터를 정규화하게 됩니다. 본문에서 퇴화 사례를 제외했다고 한 가정을 실제 코드 입력 검사에도 반영해야 합니다. 또한 이 코드는 자기 교차 여부나 평면성 검사를 대신하지 않습니다.

9.7.3 삼각분할과 팬 만들기

모든 다각형은 삼각형들로 나눌 수 있습니다. 따라서 삼각형에 대한 모든 연산과 계산을 다각형의 각 조각에 적용할 수 있습니다. 복합 다각형, 자기 교차 다각형, 심지어 단순 오목 다각형의 삼각분할도 간단한 작업이 아니며 [12,52], 이 책의 범위를 조금 벗어납니다.
다행히 단순 볼록 다각형을 삼각분할하는 일은 아주 쉽습니다. 명백한 방법 하나는 꼭짓점 하나, 예를 들어 첫 번째 꼭짓점을 선택하고 이를 중심으로 다각형을 ‘부채꼴(fan)’로 나누는 것입니다. 둘레를 따라 v1,…,vn\mathbf v_1,\ldots,\mathbf v_n으로 나열된 nn개 꼭짓점의 다각형이 주어지면, 인덱스 ii를 3부터 nn까지 변화시키며 {v1,vi−1,vi}\{\mathbf v_1,\mathbf v_{i-1},\mathbf v_i\} 형태의 삼각형 n−2n-2개를 쉽게 만들 수 있습니다(그림 9.30).
그림 9.30
그림 9.30. 부채꼴로 나누어 볼록 다각형을 삼각분할하기.
팬 방식은 길고 얇은 바늘 같은 삼각형을 많이 만드는 경향이 있습니다. 이는 표면 법선 계산 같은 상황에서 문제를 일으킬 수 있습니다. 일부 소비자용 하드웨어는 매우 긴 변을 시야 절두체에 맞추어 잘라낼 때 정밀도 문제를 겪기도 합니다. 이를 줄이려는 더 정교한 기법들이 있습니다.
한 가지 아이디어는 다음과 같습니다. 두 꼭짓점을 잇는 대각선 하나로 다각형을 두 조각으로 나눌 수 있습니다. 그러면 대각선 양 끝의 두 내각이 각각 새로운 내각 두 개로 나뉘어, 총 네 개의 새 내각이 생깁니다. 다각형을 나눌 때 이 네 내각 중 가장 작은 각이 최대가 되는 대각선을 선택합니다.
그 대각선으로 다각형을 둘로 나눕니다. 삼각형만 남을 때까지 양쪽 조각에 이 절차를 재귀적으로 적용합니다. 이 알고리즘은 가늘고 긴 조각이 더 적은 삼각분할을 만듭니다.

9.8 연습문제 (Exercises)

정답은 원서 인쇄 쪽수 774쪽부터, 제공 PDF의 795페이지부터에 있습니다.
1. 다음 매개변수 형식의 2차원 레이가 주어졌습니다.
p(t)=[53]+t[−75].\mathbf p(t)=\begin{bmatrix}5\\3\end{bmatrix} +t\begin{bmatrix}-7\\5\end{bmatrix}.
이 레이를 포함하는 직선을 기울기-절편 형식으로 구해 보세요.
2. 음함수 식 4x+7y=424x+7y=42로 정의된 2차원 직선의 기울기와 yy절편을 구해 보세요.
3. 다음 다섯 점의 집합을 생각하겠습니다.
v1=(7,11,−5),v2=(2,3,8),v3=(−3,3,1),v4=(−5,−7,0),v5=(6,3,4).\begin{aligned} \mathbf v_1&=(7,11,-5),\\ \mathbf v_2&=(2,3,8),\\ \mathbf v_3&=(-3,3,1),\\ \mathbf v_4&=(-5,-7,0),\\ \mathbf v_5&=(6,3,4). \end{aligned}
(a) 이 점들을 감싸는 AABB를 구해 보세요. pmin⁡\mathbf p_{\min}과 pmax⁡\mathbf p_{\max}는 무엇인가요?
(b) 여덟 꼭짓점을 모두 나열해 보세요.
(c) 중심점 c\mathbf c와 크기 벡터 s\mathbf s를 구해 보세요.
(d) 다섯 점에 다음 행렬을 곱해 보세요. 이것이 zz축을 중심으로 한 45도 회전 행렬이라는 것을 알아보았기를 바랍니다.
M=[0.7070.7070−0.7070.7070001].\mathbf M=\begin{bmatrix} 0.707&0.707&0\\ -0.707&0.707&0\\ 0&0&1 \end{bmatrix}.
(e) 변환된 점들의 AABB는 무엇인가요?
(f) 원래 AABB를 변환해서 얻는 AABB는 무엇인가요? 즉 변환된 여덟 꼭짓점을 감싸는 경계 상자를 구해 보세요.
4. 꼭짓점을 시계 방향으로 (6,10,−2),(3,−1,17),(−9,8,0)(6,10,-2),(3,-1,17),(-9,8,0)로 나열해 정의한 삼각형을 생각하겠습니다.
(a) 이 삼각형을 포함하는 평면의 방정식은 무엇인가요?
(b) 점 (3,4,5)(3,4,5)는 이 평면의 앞쪽에 있나요, 뒤쪽에 있나요? 평면에서 이 점까지의 거리는 얼마인가요?
(c) 점 (13.60,−0.46,17.11)(13.60,-0.46,17.11)의 무게중심 좌표를 계산해 보세요.
(d) 무게중심은 어디인가요?
(e) 내심은 어디인가요?
(f) 외심은 어디인가요?
5. 정확히 같은 평면 위에 있지는 않은 다음 점들에 가장 잘 맞는 평면 방정식은 무엇인가요?
p1=(−29.74,13.90,12.70),p2=(11.53,12.77,−9.22),p3=(9.16,2.34,12.67),p4=(14.62,10.64,−7.09),p5=(−3.31,3.16,18.68).\begin{aligned} \mathbf p_1&=(-29.74,13.90,12.70),\\ \mathbf p_2&=(11.53,12.77,-9.22),\\ \mathbf p_3&=(9.16,2.34,12.67),\\ \mathbf p_4&=(14.62,10.64,-7.09),\\ \mathbf p_5&=(-3.31,3.16,18.68). \end{aligned}
6. 꼭짓점 일곱 개에 v1,…,v7\mathbf v_1,\ldots,\mathbf v_7이라는 번호가 붙은 볼록 다각형 PP를 생각하겠습니다. 이 다각형을 팬 방식으로 나누는 방법을 보여 주세요.
정사각형 하나가 조용히 앉아 있었지
자기 직사각형 오두막 바깥에.
그때 삼각형이 쿵 하고 떨어졌네!
“병원에 가야겠어.”
다친 정사각형이 소리쳤지.
그래서 지나가던 구르는 원이
그를 태워 병원으로 데려갔네.
— Shel Silverstein, 「Shapes」(1981)

직접 확인하기

세 가중치의 합을 1로 유지하면서 점을 삼각형 안팎으로 움직여 보세요.
Fletcher Dunn · Ian Parberry, 《3D Math Primer for Graphics and Game Development, 2nd Edition》, 9장. 원서 그림과 자료.