〰️

3차원 곡선(3D Curves)

13.1 매개변수 다항 곡선 (Parametric Polynomial Curves)

13.1.1 매개변수 곡선

13.2 다항 보간 (Polynomial Interpolation)

13.2.1 에이트켄 알고리즘

13.2.2 라그랑주 기저 다항식

13.2.3 다항 보간 정리

13.3 에르미트 곡선 (Hermite Curves)

13.4 베지에 곡선 (Bézier Curves)

13.4.1 드 카스텔조 알고리즘

13.4.2 베른슈타인 기저

13.4.3 베지에 곡선의 도함수와 에르미트 형식의 관계

13.5 세분화 (Subdivision)

13.5.1 단항식 형식의 곡선 세분화

13.5.2 베지에 형식의 곡선 세분화

13.6 스플라인 (Splines)

13.6.1 기본 규칙

13.6.2 매듭점

13.7 에르미트 스플라인과 베지에 스플라인 (Hermite and Bézier Splines)

13.8 연속성 (Continuity)

13.8.1 매개변수 연속성

13.8.2 기하 연속성

13.8.3 곡선은 얼마나 매끄러울 수 있을까?

13.9 자동 접선 제어 (Automatic Tangent Control)

13.9.1 캐트멀–롬 스플라인

13.9.2 TCB 스플라인

13.9.3 끝점 조건

13.10 연습문제 (Exercises)

나는 곡선을 발견한 게 아니다. 그저 드러냈을 뿐이다. — 메이 웨스트(1892–1980)

이 장에서는 3차원 곡선을 수학적으로 표현합니다. 수학적 정의에서 곡선을 재현하는 일은 비교적 쉽습니다. 어려운 부분은 원하는 성질을 가진 곡선을 얻는 것, 또는 디자이너가 그런 곡선을 그릴 수 있는 도구를 만드는 것입니다. 목표는 곡선 수학을 자연스럽고 직관적으로 소개하는 것입니다.

다른 책들과 비교하면 두 문단마다 멈춰 증명하기보다는 중요한 요점을 짚으려 합니다. 다만 정확한 발음을 설명하려고 때때로 멈출 것입니다. 이 장에서 사용할 수학을 만든 이들 대부분이 프랑스 사람이므로 적절한 일일지도 모릅니다.

곡선과 스플라인은 여러 이유로 매우 유용합니다. 물체를 굽은 궤적으로 움직이는 명백한 응용이 있습니다. 하지만 곡선의 좌표를 꼭 공간으로 해석할 필요는 없습니다. 본질적으로 주어진 데이터 점에 색, 강도, 기타 속성 함수를 맞추려는 모든 경우에 곡선과 스플라인을 적용할 가능성이 있습니다.

이 장은 크게 둘로 나뉩니다. 첫 부분은 하나의 식으로 표현하는 단순하고 ‘짧은’ 곡선입니다.

•

13.1절은 거의 전적으로 집중할 유형인 매개변수 다항 곡선을 소개합니다. 특히 3차 다항식을 자세히 봅니다.

•

13.2절은 지정한 제어점을 통과하도록 곡선을 꿰는 다항 보간을 설명합니다.

•

13.3절은 끝점과 끝점에서의 도함수로 곡선을 표현하는 에르미트 형식을 다룹니다.

•

13.4절은 곡선의 끝점과, 통과하지는 않지만 모양에 영향을 주는 내부 제어점을 지정하는 베지에 형식을 보여 줍니다.

•

13.5절은 곡선을 작은 조각으로 나누는 방법을 설명합니다.

뒤 절반은 여러 곡선을 연속으로 연결한 더 긴 곡선인 스플라인을 다룹니다.

•

13.6절은 기본 표기, 용어, 개념을 소개합니다.

•

13.7절은 에르미트나 베지에 곡선을 스플라인으로 연결합니다.

•

13.8절은 스플라인의 연속성, 즉 매끄러움 조건을 살펴봅니다.

•

13.9절은 제어점에서 스플라인의 접선을 자동으로 정하는 여러 방법으로 논의를 마무리합니다.

13.1 매개변수 다항 곡선 (Parametric Polynomial Curves)

여기서는 거의 전적으로 한 유형, 매개변수 다항 곡선(parametric polynomial curve)에 집중합니다. 두 형용사 ‘매개변수’와 ‘다항’의 뜻을 이해하는 것이 중요하므로 13.1.1, 13.1.2절에서 자세히 설명합니다. 13.1.3절은 유용한 다른 표기를, 13.1.4절은 특히 배울 점이 많은 예인 직선을 살핍니다. 13.1.5절은 끝점과 다항식 계수의 관계를, 13.1.6절은 속도·가속도 같은 도함수와 접선벡터·국소 곡률의 관계를 다룹니다.

13.1.1 매개변수 곡선

‘매개변수’라는 말은 예상대로 곡선을 독립 매개변수의 함수로 표현할 수 있다는 뜻입니다. 매개변수에는 흔히 t를 씁니다. 곡선 함수 p(t)는 스칼라 입력 t를 받아 해당 매개변수 값의 곡선 위 점을 벡터로 반환합니다. t가 변하면 p(t)가 곡선의 모양을 따라갑니다. 단위원의 고전적인 매개변수 표현을 보겠습니다.

x(t)=\cos(2\pi t),\qquad y(t)=\sin(2\pi t).\tag{13.1}

9.1절에서 기하 기본형의 매개변수 표현을 잠시 소개했습니다. 매개변수 방식이 아닌 곡선 표현도 이해하도록 대안을 복습하겠습니다. 음함수 표현은 모양 안의 모든 점에서 참인 관계입니다. 단위원은 x² + y² = 1을 만족하는 점의 집합입니다. 함수형 표현은 한 좌표를 나머지 좌표의 함수로 씁니다. 예를 들어 단위원 위쪽 절반은 y = √(1 − x²)입니다.

t의 범위를 제한하지 않으면 p(t)는 무한할 수도 있습니다. 유한 구간을 선택하려고 t를 경계가 있는 정의역, 가장 흔히 [0, 1]로 제한하는 것이 유용합니다. t가 증가하는 방향을 ‘앞’으로 정하면 자연스럽습니다. 곡선은 t = 0에서 ‘시작’하고 t = 1에서 ‘끝나며’ 그 사이의 모든 점으로 이루어집니다.

p(t)를 벡터를 반환하는 하나의 함수로 생각할 때도 있고 특정 좌표의 함수를 꺼내면 유용할 때도 있습니다. 예를 들어 스칼라 함수 x(t)는 p(t)의 x좌표를 지정하므로 2차원에서는 p(t) = (x(t), y(t))입니다. 각 좌표가 매개변수 t에만 의존하는 별개의 함수로 주어지므로 서로 독립적입니다. 중요한 거의 모든 성질을 2차원에서 보일 수 있고 3차원 확장도 대개 간단하므로 이 장 대부분은 평면에서 작업합니다.

13.1.2 다항 곡선

다음은 ‘다항’입니다. 매개변수 다항 곡선은 p(t)를 t의 다항식으로 쓸 수 있는 곡선입니다.

\mathbf p(t)=\mathbf c_0+\mathbf c_1t+\mathbf c_2t^2+\cdots+\mathbf c_{n-1}t^{n-1}+\mathbf c_nt^n.

n은 다항식의 차수입니다. 차수가 높으면 더 많이 ‘굽이치는’ 곡선을 표현할 수 있어 유연합니다. 하지만 원치 않는 굽이침이 추가되기도 합니다.[원주 1] 13.6절에서 더 설명합니다.

매개변수 곡선이지만 다항 곡선은 아닌 예도 이미 보았습니다. 식 (13.1)의 원입니다. x(t), y(t)에 삼각함수가 있으므로 다항식이 아닙니다. 완전한 원은 매개변수 다항 형식으로 나타낼 수 없지만 원호는 유리 곡선(rational curve)으로 나타낼 수 있습니다.

유리 곡선은 본질적으로 곡선 하나를 다른 곡선으로 나눈 결과이며, 동차좌표의 사영기하(6.4.1절)와 비슷합니다. 분모의 곡선은 1차원입니다. 유리 곡선은 게임에서 단순 다항 곡선만큼 흔하지 않으므로 여기서는 다루지 않습니다.

가장 관심 있는 것은 3차 곡선(cubic curve)입니다. 식 (13.2) 형태로 쓸 수 있습니다.

\mathbf p(t)=\mathbf c_0+\mathbf c_1t+\mathbf c_2t^2+\mathbf c_3t^3.\tag{13.2}

이 표현을 단항식 형식(monomial form) 또는 거듭제곱 형식(power form)이라고 합니다. t의 각 거듭제곱 계수를 나열해 지정한다는 점을 강조하는 이름입니다. 13.2~13.4절에서는 곡선이 통과하거나 가까이 지나갈 제어점 목록처럼 더 직접적인 기하 데이터로 표현하는 다른 방법을 다룹니다. 그것들도 단항식 형식으로 바꿀 수 있으므로 여전히 다항 곡선입니다.

계수만 있으면 여러 t에서 p(t)를 계산해 쉽게 재구성합니다. 게임에서 플랫폼을 경로를 따라 움직인다고 하겠습니다. 플랫폼 액터에 경로상의 매개변수 위치 t를 기억하는 상태 변수를 두고, 매 시뮬레이션 시간 단계마다 t를 갱신한 다음 플랫폼 위치를 p(t)로 놓습니다.

곡선을 그려야 한다면, 간단한 방법으로 선분 열 개쯤으로 근사할 수 있습니다. t = 0, 1/10, 2/10, …, 9/10, 1에서 표본을 구해 이웃한 표본 점을 선분으로 잇습니다. 표본을 늘리면 원하는 수준까지 근사 오차를 줄일 수 있습니다. 더 나은 방법은 적응적으로 나눠 더 ‘굽은’ 부분에는 선분을 많이, 더 ‘곧은’ 부분에는 적게 쓰는 것입니다.

그런데 c₀, c₁, c₂, c₃는 어디서 얻을까요? 원하는 곡선이 되도록 어떻게 정할까요? 일반적으로 단항식 형식은 설계에 특히 부적합하므로 다른 형식을 쓰고 적절한 때 변환합니다. 아예 단항식 형식이 필요 없는 경우도 많습니다. 다른 형식을 다루기 전에 표기와 개념을 조금 더 소개해야 합니다.

[원주 1] 특정 호주 어린이 음악 그룹에 대한 평은 아니지만 그렇게 오해할 수도 있습니다.

13.1.3 행렬 표기

식 (13.2)를 여러 방식으로 다시 쓸 수 있습니다. 특정 좌표의 계수를 지칭할 수 있으면 유용합니다. 2차원에서 cᵢ = [c₁,ᵢ, c₂,ᵢ]라고 쓰면 좌표마다 하나의 다항식을 갖습니다.

x(t)=c_{1,0}+c_{1,1}t+c_{1,2}t^2+c_{1,3}t^3,\qquad y(t)=c_{2,0}+c_{2,1}t+c_{2,2}t^2+c_{2,3}t^3.

어떤 책들은 행렬로 더 간결하게 씁니다. 계수를 C에 넣고 t의 거듭제곱을 열벡터 t에 넣어 tᵢ = t^(i−1)이 되게 하겠습니다.

C=\begin{bmatrix}c_{1,0}&c_{1,1}&c_{1,2}&c_{1,3}\\c_{2,0}&c_{2,1}&c_{2,2}&c_{2,3}\end{bmatrix},\qquad \mathbf t=\begin{bmatrix}t^0\\t^1\\t^2\\t^3\end{bmatrix}=\begin{bmatrix}1\\t\\t^2\\t^3\end{bmatrix}.

이제 하나의 행렬 곱으로 쓸 수 있습니다.

\mathbf p(t)=C\mathbf t= \begin{bmatrix}c_{1,0}&c_{1,1}&c_{1,2}&c_{1,3}\\c_{2,0}&c_{2,1}&c_{2,2}&c_{2,3}\end{bmatrix} \begin{bmatrix}1\\t\\t^2\\t^3\end{bmatrix}.

아직 기하학적으로 해석하려 하지 말아 주세요. t는 공간의 점이 아니고 C는 변환행렬이 아닙니다. 곧 C에서 기하적 의미를 꺼내겠지만 앞 장의 기법과 아주 다릅니다. 지금은 간결한 표기를 위해 행렬을 쓴다는 데 만족하겠습니다.

C의 행 수는 데이터 차원 수와 같아야 합니다. 예를 들어 3차원 데이터라면 3입니다. 하지만 여기서 다루는 개념은 대부분 3차원, 2차원, 심지어 1차원에서도 같으므로 구체적인 x, y, z좌표를 언급할 일은 적습니다. 각 계수 cᵢ를 적절한 차원의 벡터로 남겨 C의 열 하나에 대응시키면 됩니다.

C=\begin{bmatrix}|&|&|&|\\\mathbf c_0&\mathbf c_1&\mathbf c_2&\mathbf c_3\\|&|&|&|\end{bmatrix},\qquad \mathbf p(t)=C\mathbf t= \begin{bmatrix}|&|&|&|\\\mathbf c_0&\mathbf c_1&\mathbf c_2&\mathbf c_3\\|&|&|&|\end{bmatrix} \begin{bmatrix}1\\t\\t^2\\t^3\end{bmatrix}.

차수가 높으면 계수와 거듭제곱이 많아져 C가 더 넓어지고 t가 더 길어집니다. 자연스러울 뿐 아니라 규칙상 반드시 그래야 합니다. Ct가 유효하려면 C의 열 수와 t의 행 수가 같아야 합니다.

13.1.4 두 가지 단순한 곡선

곡선을 그리는 방법을 배우러 왔겠지만, 두 가지 단순한 ‘곡선’인 직선 선분과 점을 잠시 보겠습니다.

9.2절의 반직선에서 선분의 매개변수 표현을 보았습니다. p₀에서 p₁로 향하는 반직선을 생각하고 d = p₁ − p₀라고 하면

\mathbf p(t)=\mathbf p_0+\mathbf d t.\tag{13.3}

이것도 지금까지의 다항식입니다. c₀ = p₀, c₁ = d, 나머지 계수는 0입니다. 즉 선형 곡선은 1차 다항 곡선입니다.

직선보다 더 재미없는 모양도 있습니다. 점입니다. 차수를 1에서 0으로 낮추면 상수 곡선이 됩니다. p(t) = c₀는 언제나 같은 값을 반환하므로 움직이지 않는 점 하나짜리 ‘곡선’입니다.

13.1.5 단항식 형식의 끝점

가장 기본적으로 제어하고 싶은 성질은 시작점 p(0)과 끝점 p(1)의 위치입니다. 3차 곡선을 예로 t = 0에서 보면

\mathbf p(0)=\mathbf c_0+\mathbf c_1(0)+\mathbf c_2(0)^2+\mathbf c_3(0)^3=\mathbf c_0.

c₀가 시작점을 정합니다. t = 1에서는

\mathbf p(1)=\mathbf c_0+\mathbf c_1(1)+\mathbf c_2(1)^2+\mathbf c_3(1)^3 =\mathbf c_0+\mathbf c_1+\mathbf c_2+\mathbf c_3.

즉 끝점은 모든 계수의 합입니다.

13.1.6 속도와 접선

곡선은 정적으로도 동적으로도 생각할 수 있습니다. 정적으로는 모양을 정의합니다. 비행기 날개 단면이나 Times Roman 글꼴의 S 일부를 설명할 때의 관점입니다. 동적으로는 시간에 따른 물체의 궤적이나 경로입니다. t를 ‘시간’, p(t)를 경로를 따라가는 입자의 시간 t에서의 위치로 봅니다.

정적인 모양만 보면 시간은 중요하지 않아 작업이 조금 쉬워집니다. 예를 들어 모양에서는 어느 끝이 ‘시작’이고 ‘끝’인지 상관없습니다. 시간에 따라 이동하는 경로에서는 매우 중요합니다.

동적인 관점에서 경로로 보면 ‘이 시각에 입자는 어느 방향으로 움직이나요?’, ‘얼마나 빨리 움직이나요?’라는 질문이 자연스럽습니다. 시간 t에서의 순간속도를 나타내는 v(t)를 만들면 답할 수 있습니다. 순간속도라는 표현을 쓰면 속도가 시간에 따라 변하는 경우에도 각 순간의 값을 이야기할 수 있습니다. 다음 질문은 ‘속도는 얼마나 빨리 변하나요?’입니다. 시간 t에서 속도 변화율을 나타내는 순간가속도 a(t)도 유용합니다.

한 학기 이상의 미적분을 배웠거나 11장을 읽었다면 v(t)가 p(t)의 1차 도함수임을 알 것입니다. 속도는 시간에 따른 위치 변화율이기 때문입니다. 같은 이유로 가속도 a(t)는 v(t)의 도함수입니다.

여기서는 p(t)가 t의 다항식이므로 미분은 간단합니다. 임의의 n차 곡선에서

\mathbf p(t)=\mathbf c_0+\mathbf c_1t+\mathbf c_2t^2+\cdots+\mathbf c_{n-1}t^{n-1}+\mathbf c_nt^n,

\mathbf v(t)=\dot{\mathbf p}(t)=\mathbf c_1+2\mathbf c_2t+\cdots+(n-1)\mathbf c_{n-1}t^{n-2}+n\mathbf c_nt^{n-1},

\mathbf a(t)=\dot{\mathbf v}(t)=\ddot{\mathbf p}(t)=2\mathbf c_2+\cdots+(n-1)(n-2)\mathbf c_{n-1}t^{n-3}+n(n-1)\mathbf c_nt^{n-2}.

3차 곡선의 도함수는 특히 중요하며 이 장에 여러 번 등장합니다.

\mathbf p(t)=\mathbf c_0+\mathbf c_1t+\mathbf c_2t^2+\mathbf c_3t^3,\tag{13.4}

\mathbf v(t)=\dot{\mathbf p}(t)=\mathbf c_1+2\mathbf c_2t+3\mathbf c_3t^2,\tag{13.5}

\mathbf a(t)=\dot{\mathbf v}(t)=\ddot{\mathbf p}(t)=2\mathbf c_2+6\mathbf c_3t.\tag{13.6}

반직선이라는 특별한 경우에 적용하면

\mathbf p(t)=\mathbf p_0+\mathbf d t,\qquad \mathbf v(t)=\mathbf c_1+2\mathbf c_2t+3\mathbf c_3t^2=\mathbf d,\qquad \mathbf a(t)=2\mathbf c_2+6\mathbf c_3t=\mathbf0.

예상대로 속도는 일정하고 가속도는 없습니다.

서로 다른 곡선이 같은 모양이지만 다른 경로를 정의하기도 합니다(그림 13.1). 거꾸로 따라가도 같은 모양이라는 예를 이미 말했습니다. 더 일반적으로는 곡선을 재매개변수화(reparameterize)합니다. p(t) = p₀ + dt에서 s(t) = t²를 만들어 p(s(t))를 보겠습니다.

\mathbf p(s(t))=\mathbf p(t^2)=\mathbf p_0+\mathbf d t^2.

그림 13.1의 둘은 정적 모양은 같지만 경로는 다릅니다. 왼쪽은 일정한 속도로, 오른쪽은 느리게 시작해 끝까지 가속하며 움직입니다.

그림 13.1

그림 13.1. 같은 ‘모양’이지만 서로 다른 ‘경로’를 정의하는 두 곡선

경로가 아니라 모양으로 사용하면 재매개변수화는 눈에 보이는 효과가 없습니다. 그래도 모양 설계에서 도함수가 무관한 것은 아닙니다. S 글자 일부를 곡선으로 만드는 글꼴을 상상하겠습니다. 속도 자체에는 관심이 없을 수 있어도 각 점의 접선에는 큰 관심이 있습니다. 접선은 곡선의 한 점에서 진행 방향을 나타내는 직선입니다. 여기서는 그 접선의 방향을 나타내는 단위벡터를 단위 접선벡터로 정의하겠습니다. 속도가 0이 아닌 점에서는 순간속도를 정규화하여 구할 수 있습니다.

\mathbf t(t)=\hat{\mathbf v}(t)=\frac{\mathbf v(t)}{\|\mathbf v(t)\|}.

고차 도함수에도 기하 의미가 있습니다. 2차 도함수는 곡률(curvature)과 관련되며 그리스 소문자 카파 κ로 쓰기도 합니다. 반지름 r인 원은 모든 점의 곡률이 κ = 1/r이라고 정의할 수 있습니다. 곡선의 곧은 부분은 곡률이 0이며 무한 반지름 원의 곡률로 생각할 수 있습니다. 곡률 공식은 다음과 같습니다.

\kappa(t)=\frac{\|\mathbf v(t)\times\mathbf a(t)\|}{\|\mathbf v(t)\|^3}.

13.2 다항 보간 (Polynomial Interpolation)

선형 보간에는 이미 익숙할 것입니다. 두 ‘끝점’ 값 사이를 일정한 변화율로, 공간적으로는 직선으로 이동하는 함수를 만듭니다. 함수가 두 제어점을 보간한다는 말은 그 점들을 통과하며 중간값을 계산하는 데 사용할 수 있다는 뜻입니다.

다항 보간도 비슷합니다. 제어점들이 주어지면 이를 보간하는 다항식을 만듭니다. 다항식의 차수는 제어점 수에 따라 달라집니다. n차 다항식으로 n + 1개 제어점을 보간할 수 있습니다. 선형 보간은 단순히 1차 다항 보간입니다. 이 장은 주로 3차 곡선에 관심이 있으므로 네 제어점을 보간하는 다항식을 만듭니다.

