Bézier Curves

引言

GAMES101现代图形学入门是由闫令琪老师教授。本次作业我们会通过 de Casteljau 算法来绘制由 4 个控制点表示的 Bézier 曲线。

总览

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

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

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

算法

De Casteljau 算法说明如下:

1. 考虑一个 p0, p1, … pn 为控制点序列的 Bézier 曲线。首先，将相邻的点连接起来以形成线段。
2. 用 t : (1 − t) 的比例细分每个线段，并找到该分割点。
3. 得到的分割点作为新的控制点序列，新序列的长度会减少一。
4. 如果序列只包含一个点，则返回该点并终止。否则，使用新的控制点序列并转到步骤 1。

使用 [0,1] 中的多个不同的 t 来执行上述算法，你就能得到相应的 Bézier 曲线。

开始编写

在本次作业中，你会在一个新的代码框架上编写，它比以前的代码框架小很多。和之前作业相似的是，你可以选择在自己电脑的系统或者虚拟机上完成作业。 请下载项目的框架代码，并使用以下命令像以前一样构建项目:

mkdir build
cd build
cmake ..
make

之后，你可以通过使用以下命令运行给定代码 ./BezierCurve。运行时，程序将打开一个黑色窗口。现在，你可以点击屏幕选择点来控制 Bézier 曲线。程 序将等待你在窗口中选择 4 个控制点，然后它将根据你选择的控制点来自动绘制 Bézier 曲线。代码框架中提供的实现通过使用多项式方程来计算 Bézier 曲线并绘制为红色。两张控制点对应的 Bézier 曲线如下所示:

在确保代码框架一切正常后，就可以开始完成你自己的实现了。注释掉 main 函数中 while 循环内调用 naive_bezier 函数的行，并取消对 bezier 函数的注释。要求你的实现将 Bézier 曲线绘制为绿色。

如果要确保实现正确，请同时调用 naive_bezier 和 bezier 函数，如果实现正确，则两者均应写入大致相同的像素，因此该曲线将表现为黄色。如果是这样，你可以确保实现正确。

你也可以尝试修改代码并使用不同数量的控制点，来查看不同的 Bézier 曲线。

评分与提交

评分:

• [5 分] 提交的格式正确，包含所有必须的文件。代码可以编译和运行。
• [20 分] De Casteljau 算法:
  对于给定的控制点，你的代码能够产生正确的 Bézier 曲线。
• [5 分] 奖励分数:
  实现对 Bézier 曲线的反走样。(对于一个曲线上的点，不只把它对应于一个像素，你需要根据到像素中心的距离来考虑与它相邻的像素的颜色。)
• [-2 分] 惩罚分数:
  未删除 /build, /.vscode 和 assignment4.pdf。
  未按格式建立 /images，缺少结果图片。
  未提交或未按要求完成 README.md。
  代码相关文件和 README 文件不在你提交的文件夹下的第一层。

提交:

• 当你完成作业后，请清理你的项目，记得在你的文件夹中包含 CMakeLists.txt 和所有的程序文件 (无论是否修改);
• 同时，请新建一个 /images 目录，将所有实验结果图片保存在该目录下;
• 再添加一个 README.md 文件写清楚自己完成了上述得分点中的哪几点 (如果完成了，也请同时在 images 目录下提交一份结果图片并注明)，并简要描述你在各个函数中实现的功能;
• 最后，将上述内容打包，并用“姓名 Homework4.zip”的命名方式提交到 SmartChair 平台。
  平台链接:http://www.smartchair.org/GAMES101-Spring2021/ 。

实现

代码框架

#include <chrono>
#include <iostream>
#include <opencv2/opencv.hpp>

std::vector<cv::Point2f> control_points;

void mouse_handler(int event, int x, int y, int flags, void *userdata) 
{
    if (event == cv::EVENT_LBUTTONDOWN && control_points.size() < 4) 
    {
        std::cout << "Left button of the mouse is clicked - position (" << x << ", "
        << y << ")" << '\n';
        control_points.emplace_back(x, y);
    }     
}

