Coderifleman's blog

frontend development stories.

「Algorithm」로 분류되는 글

  • 베지에 곡선과 관련된 수학적 증명 방법과 알고리즘은 1959년 프랑스의 자동차 업체 시트로엥(citroen)에서 근무하던 물리학자이자 수학자인 파울 드 카스텔조(Paul de Casteljau)가 최초 고안했다. 다른 말로 카스텔조 곡선(Casteljau curve)이라고 부른다.

    하지만 시트로엥의 정책으로 인해 카스텔조가 얻은 성과가 1974년까지 발표되지 못했고 1962년에 프랑스 자동차 회사 르노(Renault)에서 근무하던 엔지니어 피에르 베지에(Pierre Bézier)가 자동차를 디자인하는 과정에서 이 곡선을 독자적으로 개발해 사용하면서 그의 이름으로 널리 알려지게 된다.

    정의

    베지에 곡선은 간단히 말해 복수의 조절점(Control point)을 이용해 매끄러운 곡선을 그릴 수 있는 가장 일반적인 매개 변수 곡선(Parametric curve) 이다. 매개 변수 곡선이란 매개 변수를 사용해 함수를 일반화하여 곡선을 그려내는 방법을 말한다.

    베지에 곡선의 조절점과 가이드 포인트
    <그림 1. 베지에 곡선의 조절점과 가이드 포인트>

    조절점이란 곡선의 모양을 결정하는 데 사용되는 점의 집합 또는 구성원을 뜻하며 가이드 포인트는 곡선의 모양을 변경시킬 수 있는 조절 가능한 점을 뜻한다. 그림 1의 점을 왼쪽부터 차례대로 P0, P1, P2, P3라고 할 때 보통 P0와 P3는 고정해두고 P1과 P2를 조절해 곡선을 변형한다. 이때 이 P1과 P2를 가이드 포인트라 한다.

    베지에 곡선엔 차수가 붙는데 이 차수는 조절점의 개수에 따라 정해진다. 간단히 말해 N 개의 조절점으로 그려진 곡선을 N - 1차 베지에 곡선이라 한다. 예를 들어 그림 1은 조절점이 4개이므로 4 - 1 즉, 3차 베지에 곡선이다.

    베지에 곡선이 그려지는 개괄적인 원리는 이전에 포스팅했던 「중학생도 알 수 있는 베지에 곡선(Bézier Curves)」을 참고하자. GIF 애니메이션을 이용해 이해하기 쉽게 설명돼 있다.

    이번 편에서는 블렌딩(Blending)과 보간(Interpolcation)을 소개한다. 이 지식만 습득하면 나머지 n 차 베지에 곡선은 자연스럽게 이해할 수 있다.

    에버리징과 블렌딩

    점 A와 점 B의 중앙
    <그림 2. 점 A와 점 B의 중앙>

    자, 위 그림 2와 같이 서로 떨어져 있는 점 A와 점 B가 있다고 해보자. 이때 점 P를 이 두 점 사이의 평균 즉, 선분의 중앙에 두고 싶다면 어떻게 해야 할까?

    P = (A + B) / 2

    위처럼 간단히 평균을 구해 중앙에 둘 수 있다. 이 수식을 조금 다르게 전개해보자.

    P = (A + B) / 2
      = (A + B) * ½
      = ½A + ½B
      = .5A + .5B
      = (.5 * A) + (.5 * B)

    위 수식을 이용한 연산을 블렌딩(Blending)이라고 표현한다. 지정된 각각의 비율에 맞춰 적절히 혼합하는 것이다. 자, 이제 같은 값이 아닌 가중치(Weights)를 줘서 블렌딩해보자.

    점 A와 점 B의 블렌딩 비율 조절
    <그림 3. 점 A와 점 B의 블렌딩 비율 조절>
    P = (.35 * A) + (.65 * B)

    이번엔 A는 0.35(35%), B는 0.65(65%)로 비율을 조정해 블렌딩했다. 이때 두 비율의 합은 당연하겠지만 1(100%)이 돼야 한다. 이것은 반드시 지켜져야 할 필수 조건이다. 이어서 비율 값을 다음과 같이 일반화해보자.

    P = (s * A) + (t * B)

    s는 A의 비율을, t는 B의 비율을 나타낸다. 만약 s가 높으면 t는 낮아지고 반대로 t가 높으면 s는 낮아질 것이다. 잠깐, s와 t는 서로 영향을 주며 두 수의 합은 항상 1이 돼야 한다. 그렇다면 s는 1 - t와 같다고 할 수 있다.

    P = ((1-t) * A) + (t * B)

    이제 변수 t 하나만으로 비율을 조정해 블렌딩할 수 있다. 이 수식은 다음과 같이 표현될 수 있다.

    P = ((1 - t) * A) + (t * B)
      = (1 - t) * A + t * B
      = A - tA + tB
      = A + t(-A + B)
      = A + t(B - A)

    이 글에서는 수식 P = (s * A) + (t * B)를 사용해 설명을 이어가겠다. 다시 한번 말하지만 s = 1 - t다. 여기에 몇 가지 규칙이 추가된다. 만약 변수 t가 0이라면 P는 항상 A와 같으므로 다음과 같이 표현될 수 있다.

    P = ((1 - t) * A) + (t * B)
      = ((1 - 0) * A) + (0 * B)
      = (1 * A) + (0 * B)
      = A

    또 변수 t가 1이라면 P는 항상 B와 같으므로 다음과 같이 표현될 수 있다.

    P = ((1 - t) * A) + (t * B)
      = ((1 - 1) * A) + (1 * B)
      = (0 * A) + (1 * B)
      = A + B - A
      = B

    이제 수식과 몇 가지 규칙을 참고하여 블렌딩하는 자바스크립트 함수를 작성해보자.

    const A = 20;
    const B = 198;
    
    function blender(A, B, t) {
        if (t === 0) {
            return A;
        }
    
        if (t === 1) {
            return B;
        }
    
        return ((1 - t) * A) + (t * B); // or A + t * (B - A)
    }
    
    const blend = blender.bind(null, A, B);
    
    console.log(blend(.0)); // 20
    console.log(blend(.2)); // 55.6
    console.log(blend(.4)); // 91.2
    console.log(blend(.6)); // 126.8
    console.log(blend(.8)); // 162.4
    console.log(blend(1));  // 198

    See the Pen qRBdvb by Uyeong Ju (@uyeong) on CodePen.

    복합 데이터 블렌딩

    이번에는 「에버리징과 블렌딩」 절에서 이해한 수식을 이용해 복합 데이터(Compound data)를 블렌딩해보자. 블렌딩 수식만 잘 활용하면 2차원 또는 3차원 같은 복합적인 데이터도 쉽게 블렌딩할 수 있다.

    Px = (s * Ax) + (t * Bx)
    Py = (s * Ay) + (t * By)
    Pz = (s * Az) + (t * Bz)

    3차원인 경우 위처럼 개별적으로 블렌딩한 후 연산된 값을 조합해 사용한다.

    2차원에서 점 A와 점 B의 중앙
    <그림 4. 2차원에서 점 A와 점 B의 중앙>

    전 절에서는 점 A와 점 B가 동일 선상에 놓여있는 1차원적 상황이었지만 이번엔 그림 4 처럼 2차원 상황에서 P를 구해보자. 2차원에서는 x와 y 좌표로 점의 위치가 결정된다. 따라서 x와 y를 개별적으로 블렌딩한 후 구해진 값을 조합하면 P의 위치를 구할 수 있다.

    2차원에서 점 P의 위치 구하기
    <그림 5. 2차원에서 점 P의 위치 구하기>
    Px = (s * Ax) + (t * Bx)
    Py = (s * Ay) + (t * By)
    P = {Px, Py}

    위 수식은 자바스크립트 코드로 다음과 같이 표현할 수 있다.

    const Ax = 20;
    const Ay = 144;
    const Bx = 198;
    const By = 72;
    
    const blendX = blender.bind(null, Ax, Bx);
    const blendY = blender.bind(null, Ay, By);
    
    // t = .5
    // P = { blendX(t), blendY(t) }

    See the Pen EZxVVV by Uyeong Ju (@uyeong) on CodePen.

    보간

    마지막으로 보간(Interpolation)의 개념을 짤막하게 소개한다. 러핑(Lerping)이라고도 부르는 보간은 시간이 지남에 따라 블랜드 가중치를 변경하여 블렌딩을 수행하는 것을 말한다. 시간은 멈춰있지 않고 지속해서 흐르는 특징이 있으며 블랜드 가중치는 이 흐르는 시간에 의해 결정된다.

    쉽게 말해 특정 값으로 블렌딩하는 게 아닌 지속해서 흐르는 시간에 근거해 블렌딩 하는 것이다. 이러한 과정은 대개 update()로 표현된다. 아래 자바스크립트 코드를 보자.

    function interpolator(Ax, Bx, Ay, By, duration) {
      return function(update) {
      	 // x, y 블랜드 함수 준비
        const blendX = blender.bind(null, Ax, Bx);
        const blendY = blender.bind(null, Ay, By);
        
        ... 중략 ...
        
        function step(timestamp) {
          
          ... 중략 ...
          
          // 현재 시간에 해당하는 진행 값 즉, t 값 연산
          const pastTime = timestamp - startTime;
          let progress = pastTime / duration;
    
    	   // t 값을 이용해 블렌딩하고 update 콜백 함수 호출
          update(blendX(progress), blendY(progress)); // Blending...
    
          ... 중략 ...
          
          requestAnimationFrame(step);
        }
        
        requestAnimationFrame(step);
      }
    }
    
    const interpolate = interpolator(Ax, Bx, Ay, By, 1000);
    
    interpolate(function(nx, ny) {
    	// 1초간 Interpolating.
    	// P = {nx, ny}
    });

    우선 requestAnimationFrame()를 사용해 지정한 시간 만큼 흐르게 한다. 그리고 현재 시각에 해당하는 진행 값 즉, t를 구한 후 이 값을 근거해 블렌딩한다.

    See the Pen dNbgQp by Uyeong Ju (@uyeong) on CodePen.

    보간은 페이드인, 아웃 같은 애니메이션 처리나 3D 게임에서의 객체 움직임 그리고 오디오 크로스페이드 처리 등에 유용하게 사용된다.

    여기까지 2편을 마치고, 다음 편에서 이 지식을 바탕으로 1, 2차 베지에 곡선을 소개하겠다.

    참고

  • 퇴근 후 여느 때와 마찬가지로 PlayStation 4 전원에 손이 향하는 순간, 오랫동안 관리하지 못한 react-preloader-icon 컴포넌트가 돌연 떠올랐다. react-preloader-icon은 SVG Loaders의 아이콘을 React 컴포넌트로 옮기고 있는 작은 사이즈의 프로젝트다.

    SVG Loaders에 디자인된 아이콘은 12개밖에 안되지만 게으른 나머지 아직 2개밖에 옮기지 못했다. 그래서 게임은 잠시 제쳐두고 Spinning과 Puff 아이콘을 한번 React 컴포넌트로 옮겨보기로 했다.

    Spinning과 Puff
    <그림 1. Spinning과 Puff>

    SVG와 3차 베지에 곡선

    Spinning 아이콘은 손쉽게 옮겼지만, Puff 아이콘은 좀 달랐다. 이전에 옮긴 아이콘 모두 애니메이션이 선형적(linear) 이기 때문에 신경 쓸 게 없었다. 하지만 Puff 아이콘의 SVG는 조금 다른 방식으로 만들어져 있다.

    <svg width="44" height="44" viewBox="0 0 44 44" xmlns="http://www.w3.org/2000/svg" stroke="#fff">
        <g fill="none" fill-rule="evenodd" stroke-width="2">
            <circle cx="22" cy="22" r="1">
                <animate attributeName="r"
                    begin="0s" dur="1.8s"
                    calcMode="spline"
                    values="1; 20"
                    keyTimes="0; 1"
                    keySplines="0.165, 0.84, 0.44, 1"
                    repeatCount="indefinite" />
                    ... 중략 ...
            </circle>
        </g>
    </svg>

    위 코드에서 animate 엘리먼트를 살펴보자. 이 엘리먼트는 calcMode, values, keyTimes, keySplines 속성을 갖고 있다. 일단 이 속성에 관한 지식이 전혀 없기 때문에 우선 SMIL 스펙 문서를 살펴봤다.

    스펙 문서를 통해 calcMode값의 타이밍을 제어할 함수를 선택하는 속성임을 알 수 있다. 속성 값으로 “discrete”, “linear”, “paced”, “spline” 중 하나를 지정할 수 있다.

    위 코드의 calcMode 속성에는 “spline”이 지정돼 있는데 “spline”으로 지정하면 values, keyTimes, keySplines 속성과 함께 “3차 베지에 곡선“으로 값을 제어할 수 있다.

    잠깐, “3차 베지에 곡선”이라고? 다들 CSS로 애니메이션을 처리할 때 cubic-bezier라는 애니메이션 타이밍 함수를 한 번쯤 사용해본 적이 있을 것이다. cubic-bezier… 그렇다. 3차 베지에라는 뜻이다.

    CSS와 3차 베지에 곡선

    cubic-bezier 애니메이션 타이밍 함수는 x, y, x`, y` 즉, 4개의 값을 인자로 전달받아 에니메이션의 타이밍을 조절한다. x, y는 첫 번째 가이드 포인트(Guide Point)의 좌표, x`, y`은 두 번째 가이드 포인트의 좌표다. 가이드 포인트란 곡선의 형태에 영향을 주는 조절 가능한 점을 뜻한다.

    3차 베지에 곡선의 가이드 포인트
    <그림 2. 3차 베지에 곡선의 가이드 포인트>

    3차 베지에 곡선이란 이 두 가이드 포인트의 위치에 따라 그려지는 곡선을 말한다. cubic-bezier는 이 곡선을 이용해 에니메이션의 타이밍을 조절한다(이 속성은 cubic-bezier.com, CSS3 Bezier Curve Tester, desmos에서 간단히 테스트해 볼 수 있다).

    cubic-bezier를 이용해 선언한 Easing 함수 셋
    <그림 3. cubic-bezier를 이용해 선언한 Easing 함수 셋>

    우리가 알고 있는 easeInSine, easeInQuad 등과 같은 Easing 함수(참고)는 모두 이 베지에 곡선을 이용해 미리 만든 일종의 셋이다.

    한걸음 더…

    자, 본래 이야기로 다시 돌아와서…

    SVG의 calcMode="spline"의 의미를 살펴봤으니 bezier-easing같은 npm 모듈을 사용해 Puff 아이콘을 React 컴포넌트로 옮기면 된다. 하지만 커밋을 완료하고 따듯한 이불 속에서 편안한 마음으로 잠자리에 들기엔 모르는 것이 너무나 많다.

    왜 베지에 곡선이라 부를까? 무엇을 근거로 1차, 2차, 3차라고 나눌까? 또, 곡선이 그려지는 원리와 공식은 무엇일까? 몇 가지 물음이 잠 못 이루게 했고 결국 이 주제로 글을 작성하게 됐다.

    그럼 다음 편부터 본격적으로 베지에 곡선에 관해서 연재하도록 하겠다.

    참고

  • 읽기전에...

    이 문서는 일본어 「中学生でもわかるベジェ曲線」를 번역한 글입니다.

    “베지에 곡선”을 이용해 렌더링하게 되면 꽤 재미있고 편안하게 그림을 그릴 수 있다. 오늘은 이를 사용하는 누구라도 그 원리를 이해할 수 있도록 설명하고자 한다.

    “베지에 곡선”이라는 것은 매끄러운 곡선을 그리기 위한 것이지만 설명은 우선 단순한 직선부터 시작하겠다. 아래 그림 1 처럼 직선에서의 점의 움직임이 모든 “베지에 곡선”의 기본이 되기 때문이다.

    1차 베지에 곡선
    <그림 1. 1차 베지에 곡선>

    하나의 직선이 있고 그 위를 점 M이 일정 속도로 이동하고 있다. 이 점 M의 궤적은 당연하지만 단순한 직선으로 그려진다. 좋다. t선분 위를 비율적으로 얼마나 나아갔는지를 나타내는 수치다.

    여기에 선을 하나 더 추가하고 그 위에 M처럼 이동하는 점을 놓아보자. 그리고 원래의 점 MM0로, 새로운 점을 M1으로 부르자. M0M1이 움직이는 규칙은 이전과 같다. M1이라는 점이 하나 더 늘었다 하더라도 특별히 복잡해질 것은 없다.

    2차 베지에 곡선
    <그림 2. 2차 베지에 곡선>

    자, 여기에서 M0M1을 잇는 선을 하나 더 그을 수 있다. 그 선은 M0M1이 이동하면 자연스럽게 함께 움직이게 된다. 이제 그 선에 주목해보자. 그 선 위에 M0M1처럼 일정 속도로 이동하는 점을 놓을 수 있다. 그 점을 B라고 하자. 그리고 점 B가 그리는 궤적을 살펴보자. 그렇다. 점 B가 그리는 궤적을 2차 베지에 곡선(Quadratic Bezier Curve)이라고 한다.

    P0, P1 등 을 조절점(Control Point)이라고 한다. 이제 조절점을 하나 더 늘린 “베지에 곡선”을 상상해보자.

    아래 그림 3을 보면 새로운 점 P3가 추가돼 있고 P2P3를 선으로 잇고 있다. 그리고 M0M1과 같이 그 선 위를 이동하는 점을 생각해 볼 수 있다. 그 점의 이름은 M2라 하자.

    3차 베지에 곡선
    <그림 3. 3차 베지에 곡선>

    자, 2차 베이제 곡선에서는 P0, P1, P2의 조합으로 점 B의 위치를 정할 수 있었다. 그렇다면 마찬가지로 P1, P2, P3의 조합으로도 비슷하게 점의 위치를 정할 수 있을 것이다.

    이전에 부르던 점 BB0라고 부르기로 하고 P1, P2, P3의 조합으로 정해지는 새로운 점을 B1이라고 부르기로 하자. 그렇게 하면 이전과 마찬가지로 점 B0와 점 B1을 잇는 선과 그 선 위를 일정한 속도로 움직이는 점을 다시 생각해 볼 수 있는데 이때 그 점이 그리는 궤적을 3차 베지에 곡선(Cubic Bezier Curve)이라고 한다.

    여기에서 끝이 아니다. 조절점을 한 개 더 늘려 P0, P1, P2, P3 조합과 P1, P2, P3, P4 조합으로 결정되는 선과 그 선을 일정 속도로 이동하는 점 B2를 추가하고 B1B2를 잇는 선을 놓고 그 위를 지나가는 또 다른 점을 추가한 후 그 점이 그리는 궤적을 살펴볼 수 있다. 이런 식으로 곡선은 얼마든지 복잡하고 다양하게 만들 수 있다. P0부터 P4로 정해지는 곡선은 4차 베지에 곡선(Quartic Bezier Curve)이라고 부른다. 하지만 조절점을 5개 이상 늘려도 실용적인 측면에서 특별한 이점이 없으므로 일반적으로 3차 베지에 곡선까지 사용된다.

    여기까지 간단하게 “베지에 곡선”에 관해 이야기했다. 한마디로 “베지에 곡선”이란 선분 위를 일정 속도로 움직이는 점과 그러한 점과 점을 잇는 또 다른 선분, 그리고 그 위를 일정 속도로 이동하는 또 다른 점 등을 조합해 최종적으로 특정 점이 그리는 궤적을 이용해 곡선을 그려내는 방법을 뜻한다. 이해하는 데 도움이 됐으리라 기대한다.