프로그래밍을 일상 생활속으로

앞에서 B- spline곡선은 여러 개의 부분 곡선들로 이루어져 있고, 각 부분 곡선들은 매듭 구간에서 정의되고 있다고 했습니다. 그래서 부분 곡선들이 정의되어 있는 이 매듭 구간을 수정을 하면 곡선의 형태도 바뀌게 됩니다. 이 매듭 구간을 결정하는 knot을 수정함으로써 곡선의 형태를 변형시킬 수 있습니다. 하지만 knot을 수정해서 곡선의 형태를 바꾸는 것은 그다지 바람직한 방법이 아닌 것 같습니다. knot을 수정해서 변형되는 곡선의 형태를 미리 예측하기가 힘들기 때문입니다. knot의 추가 knot의 추가는  기존의 곡선의 형태를 변형시키지 않고  새로운 knot을 매듭 벡터에 추가시키는 것입니다. knot이 하나 추가되면 m이 증가되므로 $m=n+p+1$의 식에서 n이나 p가 증가되어야 합니다. p가 증가되면 하나의 부분 곡선을 이루는데 필요한 basis function의 개수가 증가되므로 p가 증가되기 전보다 곡선의 부분적인 편집 기능이 떨어지게 됩니다. 그래서 이것은 고려하지 않고 n을 증가시킵니다. 즉 새로운 제어점을 추가시킨다는 말입니다. 다시 정리하면 n+1개의 제어점 $P_0,P_1,...,P_{n-1},P_n$와 그것과 연관된 양의 값인 $W_i$, $m+1$개의 매듭을 가진 매듭 벡터 $U=\{u_0,u_1,...,u_{m-1},u_m\}$, 차수 p를 가진 B-spline 곡선에 곡선의 형태는 변형시키지 않고 새로운 매듭을 추가시키는 것입니다. 추가시킬 새로운 매듭  u 가 매듭 구간 $[u_k,u_{k-1})$에 속한다고 가정하면, 이 매듭 구간에서 정의되는 곡선은 제어점 $P_{k-p},P_{k-p+1},...,P_{k-1},P_k$에 의해서 형성됩니다. 우리는 새로운 제어점을 찾아야 하기 때문에 $P_{k-p},P_{k-p+1}$상의 $Q_{k-p+1}, P_{k-p+1},P_{k-p+2}$상의 $Q_{k-p+2},…,P_{k-1},P_k$상의 $Q_k$을 찾아야 합...

곡선의 변형 B-spline곡선의 변형은 아래의 조작으로 가능하다. ● 매듭 벡터의 변경 ● basis함수의 차수 변경 ● 제어점의 위치 변경 ● 중복된 제어점 사용 ● 중복된 매듭 값 사용 우리는 basis함수의 값을 계산해내는 과정을 알아보았다. 인자로 넘겨준 $u$가 속하는 매듭 구간도 구했고 거기서부터 차수를 $0$에서부터 $p$까지 증가시키면서 basis함수도 구했다. 제어점의 이동 제어점의 이동은 B-spline곡선의 모양을 변형하는 한 방법이 된다. 제어점 $P_k$을 이동시키면 B-spline곡선 $C(u)$중 매듭 구간 $[U_k,U_{k+1})$에 속하는 부분만 변형이 된다. (나머지 구간에서의 B-spline곡선은 0이 되기 때문에 이동에 의한 변형은 생기지 않는다.) 조금 더 자세히 살펴보자면 제어점이 이동되어지는 벡터의 방향으로 곡선이 변형이 된다. $P_k$가 새로운 위치 $P_{k+v}$로 이동되었다면, 이 된다. 기존의 곡선에서 $N_k,p(u)v$만큼 이동된다는 것을 알 수 있다. 하지만 여기서 $u$가 매듭 구간 $[U_k,U_{k+1})$에 속하지 않는다면 곡선의 변형은 없을 것이다.