곡선 설계에서 ‘보간한다’는 말은 제어점을 통과한다는 사실을 특별히 강조합니다. 제어점을 통과하지 않고 어떤 방식으로 끌려가기만 하는 근사(approximation)와 구별됩니다. 실제로 통과하는 제어점은 매듭 있는 밧줄을 떠올리며 매듭(knot)이라고 부릅니다. 보간이 가능하다면 근사는 쓸모없을 것처럼 보일 수 있지만, 근사 기법에도 장점이 있음을 보게 됩니다.

다항 보간은 잘 연구된 해법이 여러 개 있는 고전적인 문제입니다. 3차원 수학 책이므로 주로 기하적으로 설명하지만, 데이터 점에 함수를 맞추는 작업은 폭넓게 응용되므로 대부분의 문헌은 더 일반적인 관점을 취합니다.

설명을 위해 그림 13.2의 특정 예를 쓰겠습니다. S를 옆으로 눕힌 듯한 곡선입니다. 보간하려는 네 제어점을 표시했습니다. 뒤에 유용할 이유 때문에 y좌표 범위를 [2, 3]으로 골랐습니다.

그림 13.2

그림 13.2. 곡선 예와 네 제어점. 이 모양을 그릴 수 있을까요?

t	x(t)	y(t)
0	0	2
1/3	1/3	3
2/3	2/3	2
1	1	3

각 제어점의 위치 x, y뿐 아니라 그 점에 도달할 시각 t도 지정해야 합니다. 독립 값인 ‘시간 값’은 t₁, t₂, …, tₙ, 그 시각의 공간 좌표인 종속 값은 y₁, y₂, …, yₙ이라고 씁니다. 찾으려는 다항함수는 P이며 yᵢ = P(tᵢ)입니다.

시간 값 배열 t₁…tₙ은 다른 맥락에서 매듭벡터(knot vector) 또는 매듭열(knot sequence)이라고 합니다. 여기서 벡터는 수의 배열이라는 뜻이며 기하적 벡터라는 뜻은 아닙니다. 예제처럼 t 간격이 일정하면 균일(uniform), 아니면 비균일(nonuniform) 매듭벡터입니다. 혼동하지 말아 주세요. 매듭벡터는 제어점의 열이 아니라 t값의 열입니다.

x좌표는 어떨까요? x와 y가 독립이므로 일반적인 2차원 곡선 맞춤은 별개의 1차원 문제 두 개입니다. 같은 매듭벡터를 쓴다는 사실 외에는 관계없습니다. 그림 13.2도 2차원 곡선처럼 보이지만 한 좌표, y좌표를 시간의 함수로 그린 그래프로 보는 것이 더 정확합니다. 보통 방향의 S 대신 옆으로 누운 S를 고른 이유는 전자가 함수의 그래프가 아니기 때문입니다. 한 x값에 여러 y값이 대응하므로 엄밀히는 관계(relation)라고 합니다.

따라서 그림 13.2를 y(t)라는 1차원 함수로 해석하거나, 한 좌표가 단순한 x = t인 2차원 곡선으로 해석할 수 있습니다. 이 책과 다른 자료의 곡선 그림에서 흔히 혼란을 일으키는 부분입니다. 가로축을 특히 주의하여 한 좌표의 시간 그래프인지, 두 공간 좌표를 모두 나타내는 2차원 곡선인지 확인하겠습니다.

전통적인 다항 보간 문헌은 보통 y = f(x)라는 추상적 함수로 설명합니다. 거기서 x는 독립변수이지만 이 책에서는 종속 값일 수 있습니다. 그래서 여기의 표기는 x와 그에 따르는 혼란을 피했습니다.

이제 ‘각 점에 언제 도착하는지는 관심 없고 그냥 점들을 지나는 부드러운 모양을 원한다’는 질문에 답할 수 있습니다. 안타깝게도 그것만으로는 곡선을 유일하게 정의할 수 없습니다. 모양을 확정할 다른 기준이 필요하며 제어점마다 시간 값을 붙이는 것이 한 방법입니다. 일반적인 다항 보간 응용에서는 알려진 데이터에 함수를 맞추므로 종속변수 값을 지정할 수 있어야 합니다.

이런 시간 값에 대한 정보가 없으면 합리적으로 만들어 낼 수 있습니다. 예를 들어 인접한 t의 차이를 대응하는 제어점 사이의 유클리드 거리에 비례시킬 수 있습니다. 하지만 적절한 t를 정할 방법이 마땅치 않은 경우가 많은데도 다항 보간이 이를 요구한다는 사실은 뒤에 얻을 발견의 전조입니다.

기본 규칙을 정했으니 곡선을 만들어 보겠습니다. 13.2.1절은 기하적 접근, 13.2.2절은 조금 더 추상적인 수학적 접근입니다.

13.2.1 에이트켄 알고리즘

첫 접근은 알렉산더 에이트켄(Alexander Aitken, 1895–1967)의 재귀 기법입니다. 많은 재귀 알고리즘처럼 분할 정복 원리로 작동합니다. 어려운 문제를 둘 이상의 쉬운 문제로 나누어 따로 푼 다음 결과를 합칩니다. 여기서 어려운 문제는 n개 제어점을 보간하는 곡선입니다. 마지막 점을 무시하고 첫 n−1개를 보간하는 곡선과, 첫 점을 무시하고 마지막 n−1개를 보간하는 곡선으로 나눕니다. 그리고 둘을 혼합합니다.

중요한 3차 경우를 예로 들어 보겠습니다. y₁…y₄를 각 시각 t₁…t₄에서 보간하려 합니다. 분할 정복으로 y₁…y₃를 보간하는 곡선과 y₂…y₄를 보간하는 곡선을 만듭니다. 각각 제어점이 세 개이므로 2차 곡선입니다. 물론 2차 곡선 맞춤도 아직 어렵기 때문에 더 나눠야 합니다.

첫 2차 곡선 y₁, y₂, y₃를 y₁–y₂와 y₂–y₃로 나눕니다. 제어점 두 개씩인 이 곡선들은 직선 선분입니다. 마침내 정말 쉬운 문제입니다!

곡선이 많아졌으니 표기를 정하겠습니다. yᵢ¹(t)는 yᵢ와 yᵢ₊₁ 사이의 선형 곡선, yᵢ²(t)는 yᵢ와 yᵢ₊₂ 사이의 2차 곡선입니다. 위첨자는 재귀 수준이자 다항식 차수이고 아래첨자는 곡선을 따라가는 인덱스입니다.

y₁, y₂, y₃를 보간하는 y₁²(t)는 첫 두 선형 구간을 포함한 두 직선을 혼합하여 만듭니다. 그림 13.3은 이 과정을 보여 줍니다. S 예제의 데이터 대신 덜 대칭적인 경우를 써 혼합 과정을 더 잘 보이게 했습니다. 각 곡선 구간은 모든 t에 대해 정의되는 무한 곡선의 일부라는 점도 보겠습니다.

그림 13.3

그림 13.3. 에이트켄 알고리즘으로 두 선형 구간을 혼합하여 2차 곡선 만들기

수학은 전부 선형 보간입니다. 가장 쉬운 선분은 이웃한 제어점 사이의 보간입니다.

y_1^1(t)=\frac{(t_2-t)y_1+(t-t_1)y_2}{t_2-t_1},\qquad y_2^1(t)=\frac{(t_3-t)y_2+(t-t_2)y_3}{t_3-t_2}.

2차 곡선은 선분들 사이를 선형 보간하므로 약간만 더 복잡합니다.

y_1^2(t)=\frac{(t_3-t)y_1^1(t)+(t-t_1)y_2^1(t)}{t_3-t_1}.

각 곡선은 차수가 더 낮은 두 곡선의 선형 보간이라는 패턴이 보일 것입니다. 점화식으로 간결하게 정리할 수 있습니다.

y_i^0(t)=y_i,\qquad y_i^j(t)=\frac{(t_{i+j}-t)y_i^{j-1}(t)+(t-t_i)y_{i+1}^{j-1}(t)}{t_{i+j}-t_i}.

각 수준에서 혼합하는 두 곡선은 가운데 제어점들을 이미 통과하므로 알고리즘이 작동합니다. 맨 바깥 제어점 둘은 한 곡선만 통과하지만 그 t값에서는 가중치가 극단값에 도달해 해당 제어점을 통과하는 곡선에 가중치 전부를 줍니다.

옆으로 누운 S에 적용하겠습니다. 그림 13.4의 왼쪽에서는 세 선형 구간이 혼합되어 2차 구간 둘이 됩니다. 오른쪽에서는 그 둘을 혼합하여 네 제어점을 모두 보간하는 최종 3차 곡선을 얻습니다.

그림 13.4 — 구성 이미지 1

그림 13.4 — 구성 이미지 2

그림 13.4. 에이트켄 알고리즘의 두 수준

그렇다면 처음 목표를 성공적으로 달성했을까요? 정확히는 아닙니다. 제어점은 통과하지만 원하던 곡선은 아닙니다. 그림 13.4 오른쪽을 처음의 그림 13.2와 비교하면, 에이트켄 곡선은 가운데 제어점 둘의 y값을 넘어섭니다. 우리는 불편한 진실을 발견했습니다.[원주 2]

다항 보간은 기하학적 곡선 설계에서 원하는 종류의 제어를 제공하지 않습니다.

하지만 실망하지 말아 주세요. 13.4절의 베지에 곡선과 13.6절의 스플라인에서 도움이 될 중요한 생각들을 배웠습니다. 사실 조금만 더 참고 다항 보간 논의를 이어 주기를 부탁합니다. 영화 타이타닉을 보는 것과 비슷합니다. 여정이 비극으로 끝날 줄 알아도 도중에 유용한 것을 얻을 수 있습니다. 이 장의 다른 기법들은 교육적 가치뿐 아니라 실용성도 있음을 약속합니다.

실제 다항식 P를 계산하지 않았다는 점을 눈치챘을 것입니다. 계산은 어렵지 않지만 지루하고 통찰도 많지 않습니다. 중요한 점은 에이트켄이 반복 선형 보간으로 곡선을 혼합하는 재귀 과정이라는 것입니다. 대수를 풀어 줄 컴퓨터가 있는데 세부사항에 굳이 매달릴 필요가 있을까요?[원주 3] 그렇다고 게으른 저자 때문에 손해 봤다고 생각할 필요는 없습니다. 다항식이 정말 궁금하거나 책값을 했다고 느끼고 싶다면 계속 읽어 보세요. 다음 절에서 덜 지루한 다른 방법으로 구합니다.

[원주 2] 에이트켄의 ‘앨 고어 리듬(Al Gore rhythm)’이라고나 할까요. algorithm과 영화 《불편한 진실》을 잇는 말장난입니다.

[원주 3] 교수에게 이런 변명을 하지는 말아 주세요. 다만 취업 면접에서는 통한 적이 있다고 합니다.

13.2.2 라그랑주 기저 다항식

기하적 직관에서 에이트켄 알고리즘을 얻었습니다. 이제 더 추상적인 수학 관점으로 접근합니다.

한 접근은 선형대수에서 나옵니다.[원주 4] 제어점마다 식 하나, 계수마다 미지수 하나가 생깁니다. 연립방정식을 n×n 행렬[원주 5]에 넣고 가우스 소거법이나 LU 분해 같은 표준 기법으로 풀 수 있습니다. 이 책 범위 밖이지만 좋은 선형대수·수치해석 책 대부분에서 배울 수 있습니다.

행렬을 푸는 계산은 비교적 오래 걸리며 n×n 행렬은 최악의 경우 O(n³) 시간이 필요합니다. 다행히 더 효율적인 방법이 있습니다. 에이트켄처럼 크고 복잡한 문제를 작고 쉬운 문제들로 나누고 결과를 합칩니다. 에이트켄은 재귀지만 여기서는 제어점마다 간단한 문제 하나를 만듭니다.

지금은 y를 무시하고 t만 보겠습니다. 각 매듭 tᵢ에서 1, 다른 모든 매듭에서 0이 되는 다항식을 만들 수 있다면 어떨까요? i번째 다항식을 ℓᵢ라고 하면 ℓᵢ(tᵢ) = 1, 모든 j ≠ i에서 ℓᵢ(tⱼ) = 0입니다. n = 4이면 다음 값이어야 합니다.

매듭	ℓ₁	ℓ₂	ℓ₃	ℓ₄
t₁	1	0	0	0
t₂	0	1	0	0
t₃	0	0	1	0
t₄	0	0	0	1

보충·원문 정정

제공 PDF 표의 첫 줄 둘째 항은 ℓ₁(t₁)=0으로 오식되어 있습니다. 문맥과 정의상 ℓ₂(t₁)=0이며 위 표에 이를 반영했습니다.

이 성질의 다항식을 만들면 기저 다항식으로 쓸 수 있습니다. 각각 ℓᵢ에 해당 좌표 yᵢ를 곱하고 모두 더합니다.

P(t)=\sum_{i=1}^n y_i\ell_i(t) =y_1\ell_1(t)+y_2\ell_2(t)+\cdots+y_{n-1}\ell_{n-1}(t)+y_n\ell_n(t).\tag{13.7}

실제로 P(tᵢ) = yᵢ라서 제어점을 보간하는지 잠시 확인하겠습니다. 기저 다항식은 매듭벡터 t에만 의존하고 좌표 y에는 의존하지 않습니다. 따라서 같은 매듭벡터의 여러 곡선을 빠르게 구성할 수 있습니다. 같은 매듭열을 공유하는 1차원 곡선 셋으로 이루어진 3차원 곡선이 바로 이런 경우입니다.

물론 기저 다항식을 알아야만 가능하며 ℓᵢ를 찾는 것 자체도 다항 보간 문제입니다. 하지만 보간할 ‘데이터 점’이 모두 0 아니면 1이므로 간단한 형식으로 쓸 수 있습니다. 이것을 라그랑주 기저 다항식이라고 합니다.[원주 6][원주 7] 매듭벡터 t₁…tₙ에 대해서는

\ell_i(t)=\prod_{\substack{1\le j\le n\\j\ne i}}\frac{t-t_j}{t_i-t_j} =\frac{t-t_1}{t_i-t_1}\cdots\frac{t-t_{i-1}}{t_i-t_{i-1}} \frac{t-t_{i+1}}{t_i-t_{i+1}}\cdots\frac{t-t_n}{t_i-t_n}.\tag{13.8}

보충·원문 정정

원문 전개식은 처음 인덱스를 t₀로, 한 분모를 tᵢ − iᵢ₊₁로 잘못 썼습니다. 곱 기호의 정의와 일치하도록 각각 t₁과 tᵢ − tᵢ₊₁로 고쳤습니다. j = i인 인자는 제외합니다.

t = tᵢ에서는 각 인자가 1이라 전체가 1이고, 다른 매듭에서는 인자 하나가 0이라 전체가 0이 됩니다.

S 예제의 균일 매듭벡터 (0, 1/3, 2/3, 1)에 적용하겠습니다. 첫 기저는 전개하고 나머지는 결과만 제시합니다.

\begin{aligned} \ell_1(t)&=\left(\frac{t-t_2}{t_1-t_2}\right)\left(\frac{t-t_3}{t_1-t_3}\right)\left(\frac{t-t_4}{t_1-t_4}\right)\\ &=\left(\frac{t-1/3}{0-1/3}\right)\left(\frac{t-2/3}{0-2/3}\right)\left(\frac{t-1}{0-1}\right)\\ &=\left(\frac{3t-1}{-1}\right)\left(\frac{3t-2}{-2}\right)\left(\frac{t-1}{-1}\right)\\ &=\frac{(3t-1)(3t-2)(t-1)}{-2}\\ &=-\frac92t^3+9t^2-\frac{11}2t+1, \end{aligned}

\ell_2(t)=\frac{27}2t^3-\frac{45}2t^2+9t,\qquad \ell_3(t)=-\frac{27}2t^3+18t^2-\frac92t,\qquad \ell_4(t)=\frac92t^3-\frac92t^2+t.

그림 13.5는 이 기저 다항식의 모습입니다.

그림 13.5 — 구성 이미지 1

그림 13.5 — 구성 이미지 2

그림 13.5 — 구성 이미지 3

그림 13.5 — 구성 이미지 4

그림 13.5. 균일 매듭벡터의 3차 라그랑주 기저 다항식

이제 S 예제의 y값을 식 (13.7)에 넣어 완전한 보간 다항식을 구합니다.

\begin{aligned} P(t)&=y_1\ell_1(t)+y_2\ell_2(t)+y_3\ell_3(t)+y_4\ell_4(t)\\ &=2[-\tfrac92t^3+9t^2-\tfrac{11}2t+1]+3[\tfrac{27}2t^3-\tfrac{45}2t^2+9t]\\ &\quad+2[-\tfrac{27}2t^3+18t^2-\tfrac92t]+3[\tfrac92t^3-\tfrac92t^2+t]\\ &=-9t^3+18t^2-11t+2+\tfrac{81}2t^3-\tfrac{135}2t^2+27t\\ &\quad-27t^3+36t^2-9t+\tfrac{27}2t^3-\tfrac{27}2t^2+3t\\ &=18t^3-27t^2+10t+2. \end{aligned}

그림으로도 보겠습니다. 먼저 각 기저 다항식에 대응하는 좌표값을 곱하면 그림 13.6입니다. 그 결과들을 더하면 그림 13.7 위쪽의 파란 보간 곡선 P가 됩니다.

그림 13.6

그림 13.6. 각 라그랑주 기저 다항식에 대응 좌표값 곱하기

그림 13.7

그림 13.7. 보간 곡선은 배율을 곱한 기저 다항식들의 합이다

‘기저’라는 말은 매듭에서의 함수값이 주어졌을 때 이 다항식을 재료로 어떤 다항식이든 재구성할 수 있다는 점을 강조합니다. 기저벡터(3.3.3절)와 같은 개념입니다. 임의의 벡터를 기저벡터의 선형결합으로 나타내듯, 여기서 기저가 생성하는 공간은 기하학적 3차원 공간이 아니라 특정 차수의 모든 다항식으로 이루어진 벡터공간입니다. 각 곡선의 배율은 매듭에서 알려진 다항식 값입니다.

곱하고 더하는 과정을 달리 이해할 수도 있습니다. 다항식을 재료, 제어점을 배율로 보는 대신 곡선 위 각 점을 제어점들의 가중평균으로 보고 기저 다항식이 혼합 가중치를 준다고 생각하겠습니다. 제어점이 재료, 기저 다항식이 배율이 됩니다. 우리는 이 배율을 더 구체적으로 무게중심 좌표(barycentric coordinates)라고 부르고 싶습니다. 9.6.3절에서는 삼각형에서 소개했지만 어떤 값을 데이터 점들의 가중평균으로 나타내는 일반적인 기법을 뜻합니다.

기저 다항식은 무게중심 좌표, 즉 혼합 가중치를 반환하는 함수로 볼 수 있습니다.

어떤 구간에서는 값이 음수 또는 1보다 큽니다. 직접 다항 보간이 제어점을 넘어가는 이유입니다. 모든 무게중심 좌표가 [0, 1] 안이면 결과 점은 제어점의 볼록 껍질(convex hull) 안에 있음을 보장합니다. 볼록 껍질은 모든 제어점을 포함하는 가장 작은 다각형입니다.

제어점들을 고무줄로 둘러 팽팽히 당겼다가 놓은 것처럼 ‘수축 포장’합니다. 좌표 하나라도 범위 밖이면 결과가 껍질 밖으로 나갈 수 있습니다. 곡선 설계에는 볼록 껍질 보장이 매우 유용합니다. 13.4절에서 베지에 곡선이 베른슈타인 기저로 이 보장을 제공함을 보게 됩니다.

[원주 4] 이 책의 기하 중심 부분집합이 아니라 본격적인 선형대수 이야기입니다.

[원주 5] 각 행이나 열이 어떤 항의 거듭제곱 등비수열인 이런 행렬은 프랑스 수학자 Alexandre-Théophile Vandermonde(1735–1796)의 이름을 따 반데르몽드 행렬이라고 합니다.

[원주 6] Joseph Louis Lagrange(1736–1813)의 이름이 붙었지만 Edward Waring(1736–1798)이 1779년에 발견했습니다. 흥미롭게도 라그랑주는 이언 파베리의 박사 지도교수의 박사 지도교수의 … 박사 지도교수를 열 번 거슬러 올라간 인물입니다.

[원주 7] 프랑스 수학자의 이름은 영어로 ‘luh-GRAWNGE’에 가깝게 발음해야 합니다. 그렇지 않으면 텍사스의 작은 마을 La Grange(‘luh-GRAYNGE’)를 말한다고 생각할 수 있습니다. 저자들이 알기로 그 마을 이름의 기저 다항식은 없습니다. 다만 ZZ Top은 근처의 유곽을 기리며 마을 이름으로 노래를 만들었습니다.

13.2.3 다항 보간 정리

두 관점으로 접근했습니다. 에이트켄 알고리즘은 반복 선형 보간에 기반한 기하적 방법이며, 다항식 자체를 몰라도 주어진 t의 곡선 위 점을 계산합니다. 라그랑주 보간은 매듭벡터에만 의존하는 기저함수를 만듭니다. 기저마다 해당 좌표를 곱해 모두 더한다고 볼 수도 있고, 기저가 무게중심 좌표를 계산하여 제어점의 가중평균에 쓴다고 볼 수도 있습니다.

서로 다른 시간 값으로 지정한 같은 데이터에는 두 방법이 같은 곡선을 줍니다. 게다가 이 다항식은 유일합니다. 같은 차수의 다른 다항식은 그 점들을 보간하지 않습니다. 비공식적인 논리는 이렇습니다. n차 다항식에는 단항식 형식의 n + 1개 계수에 대응하는 n + 1개 자유도가 있습니다. 따라서 n + 1개 제어점을 보간하는 n차 다항식은 유일해야 합니다. 더 엄밀한 설명은 Farin[20, 6.2절]을 참고해 보세요.

