[Multimedia] Lecture 12. Curve and Spline

본 포스팅은 인하대학교 안남혁 교수님의 [202601-EEC4410-001] Multimedia을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

1. Implicit vs Parametric

 

• 암시적(Implicit): $f(x, y) = 0$ 꼴. 특정 점이 도형 위에 있는지 확인(True/False)하기 좋다. (예: 원의 방정식 $x^2 + y^2 = r^2$)
• 매개변수(Parametric): $p(t) = (x(t), y(t))$ 꼴. 시간에 따라 변화하는 위치를 계산하기 좋아 멀티미디어 애니메이션 및 곡선 표현에 훨씬 유리하다.

 

2. Bezier Curve

 

Linear Bezier Curve (1차 Bezier Curve)

두 개의 제어점 $P_0$와 $P_1$ 사이를 잇는 직선이다. 가장 단순한 형태이며, 두 점 사이를 일정한 비율 $t$로 내분하는 점들의 집합이다. $t$는 0에서 1 사이의 값을 가진다.

 

Quadratic Bezir Curve (2차 Bezier Curve)

 Quadratic Bezier Curve는 두 개의 Linear Bezier Curve을 혼합하여 생성된 곡선이다. 이 곡선의 가장 큰 기하학적 특징은 시작점 $A(p_0)$와 끝점 $C(p_2)$를 정확히 통과(interpolate)한다는 것이다. 반면 중간에 위치한 점 $B(p_1)$는 곡선이 통과하지 않으며, 단지 곡선이 그 방향으로 끌려가도록(pulled toward) 유도하는 역할을 한다.

 Quadratic Bezir Curve를 그리기 위해 Linear Interpolations을 재귀적으로 반복하는 de Casteljau Algorithm을 적용한다.

 

• 1단계: 세 개의 점 A, B, C가 주어졌을 때, 선분 AB와 선분 BC를 생각한다. 이 두 선분 위를 동일한 매개변수 비율 $t$에 따라 이동하는 두 점 E와 F를 각각 구한다.
• 2단계: 이렇게 구한 새로운 점 E와 F를 연결한 선분 EF 위를 다시 동일한 비율 $t$로 보간하여 최종 점 P의 위치를 결정한다. 이 과정을 모든 $t$ 값(0~1)에 대해 반복하여 점 P의 자취를 연결하면 곡선이 완성된다.

 

 

 수식적이고 공식적인 표기법에서는 점 A, B, C 대신 $p_0, p_1, p_2$라는 기호를 사용한다. 1차 보간으로 얻은 점들은 $p_0^1, p_1^1$로 표기하며, 최종적으로 곡선 위를 지나는 점은 $p_0^2 = p(t)$가 된다.

 

여기서 점 B, 즉 $p_1$을 곡선의 제어점(Control point)이라고 부른다. 중요한 점은 2차 베지에 곡선이 이 제어점에 절대 직접 닿지 않는다는 사실이다. 하지만 이 제어점의 위치가 곡선이 얼마나 휘어질지를 결정하는 곡률(curvature)에 직접적인 영향을 미친다.

 

Cubic Bezier Curve (3차 Bezier Curve)

Cubic Bezier Curve는 2개의 Quadratic Bezier Curve 또는 3개의 Linear Bezier Curve을 혼합하여 생성한다.

 

 

• 1단계: 4개의 점 A, B, C, D가 주어졌을 때, 선분 AB, BC, CD 위를 $t$ 비율로 이동하는 점 E, F, G를 각각 찾는다.
• 2단계: 새로 구한 점들을 이은 선분 EF, FG 위를 다시 동일한 비율 $t$로 이동하는 점 Q, R을 찾는다.
• 3단계: 마지막으로 선분 QR 위를 $t$ 비율로 이동하는 최종 점 P를 계산한다. $t$가 변함에 따라 이 점 P가 그리는 궤적이 바로 3차 베지에 곡선이 된다.

 

 

 공식적인 수식에서는 4개의 점을 $p_0, p_1, p_2, p_3$로 표기한다. 이 중 중간에 위치한 B와 C (수식 표기로는 $p_1$과 $p_2$)는 제어점(Control point) 역할을 한다.

 

 가장 중요한 특징은 곡선이 이 제어점들에 절대 직접 닿지 않는다는 사실이다.하지만 제어점의 위치는 곡선이 어떻게 휘어질지를 결정하는 곡률(Curvature)에 직접적인 영향을 준다.

 

 High-order Bezier Curve는 실제로 잘 쓰이지 않고, Quadratic 및 Cubic Bezier Curve을 가장 표준적으로 사용한다. 만약 3차 곡선 하나로 표현할 수 없는 복잡한 모양을 만들어야 한다면, 3차 곡선 여러 개를 부드럽게 이어 붙이는 Spline 방식을 사용한다.

 

