计算机图形学#1 – 基本图形的扫描转换
|
727
|
0
|
笔记

4305 字
|
39 分钟

这一部分的演示代码基于 OpenGL 的 glfw 库以及 Windows 自带的 opengl32.lib 库，并使用Microsoft Visual Studio 2022 以 C++ 进行编写。用到的代码框架如下为了偷懒把绘制单个像素点的功能封装在了drawPixel函数里，以及为了给我自己加强代码可读性便于理解多加了一个自定义的像素点类PixelPoint。 这部分提取出来主要是为了脱离OpenGL特有的代码来更加一般化的描述算法，而不会被一些只存在于OpenGL里的东西妨碍对于图形学算法的理解。

#include"GLFW/glfw3.h"
#include <cmath>
#include <iostream>
using namespace std;

// 窗口大小
const int WIDTH = 300;
const int HEIGHT = 300;
// 原点位置
int Ox = 150;
int Oy = 150;

// 像素点类定义
struct PixelPoint {
    PixelPoint() { x = y = 0; }
    PixelPoint(int x, int y) :x(x), y(y) {}

    // x,y是相对于窗口左下角的非负整数,与一般的数学坐标轴类似
    int x, y;
};

// 在屏幕上对应坐标的点绘制一个像素
void drawPixel(int x, int y) {
    // openGL默认是在世界坐标中绘制,以画面中心为原点,坐标范围为[-1,1],所以需要转化一下坐标
    float transX = (float)(x + Ox) / (WIDTH / 2) - 1;
    float transY = (float)(y + Oy) / (HEIGHT / 2) - 1;

    // 绘制出的点为黑色
    glColor3f(0.0, 0.0, 0.0);

    glBegin(GL_POINTS);
    glVertex2f(transX, transY);
    glEnd();
}

// 主要编写渲染的部分
void draw() {
    /*这里编写*/
}

int main() {
    // 初始化glfw
    if (!glfwInit()) {
        cout << "Failed to initialize GLFW" << endl;
        return -1;
    }

    // 创建窗口
    GLFWwindow* window = glfwCreateWindow(WIDTH, HEIGHT, "hello world", NULL, NULL);
    if (window == nullptr) {
        cout << "Failed to create window" << endl;
        return -1;
    }
    glfwMakeContextCurrent(window);

    // 循环渲染
    while (!glfwWindowShouldClose(window)) {
        // 清空窗口
        glClearColor(1.0f, 1.0f, 1.0f, 0.0f);
        glClear(GL_COLOR_BUFFER_BIT);

        // 开始绘制
        draw();

        //刷新缓冲并检测事件
        glfwSwapBuffers(window);
        glfwPollEvents();
    }

    //清空资源
    glfwTerminate();
    return 0;
}

什么是扫描转换？

我们在计算机中描述一个模型的时候，往往使用了这些模型的顶点来进行描述整个模型。而我们的显示器也被称作光栅显示器（也就是可以看成一个个像素形成的点阵，每个像素可以由多种颜色显示），在光栅显示器上显示的任何一种图形都是多种颜色或一种颜色的像素的集合，如果想要在显示器上直观的将这个图形显示出来，就需要告诉显示器哪些像素要亮以及要亮成什么颜色。相当于将一个连续的几何体（直线、曲线等等）变成了离散的点集（像素）。确定这个像素集合和每个像素的颜色用于显示图形的过程就叫图形的生成，也叫做光栅化。更为标准的定义如下：在像素点阵中确定最佳逼近理想点集，并用指定的颜色显示这些像素点集的过程。更为概括的理解如下：光栅化就是找到所有被几何原型所占据的所有像素点。

图形的扫描转换是一种按照扫描线顺序来将光栅化的结果填入帧缓存寄存器的一种方式。图形的生成是从顶点描述的图形转化为图形对应的像素集的过程，而图形的扫描转换是包含图形的生成以及将生成的像素集以扫描线顺序填入帧缓存寄存器的过程。

小趣事：

光栅化英语为 Rasterize ，其中的 Raster 其实是德语的“屏幕”的意思

直线的扫描转换算法

给出直线两个端点，计算并输出最佳逼近直线的像素序列。这个过程也叫直线的光栅化

数值微分算法 DDA

算法核心

