보간과 극사
두 개의 서로 다른 물체가 있을 때, 그 중간을 어떻게 만들어 갈 것인지에 관한 문제로, 시점에 가까우면 시점의 속성을 더 강하게 반영하고 반대로 종점에 가까우면 종점의 속성을 강하게 반영한다.
시점의 속성과 종점 속성을 더해 2로 나누면 중간점으로서 평균을 얻을 수 있지만, 보간은 두 개의 다른 물체의 혼합 비율을 평균처럼 1:1 비율로 잡는 대신 서서히 변화시켜 간다. 다시 말해, 선형보간이라면 다음 식에서 t를 서서히 변화시킴으로서 y{0}과 y{1} 중 어느 쪽 속성을 강하게 반영할 것인지에 관한 혼합 비율을 제어한다.
곡선을 생성할 때 기본이 되는 것은 입력으로서의 제어점을 처음에 몇 개 두고, 사람이 중간에 인위적으로 조작하지 않아도 컴퓨터가 적당히 계산해 보간하고 제어점을 통과하는 자연스러운 형태의 선이 그어진다는 사고방식이다. 이른바 절차적 생성의 기본이라고 할 수 있다.
폴리곤 메시를 이용한 모델 생성이 입력 데이터를 풍부하게 CPU 자원을 절약하는 방법이라면, 실시간 그래픽스에서 곡선을 생성하는 것 CPU 자원을 더 사용하는 절차적 생성 방법에 속한다. 절차적 생성이란 처음에 최소한의 시드 데이터만 입력하고, 실행 시 CPU 자원을 사용하여 알고리즘으로 계산한, 다양한 표현의 데이터를 메모리에 생성해 이용하는 방법이다. 단순히 곡선 외에도 프랙털 도형처럼 계산으로 새로 만들어지는 다양한 패턴이 존재한다. 특정 종류의 게임에서 이루어지는 맵이나 미로 데이터의 자동 생성 역시 절차적 생성의 일종이다. 이번에는 시드가 제어점에 해당해서, 제어점과 알고리즘만 일치하면 완전히 똑같은 곡선을 몇 번이라도 생성할 수 있다.
제어점을 사용한 곡선 생성의 일반적인 응용 사례 중 하나로, Adobe Illustrator 등의 그래픽스 툴에서 곡선을 만드는 경우를 꼽을 수 있다. 앵커 포인트와 패스를 구사해서 어느 정도는 사용자가 입력하여 형태를 다듬지만, 최종적인 곡선 자체는 그래픽스 툴이 자동으로 보기 좋게 생성한다.
보간으로서의 곡선 생성이라는 사고방식과는 별개로 근사를 위한 알고리즘도 있다. 근사는 제어점 사이를 연결한다기보다는 제어점 자체를 느슨한 기준으로 삼아 대체로 비슷한 경로를 만들어냄으로써 전체적으로 자연스러운 형태의 곡선을 얻는 방법으로, 완성된 곡선이 반드시 제어점을 통과하지는 않는다. 다시 말해, 제어점은 곡선의 형태에 영향을 주는 것이 불과하다.
따라서, 곡선 알고리즘을 선택할 때는 사용할 알고리즘이 보간을 하는 것인지, 아니면 근사를 하는 것인지 알고리즘의 특성을 이해하고 선택해야 한다.(실제로는 이 두 가지가 용어적으로 혼동되는 경우가 많음.)
매개변수 함수
가장 일반적인 곡선 알고리즘의 매개변수로 표현된다. 매개변수 함수를 포함하여 함수의 형식에는 양함수, 음함수가 있다.
양함수는 y= f(x)처럼 일반적인 형식의 함수로, x 값에 대해 단 한 개의 y가 정해지는것이 특징이다.
하지만, 예를 들어 단위원을 표현하고자 할 때, 직교좌표에서는 한 개의 x 값에 대해 y 값이 2개 필요하므로, 양함수를 꼭 사용하고 싶다면, 극좌표계 등 다른 좌표계로 표현해야 한다. 이처럼 양함수로는 표현할 수 없는 곡선이 존재한다.
음함수는 f(x, y) = 0과 같은 형식의 함수다. 대수기하학에서 자주 사용되는 형식으로, 예를 들어 단위원은 x^2 + y^2 - 1 = 0과 같은 형식의 함수다. 대수기하학에서 자주 사용되는 형식으로, 예를 들어 단위원은 x^2 + y^2 - 1 = 0으로 나타낼 수 있다. 단 f(x, y, z) = 0으로 하면, 이 식만으로는 곡선이 아닌 곡면을 나타나게 되므로, 한 개의 식으로는 3차원 곡선을 표현할 수 없다.
양함수, 음함수는 데카르트 방정식이라는 종류의 방정식이지만, 매개변수 함수는 다른 장르이다. 매개변수 함수는 매개변수 t를 매개로 삼아, 복수의 양함수를 다시 표현하고, x, y 등 원래 한개의 식 안에 있던 상분을 따로 분리해 성분별로 표시한다. 매개변수 t의 1차원 정의역을 2D 평면상이나 3D 공간 내의 곡선에 사상하는 것이 매개변수 곡선이다. 몇 차원이라도 대응할 수 있고, 모든 종류의 곡선을 표현할 수 있다. 따라서 게임에서 곡선을 사용하는 한 한결같이 매개변수 곡선을 이용한다.
다항식
매개변수 곡선을 나타내는 식은 다음 n차 다항식의 형식이 된다.
다항식 안에서 t는 변수다. c{0}, c{1}과 같은 상수는 계수라고 한다. 상수 또는 계수와 변수 t의 조합은 항이라며, 항이 하나인 식을 단항식이라 한다. n은 다항식 전체의 차수라고 한다. 항에도 차수가 있는데, 매개변수 곡선에 한정되지 않는 일반적인 다항식의 경우, 예를 들어 항이 2x^2y이고 x, y가 변수 일 때 그 항의 차수는 2 + 1 = 3이다. 또한 매개변수 곡선의 다항식은 행렬로서도 표현할 수 있다.
y = ax + b 형식의 1차 다항식은 두 점을 통과하는 선을 나타낼 수 있으므로, 두 점의 보간에 사용할 수 있다. 마찬가지로 y = ax^2 + bx + c 형식의 2차 다항식이라면 세 점을 통과하는 선을 나타낼 수 있다. 이처럼 n차 다항식이 있으면, n + 한 개의 자유도를 가지게 할 수 있다.
이 사실은 n차 다항식에 대해서 [t{0} ... t{n}]에 대응하는 n + 한 개의 다른 값 [p{0} ... p{n}] (= 제어점의 좌표)을 알면, 그 n차 다항식을 타나태는 곡션의 계수 [c{0} ... c{n}]를 다음과 같이 이미 아는 값의 벡터에 역행렬을 곱해서 산출하고, 매개변수 곡선의 다항식을 구해 곡선상의 임의의 점을 계산할 수 있다는 것을 뜻한다. 이처럼 다항식을 사용해 보유한 데이터로부터 경향을 추정하는 방법은 곡선 맞춤의 일종으로서 통계학에서 이용된다.
곡선과 스플라인
다항식으로 매개변수 곡선을 나타낼 경우, 시점, 종점을 포함하는 제어점이 세 개라면 2차 다항식, 네 개라면 3차 다항식처럼, 제어점을 늘리면 늘릴수록 복잡한 곡선을 그릴 수 있다. 하지만 다음과 같은 바람직하지 않는 상황이 나타난다.
- 제어점이 늘어나면 다항식의 차수가 올라가므로, 식이 복잡성이 증가하고, 시작 쪽의 제어점 위치를 조정하면 마지막 제어점 구간의 곡선도 움직인다 = 국소적 제어가 듣지 않는 상태가 된다.
- 다항식의 차수가 올라가면, 매개변수에 연동한 다항식 값의 변동폭이 커진다.
그러므로, 곡선의 다항식 차수를 억제하면서 복수의 곡선을 절점으로 서로 연결하여, 하나의 긴 곡선으로 다루는 스플라인 방식의 곡선 표현이 일반적으로 이용된다.
스플라인을 구성함으로써, 구성 부분 각각의 곡선은 국소적 제어가 가능하여 다른 곡선에 영향을 주지 않는다. 또한, 각 곡선의 다항식은 차수를 억제할 수 있어 비교적 단순해진다.
한편으로, 곡선 연결법에 따라서는 곡선 내부에서는 매끄럽지만 절점 부분에서 두 개의 곡선이 급격한 각도로 연결되는 등 부자연스러운 상태가 되는 것도 예상되는 만큼, 절점에서의 매끄러운 연결을 어떻게 보증할지가 문제될 수 있다.
곡선 알고리즘 - 베지어 곡선
베지어 곡선은 프랑스의 자동차업체 르노의 베지어와 시트로엥의 드 카스텔조가 각각 독집적으로 자동차 디자인용으로 개발한 것으로, 가장 일반적인 곡선 알고리즘이다. 1차 베지어 곡선은 점 p{0}에서 점 p{1}를 향한 단순한 직선이다.
시간 t가 증가함에 따라 p{0}의 가중치(1-t)는 감소하고 p{1}의 가중치(t)가 증가한다. 이때 p{1} 와 p{1} 의 위치를 블렌딩한 하나의 점으로서 p{0}와 p{1}사이를 일정 속도로 이동해 간다.
다시 말해, 1차 베지어 곡선은 두 개의 제어점의 가중평균으로서의 선형보간을 한다.
2차 베지어 곡선은 1차 베지어 곡선을 두 개 블렌딩 한 것이다.
d(t)와 e(t)는 각각 d와 e의 위치를 t라는 매개변수로 변화시키는 매개변수 함수로, t의 1차 함수다. p(t)는 d(t)와 e(t)의 결과를 사용하므로, p(t)를 전개하면 d(t)나 e(t) 안의 t에 p(t) 자체의 t가 곱해지고, 식 안에 t^2이 나타난다. 이것이 베지어 곡선이 2차라는 직접적 근거다. 즉 2차 베지어 함수는 2차 함수이고, 이른바 포물선을 선형 변환한 것이다. 완성된 곡선은 시점과 종점 이외의 제어점은 지나지 않는다. 제어점이 늘어나도, 마찬가지로 베지어 곡선끼리 블렌딩해 가므로 제어점이 하나 증가할 때마다 다항식의 차수는 올라간다. 이렇게 최종적인 다항식을 재귀적으로 조립해가는 알고리즘을 드 카스텔조 알고리즘이라고 한다.
드 카스텔조 알고리즘을 사용하면, 최종적으로 제어점을 연결하는 선형보간으로 분해되어 간다. 선형보간이 아핀 변환에 의해 비율을 바꾸지 않는다는 점에서 보면, 베지어 곡선을 아핀 변환하고 싶은 경우는 아핀 변환한 제어점을 사용해 베지어 곡선을 그리면 기대한 효과를 얻을 수 있다. 이런 특성을 아핀 불변성이라고 한다.(원금투영 변환은 불변성이 없다.)
베지어 곡선의 다항식 B(t)를 일반화하면 다음 식이 된다.
캣멀롬 스플라인
캣멀롬 스플라인은 CG에서 부드러운 키프레임 애니메이션을 실현할 때 사용된다. 곡선 알고리즘으로서는 3차 에르미트 곡선을 사용한다. 캣멀롬 스플라인은 모두 제어점을 통과해 보간하는 특징이 있다. 또한 국수적으로 제어할 수 있어 C^1 연속성이 있다.
3차 에르미트 곡선은 시점 P{0}, 종점 P{1}이라는 두 개의 제어점 외에, P{0}에서의 접선(=곡선의 방향과 속도)인 P`{0}과 P`{1} 에서의 접선 P`{1}이라는 네 개의 벡터를 사용한다. 이 조건을 만족하는 다항식 H(t)를 구해보자.
H(t)는 3차 매개변수 곡선이므로 3차 다항식일 것이다.
또한, t ∈ [0, 1] 이므로 시점, 종점과 그들의 접선의 조건을 H(t)에 적용하기로 한다. 우선은 시점이다 시점 t = 0 이므로 다음과 같다.
마찬가지로 종점은 t = 1이므로 다음과 같다.
H(t)를 미분한 도함수는 다음과 같다.
또한, t = 0 일때의 접선은 다음과 같다.
또한 t = 1 일때의 접선은 다음과 같다.
이상의 연립방정식을 풀어보자.
이제 계수가 모두 구해졌으므로 원래 다항식에 대입하면, 다음과 같은 3차 에르미트 곡선의 다항식을 얻을 수 있다.
B 스플라인
B 스플라인은 베지어 곡선을 일반화한 알고리즘으로서 알려졌다. B 스플라인 C^2 연속성을 가지므로 절점끼리 매끄럽게
연결되며, 국소 제어가 가능해 부분적인 조정을 세밀하게 할 수 있다. 그 대신 보간이 아닌 근사로 제어점은 지나지 않는다.
베지어 곡선에서는 블렌딩 함수로서 제어점에 가중치를 두는 번스타인 다항식을 이용했지만, B 스플라인에서는 B 스플라인 기저 함수가 쓰인다. n + 1 개의 제어점을 p{i}(i는 0부터 n), k를 차수보다 1 많은 오더, n + k + 1 개의 절점을 x{i} (i는 0부터 n + k)라고 했을 때, 제어점의 수와 차수는 B 스플라인에서는 독립적이며, 제어점의 수는 오더 이상이라면 몇 개가 되든 상관없다.
스플라인 함수의 계산에는 드 카스텔조 알고리즘의 일반화인 드 보어 알고리즘이 사용된다. 블렌딩 함수를 그림으로 나타내면 피라미드 모양이다. 3차 B 스플라인(오더 4)으로 말하자면 오더 4의 블렌딩 함수를 만들기 위해 오더 3의 블렌딩 함수를 조합하는 것처럼 차례로 낮은 오더의 블렌딩 함수를 재귀적으로 호출하고, 구체적인 값으로서 오더 1의 값이 0이나 1로 돌아온 것을 모아 높은 오더로 반환해서, 계수를 곱해 합성하게 된다.
B 스플라인의 특징은 내 게의 점을 선택하고, P{i-1}과 P{i}를 근사를 위해서 계속 사용하면서 P{i-2}, P{i+1}은 접선을 구하기 위해 사용하는 조작을 최초의 제어점으로부터 하나씩 앞으로 나아가며 차례로 반복해가는 것이다.
지금까지 설명한 B 스플라인은 엄밀히 말하면 균일 B 스플라인이라고 해서, 절점 간격이 일정한 것을 가리킨다. 절점 간격이 일정하지 않은 B 스플라인은하다고 하고, 제어점에 가중치를 부여하면 유리하다고 한다. B 스플라인의 일반화인 NURBS는 비균일 유리 B 스플라인이다.