Basis 함수의 계산 B-spline곡선을 계산하려면 먼저 basis함수를 계산해야 합니다.. B-spline basis함수의 계산은 basis함수의 정의로부터 시작합니다. B-spline basis함수의 정의는 식 )을 참조하시면 됩니다. 우리가 $N_k,p(u)$을 계산하기 위해서는 정의 상 $N_k,p-1(u)$와 $N_k+1,p-1(u)$가 필요합니다. 또 $N_k,p-1(u)$을 계산하기 위해서는 $N_k,p-2(u),N_k+1,p-2(u)$가 필요하고, $N_k+1,p-1(u)$을 계산하기 위해서는 $N_k+1,p-2(u) , N_k+2,p-2(u)$가 필요합니다. 여기서 $N_k+1,p-2(u)$가 두 번 중복됨을 주목하세요. 호출 깊이가 깊어짐에 따라서 이러한 중복되는 항의 개수가 많아지게 됩니다. 이것은 Bezier곡선의 계산에서 de asteljau 알고리즘과 비슷합니다. 조금 시각을 바꾸어서 $u$가 매듭 구간 $[u_k , u_{k+1}])$ 에 존재한다고 가정하면 이 구간에서 0이 아닌 차수가 0인 basis함수는 $N_k,0(u)$이 될 것입니다. 또 0이 아닌 차수가 1인 basis함수는 $N_{k-1},1(u) , N_k,1(u)$이 됩니다. 이렇게 해서 이 구간에서 0이 아닌 차수가 p인 basis 함수는 적어도 $p+1$개가 됩니다. $( N_k-p,p(u) , N_{k-p+1},p(u) , ... , N_{k-1},p(u) , N_k,p(u))$ 삼각형 모양의 영역에서 제일 위쪽의 화살표와 아래쪽 화살표가 가리키는 항은 바로 앞 차수의 하나의 항에서만 계산이 됩니다. 중간에 있는 부분은 정의에서처럼 앞 차수의 두 항에 의해서 계산이 이루어지게 됩니다. 전개 해보면, $$ \begin{align} N_{i,p}&=\frac{u-u_i}{u_{i+p}-u_i}N_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u)...

Bspline 곡선의 성질 B-spline곡선은 많은 부분에서 Bezier곡선과 유사합니다. B-spline곡선은 Bezier곡선보다 더 낳은 점을 가지고 있는데, 여기서 Bspline곡선의 성질을 알아보도록 하겠습니다. 일반적인 경우로써 차수가 $p$이고 $n+1$개의 제어점을 가지고 knot vector가 $U={u_0 , u_1,...,u_m-1 , u_m}$인 Bspline곡선에 대해서 생각해 보겠습니다. Bspline곡선은 차수가 p인 여러 개의 곡선의 식으로 이루어져 있습니다. (Bezier곡선은 하나의 곡선식으로 이루어집니다.) $m=n+p+1$의 식을 만족합니다. 차수가 $p$이고 인덱스 번호가 가장 높은 basis function을 $N_{n,p}$라고 하면, 이  basis function은 매듭구간 $[u_n , u_{n+p+1})$에서 0이 아닌 값을 가집니다. 이 $N_n,p$가 가장 인덱스 번호가 높은 basis function이기 때문에 $u_{n+p+1}$가 가장 값이 큰 매듭이 됩니다. 따라서 $m=n+p+1$이 됩니다. 고정 Bspline곡선(clamped B-spline)은 양끝 제어점을 지납니다. 보다 더 엄격하게 콘벡스헐 성질을 만족시킵니다. 부분적인 편집이 가능합니다.. knot의 중복도가 k일 때 $C_{k-p}$연속성을 만족시킵니다. Bezier곡선은 B-spline곡선의 특수한 형태입니다. 어파인 변형에 대해서 불변입니다.

예를 들어가며 B-spline basis function의 형태를 살펴보도록 하겠습니다. {0 , 1 , 2 , 3}일 때 차수를 0에서 2까지 증가시키면서 basis function을 나타내었습니다. <차수가 0일 경우> 차수가 0일 때는 basis function의 정의에 의해서 step function이 됩니다. i가 0일 때는 [0,1)에서 1이 되고 나머지에서는 0이 됩니다. 1일 때는 [1,2)구간에서 1이 되고 나머지에서는 0이 됩니다. 2일 때는 [2,3)에서 1이 되고 나머지 구간에서는 0이 됩니다. <차수가 1일 경우> 차수가 0이었을 때 하나의 basis function이 유효한 구간의 크기는 1이었지만 차수가 1일 때는 구간의 크기가 2가 됩니다. $$ \begin{aligned} N_{0,1}(t)&=\frac{u-u_0}{u_1-u_0}N_{0,0}(u)+\frac{u_2-u}{u_2-u_1}N_{1,0}(u)\\ &=uN_{0,0}(u)+(2-u)N_{1,0}(u)\\ N_{1,1}(t)&=\frac{u-u_1}{u_2-u_1}N_{1,0}(u)+\frac{u_3-u}{u_3-u_2}N_{2,0}(u)\\ &=(u-1)N_{1,0}(u)+(2-u)N_{2,1}(u) \end{aligned} $$ $N_{0,1}(u)$는 $N_{0,0}(u),N_{1,0}(u)$의 합으로 구성되기 때문에 그 값이 [0,2)에서는0보다 크거나 같고 그 이외의 구간에서는 0이 됩니다. 이와 같은 이유로 해서 $N_{1,1}(u)$는 $[1,3)$에서는 0보다 크거나 같고 나머지 구간에서는 0이 됩니다. <차수가 2일 경우> $$ \begin{aligned} N_{0,2}(u)&=\frac{u-u_0}{u_2-u_0}N_{0,1}(u)+\frac{u_3-u}{u_3-u_1}(u)\\ &=0.5\times u \times N_{0,1}u + 0....

