[OpenGL ES] 17강 : 베지어 곡선, 드 카스텔조 알고리즘, 허밋(Hermit) 곡선, Bilinear Patch, 베지어 삼각형

이 강의는 유투브에 무료로 공개되어 있는 한정현 교수님의 컴퓨터 그래픽스 강좌를 정리한 글입니다. 자세한 내용은 강의를 직접 들으시거나 책을 구입하셔서 확인해 보세요. 강의 자료는 깃헙 링크에 올라와 있습니다.

---

요약 :

1. 베지어 곡선은, 주어진 정점(control point)을 잇는 곡선이다. 점이 N 개 있을때, N-1 차 베지어 곡선을 만들 수 있는데, 그냥 선형 보간을 여러 번 반복해서 취하면 된다. 이 기법을 드 카스텔조 알고리즘이라고 한다.

2. 테셀레이션은, 컴퓨터가 곡선 및 곡면을 처리하는 방식으로, 베지어 곡선 및 곡면을 작은 선분이나 폴리곤의 조합으로 쪼개는 과정을 의미한다. 간격이 작을 수록 더 매끈한 곡면을 만들 수 있을 것이다. 컨트롤 포인트를 기준으로 선형 보간을 반복하여 패치(patch)를 만들어 곡면을 표현할 수 있다.

3. 베지어 삼각형은, 기존의 겹선형 패치(bilinear patch) 를 만드는 것처럼, 사각형 모양의 패치를 만드는 것 대신, 삼각형 모양의 패치를 만들 때 사용된다. 무게중심 조합(barycentric combination) 기법을 사용하여, 선형 방정식을 재귀적으로 사용하면 베지어 삼각형 패치를 구할 수 있다.

베지어 곡선

우리는 이미 이전에 선분을 내분하여 보간하는 방법에 대해 배웠다. 위의 경우, t 가 0 과 1 사이에 있다고 가정하고, 선분을 나눈 방정식을 t 에 대해 표현한 것이다.

 

드 카스텔죠(de Castelijau) 알고리즘은, 이러한 선형 보간을 재귀적으로 행한 것이다.

즉, 선형 보간을 1 번 하면 t 에 대한 1차 방정식이 만들어지고, 2 번을 하면 2 차 방정식이 만들어진다. 이때, p0, p2 가 있다고 할 때, p1 이라는 점을 잡고 p1 으로 특정 점을 '잡아 끌었다'고 했을 때, 해당 점들의 집합이 어떻게 표현되는지 보자.

위에서 가운데 빨간색 곡선은, 해당 보간을 통해 만들어진 2차 방정식을 그대로 보여준다. p0 에서 p2 까지를 보간한 것이다! 😄

 

위에서는 p0, p2, 그리고 p1 을 이용해 2번 보간을 했는데... 사실 3번을 하지 못할 이유 따위는 없다 😆

3번을 하면, 그냥 뭐.. 간단히 생각해서, 3차 방정식이 나올 것이다. 다음과 같이 :

 

드 카스텔조 알고리즘은 더 높은 차수의 베지에 곡선을 위해 사용된다. 예를 들어, 5개의 점이 있을 때는 4차 베지에 곡선 방정식을 만들 수 있을 것이다.

그런데 더 높은 차수의 곡선은 괴상한 뒤틀림 현상이 발생하기도 하며, 각 포인트에 대한 근사적인 곡선을 제대로 표현해 주지도 않는다. 위 슬라이드에서의 4차 베지에 곡선을 보면, 그 의미를 바로 알 수 있을 것이다.

또한, 2차 곡선의 경우에는 flexibility 가 매우 떨어지므로, 3차 베지에 곡선이 제일 많이 사용된다 😊

 

p0, p1, p2... 같은 점을 control point 라고 부른다. n 차 베지에 곡선은 n + 1 개의 control point 를 필요로 할 것이다.

