Xungerrrr's Blog

Draw Line

Compute Graphics - Homework 3

Computer Graphics
Word count: 1.5kReading time: 7 min
2019/03/26 Share

使用Bresenham算法画一个三角形边框

根据要求，设计一个三角形的类，如下。在构造函数中输入三个顶点坐标。使用draw函数画图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Triangle {
public:
    Triangle(Shader &shaderProgram, int x1, int y1, int x2, int y2, int x3, int y3, int width, int height, float col[]);
    void draw();
    
private:
    float color[3] = { 1.0f, 1.0f, 1.0f };
    unsigned int VBO, VAO;
    int windowWidth, windowHeight;
    int x1, y1, x2, y2, x3, y3;
    Shader shader;

    void drawLine(int x0, int y0, int xn, int yn);
    void drawPoint(int x, int y, int z, float color[3]);
};

draw函数初始化缓冲区，然后调用drawLine函数画三角形的三条边：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Triangle::draw() {
    glGenBuffers(1, &VBO);
    glGenVertexArrays(1, &VAO);

    glBindVertexArray(VAO);
    glBindBuffer(GL_ARRAY_BUFFER, VBO);
    
    glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 6 * sizeof(float), (void*)0);
    glEnableVertexAttribArray(0);
    glVertexAttribPointer(1, 3, GL_FLOAT, GL_FALSE, 6 * sizeof(float), (void*)(3 * sizeof(float)));
    glEnableVertexAttribArray(1);

    drawLine(x1, y1, x2, y2);
    drawLine(x1, y1, x3, y3);
    drawLine(x2, y2, x3, y3);

    glDeleteVertexArrays(1, &VAO);
    glDeleteBuffers(1, &VBO);
}

drawLine函数根据两个端点坐标，使用Bresenham算法计算直线上每一个点的坐标，然后调用drawPoint函数画点。步骤如下：

  1. 输入数据

    (x0, y0)为起点坐标，(xn, yn)为终点坐标。

    1
    void Triangle::drawLine(int x0, int y0, int xn, int yn)

  2. 计算Δx和Δy，判断Δx和Δy是否为0

    如果Δx和Δy都为0，说明两点重合，只画一个点；如果Δx为0，则画一条垂直的线；如果Δy为0，则画一条水平的线。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int delta_x = abs(xn - x0), delta_y = abs(yn - y0);
    int x = x0, y = y0;
    if (delta_x == 0 && delta_y == 0) {
        drawPoint(x, y, 0, color);
    }
    else if (delta_x == 0) {
        int y_dir = (yn - y0) / delta_y;
        for (int i = 0; i <= delta_y; i++) {
            drawPoint(x, y, 0, color);
            y += y_dir;
        }
    }
    else if (delta_y == 0) {
        int x_dir = (xn - x0) / delta_x;
        for (int i = 0; i <= delta_x; i++) {
            drawPoint(x, y, 0, color);
            x += x_dir;
        }
    }

  3. 如果Δx和Δy均不为0，则使用Bresenham算法画直线

    • 斜率m的绝对值小于或等于1时，每次移动x坐标一个单位，然后计算y坐标。（根据端点坐标确定移动方向）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      else if ((float)delta_y / (float)delta_x <= 1) {
          int x_dir = (xn - x0) / delta_x;
          int y_dir = (yn - y0) / delta_y;
          int p = 2 * delta_y - delta_x;
          for (int i = 0; i <= delta_x; i++) {
              drawPoint(x, y, 0, color);
              x += x_dir;
              if (p <= 0) {
                  p += (2 * delta_y);
              }
              else {
                  y += y_dir;
                  p += (2 * delta_y - 2 * delta_x);
              }
          }
      }

    • 斜率m的绝对值大与1时，每次移动y坐标一个单位，然后计算x坐标。（根据端点坐标确定移动方向）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      else {
          int x_dir = (xn - x0) / delta_x;
          int y_dir = (yn - y0) / delta_y;
          int p = 2 * delta_x - delta_y;
          for (int i = 0; i <= delta_y; i++) {
              drawPoint(x, y, 0, color);
              y += y_dir;
              if (p <= 0) {
                  p += (2 * delta_x);
              }
              else {
                  x += x_dir;
                  p += (2 * delta_x - 2 * delta_y);
              }
          }
      }

drawPoint函数会根据窗口大小，将输入的坐标值转换成-1~1之间的标准坐标值，然后绘制一个点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Triangle::drawPoint(int x, int y, int z, float color[3]) {
    float point[6];
    point[0] = (float)x / windowWidth * 2;
    point[1] = (float)y / windowHeight * 2;
    point[2] = z;
    point[3] = color[0];
    point[4] = color[1];
    point[5] = color[2];

    shader.use();
    glViewport(0, 0, windowWidth, windowHeight);
    glBufferData(GL_ARRAY_BUFFER, sizeof(point), point, GL_STATIC_DRAW);
    glBindVertexArray(VAO);
    glDrawArrays(GL_POINTS, 0, 1);
}

最后在ImGui设置三个点的坐标，就可以画出三角形

使用Bresenham算法画一个圆