预先设置好绘制的步数stepNum，通过直线的微分方程确定每一步绘制的点的坐标增量（也可理解为将直线分成了等长的stepNum段），调整增量的大小使得两个坐标的最大增量固定为1，另一个方向上的坐标使用四舍五入，不断步进完成绘制。

算法理解

首先是为什么对象是最大增量？根据前面描述的扫描转换思想，DDA的做法就是将垂直于长轴的直线作为扫描线，相当于保证在统一扫描线上，不会存在两个或者更多的点，这样才方便我们通过移动扫描线一个点一个点的表示和绘制。

然后是为什么最大增量是1？而我们最后需要得到是像素点阵，而像素的最小单位是1个，所以每次扫描线的移动距离为1。

具体步骤

首先根据直线的两个端点算出总的坐标增量，选取其中大的值为步数（也可以理解为扫描线条数），再将两个方向上的坐标增量除以最大的那个坐标增量（也就是步长），这样得到了两个更小的坐标增量，其中一个坐标增量小于1，一个刚好等于1。然后我们用浮点型来记录实际坐标，将实际坐标四舍五入得到对应的像素的下标。绘制完后计算下一个点的实际坐标，一直把所有点绘制完。

代码实现

// 绘制直线,起点为点S,重点为点T (DDA方法)
void drawLineDDA(PixelPoint S, PixelPoint T) {
    // 坐标增量
    float dx = T.x - S.x;
    float dy = T.y - S.y;

    // 步数
    int stepNum = abs(dx) > abs(dy) ? abs(dx) : abs(dy);// 短边对应坐标轴作为扫描线,所以选取长边长度为次数

    // 将总坐标增量调整为每步的坐标增量
    dx /= stepNum;
    dy /= stepNum;

    // 当前实际坐标
    float nowx = S.x;
    float nowy = S.y;

    // 开始绘制单个顶点，总共需要绘制步数+1个点（包含起始点）
    for (int i = 0; i <= stepNum; i++) {
        // 实际坐标四舍五入得到像素坐标
        drawPixel((int)(nowx + 0.5), (int)(nowy + 0.5));
        // 移动到下一个点
        nowx += dx;
        nowy += dy;
    }
}
// 主要部分
void draw() {
    drawLineDDA(PixelPoint(10, 100), PixelPoint(200, 200));
}

后续给出的函数都只需要在draw函数中给出需要的参数调用即可，在之后的代码中不会再包含draw函数的内容

性能分析

DDA的好处就是简单好写，但是在上面也说了，我们需要用浮点型来计算实际坐标，还需要使用四舍五入这样的运算，按照上面的代码实现方式有4次浮点型加法，而浮点型加法是显著慢于整型加法的，所以说效率很低。

那么我们接下来想一想能不能将一部分的浮点型加法改成整型加法。再仔细回想一下，在DDA中，每一步的时候需要计算两个方向的浮点数坐标，然后四舍五入来得到下一个像素的坐标。但是因为我们要求两个方向上的最大增量固定为1，另一个方向上的增量一定是小于1的，也就是对于最后舍入的像素坐标来说，增量要么是1要么是0 ，那我们能不能求出来什么时候增量为1，什么时候增量为0呢？

中点Bresenham算法

算法核心

不妨假设x轴坐标增量为1，y轴坐标增量小于1大于0，当前像素点若为(x,y) ，若点(x+1,y+1)和 (x+1,y)的中点在直线的上方，那么显示的就是(x+1,y+1)这个像素点，否则就显示的是(x+1,y)这个像素点。再以新的点继续步进。具体如何高效的判定上方还是下方在后续的具体步骤中进行分析。

算法理解

在之前讨论的优化DDA的方法中，我们尝试解决的问题是如何更加快速的确定增量。在这里我们使用的方法而正如其名：利用两个增量的中点坐标，看实际坐标更靠近于哪一个点。以下图绘制直线 2x-3y-2=0 为例，用最粗暴的实现方式来理解，我们在当前绘制完成的坐标 \text{Now}(1,0) 通过计算两种增量对应的点，分别为y轴有增量的点 \text{Next}_\text{up}(2,1) 和没有增量的点 \text{Next}_\text{down}(2,0) 计算出他们的中点 \text{Next}_\text{middle}(2,0.5)，实际在直线上的点 \text{Next}_\text{real}(2,\frac{2}{3}) 是在 \text{Next}_\text{up} 和 \text{Next}_\text{middle} 之间的，所以下一步对应的像素点就应该是 \text{Next}_\text{up}