Bezier곡선에 유연성을 제공하기 위해서는 차수를 높이거나 분할하는 방법밖에 없었습니다. Bezier 곡선을 분할했다면 연속성을 유지하기 위해 연결되는 두 곡선 중 첫 번째 곡선의 제일 마지막 제어점에서의 기울기와 두 번째 곡선의 첫 번째 제어점에서의 기울기가 서로 같아야 했습니다. 어쨌던 차수를 높이거나 분할하는 방법은 가중 곡선의 형태를 유지하거나 계산상의 부담을 가중시키게 되는데, B-Spline 곡선에서는 차수를 높이지 않아도 $C1$연속성을 유지하기 위한 고려도 하지 않아도 됩니다. 임의의 제어점을 Bezier곡선으로 표현을 하면 차수가 제어점 개수보다 하나 작은 다항식이 생깁니다. B-Spline곡선은 Bezier곡선보다 더 낮은 차수의 식으로 곡선의 표현이 가능합니다. 낮은 차수의 식으로 곡선을 표현하려면 결과적으로 여러 개의 식이 필요하게 됩니다. 각각의 식이 곡선의 일부분을 표현하므로 곡선을 식의 개수만큼 분할하는 것과 같이 됩니다. 앞에서 우리는 Bezier곡선에 대해서 살펴보았습니다. Bezier곡선이 어떤 복잡한 모양을 띄게 되더라도 처음에는 단순한 직선에서부터 시작되었습니다. 마치 어떤 풍성한 나무라도 그것은 뿌리로부터 시작된 것 처럼. B-Spline곡선도 그것이 복잡한 모양을 띄어도 단순한 영역에서부터 시작되었습니다. 그것은 이 단순한 영역 밖에서는 존재하지 않고 오로지 그 영역 상에서만 존재합니다. 이 영역을 뿌리로 하여 곡선이 뻗어 나가게 됩니다. B-Spline곡선은 차수를 낮추면 여러 개의 식(각각의 식은B-spline곡선의 일부분을 표현한다)이 생기며 이 식들은 그것의 뿌리가 되는 영역의 일부분 상에 존재하게 됩니다. 이 영역을 여러 개의 조각으로 나누는 점들을 knot이라고 합니다. 4차의 bspline을 그리는 프로그램을 첨부 합니다.

Bspline 정의 $n + 1$개의 제어점 $(P_0 , P_1 , ... , P_{n-1} , P_n)$과 $\text{knot vector U}={U_0 , U_1 , ... , U_{m-1} , U_m}$, Bspline의 차수 p가 주어져있을 때 Bspline곡선은 $$ \begin{aligned} C(u)&=\sum_{i=0}^n N_{i,p}(u) P_i,\\ N_{i,0}&=\begin{cases} 1 & u_i \le u \lt u_{i+1}\\ 0 & otherwise \end{cases}\\ N_{i,p}&=\frac{u-u_i}{u_{i+p} - u_i} N_{i,p-1}(u) + \frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}} N_{i+1,p-1}(u) \end{aligned} $$ 이 됩니다. 위 식은 Bezier 곡선 식과 유사하지만 보다 많은 항들이 있습니다. $N_i,p(u)$는 Bspline의 basis function이고, 여기서 p 는 Bspline곡선의 차수이고, $P_i$는 제어점입니다. 매듭 벡터의 개수($m+1$)와 제어점의 개수와 곡선의 차수와의 관계를 살펴보면, 아래와 같은 식을 만족하게 됩니다. $$ \textcolor{red}{m=n+p+1} $$ 이 식이 성립되는 이유는 아래절에 나와 있습니다. Bspline Basis Functions Bspline의 Basis Function은 Bezier의 그것과 많은 부분에서 유사하지만 보다 복잡합니다. Bezier의 Basis Function에는 없는 두 가지의 특성이 있는데, ① 도메인이 여러 개의 knot으로 나누어져 있습니다. ② Basis Function이 도메인 전 영역에 걸쳐서 0보다 작지는 않습니다. ②번 성질에 의해서 B-spline곡선은 부분적인 편집이 가능해집니다. Bspline이 기반을 두고 있는 도메인이 여러 개의 knot으로 나누어진다고 했는데, 이...