• 직관적인 제어 불가능 (Little Controllability): 점이 많아질수록 특정 점을 움직였을 때 곡선 자체가 어떻게 변할지 예측하기 어려워진다.
• Runge's Phenomenon: 높은 차수를 사용하면 곡선의 양 끝단에서 심하게 요동치는 현상(undesired wiggles)이 발생하는 문제가 있다. -> 수학적으로 완벽하게 맞추려다 하다보니 발생함

 

de Casteljau Algorithm (드 카스텔조 알고리즘)

 

 de Casteljau Algorithm은 주어진 점들 사이를 특정 비율 $t$ (0에서 1 사이의 값)로 연결하고, 새로 생긴 점들을 다시 같은 비율 $t$로 연결하는 과정을 최종적으로 '단 하나의 점'이 남을 때까지 반복(Recursive)하는 것이다.

 

• Quadratic Bezier Curve 예시:
  • 3개의 점 $p_0, p_1, p_2$가 주어졌을 때의 과정이다.
    1. $p_0$와 $p_1$ 사이를 $t$ 대 $(1-t)$로 내분하는 점 $p_0^1$을 구한다. ($p_0^1 = (1-t)p_0 + tp_1$)
    2. $p_1$과 $p_2$ 사이를 동일하게 $t$ 비율로 내분하는 점 $p_1^1$을 구한다.
    3. 이제 새로 생긴 두 점 $p_0^1$과 $p_1^1$ 사이를 다시 $t$ 비율로 내분하는 점 $p_0^2$를 구한다. 이 점 $p_0^2$가 바로 곡선 위를 지나는 실제 점이 되며, $t$가 0에서 1로 변함에 따라 점이 이동하며 곡선을 그리게 된다.
• Cubic Bezier Curve 예시: 
  • 대부분의 그래픽 프로그램에서 사용하는 4개의 점 $p_0, p_1, p_2, p_3$를 사용하는 방식이다.
    
    1. 4개의 점 사이에서 3개의 새로운 점($p_0^1, p_1^1, p_2^1$)을 찾는다. 
    2. 그 3개의 점 사이에서 다시 2개의 점($p_0^2, p_1^2$)을 찾는다.
    3. 마지막으로 2개의 점 사이에서 1개의 점($p_0^3$)을 찾으면, 그 점이 곡선의 위치가 된다. 슬라이드의 트리(Tree) 구조 다이어그램은 이처럼 점의 개수가 하나씩 줄어드는 계산 과정을 시각적으로 잘 보여준다.

 

 $n$차 Bezier Curve을 그리기 위해서는 $(n+1)$개의 제어점(Control Points)이 필요하다. 이때 슬라이드 우측 하단의 피라미드 숫자 배열(1, 1 1, 1 2 1, 1 3 3 1 ...)은 파스칼의 삼각형을 나타내며, 이는 곡선 공식에서 각 제어점이 가지는 영향력(가중치)의 계수를 의미한다.

 

 예를 들어 3차 곡선의 최종 공식은 $p(t) = (1-t)^3p_0 + 3t(1-t)^2p_1 + 3t^2(1-t)p_2 + t^3p_3$ 인데, 여기서 계수가 파스칼 삼각형의 3번째 줄인 1, 3, 3, 1을 따르는 것을 볼 수 있다.

 

