오다기리 박의 알고리즘 노트

베지에 곡선 위의 점을 효율적으로 계산하는 de Casteljau 알고리즘에 대해서 알아보자. CAGD(Computer Aided Geometric Design)에서는 곡선과 곡면을 주로 다루기 때문에 de Casteljau 알고리즘이 많이 사용된다. 알고리즘을 일반화시켜서 곡면 위의 점을 계산할 수도 있다. 1959년에 Paul de Casteljau이라는 수학자이자 물리학자가 고안했다. 3차 베지에 곡선 C(t)의 제어점이 다음과 같이 b0, b1, b2, b3 로 주어졌다고 하자. 예시로, 파라미터 t = 0.3일 때 곡선 위의 점 C(0.3)을 계산해보자. 각 제어점 사이마다 t = 0.3에서의 내분점을 계산하면 3개의 새로운 점을 구할 수 있다. 이 1단계 내분점들을 초록색으로 표기해보자. (1..

베지에 곡선 (Bézier curve)는 n개의 제어점(control point)으로부터 만들어지는 n-1차 곡선으로 수치 해석 분야에서 중요하게 사용된다. 특히 3차 베지에 곡선은 포스트스크립트 글꼴, 메타폰트(METAFONT), 김프 등에서 부드러운 폰트를 만드는데에 이용되고 있다. 이 글에서 3차 베지에 곡선의 수학적인 표현법에 대해 알아보자. 다음 그림처럼 실수 파라미터 t가 0과 1사이에서 움직인다고 하자. 움직이는 t의 값에 따라서 3차원 공간 위에 그려지는 곡선을 C(t)라고 표기한다. C(t)의 x, y, z 각 좌표를 t에 대한 식으로 표현할 수만 있다면 우리는 t를 마음대로 움직이면서 그에 대응되는 곡선 위의 점을 구할 수 있을 것이다. 그렇다면 C(t)의 식을 어떻게 쓸 수 있을까? ..