곡선 처리.

Presentation on theme: "곡선 처리."— Presentation transcript:

1 곡선 처리

2 곡선의 연결과 Continuity Zero-Order Continuity First-Order Continuity
복잡한 구조의 곡선을 구성하기 위하여서는 그 곡선을 한번에 정의할 수 있는 복잡한 함수를 사용하기 보다는 간단한 함수로 정의할 수 있는 짧고 단순한 형태의 곡선을 여러 개 연결하는 방법을 사용한다. 이때 연속된 두 개의 곡선이 연결된 모양에 따라서 다음과 같은 continuity가 존재한다. Zero-Order Continuity 두개의 곡선의 단순히 연결되어 있는 것 첫 번째 곡선의 끝점과 두 번째 곡선의 시작점을 일치시킴으로써 얻을 수 있다. First-Order Continuity 접선 첫 번째 곡선의 끝점과 두 번째 곡선의 시작 점을 연결 시키고, 두 곡선의 연결 점에서의 접선의 기울기를 같게 함으로써 얻을 수 있다. 이 경우 두 곡선의 연결 점을 눈으로 식별할 수 없다. Second-Order Continuity 접선 연결 점에서의 접선의 기울기 뿐 아니라 곡률까지 같게 함으로써 얻을 수 있다. 이 경우에는 연결 점을 식별할 수 없을 뿐 아니라 두 개의 곡선이 마치 하나의 곡선같이 보인다. 2차원 곡선

3 Bezier Curve 여러 개의 컨트롤 포인트를 사용하여 첫 번째 컨트롤 포인트와 마지막
컨트롤 포인트를 다음의 예와 같이 연결하는 곡선을 정의하는 방법으로서 비교적 구현이 쉽고 Zero Order Continuity와 First Order Continuity를 구현하기 쉬운 곡선 Approximation 방법 p0 p1 p2 세 개의 컨트롤 포인트를 사용한 Bezier 곡선 p3 네 개의 컨트롤 포인트를 다섯 개의 컨트롤 포인트를 p4 2차원 곡선

4 Bezier Curve에서 사용하는 컨트롤 포인트들은 곡선 상의 한 점의 위치를 결정하는데 각각 영향을 미친다.
사용하여 나타낸다. (u의 값이 0이면 곡선의 시작위치를 의미하고 1이면 곡선의 끝의 위치를 의미한다) u의 값이 주어졌다고 하고 그 위치에서 각 컨트롤 포인트가 미치는 영향은 다음의 Blending Function을 사용하여 정의된다. u의 위치에서 k번 째 컨트롤 포인트가 미치는 영향을 BEZ k,n(u)로 나타내면 BEZ k,n(u) = C(n,k) u k (1 - u) n-k 위의 식에서 C(n,k)는 2항 계수로서 n ! C(n,k) = k ! (n - k) ! 로 정의 된다. 2차원 곡선

5 모든 컨트롤 포인트가 각각 Blending function BEZ k,n(u) 만큼 영향을 미치므로
전체 컨트롤 포인트가 곡선의 구간 내의 임의의 위치에서 미치는 영향의 합이 그 위치에서의 곡선 상의 점의 값을 결정한다. 임의의 위치에서의 곡선상의 점을 p(u)라고 하면 n p(u) =  pk BEZ k,n(u) ( 0  u  1 ) k=0 위 식의 각 term의 수식을 직접 대입하여 나타내면 다음과 같다. n n ! p(u) =  pk u k (1 - u) n - k ( 0  u  1 ) k= k ! (n - k) ! 2차원 곡선

6 : 앞 페이지의 식에 의하면 p(u)는 결국 다음의 term들의 합이 된다. p0 u 0 (1 - u) n - 0
k = 0 인 경우 p u 1 (1 - u) n - 1 1 ! (n - 1) ! k = 1 인 경우 p u 2 (1 - u) n - 2 2 ! (n - 2) ! k = 2 인 경우 pn u n (1 - u) n - n n ! (n - n) ! k = n 인 경우 p0 (1 - u) n pn u n p1 n u (1 - u) n-1 n(n-1) p u2 (1 - u) n-2 2 2차원 곡선