根据要求，设计一个圆的类，如下。在构造函数中输入圆心坐标和半径。使用draw函数画图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Circle {
public:
    Circle(Shader &shaderProgram, int x, int y, int r, int width, int height);
    void draw();
    
private:
    float color[3] = { 1.0f, 1.0f, 1.0f };
    unsigned int VBO, VAO;
    int windowWidth, windowHeight;
    int x0, y0, r;
    Shader shader;

    void drawSymmetricPoints(int x, int y);
    void drawPoint(int x, int y, int z, float color[3]);
};

draw函数初始化缓冲区，使用Bresenham算法计算1/8圆周的坐标，然后调用drawSymmetricPoints画出所有8个对称点。计算时，x坐标每次增加1，然后计算y坐标的值。

1
2
3
4
5
6
7
8
9
10
11
12
int x = x0, y = y0 + r, d = 1 - r;
for (int i = 0; i <= r / sqrt(2); i++) {
    drawSymmetricPoints(x, y);
    x++;
    if (d <= 0) {
        d += (2 * (x - x0) + 1);
    }
    else {
        y--;
        d += (2 * (x - y + y0 - x0) + 2);
    }
}

drawSymmetricPoints函数计算8个关于圆心对称的点，然后调用drawPoint函数画点。drawPoint函数与画三角形的drawPoint函数相同。

1
2
3
4
5
6
7
8
9
10
void Circle::drawSymmetricPoints(int x, int y) {
    drawPoint(x, y, 0, color);
    drawPoint(y - y0 + x0, x - x0 + y0, 0, color);
    drawPoint(2 * x0 - x, y, 0, color);
    drawPoint(y - y0 + x0, x0 + y0 - x, 0, color);
    drawPoint(x, 2 * y0 - y, 0, color);
    drawPoint(y0 + x0 - y, x - x0 + y0, 0, color);
    drawPoint(2 * x0 - x, 2 * y0 - y, 0, color);
    drawPoint(y0 + x0 - y, x0 + y0 - x, 0, color);
}

最后在ImGui设置圆心坐标和半径，就可以画出圆。

在GUI在添加菜单栏，可以选择是三角形边框还是圆，以及能调整圆的大小

在菜单栏中绑定bool对象，实现选择：

1
2
3
4
5
if (ImGui::BeginMainMenuBar()) {
    ImGui::MenuItem("Triangle", NULL, &tri);
    ImGui::MenuItem("Circle", NULL, &cir);
    ImGui::EndMainMenuBar();
}

圆的参数由ImGuid的滑块传入，因此可以调整圆的大小：

1
2
3
4
5
6
7
8
9
if (cir) {
    ImGui::Begin("Circle");
    ImGui::SliderInt("x", center, -windowWidth / 2, windowWidth / 2);
    ImGui::SliderInt("y", center + 1, -windowWidth / 2, windowWidth / 2);
    ImGui::SliderInt("Radius", radius, 0, windowWidth / 2);
    ImGui::End();
    Circle circle(shader, center[0], center[1], radius[0], windowWidth, windowHeight);
    circle.draw();
}

Bonus：使用三角形光栅转换算法，用和背景不同的颜色，填充你的三角形

给三角形类添加两个方法。fill方法用来填充三角形，contain方法用来判断一个点是否在三角形内部。

fill函数中，先对顶点坐标进行排序，得到三角形的包围盒。然后遍历包围盒内的点，调用contain判断点是否在内部，最后调用drawPoint画点即可。

1
2
3
4
5
6
7
for (int x = x_axis[0]; x <= x_axis[2]; x++) {
    for (int y = y_axis[0]; y <= y_axis[2]; y++) {
        if (contain(x, y)) {
            drawPoint(x, y, 0, color);
        }
    }
}

contain函数使用向量的向量积来判断点是否在三角形内部。以该点为起点，分别以三个顶点为终点，可以得到三个向量。按照顺序两两求向量积，得到三个乘积。如果三个乘积同号，则说明点在三角形内部。

1
2
3
4
5
6
7
8
9
10
11
bool Triangle::contain(int x, int y) {
    int v1[] = { x - x1, y - y1 };
    int v2[] = { x - x2, y - y2 };
    int v3[] = { x - x3, y - y3 };
    int cross_product_1 = v1[0] * v2[1] - v1[1] * v2[0];
    int cross_product_2 = v2[0] * v3[1] - v2[1] * v3[0];
    int cross_product_3 = v3[0] * v1[1] - v3[1] * v1[0];
    if (cross_product_1 * cross_product_2 >= 0 && cross_product_2 * cross_product_3 >= 0)
        return true;
    return false;
}

填充结果

动画演示

CATALOG
  1. 1. 使用Bresenham算法画一个三角形边框
  2. 2. 使用Bresenham算法画一个圆
  3. 3. 在GUI在添加菜单栏，可以选择是三角形边框还是圆，以及能调整圆的大小
  4. 4. Bonus：使用三角形光栅转换算法，用和背景不同的颜色，填充你的三角形
  5. 5. 动画演示
Total : 43
2020
2019
2018
2017
Android Computer Graphics iOS UWP Unity Java Linux 实训 blog Face-Recognition Image-Understanding Azure Computer Vision SE
Unity