Curve, Spline

Curve

Curve가 필요한 이유

• smoothness
  • discontinuity를 없애기 위해서 필요하다.
  • smooth shape, smooth movement를 표현하기 위해서 curve가 필요하다.

 

Curve 표현

컴퓨터그래픽에서는 prametric representation이 가장 적합하다.

• non-parametric
  • explicit
    • $y = f(x)$
    • 장점
      • point를 만들기가 쉽다.
      • 그려야 할 점의 위치를 표현하기에 쉽다.
    • 단점
      • 표현할 수 있는 모양에 제한이 있다.
      • 예를 들어, 수직선을 표현하지 못한다. 
        

        

  • implicit
    • $f(x, \, y) = 0$
    • 장점
      • point가 외부에 존재하는지, 내부에 존재하는지 알기 쉽다.
      • 좌표를 넣어서 음수면 내부에 위치하고, 양수면 외부에 위치한다.
    • 단점
      • point을 만들기가 힘들다.
      • x 값을 넣어도 y 값을 구하기 위해 추가적인 계산이 필요하다.
        

        

• parametric
  • $(x, y) = (f(t), g(t))$
  • 추가 parameter(t)를 도입해서 x와 y를 각각 t에 대해 표현한다.
  • parameter t는 curve 위에서 점의 local coordinate이다.
  • 장점
    • point를 만들기 쉽다.
    • t가 결정되면 x, y가 바로 결정된다.

 

---

Polynomial Curve

다항식으로 curve를 표현한다.

 

n차 다항식의 parametric representation은 다음과 같다.

$x(t) = a_n t^n + a_{n-1} t^{n-1} + ... + a_1 t + a_0$

 

장점

• 간단하다
• 효율적이다
• curve의 모양을 바꾸기도 쉽다.
• 오래전부터 사용되었다.

 

방법

• Polynomial interpolation
• Hermite curve
• Bezier curve

 

---

Polynomial Interpolation

주어진 데이터(점)을 지나도록 interpolation을 해서 polynomial을 만들어서 curve를 표현한다.

 

n차 다항식을 이용해서 interpolation을 한다.

n차 다항식을 구하기 위해서는 n+1개의 점이 필요하다.

 

그런데 차수(n)가 늘어나면 양쪽 끝부분에 대한 변동이 커진다.

따라서 보통 3차 다항식(cubic polynomial)을 이용한다.

 

Cubic Polynomial

3차 다항식은 3차원 curve를 표현하는 가장 작은 차수의 polynomial이다.

또한 차수를 3에서 더 높이지 않으면 끝쪽으로 갈수록 변동이 크지 않다.

 

따라서 주로 3차 다항식을 이용해서 interpolation 한다.

 

Spline

복잡한 curve는 spline을 통해서 구한다.

Spline은 여러 개의 다항식이 조각으로 연결된 piecewise polynomial이다.

 

Single Piece of Cubic Polynomial

$p(t) = at^3 + bt^2 + ct + d$

 

특정한 curve를 찾기 위해서 a, b, c, d를 알아야 한다.

4개의 미지수가 있으므로 4개의 정보가 필요하다.

• 4개의 point : linear polynomial
• 2개의 end point와 그 점에서의 변화율 : hermit curve

 

---

Linear Polynomial

두 가지 표현 방법이 있다.

• coefficients and variable
  • $p(t) = at^3 + bt^2 + ct + d$
    • coefficient(계수) : $a, b, c, d$
    • variable : $t$
• basis function and point
  • $p(t) = b_0 (t) p_0 + b_1 (t) p_1 + b_2 (t) p_1 + b_2 (t) p_2 + b_3 (t) p_3$
    • basis functions : $b_0 (t), b_1(t), b_2(t), b_3(t)$
    • point : $p_0, p_1, p_2, p_3$
      • = control point, data point

 

Basis Function

t의 값의 변화에 따라 각 control point들이 curve에 주는 영향력을 나타낸다.

아래에서 t가 커질수록 $p_1$의 영향이 큼을 알 수 있다.

 

예시