7 Bezier Curve와 Zero-Order Continuity
앞에서 u의 값은 0~1사이의 값으로서 u = 0 이면 곡선의 시작위치를 의미하고 u = 1이면 곡선의 끝의 위치를 가리킨다고 하였다. 앞 페이지의 각 term들을 보면 u = 0인 경우(시작 점) 에는 k = 0인 경우에는 Blending function의 값이 1이고 나머지의 경우에는 모두 0이다. 따라서 첫번째 컨트롤 포인트(P0)가 곧 곡선의 시작 점이 됨을 알 수 있다. 또 u = 1인 경우(끝 점)에는 k = n인 마지막 Blending function의 값이 1이고 나머지 경우는 모두 값이 0이다. 따라서 마지막 컨트롤 포인트가 곧 곡선의 끝 점이 됨을 알 수 있다. 따라서, 두 개의 곡선을 정의하는 컨트롤 포인트들이 있다고 할 때 첫 번째 곡선의 마지막 컨트롤 포인트와 두 번째 곡선의 첫 번째 컨트롤 포인트의 위치를 같게 함으로써 두 개의 곡선을 쉽게 연결할 수 있다. Zero Order Continuity를 쉽게 얻을 수 있다. 그 이외의 (0 < u < 1)인 구간에서는 모든 컨트롤 포인트들이 조금씩 곡선의 점의 위치에 영향을 미친다. 2차원 곡선

8 Cubic Bezier Curve Bezier Curve에 사용되는 컨트롤 포인트의 개수는 제한이 없다. 그러나 앞에서
본 바와 같이 (n+1)개의 컨트롤 포인트를 사용하는 경우의 Blending function 식의 차수가 n이 되므로 컨트롤 포인트를 너무 많이 사용하면 식이 복잡해지고 연산의 양이 많아 진다. 따라서 Bezier Curve를 사용하는 대부분의 Graphics Package들에서는 컨트롤 포인트의 개수를 4개 (p0 .. p3)로 제한하고 있다. 네 개의 컨트롤 포인트를 사용하면 Blending function의 차수가 3이 되므로. 이를 Cubic Bezier Curve라고 한다. Cubic Bezier Curve의 p(u)의 값은 다음과 같이 구해진다. p(u) = P0 (1-u) P1 3u (1-u)2 + p2 3u2(1-u) + p3 u3 2차원 곡선

9 p  (x,y) 이므로 아래의 Cubic Bezier Curve의 식은 x값과 y값에 대하여 따로 적용하여야 한다.
x(u) = x0 (1-u) x1 3u (1-u)2 + x2 3u2(1-u) + x3 u3 p(u) = P0 (1-u) P1 3u (1-u)2 + p2 3u2(1-u) + p3 u3 y(u) = y0 (1-u) y1 3u (1-u)2 + y2 3u2(1-u) + y3 u3 2차원 곡선

10 Bezier Curve와 First-Order Continuity
알아 보기 위하여 아래의 Cubic Bezier Curver의 식을 u에 대하여 미분 하면 p(u) = P0 (1-u) P1 3u (1-u)2 + p2 3u2(1-u) + p3 u3 P0 (1-u)3 P0 [3 (1-u)2 (-1) ] = P0 [-3(1-u)2] = -3 P0 (1-u) 2 P1 3u (1-u)2 3 P1 [(1-u)2 + u . 2(1-u) . (-1) ] = 3 P1 [(1-u)2 - 2u(1-u)] p2 3u2(1-u) 3 p2 [2u(1-u) + u2 (-1)] = 3 p2 [2u(1-u) - u2 ] = -3 p2 [u2 - 2u(1-u) ] p3 [3u2 ] = 3 p3 u2 d p(u) = d u -3 P0 (1-u) 3 P1 [(1-u)2 - 2u(1-u)] + -3 p2 [u2 - 2u(1-u) ] 3 p3 u2 미분 계속 2차원 곡선