image-20220919212937424

上述的实现方式是最为暴力的，可以做很多基础优化。为了检测是不是真正理解了，可以试着再想想在画完 (2,1) 后，下一个画的坐标是什么，结果在下面的图中：

image-20220919235210643

首先可以想到的是，上述的实现甚至还有一个求解直线方程来计算点 \text{Next}_\text{real} 的坐标的 ，会很耗时间，能不能换一个方法来确定点 \text{Next}_\text{real} 和点 \text{Next}_\text{middle}的位置关系呢？我们转换一下思路，我们可以通过确定点 \text{Next}_\text{middle}和直线的位置关系来间接确定\text{Next}_\text{real} 和点 \text{Next}_\text{middle}的位置关系。对于一般式的直线方程Ax+By+C=0，有点P(x_0,y_0)，若Ax_0+By_0+C>0则在点在直线下方；相反的则在上方。（这里点在直线上约定为不增加）。也就是说，我们只需要由当前点 \text{Now}(x_i,y_i) 推算出 中点 \text{Next}_\text{middle}(x_i+1,y_i+0.5) 对应带入到直线方程的值d_i=A(x_i+1)+B(y_i+0.5)+C = -k(x_i+1)+(y_i+0.5)-b （这里的 k 和 b 是对应的斜截式中的斜率和截距）的正负就可以确定下一步了。也就是说，可以有如下的递推式：

\begin{align}
x_{i+1}=x_i+1 ; \quad
y_{i+1}=
    \begin{cases}
        &y_i        & d \geq 0 \\
        &y_i + 1    & d <  0 \\
    \end{cases}
\end{align}

接着观察这个 d_i=A(x_i+1)+B(y_i+0.5)+C 式子，可以发现 d_{i + 1} 也可以根据 y_i 的两种变化（也就是 d_i 的正负）分两种情况递推：对于 d_i \geq 0 的情况，代入y_{i+1}=y_i ：

\begin{align}
d_{i+1} &=  A(x_{i + 1} + 1) + B(y_{i + 1} + 0.5) + C \\
        &=  A(x_i + 2) + B(y_i + 0.5) + C \\
        &=  A(x_i + 1) + B(y_i + 0.5) + C + A \\
        &=  d_i + A \\
\end{align}

同理，对于 d_i < 0 的情况，代入y_{i+1}=y_i+1 ：

\begin{align}
d_{i+1} &=  A(x_{i + 1} + 1) + B(y_{i + 1} + 0.5) + C \\
        &=  A(x_i + 2) + B(y_i + 1 + 0.5) + C \\
        &=  A(x_i + 1) + B(y_i + 0.5) + C + A + B \\
        &=  d_i + A + B
\end{align}

递推式有了，我们还需要计算一下初始值。将直线的起始点(x_0,y_0)带入原方程中，可得：

\begin{align}
d_0 &=  A(x_0 + 1) + B(y_0 + 0.5) + C \\
    &=  Ax_0 + A + By_0  + 0.5B + C \\
    &=  (Ax_0  + By_0 + C) + A + 0.5B \\
    &=  A + 0.5B
\end{align}

合起来整理一下就是：

\begin{align}
d_0 = A + 0.5B, \quad 
d_{i+1}=
    \begin{cases}
        &d_i + A        & d \geq 0 \\
        &d_i + A + B    & d <  0 \\
    \end{cases}

\end{align} 
\tag{1}

注意以上递推方程成立的条件有两个：

  • x轴坐标增量为1，y轴坐标增量小于1，且坐标增量都为非负（使得 y_{i+1} 只能 y_{i+1}等于 y_i 或 y_i + 1 ）
  • 扫描线从左到右扫描（使得x_{i+1}=x_i+1始终成立）

如果用斜截式来理解的话成立的条件就更加简单：k\in[0,1] ；如果用图像的角度来理解的话也很清晰：直线需要在以起点为原点的第一象限角平分线到 x 轴正半轴的区域内。那其他的情况怎么办呢？在绘制的时候使用对称转换一下坐标即可。

回到优化的话题上来，在使用递推式来判断增量大小后效率已经好了不少，但是注意到在上述的递推式中，还有一个浮点数 0.5 。在判断 y 到底需不需要加 1 的时候，我们只是判断了 d 的正负，也就是说 d 的绝对值大小是没有意义的，那自然就可以让 2d 来代替 d 来作为判断依据。而与此同时，递推方程中的浮点数也被消除了，变成了一下形式：（下面 (2)公式中的 d 实际的值等于 (1) 公式中的 2d )