곡선 설계에 이상적이지 않은 주된 이유는 오버슈트를 제어하기 어렵다는 점입니다. 바탕인 라그랑주 기저가 [0, 1]에 제한되지 않으므로 곡선이 제어점의 볼록 껍질을 벗어날 수 있습니다. 직접 다항 보간은 게임에서 쓰임이 제한적이지만, 이를 공부하며 반복 선형 보간과 기저 다항식이라는 주제를 만났고 두 기법 사이의 아름다운 쌍대성도 조금 보았습니다.

13.3 에르미트 곡선 (Hermite Curves)

다항식 보간은 곡선을 지정한 매듭점 사이로 통과시켜 곡선 내부의 모양을 제어하려 합니다. 그러나 곡선이 진동하거나 지나치게 튀어나가는 경향 때문에 원하는 만큼 잘 작동하지 않습니다. 그러므로 다른 접근을 시도해 보겠습니다. 물론 양 끝점의 위치는 여전히 지정하고 싶습니다. 하지만 이번에는 보간할 내부 위치를 지정하는 대신 양 끝점의 접선으로 곡선의 모양을 제어합니다.

이렇게 지정한 곡선을 에르미트 곡선(Hermite curve) 또는 에르미트 형식의 곡선이라고 합니다. 샤를 에르미트(Charles Hermite, 1822–1901)의 이름에서 따온 명칭입니다.[원주 8]

에르미트 형식은 곡선의 시작 위치와 끝 위치, 그리고 그곳의 도함수를 나열하여 곡선을 지정합니다. 3차 곡선에는 계수가 네 개뿐이므로 1차 도함수, 즉 양 끝점의 속도까지만 지정할 수 있습니다. 따라서 3차 곡선을 에르미트 형식으로 기술한다는 것은 다음 네 가지 정보를 지정한다는 뜻입니다.

•

t=0t=0t=0에서의 시작 위치

•

t=0t=0t=0에서의 1차 도함수, 즉 초기 속도

•

t=1t=1t=1에서의 끝 위치

•

t=1t=1t=1에서의 1차 도함수, 즉 최종 속도

원하는 시작 위치와 끝 위치를

\mathbf p_0,\mathbf p_1

, 시작 속도와 끝 속도를

\mathbf v_0,\mathbf v_1

이라고 하겠습니다. 그림 13.8에는 3차 에르미트 곡선의 예가 나와 있습니다. 그림의 속도 벡터

\mathbf v_0,\mathbf v_1

은 실제 길이의 3분의 1로 그렸습니다. 공간을 절약하려는 이유도 있고, 13.4절에서 베지에 곡선을 배운 뒤 이해하게 될 또 다른 이유도 있습니다.

그림 13.8

그림 13.8. 여러 가지 3차 에르미트 곡선.

에르미트 값으로부터 단항식 형식의 계수를 구하는 일은 앞에서 다룬 식들을 결합하는 비교적 간단한 대수 과정입니다. 네 에르미트 조건은 다음 연립방정식으로 옮길 수 있습니다.

\mathbf p(0)=\mathbf p_0\quad\Longrightarrow\quad\mathbf c_0=\mathbf p_0.\tag{13.9}

\mathbf v(0)=\mathbf v_0\quad\Longrightarrow\quad\mathbf c_1=\mathbf v_0.\tag{13.10}

\mathbf v(1)=\mathbf v_1\quad\Longrightarrow\quad\mathbf c_1+2\mathbf c_2+3\mathbf c_3=\mathbf v_1.\tag{13.11}

\mathbf p(1)=\mathbf p_1\quad\Longrightarrow\quad\mathbf c_0+\mathbf c_1+\mathbf c_2+\mathbf c_3=\mathbf p_1.\tag{13.12}

끝점을 지정하는 식 (13.9), (13.12)는 13.1.5절에서 했던 이야기를 반복한 것입니다. 속도를 지정하는 식 (13.10), (13.11)은 3차 다항식의 속도 식, 즉 인쇄본 652쪽의 식 (13.5)에서 바로 나옵니다. 여기서 식을 나열한 순서는 곡선을 다루는 다른 문헌에서도 쓰이는 관례이며, 이 순서가 편리한 이유는 뒤에서 드러납니다.

이 연립방정식을 풀면 에르미트 위치와 도함수로부터 단항식 계수를 계산하는 방법을 얻습니다.

\mathbf c_0=\mathbf p_0.\tag{13.13}

\mathbf c_1=\mathbf v_0.\tag{13.14}

\mathbf c_2=-3\mathbf p_0-2\mathbf v_0-\mathbf v_1+3\mathbf p_1.\tag{13.15}

\mathbf c_3=2\mathbf p_0+\mathbf v_0+\mathbf v_1-2\mathbf p_1.\tag{13.16}

13.1.2절에서 도입한 간결한 행렬 표기로도 쓸 수 있습니다. 계수들을 행렬

C

의 열에 넣고

t

의 거듭제곱들을 열벡터

\mathbf t

에 넣으면 다항식 곡선을 행렬곱

C\mathbf t

로 나타낼 수 있다는 것을 기억하겠습니다.

\mathbf p(t)=C\mathbf t= \begin{bmatrix}|&|&|&|\\\mathbf c_0&\mathbf c_1&\mathbf c_2&\mathbf c_3\\|&|&|&|\end{bmatrix} \begin{bmatrix}1\\t\\t^2\\t^3\end{bmatrix}.

여기서

\mathbf p(t)

와 각 계수 벡터

\mathbf c_i

는 기하학적 차원 수, 즉 1D·2D·3D에 맞는 높이의 열벡터입니다.

\mathbf t

의 높이는

\mathbf c

의 개수와 같으며, 곡선의 차수에 따라 달라집니다.

에르미트 위치와 속도를 행렬

P

의 열에 넣고 변환 행렬

H

를 곱하면 계수 행렬

C

자체도 행렬곱으로 쓸 수 있습니다.

\begin{aligned} \mathbf p(t)&=C\mathbf t=PH\mathbf t\\ &=\begin{bmatrix}|&|&|&|\\\mathbf p_0&\mathbf v_0&\mathbf v_1&\mathbf p_1\\|&|&|&|\end{bmatrix} \begin{bmatrix}1&0&-3&2\\0&1&-2&1\\0&0&-1&1\\0&0&3&-2\end{bmatrix} \begin{bmatrix}1\\t\\t^2\\t^3\end{bmatrix}. \end{aligned}

곱

PH\mathbf t

는 두 가지로 해석할 수 있습니다.

P(H\mathbf t)

로 묶으면 행렬곱

H\mathbf t

를 에르미트 기저 함수로 해석할 수 있습니다. 이 기저에 대해서는 잠시 뒤 더 이야기합니다. 또는

C=PH

로 생각할 수도 있습니다. 이 경우

H

를 곱하는 것은 에르미트 기저에서 단항식 기저로 변환하는 연산이며, 사실상 식 (13.13)–(13.16)을 다시 쓴 것입니다.

여기서 강조하고 싶은 점이 있습니다. 단항식, 에르미트, 베지에라는 말은 같은 다항식 곡선 집합을 서로 다르게 기술하는 방법을 뜻합니다. 서로 다른 곡선 집합을 뜻하는 것이 아닙니다. 에르미트 형식의 곡선을 단항식 형식으로 바꿀 때는 식 (13.13)–(13.16)을 쓰고, 단항식 형식을 에르미트 형식으로 바꿀 때는 식 (13.9)–(13.12)를 씁니다.

이제 에르미트 기저를 자세히 살펴보고, 이것이 작동하는 이유에 관한 기하학적 직관을 얻어 보겠습니다. 기저 함수는

t

를 받아 무게중심 좌표를 내놓는 함수로 해석할 수 있습니다. 3차 에르미트 곡선에서 혼합하는 값은 네 개, 즉 두 위치와 두 속도 벡터입니다.[원주 9] 따라서 기저 함수도 네 개이며, 행렬곱

H\mathbf t

로 얻은 열벡터의 성분들이 바로 그 함수입니다. 곱을 전개하면 다음과 같습니다.

\begin{aligned} \mathbf p(t)&=P(H\mathbf t)\\ &=\begin{bmatrix}|&|&|&|\\\mathbf p_0&\mathbf v_0&\mathbf v_1&\mathbf p_1\\|&|&|&|\end{bmatrix} \left(\begin{bmatrix}1&0&-3&2\\0&1&-2&1\\0&0&-1&1\\0&0&3&-2\end{bmatrix} \begin{bmatrix}1\\t\\t^2\\t^3\end{bmatrix}\right)\\ &=\begin{bmatrix}|&|&|&|\\\mathbf p_0&\mathbf v_0&\mathbf v_1&\mathbf p_1\\|&|&|&|\end{bmatrix} \begin{bmatrix}1-3t^2+2t^3\\t-2t^2+t^3\\-t^2+t^3\\3t^2-2t^3\end{bmatrix}. \end{aligned}

이 기저 함수들, 즉

H\mathbf t

의 각 행에

H_0(t),\ldots,H_3(t)

라는 이름을 붙이겠습니다. 다른 자료에서는 같은 함수들에 다른 아래첨자를 붙이기도 합니다.

\begin{aligned} H_0(t)&=1-3t^2+2t^3,\\ H_1(t)&=t-2t^2+t^3,\\ H_2(t)&=-t^2+t^3,\\ H_3(t)&=3t^2-2t^3. \end{aligned}

행렬곱을 전개하면 이 함수들이 혼합 가중치로 쓰인다는 사실이 분명해집니다.

\begin{aligned} \mathbf p(t)&=\begin{bmatrix}|&|&|&|\\\mathbf p_0&\mathbf v_0&\mathbf v_1&\mathbf p_1\\|&|&|&|\end{bmatrix} \begin{bmatrix}H_0(t)\\H_1(t)\\H_2(t)\\H_3(t)\end{bmatrix}\\ &=H_0(t)\mathbf p_0+H_1(t)\mathbf v_0+H_2(t)\mathbf v_1+H_3(t)\mathbf p_1. \end{aligned}

그림 13.9는 에르미트 기저 함수의 그래프입니다.

그림 13.9

그림 13.9. 에르미트 기저 함수.

여기서 몇 가지를 관찰해 보겠습니다. 첫째,

H_0(t)+H_3(t)=1

입니다. 따라서 “점”을 서로 더한다는 개념이 못마땅했던 독자도 안심할 수 있습니다. 이 상황을 점들의 올바른 무게중심 조합으로 해석할 수 있기 때문입니다.

곡선

H_3(t)

는 특별히 주목할 가치가 있습니다. 스무스스텝(smoothstep) 함수라는 이름으로도 알려져 있으며, 모든 게임 프로그래머가 알아야 할 보석 같은 함수입니다. RenderMan 셰이딩 언어나 HLSL을 비롯해 여러 곳에서 만날 수 있습니다. 선형 보간, 특히 카메라 전환의 딱딱하고 기계적인 느낌을 없애고 싶다면 평소처럼 정규화된 보간 비율

t

를

0\le t\le1

범위로 계산한 뒤,

t

를

3t^2-2t^3

으로 바꾸면 됩니다.

그러면 놀랍게도 전체 움직임이 한결 세련되어 보입니다. 스무스스텝 함수가 양 끝점에서 속도가 갑자기 뛰는 현상을 없애기 때문입니다. 즉

H_3'(0)=H_3'(1)=0

입니다.

스무스스텝은 여러분의 친구입니다

에르미트 기저 함수 H3(t)H_3(t)H3​(t)는 스무스스텝 함수라고도 부릅니다. 선형 보간에 바탕을 둔 거의 모든 전환, 특히 카메라 전환은 스무스스텝 함수를 사용하면 느낌이 좋아집니다.

에르미트 곡선에 관해 마지막으로 한 가지 덧붙이겠습니다. 다른 다항식 곡선 형식처럼 더 높은 차수의 에르미트 곡선도 설계할 수 있습니다. 다만 컴퓨터 그래픽스와 애니메이션에서는 3차 다항식을 가장 많이 씁니다. 3차 스플라인에서는 양 끝점의 위치, 즉 “0차” 도함수와 속도, 즉 1차 도함수를 지정했습니다. 여기에 가속도, 즉 2차 도함수까지 지정하면 5차 에르미트 곡선(quintic Hermite curve)이 됩니다.

[원주 8] 이 사람도 프랑스인입니다. 그의 어머니는 아마 이름을 “에르미트(air-MEET)”라고 발음했을 것입니다. 하지만 영어권에서는 저자들이 아는 박사 학위 소지자 중 일부를 포함해 많은 사람이 “허마이트(HUR-mite)”라고 발음합니다. 그러니 그렇게 발음해도 괜찮을 것입니다.

[원주 9] 점과 벡터를 “혼합”한다는 개념에 반대하는 엄격한 독자라면 2.4절을 참고해 보세요. 걱정할 필요는 없습니다. 그런 불편한 뒤섞기가 일어나지 않도록 식을 해석할 수도 있습니다.

13.4 베지에 곡선 (Bézier Curves)

이 장에서는 지금까지 곡선에 관한 여러 유익한 개념을 다루었지만, 곡선을 설계하는 완전히 실용적인 방법은 아직 설명하지 않았습니다. 이번 절에서 그것이 달라집니다.[원주 10] 베지에 곡선(Bézier curve)은 프랑스인[원주 11] 엔지니어 피에르 베지에(Pierre Bézier, 1910–1999)가 자동차 회사 르노에서 일하던 중 발명했습니다.

곡선 설계에 잘 맞는 여러 바람직한 성질을 갖습니다. 특히 베지에 곡선은 보간 대신 근사를 합니다. 처음과 마지막 제어점은 지나지만 내부 제어점은 그 근처를 지나갈 뿐입니다. 그래서 이 점들을 “매듭점” 대신 “제어점”이라고 부릅니다. 그림 13.10은 몇 가지 3차 베지에 곡선의 예입니다.

그림 13.10

그림 13.10. 여러 가지 3차 베지에 곡선.

13.2절의 다항식 보간 문제에는 같은 결과를 내는 두 가지 해법이 있었습니다. 에이트켄 알고리즘은 기하학적 직관에 호소하는 재귀적 구성 방법이고, 더 추상적인 접근법에서는 라그랑주 기저 다항식이 나왔습니다. 베지에 곡선에도 비슷한 이중성이 있습니다. 에이트켄 알고리즘에 대응하는 것은 드 카스텔조 알고리즘(de Casteljau algorithm)으로, 반복적인 선형 보간을 통해 베지에 곡선을 구성하는 재귀적 기하 기법입니다. 13.4.1절에서 다룹니다. 라그랑주 기저에 대응하는 것은 베른슈타인 기저(Bernstein basis)이며 13.4.2절에서 설명합니다. 동전의 양면을 모두 살펴본 뒤에는 13.4.3절에서 베지에 곡선의 도함수[원주 12]를 조사하고 에르미트 형식과의 관계를 밝힙니다.

이 책에서는 수학과 기하가 아름답게 협력하는 사례를 여러 번 보았지만, 베지에 곡선에서 두 분야가 만나는 방식은 특히 우아합니다. 베지에 곡선의 중요한 성질은 거의 모두 서로 다른 분야의 연구자들이 여러 번 독립적으로 발견한 것처럼 보입니다. 로저스의 책 [58]에는 그 역사에 관한 흥미로운 이야기가 있습니다.

13.4.1 드 카스텔조 알고리즘

드 카스텔조 알고리즘은 반복적인 선형 보간으로 베지에 곡선을 구성하는 방법입니다. 물리학자이자 수학자인 폴 드 카스텔조(Paul de Casteljau)가 1959년에 만들었습니다.[원주 13] 원문에는 그의 생몰 연도가 “1910–1999”라고 적혀 있습니다. 여기서는 알고리즘 설명을 그대로 따르되, 이 인물 정보는 원문 표기임을 구분해 둡니다.

중요한 3차 곡선을 예로 알고리즘의 작동 방식을 살펴보겠습니다. 먼저 표기를 조금 정해야 합니다. 3차 곡선은 네 제어점

\mathbf b_0,\ldots,\mathbf b_3

으로 정의합니다. 베지에 제어점의 첨자는 관례적으로 0에서 시작합니다. C 프로그래머들에게 반가운 관례일 것입니다. 또한 에이트켄 알고리즘처럼 재귀 단계는 위첨자로 나타냅니다. 원래 제어점은 0단계이므로

\mathbf b_i^0=\mathbf b_i

입니다.

이제 0에서 1 사이의 특정 매개변수

t

를 생각하겠습니다. 드 카스텔조 알고리즘은 이에 대응하는 곡선 위의 점

\mathbf p(t)

를 다음과 같이 기하학적으로 구성합니다. 연속한 제어점의 각 쌍 사이에서 비율

t

로 보간하여 새 점을 얻습니다. 원래 네 제어점

\mathbf b_0^0,\ldots,\mathbf b_3^0

에서 시작하면 새 점

\mathbf b_0^1,\mathbf b_1^1,\mathbf b_2^1

세 개가 나옵니다.

이 세 점의 연속한 쌍을 다시 보간하면

\mathbf b_0^2,\mathbf b_1^2

두 개가 나오며, 마지막으로 한 번 더 보간하면 찾던 점

\mathbf b_0^3=\mathbf p(t)

를 얻습니다. 그림 13.11은 같은 곡선에

t=0.25,0.50,0.75

를 적용한 모습입니다.

그림 13.11

그림 13.11. 3차 곡선에 적용한 드 카스텔조 알고리즘.

그림 13.12처럼 모든

\mathbf b

를 삼각형 모양으로 배열하면 이해하기 쉽습니다. 각각의 중간점은 바로 윗줄에 있는 두 점을 선형 보간한 결과입니다.

그림 13.12

그림 13.12. 3차 곡선에 대한 드 카스텔조 알고리즘의 계층 관계.

이 재귀 관계와 기본 선형 보간 공식을 합치면 다음 점화식을 얻습니다.

드 카스텔조 점화식

\begin{aligned} \mathbf b_i^0(t)&=\mathbf b_i,\\ \mathbf b_i^n(t)&=(1-t)\mathbf b_i^{n-1}(t)+t\mathbf b_{i+1}^{n-1}(t). \end{aligned}

코드 13.1은 특정

t

에서 베지에 곡선을 평가하도록 드 카스텔조 알고리즘을 C++로 구현한 예입니다. 호출자는 원래 제어점들을 배열로 전달합니다. 연산은 배열 자체를 덮어쓰므로 이 배열은 임시 작업 공간 역할도 합니다. 바깥 반복문의 각 반복에서 한 차례의 보간을 수행하고, 현재 단계의 점들을 위첨자가 하나 더 큰 다음 단계의 점들로 바꿉니다.

원하는 결과

\mathbf p(t)

하나가 남을 때까지 계속합니다. 이 코드는 알고리즘의 작동 원리를 보여 주려는 예이며, 특별히 빠른 구현이나 깔끔한 인터페이스를 제시하려는 것은 아닙니다.

Vector3 deCasteljau(
    int n,             // 곡선의 계수(order), 즉 점의 개수
    Vector3 points[],  // 점 배열. 제자리에서 연산하므로 덮어쓴다.
    float t            // 평가하려는 매개변수 값
) {
    // 제자리에서 변환을 수행한다.
    while (n > 1) {
        --n;
        // 다음 보간 단계를 수행하여 곡선의 차수를 하나 줄인다.
        for (int i = 0; i < n; ++i) {
            points[i] = points[i] * (1.0f-t) + points[i+1] * t;
        }
    }
    // 결과는 이제 첫 번째 칸에 있다.
    return points[0];
}

C++

복사

코드 13.1. 드 카스텔조 알고리즘으로 베지에 곡선 위의 점 평가하기.

이 방법으로 임의의

t

에 대한 점을 반복 보간하여 찾을 수 있지만, 제어점으로부터 그 점을 곧바로 계산하는 닫힌 형태의 식은 아직 얻지 못했습니다. 그런 식이 필요 없는 경우도 많다는 점을 강조하고 싶습니다. 그래도 단항식 형식으로 유도해 보겠습니다. 원하는 것은

t

의 거듭제곱별로 묶인 다항식입니다. 1차, 2차를 거쳐 3차로 올라가겠습니다. 13.4.2절에서는 임의 차수의 곡선 식으로 이어지는 일반적인 패턴을 제시합니다.

1차의 경우는 점화식에서 거의 아무 수고 없이 바로 나옵니다.

\begin{aligned} \mathbf b_i^0(t)&=\mathbf b_i,\\ \mathbf b_i^1(t)&=(1-t)\mathbf b_i^0(t)+t\mathbf b_{i+1}^0(t)\\ &=(1-t)\mathbf b_i+t\mathbf b_{i+1}\\ &=\mathbf b_i+t(\mathbf b_{i+1}-\mathbf b_i). \end{aligned}

한 단계를 더 적용하면 2차 다항식이 됩니다.

\begin{aligned} \mathbf b_i^2(t)&=(1-t)\mathbf b_i^1(t)+t\mathbf b_{i+1}^1(t)\\ &=(1-t)[\mathbf b_i+t(\mathbf b_{i+1}-\mathbf b_i)] +t[\mathbf b_{i+1}+t(\mathbf b_{i+2}-\mathbf b_{i+1})]\\ &=[\mathbf b_i+t(\mathbf b_{i+1}-\mathbf b_i)]-t[\mathbf b_i+t(\mathbf b_{i+1}-\mathbf b_i)]\\ &\quad+t[\mathbf b_{i+1}+t(\mathbf b_{i+2}-\mathbf b_{i+1})]\\ &=\mathbf b_i+t(\mathbf b_{i+1}-\mathbf b_i)-t\mathbf b_i-t^2(\mathbf b_{i+1}-\mathbf b_i)\\ &\quad+t\mathbf b_{i+1}+t^2(\mathbf b_{i+2}-\mathbf b_{i+1})\\ &=\mathbf b_i+t(2\mathbf b_{i+1}-2\mathbf b_i)+t^2(\mathbf b_i-2\mathbf b_{i+1}+\mathbf b_{i+2}). \end{aligned}