이때, 각 항의 계수는 t 의 다항식으로 표현되게 되는데... 이 계수들을 번스타인(Bernstein) 다항식이라고 부른다!

 

control point 의 위치에 따라 곡선의 모양이 달라진다..! 😮

 

 

테셀레이션 (Tessellation)

그런데, 컴퓨터는 사실 곡선을 '진짜' 곡선으로 받아들여 그려내지 않는다. 베지어 곡선은 사실 아주 작은 선분의 집합으로 쪼개지게 되는데... 이 과정을 바로 테셀레이션(tessellation) 이라고 한다!

아하~ 그렇게 주구장창 나오던, 어렵고 간지나게 느껴지던 테셀레이션이, 사실 베지에 곡선을 작은 선분 조각으로 나누는 과정에 불과했던 것이다  😅

당연히, t 값이 늘어나는 간격이 작으면 작을수록, 베지에 곡선에 더 많은 선분 조각들이 생길 것이고, 더 매끄러운 표현이 가능할 것이다(비용은 많이 들겠지만...).

 

이때, 테셀레이션을 한 녀석을 아핀 변환한다고 하자. 사실 순서를 어떻게 놓든 간에, 결과는 동일할 것이다(아핀 변환 -> 테셀레이션 이나, 테셀레이션 -> 아핀 변환 이나, 결과가 같다는 뜻이다)!

하지만... 테셀레이션을 하고 아핀 변환을 하는 것 보다는, 당연히 아핀변환을 하고 테셀레이션을 하는 것이 훨씬 효율적이다. 

왜? 아핀 변환을 먼저 하면 점 4 개에 대해서만 변환을 해주고 바로 테셀레이션을 진행하면 되지만, 테셀레이션을 한 다음 아핀 변환을 하면 쪼개진 선분의 각 점에 대해 변환 계산을 해 주어야 하기 때문이다 😉

 

허밋(Hermite) 곡선이라는 녀석도 있는데... 이건 뭘까?

우리는 베지에 곡선을 배워서, p0 에서 p3 까지의 베지에 곡선을 t 에 대한 3차식으로 표현할 수 있었다. 그걸 미분한 다음, 각각 p0 와 p1 에서의 값을 t 에 집어넣어 보자. 각각 0 과 1 이 될 것이다 😄

그럼, 정리했을때 아래와 같은 식을 얻게 된다 :

즉, 점 p0 와 p3 에서의 접선을 각각 v0, v3 라고 했을 때, 우리는 접선의 식을 pi 점들로 표현할 수 있게 되었다.

추가로, p1, p2 를 p0, p3, v0, v3 로 표현할 수 있게 되었다! 즉, 우리는 이제 p(t) 를 시작점인 p0 와 끝점인 p3, 그리고 각각의 점에서의 접선 v0, v3 만을 이용해 기존의 베지어 곡선을 동일하게 표현할 수 있게 되었는데, 이런 식으로 만든 곡선을 허밋 곡선(Hermite Curve) 라고 한다.

 

캣멀-롬 스플라인(Catmull-Rom Spline)은 점 q(i)에서 점 q(i+1) 의 곡선(spline)인데... 사실 새로운 개념이라기 보다는, 위에서 설명한 허밋 곡선을 그리기 위한 기법이라고 이해하면 된다. 스플라인은, 두 점 사이에 그려진 곡선을 의미한다.

즉, 우리는 아까 허밋 곡선을 어떻게 그린다고 했는가...? 바로 양 끝 점과, 양 끝점에서의 속도(v)만 가지고 베지어 곡선과 동일한, 허밋 곡선을 그릴 수 있다고 했었다. 캣멀-롬 스플라인은, 바로 그 점을 응용한다.