• $x(t) = (x_1 - x_0) t + x_0$
• $y(t) = (y_1 - y_0)t + y_0$
• coefficients and variable
  • $p(t) = (x(t), y(t)) = (p_1 - p_0) t + p_0$
  • matrix formulation
    • $p(t) = \begin{bmatrix} x(t) & y(t) \end{bmatrix}$
    • $= \begin{bmatrix} t & 1 \end{bmatrix} \begin{bmatrix} -1 & 1 \\  1 & 0 \end{bmatrix} \begin{bmatrix} p_0 \\ p_1 \end{bmatrix} $
• basis functions and point
  • $p(t) = (1-t) p_0 + tp_1$
  • matrix formulation
  • $p(t) = \begin{bmatrix} x(t) & y(t) \end{bmatrix}$
  • $= ( \begin{bmatrix} t & 1 \end{bmatrix} \begin{bmatrix} -1 & 1 \\ 1 & 0 \end{bmatrix} ) \begin{bmatrix} p_0 \\ p_1 \end{bmatrix}$

 

---

Hermite Curve

Linear polynomial보다 더 발전된 형식이다.

보통 cubic polynomial을 사용한다.

 

식을 구하기 위한 4개의 데이터로 다음을 준다.

• 2개의 end points
• 각 point 에서의 변화율

 

a, b, c, d 구하기

• $x(t) = at^3 + bt^2 + ct + d$
• $x \' (t) = 3at^2 + 2bt + c$

에서 t = 0과 t = 1일 때의 point가 주어지므로

• $x(0) = x_0 = d$
• $x(1) = x_1 = a +b+c+d$
• $x \' (0) = x \' _0 = c$
• $x \' (1) = x \' _1 = 3a + 2b + c$

 

따라서 $a, b, c, d$는 다음과 같이 된다.

 

Matrix Form

Basis matrix에서

• 각각의 row가 coefficient이다.
  • $a = 2p_0 -2p_1 + 1v_0 + 1v_1$
  • $b = -3p_0 + 3p_1 -2v_0 -1v_1$
  • ...
• 각각의 column이 basis function이다.
  • $b_0(t) = 2t^3 -3t^2 +0t + 1$
  • $b_1(t) = -2t^3 + 3t^2 + 0t + 0$
  • ...

 

Basis Function

각 basis function은 t에 따라 다음과 같은 그래프를 가지므로, $p_0, p_1, v_0, v_1$도 그에 비례해서 영향력을 가진다.

 

---

Bezier Curve

Hermite curve는 2개는 point로, 2개는 vector로 데이터를 받아온다.

Bezier curve는 $p_1$의 변화율을 뒤집어서 각 변화율의 끝에 점이 하나씩 더 있다고 생각해서 4개의 point로 데이터를 받아온다.

 

점의 위치까지의 거리의 3배가 해당 점에서의 변화율이다.

 

특성

• control point들을 움직여서 직관적으로 curve를 그릴 수 있다.
• 항상 curve는 control point들의 convex hull 안에 존재한다.
  • convex hull : point들을 모두 포함하는 가장 작은 크기의 볼록 다각형
• end point interpolation
  • 가운데 점을 지나는 것이 아니라 양 끝점을 지나는 curve이다.

convex hull of Bezier curve

 

활용 : Bezier Spline

Bezier curve의 조각(picewise)들을 이은 것이다.

Bezier curve의 연속이다.

 

다음과 같은 상황 속에서 널리 사용된다.

• 어도비 일러스트레이터와 같이 그래픽 도구에서 shape을 그리기 위해서 많이 사용된다.
• Blender나 Maya와 같이 3D authoring tool에서 animation path를 그리기 위해서 사용된다.
• TrueType font, PostScript font 등 글자를 나타내기 위해서 사용된다.

Bezier spline

 

Hermite to Bezier

아래에서 $p_0, p_1, v_0, v_1$은 Hermite curve의 control point이고, $q_0, q_1, q_2, q_3$가 Bezier curve의 control point이다.

 

• $p_0 = q_0$
• $p_1 = q_3$
• $v_0 = 3(q_1 - q_0)$
• $v_1 = 3(q_3 - q_2)$

 

Bezier Matrix

가 된다.

 

따라서 Bezier matrix는 다음과 같다.

 