즉 제어점이 세 개인 2차 베지에 곡선은 단항식 형식으로 다음과 같습니다.

\mathbf p(t)=\mathbf b_0^2(t)=\mathbf b_0+t(2\mathbf b_1-2\mathbf b_0)+t^2(\mathbf b_0-2\mathbf b_1+\mathbf b_2).\tag{13.17}

마지막 보간으로 3차 곡선을 구하기 전에 식 (13.17)의 2차 표현을 더 살펴보겠습니다. 베지에 형식에서 단항식 기저로의 이 변환은 앞에서 도입한 행렬 형식으로 간결하게 쓸 수 있습니다. 제어점

\mathbf b_0,\mathbf b_1,\mathbf b_2

를 행렬

B

의 열로 넣으면 다음과 같습니다.

\mathbf p(t)=C\mathbf t=BM\mathbf t= \begin{bmatrix}|&|&|\\\mathbf b_0&\mathbf b_1&\mathbf b_2\\|&|&|\end{bmatrix} \begin{bmatrix}1&-2&1\\0&2&-2\\0&0&1\end{bmatrix} \begin{bmatrix}1\\t\\t^2\end{bmatrix}.\tag{13.18}

13.3절의 에르미트 곡선에서 보았듯, 곱

BM\mathbf t

를 묶는 두 방식은 두 해석으로 이어집니다.

BM

을 먼저 계산하면 단항식 계수 행렬

C

를 얻습니다. 따라서

M

은 베지에 형식을 단항식 형식으로 바꾸는 변환 행렬입니다. 단항식 형식을 직접 평가하는 편이 드 카스텔조 알고리즘을 실행하는 것보다 빠릅니다. 따라서 같은 곡선을 서로 다른 많은

t

에서 평가해야 하는 상황, 예를 들어 베지에 경로를 따라 시간에 맞춰 물체를 움직일 때는 이 형식이 더 적합할 수 있습니다. 다만 정밀도 문제를 알아 두어야 합니다. 예를 들어

t=1.0

에서 드 카스텔조 알고리즘을 실행하면 마지막 제어점과 정확히 일치하는 결과를 보장할 수 있습니다. 반면 단항식 다항식에

t=1.0

을 대입할 때는 부동소수점 표현 때문에 계수의 합이 그 값과 정확히 같지 않을 수 있습니다.

다른 묶음 방식은 오른쪽 곱을 먼저 수행하는

B(M\mathbf t)

입니다. 특정

t

값을 대입하면

M\mathbf t

는 무게중심 좌표의 열벡터입니다.

t

를 변수로 남긴 채 곱하면 기저로 해석할 수 있는 다항식의 열벡터를 얻습니다. 베지에 곡선의 기저 다항식은 13.4.2절에서 다룰 베른슈타인 기저입니다.

반복 보간으로 돌아가겠습니다. 한 번 더 반복하면 3차 다항식이 나옵니다. 이렇게 모두 전개하고 나면 꽤 진이 빠집니다!

\begin{aligned} \mathbf b_i^3(t)&=(1-t)\mathbf b_i^2(t)+t\mathbf b_{i+1}^2(t)\\ &=(1-t)[\mathbf b_i+t(2\mathbf b_{i+1}-2\mathbf b_i)+t^2(\mathbf b_i-2\mathbf b_{i+1}+\mathbf b_{i+2})]\\ &\quad+t[\mathbf b_{i+1}+t(2\mathbf b_{i+2}-2\mathbf b_{i+1})+t^2(\mathbf b_{i+1}-2\mathbf b_{i+2}+\mathbf b_{i+3})]\\ &=[\mathbf b_i+t(2\mathbf b_{i+1}-2\mathbf b_i)+t^2(\mathbf b_i-2\mathbf b_{i+1}+\mathbf b_{i+2})]\\ &\quad-t[\mathbf b_i+t(2\mathbf b_{i+1}-2\mathbf b_i)+t^2(\mathbf b_i-2\mathbf b_{i+1}+\mathbf b_{i+2})]\\ &\quad+t[\mathbf b_{i+1}+t(2\mathbf b_{i+2}-2\mathbf b_{i+1})+t^2(\mathbf b_{i+1}-2\mathbf b_{i+2}+\mathbf b_{i+3})]\\ &=\mathbf b_i+t(2\mathbf b_{i+1}-2\mathbf b_i)+t^2(\mathbf b_i-2\mathbf b_{i+1}+\mathbf b_{i+2})\\ &\quad-t\mathbf b_i-t^2(2\mathbf b_{i+1}-2\mathbf b_i)-t^3(\mathbf b_i-2\mathbf b_{i+1}+\mathbf b_{i+2})\\ &\quad+t\mathbf b_{i+1}+t^2(2\mathbf b_{i+2}-2\mathbf b_{i+1})+t^3(\mathbf b_{i+1}-2\mathbf b_{i+2}+\mathbf b_{i+3})\\ &=\mathbf b_i+t(3\mathbf b_{i+1}-3\mathbf b_i)+t^2(3\mathbf b_i-6\mathbf b_{i+1}+3\mathbf b_{i+2})\\ &\quad+t^3(-\mathbf b_i+3\mathbf b_{i+1}-3\mathbf b_{i+2}+\mathbf b_{i+3}). \end{aligned}

이번에는 3차 단계가 마지막 재귀 단계라고 가정하여 마지막 줄을 다시 쓰겠습니다.

\begin{aligned} \mathbf p(t)=\mathbf b_0^3(t)&=\mathbf b_0+t(3\mathbf b_1-3\mathbf b_0)+t^2(3\mathbf b_0-6\mathbf b_1+3\mathbf b_2)\\ &\quad+t^3(-\mathbf b_0+3\mathbf b_1-3\mathbf b_2+\mathbf b_3). \end{aligned}\tag{13.19}

놓치지 않도록 강조하자면, 식 (13.19)는 3차 베지에 곡선을 단항식 형식으로 변환하는 방법을 알려 줍니다. 중요한 결과이므로 계수를 명시적으로 다시 적겠습니다.

\begin{aligned} \mathbf c_0&=\mathbf b_0,\\ \mathbf c_1&=-3\mathbf b_0+3\mathbf b_1,\\ \mathbf c_2&=3\mathbf b_0-6\mathbf b_1+3\mathbf b_2,\\ \mathbf c_3&=-\mathbf b_0+3\mathbf b_1-3\mathbf b_2+\mathbf b_3. \end{aligned}

이 변환도 식 (13.18)의 2차 경우처럼 행렬에 넣을 수 있습니다. 곡선 위의 특정 점

\mathbf p(t)

를 구하는 3차 식은 행렬 표기로 다음과 같습니다.

\mathbf p(t)=C\mathbf t=BM\mathbf t= \begin{bmatrix}|&|&|&|\\\mathbf b_0&\mathbf b_1&\mathbf b_2&\mathbf b_3\\|&|&|&|\end{bmatrix} \begin{bmatrix}1&-3&3&-1\\0&3&-6&3\\0&0&3&-3\\0&0&0&1\end{bmatrix} \begin{bmatrix}1\\t\\t^2\\t^3\end{bmatrix}.

이 과정의 역도 가능합니다. 즉 어떤 다항식 곡선이든 단항식 형식에서 베지에 형식으로 바꿀 수 있습니다. 다항식 곡선이 주어지면 그것을 기술하는 베지에 제어점은 유일하게 정해집니다.

\mathbf b_0=\mathbf c_0.\tag{13.20}

\mathbf b_1=\mathbf c_0+\tfrac13\mathbf c_1.\tag{13.21}

\mathbf b_2=\mathbf c_0+\tfrac23\mathbf c_1+\tfrac13\mathbf c_2.\tag{13.22}

\mathbf b_3=\mathbf c_0+\mathbf c_1+\mathbf c_2+\mathbf c_3.\tag{13.23}

물론 이것도 행렬 형식으로 쓸 수 있습니다.

\begin{bmatrix}|&|&|&|\\\mathbf b_0&\mathbf b_1&\mathbf b_2&\mathbf b_3\\|&|&|&|\end{bmatrix} =\begin{bmatrix}|&|&|&|\\\mathbf c_0&\mathbf c_1&\mathbf c_2&\mathbf c_3\\|&|&|&|\end{bmatrix} \begin{bmatrix}1&1&1&1\\0&1/3&2/3&1\\0&0&1/3&1\\0&0&0&1\end{bmatrix}.

[원주 10] 정확히는 그중 일부만 달라질 것입니다. 이번 절도 여전히 유익한 읽을거리이기를 바랍니다. 무슨 뜻인지 알겠지요.

[원주 11] 이런 분들 중 프랑스인이 많다고 말씀드렸지요! 참고로 이름은 “베지에(BEZ-ee-ay)”라고 발음합니다.

[원주 12] 동전 이야기에 이어 “교환 비율(rate of exchange)”이라고 해 두겠습니다. 말장난을 용서해 주시길. [옮긴이 설명: rate는 변화율을, exchange는 금융 거래를 연상시키며 derivatives는 도함수와 파생상품을 함께 뜻합니다.]

[원주 13] 그렇습니다. 이 사람도 프랑스인입니다. 그러니 이름을 제대로 발음하는 편이 좋겠습니다. “드 카스텔조(duh CAS-tul-jho)”입니다. 그는 르노의 경쟁사인 시트로엥에서 일했습니다.

손잡이를 움직이면 무엇이 바뀔까요?

3차 베지에 곡선의 네 제어점을 다음과 같이 두겠습니다.

\mathbf b_0=(0,0),\quad\mathbf b_1=(1,2),\quad\mathbf b_2=(3,2),\quad\mathbf b_3=(4,0).

시작과 끝은

(0,0)

(4,0)

입니다. 처음 속도는

3(\mathbf b_1-\mathbf b_0)=(3,6)

이고 마지막 속도는

3(\mathbf b_3-\mathbf b_2)=(3,-6)

입니다. 두 내부 제어점은 곡선이 반드시 통과할 점이 아니라 출발 및 도착 방향을 잡아 주는 손잡이입니다.

t=1/2

에서 드 카스텔조를 손으로 해 보겠습니다.

첫 보간은 (0.5,1)(0.5,1)(0.5,1), (2,2)(2,2)(2,2), (3.5,1)(3.5,1)(3.5,1) 세 점을 만듭니다.

그 점들을 다시 보간하면 (1.25,1.5)(1.25,1.5)(1.25,1.5), (2.75,1.5)(2.75,1.5)(2.75,1.5)가 됩니다.

마지막 보간 결과는 (2,1.5)(2,1.5)(2,1.5)입니다.

따라서 이 곡선은 중간에 높이 2인 제어점을 지나지 않고, 높이 1.5인 점을 지납니다. 같은 값을 베른슈타인 가중치

(1/8,3/8,3/8,1/8)

로 계산해도 결과는

(2,1.5)

입니다. 기하적 보간과 기저 다항식이 같은 계산이라는 것을 숫자로 확인할 수 있습니다.

시각 실험에서는 먼저

t

를 0에서 1까지 움직이며 네 점 → 세 점 → 두 점 → 한 점의 흐름을 보겠습니다. 다음으로

t=0.5

를 유지하고 제어점

P_1

의 높이를 바꾸겠습니다. 시작점은 고정되지만 출발 접선과 곡선 내부가 바뀝니다. 이는 베지에 제어점의 전역 지지를 보여 줍니다.

13.4.2 베른슈타인 기저

13.4.1절의 마지막에서는 베지에 제어점으로부터 곡선의 다항식을 계산하는 대수 작업을 했습니다. 그 다항식은

t

의 거듭제곱별 계수를 쓰는 단항식 형식이었습니다. 거듭제곱 대신 제어점별로 항을 모으면 다항식을 베지에 형식으로도 쓸 수 있습니다. 이렇게 쓰면 각 제어점에 붙는 계수는 그 제어점이 곡선에 기여하는 무게중심 가중치를

t

의 함수로 나타낸 것이 됩니다.

13.4.1절의 대수 계산을 반복해 보겠습니다. 이번에는 몇 가지 관찰로 이어지도록 식을 조금 다른 방식으로 씁니다. 앞에서처럼 1차의 경우부터 시작합니다.

\mathbf b_i^0=\mathbf b_i

임을 기억하겠습니다.

\begin{aligned} \mathbf b_i^1(t)&=(1-t)\mathbf b_i^0(t)+t\mathbf b_{i+1}^0(t)\\ &=(1-t)\mathbf b_i+t\mathbf b_{i+1}. \end{aligned}

그다음은 2차입니다.

\begin{aligned} \mathbf b_i^2(t)&=(1-t)\mathbf b_i^1(t)+t\mathbf b_{i+1}^1(t)\\ &=(1-t)[(1-t)\mathbf b_i+t\mathbf b_{i+1}]+t[(1-t)\mathbf b_{i+1}+t\mathbf b_{i+2}]\\ &=(1-t)^2\mathbf b_i+t(1-t)\mathbf b_{i+1}+t(1-t)\mathbf b_{i+1}+t^2\mathbf b_{i+2}\\ &=(1-t)^2\mathbf b_i+2t(1-t)\mathbf b_{i+1}+t^2\mathbf b_{i+2}. \end{aligned}

마지막으로 3차입니다.

\begin{aligned} \mathbf b_i^3(t)&=(1-t)\mathbf b_i^2(t)+t\mathbf b_{i+1}^2(t)\\ &=(1-t)[(1-t)^2\mathbf b_i+2t(1-t)\mathbf b_{i+1}+t^2\mathbf b_{i+2}]\\ &\quad+t[(1-t)^2\mathbf b_{i+1}+2t(1-t)\mathbf b_{i+2}+t^2\mathbf b_{i+3}]\\ &=(1-t)^3\mathbf b_i+2t(1-t)^2\mathbf b_{i+1}+t^2(1-t)\mathbf b_{i+2}\\ &\quad+t(1-t)^2\mathbf b_{i+1}+2t^2(1-t)\mathbf b_{i+2}+t^3\mathbf b_{i+3}\\ &=(1-t)^3\mathbf b_i+3t(1-t)^2\mathbf b_{i+1}+3t^2(1-t)\mathbf b_{i+2}+t^3\mathbf b_{i+3}. \end{aligned}

어떤 패턴이 보일 것입니다. 더 분명히 드러나도록 5차까지 적어 보겠습니다. 대수 전개는 위와 비슷하므로 생략합니다.

\mathbf b_0^1(t)=(1-t)\mathbf b_0+t\mathbf b_1.\tag{13.24}

\mathbf b_0^2(t)=(1-t)^2\mathbf b_0+2t(1-t)\mathbf b_1+t^2\mathbf b_2.\tag{13.25}

\mathbf b_0^3(t)=(1-t)^3\mathbf b_0+3t(1-t)^2\mathbf b_1+3t^2(1-t)\mathbf b_2+t^3\mathbf b_3.\tag{13.26}

\begin{aligned} \mathbf b_0^4(t)&=(1-t)^4\mathbf b_0+4t(1-t)^3\mathbf b_1+6t^2(1-t)^2\mathbf b_2\\ &\quad+4t^3(1-t)\mathbf b_3+t^4\mathbf b_4. \end{aligned}\tag{13.27}

원문 수식 교정

제공 PDF의 식 (13.27)은 넷째 항을

4t^3(t-1)\mathbf b_3

로 인쇄했습니다. 이는 부호 오자입니다. 위에서는 베른슈타인 기저 및 그림 13.13과 일치하는

4t^3(1-t)\mathbf b_3

로 바로잡았습니다.

\begin{aligned} \mathbf b_0^5(t)&=(1-t)^5\mathbf b_0+5t(1-t)^4\mathbf b_1+10t^2(1-t)^3\mathbf b_2\\ &\quad+10t^3(1-t)^2\mathbf b_3+5t^4(1-t)\mathbf b_4+t^5\mathbf b_5. \end{aligned}\tag{13.28}

이제 패턴이 더 선명합니다. 각 항에는 상수 계수,

(1-t)

의 거듭제곱,

t

의 거듭제곱이 있습니다.

t

의 지수는 증가하므로

\mathbf b_i

에는

t^i

가 붙습니다.

(1-t)

의 지수는 반대로 감소합니다.

상수 계수의 패턴은 조금 더 복잡합니다. 잠깐 조합론으로 돌아가는 것을 양해해 주세요. 흥미로운 우회가 되기를 바랍니다. 패턴이 잘 보이도록 처음 여덟 줄을 삼각형 모양으로 적겠습니다.

줄 번호                 파스칼의 삼각형
                         1
                       1   1
                     1   2   1
                   1   3   3   1
                 1   4   6   4   1
               1   5  10  10   5   1
             1   6  15  20  15   6   1
           1   7  21  35  35  21   7   1

Plain Text

복사

삼각형 바깥 경계의 1들을 제외하면 모든 수는 바로 위의 두 수를 더한 값입니다. 이것은 수백 년 동안 연구된 매우 유명한 수 패턴이며 이항계수(binomial coefficients)라고 합니다.

n

번째 줄이 이항식

(a+b)^n

을 전개할 때의 계수를 주기 때문입니다.

이런 수들을 삼각형으로 정리하고 싶다는 충동을 느낀 사람은 많았습니다. 수학자이자 물리학자인 블레즈 파스칼(Blaise Pascal, 1623–1662)도 그중 하나입니다.[원주 14] 이항계수를 이렇게 삼각형으로 배열한 것을 파스칼의 삼각형이라고 합니다.[원주 15]

이항계수에는 특별한 표기가 있습니다. 파스칼의 삼각형에서

n

번째 줄의

k

번째 수는 다음처럼 씁니다.

n

과

k

모두 0부터 셉니다.

\binom nk.

예를 들어

\binom62=15

입니다.

\binom nk

는 “

n

choose

k

”, 즉 “

n

개 중

k

개 선택”이라고 읽습니다. 이 값은

n

개의 물체가 있는 집합에서 순서를 무시하고

k

개를 고르는 부분집합의 개수이기도 하기 때문입니다.

이제 이항계수를 계산하는 일반 공식을 살펴보겠습니다. 다만 이 공식은 주로 흥미를 위한 것임을 강조합니다. 이 장에서 곡선을 다루는 데 쓰는 이항계수는 파스칼 삼각형의 처음 몇 줄로 제한되기 때문입니다. 11.4.6절의 팩토리얼 연산자

n!

을 기억하겠습니다. 이는 1부터

n

까지 모든 정수의 곱입니다.

n!=\prod_{i=1}^n i=1\times2\times3\times\cdots\times n.

팩토리얼을 사용하고

0!\equiv1

로 정의하면 이항계수는 다음과 같습니다.

\binom nk=\frac{n!}{k!(n-k)!}.

이항계수는 확률이나 알고리즘 분석처럼 조합과 순열을 다루는 응용에서 자주 등장합니다. 중요하기도 하고 그 안에서 찾을 수 있는 패턴이 놀랄 만큼 많기도 해서 많은 연구가 이루어졌습니다. 크누스 [39]는 이항계수, 특히 컴퓨터 알고리즘에서의 활용을 매우 철저하게 다룹니다.

곡선으로 돌아가겠습니다. 무게중심 가중치의 패턴을 분석했으니, 각 제어점의 가중치를 함수

B_i^n(t)

로 바꾸어 베지에 곡선을 다시 쓰겠습니다. 3차 곡선 식 (13.26)을 예로 들면 다음과 같습니다.

\begin{aligned} \mathbf b_0^3(t)&=(1-t)^3\mathbf b_0+3t(1-t)^2\mathbf b_1+3t^2(1-t)\mathbf b_2+t^3\mathbf b_3\\ &=B_0^3(t)\mathbf b_0+B_1^3(t)\mathbf b_1+B_2^3(t)\mathbf b_2+B_3^3(t)\mathbf b_3. \end{aligned}

일반적으로 제어점이

n+1

개인

n

차 베지에 곡선은 다음과 같습니다.

\mathbf b_0^n(t)=\sum_{i=0}^{n}B_i^n(t)\mathbf b_i.

함수

B_i^n(t)

는 세르게이 베른슈타인(Sergei Bernstein, 1880–1968)의 이름을 딴 베른슈타인 다항식입니다.[원주 16] 이미 그 패턴은 알아냈지만 정확한 공식도 적어 두겠습니다.

B_i^n(t)=\binom ni t^i(1-t)^{n-i},\qquad0\le i\le n.

그림 13.13은 4차까지의 베른슈타인 다항식 그래프입니다.

그림 13.13 — 구성 이미지 1

그림 13.13 — 구성 이미지 2

그림 13.13 — 구성 이미지 3

그림 13.13 — 구성 이미지 4

그림 13.13. 1차부터 4차까지의 베른슈타인 다항식.

베른슈타인 다항식의 성질을 보면 베지에 곡선이 어떻게 행동하는지 많이 알 수 있습니다. 몇 가지 성질을 자세히 살펴보겠습니다.

합이 1입니다. 베른슈타인 다항식은 모든

t

에서 합이 1입니다. 그렇지 않으면 올바른 무게중심 좌표가 되지 않으므로 반가운 성질입니다. 그림 13.13을 눈으로 보거나 식을 대충 훑는 것만으로는 바로 드러나지 않지만 증명할 수 있습니다. 2차의 경우를 직접 증명하고 싶다면 연습문제 4를 참고해 보세요.

볼록 껍질 성질. 베른슈타인 다항식의 값은 곡선 전체 구간

0\le t\le1

에서 0부터 1 사이에 있습니다. 앞의 성질과 결합하면 베지에 곡선이 볼록 껍질 성질을 따른다는 뜻입니다. 즉 곡선은 제어점의 볼록 껍질 안에 머뭅니다.

