de Casteljau 알고리즘

베지에 곡선 위의 점을 효율적으로 계산하는 de Casteljau 알고리즘에 대해서 알아보자.

 

 

CAGD(Computer Aided Geometric Design)에서는 곡선과 곡면을 주로 다루기 때문에 de Casteljau 알고리즘이 많이 사용된다. 알고리즘을 일반화시켜서 곡면 위의 점을 계산할 수도 있다. 1959년에 Paul de Casteljau이라는 수학자이자 물리학자가 고안했다.

 

 

3차 베지에 곡선 C(t)의 제어점이 다음과 같이 b₀, b₁, b₂, b₃ 로 주어졌다고 하자. 

 

 

 

 

예시로, 파라미터 t = 0.3일 때 곡선 위의 점 C(0.3)을 계산해보자. 각 제어점 사이마다 t = 0.3에서의 내분점을 계산하면 3개의 새로운 점을 구할 수 있다. 이 1단계 내분점들을 초록색으로 표기해보자. (1단계이므로 윗첨자에 1을 쓰고 내분 시작점을 아래첨자로 쓴다.)

 

 

 

 

재귀 알고리즘이므로 곡선 위의 점 하나가 나올 때까지 내분을 이어간다. 2단계 내분점들을 파란색으로 표기해보자.

 

 

 

 

두 점만 남았으니 마지막 3단계 내분점을 계산하면

 

 

 

 

한 점이 결과로 나온다. 이 점이 바로 곡선 위에서 t = 0.3에 대응되는 점이다.

 

 

 

지금까지는 3차 베지에 곡선에서 t = 0.3의 점 계산에 대해 알아보았지만,

일반적으로 생각해보면 n차 베지에 곡선에서 t의 점 계산을 하기 위해서는 n-1개의 제어점에서 시작하여 총 n번의 내분식을 반복하면 된다.

1단계에서는 n개의 내분점이 얻어지고,

2단계에서는 n-1개의 내분점이 얻어지고,

...

n단계에서는 1개의 최종점이 얻어진다.