void naive_bezier(const std::vector<cv::Point2f> &points, cv::Mat &window) 
{
    auto &p_0 = points[0];
    auto &p_1 = points[1];
    auto &p_2 = points[2];
    auto &p_3 = points[3];

    for (double t = 0.0; t <= 1.0; t += 0.001) 
    {
        auto point = std::pow(1 - t, 3) * p_0 + 3 * t * std::pow(1 - t, 2) * p_1 +
                 3 * std::pow(t, 2) * (1 - t) * p_2 + std::pow(t, 3) * p_3;

        window.at<cv::Vec3b>(point.y, point.x)[2] = 255;
    }
}

cv::Point2f recursive_bezier(const std::vector<cv::Point2f> &control_points, float t) 
{
    // TODO: Implement de Casteljau's algorithm
    return cv::Point2f();

}

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 
    // recursive Bezier algorithm.

}

int main() 
{
    cv::Mat window = cv::Mat(700, 700, CV_8UC3, cv::Scalar(0));
    cv::cvtColor(window, window, cv::COLOR_BGR2RGB);
    cv::namedWindow("Bezier Curve", cv::WINDOW_AUTOSIZE);

    cv::setMouseCallback("Bezier Curve", mouse_handler, nullptr);

    int key = -1;
    while (key != 27) 
    {
        for (auto &point : control_points) 
        {
            cv::circle(window, point, 3, {255, 255, 255}, 3);
        }

        if (control_points.size() == 4) 
        {
            naive_bezier(control_points, window);
            //   bezier(control_points, window);

            cv::imshow("Bezier Curve", window);
            cv::imwrite("my_bezier_curve.png", window);
            key = cv::waitKey(0);

            return 0;
        }

        cv::imshow("Bezier Curve", window);
        key = cv::waitKey(20);
    }

    return 0;
}

De Casteljau算法

$$
b^2_0(t) = (1 - t)^2b_0 + 2t(1 - t)b_1 + t^2b_2
$$

bezier() 函数则调用 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 
    // recursive Bezier algorithm.
    for (float t = 0; t <= 1; t += 0.001f) {
        auto point = recursive_bezier(control_points, t);
        window.at<cv::Vec3b>(point.y, point.x)[1] = 255;
    }
}

朴素算法

由于给定的框架代码有四个控制点，所以我们可以向课程中那样依次推演：

cv::Point2f recursive_bezier(const std::vector<cv::Point2f> &control_points, float t) 
{
    // TODO: Implement de Casteljau's algorithm
    
    auto p_0 = control_points[0];
    auto p_1 = control_points[1];
    auto p_2 = control_points[2];
    auto p_3 = control_points[3];

    auto p_01 = (1 - t) * p_0 + t * p_1;
    auto p_12 = (1 - t) * p_1 + t * p_2;
    auto p_23 = (1 - t) * p_2 + t * p_3;

    auto p_012 = (1 - t) * p_01 + t * p_12;
    auto p_123 = (1 - t) * p_12 + t * p_23;

    return cv::Point2f((1 - t) * p_012 + t * p_123);
}

递归算法

另一种递归方式则采用分而治之的策略，将问题不断分化：

cv::Point2f recursive_bezier(const std::vector<cv::Point2f> &control_points, float t) 
{
    // TODO: Implement de Casteljau's algorithm
    if (control_points.size() == 1)
        return control_points[0];

    std::vector<cv::Point2f> lines;
    for (int i = 0; i < control_points.size() - 1; i++)
        lines.emplace_back((1 - t) * control_points[i] + t * control_points[i + 1]);

    return recursive_bezier(lines, t);
}

参考文章

• 作业四得到这样的结果是否满足要求？
• 从零开始学图形学：10分钟看懂贝塞尔曲线
• GAMES101作业4-贝塞尔曲线&OpenCV图像处理
• 【GAMES101】作业4（提高）含Bazier曲线的反走样处理