Basis 함수의 계산

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)\\ N_{i+1,p}&=\frac{u-u_{i+1}}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u)+\frac{u_{i+p+2}-u}{u_{i+p+2}-u_{i+2}}N_{i+2,p-1}(u)\\ \end{align} . . . $$ $\frac{N_{i+1,p-1}(u)}{u_{i+p+1}-u_{i+1}}$이 두 번 계산되어짐을 알 수 있습니다.
이러한 불필요한 계산을 피해야만 합니다.
$i$번째 basis함수에서 $\frac{N_{i+1,p-1}(u)}{u_{i+p+1}-u_{i+1}}$ 항을 계산해서 저장해두었다가 $i+1$번째 basis함수에서 사용하도록 하면 됩니다.

---

input : n,p ,m,u and m+1 knots {$u_0 , u_1 , ... , u_m-1 , u_m$}
output: Coefficients $N_0,p(u) , N_1,p(u) ,,, N_n-1,p(u) , N_n,p(u)  in   N[0],,N[n]$
Algorithm:
Initialize N[0n] to 0;
If u=u0 then
    N[0] = 1.0;
    Return;
Else u=um then
    N[n] = 1.0;
Return;
Endif
N[k] = 1.0;
For I=1 to p do
    Begin
      factor = $\frac{N[(k-1)+1]}{u_{k_1}-u_{(k-1)+1}}$
      $N[k-1] = factor*(u_{k+1} - u)$
      for j=k-i+1 to k-1 do
        $newfactor = \frac{N[j+1]}{u_{j+i+1}-u{j+1}}$
        $N[j] = factor*(u-u_i)+newfactor*(u_{j+i+1}-u)$
        factor=newfactor
      endfor
      $N[k]=factor*(u-u_i)$
    endfor
end

---

위에 basis함수를 계산하는 알고리즘을 나타내었습니다.
이것으로 basis함수를 계산할 수 있을까? 물론 할 수는 있을 것입니다.
그러나 그보다 먼저 $u$가 속하는 매듭 구간을 찾아야 할 것입니다. 위에서는 $u$가 매듭 구간에 속한다고 가정을 하고 계산을 수행하였습니다.

이 매듭 구간을 찾는 것은 여러분의 몫으로 남겨두겠습니다.