• 4차 Bezier Curve 예시:
  • 4차 베지에 곡선(Quartic Bezier Curve)은 5개의 제어점($P_0, P_1, P_2, P_3, P_4$)을 사용하여 정의된다.
    
    번스타인 다항식(Bernstein Polynomial)의 일반식 $B_i^n(t) = \binom{n}{i} t^i (1-t)^{n-i}$에 차수 $n=4$를 대입하여 전개하면 파스칼의 삼각형 5번째 행의 계수인 1, 4, 6, 4, 1을 따르게 된다.
    
    이에 따른 4차 베지에 곡선의 최종 방정식은 다음과 같다.(여기서 $t$는 $0 \le t \le 1$의 범위를 가진다.)
    $$P(t) = (1-t)^4 P_0 + 4t(1-t)^3 P_1 + 6t^2(1-t)^2 P_2 + 4t^3(1-t) P_3 + t^4 P_4$$

 

2024-2 기말고사

• 정답:
  5차 베지에 곡선(Quintic Bezier Curve)은 총 6개의 제어점($P_0, P_1, P_2, P_3, P_4, P_5$)을 사용하여 정의된다.
  
  번스타인 다항식(Bernstein Polynomial)의 일반식 $B_i^n(t) = \binom{n}{i} t^i (1-t)^{n-i}$에 차수 $n=5$를 대입하여 전개하면 파스칼의 삼각형 6번째 행의 계수인 1, 5, 10, 10, 5, 1을 따르게 된다.
  
  이에 따른 5차 베지에 곡선의 최종 방정식은 다음과 같다.(여기서 $t$는 $0 \le t \le 1$의 범위를 가진다.)
  $$P(t) = (1-t)^5 P_0 + 5t(1-t)^4 P_1 + 10t^2(1-t)^3 P_2 + 10t^3(1-t)^2 P_3 + 5t^4(1-t) P_4 + t^5 P_5$$

 

Tessellation

• 수학적으로 완벽하게 매끄러운 곡선을 한 번에 처리하여 그리는 것은 어렵다. 따라서 곡선을 여러 개의 짧은 직선 조각(line segments)으로 나누어 근사하는 방식을 사용하며, 이 과정을 Tessellation이라고 부른다.
  
  결과적으로 파라미터 $t$의 간격을 얼마나 조밀하게 나눌 것인지(얼마나 많은 점을 찍을 것인지)에 따라 렌더링 품질이 결정된다. $t$를 잘게 쪼갤수록 곡선은 더욱 매끄러워지지만 화면에 그리기 위해 계산해야 하는 직선의 개수도 함께 증가하게 된다.

 

3. Spline

 앞서 배운 High-order Bezier Curve는 차수가 높아질수록 한계점들이 명확하였다. 이를 해결하기 위해 등장한 것이 바로 Spline이다.

 

 Spline은 제어하기 쉬운 낮은 차수의 곡선을 여러 개 이어 붙여 만든 하나의 긴 곡선을 의미한다.

• 매듭 (Knot): 각 개별 곡선들이 서로 맞닿아 연결되는 끝점(또는 시작점)을 매듭이라고 부른다.
• $t$: Spline은 전체를 아우르는 Global $t$ (시작부터 끝까지 0에서 1로 증가)와, 각 곡선 구간마다 별도로 적용되는 Local $t$ (매듭을 지날 때마다 0으로 리셋됨)를 동시에 가진다.

 

 여러 개의 곡선을 이어 붙였을 때, 매듭(Knot)가 얼마나 부드러운지를 수학적으로 정의한 것이 Continuity이다.

 

 

• $C^0$ continuity (Position): 두 곡선이 단순히 끊어지지 않고 한 점에서 만나기만 한 상태다. 위치만 일치하기 때문에 이음새 부분에서 뾰족하게 꺾일 수 있다.
• $C^1$ continuity (Velocity): 위치뿐만 아니라 1차 미분값(속도, 즉 접선의 기울기)까지 일치하는 상태다. 시각적으로 꺾임 없이 부드럽게 연결되어 보이며, 가장 널리 쓰이는 조건이다.
• $C^2$ continuity (Acceleration): 위치, 1차 미분(속도), 그리고 2차 미분(가속도, 즉 곡률의 변화량)까지 모두 일치하는 상태다. 이음새를 눈으로 전혀 분간할 수 없을 만큼 완벽하게 매끄러운 연결을 보장한다.

 

 

 Spline은 국소적 제어가 가능하다는 큰 특징을 갖고 있다. Control point의 위치를 수정했을 때, Spline 전체의 모양이 바뀌는 것이 아니라 해당 점 근처의 곡선 구간만 형태가 변한다. 

 

 곡선을 생성할 때 주어진 점들을 어떻게 활용하느냐에 따라 두 가지 방식으로 나뉜다.

 

 