[0,1]

구간 안에 머물지 않는 라그랑주 기저 다항식과 비교해 보겠습니다. 그 때문에 다항식 보간은 볼록 껍질 성질을 따르지 않습니다. 그림 13.4에서 보았던 바람직하지 않은 “지나침” 현상이 그 결과 중 하나입니다.

끝점을 보간합니다. 처음과 마지막 다항식은 우리가 필요한 곳에서 1에 도달합니다.

B_0^n(0)=1

B_n^n(1)=1

이므로 곡선은 양 끝점을 지납니다. 기저 다항식 중 어느 것이든 1에 도달하는 곳은

t=0,1

뿐입니다. 그래서 다른 제어점들은 보간되지 않고 근사됩니다.

전역 지지(global support). 모든 다항식은 열린 구간

(0,1)

, 즉 양 끝점을 제외한 곡선 전체에서 0이 아닙니다. 제어점의 혼합 가중치가 0이 아닌 영역을 그 제어점의 지지 영역(support)이라고 합니다. 제어점은 지지 영역 안의 곡선에 영향을 줍니다.

베른슈타인 다항식은 양 끝점을 제외한 모든 곳에서 0이 아니므로 베지에 제어점은 전역 지지를 갖습니다. 실용적으로는 어떤 제어점 하나를 움직여도 곡선 전체가 영향을 받는다는 뜻입니다. 곡선 설계에 바람직한 성질은 아닙니다. 곡선의 한 구간을 원하는 모양으로 만들었다면 멀리 떨어진 다른 제어점을 편집하더라도 이미 마음에 드는 구간이 흔들리지 않기를 바랍니다.

이런 부러운 상황을 국소 지지(local support)라고 합니다. 특정 제어점을 움직일 때 그 점의 “가까운” 부분만 영향을 받는다는 뜻입니다. 여기서 가까움의 정의는 방식에 따라 달라질 수 있습니다.

국소 지지란 기저 함수가 어떤 구간 안에서만 0이 아니고, 그 구간 밖에서는 0이라는 뜻입니다. 안타깝게도 그런 기저 함수는 하나의 다항식으로 표현할 수 없습니다. 따라서 하나의 다항식 곡선으로는 국소 제어를 얻을 수 없습니다. 하지만 작은 곡선들을 알맞게 이어 스플라인을 만들면 국소 지지가 가능합니다. 13.6절에서 설명합니다.

극댓값이 하나입니다. 각 제어점은 곡선 전체에 영향을 주지만, 가장 큰 영향을 주는 곳은 곡선 위의 특정한 한 지점입니다. 제어점

\mathbf b_i

의 혼합 가중치인 베른슈타인 다항식

B_i^n(t)

는 정확히

t=i/n

일 때 하나의 최댓값을 갖습니다. 또한 그때

\mathbf b_i

의 가중치는 다른 어느 제어점보다 큽니다.

따라서 베지에 제어점의 지지가 전역적이어서 곡선 내부의 모든 점이 모든 제어점의 영향을 어느 정도 받기는 하지만, 가장 가까운 제어점의 영향이 가장 큽니다.

추가 설명 — 여기서 “가깝다”의 뜻

마지막 문장은

t=i/n

이라는 매개변수상의 대응을 가리킵니다. 공간에서 유클리드 거리가 가장 짧은 제어점이 언제나 최대 가중치를 갖는다는 뜻은 아닙니다. 제어점을 어디로 옮기든

B_i^n(t)

자체는 제어점의 위치와 무관합니다.

[원주 14] 그렇습니다. 그도 프랑스인이었습니다. 이언 파베리의 박사 지도교수 계보를 16대 거슬러 올라가 약간 왼쪽으로 가면 그가 나타납니다.

[원주 15] 파스칼에게는 삼각형 외에도 압력의 SI 단위, 법칙, 프로그래밍 언어, 내기가 그의 이름으로 붙어 있습니다. 다만 마지막 두 가지는 이제 진지하게 사용되지 않습니다. [옮긴이 설명: 원문의 농담을 옮긴 것이며, 현재의 프로그래밍 언어 사용 실태를 조사한 진술은 아닙니다.]

[원주 16] 프랑스인이 아니라 러시아인입니다.

13.4.3 베지에 곡선의 도함수와 에르미트 형식의 관계

베지에 곡선의 도함수를 살펴보겠습니다. 여기서도 3차 곡선을 예로 들 것이므로 속도와 가속도를 이야기하게 됩니다. 속도는 곡선의 접선, 즉 방향과 관계가 있고, 가속도는 곡률과 관계가 있다는 것을 기억하겠습니다.

13.1.6절에서는 단항식 계수로부터 곡선의 속도 함수를 얻는 방법을 보았습니다.

\begin{aligned} \mathbf p(t)&=\mathbf c_0+\mathbf c_1t+\mathbf c_2t^2+\mathbf c_3t^3,\\ \mathbf v(t)=\dot{\mathbf p}(t)&=\mathbf c_1+2\mathbf c_2t+3\mathbf c_3t^2. \end{aligned}\tag{13.29}

13.4.1절에서는 3차 베지에 곡선으로부터 단항식 계수를 구했습니다.

\begin{aligned} \mathbf c_0&=\mathbf b_0,\\ \mathbf c_1&=3\mathbf b_1-3\mathbf b_0,\\ \mathbf c_2&=3\mathbf b_0-6\mathbf b_1+3\mathbf b_2,\\ \mathbf c_3&=-\mathbf b_0+3\mathbf b_1-3\mathbf b_2+\mathbf b_3. \end{aligned}

이 계수들을 속도 식 (13.29)에 대입하면 베지에 제어점으로 곡선의 순간 속도를 나타내는 공식을 얻습니다.

\begin{aligned} \mathbf v(t)&=\mathbf c_1+2\mathbf c_2t+3\mathbf c_3t^2\\ &=(3\mathbf b_1-3\mathbf b_0)+2(3\mathbf b_0-6\mathbf b_1+3\mathbf b_2)t\\ &\quad+3(-\mathbf b_0+3\mathbf b_1-3\mathbf b_2+\mathbf b_3)t^2. \end{aligned}

양 끝점

t=0,1

에서의 속도를 생각해 보겠습니다.

\begin{aligned} \mathbf v(0)&=(3\mathbf b_1-3\mathbf b_0)+2(3\mathbf b_0-6\mathbf b_1+3\mathbf b_2)(0)\\ &\quad+3(-\mathbf b_0+3\mathbf b_1-3\mathbf b_2+\mathbf b_3)(0)^2\\ &=3(\mathbf b_1-\mathbf b_0). \end{aligned}\tag{13.30}

\begin{aligned} \mathbf v(1)&=(3\mathbf b_1-3\mathbf b_0)+2(3\mathbf b_0-6\mathbf b_1+3\mathbf b_2)(1)\\ &\quad+3(-\mathbf b_0+3\mathbf b_1-3\mathbf b_2+\mathbf b_3)(1)^2\\ &=3\mathbf b_1-3\mathbf b_0+6\mathbf b_0-12\mathbf b_1+6\mathbf b_2-3\mathbf b_0+9\mathbf b_1-9\mathbf b_2+3\mathbf b_3\\ &=3(\mathbf b_3-\mathbf b_2). \end{aligned}\tag{13.31}

흥미로운 결과입니다.

\mathbf b_1-\mathbf b_0

는 첫 번째 제어점에서 두 번째 제어점으로 향하는 벡터이고,

\mathbf b_3-\mathbf b_2

는 세 번째 제어점에서 마지막 제어점으로 향하는 벡터입니다. 따라서

t=0

에서 곡선의 시작 접선은 첫 내부 제어점을 “향하고”,

t=1

에서 끝 접선은 마지막 내부 제어점에서 끝점으로 향하는 벡터와 평행합니다.

실제로

t

가 증가하는 방향으로 곡선을 따라 움직인다고 생각하면

t=1

의 접선은 세 번째 제어점에서 곧바로 멀어지는 방향입니다. 이것은 핵심적인 관찰입니다.

베지에 제어 다각형의 첫 번째 변은 곡선 시작점의 1차 도함수를 완전히 결정하고, 마지막 변은 끝점의 1차 도함수를 완전히 결정합니다. 이 도함수가 0이 아니라면 접선 방향도 정해집니다.

3차 베지에 곡선의 중간 제어점이 하는 일을 보는 또 다른 방법은 베지에 형식과 에르미트 형식의 관계를 살펴보는 것입니다. 3차 에르미트 형식은 초기 위치

\mathbf p_0

와 속도

\mathbf v_0

, 최종 위치

\mathbf p_1

와 속도

\mathbf v_1

를 포함합니다. 이제 베지에 제어점과 곡선 속도의 관계를 알았으므로 베지에에서 에르미트로 쉽게 바꿀 수 있습니다.

원문 표기 교정

이 대목의 제공 PDF에는 초기 속도가

\mathbf p_1

로 인쇄되어 있습니다.

\mathbf v_0

의 오자입니다. 또한 앞 문단의 “첫 제어점”은 시작점 자체가 아니라 첫 내부 제어점

\mathbf b_1

을 가리킵니다.

\mathbf p_0=\mathbf b_0.\tag{13.32}

\mathbf v_0=3(\mathbf b_1-\mathbf b_0).\tag{13.33}

\mathbf v_1=3(\mathbf b_3-\mathbf b_2).\tag{13.34}

\mathbf p_1=\mathbf b_3.\tag{13.35}

반대로 에르미트에서 베지에로 변환할 수도 있습니다.

\begin{aligned} \mathbf b_0&=\mathbf p_0,\\ \mathbf b_1&=\mathbf p_0+\tfrac13\mathbf v_0,\\ \mathbf b_2&=\mathbf p_1-\tfrac13\mathbf v_1,\\ \mathbf b_3&=\mathbf p_1. \end{aligned}

이처럼 에르미트와 베지에 형식은 밀접히 연결되어 있으며 서로 매우 쉽게 변환할 수 있습니다. 그림 13.14는 그 관계를 기하학적으로 보여 줍니다.

그림 13.14

그림 13.14. 베지에 형식과 에르미트 형식의 관계.

양 끝점의 1차 도함수는 각각 가장 가까운 베지에 제어점 두 개로 완전히 결정된다고 했습니다. 이를 더 일반화할 수 있습니다. 양 끝점의

n

차 도함수는 각각 가장 가까운

n+1

개의 제어점으로 완전히 결정됩니다. “0차 도함수”, 즉 곡선의 위치는 보간되는 제어점 하나로 완전히 결정됩니다. 1차 도함수는 이미 설명했습니다.

끝점의 2차 도함수, 즉 가속도는 가장 가까운 세 제어점으로 정해집니다. 실제로 3차 곡선의 가속도가 베지에 제어점으로 어떻게 표현되는지 살펴보겠습니다. 가속도 식 (13.6)을 단항식 형식에서 베지에 형식으로 바꾸면 다음과 같습니다.

\begin{aligned} \mathbf a(t)&=2\mathbf c_2+6\mathbf c_3t\\ &=2(3\mathbf b_0-6\mathbf b_1+3\mathbf b_2)+6(-\mathbf b_0+3\mathbf b_1-3\mathbf b_2+\mathbf b_3)t\\ &=(6\mathbf b_0-12\mathbf b_1+6\mathbf b_2)+(-6\mathbf b_0+18\mathbf b_1-18\mathbf b_2+6\mathbf b_3)t. \end{aligned}

양 끝점의 가속도는 다음과 같습니다.

\begin{aligned} \mathbf a(0)&=(6\mathbf b_0-12\mathbf b_1+6\mathbf b_2)+(-6\mathbf b_0+18\mathbf b_1-18\mathbf b_2+6\mathbf b_3)0\\ &=6\mathbf b_0-12\mathbf b_1+6\mathbf b_2,\\ \mathbf a(1)&=(6\mathbf b_0-12\mathbf b_1+6\mathbf b_2)+(-6\mathbf b_0+18\mathbf b_1-18\mathbf b_2+6\mathbf b_3)1\\ &=6\mathbf b_1-12\mathbf b_2+6\mathbf b_3. \end{aligned}

예상대로 시작 가속도는 처음 세 제어점으로, 끝 가속도는 마지막 세 제어점으로 완전히 결정됩니다.

연속한 제어점 사이의 차이, 즉 베지에 제어 다각형의

i

번째 변 벡터를 간단히

\mathbf d_i=\mathbf b_{i+1}-\mathbf b_i

로 쓰겠습니다. 이 표기를 사용하면 가속도 공식이 속도 공식과 놀라울 만큼 비슷해집니다.

\begin{aligned} \mathbf a(0)&=6\mathbf b_0-12\mathbf b_1+6\mathbf b_2 =6\mathbf b_0-6\mathbf b_1-6\mathbf b_1+6\mathbf b_2\\ &=6[(\mathbf b_2-\mathbf b_1)-(\mathbf b_1-\mathbf b_0)]\\ &=6(\mathbf d_1-\mathbf d_0). \end{aligned}\tag{13.36}

\begin{aligned} \mathbf a(1)&=6\mathbf b_1-12\mathbf b_2+6\mathbf b_3 =6\mathbf b_1-6\mathbf b_2-6\mathbf b_2+6\mathbf b_3\\ &=6[(\mathbf b_3-\mathbf b_2)-(\mathbf b_2-\mathbf b_1)]\\ &=6(\mathbf d_2-\mathbf d_1). \end{aligned}\tag{13.37}

위 논의는 어떤 차수의 베지에 곡선에도 적용됩니다. 일반적인 패턴은 이렇습니다. 제어점

\mathbf b_i

를 움직이면 곡선 시작점의

i

차 이상 도함수에 영향을 주지만, 그보다 낮은 차수의 도함수에는 영향을 주지 않습니다. 끝점에서도 비슷합니다. 제어점

\mathbf b_i

는

n-i

차 이상 도함수에 영향을 줍니다.

여기서는 3차 곡선 구간 하나를 기준으로 읽어야 합니다. 그 구간의 제어점을 바꾸면 구간 전체의 3차 도함수가 바뀔 수 있습니다. 3차 다항식의 3차 도함수는 상수이고 그보다 높은 도함수는 모두 0이기 때문입니다. 여러 구간으로 이루어진 스플라인 전체에 무조건 같은 영향이 퍼진다는 뜻은 아닙니다. 두 개 이상의 베지에 곡선 구간을 스플라인으로 이었을 때의 연속 조건을 다루는 13.8.1절에서 다시 살펴봅니다.

같은 직선, 다른 움직임

시작점

A

, 끝점

B

를 잇는 곡선에도 여러 시간 배치가 가능합니다.

의도	3차 베지에 제어점	움직임
일정한 속도	$A,\ A+(B-A)/3,\ A+2(B-A)/3,\ B$	$\mathbf p(t)=A+t(B-A)$
부드럽게 출발·정지	$A,\ A,\ B,\ B$	$\mathbf p(t)=A+(3t^2-2t^3)(B-A)$

두 곡선의 공간상 모양은 같습니다. 두 번째는 양 끝에서 속도가 0이고 중간에서 가장 빠릅니다. 카메라가 고정된 두 위치 사이를 이동할 때 출발과 정지를 부드럽게 만들고 싶다면 이 차이가 중요합니다.

곡률은 가속도의 크기와 같지 않다

원문의 곡률 공식은 속도가 0이 아닌 곳에 적용합니다.

\kappa=\frac{\|\mathbf v\times\mathbf a\|}{\|\mathbf v\|^3}.

직선에서 속력을 높이는 경우에도 가속도는 있지만

\mathbf v

와

\mathbf a

가 평행이므로 곡률은 0입니다. 반대로 일정한 속력으로 원을 돌아도 속도의 방향이 바뀌므로 가속도가 있습니다. 곡률은 경로의 굽음을 나타내고, 가속도는 속력과 진행 방향의 변화 모두를 포함합니다. 정지점에서는 분모가 0이므로 공식을 그대로 평가하지 않습니다.

13.5 세분화 (Subdivision)

13.6절부터는 곡선들을 이어 원하는 만큼 길고 복잡한 스플라인을 만드는 문제를 다룹니다. 그 전에 이번 절에서는 반대 문제, 즉 곡선을 더 작은 조각으로 나누는 방법을 살펴보겠습니다.

왜 이런 일을 할까요? 몇 가지 이유가 있습니다.

•

곡선 세밀화. 곡선을 대화식으로 설계하다 보면 거의 원하는 모양에 도달했지만, 곡선 하나만으로는 필요한 유연성이 조금 모자랄 수 있습니다. 이때 곡선을 둘로 잘라 스플라인으로 만들면 더 자유롭게 조절할 수 있습니다.

•

근사 기법. 곡선의 일부는 보통 곡선 전체보다 단순합니다. 여기서 단순하다는 것은 직선에 더 가깝다는 뜻입니다. 따라서 충분히 많은 조각으로 자른 뒤, 그 조각들을 직선 구간처럼 취급하여 렌더링하거나 광선 추적할 수 있습니다. 이렇게 하면 곡선을 해석적으로 렌더링하거나 광선 추적했을 때의 결과를 근사합니다. 엄밀히 말해 구간별 선형 근사에 세분화가 반드시 필요한 것은 아닙니다. 이미 일정 간격으로 곡선을 평가한 표본점들을 직선으로 연결하는 간단한 방법을 설명했습니다. 다만 세분화를 쓰면 직선에 가까운 부분에는 적은 선분을, 더 많이 휜 부분에는 많은 선분을 쓰도록 선분 수를 적응적으로 선택할 수 있습니다.

이것이 곡선 세분화를 하는 “이유”입니다. “방법”을 배우기 전에 “무엇을” 하려는지 조금 더 정확히 정하겠습니다. 함수

\mathbf p(t)

로 정의되는 매개변수 다항식 곡선

P

를 생각하겠습니다. 늘 그렇듯 시작은

t=0

, 끝은

t=1

로 합니다. 이제 임의의 시점

t=a

에서 시작하여

t=b

에서 끝나는 구간

Q

를 생각하겠습니다. 그림 13.15에 나타냈습니다.

그림 13.15

그림 13.15. 세분화로 곡선의 일부 구간 추출하기.

세분화의 목표는

Q

를 단항식·에르미트·베지에 중 어떤 형식으로든 수학적으로 기술하는 것입니다. 그런데 이미 그 기술이 있지 않을까요? 애초에

P

의 수학적 기술이 어떤 형식으로든 주어졌다고 가정했으므로 “

P

로 정의한 곡선을 취하되, 0에서 시작하고 1에서 끝내는 대신

a

에서 시작하고

b

에서 끝내라”라고

Q

를 정의하는 것은 완전히 타당합니다.

하지만 그것은 우리가 정말 원하는 것이 아닙니다.

Q

가

P

를 참조하지 않는 완전히 독립적인 “보통의” 곡선이기를 원합니다. 다른 곡선에 종속되거나 추가 조건이 붙은 형태를 원하는 것이 아닙니다. 예를 들어 베지에 형식을 쓴다면

Q

를 정의하는 새로운 베지에 제어점들을 얻고 싶습니다.

다음 두 절은 곡선을 세분화하는 서로 다른 방법을 제시합니다. 13.5.1절은 단항식 형식에 대한 직접적인 대수 접근법입니다. 13.5.2절은 기하학에 바탕을 두어 우아하고 효율적인 구현으로 이어지는 베지에 곡선 세분화를 다룹니다.

에르미트 형식은 세분화에 자연스럽게 들어맞지 않습니다. 에르미트 곡선을 세분화하려면 먼저 다른 형식, 아마도 베지에로 바꾼 다음 그 형식에서 세분화합니다.

13.5.1 단항식 형식의 곡선 세분화

단항식 형식에서 곡선의 일부 구간을 추출하는 것은 직접적인 대수 작업입니다. 단항식 형식은 단지

t

에 대한 명시적인 다항식이라는 것을 기억하겠습니다. 대개

0\le t\le1

부분에만 관심이 있지만, 다항식은 모든

t

에서 정의되므로 실제로는 무한한 곡선을 정의합니다. 추출하려는 작은 구간

Q

도 같은 무한 곡선의 다른 부분일 뿐입니다.

이를 생각하면 세분화 문제를 간단한 재매개변수화(reparameterization) 문제로 볼 수 있습니다. 단항식 계수를 직접 이리저리 조작하는 대신 매개변수에 대수를 적용합니다.

\mathbf q(s)

가 곡선

Q

를 그리는 동안 0에서 1까지 변하는 국소 매개변수

s

를 도입하겠습니다. 그러면

\mathbf p(t)

를 통해

\mathbf q(s)

를 다음과 같이 정의할 수 있습니다.

\begin{aligned} t&=F(s),\\ \mathbf q(s)&=\mathbf p(t)=\mathbf p(F(s)). \end{aligned}

F(s)

는 국소 매개변수

s

에 대응하는 전역 매개변수

t

를 돌려주는 재매개변수화 함수입니다. 끝점 조건

F(0)=a

F(1)=b

를 만족해야 하므로

F

의 형태를 찾기는 어렵지 않습니다.

t

와

s

사이에 간단한 선형 관계를 쓰면 다음과 같습니다.

t=F(s)=a+s(b-a).

양 끝점에서 정말 올바르게 작동하는지 확인해 보아도 좋습니다.

물론 지금까지 한 일은

Q

를

P

로 정의한 것뿐입니다. 이번 절 시작에서 바로 그런 정의만으로는 부족하다고 말했습니다. 차이는 여기서 수학을 계속 전개하고

\mathbf p(t)

의 식을 대입한 뒤

t

를 없애면

\mathbf q(s)

의 직접적인 식을 얻을 수 있다는 점입니다. 그러면 처음 세운 목표에 맞는 독립적인 “보통의” 곡선이 됩니다.

