한 점에서 Bezier 곡선까지의 최단거리나, Bezier 곡선상의 한 지점에서 접선 또는 법선을 구하기 위해서는 도함수를 구해야 할 필요가 생긴다. 그런데 주어진 찻수에서 Bezier 곡선의 도함수는 한 찻수 낮은 Bezier 곡선으로 표현할 수 있어서 상대적으로 쉽게 계산할 수 있다. 찻수가 $n$인 Bezier 곡선이
$$ {\bf B}(t) = \sum_{k=0}^n b_{n,k}(t) {\bf Q}_k = \sum_{k=0}^n\frac{n!}{k! (n-k)!}t^k (1-t)^{n-k} {\bf Q}_k$$
로 표현되므로 이의 미분은
$$ \frac{d {\bf B}(t)}{dt} = \sum_{k=1}^n \frac{n!}{(k-1)! (n-k)!} t^{k-1} (1-t)^{n-k} {\bf Q}_k - \sum_{k=0}^{n-1} \frac{n!}{k! (n-1-k)!} t^k (1-t)^{n-1-k}{\bf Q}_{k}\\ =\sum_{k=0}^{n-1} \frac{(n-1)!}{k! (n-1-k)!}t^k (1-t)^{n-1-k} (n{\bf Q}_{k+1}- n {\bf Q}_k ) = \sum_{k=0}^{n-1} b_{n-1,k}(t) (n {\bf Q}_{k+1} - n{\bf Q}_k)$$
따라서 $n$ Bezier 곡선의 미분은 control 점이
$$ \tilde {\bf Q}_k = n( {\bf Q}_{k+1} - {\bf Q}_k) \qquad k=0, 1,..,n-1$$
로 주어지는 $(n-1)$차 Bezier 곡선으로 표현된다. 미분을
$$ \frac{d{\bf B} (t)}{dt} =n \left[{\bf B}_1(t) - {\bf B}_0(t) \right] \\ {\bf B}_1(t ) = \sum _{i=0}^{n-1} b_{n-1,i}(t) {\bf Q}_{i+1} ,\qquad {\bf B}_0(t) = \sum_{i=0}^{n-1} b_{n-1,i}(t) {\bf Q}_i $$처럼 분해를 하면 ${\bf B}_1(t)$는 컨트롤점이 $\{\bf P_1, P_2,...,P_n\}$으로 구성된 $(n-1)$차 Bezier 곡선이고, ${\bf B}_0(t)$는 컨트롤점이 $\{ \bf P_0, P_1,...,P_{n-1}\}$으로 만들어지는 $(n-1)$차 Bezier 곡선이다. 따라서 Casteljau 알고리즘을 이용하여 ${\bf B}_1(t)$와 ${\bf B}_0(t)$을 구하여 그 차이를 계산하면 미분값을 얻을 수 있다.
곡선의 curvature: https://kipl.tistory.com/105
// Bezier cureve evaluation at t;
// deg = the degree of the bezier curve;
double Bezier(int deg, double Q[], double t) {
if (deg==0) return Q[0];
else if (deg==1) return (1 - t) * Q[0] + t * Q[1];
else if (deg==2) return (1-t)*((1-t)*Q[0] + t*Q[1]) + t*((1-t)*Q[1] + t*Q[2]);
std::vector<double> Q1(deg + 1);
for (int i = 0; i <= deg; i++) Q1[i] = Q[i];
// triangle computations;
for (int k = 0; k < deg; k++)
for (int j = 0; j < (deg - k); j++)
Q1[j] = (1 - t) * Q1[j] + t * Q1[j + 1];
return Q1[0];
}
// derivative of a Bezier curve at t;
double BezierDerivative(int deg, double Q[], double t) {
if (deg==0) return 0;
else if (deg==1) return Q[1] - Q[0];
else if (deg==2) return 2*((1-t)*(Q[1]-Q[0])+t*(Q[2]-Q[1]));
std::vector<double> Q1(degree + 1);
for (int i = 0; i <= deg; i++) Q1[i] = Q[i];
// triangle computations;
for (int k = 0; k < (deg - 1); k++)
for (int j = 0; j < (deg - k); j++)
Q1[j] = (1 - t) * Q1[j] + t * Q1[j + 1];
return deg * (Q1[1] - Q1[0]);
};
// 2nd derivative of a Bezier curve at t;
double EvalBezier2ndDeriv(int deg, double Q[], double t) {
if (2 > deg) return 0;
std::vector<double> Q1(deg+1);
for (int i = 0; i <= deg; i++) Q1[i] = Q[i];
for (int i = 0; i < (deg-2); i++)
for (int j = 0; j < (deg-i); j++)
Q1[j] = (1-t)*Q1[j] + t*Q1[j+1];
double v0 = 2*(Q1[1] - Q1[0]);
double v1 = 2*(Q1[2] - Q1[1]);
return v1 - v0;
};
// curvature of a Bezier curve at t;
double BezierCurvature(int deg, CfPt Q[], double t) {
if (deg < 2) return 0;
CfPt d1 = EvalBezierDeriv(deg, Q, t);
CfPt d2 = EvalBezier2ndDeriv(deg, Q, t);
double flen = hypot(d1.x, d1.y);
return fabs(d1.x*d1.y - d2.x*d1.y)/ flen / flen / flen;
}'Computational Geometry' 카테고리의 다른 글
| Least Squares Bezier Fit (0) | 2024.04.05 |
|---|---|
| Why Cubic Splines? (9) | 2024.03.16 |
| Natural Cubic Spline (0) | 2024.03.11 |
| Approximate Distance Between Ellipse and Point (0) | 2024.03.08 |
| Distance from a Point to an Ellipse (0) | 2024.03.06 |