\begin{align}
d_0 = 2A + B, \quad 
d_{i+1}=
    \begin{cases}
        &d_i + 2A       & d \geq 0 \\
        &d_i + 2A + 2B  & d <  0 \\
    \end{cases}
\end{align}
\tag{2}

而在实际运用中，如果指定的是直线的起点 S(x_0,y_0) 和终点 T(x_1,y_1)，相较于一般式，更容易得到的是斜截式。（下面 (3)公式中的 d 实际的值等于 (2) 公式中的 d/B )

\begin{align}
d_0 = 1 - 2k, \quad 
d_{i+1}=
    \begin{cases}
        &d_i - 2k       & d \geq 0 \\
        &d_i - 2k + 2   & d <  0 \\
    \end{cases}
\end{align}
\tag{3}

再次发现因为 d 的绝对值大小是没有意义的，而正常求斜率 k=(x_1-x_0)/(y_1-y_0) 需要用到除法，那我们可以设 \Delta x=x_1-x_0,\,\Delta y=y_1-y_0 ，我们用整个 \Delta x * d 来代替 (3) 式中的 d 来作为判断依据，就和之前 (1) 式中的处理 0.5的方式一样将求 k 的除法变成了整数，就可以得到：

\begin{align}
d_0 =  \Delta x - 2\Delta y, \quad 
d_{i+1}=
    \begin{cases}
        &d_i - 2 \Delta y               & d \geq 0 \\
        &d_i - 2 \Delta y + 2 \Delta x  & d <  0 \\
    \end{cases}
\end{align}
\tag{4}

上述 (1)(2)(3)(4) 式都是可行的递推式，其中(2)式效率高于(1)式，具体使用哪一种可以根据给出的直线形式来确定。

具体步骤

以给出直线的起点 S(x_0,y_0) 和终点 T(x_1,y_1) 为例，首先需要判断直线是否满足上述递推方程成立的条件，否则将直线进行对称、旋转、平移等变换，得到满足的直线（注意点 S 和 T 的坐标也需要变换）。计算变换后直线 \Delta x=x_1-x_0,\,\Delta y=y_1-y_0\,,d = \Delta x - 2 \Delta y 。从起点开始绘制，根据 d 值决定步进增量并用递推式更新 d 的值，反复步进，一直把所有点绘制完。

代码实现

// 绘制直线,起点为点S,重点为点T,斜率在[0,1] (Bresenham方法)
void drawLineBresenham(PixelPoint S, PixelPoint  T) {
    // 保证从左到右
    if (S.x > T.x)
        swap(S, T);
    // delta值用于计算d的递推值
    int deltaX = T.x - S.x;
    int deltaY = T.y - S.y;

    // 当前坐标
    int nowX = S.x;
    int nowY = S.y;

    // 偏差值
    int d = deltaX - 2 * deltaY;
    // y增量为0时的预处理偏差值增量
    int downD = 2 * deltaX - 2 * deltaY;
    // y增量为1时的预处理偏差值增量
    int upD = -2 * deltaY;

    // 步进
    while (nowX <= T.x) {
        drawPixel(nowX, nowY);
        // x增量固定为1
        nowX++;
        // y增量根据偏差值d
        if (d >= 0) {
            // 中点在直线下,y增量为0
            d += downD;
        }
        else {
            // 中点在直线上,y增量为1
            nowY++;
            d += upD;
        }
    }
}

圆的扫描转换

对于一个完整的圆，它是关于x轴、y轴、x=y、x=-y对称的，也就是说可以从弧度出发将一个圆划分成每\frac{\pi}{2}为一个区间进行对称，也就是说如果我们在[\frac{\pi}{2},\pi]上确定了点(x,y)，那么也就可以确定其他7个点：(y,x)，(-y,x)，(-x,y)，(-x,-y)，(-y,-x)，(y,-x)，(x,-y)。也就是说，我们只需要确定[\frac{\pi}{2},\pi]上的点的坐标，就可以确定整个圆上点的坐标。那么问题转化为求[\frac{\pi}{2},\pi]上的弧线段上点的坐标。（当然还可以继续划分，也可以选用其他段上初始点进行绘制）

简单方程方式

算法核心

