使用 Bresenham 线算法绘制线条

Question

我的计算机图形作业是仅使用绘制点的能力来实现 OpenGL 算法。

所以很明显，我需要让 drawLine() 工作，然后才能画出其他任何东西。 drawLine() 只能使用整数来完成。没有浮点数。

这是我被教导的。基本上，线条可以分为 4 种不同的类别，正陡、正浅、负陡和负浅。这是我应该画的图：

这是我的程序正在绘制的图片：

颜色是为我们完成的。给定顶点，我们需要使用 Bresenham 的线算法根据起点和终点绘制线。

这是我到目前为止所拥有的：

 int dx = end.x - start.x;
int dy = end.y - start.y;

//initialize varibales
int d;
int dL;
int dU;

if (dy > 0){
        if (dy > dx){
                //+steep
                d = dy - 2*dx;
                dL = -2*dx;
                dU = 2*dy - 2*dx;

                for (int x = start.x, y = start.y; y <= end.y; y++){
                        Vertex v(x,y);
                        drawPoint(v);

                        if (d >= 1){
                                d += dL;
                        }else{
                                x++;
                                d += dU;
                        }
                }
        } else {
                //+shallow
                d = 2*dy - dx;
                dL = 2*dy;
                dU = 2*dy - 2*dx;

                for (int x = start.x, y = start.y; x <= end.x; x++) {
                        Vertex v(x,y);
                        drawPoint(v);

                        // if choosing L, next y will stay the same, we only need
                        // to update d by dL
                        if (d <= 0) {
                                d += dL;
                        // otherwise choose U, y moves up 1
                        } else {
                                y++;
                                d += dU;
                        }
                }
        }
} else {
        if (-dy > dx){
                cout << "-steep\n";
                //-steep
                d = dy - 2*dx;
                //south
                dL = 2*dx;
                //southeast
                dU = 2*dy - 2*dx;

                for (int x = start.x, y = start.y; y >= end.y; --y){
                        Vertex v(x,y);
                        drawPoint(v);

                        //if choosing L, next x will stay the same, we only need
                        //to update d
                        if (d >= 1){
                                d -= dL;
                        } else {
                                x++;
                                d -= dU;
                        }
                }

        } else {
                cout << "-shallow\n";
                //-shallow
                d = 2*dy - dx;
                dL = 2*dy;
                dU = 2*dy - 2*dx;

                for (int x = start.x, y = start.y; x <= end.x; x++){
                        Vertex v(x,y);
                        drawPoint(v);

                        if (d >= 0){
                                d += dL;
                        } else {
                                --y;
                                d -= dU;
                        }
                }
        }
}

我知道我的错误会很愚蠢，但老实说，我无法弄清楚我做错了什么。为什么有些线条画错如上图？

原文由 ToastyMallows 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果有人想知道问题是什么，我仍然不知道它是什么。我最终做的是重构我的代码，以便 -shallow 和 -steep 分别使用与 +shallow 和 +steep 相同的算法。在调整 x,y 坐标（否定 x 或 y 坐标）后，当我去绘制它们时，我否定了我原来的否定，以便它绘制在正确的位置。

原文由 ToastyMallows 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我在 C++ 中实现了原始的 Bresenham 算法，并尝试尽可能多地优化（尤其是关于从内部循环中删除 IF）。

它绘制线性缓冲区而不是表面，就此而言，此实现几乎与 EFLA（极快线算法） 一样快（可能慢 5%）。

 #include <vector>
#include <math.h>
using namespace std;

vector<unsigned char> buffer;

int imageSide = 2048; // the width of the surface

struct Point2Di
{
    int x;
    int y;
    Point2Di(const int &x, const int &y): x(x), y(y){}
    Point2Di(){}

};

void drawLine(const Point2Di &p0, const Point2Di &p1)
{
    int dx = p1.x - p0.x;
    int dy = p1.y - p0.y;

    int dLong = abs(dx);
    int dShort = abs(dy);

    int offsetLong = dx > 0 ? 1 : -1;
    int offsetShort = dy > 0 ? imageSide : -imageSide;

    if(dLong < dShort)
    {
        swap(dShort, dLong);
        swap(offsetShort, offsetLong);
    }

    int error = 2 * dShort - dLong;
    int index = p0.y*imageSide + p0.x;
    const int offset[] = {offsetLong, offsetLong + offsetShort};
    const int abs_d[]  = {2*dShort, 2*(dShort - dLong)};
    for(int i = 0; i <= dLong; ++i)
    {
        buffer[index] = 255;  // or a call to your painting method
        const int errorIsTooBig = error >= 0;
        index += offset[errorIsTooBig];
        error += abs_d[errorIsTooBig];
    }
}

我正在使用的 EFLA 实现是：

 void drawLine(Point2Di p0,  Point2Di p1)
{
    bool yLonger=false;
    int shortLen=p1.y-p0.y;
    int longLen=p1.x-p0.x;
    if (abs(shortLen)>abs(longLen)) {
        swap(shortLen, longLen);
        yLonger=true;
    }
    int decInc = longLen==0 ?  decInc=0 : ((shortLen << 16) / longLen);

    if (yLonger) {
        p0.y*=imageSide;
        p1.y*=imageSide;
        if (longLen>0)
            for (int j=0x8000+(p0.x<<16);p0.y<=p1.y;p0.y+=imageSide, j+=decInc)
                buffer[p0.y + (j >> 16)] = 255;  // or a call to your painting method
        else
            for (int j=0x8000+(p0.x<<16);p0.y>=p1.y;p0.y-=imageSide, j-=decInc)
                buffer[p0.y + (j >> 16)] = 255;  // or a call to your painting method
    }
    else
    {
        if (longLen>0)
            for (int j=0x8000+(p0.y<<16);p0.x<=p1.x;++p0.x, j+=decInc)
                buffer[(j >> 16) * imageSide + p0.x] = 255;  // or a call to your painting method
        else
            for (int j=0x8000+(p0.y<<16);p0.x>=p1.x;--p0.x, j-=decInc)
                buffer[(j >> 16) * imageSide + p0.x] = 255;  // or a call to your painting method
    }
}

原文由 Adriel Jr 发布，翻译遵循 CC BY-SA 4.0 许可协议