作业 4：Bézier 曲线

作业要求

Bézier 曲线是一种用于计算机图形学的参数曲线。在本次作业中，你需要实现 de Casteljau 算法来绘制由 4 个控制点表示的 Bézier 曲线 (当你正确实现该算法时，你可以支持绘制由更多点来控制的 Bézier 曲线)。

你需要修改的函数在提供的 main.cpp 文件中。

1. bezier：该函数实现绘制 Bézier 曲线的功能。它使用一个控制点序列和一个 OpenCV::Mat 对象作为输入，没有返回值。它会使 t 在 0 到 1 的范围内进 行迭代，并在每次迭代中使 t 增加一个微小值。对于每个需要计算的 t，将 调用另一个函数 recursive_bezier，然后该函数将返回在 Bézier 曲线上 t 处的点。最后，将返回的点绘制在 OpenCV::Mat 对象上。
2. recursive_bezier：该函数使用一个控制点序列和一个浮点数 t 作为输入， 实现 de Casteljau 算法来返回 Bézier 曲线上对应点的坐标。

recursive_bezier

贝塞尔曲线的起点为 $p_0$，终点为 $p_3$，起点方向向量为 $\overrightarrow{p_0{p}_1}$，终点方向向量为 $\overrightarrow{p_2{p}_3}$。

不断进行线性插值，观察到给定 $n+1$ 个控制点 $b_0,b_1,\cdots ,b_n$，可以得到最高为 $n$ 阶的点 $b_0^n$

b 0 1 ( t ) = ( 1 − t ) b 0 + t b 1 b 1 1 ( t ) = ( 1 − t ) b 1 + t b 2 b 0 2 ( t ) = ( 1 − t ) b 0 1 + t b 1 1 b 0 2 ( t ) = ( 1 − t ) 2 b 0 + 2 t ( 1 − t ) b 1 + t 2 b 2

b01​(t)b11​(t)b02​(t)b02​(t)​=(1−t)b0​+tb1​=(1−t)b1​+tb2​=(1−t)b01​+tb11​=(1−t)2b0​+2t(1−t)b1​+t2b2​​

其中
B i n ( t ) = ( n i ) t i ( 1 − t ) n − i B_{i}^{n}(t)=\left(

\right) t^{i}(1-t)^{n-i} Bin​(t)=(ni​)ti(1−t)n−i
因此对于三次贝塞尔曲线，只需要实现公式
$${\mathbf{b}}^3(t)=(1-t{)}^3{\mathbf{b}}_0+3(1-t{)}^{2}t{\mathbf{b}}_1+3(1-t)t^2{\mathbf{b}}_2+t^3{\mathbf{b}}_3$$
所以 recursive_bezier 函数可以直接按照上式写出

cv::Point2f recursive_bezier(const std::vector<cv::Point2f> &control_points, float t) 
{
    // TODO: Implement de Casteljau's algorithm
	auto point = std::pow(1 - t, 3) * control_points[0] + 3 * std::pow(1 - t, 2) * t * control_points[1] + 3 * (1 - t) * std::pow(t, 2) * control_points[2] + std::pow(t, 3) * control_points[3];
    return point;
}   
1
2
3
4
5
6

但是，我们如果要实现更一般的情况，即对任意数量的点实现位置计算，需要实现公式
b n ( t ) = ∑ j = 0 n b j B j n ( t ) = ∑ j = 0 n b j ( n j ) t j ( 1 − t ) n − j \mathbf{b}^n(t)=\sum^n_{j=0}\mathbf{b}_jB_j^n(t)=\sum^n_{j=0}\mathbf{b}_j\left(

\right)t^j(1-t)^{n-j} bn(t)=j=0∑n​bj​Bjn​(t)=j=0∑n​bj​(nj​)tj(1−t)n−j
即

cv::Point2f recursive_bezier(const std::vector<cv::Point2f> &control_points, float t) 
{
    // TODO: Implement de Casteljau's algorithm
    cv::Point2f point(0.0f, 0.0f);
    for (int i = 0; i < control_points.size(); i++) {
        float B = C(control_points.size() - 1, i) * std::pow(t, i) * std::pow(1 - t, control_points.size() - 1 - i);
        point += B * control_points[i];
    }
    return point;
}
1
2
3
4
5
6
7
8
9
10

其中 C 为组合数的函数，实际上可以并不需要这个函数，而且每次调用会重复很多的计算，但是为了使用 C 函数后代码更加直观