利用圆弧的函数方程，直接对计算的坐标进行取整计算，来得到对应的坐标位置。

算法理解

圆在直角坐标系下的公式可以表达为 x^2+y^2=R^2，而按照扫描线的思想，对于[0,\frac{\pi}{2}]上的圆弧，x轴正方向为最大的位移方向，那么就可以写出这样的递推式来求点：（公式中的round为四舍五入取整函数）

\begin{align}
x_{i+1}=x_i+1 ,x \in [0,\frac{R}{\sqrt{2}} ];\quad
y_{i+1}=round(\sqrt{R^2-x_{i+1}^2}); \quad

\end{align}

圆在极坐标系下的公式可以表达为 x=Rcos\theta,y=Rsin\theta，同样的按照步进的思想控制 \theta 大小的变化，就可以得到点上的所有坐标。那么就可以写出这样的递推式来求点(这里可以试一下改变\Delta\theta 的值，看一看会发生什么)：

\begin{align}
\theta _{i+1}=\theta _i + \Delta \theta,
\theta \in [0,\frac{\pi}{2}]; \quad
\begin{cases}
x_{i+1}=round(Rcos\theta_{i+1}); \\
y_{i+1}=round(Rsin\theta_{i+1}); \quad
\end{cases}
\end{align}

代码实现


// 绘制圆心在(x,y),半径为R的圆，直角坐标系方程方程
void drawCircleRetangular(int x,int y,double R) {
    // 对于圆心的处理：将圆心移动到坐标原点
    int nowX = 0;
    int nowY = R;
    // 步进计算
    while (nowX <= R / sqrt(2.0)) {
        // 利用对称性一次绘制8个点,还原平移得到将相对于原点的坐标还原为实际坐标
        drawPixel(x + nowX, y + nowY);
        drawPixel(y + nowY, x + nowX);
        drawPixel(x - nowX, y + nowY);
        drawPixel(y - nowY, x + nowX);
        drawPixel(x - nowX, y - nowY);
        drawPixel(y - nowY, x - nowX);
        drawPixel(x + nowX, y - nowY);
        drawPixel(y + nowY, x - nowX);
        // 更新
        nowX += 1;
        nowY = round(sqrt(R * R - nowX * nowX));
    }
}
// 绘制圆心在(x,y),半径为R的圆，极坐标方程方式
void drawCirclePolar(int x, int y, int R) {
    // 对于圆心的处理：将圆心移动到坐标原点
    int nowX = 0;
    int nowY = R;
    float theta = 0;
    // 每次theta的改变量,也就是步进量
    float delta = 0.01;
    // 常量PI
    float PI = acos(-1);
    // 步进计算
    while (theta <= PI / sqrt(2.0)) {
        // 利用对称性一次绘制8个点,还原平移得到将相对于原点的坐标还原为实际坐标
        drawPixel(x + nowX, y + nowY);
        drawPixel(y + nowY, x + nowX);
        drawPixel(x - nowX, y + nowY);
        drawPixel(y - nowY, x + nowX);
        drawPixel(x - nowX, y - nowY);
        drawPixel(y - nowY, x - nowX);
        drawPixel(x + nowX, y - nowY);
        drawPixel(y + nowY, x - nowX);
        // 更新
        theta += delta;
        nowX = round(R * cos(theta));
        nowY = round(R * sin(theta));
    }
}

性能分析

对于直角坐标系下的递推方程，涉及到求平方根以及浮点数的运算及取整；对于极坐标下的递推方程，涉及到三角函数和浮点数的运算及取整。这些运算相对于简单的浮点数加减来说都算是慢的了，更不要说是相比整数了。这种方法简单直观，但是计算量极大，效率极低。

中点Bersenham算法

算法核心

整体上与直线的扫描转换相同

弧线的扫描转换算法

在这里的“弧线”是指能够写出对应方程的弧线段，而对于不规则的弧线通常将其划分为可以拟合的多个弧线段来绘制，而且对于存在对称性的弧线，通常使用对称性一次性绘制多个点，从而减少计算量。

绘制抛物线曲线

对 f(x)=kx^2（k可以为小数） 构造函数 F(x,y) = y-kx^2 。由于函数性质可以发现 kx^2 是关于 y 轴对称的,也就是说可以只讨论第一象限的图像，并通过对称得到完整的图形。由f'(x)= 2kx可得在[0,\frac{1}{2k}] 最大位移方向为 x 轴方向，在 [\frac{1}{2k},+\infty) 最大位移方向为 y 轴方向，所以分成两段讨论。