• Interpolation: 곡선이 주어진 점들을 반드시 통과하며 그려지는 방식이다. Hermite Spline이나 Catmull-Rom Spline이 여기에 속한다. 점을 찍는 곳으로 선이 무조건 지나가기 때문에 초보자가 직관적으로 경로를 짜거나 디자인하기 훨씬 유리하다.
• Approximation: 곡선이 주어진 점들을 직접 통과하지 않고, 점들의 위치에 자석처럼 이끌려(guided) 형태가 결정되는 방식이다. 우리가 앞서 배운 Bezier Spline이 가장 대표적이다.

 

 

Cubic Bezier Spline

Cubic Bezier Curve들을 여러 개 이어 붙여서 만든 긴 곡선을 Cubic Bezier Spline이라고 부른다. 파워포인트의 곡선 그리기 도구나 어도비 펜 툴이 해당 방식을 사용한다.

 

Cubic Hermite Curve

 Herimite Spline은 Bezier Spline과 유사한 3차 곡선이지만 곡선을 제어하는 방식에서 큰 차이가 존재한다.

 

• Bezier Curve: 시작점과 끝점 외에, 곡선 밖에서 선을 끌어당기는 2개의 제어점 ($B, C$ 또는 $p_1, p_2$)의 위치를 지정한다.
• Herimite Curve: 제어점을 사용하는 대신, 시작점과 끝점에서의 속도(Velocity, 또는 접선 벡터 $U, V$)를 직접 지정한다. 즉, 선이 어느 방향으로 얼마만큼의 힘(크기)으로 뻗어 나갈지를 정해주는 방식이다.

 Bezier Curve와 Hermite Curve는 서로 완벽하게 변환될 수 있다.

 

 Cubic Bezier Curve의 공식을 시간 t에 대해 1차 미분(First-order derivation)하면, 곡선 위 특정 점에서의 접선 벡터(속도)를 구하는 식이 나온다.

 

 

• $t=0$ (시작점)일 때의 속도 $v_0$ (또는 $U$): $v_0 = \dot{p}(0) = 3(p_1 - p_0)$
• $t=1$ (끝점)일 때의 속도 $v_3$ (또는 $V$): $v_3 = \dot{p}(1) = 3(p_3 - p_2)$

 

 

 이 수식을 Bezier Curve의 Control point $p_1, p_2$를 구하는 식으로 다시 정리하면 다음과 같다.

• $p_1 = p_0 + \frac{1}{3}v_0$
• $p_2 = p_3 - \frac{1}{3}v_3$

 

 결론적으로, Herimite Curve의 속도 벡터($v_0, v_3$)를 알면 이를 3으로 나누어 Bezier Curve의 제어점 위치를 계산할 수 있고, 반대로 제어점 위치를 알면 속도 벡터를 구할 수 있다. 디자이너는 시각적으로 편한 베지에(제어점) 방식을 선호하고, 수학적으로 계산하는 프로그램 내부에서는 에르미트(속도 벡터) 방식을 활용할 수 있는 이유가 바로 이 수식 때문이다.

 

실무에서는 Bezier Spline나 Hermite Spline보다는 Catmull-Rom Spline을 경로 생성에 가장 많이 사용한다. 먼저, Catmull-Rom spline은 별도의 spline이라기 보다는 Cubic Hermite Spline의 특수한 기법에 해당된다.

 

• Cubic Hermite Curve의 단점: 곡선의 시작점과 끝점의 속도를 수학적으로 계산해서 입력해야 한다.
• Cubic Bezier Curve의 단점: control point를 일일이 마우스로 통과하게 만들어주어야 한다.

 

 반면에 Catmull-Rom spline은 점을 찍기만 하면 컴퓨터가 속도와 방향을 계산해주므로 편리하다. 컴퓨터가 자동으로 속도를 계산하는 원리는 다음과 같다.

$$p'(t_i) = \frac{p_{i+1} - p_{i-1}}{2}$$