그러나 이어지는 대수 노동은 특별한 통찰 없이 지저분한 결과만 만듭니다. 여기서 전달하려는 핵심은 단항식 곡선의 세분화가 대수로 해결할 수 있는 간단한 재매개변수화 문제라는 점입니다. 또한 단항식 형식과 다른 형식 사이를 변환할 수 있으므로 어떤 형식의 다항식 곡선이라도 확실히 세분화하는 방법을 이제 갖추었습니다.

하지만 이런 “무식한” 접근법에 만족할 필요는 없습니다. 베지에 형식에서는 더 나은 방법이 있습니다.

13.5.2 베지에 형식의 곡선 세분화

베지에 곡선은 드 카스텔조 알고리즘의 변형을 통해 기하학적으로 세분화할 수 있습니다. 임의의 끝 매개변수

a,b

에 대한 구간을 추출하는 전체 알고리즘은 한 번에 이해하기 어려우므로, 파린 [20, 7.2절 이후]을 따라 간단한 경우부터 시작합니다.

먼저 곡선의 “왼쪽 부분”만 추출한다고 제한하겠습니다. 즉

a=0

으로 고정합니다. 작은 곡선의 첫 베지에 제어점

s=0

은 큰 곡선의 첫 제어점

t=0

과 같음이 분명합니다. 끝점

t=b

역시 13.4.1절의 기본 드 카스텔조 알고리즘으로 구할 수 있습니다. 그림 13.16은

b=0.75

인 예입니다.

그림 13.16

그림 13.16. 드 카스텔조 알고리즘으로 내부 끝점 찾기.

양 끝점은 얻었습니다. 이제 까다로운 내부 제어점들 차례입니다. 놀랍게도 그림 13.16을 자세히 보면 이미 그 점들도 구성했다는 것을 알 수 있습니다! 드 카스텔조 보간을 한 단계 수행할 때마다 필요한 베지에 제어점 하나가 나옵니다. 그림 13.17은 선택된 베지에 점과 제어 다각형을 보여 주어 이 사실을 분명하게 만듭니다.

그림 13.17

그림 13.17. 드 카스텔조 알고리즘으로 추출한 곡선 구간의 모든 베지에 제어점을 얻습니다.

왜 작동할까요? 13.4.3절의 베지에와 에르미트 관계를 떠올려 보겠습니다. 첫 내부 제어점

\mathbf b_1

은

t=0

에서 1차 도함수, 즉 속도를 완전히 결정합니다. 추출한 부분 곡선은 같은 무한 곡선의 일부이므로 기하학적으로는 위치와 도함수가 모든 곳에서 일치합니다.

하지만 도함수는 매개변수의 변화에 대한 변화율입니다. 세분화하면 더 작은 공간 구간에서 매개변수가 0부터 1까지 가므로 매개변수를 “더 빨리” 움직이게 한 셈입니다. 따라서 부분 곡선의 도함수는 같은 방향이지만, 추출한 곡선의 비율만큼 더 짧습니다. 여기서는 그 비율이

b

입니다.

추가 설명 — 매개변수 구분

위 문장의 “0부터 1”은 부분 곡선의 국소 매개변수

s

를 말합니다. 원래 매개변수는

t=bs

이므로

d\mathbf q/ds=b\,d\mathbf p/dt

입니다. 공간상 접선 방향은 같지만 속도 벡터의 크기는

b

배입니다. 원문은 이 설명에서 매개변수 기호를

t

로 함께 사용합니다.

지금까지 알아낸 내용을 정리하겠습니다. 왼쪽 부분

0\le t\le b

를 추출하려면 끝점

t=b

를 찾듯이 드 카스텔조 세분화를 수행합니다. 매 보간 단계의 첫 제어점을 모으면 세분화된 곡선의 제어점들이 됩니다. 오른쪽 부분을 추출하는 방법도 비슷하므로 자세한 설명은 생략합니다.

지금까지의 지식만으로 처리할 수 있는 중요한 특수 경우가 있습니다. 곡선을

t=1/2

에서 “반으로” 나누는 것입니다. 이 계산을 이용하면 적응적 세분화에 대한 우아한 재귀 알고리즘을 만들 수 있습니다. 원래 베지에 제어점에는 늘 쓰던 표기

\mathbf b_i

를 쓰겠습니다. 왼쪽과 오른쪽 반쪽의 제어점에는 임의로 고른 두 글자

\mathbf q_i,\mathbf r_i

를 각각 쓰겠습니다. 일곱 제어점은 다음과 같습니다.

\begin{aligned} \mathbf q_0&=\mathbf b_0,\\ \mathbf q_1&=\mathbf b_0/2+\mathbf b_1/2,\\ \mathbf q_2&=\mathbf b_0/4+\mathbf b_1/2+\mathbf b_2/4,\\ \mathbf q_3=\mathbf r_0&=\mathbf b_0/8+3\mathbf b_1/8+3\mathbf b_2/8+\mathbf b_3/8,\\ \mathbf r_1&=\mathbf b_1/4+\mathbf b_2/2+\mathbf b_3/4,\\ \mathbf r_2&=\mathbf b_2/2+\mathbf b_3/2,\\ \mathbf r_3&=\mathbf b_3. \end{aligned}

일반적인 경우는 블로서밍(blossoming)으로 얻습니다. 이는 서로 다른 보간 비율로 드 카스텔조 단계를 반복하는 여러 기법을 가리키는 일반 용어입니다. 각 제어점을 결정하려면 적어도 3차 곡선에서는 드 카스텔조 단계를 세 번 밟습니다. 각 제어점

\mathbf b_i

에 대해 그중

i

번은

t=b

를, 나머지는

t=a

를 씁니다.

어느 단계에서

a

를 쓰고 어느 단계에서

b

를 쓰는지는 중요하지 않습니다. 중요한 것은 각각을 쓰는 횟수입니다.

3차 곡선의 각 점을 생각하면 명확해집니다.

\mathbf b_0

를 계산할 때는 세 단계 모두 보간 비율

t=a

를 씁니다.

\mathbf b_1

에서는 두 단계에

t=a

, 한 단계에

t=b

를 씁니다.

\mathbf b_2

는 한 단계에만

t=a

를 쓰고 다른 두 단계에는

t=b

를 씁니다. 마지막 제어점

\mathbf b_3

는 이번 절 시작에서 설명한 것처럼 세 단계 모두

t=b

를 씁니다.

추가 설명 — 마지막 문단의 첨자

여기서 계산한다고 말한

\mathbf b_0,\ldots,\mathbf b_3

는 추출 결과의 새 제어점들입니다. 구현에서는 원래 제어점 배열과 구분하여

\mathbf q_0,\ldots,\mathbf q_3

처럼 다른 이름을 쓰면 혼동을 줄일 수 있습니다.

13.6 스플라인 (Splines)

지금까지 3차 곡선에 집중한 데에는 좋은 이유가 있습니다. 3D에서 가장 널리 쓰이는 종류이기 때문입니다. 제어점 네 개의 베지에 곡선이든, 계수 네 개의 단항식 곡선이든, 양 끝점과 두 도함수를 갖는 에르미트 곡선이든 본질적으로 네 개의 벡터값으로 정의됩니다. 각 좌표에 스칼라 자유도가 네 개 있다는 뜻입니다. 따라서 3차 곡선 하나만으로 표현할 수 있는 모양에는 상당한 제한이 있습니다.

작은 곡선들을 스플라인(spline)으로 이어 붙이면 더 큰 자유를 얻습니다. 이 장의 나머지에서 다룰 주제입니다. 스플라인에 들어가기 전에 가능한 다른 대안인 더 높은 차수의 다항식을 잠깐 생각해 보겠습니다. 어떤

n

차 곡선도

n+1

차 곡선으로 바꿀 수 있음은 분명합니다. 이 변환을 차수 올리기(degree elevation)라고 합니다. 단항식 형식에서는 간단합니다. 새 최고차항의 계수로 0을 추가하면 됩니다.

베지에 형식에서 차수 올리기는 새 제어점 하나를 추가합니다. 짐작했겠지만 새 제어점 위치는 선형 보간으로 기하학적으로 구성할 수 있습니다.

n+1

개의 제어점

\mathbf b_i

를 가진

n

차 곡선이 주어졌을 때, 차수를 올리면

n+2

개의 제어점

\mathbf b'_j

를 가진

n+1

차 곡선이 됩니다. 새 제어점을 결정할 때는 제어점 첨자에 비례하는 보간 비율로 선형 보간합니다.

\mathbf b'_j=\frac{j}{n+1}\mathbf b_{j-1}+\left(1-\frac{j}{n+1}\right)\mathbf b_j,\qquad0\le j\le n+1.\tag{13.38}

존재하지 않는 점

\mathbf b_{-1}

도 가중치 0으로 “혼합”된다는 데 주의하겠습니다.

구현 설명 및 원문 표기 교정

제공 PDF의 이 설명은 존재하지 않는 점을

\mathbf b'_{-1}

로 표기하지만 식에는 원래 점

\mathbf b_{-1}

이 들어갑니다. 반대 끝에서는

\mathbf b_{n+1}

역시 가중치 0입니다. 실제 배열 접근은 하지 말고

\mathbf b'_0=\mathbf b_0

\mathbf b'_{n+1}=\mathbf b_n

을 별도로 대입한 뒤 내부 점에만 식을 적용합니다.

에르미트 곡선에서는 보통 양 끝점에서 같은 수의 도함수를 지정할 수 있도록

n

이 홀수인 경우에만 관심을 둡니다.

더 높은 차수의 다항식은 더 많이 “굽이치는” 곡선을 표현할 수 있습니다. 하지만 일반적으로 몇 가지 단점이 있습니다.

•

곡선이 전역 지지를 갖습니다. 각 제어점은 양 끝점을 제외한 곡선의 모든 점에 0이 아닌 가중치로 영향을 줍니다.

•

원하지 않는 곳에 불필요한 “굽이침”이 생겨 제어점 사이에서 이리저리 진동하기도 합니다. 이를 룽게 현상(Runge phenomenon)이라고 합니다.[원주 17]

•

이 불필요한 굽이침과 어느 정도 관련된 또 다른 사실은 고차 곡선이 매우 민감하다는 것입니다. 전역 지지 때문에 제어점 하나의 변화가 곡선 전체를 바꾸며, 높은 민감도 때문에 그 반응이 매우 클 수 있습니다.

•

다항식 보간을 실용적인 곡선 설계 도구에서 제외했으므로, 양 끝점 외에는 곡선이 반드시 통과하기를 원하는 점을 직접 지정할 수 없습니다.

근본 문제는 다항식 하나에 너무 많은 일을 요구한다는 것입니다. 스플라인에는 이런 단점이 없습니다.

이제 어떤 내용을 다룰지 보겠습니다. 먼저 논의를 편하게 하기 위해 표기를 확장하고 국소 매개변수화와 전역 매개변수화 사이에 간접 단계를 도입합니다. 13.6.1절과 13.6.2절에서 합니다. 이어 13.7절에서 Adobe Photoshop, Autodesk 3DS Max 등 많은 소프트웨어 패키지에서 사용하는 에르미트 및 베지에 스플라인을 설명합니다.

그러면 자연히 “이음매”에서 무엇을 해야 하는지로 관심이 옮겨 갑니다. 첫 과제는 연결점에서 곡선이 매끄러우려면 어떤 기준을 만족해야 하는지 정의하는 것입니다. 이런 연속 조건이 13.8절의 주제입니다. 이 문제들을 이해하고 나면 이 장의 처음에 세운 목표, 즉 곡선의 모양을 직관적으로 정의할 수 있는 스플라인 시스템에 드디어 도달합니다.

각 제어점의 위치와 접선을 사용자가 지정할 수 있는 유연한 설계 도구를 만든 뒤, 13.9절에서는 설계자가 제어점의 위치만 지정하고 접선은 직관적인 사용자 제어값에 따라 자동으로 계산하는 방법을 조사합니다.

13.6.1 기본 규칙

스플라인은

\mathbf q_0,\mathbf q_1,\ldots,\mathbf q_{n-1}

로 표기하는

n

개의 구간으로 구성됩니다.

i

번째 구간

\mathbf q_i

는 국소 매개변수

s_i

를 받는 함수입니다. 이 매개변수는 구간 전체에서 0부터 1까지 변하도록 정규화합니다. 즉 각 구간에는 이 장 앞부분에서 공부한 것과 똑같은 곡선 함수

\mathbf q_i(s_i)

가 있습니다.

달라진 것은 함수 이름을

\mathbf p

에서

\mathbf q_i

로, 인수 이름을

t

에서

s_i

로 바꾼 겉모양뿐입니다.

전체 스플라인을 가리킬 때는 두 표기를 씁니다. 하나는 위 표기에서 아래첨자를 빼는 것입니다. 함수

\mathbf q(s)

는 전체 스플라인을 가리키고, 첨자가 없는

s

는 전역 매개변수입니다.

s

가 0에서

n

까지 변하면

\mathbf q(s)

가 전체 스플라인을 그립니다.

합성 함수

\mathbf q(s)

는 아주 간단합니다. 기본적으로

s

의 정수 부분을 취해 현재 구간의 첨자

i

를 구하고, 소수 부분을

s_i

로 삼아 구간

\mathbf q_i

에 넣습니다. 따라서 첫 구간

\mathbf q_0(s_0)

는

\mathbf q(0)

부터

\mathbf q(1)

사이를 정의하고, 두 번째 구간은

\mathbf q(1)

부터

\mathbf q(2)

사이를 정의하는 식입니다. 더 형식적으로 쓰면 다음과 같습니다.

\begin{aligned} i&=\lfloor s\rfloor&&\text{바닥 함수로 구간 선택},\\ s_i&=s-i&&\text{국소 매개변수 계산},\\ \mathbf q(s)&=\mathbf q_i(s_i)&&\text{구간 평가}. \end{aligned}

특정한

s

가 주어지면 스플라인 위의 점

\mathbf q(s)

를 명확히 식별할 수 있습니다. 반면 특정한

s_i

값은 구간

i

의 맥락 안에서만 의미가 있습니다. 아래첨자가 이 사실을 강조합니다.

구현 보충 — 마지막 끝점

s=n

에서는 그대로

\lfloor s\rfloor

을 쓰면 존재하지 않는

n

번 구간을 선택합니다. 끝점은

\mathbf q(n)=\mathbf q_{n-1}(1)

로 처리합니다. 즉 유효 범위

[0,n]

안에서

i=\min(\lfloor s\rfloor,n-1)

s_i=s-i

로 계산할 수 있습니다.

곡선의 시간 배치가 중요하지 않다면 이 표기만으로 충분할 수 있습니다. 하지만 애니메이션 경로를 정의할 때는 대개 한 단계의 간접화가 필요합니다. 주어진 “시간”

t

에서 위치를 돌려주는 최종 곡선에

\mathbf p(t)

라는 표기를 도입하겠습니다. 같은 곡선을 다르게 매개변수화한 것뿐입니다.

\mathbf p(t)

와

\mathbf q(s)

는 같은 모양을 그리지만 경로 위의 같은 점에 대응하는

s

와

t

는 보통 같지 않습니다. 어떤 부분은 빠르게, 어떤 부분은 느리게 지나도록 매개변수화할 수 있습니다.

s

의 범위는 매듭점 수로 고정되지만,

t

의 범위인 전체 소요 시간은 원하는 대로 정할 수 있습니다.

일반적으로 시간

t

를 매개변수

s

로 매핑하는 함수를 만들어

\mathbf q(s)

로부터

\mathbf p(t)

를 정의할 수 있습니다.

s

가

t

의 함수라는 점을 명시하려면

s(t)

라고 쓰며, 이를 시간-매개변수 함수(time-to-parameter function)라고 합니다.

프로그래머라면

\mathbf p(t)

를 공개 인터페이스,

\mathbf q(s)

를 내부 구현 세부사항이라고 생각해도 좋습니다. 간접 단계를 도입해 복잡성을 나누는 컴퓨터 과학의 기본 기법을 사용하는 셈입니다.

이 표기 아래에서

\mathbf p(t)

를 평가하는 기본 절차는 다음과 같습니다.

시간-매개변수 함수 s(t)s(t)s(t)를 평가하여 시간 ttt를 sss로 매핑합니다.

sss의 정수 부분을 iii, 소수 부분을 sis_isi​로 얻습니다.

곡선 구간 qi(si)\mathbf q_i(s_i)qi​(si​)를 평가합니다.

물론 스플라인의 시간 배치에 관심이 없고 모양만 중요하다면 첫 단계는 필요 없습니다. 단순한 매핑

s(t)=t

를 써도 됩니다. 아쉽지만 지면의 제약 때문에 이 책에서는 바로 그렇게 할 것입니다. 시간 배치의 세부적인 문제는 다루지 않습니다.

일단

s=t

라고 가정하면 첫 단계는 자명합니다. 둘째 단계도 쉽고, 셋째 단계에는 이 장의 앞부분을 할애했습니다. 따라서 스플라인을 평가하는 방법은 이미 알고 있습니다. 이제 만드는 방법을 보겠습니다.

13.6.2 매듭점

두 구간 사이의 연결점을 생각해 보겠습니다. 곡선이 연속이려면 한 구간의 끝점이 다음 구간의 시작점과 일치해야 함은 분명합니다. 더 바람직한 추가 기준은 13.8절에서 다룹니다. 이처럼 공유되고 스플라인이 보간하는 제어점을 스플라인의 매듭점(knot)이라고 부릅니다.

i

번 매듭점은

\mathbf k_i

로 쓰며, 매듭점은 구간보다 하나 더 많으므로

\mathbf k_0,\ldots,\mathbf k_n

으로 번호를 매깁니다.

각 구간이 매듭점에서 연결된다고 가정합니다. 즉

s

가 정수일 때

\mathbf q(s)

는 매듭점을 지납니다. 이 가정 아래에서는 각 구간의 시작점과 끝점에 별도 표기나 별도 저장 공간이 필요 없습니다. 내부 매듭점

\mathbf k_i

하나가 구간

\mathbf q_i

의 시작점과 구간

\mathbf q_{i-1}

의 끝점이라는 두 역할을 맡습니다. 따라서 다음 관계가 성립합니다.

\begin{aligned} \mathbf q(i)&=\mathbf k_i,\\ \mathbf q_i(0)&=\mathbf k_i,\\ \mathbf q_i(1)&=\mathbf k_{i+1}. \end{aligned}

\mathbf k_i

는 하나의 점을 지정합니다. 반면

\mathbf q_i

는 국소 매개변수

s_i

를 받아 점을 내놓는 함수, 즉 전체 구간을 가리킵니다. 이 모든 표기를 그림 13.18에 나타냈습니다.

그림 13.18

그림 13.18. 구간이

n

개인 스플라인에는

\mathbf k_0,\ldots,\mathbf k_n

으로 이름 붙인

n+1

개의 매듭점이 있습니다.

애니메이션에서는 매듭점을 키(key)라고도 합니다. 숙련된 애니메이터가 캐릭터의 중요한 자세에 해당하는 키 프레임을 그리고, 경험이 적고 인건비도 적게 드는 견습생이 중간 프레임을 채우던 전통적인 제작 방식에서 온 말입니다. 컴퓨터 애니메이션의 키는 위치, 자세, 또는 다른 어떤 데이터든 사람이 특정 시점의 값을 지정한 것이 될 수 있습니다.

다른 출처에서 값이 주어져도 마찬가지입니다. “빠진 프레임을 채우는” 견습생 역할은 애니메이션 프로그램이 맡으며, 이 장에서 논의하는 것 같은 보간법을 씁니다. 앞서 말했듯 초기 스플라인 연구의 대부분은 움직이는 궤적이 아니라 정적인 모양을 정의하는 것이 목적이었으므로 “매듭점”이라는 용어가 더 널리 쓰입니다.

[원주 17] “룽게(RUN-guh)”라고 발음합니다.

13.7 에르미트 스플라인과 베지에 스플라인 (Hermite and Bézier Splines)

스플라인은 곡선 구간들을 매끄럽게 맞물리도록 이어 만듭니다. 어떤 곡선 구간을 사용할까요? 곧 드러날 이유로, 개별 구간은 에르미트 표현을 쓰는 편이 우리에게 가장 편리합니다. 여기서 “우리”란 애니메이션 시스템 코드를 작성하거나 이어지는 절의 수학적 논의를 수행하는 사람들입니다.

스플라인을 그래픽으로 표시하거나 조작할 때는 보통 베지에 형식을 선호합니다. 물론 두 형식은 밀접하게 연결되어 있으며 쉽게 상호 변환됩니다. 관계가 기억나지 않아도 잠시 뒤 다시 살펴봅니다.

에르미트 곡선 구간은 시작과 끝의 위치 및 속도로 정의된다는 것을 기억하겠습니다. 단일 구간에 집중할 때는 위치를

\mathbf p_0,\mathbf p_1

, 속도를

\mathbf v_0,\mathbf v_1

로 썼습니다. 스플라인에서는 구간 대신 매듭점을 중심으로 표기를 구성합니다. 위치에는

\mathbf p

를 쓰지 않습니다. 앞에서 말했듯

\mathbf q_i(0)

의 시작 위치인 매듭점

\mathbf k_i

가 이전 구간의 끝 위치

\mathbf q_{i-1}(1)

역할도 하기 때문입니다.

속도의 경우

\mathbf v_i^{\mathrm{out}}

은 매듭점

i

에서 나가는 속도를 뜻하며 구간

\mathbf q_i

의 시작 속도를 정의합니다. 마찬가지로

\mathbf k_i

의 왼쪽에서 들어오는 속도는

\mathbf v_i^{\mathrm{in}}

으로 쓰며 이전 구간

\mathbf q_{i-1}

의 끝 속도를 정의합니다. 이 속도 벡터들을 접선이라고도 부릅니다.