对于[0,\frac{1}{2k}]段，判别式如下：

\begin{align}
d_i &= F(x_i + 1,y_i + 0.5)         \\
    &= y_i + 0.5 - k(x_i + 1) ^ 2   \\
    &= y_i + 0.5 - k x_i^2 - 2kx_i - k
\end{align}
\tag{1.1}

对于点 P(x_0,y_0)，若 d = y_0 - kx_0^2 <0，则点 P 在曲线上方，否则认为是在上方（与直线类似），x 和 y 的增量如下：

\begin{align}
x_{i+1}=x_i+1 ; \quad
y_{i+1}=
    \begin{cases}
        &y_i        & d \geq 0 \\
        &y_i + 1    & d <  0 \\
    \end{cases}
\end{align}
\tag{1.2}

当 d \geq 0 时：

\begin{align}
d_{i+1} &=  y_{i+1}+0.5-kx_{i+1}^2-2kx_{i+1}-k      \\
        &=  y_i+0.5-k(x_i+1)^2 -2k(x_i+1)-k         \\
        &=  d_i -2kx_i-2k-k                         \\
        &=  d_i - 2kx_i -3k
\end{align}
\tag{1.3}

当 d < 0 时：

\begin{align}
d_{i+1} &=  y_{i+1}+0.5-kx_{i+1}^2-2kx_{i+1}-k      \\
        &=  y_i+1+0.5-k(x_i+1)^2 -2k(x_i+1)-k       \\
        &=  d_i-2kx_i-2k-k+1                        \\
        &=  d_i-2kx_i-3k+1
\end{align}
\tag{1.4}