즉, 우리는 일단  q1 에서 q2 까지의 곡선을 그리고 싶다. 그러려면 q1 과 q2 에서의 접선의 벡터(혹은 속도 벡터)를 알아야 한다. q1 에서의 접선 벡터 v1 은 q1 -> q3 의 벡터라고 가정하고, q2 에서의 접선 벡터 v2 를 v1 의 절반 (방향은 같으니까) 이라고 하면, 우리는 이제 허밋 곡선의 방정식에 의해 q1 과 q2 를 잇는 곡선(spline)을 얻을 수 있게 된다! 😆

이것이 바로... Catmull-Rom Spline 이다. 

아까 두루뭉술하게 '절반' 이라는 표현을 사용했는데, vi 를 결정할 때, τ 의 값을  0.5 로 잡으면 '절반'이 된다. 보통 0.5로 곡률을 설정한다고 한다 😅

혹시 추가적인 설명이 필요하다면... 이 글에서 그림과 함께 자세히 알려주고 있으니 살펴보자 😁

 

이제 그 응용을 보자. 주전자가 있고, 카메라가 파란색 곡선을 따라 움직인다고 해 보자. 즉, 눈이 카메라의 렌즈에 달려 있는 것이다.

파란색 곡선이 허밋 곡선 식 p(t) 로 정의되었다고 하면... 카메라의 위치를 캣멀-롬 스플라인 식을 통해, p(t) 를 따라 이동하는 EYE 를 구할 수 있게 된다. 😉

참고로 UP 벡터는 좌표계의 노말 벡터이다. 🙂

 

이제 주전자도 같이 움직인다고 해 보자. 우리는 주전자의 끝점을 바라볼 것이다. 뭐... 원리는 동일하다.

 

 

Bilinear Patch

이제 곡면에 대해 알아보자. 경계를 가진 곡면을 패치(patch) 라고 부른다. 가장 단순한 형태의 패치는 겹선형 패치(bilinear patch) 이다.

4개의 control point 를 이용하여 선형 보간을 결합하면, 위처럼 사다리꼴을 line segment 들의 집합으로 분할할 수 있다.

위에서 보면... p00 와 p01 사이의 점들은 u 에 대한 식으로 선형 보간하여 표현하였고, p00 와 p10 사이의 점들은 v 에 대한 식으로 선형보간하였다.

즉, 사다리꼴 내부의 한 점 p(u, v) 는 u 와 v 를 이용해 표현이 가능하다! 😉

이를 행렬 연산으로도 표현할 수 있다..! 이때, 2x2 행렬 (control point 로 이루어진) 좌우의 행벡터와 열벡터는 1차 번스타인 다항식들을 원소로 가진다.

 

이제 해당 Patch 들에 대해 Tessellation 을 해 보자... 즉, 위처럼 촘촘하게 만든 사각형을 삼각형으로 쪼개 표현해 볼 수도 있을 것이다.

뭐 일단 테셀레이션의 관건은, 위에서 선형 보간 변수로 잡은 u, v 를 얼만큼의 간격으로 진행시킬지.. 일 것이다. 위의 테셀레이션은 그냥 nested for loop 으로도 표현할 수 있다.

 

만약 위의 for loop 에서 했던 것처럼... u -> v 순으로 선형 보간을 하지 않고, v -> u 순으로 선형 보간을 하면 어떻게 될까?

어떻게 되긴! 같은 식을 얻게 된다 😀

 

control point 가 이루는 공간은 plane 일 필요는 없으며, 따라서 bilinear patch 도 마찬가지로 plane 일 필요가 없다.

위에서는 3차원 공간에서의 control point 들과 이에 따른 bilinear patch 가 어떻게 표현되는지 보여주고 있다.

 

그럼 위처럼 구겨진 듯한 모양이 있을땐 어떻게 할까...? 간단하게 생각해서, 선형 보간을 한 번 더 해주면 된다! 😄

일단 u 를 기준으로 위의 도형을 보자. 점을 3개씩 잡는다고 했을 때... p01, p11, p21 을 잇는 2차 베지어 곡선을 구할 수 있다. 해당 베지어 곡선에 대해, 선형 보간을 수행해 주면 된다.