그림 13.19는 에르미트 구간이 다섯 개인 스플라인을 보여 줍니다. 모든 매듭점, 구간, 접선에 방금 설명한 표기를 붙였습니다.

그림 13.19

그림 13.19. 에르미트 형식의 구간으로 이루어진 스플라인에 사용하는 표기.

그림 13.19와 이 장의 모든 에르미트 곡선 그림에서 접선은 실제 크기의 3분의 1로 그렸다는 점을 기억하겠습니다. 공식적으로는 도해를 작게 하여 이 책이 지구의 천연자원을 덜 쓰도록 했다고 말하고 싶습니다. 더 정확한 이유는 접선 길이를 3분의 1로 그리면 베지에 제어 다각형의 변과 같아지기 때문입니다.

이렇게 맞추면 교육적인 이점도 있지만, 더 중요한 이유는 저자들의 게으름을 도와준다는 것입니다. 그림의 곡선을 만든 도구가 베지에 스플라인에 기반하기 때문입니다.

이 책의 그림 속 스플라인은 Adobe Photoshop에서 패스를 만들고 그 패스를 “따라 그리기(stroke)”하여 만들었습니다. 접선 벡터 화살표는 한 끝을 매듭점에, 다른 끝을 곡선 모양을 조절하는 “핸들”에 놓아 그렸습니다. 그 핸들은 본질적으로 베지에 제어점과 같습니다. Photoshop은 매듭점을 “고정점(anchor point)”이라고 부르고, 보간되지 않는 내부 베지에 제어점을 “제어점(control point)”이라고 부릅니다.

예를 들어 그림 13.20은 저자 한 사람이 그림 13.19를 열심히 만드는 동안 찍은 화면입니다. Photoshop의 조작점을 보기 쉽도록 실제 그림의 불투명도를 낮췄습니다.

그림 13.20

그림 13.20. Adobe Photoshop으로 그림 13.19 만들기.

베지에 곡선 이야기가 나온 김에 베지에 스플라인의 표기도 도입하겠습니다. 단일 베지에 구간에서는

i

번째 제어점을

\mathbf b_i

라고 했습니다. 여기서는

i

번째 매듭점 들어오는 쪽(원문의 in front)의 제어점을

\mathbf f_i

, 나가는 쪽(after)의 제어점을

\mathbf a_i

로 씁니다.[원주 18] 그림 13.21에 나타냈습니다.

그림 13.21

그림 13.21. 스플라인과 베지에 제어 다각형, 그리고 베지에 스플라인에 사용하는 표기.

에르미트와 베지에 형식 사이의 중요한 관계를 13.4.3절에서 소개했습니다. 새로 도입한 스플라인 표기로 다시 쓰면 다음과 같습니다.

\begin{aligned} \mathbf v_i^{\mathrm{in}}&=3(\mathbf k_i-\mathbf f_i),& \mathbf f_i&=\mathbf k_i-\mathbf v_i^{\mathrm{in}}/3,\\ \mathbf v_i^{\mathrm{out}}&=3(\mathbf a_i-\mathbf k_i),& \mathbf a_i&=\mathbf k_i+\mathbf v_i^{\mathrm{out}}/3. \end{aligned}

[원주 18] 매듭점 중심의 표기를 쓰고 기억하기 쉬운 말에 맞춰 제어점에 서로 다른 글자를 붙이면서 구간의 차수를 3차로 고정했습니다. 다른 자료에서는 구간

j

의

i

번째 점을

\mathbf b_i^j

처럼 쓰거나, 다각형의 모든 점을 단순히

\mathbf b_i

로 쓰기도 합니다. 후자의 경우 매듭점은

\mathbf b_0,\mathbf b_3,\mathbf b_6,\ldots

입니다. 이런 표기는 더 일반적이지만 읽는 데 더 많은 머릿속 작업이 필요합니다. 우리는 그 수고를 최소화하고 싶습니다. [원문 교정: 제공 PDF에는 마지막 나열이

\mathbf b_0,\mathbf b_3,\mathbf b_7

로 되어 있습니다. 끝점을 공유하는 3차 구간에서는 3칸마다 매듭점이므로

\mathbf b_6

로 바로잡았습니다.]

13.8 연속성 (Continuity)

여러 절에 걸쳐 구간들을 스플라인으로 매끄럽게 잇는 방법을 알려 주겠다고 약속했습니다. 이렇게 뜸을 들이다 보니 신비한 비밀처럼 느꼈을지도 모릅니다. 하지만 그림 13.19를 자세히 보면 기준은 비교적 분명합니다.

\mathbf k_1,\mathbf k_2

에서처럼 매듭점의 들어오는 속도 벡터와 나가는 속도 벡터가 같으면 곡선은 매끄럽습니다.

\mathbf k_3

에서는 접선이 다르고 곡선에 꺾임이 있습니다. 꽤 자명하지 않나요? 사실은 이 주제에 관해 할 이야기가 훨씬 더 있습니다.

그림 13.19에서

\mathbf k_4

근처를 보겠습니다. 들어오는 속도

\mathbf v_4^{\mathrm{in}}

은 나가는 속도

\mathbf v_4^{\mathrm{out}}

보다 훨씬 길지만 곡선의 모양은 “매끄럽습니다”. “저기는 매끄럽지 않아요! 곡선을 따라 움직이다 보면 키를 지나는 순간 급브레이크를 밟게 되잖아요”라고 생각할지도 모릅니다.

하지만 접선 벡터를 그림에서 빼고 모양만 보세요. 모양은 매끄럽지 않나요? 되풀이되는 주제로 돌아왔습니다. 애니메이션 경로는 정적인 모양보다 더 많은 것을 요구합니다. 방금 반론에서 “매듭점” 대신 “키”라고 하여 애니메이션 쪽 용어를 쓴 것도 눈치채셨나요? 아주 빨리 배우고 있습니다!

매끄러운 애니메이션 이야기가 나왔으니, 조금 전에

\mathbf k_1,\mathbf k_2

에서 매끄럽다고 한 말도 생각해 보겠습니다. 정말 그럴까요? 모양은 매끄러워 보이지만 매끄러운 모양과 매끄러운 애니메이션은 다르다고 방금 지적했습니다. 일반적으로는 시간-매개변수 함수

s(t)

를 더 알지 못하면 애니메이션이 매끄러운지 판단할 수 없습니다.

모양이 매끄럽지 않으면 애니메이션도 매끄럽지 않습니다. 다만 잠시 뒤 설명할 예외 하나가 있습니다. 모양이 매끄러워도

s(t)

의 불연속 때문에 애니메이션에 불연속이 생길 수 있습니다.

s(t)=t

이면 이 단순한 매핑이 불연속을 새로 만들지 않으므로 접선이 같다면 움직임도 매끄럽습니다.

마지막으로 들어오는 속도와 나가는 속도가 모두 0인 매듭점을 생각하겠습니다. 이 경우 접선은 연속이지만 대부분의 사람은 그 매듭점의 모양이 매끄럽지 않다고 느낄 것입니다. 움직임은 어떨까요? 완전히 멈춘 뒤 어쩌면 다른 방향으로 가속해 나가는 움직임은 매끄러울까요? 이는 필요에 따라 달라집니다.

“매끄러울까요?”라는 질문의 답이 다소 모호해 보입니다. 수학책에서 “매끄럽다” 같은 애매한 말에 따옴표를 붙이는 것은 좋은 방식이 아닙니다. 더 정확한 용어가 필요합니다. 곡선에서 가장 중요한 매끄러움 기준은 매개변수 연속성(parametric continuity)과 그에 밀접하게 관련된 기하 연속성(geometric continuity)입니다. 수학적으로 정의하기 더 쉬운 매개변수 연속성부터 차례로 살펴보겠습니다.

13.8.1 매개변수 연속성

처음

n

차까지의 도함수가 연속이면 곡선이

C^n

연속성을 갖는다고 합니다.

C^0

곡선은 위치, 즉 “0차 도함수”가 연속인 곡선입니다. 종이에서 연필을 떼지 않고 한 획으로 그릴 수 있다는 뜻이며, 애니메이션 경로에서는 “순간이동” 없이 움직일 수 있다는 뜻입니다.[원주 19]

C^1

곡선은 1차 도함수가 연속이므로 속도가 순간적으로 뛰지 않습니다.

속도가 빠르게 변할 수 없다는 뜻은 아닙니다. 중간 속도들을 거치지 않은 채 한 순간의 속도에서 다음 순간의 다른 속도로 건너뛰지 않는다는 뜻입니다. 예를 들어 그림 13.19의 곡선은 하나로 연결되어 있으므로 모든 곳에서

C^0

연속입니다. 속도가 갑자기 뛰는

\mathbf k_3,\mathbf k_4

를 제외한 모든 곳에서는

C^1

연속입니다.

n

이 더 크다는 것은 더 높은 차수의 도함수도 연속이라는 뜻입니다. 2차 도함수인 가속도가 연속이면

C^2

입니다. 이 책의 목적에서는

C^1

보다 높은 연속 조건은 그다지 중요하지 않습니다.

C^1

연속성이 없어서 속도가 갑자기 바뀌면 무한한 가속도에 해당하므로 많은 문제가 생깁니다.

로봇이나 절삭 공구처럼 실제 물체를 제어하는 경로라면 구동 모터에 물리적으로 불가능한 일을 요구하는 셈입니다. 애니메이션이 전적으로 컴퓨터 속 가상 세계 안에서만 일어나더라도, 사람은 보통 그런 경로를 “덜컥거린다”고 느낍니다. 따라서 속도 불연속은 피하거나 적어도 제어하는 편이 좋습니다.

반면 가속도가 갑자기 변하는 것은 그만큼 거슬리는 느낌을 만들지 않으며 대부분의 목적에서 충분히 받아들일 만합니다.

개별 다항식 곡선 구간은 그 자체로

C^\infty

연속입니다. 다항식은 원하는 만큼 미분해도 언제나 실숫값의 연속 함수를 얻기 때문입니다. 결국 도함수는 상수 0 함수가 됩니다. 그래서 앞에서는 연속성 문제가 나오지 않았습니다. 걱정할 곳은 매듭점뿐입니다.

고차 도함수에 관해 마지막으로 덧붙이겠습니다. 곡선이

C^n

연속이라고 하면 그보다 낮은 모든 도함수도 연속임을 포함합니다. 예를 들어 가속도가 연속이면 속도와 위치도 연속이어야 합니다. 함수가 어떤 점에서 불연속이면 그 점의 도함수는 정의되지 않습니다.

이제 비형식적으로 이야기한 매개변수 연속성의 기준을 에르미트와 베지에 곡선에 대해 수학적으로 정의하겠습니다. 13.4.3절에서 베지에 도함수에 관해 관찰한 다음 사실들을 사용합니다.

•

베지에 구간 끝점의 nnn차 도함수는 끝점과 가장 가까운 nnn개의 제어점으로 완전히 결정됩니다.

•

끝점의 속도는 끝점과 인접 제어점 사이의 벡터에 비례합니다. 식 (13.30), (13.31)을 참고해 보세요.

•

끝점의 가속도는 제어 다각형에서 가장 가까운 두 변의 변위 벡터 사이 차이에 비례합니다. 식 (13.36), (13.37)을 참고해 보세요.

C^0

부터 시작하겠습니다. 선택한 표기 덕분에 생각할 것도 없습니다. 한 구간의 끝점과 다음 구간의 시작점은 정의상 같습니다.

C^1

은 키에서 접선이 같으면 성립한다고 했습니다. 에르미트 형식으로 바로 쓰면 다음과 같습니다.

\mathbf v_i^{\mathrm{in}}=\mathbf v_i^{\mathrm{out}}.

조금만 계산하면 3차 베지에 형식으로도 쓸 수 있습니다.

\mathbf k_i-\mathbf f_i=\mathbf a_i-\mathbf k_i.

간단한 대수 정리를 하면, 기하학적으로 매듭점이

\mathbf f_i

와

\mathbf a_i

를 잇는 선분의 중점이라는 뜻임을 알 수 있습니다.

\begin{aligned} \mathbf k_i-\mathbf f_i&=\mathbf a_i-\mathbf k_i,\\ 2\mathbf k_i&=\mathbf f_i+\mathbf a_i,\\ \mathbf k_i&=(\mathbf f_i+\mathbf a_i)/2. \end{aligned}

대부분의 곡선 설계 도구는 이 규칙을 자동으로 지켜 줍니다. 원문에서는 Photoshop의 제어점을 움직일 때 반대쪽 제어점도 시소처럼 움직이는 방식을 예로 듭니다. 제어점을 고정점인 매듭점에서 멀리 당기면 반대쪽 제어점도 대칭으로 움직여

C^1

관계를 유지합니다. 곡선에 모서리를 만들고 싶다면 보조 키를 눌러 이 동작을 하지 않도록 할 수 있습니다.

이제

C^2

연속성을 보겠습니다. 에르미트보다 베지에 형식에서 시각화하기 쉽습니다. 13.4.3절에서 배운 내용을 적용하여 한 구간의 끝 가속도인 아래 식의 왼쪽과 다음 구간의 시작 가속도인 오른쪽을 일치시키면 됩니다.

\begin{aligned} 6\mathbf a_{i-1}-12\mathbf f_i+6\mathbf k_i&=6\mathbf k_i-12\mathbf a_i+6\mathbf f_{i+1},\\ \mathbf a_{i-1}-2\mathbf f_i+\mathbf k_i&=\mathbf k_i-2\mathbf a_i+\mathbf f_{i+1},\\ 2\mathbf f_i-\mathbf a_{i-1}&=2\mathbf a_i-\mathbf f_{i+1},\\ \mathbf f_i+(\mathbf f_i-\mathbf a_{i-1})&=\mathbf a_i+(\mathbf a_i-\mathbf f_{i+1}). \end{aligned}

기하학적으로는 다음 뜻입니다. 매듭점과 직접 맞닿은 변이 아니라 한 변 떨어진 양쪽 베지에 제어 다각형의 변을 가져와 길이를 “두 배”로 늘립니다. 이들이 같은 점에서 만나면

C^2

연속입니다. 그림 13.22의 두 베지에 곡선을 비교하면 보입니다. 둘 다 매듭점

\mathbf k_i

가

\mathbf f_i

와

\mathbf a_i

사이의 중점이므로

C^1

연속입니다.

위 곡선은 이웃 제어 다각형 변을 연장한 선들이 같은 점에서 만나므로

C^2

연속이지만, 아래 곡선은 그렇지 않습니다.

그림 13.22

그림 13.22. 3차 베지에 스플라인의 연속 조건.

매개변수를 같은 간격으로 바꾸어도 등속은 아니다

프레임마다

t

를

0.01

씩 늘리는 것은 매개변수를 일정하게 바꾸는 것입니다. 공간에서의 이동 거리가 같다는 뜻은 아닙니다. 실제 속력은

\|d\mathbf p/dt\|

이므로 곡선을 따라 달라질 수 있습니다. 원문의 표본점 간격이 고르지 않은 도해들은 바로 이 차이를 드러냅니다.

실제 시간

\tau

로

D

초 동안 한 구간을 이동시키려면

t=\tau/D

를 쓸 수 있습니다. 연쇄법칙에 따라 다음과 같습니다.

\frac{d\mathbf p}{d\tau}=\frac1D\frac{d\mathbf p}{dt},\qquad \frac{d^2\mathbf p}{d\tau^2}=\frac1{D^2}\frac{d^2\mathbf p}{dt^2}.

따라서 두 구간의 재생 시간이 다르면 원문의 같은 길이 손잡이 조건만으로 실제 시간에 대한

C^1

이 보장되지 않습니다. 접합점에서 왼쪽 구간의 마지막 내부 제어점을

\mathbf f_i

, 오른쪽의 첫 내부 제어점을

\mathbf a_i

, 각 구간 소요 시간을

D_L,D_R

라고 하면 실제 속도 연속 조건은 다음과 같습니다.

\frac{3(\mathbf k_i-\mathbf f_i)}{D_L} =\frac{3(\mathbf a_i-\mathbf k_i)}{D_R}.

왼쪽이 2초, 오른쪽이 1초라면 왼쪽 손잡이가 오른쪽보다 두 배 길어야 같은 실제 속도로 연결됩니다. 본문의 조건은 두 구간의 매개변수 척도가 같을 때의 식입니다.

13.8.2 기하 연속성

기하 연속성은 더 넓은 연속성 기준입니다. 저자마다 서로 다른 정의를 쓰지만, 매우 일반적인 정의는 어떤 방식으로든 재매개변수화하여

C^n

연속으로 만들 수 있으면 곡선은

G^n

연속이다라는 것입니다. 예를 보겠습니다.

그림 13.19의

\mathbf k_4

에서는 접선이 같지 않으므로

C^1

연속이 아닙니다. 하지만 그곳은

G^1

연속입니다. 힌트는 매듭점에서 접선들이 평행하다는 것입니다. 접선이 평행하지 않다면 곡선을 따라 매끄럽게 움직일 방법이 없습니다. 반면 평행하다면 불연속은 방향 변화가 아니라 순전히 속력 변화입니다. 속력의 도약을 정확히 상쇄하는 변화를 시간-매개변수 함수

s(t)

에 주의 깊게 넣으면 불연속을 제거할 수 있습니다.

고차 기하 연속성도 이 생각을 확장한 것이지만 시각화하기는 조금 더 어렵습니다. 곡률이 연속적으로 바뀌면 곡선은

G^2

연속이라고 합니다.

추가 설명 — 방향과 시간 미분

보통의 정칙 곡선에서

G^1

은 두 접선이 0이 아니며 같은 진행 방향의 양의 배수라는 조건입니다. 역방향 평행은 충분하지 않습니다. 속력 차이를 보상할 때는 위치 매핑

s(t)

자체를 점프시키는 것이 아니라 그 미분

ds/dt

의 값을 조절합니다. 양쪽 속도를 0으로 만들면 꺾인 모양에서도

C^1

움직임을 만들 수 있지만, 이는 위 본문에서 따로 언급한 정지점의 예외입니다.

13.8.3 곡선은 얼마나 매끄러울 수 있을까?

연속성 논의를 마치며 중요한 질문을 던져 보겠습니다. 다항식 스플라인에서 기대할 수 있는 가장 높은 연속성은 어느 정도일까요? 개별 곡선 구간은 원하는 만큼 미분해도 결과가 연속이므로

C^\infty

연속이라고 했습니다. 스플라인에서도 같은 매끄러움을 얻을 수 있을까요?

인접한 두 3차 베지에 구간을 생각하겠습니다. 첫 구간은 고정하고 매듭점에 점점 더 높은 연속성을 요구하면 둘째 구간에 어떤 일이 생기는지 보겠습니다.

C^0

를 요구하면 첫 베지에 제어점이 고정됩니다. 스플라인이

C^0

연속이려면 둘째 구간의 첫 끝점은 첫 구간의 마지막 끝점과 같아야 합니다.

C^1

은 어떨까요? 끝점의 속도는 끝점과 인접 제어점으로 완전히 결정됩니다. 따라서 속도를 맞추려면 두 번째 제어점 위치도 고정해야 합니다.

이 패턴을 계속하면 베지에 구간의

n

차 도함수까지 맞추려면

n+1

개의 제어점을 “고정”해야 한다는 것을 알 수 있습니다. 원문은 3차 곡선에서

C^4

이상의 연속성을 요구하면 얻을 수는 있지만 모든 구간을 같은 무한 다항식의 일부로 만들어야 한다고 설명합니다. 연속성은 얻었지만 애초에 스플라인을 쓴 이유인 유연성을 잃어버린 것입니다!

원문 설명 교정: 3차 다항식 두 개가 같은 매개변수 척도에서 위치와 1·2·3차 도함수까지 일치하면 이미 같은 다항식으로 고정됩니다. 따라서 여기서 자유도가 사라지는 경계는 C3C^3C3입니다. 원문의 “C4C^4C4 이상”도 그보다 강한 조건으로서는 참이지만, 바로 다음 문단의 Cn−1C^{n-1}Cn−1 한계를 설명하는 정확한 경계는 아닙니다.

실용적으로 말해

n

차 다항식 스플라인, 즉 제어점이

n+1

개인 베지에 구간으로 이루어진 스플라인은 실제로

C^{n-1}

까지의 연속성을 얻는다고 볼 수 있습니다. 예를 들어 구간별 선형, 즉 1차 스플라인은

C^0

까지만 가능합니다. 연결된 곡선은 만들 수 있지만 서로 다른 직선들을 쓰면서 접선까지 맞출 수는 없습니다. 2차 다항식은 접선인

C^1

까지 맞출 수 있지만 가속도까지는 맞추지 못합니다.

이 책에서 집중한 3차 곡선은 구간당 자유도를 하나로 줄이면

C^2

연속이 가능합니다. 그보다 높은 연속성을 얻으려면 시간 배치를 제외한 모든 자유도를 없애고 각 구간을 같은 다항식의 일부로 만들어야 합니다.

[원주 19] 이런, 수학책에서 좋지 않다고 방금 말했던 따옴표를 또 썼습니다!

13.9 자동 접선 제어 (Automatic Tangent Control)

이 장의 처음에는 곡선이 통과할 점들을 나열하는 것만으로 곡선을 정의하겠다는 계획으로 탐구를 시작했습니다. 13.2절에서 기본 다항식 보간을 시도했지만 원하는 결과를 얻지 못했습니다. 그 뒤 개발한 베지에 형식에서는 보간되는 두 끝점과, 보간되지는 않지만 양 끝점의 도함수를 정하는 내부 제어점들을 사용자가 지정해야 했습니다. 3차 베지에에서는 내부 제어점이 두 개입니다. 그리고 지금까지 그런 베지에 구간들을 매끄러운 스플라인으로 잇는 방법을 배웠습니다.