所以[0,\frac{1}{2k}]段总的递推式如下(初始点为(0,0):

d_0 =  0.5 - k \,,d_{i+1}=
\begin{cases}
d_i - 2kx_i -3k             & d_i \geq 0 \\
d_i - 2kx_i -3k + 1         & d_i < 0 
\end{cases}

对于 [\frac{1}{2k},+\infty) 段，判别式如下：

\begin{align}
d_i &= F(x_i + 0.5,y_i + 1)         \\
    &= y_i + 1 - k(x_i + 0.5) ^ 2   \\
    &= y_i -kx_i^2 - kx_i -0.25k +1 \\
\text{令}d_i' &= 4d_i\\
d_i'&= 4y_i - 4kx_i^2 - 4kx_i -k +4
\end{align}
\tag{2.1}

对于点 P(x_0,y_0)，若 d = y_0 - kx_0^3 <0，则点 P 在曲线右方，否则认为是在左方，x 和 y 的增量如下：

\begin{align}
 x_{i+1}=
    \begin{cases}
        &x_i + 1    & d \geq 0 \\
        &x_i        & d <  0 \\
    \end{cases}\quad,
y_{i+1}=y_i+1 ;
\end{align}
\tag{2.2}

当 d \geq 0 时：

\begin{align}
d_{i+1} &=  4y_{i+1} - 4kx_{i+1}^2 - 4kx_{i+1} -k +4        \\
        &=  4(y_i+1) -4k(x_i+1)^2 -4k(x_i+1)-k+4            \\
        &=  4y_i - 4kx_i^2 -8kx_i-4k - 4kx_i -4k - k +8     \\
        &=  (4y_i - 4kx_i^2- 4kx_i -k +4) -8kx_i -8k + 4    \\
        &=  d_i - 8kx_i - 8k +4                             \\
\end{align}
\tag{2.3}

当 d < 0 时：

\begin{align}
d_{i+1} &=  4y_{i+1} - 4kx_{i+1}^2 - 4kx_{i+1} -k +4        \\
        &=  4(y_i+1) -4k(x_i)^2 -4k(x_i)-k+4                \\
        &=  (4y_i -4k(x_i)^2 -4k(x_i)- k + 4) + 4           \\
        &=  d_i + 4

\end{align}
\tag{2.4}

再令d_i'= d_i/4, [\frac{1}{2k},+\infty) 段总的可写成如下(初始点为(\frac{1}{2k},\frac{1}{4k}))

d_0 =   0.5 - k/4 \,,d_{i+1}=
\begin{cases}
d_i - 2kx_i - 2k +1 & d_i \geq 0 \\
d_i + 1             & d_i < 0 
\end{cases}

运行结果

y=0.5x^2,x\in[-100,100]

image-20220920154856913

y=-0.01x^2,x\in[-300,300]

image-20220920160020391

代码

#include"GLFW/glfw3.h"

#include <iostream>
using namespace std;

// 窗口大小
int WIDTH = 600;
int HEIGHT = 600;
// 原点位置
int Ox = 0;
int Oy = 0;

// 像素点类定义
struct PixelPoint {
    PixelPoint() { x = y = 0; }
    PixelPoint(int x, int y) :x(x), y(y) {}

    // x,y是相对于窗口左下角的非负整数,与一般的数学坐标轴类似
    int x, y;
};

// 在屏幕上对应坐标的点绘制一个像素
void drawPixel(int x, int y) {
    // openGL默认是在世界坐标中绘制,以画面中心为原点,坐标范围为[-1,1],所以需要转化一下坐标
    float transX = (float)(x + Ox) / (WIDTH / 2) - 1;
    float transY = (float)(y + Oy) / (HEIGHT / 2) - 1;

    // 绘制出的点为黑色
    glColor3f(0.0, 0.0, 0.0);

    glBegin(GL_POINTS);
    glVertex2f(transX, transY);
    glEnd();
}

// 绘制抛物线y=kx2 ,绘制范围为-maxX到+maxX
void drawArcBresenham(float k, int maxX) {
    // 上下翻转标记,翻转时为1
    int reverse =0 ;
    // 判断是否需要翻转
    if (k < 0) {
        reverse = 1;
        k = -k;
    }

    // 当前坐标
    int nowX;
    int nowY;
    // 偏差值(因为d在递推中于a有关，而a为浮点数，所以d也必须为浮点数）
    float d;

    // 分段绘制[0,1/2k]
    int range = (int)(1.0f / (2 * k));
    // 控制边界
    if (range > maxX)
        range = maxX;
    // 初始状态
    nowX = 0; nowY = 0;
    d = 0.5 - k;
    // 开始绘制
    while (nowX <= range) {
        //如果上下翻转就需要取反y
        if (reverse) {
            drawPixel(nowX, -nowY);
            drawPixel(-nowX, -nowY);
        }
        else {
            drawPixel(nowX, nowY);
            drawPixel(-nowX, nowY);
        }

        nowX++;
        if (d >= 0) {
            d += -2 * k * nowX - 3 * k;
        }
        else {
            nowY++;
            d += -2 * k * nowX - 3 * k + 1;
        }
    }

    // 分段绘制[1/2k,maxX]
    range = maxX;
    // 初始状态
    nowX = 1.0f / (2 * k); nowY = 1.0f / (4 * k);
    d = 0.5 - k / 4;
    // 开始绘制
    while (nowX <= range) {
        //如果上下翻转就需要取反y
        if (reverse) {
            drawPixel(nowX, -nowY);
            drawPixel(-nowX, -nowY);
        }
        else {
            drawPixel(nowX, nowY);
            drawPixel(-nowX, nowY);
        }

        nowY++;
        if (d >= 0) {
            nowX++;
            d += -2 * k * nowX - 2 * k + 1;
        }
        else {

            d += 1;
        }
    }
}
// 主要部分
void draw() {
    Ox = WIDTH / 2;
    Oy = HEIGHT / 2;
    drawArcBresenham(-0.005f,100);
}

int main() {
    // 初始化glfw
    if (!glfwInit()) {
        cout << "Failed to initialize GLFW" << endl;
        return -1;
    }

    // 创建窗口
    GLFWwindow* window = glfwCreateWindow(WIDTH, HEIGHT, "hello world", NULL, NULL);
    if (window == nullptr) {
        cout << "Failed to create window" << endl;
        return -1;
    }
    glfwMakeContextCurrent(window);

    // 循环渲染
    while (!glfwWindowShouldClose(window)) {
        // 清空窗口
        glClearColor(1.0f, 1.0f, 1.0f, 0.0f);
        glClear(GL_COLOR_BUFFER_BIT);

        // 开始绘制
        draw();

        //刷新缓冲并检测事件
        glfwSwapBuffers(window);
        glfwPollEvents();
    }

    //清空资源
    glfwTerminate();
    return 0;
}
计算机图形学
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
OpenGL#1 – 上手OpenGL

							
							

							
计算机图形学#0 – 基本概念