11 Bezier Curve와 First-Order Continuity
계속 곡선의 시작 점에서의 접선의 기울기를 알아 보기 위하여 앞 페이지의 우측의 도함수에 u = 0을 대입해 보면 -3 P0 (1-u) P1 [(1-u)2 - 2u(1-u)] (-3) p2 [u2 - 2u(1-u) ] p3 u2 = 3 ( P1 - P0 ) (when u=0) 따라서, Bezier 곡선의 시작점에서의 접선은 P0 에서 P1 으로 향하는 vector와 방향이 같다는 것을 알 수 있다. 또한, 곡선의 끝 점에서의 접선의 기울기를 알아 보기 위하여 앞 페이지의 우측의 도함수에 u = 1을 대입해 보면 -3 P0 (1-u) P1 [(1-u)2 - 2u(1-u)] (-3) p2 [u2 - 2u(1-u) ] p3 u2 = 3 ( P3 - P2 ) (when u=1) 따라서, Bezier 곡선의 끝점에서의 접선은 P2 에서 P3 로 향하는 vector와 방향이 같다는 것을 알 수 있다. 계속 2차원 곡선

12 Bezier Curve와 First-Order Continuity
계속 곡선의 First-Order Continuity를 얻기 위하여서는 두 개의 곡선의 연결 점에서의 두 곡선의 접선의 기울기를 같게 해 주어야 한다고 앞에서 이야기 한 바 있다. 두 개의 Bezier Curve의 연결 점에서의 두 곡선의 접선의 기울기를 같게 해 주기 위해서는 앞 페이지에서 알아본 대로 Bezier curve의 양 끝 점에서의 접선의 기울기가 각각 양 끝점에서 이웃한 두 개의 컨트롤 포인트를 연결하는 선분과 방향이 같다는 점을 이용할 수 있다. 즉 , 다음의 그림과 같이 두 Bezier curve의 연결 점과 그와 각각 이웃한 두 컨트롤 포인트를 일직선 상에 배치함으로써 Bezier Curve의 First-Order Continuity를 얻을 수 있다. 곡선 1 곡선 2 두 점이 같은 위치에 있음: Zero-Order Continuity 두 연결 점과 그와 각각 이웃한 두 점 (모두 4개의 점)이 일직선 상에 있다 : First-Order Continuity 2차원 곡선

13 get_2d_bezier_curve()함수 소스 (2d-bez.c 파일 내)
void get_2d_bezier_curve(float *cx, float *cy, float *x, float *y, int n) { int i; float u, du, cu, Bez03, Bez13, Bez23, Bez33; u=0.0; du = 1.0 / (float)(n-1); for(i=0; i<n; i++) { cu = u; Bez03 = cu * cu * cu; Bez13 = 3.0 * u * cu * cu; Bez23 = 3.0 * u * u * cu; Bez33 = u * u * u; x[i] = cx[0] * Bez03 + cx[1] * Bez13 + cx[2] * Bez23 + cx[3] * Bez33; y[i] = cy[0] * Bez03 + cy[1] * Bez13 + cy[2] * Bez23 + cy[3] * Bez33; u += du; }/*i*/ } 2차원 곡선

14 Bezier Curve 테스트 프로그램 파일: “2dBezTst.c”
draw_2d_bezier_curve()함수 소스 (2d-bez.c 파일 내) int draw_2d_bezier_curve(float *cx, float *cy, int n, float r, float g, float b) { float *x, *y; x = malloc(sizeof(float) * n); if(!x) return 0; y = malloc(sizeof(float) * n); if(!y) { free(x); return 0; } get_2d_bezier_curve(cx,cy,x,y,n); draw_polygon(x,y,n, r,g,b); free(x); free(y); return 1; } Bezier Curve 테스트 프로그램 파일: “2dBezTst.c” 2차원 곡선