Bernstein Polynomial

Bernstein polynomial을 이용해서 curve를 만든 것을 Bezier curve로 볼 수 있다.

Bezier curve에서 각 basis function은 Bernstein polynomial에서 나온다.

 

Basis Function

t에 따른 각 control point의 영향은 basis function을 따른다.

 

t = 0 일 때는 p0만 영향을 주고, t = 1에서는 p3만 영향을 준다.

 

De Casteljau's Algorithm

Bezier curve를 계산하는 또다른 방법이다.

 

다음과 같은 특성이 있다.

• Bezier curve의 점을 계산하기에 좋은 recursive algorithm이다.
• 하나의 Bezier curve를 2개의 Bezier curve(segment)로 나눌 수 있다. (subdivision)
• 나눠진 curve에 대해 별도의 연산을 수행할 수 있다.
• 충분히 많이 subdivision을 하면 각각의 segment의 control point를 연결하면 curve가 나온다.

 

알고리즘은 다음과 같다.

1. control point 4개를 이용해서 시작한다.
2. 인접한 contorl point끼리 $t:1-t$로 내분한다.
   • $q_0 = Lerp(t, p_0, p_1)$
   • $q_1 = Lerp(t, p_1, p_2)$
   • $q_2 = Lerp(t, p_2, p_3)$
3. 내분된 점끼리 또다시 $t:1-t$로 내분한다.
   • $r_0 = Lerp(t, q_0, q_1)$
   • $r_1 = Lerp(t, q_1, q_2)$
4. 얻어진 2개의 point를 다시 $t:1-t$ 내분하면 그것이 curve 위의 점이다.
   • $x = Lerp(t, r_0, r_1)$

 

그렇게 해서 얻어진 점은 다음과 같다.

$K, L, M, N$ : 기존의 control point

1. $A, B, C$
   • $A = (1-t)K + tL$
   • $B = (1-t)L + tM$
   • $C = (1-t)M + tN$
2. $P, Q$
   • $P = (1-t)A + tB$
   • $Q = (1-t)B + tC$
3. $T$ : Bezier curve 위의 점
   • $T = (1-t)P + tQ$

 

따라서 Bezier curve $T = (1-t)^3 K + 3t(1-t)^2 L + 3t^2(1-t) M + t^3 N$ 이 된다.

 

---

Displaying Curves

실제 curve를 렌더링 하는 방법

• curve에 존재하는 점들을 구해서 그 점들을 잇는 line segment를 그려야 한다.
• curve를 그리는 하드웨어는 거의 없다.(없다고 봐도 무방)

 

Curve 상의 각 점을 구하는 방법

• Brute-force
  • t 값을 조금씩 늘리면서 p(t)를 구하고, 구해진 각 점(p(t))들을 선으로 잇는다.
  • 이는 중복된 계산이 생길 수 밖에 없다.
• Final difference
  • 같은 일을 하지만 중복된 계산을 훨씬 줄일 수 있는 방법이다.
• Subdivision
  • de Casteljau's algorithm을 이용한다.
  • subdivision을 많이 수행해서 각 control point들을 잇는다.

 

---

Spline

Spline은 picewise polynomial로, 조각난 polynomial을 이은 것이다.

 

3가지 이슈가 있다.

• 어떻게 smooth하게 연결할 것인가
  • 이어지는 점에서의 변화율(기울기)가 같으면 된다.
  • 변화율의 점까지의 길이가 같으면 매끄러움이 더욱 보정된다.
• spline의 모양을 control 하는 것이 얼마나 쉬운가
  • 점 하나의 움직임이 local(근처)에만 영향을 주는지, 전체적으로 영향을 주는지
  • local에만 영향을 주는 것이 모양을 control 하기에 더 편하다.
• spline이 주어진 point들을 전부 지나는가
  • 주어진  point들을 모두 지나는지, 근처만을 지나는지

 

---

참고

본 포스트는 한양대학교 이윤상 교수님의 수업을 정리한 내용입니다.

출처: 한양대학교 이윤상 교수님 컴퓨터그래픽스 강의 강의자료 - https://cgrhyu.github.io/courses/2022-spring-cg.html

CGR LAB