즉, nested for loop 에서 for loop 이 3 개 있는 느낌이다 😆

 

위 식을 풀게 되면 2차 베지어 패치는 위의 슬라이드에 나온 것처럼 행렬 형태로 표현할 수 있다.

이 식에서, 3x3 행렬 좌우의 행벡터와 열벡터는 각각 v 와 u 의 2차 번스타인 다항식들로 구성되어 있다.

각 컨트롤 포인트의 계수는 u 와 v 의 번스타인 다항식이 결합된 형태인데, 이는 컨트롤 포인트에 대한 가중치 역할을 한다. 그림 17.12-(e) 는 이 가중치를 가시화한 것이다.

 

위 그림은 예시로 참고하자. 뭐, 각 컨트롤 포인트들이 꼭 같은 plane 위에 있어야 할 필요는 없다... 정도로 이해하면 될 듯 하다 😅

 

이 그림은 2차 베지어 패치를 만드는 또 다른 방식을 보여준다. 즉, 먼저 4 개의 control point 를 가진 plane 으로 위의 도형을 나누고, 각각에 대해 선형 보간을 통해 구한 bilinear patch 를 만든 다음, 같은 과정을 반복한다 😄

이를 반복적 겹선형보간(repeated bilinear interpolation) 이라고 부르며, 결과는 첫번째 방식과 동일하다! 😊

 

3차 베지어 패치(Bicubin Bezier Patch)는 4x4 컨트롤 포인트를 사용하여 정의할 수 있다. 방식은 이전과 동일하다.

 

실제 렌더링되는 그림을 보자.

 

컨트롤 포인트 하나가 움직일 때 곡면 모양이 상당히 변화되는 것을 확인할 수 있는데, 이것은 베지어 패치의 큰 장점이다. 베지어 패치를 테셀레이션하여 얻은 삼각형 메시의 정점들을 움직여 동일한 결과를 얻을 수도 있겠지만, 이는 훨씬 고된 작업을 필요로 한다 🤗

 

 

베지어 삼각형

지금까지 배운 베지어 패치의 컨트롤 포인트들은 사각형 구조를 가졌다. 베지어 삼각형은 삼각형 구조의 패치를 말한다.

일단, 1차 베지어 삼각형은 세 개의 컨트롤 포인트들이 하나의 평면을 이룬다. 따라서 그냥 보통의 삼각형이다.

우리는 내부의 점 p 가 이루는 각 꼭짓점의 '반대편' 삼각형의 면적에 비례한 각 포인트 별 가중치를 u, v, w 라고 정의할 수 있는데, (u, v, w) 를 무게중심 좌표(barycentric coordinates) 로 부를 것이다.

 

베지어 삼각형으로 곡면을 표현하기 위해서, 6개의 컨트롤 포인트를 사용해 보자.

반복적 겹선형보간처럼, 여기서는 반복적 무게중심 조합(repeated barycentric combination)을 활용할 것이다.

이는, 그냥 무게 중심 조합 식을 2번 쓴 것에 불과하다. 다만, 실제로 테셀레이션을 진행할 때는 살짝 코드를 변형해야 한다. 2번째로 u, v, w 를 사용할 때는, u + v + w 가 1을 넘으면 안된다는 조건이 있기 때문이다.

따라서, 위 식의 3번째 줄에서 w 에 (1 - u - v) 를 넣고,

위 식에 u, v, w 를 대입해 곡면 위의 점을 얻어야 한다. (e) 의 그림은 u, v 를 0.1 간격으로 샘플하여 테셀레이션한 결과를 보여준다. 삼각형의 각 변은 2차 베지어 곡선을 이루게 된다.

 

3차 베지어 패치도 원리는 동일하며, 각 경계선은 3차 베지어 곡선을 이루게 된다 😄