float C(int a, int b) {
    float ans = 1;
    for (int i = 1; i <= a; i++) {
        ans *= i;
        if (i <= b) ans /= i;
        if (i <= a - b) ans /= i;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9

bezier

bezier 函数只需要在 $t\in [0,1]$ 内调用 recursive_bezier 并绘制即可

void bezier(const std::vector<cv::Point2f> &control_points, cv::Mat &window) 
{
    // TODO: Iterate through all t = 0 to t = 1 with small steps, and call de Casteljau's 
    for (float t = 0.0f; t <= 1.0f; t += 0.001f) {
        auto point = recursive_bezier(control_points, t);
        window.at<cv::Vec3b>(point.y, point.x)[1] = 255;	//设置绿色：rgb中g为255
    }
}
1
2
3
4
5
6
7
8

任意数量控制点的贝塞尔曲线

首先，对任意数量的点实现位置计算，需要实现公式
b n ( t ) = ∑ j = 0 n b j B j n ( t ) = ∑ j = 0 n b j ( n j ) t j ( 1 − t ) n − j \mathbf{b}^n(t)=\sum^n_{j=0}\mathbf{b}_jB_j^n(t)=\sum^n_{j=0}\mathbf{b}_j\left(

\right)t^j(1-t)^{n-j} bn(t)=j=0∑n​bj​Bjn​(t)=j=0∑n​bj​(nj​)tj(1−t)n−j
即

cv::Point2f recursive_bezier(const std::vector<cv::Point2f> &control_points, float t) 
{
    // TODO: Implement de Casteljau's algorithm
    cv::Point2f point(0.0f, 0.0f);
    for (int i = 0; i < control_points.size(); i++) {
        float B = C(control_points.size() - 1, i) * std::pow(t, i) * std::pow(1 - t, control_points.size() - 1 - i);
        point += B * control_points[i];
    }
    return point;
}
1
2
3
4
5
6
7
8
9
10

其中 C 为组合数的函数

float C(int a, int b) {
    float ans = 1;
    for (int i = 1; i <= a; i++) {
        ans *= i;
        if (i <= b) ans /= i;
        if (i <= a - b) ans /= i;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9

定义全局变量 int numOfControlPoints = 4;，并把代码中表示控制点数量的 4 全部改为 numOfControlPoints，并在主函数设置一个键盘输入改变 numOfControlPoints 的值即可。

反走样

实现对 Bézier 曲线的反走样。(对于一个曲线上的点，不只把它对应于一个像素，你需要根据到像素中心的距离来考虑与它相邻的像素的颜色。)

实际上作业上已经提示了我们怎么做，对于 recursive_bezier 所得到的点（下图中的紫色点）

以紫色点所在像素为中心，计算此九宫格内九个像素点中心到紫色点的距离，为了方便用距离的大小反映颜色的深浅，我们将距离进行归一化：

观察到，以左下角像素点为例，若紫色点位于中心像素的右上角，那么此时距离最大，且最大距离为 $\frac{3\sqrt{2}}{2}$，因此我们可以这样进行归一化
$$normal\_distance=\frac{\sqrt{2}}{3}distance$$
因为颜色的深度随距离的增加而减小，所以我们这样计算颜色
$$color=255(1-normal\_distance)$$
但是我们发现，在计算下一个点时，九宫格可能包含已经被上一个点所填充的像素，因此，我们在更新颜色的时候，需要取当前颜色与更新颜色的最大值进行更新，即仅当更新颜色大于当前颜色时才进行更新

void bezier(const std::vector<cv::Point2f> &control_points, cv::Mat &window) 
{
    // TODO: Iterate through all t = 0 to t = 1 with small steps, and call de Casteljau's 
    for (float t = 0.0f; t <= 1.0f; t += 0.001f) {
        auto point = recursive_bezier(control_points, t);
        auto centerPoint = cv::Point2f(int(point.x) + 0.5f, int(point.y) + 0.5f);
        auto x = point.x, y = point.y, centerX = centerPoint.x, centerY = centerPoint.y;
        for (int i = -1; i <= 1; i++)
            for (int j = -1; j <= 1; j++) {
                float distance = std::sqrt(std::pow(x - centerX - i, 2) + std::pow(y - centerY - j, 2));
                float normal_distance = distance * std::sqrt(2) / 3;    
                float color = 255.0f * (1 - normal_distance);
                if (window.at<cv::Vec3b>(centerY + j - 0.5f, centerX + i - 0.5f)[1] < color)
                    window.at<cv::Vec3b>(centerY + j - 0.5f, centerX + i - 0.5f)[1] = color;
            }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最终效果

6 个控制点的贝塞尔曲线

• 不进行反走样：

• 反走样后：

• 对比