이번 절에서는 추가 조건을 사용자가 지정하지 않고 매듭점만으로 스플라인을 결정하는 여러 방법을 조사합니다. “자연스러워” 보이며 주어진 점들을 통과하는 곡선을 만들거나 데이터 점들을 매끄럽게 보간하고 싶을 때 유용합니다.

당장은 처음과 마지막 매듭점을 무시하고 내부 매듭점에 집중하겠습니다. 풀어야 할 문제는 매듭점의 위치만 사용하여 적당한

\mathbf v_i^{\mathrm{in}},\mathbf v_i^{\mathrm{out}}

을 계산하는 것입니다. 이 문제에 가장 편한 형식인 에르미트로 문제를 표현했다는 점에 주목하겠습니다. 그림 13.23은 세 제어점과 세 가지 서로 다른 접선 선택을 보여 줍니다.

그림 13.23

그림 13.23. 가운데 매듭점의 접선을 서로 다르게 선택하여 얻은 세 가지 보간 스플라인.

이어지는 절들은 “좋은” 보간 스플라인이 되도록 접선을 선택하는 기법들을 다룹니다. 먼저 13.9.1절의 캐트멀–롬 스플라인은 간단하고 직접적인 방법입니다. 13.9.2절의 TCB 스플라인은 캐트멀–롬을 일반화한 혼합 방식으로, 사용자가 접선의 기하학적 위치를 직접 지정하지 않고도 더 직관적으로 모양을 조절하도록 추가 “슬라이더”를 제공합니다. 마지막으로 13.9.3절에서는 양 끝점을 처리하는 몇 가지 선택지를 나열합니다.

읽는 동안 이 스플라인들이 여전히 모두 에르미트 스플라인이라는 사실을 기억하겠습니다. 단지 접선을 자동 계산하는 여러 방법을 도입하는 것입니다. 접선이 결정된 뒤에는 다른 에르미트 스플라인과 다르지 않습니다.

13.9.1 캐트멀–롬 스플라인

그림 13.23에서 세 접선 선택 중 가장 자연스러운 것은 가운데 것이라는 점이 분명해 보입니다. 왜 그럴까요? 이전 매듭점

\mathbf k_{i-1}

에서 다음 매듭점

\mathbf k_{i+1}

로 가는 벡터가 수평이므로 접선도 수평인 것이 자연스럽습니다. 따라서 좋은 접선을 고르는 한 가지 경험 법칙은 매듭점의 접선을 그 이전과 다음 매듭점을 잇는 선에 평행하게 두는 것입니다.

이 예에서는 가운데 매듭점이 양 이웃의 중간 위치에 있다는 점이 다소 의도적으로 만들어진 특수 경우입니다. 하지만 이웃 둘을 잇는 선이 수평이라는 점 자체는 특수하지 않습니다. 관점을 회전하면 언제든 그런 배치로 볼 수 있기 때문입니다.

그렇다면 접선은 얼마나 길어야 할까요? 다시 이전과 다음 매듭점 사이의 벡터를 기준으로 삼을 수 있을 것입니다. 이웃이 멀수록 곡선도 커지는 듯하므로 접선을 그 벡터의 일정한 배수로 정하면 좋겠습니다. 즉

\mathbf v_i^{\mathrm{in}}=\mathbf v_i^{\mathrm{out}}=a(\mathbf k_{i+1}-\mathbf k_{i-1})

로 둡니다. 그런데

a

에는 무엇을 써야 할까요?

그냥 실험해서 보기 좋은 결과를 내는 깔끔한 수를 찾는 방법도 있습니다.

a=1/2

는 간단하고 어느 정도 잘 작동하므로 이것으로 하겠습니다. 그림 13.24는 이 방법으로 생성한 닫힌 스플라인입니다.

그림 13.24

그림 13.24. 캐트멀–롬 스플라인.

a=1/2

가 “중간 정도”의 결과를 주지만 취향의 문제라는 주장도 가능합니다. 더 “팽팽한” 곡선이 필요하면 더 작은

a

를 쓰고, 때로는 더 “느슨한” 곡선을 원할 수도 있습니다. 좋은 생각이지만 잠시 접어 두고 우연히 발견한 이 방법에 관해 두 가지를 더 말하겠습니다.

첫째, 이름과 정식 정의를 붙이겠습니다. 다음 관계로 접선을 구하는 스플라인을 캐트멀–롬(Catmull–Rom) 스플라인이라고 합니다.

\mathbf v_i^{\mathrm{in}}=\mathbf v_i^{\mathrm{out}}=\frac{\mathbf k_{i+1}-\mathbf k_{i-1}}2.\tag{13.39}

이름은 이를 발명한 두 사람에게서 왔습니다. 그중 한 사람은 에드윈 캐트멀(Edwin Catmull, 1945–)이며, 이후 월트 디즈니 애니메이션 스튜디오와 픽사 애니메이션 스튜디오의 사장이 되었습니다. [옮긴이 설명: 원문의 역사적 서술입니다. 현재 직위를 뜻하지 않습니다.]

둘째로 이야기하고 싶은 것은 식 (13.39)를 유도하는 다른 관점입니다. 간단히 대수적으로 조작하면 다음과 같습니다.

\begin{aligned} \mathbf v_i^{\mathrm{in}}=\mathbf v_i^{\mathrm{out}} &=\frac{\mathbf k_{i+1}-\mathbf k_{i-1}}2\\ &=\frac{\mathbf k_{i+1}-\mathbf k_i+\mathbf k_i-\mathbf k_{i-1}}2\\ &=\frac{(\mathbf k_{i+1}-\mathbf k_i)+(\mathbf k_i-\mathbf k_{i-1})}2. \end{aligned}

마지막 줄의 기하학적 의미는 매듭점의 접선을 계산할 때 제어 다각형의 이웃한 두 차이 벡터를 평균한다는 것입니다.

13.9.2 TCB 스플라인

13.9.1절에서는 제어 다각형의 인접한 변 벡터들에 적절한 상수

a

를 곱하고 결과를 더해 접선을 계산했습니다.

a

를 바꾸면 곡선 모양을 조절하는 직관적인 “다이얼”을 얻었습니다. 배율을 하나가 아니라 두 개로 두면 더 일반화할 수 있습니다. 즉 인접 변 벡터들의 임의의 선형결합을 취할 수 있습니다. 두 배율에 각각 다이얼 하나를 직접 배정하는 단순한 접근은 그다지 직관적인 시스템이 되지 않습니다. 대신 장력(tension), 연속성(continuity), 편향(bias)이라는 직관적인 다이얼 세 개를 제공하고 이들로부터 두 배율을 유도하는 것이 표준 기법입니다. 이렇게 접선을 구한 스플라인은 코차넥–바텔스(Kochanek–Bartels) 스플라인이며, 이름의 앞글자를 따 흔히 TCB 스플라인이라고 합니다.[원주 20]

코차넥과 바텔스 [40]는 다이얼 세 개를 모두 0으로 하면 표준 캐트멀–롬 곡선이 되도록 식을 설계했습니다. 모든 매개변수에 보통 유용한 범위는

[-1,+1]

이지만 그 밖의 값도 문제가 없습니다. 따라서 각 설정은 캐트멀–롬에서 출발하여 특정 방향으로 모양을 조절하는 수단이라고 생각할 수 있습니다. 먼저 각 설정을 단독으로 구현하는 방법을 보고, 뒤에서 세 설정을 합친 전체 공식을 제시하겠습니다.

장력 설정은 앞 절의

a

와 관련이 있습니다. 장력에는

t

를 쓰며, 다행히 여기서는 시간 매개변수라는 다른 뜻의

t

와 혼동할 상황이 없습니다. 다른 TCB 설정과 마찬가지로

t=0

은 일반 캐트멀–롬 곡선에 대응합니다. 장력을 올리면 곡선이 “팽팽해집니다”. 앞 절에서

a

를 줄인 것과 본질적으로 같은 효과입니다. 그림 13.25는 장력의 효과를 보여 줍니다. 각 곡선에서 연속성과 편향은 0입니다.

t=0

인 그림 13.24의 표준 캐트멀–롬 곡선과 비교해 보겠습니다.

그림 13.25

그림 13.25. 서로 다른 장력 값을 적용한 TCB 스플라인. [원문 캡션의 “continuity”는 본문 및 그림의

t

값과 맞지 않는 오자이므로 “장력”으로 교정했습니다.]

t=1

이면

\mathbf v_i^{\mathrm{in}}=\mathbf v_i^{\mathrm{out}}=0

이 됩니다. 매듭점에서 속도가 0이 되면서 모양에 뾰족점이 생깁니다.

t

를 더 올리면 속도가 “잘못된 방향”을 향해 매듭점에 고리가 생깁니다. 반대쪽 극단인

t=-1

은 캐트멀–롬보다 “두 배 느슨한” 곡선을 만듭니다. 이 값 자체에 특별한 의미가 있는 것은 아닙니다.

t

를 더 음수로 만들면 더 느슨하게 만들 수 있습니다.

캐트멀–롬 접선 식에 장력을 넣으면 다음과 같습니다.

\begin{aligned} \mathbf v_i^{\mathrm{in}}=\mathbf v_i^{\mathrm{out}} &=\frac{(1-t)(\mathbf k_{i+1}-\mathbf k_{i-1})}2\\ &=\frac{1-t}2(\mathbf k_i-\mathbf k_{i-1})+\frac{1-t}2(\mathbf k_{i+1}-\mathbf k_i). \end{aligned}

다음은 연속성 설정입니다. 곡선의 매끄러움을 깨고 매듭점에 모서리를 만들 수 있습니다. 값이 0이면 장력과 편향이 무엇이든 두 접선이 같아지므로 13.8.1절에서 설명한 매개변수 연속성을 보장합니다. 원문은 여기서

C^2

라고 적었지만, 같은 접선으로 보장되는 것은

C^1

입니다.

연속성 값을 낮추면 각 접선이 그쪽의 이웃 매듭점을 향해 회전합니다.

c=-1

이면 각 접선이 이웃 매듭점을 곧바로 향하므로 “스플라인”은 직선 구간들로 이루어집니다. 그림 13.26은 여러 연속성 값의 효과입니다.

그림 13.26

그림 13.26. 서로 다른 연속성 값을 적용한 TCB 스플라인.

c=-1

은 모양만 보면

t=1

과 비슷한 효과를 낸다는 점에 주목하겠습니다. 둘 다 각 구간이 직선 모양이 됩니다. 그러나 애니메이션 관점에서는 매우 다릅니다. 장력이 100%인 스플라인은 각 키에서 멈추고 구간 중간에서 최대 속도에 이릅니다. 에르미트 스무스스텝의 속도 양상이며, 각 구간의 점 간격이 균일하지 않은 데서 보입니다.

그림 13.25의

t=1

스플라인에서는 베지에 제어점들이 매듭점과 겹쳐 보이지 않습니다. 반면 그림 13.26의

c=-1

에서는 각 직선 구간을 따라 베지에 제어점들이 등간격으로 놓입니다. 앞에서 보았듯 이것은 등속 곡선을 만듭니다. 곡선을 그리는 작은 검은 점들의 간격이 같은 것이 그 증거입니다.

TCB 연속성의 수식은 다음과 같습니다.

\begin{aligned} \mathbf v_i^{\mathrm{in}}&=\frac{1-c}2(\mathbf k_i-\mathbf k_{i-1})+\frac{1+c}2(\mathbf k_{i+1}-\mathbf k_i),\\ \mathbf v_i^{\mathrm{out}}&=\frac{1+c}2(\mathbf k_i-\mathbf k_{i-1})+\frac{1-c}2(\mathbf k_{i+1}-\mathbf k_i). \end{aligned}

마지막으로 편향 인수는 캐트멀–롬처럼 접선을 양 이웃을 잇는 선과 평행하게 두는 대신, 어느 한쪽 이웃 매듭점 쪽으로 돌릴 수 있습니다. 세 매듭점이 이어진 상황을 생각하겠습니다. 음의 편향은 곡선이 셋째 매듭점을 “미리 예상”하도록 하여 가운데 매듭점에 도달하기 조금 전부터 셋째 쪽으로 돌게 합니다. 양의 편향은 셋째 쪽으로 도는 것을 늦추어 가운데 매듭점을 어느 정도 “지나치게” 합니다. 그림 13.27은 여러 편향 값을 적용한 예입니다.

그림 13.27

그림 13.27. 서로 다른 편향 값을 적용한 TCB 스플라인.

편향 값은 결과 접선에 대한 두 제어 다각형 변의 상대 가중치를 조절합니다.

\mathbf v_i^{\mathrm{in}}=\mathbf v_i^{\mathrm{out}}= \frac{1+b}2(\mathbf k_i-\mathbf k_{i-1})+\frac{1-b}2(\mathbf k_{i+1}-\mathbf k_i).

지금까지는 각 설정의 수학을 이해하기 쉽도록 하나씩 분리했습니다. 이제 세 설정을 합치겠습니다.

TCB 스플라인의 접선 계산

\begin{aligned} \mathbf v_i^{\mathrm{in}}&=\frac{(1-t)(1+b)(1-c)}2(\mathbf k_i-\mathbf k_{i-1}) +\frac{(1-t)(1-b)(1+c)}2(\mathbf k_{i+1}-\mathbf k_i),\\ \mathbf v_i^{\mathrm{out}}&=\frac{(1-t)(1+b)(1+c)}2(\mathbf k_i-\mathbf k_{i-1}) +\frac{(1-t)(1-b)(1-c)}2(\mathbf k_{i+1}-\mathbf k_i). \end{aligned}

마지막으로 한 가지. 이 절의 예제에서는 모든 매듭점에 같은 값을 썼지만 꼭 그럴 필요는 없습니다. TCB 값은 매듭점별로 조절하는 경우가 많습니다.

TCB 값을 읽는 순서

먼저 세 값을 모두 0으로 두면 이 장의 균일 캐트멀–롬 곡선이 됩니다. 장력은 두 접선의 공통 크기를 조절합니다. 연속성은 들어오는 접선과 나가는 접선을 서로 다르게 하여 모서리를 만들 수 있습니다. 편향은 양쪽 접선이 이전 구간 또는 다음 구간의 방향을 얼마나 따를지 조절합니다. 한 번에 하나씩 바꾸면 효과를 구분하기 쉽습니다.

본문에서 사용한 TCB의

t

는 장력입니다. 코드에서는 시간 매개변수와 혼동하지 않도록 tension, continuity, bias, u처럼 이름을 나누면 좋습니다.

13.9.3 끝점 조건

캐트멀–롬 방식은 주어진 매듭점의 접선을 계산할 때 이전과 다음 매듭점에 의존합니다. 그렇다면 이전이나 다음 매듭점이 없는 끝점에서는 어떻게 해야 할까요? 여러 해법이 제안되었습니다.

명백한 한 가지 답은 손을 들고 포기하듯 끝점의 접선을 0으로 두는 것입니다. 첫 발도 쏘기 전에 항복하는 것 같지만 애니메이션에는 실제로 좋은 선택일 수 있습니다. 움직이는 물체가 처음과 마지막에 “정지” 상태이기를 바라는 것이 자연스러운 경우가 많기 때문입니다.

다른 생각은 접선 계산에는 쓰지만 보간하지 않는 추가 매듭점

\mathbf k_{-1},\mathbf k_{n+1}

을 만드는 것입니다. 이런 가상점(phantom point)은 어디에 두어야 할까요? 원문은 이웃 끝점을 복제하면 접선이 0이 되어 앞 문단의 “항복” 스플라인과 같아진다고 설명합니다. 또 다른 방법은 사용자에게 가상점을 배치하도록 하는 것입니다. 원문에서는 이 방식을 카디널 스플라인(Cardinal spline)이라고 부릅니다.

원문 설명 교정: 식 (13.39)에서 첫 매듭점의 접선은 (k1−k−1)/2(\mathbf k_1-\mathbf k_{-1})/2(k1​−k−1​)/2입니다. 따라서 끝점 자체를 복제하여 k−1=k0\mathbf k_{-1}=\mathbf k_0k−1​=k0​으로 두면 접선은 보통 0이 아닙니다. 접선을 0으로 만들려면 반대쪽 이웃을 복제하여 k−1=k1\mathbf k_{-1}=\mathbf k_1k−1​=k1​로 두어야 합니다. 마지막 끝점도 kn+1=kn−1\mathbf k_{n+1}=\mathbf k_{n-1}kn+1​=kn−1​로 두면 0이 됩니다. 끝점을 단순 복제하는 규칙과 0 접선 규칙을 혼동하지 마세요. 또한 “카디널 스플라인”은 문헌마다 명칭의 범위가 다르므로 이 문단은 원문의 용어 사용을 보존했습니다.

마지막 방법은 처음 또는 마지막 세 매듭점에 맞는 2차 곡선을 구하고 그 곡선의 끝점 접선을 사용하는 것입니다. 곡선 맞추기는 다항식 보간의 한 예이므로 에이트켄 알고리즘 등 이 장 앞부분의 기법으로 할 수 있습니다.

[원주 20] 우리에게 가장 중요한 이유는 TCB가 “코차넥(koh-CHAN-ick)”보다 발음하기 쉽다는 것입니다.

13.10 연습문제 (Exercises)

답은 원서 인쇄본 792쪽에 있습니다.

연습문제 1

매듭값 열

t_1=0,t_2=1,t_3=2

에 대한 라그랑주 기저 다항식들을 구해 보세요.

연습문제 2

투사체의 운동은 11.6절에서 보았듯 다음 2차 함수로 기술할 수 있습니다.

\mathbf p(t)=\mathbf p_0+t\mathbf v_0+t^2(\mathbf a/2).

여기서

\mathbf p_0

는 초기 위치,

\mathbf v_0

는 초기 속도,

\mathbf a

는 일정한 가속도이며 보통 중력에 의한 것입니다. 투사체, 예를 들어 청어 샌드위치의 경로를 애니메이션으로 만들려고 한다고 하겠습니다. 1.3.4절의 표준 3D 좌표 공간에서 물체를 원점에서 발사합니다.

t=1

에 최고점

\mathbf p(1)=(0,h,d/2)

에 이르고,

t=2

에

\mathbf p(2)=(0,0,d)

로 착지합니다. 변수

h,d

로

\mathbf p(t)

의 단항식 형식을 유도해 보세요.

연습문제 3

아래 그림의 베지에 곡선을 생각해 보세요.

연습문제 3 원본 베지에 곡선

연습문제 3의 원본 베지에 곡선 도해.

(a) 드 카스텔조 알고리즘으로

t=0.40

에서의 위치를 구해 보세요.

(b) 곡선을 에르미트 형식으로 바꿔 보세요.

(d) (c)에서 구한 다항식에

t=0.40

을 대입하여 (a)의 답을 확인해 보세요.

(e) 속도 다항식 함수

\mathbf v(t)

는 무엇일까요?

(f)

t=0.40,t=0.00,t=1.00

에서의 속도는 각각 얼마일까요?

연습문제 4

2차 베른슈타인 기저 다항식들의 합이 어떤

t

에서든 1임을 증명해 보세요.

연습문제 5

\mathbf p(t)

가 언제나 같은 점을 돌려주는 “상수 곡선”을 얻으려면 베지에 제어점을 어디에 두어야 하나요?

연습문제 6

일정한 속도로 직선 구간을 지나는 1차 “곡선”을 얻으려면 베지에 제어점을 어디에 두어야 하나요?

연습문제 7

이번에도 직선 모양이지만 속도는 스무스스텝 양상, 즉 0에서 시작하여 가운데에서 최대가 되도록 가속한 뒤 다시 감속하여 0으로 끝나는 곡선을 원합니다. 베지에 제어점을 어디에 두어야 하나요?

연습문제 8

\mathbf b_0=\mathbf b_2

\mathbf b_1=\mathbf b_3

인 베지에 곡선을 따라 움직이는 입자의 운동을 설명해 보세요.

연습문제 9

연습문제 2의 투사체 청어 샌드위치를 다시 생각해 보세요. 이것을 애니메이션으로 만들어야 하는데 사용할 수 있는 도구가 3차 베지에 곡선뿐이라고 하겠습니다. 실제 물리 운동에 맞는 2차 운동을 얻으려면 네 베지에 제어점을 어디에 두어야 하나요? 샌드위치가 공중에 떠 있는 전체 시간은 신경 쓰지 말고 궤적의 모양만 고려해 보세요.

연습문제 10

그림 12.8, 인쇄본 588쪽의 포물선 모양을 그릴 때 저자들은 보드의 질량 중심에 대한 영상 공간의

x,y

좌표 목록을 만들고 최소제곱 맞추기를 수행하여 포물선

y=-0.364x^2+1.145x+2.110

을 얻었습니다. 포물선을 그리는 데 쓴 Adobe Illustrator의 펜 도구는 3차 베지에 곡선에 기반합니다. 곡선 시작과 끝의

x

좌표는 각각

-0.9683

4.2253

이었습니다. 네 제어점의

(x,y)

좌표는 무엇이었을까요?

연습문제 11

연습문제 3의 곡선으로 돌아가겠습니다.

(a)

0.2

부터

0.5

까지인 부분 구간의 베지에 제어점들을 계산해 보세요.

(b) 이 곡선을

t=1/2

에서 두 반쪽으로 나눠 보세요. 양쪽 곡선의 베지에 제어점은 각각 무엇일까요?

나의 곡선들은 미치지 않았다.

— 앙리 마티스(Henri Matisse, 1869–1954)

직접 확인하기

제어점과 매개변수를 바꾸어 선형 보간이 베지에 곡선을 만드는 과정을 확인해 보세요.

Fletcher Dunn · Ian Parberry, 《3D Math Primer for Graphics and Game Development, 2nd Edition》, 13장. 원서 그림과 자료.