이는 Bezier곡선이 control point가 만드는 convex region 내부에 있음을 의미한다. Bezier곡선의 convexity 성질은 여러 좋은 특성을 준다. 몇 가지만 나열하면, 첫째가 Bezier곡선은 항상 컨트롤 포인트의 convex hull 내에 놓이게 되므로 곡선의 제어 가능성을 보장한다. 둘째는 교차 여부를 쉽게 확인할 수 있다. 또한 culling을 가능하게 한다.
n 차 Bezier 곡선은 두 개의 (n - 1) 차 Bezier 곡선의 선형보간으로 표현할 수 있다. Bezier 곡선은 Bernstein 다항식을 이용해서도 표현할 수도 있지만, 높은 찻수의 곡선일 때는 De Casteljau's Algorithm을 이용하는 것이 수치적으로 보다 안정적인 결과를 준다.
// De Casteljau's algorithm; recursive version;
double Bezier(double t, int n, double Q[]){
if (n == 1) return Q[0];
else return (1 - t) * Bezier(t, n - 1, &Q[0]) + t * Bezier(t, n - 1, &Q[1]);
}
// De Casteljau's algorithm; non-recursive. calling of Bezier() modifies Q's;
double Bezier(double t, int n, double Q[]){
for (int k = 1; k < n; k++)
for (int j = 0; j < (n - k); j++)
Q[j] = (1 - t) * Q[j] + t * Q[j + 1];
return Q[0];
}
void BezierCurve(std::vector<CfPt> &cntls,
int npts, std::vector<CfPt> &curves) {
int n = cntls.size();
std::vector<double> xp(n), xp(n);
// clone control points;
for (int k = 0; k < n; k++) {
xp[k] = cntls[k].x;
yp[k] = cntls[k].y;
}
curves.resize(npts);
for (int i = 0; i < npts; ++i) {
double t = double(i) / (npts - 1);
curves[i] = CfPt(Bezier(t, n, &xp[0]), Bezier(t, n, &yp[0]));
}
}
그러나 일반적으로 이 적분은 닫힌 형태로 주어지지 않으므로 Gauss-Legendre quadrature와 같은 수치 적분에 의존해서 그 값을 계산하여야 한다. Bezier curve의 경우는 기하학적인 방법을 이용하여서 좀 더 간편하게 그 길이를 구할 수 있다. Bezier curve의 길이에 대한 간단한 근사는 현의 길이($|\mathbf{Q}_3- \mathbf {Q}_0|$)로 근사하는 것이다. 그러나 현의 길이는 lower bound만을 준다. 다음으로 고려할 근사는 control 점 사이 거리의 합이다. 이것은 실제 길이의 upper bound를 준다. 따라서 근사적인 길이는 이 두 거리의 평균으로 잡으면 될 것이다:
$$ \text{Arc Length}\sim \frac{ \text {현의 길이} + \text {control point 사이 거리 합}}{2}.$$
의 차이가 충분히 작아야 한다. 만약에 이 두 길이의 차이기 정해진 임계값보다도 크면 Bezier curve를 둘로 분할해서 좌우 두 Bezier curve에 대해서 동일한 검사를 한다. 충분히 평탄한 경우는 위의 평균값으로 근사하고 그렇지 못한 경우는 충분히 평탄해질 때까지 분할하는 과정을 반복한다. 아래 코드는 3차 Bezier curve의 길이를 이 알고리즘을 이용해서 구하는 과정을 구현한 것이다.
#define DistL2(A, B) sqrt(((A).x-(B).x)*((A).x-(B).x) + ((A).y-(B).y)*((A).y-(B).y))
static void BezierSubDiv(CfPt Q[4], CfPt leftQ[4], CfPt rightQ[4]) {
CfPt T[4][4]; /* Triangle Matrix */
for (int j = 0; j < 4; ++j) T[0][j] = Q[j];
// de Casteljau divides and conquers at t = 0.5;
for (int i = 1; i < 4; ++i)
for (int j = 0 ; j <= 3 - i; ++j)
T[i][j] = (T[i - 1][j] + T[i - 1][j + 1]) / 2;
// left subdiv control points;
for (int j = 0; j < 4; ++j) leftQ[j] = T[j][0];
// right subdiv control points;
for (int j = 0; j < 4; ++j) rightQ[j] = T[3 - j][j];
}
void BezierLength(CfPt Q[4], double tol, double *length) {
CfPt leftQ[4], rightQ[4];
double controlLen = 0;
for (int i = 0; i < 3; ++i) controlLen += DistL2(Q[i], Q[i + 1]);
double cordLen = DistL2(Q[0], Q[3]);
// test flatness;
if (fabs(controlLen - cordLen) > tol) {
BezierSubDiv(Q, leftQ, rightQ); /* divide */
BezierLength(leftQ, tol, length); /* left side */
BezierLength(rightQ, tol, length); /* right side */
return;
}
*length = *length + (cordLen + controlLen) / 2 ;
return ;
}
De Casteljau's algorithm
다음은 4분원의 길이를 위의 알고리즘을 이용해서 구하는 예제이다. 네 개의 control point는
Bezier 곡선을 이용한 원의 근사처럼 타원을 근사해보도록 하자. 원점을 중심으로 하고 장축 반지름이 $a$, 단축 반지름이 $b$인 타원을 1사분에서 3차 Bezier curve을 이용해서 근사하려면 4개의 control point가 필요하다. 원의 경우처럼, 끝점에서 접선의 기울기를 같게 하는 조건을 부여하면 control point는
한 개의 Bezier 곡선을 이용해서 원을 표현할 수 없음은 잘 알려진 사실이다. 그럼 Bezier 곡선을 이용해서 얼마나 원(호)을 잘 근사할 수 있을까? 원점에 중심을 둔 반지름 1인 원의 1 사분면 원호가 3차 Bezier 곡선으로 얼마나 잘 표현되는지 알아보자. 3차 Bezier 곡선은 4개의 control point $\{ \mathbf {P}_i | i=0,1,2, 3\}$이 주어진 경우
그럼 원에서 얼마나 벗어날까? 원 중심에서 거리를 차이를 구해보면 Bezier 곡선이 항상 원의 바깥으로 치우쳐 있음을 알 수 있다:
$$\Delta(t) = ||\mathbf {B}(t)||-1\ge 0$$
최대로 벗어나는 정도는 $t=(3\pm \sqrt{3})/6$일 때 $\Delta_\text {max}=\frac{1}{3}\sqrt{ \frac{71}{6}-2\sqrt{2}}-1=0.00027253...$이므로 대부분의 경우 크게 벗어남이 없는 원의 근사를 준다.
(2-2) $t=1/2$에서 Bezier 곡선이 원을 통과하는 조건 대신 원에서 벗어남을 최소로 하는 조건을 부여하면 더 좋은 근사를 얻을 수 있다:
$$k=\text{argmin}|\Delta|_\text{max}$$
이 경우 Bezier 곡선은 원의 바깥에 놓이지 않고 교차하게 된다. $t=1/2$에서 최솟값, $t=\frac{1}{2}\left(1\pm \frac{\sqrt{3k^2+20k -12}}{2-3k}\right) $일 때 최댓값을 가지는데, 두 값의 절댓값이 같게 되려면(closed form이 없다)
$$ k = 0.551915023...$$
을 선택해야 하고, 이때 벗어남의 최댓값은 $|\Delta|_\text{max} = 0.00019607...$이므로 더 좋은 근사가 된다.
(2-3) 또 다른 제한조건은 없을까? Bezier 곡선이 만드는 면적이 사분원의 면적을 표현하도록 제한을 가하는 경우:
댓글을 달아 주세요