如何在二维数组中绘制"线"(模拟屏幕)

Question

我正在开发一个打印到位图的项目(更具体地说是一个RAW,但这对问题并不重要),但我正在使用二维数组进行编程.

我希望能够为a,b,x和y的任意值绘制从点(a,b)到点(x,y)的直线.我不需要任何像抗锯齿这样的花哨的东西; 在这一点上,最近邻居是好的.为了举个例子,让我们假设我有一个5x5的2d数组,就像这样:

00,10,20,30,40
01,11,21,31,41
02,12,22,32,42
03,13,23,33,43
04,14,24,34,44

现在,让我们假设我想在04和42之间绘制一条线.我想要一种可靠地想出这样的东西:

0,0,0,0,0
0,0,0,0,0
0,0,0,1,1
0,1,1,1,0
1,1,0,0,0

我敢肯定有人在想"哎呀,这个家伙是不是迟钝了？他在这里失败了吗？",但是,请你幽默我!

我在C++工作,但这应该是实际问题的次要问题.

Answer 1

Bresenham的线算法是您所需要的:

Bresenham线算法结果的插图.

Answer 2

就像Simucal说的那样,Bresenham是要走的路.这是一个天真的实现.

不完美的C代码,如果你想要线段上的厚度,你必须做一些魔术.此外,你应该沿着x遍历,而不是像我在这里一样.它更适合缓存.如果您想要抗锯齿,请搜索"Wu-lines".将位置中的分数用作渐变是一个聪明的技巧.

线条粗细的提示:如果顶点是逆时针顺序,则计算v1 - v0的标准化向量V(-y,x),如果顶点按顺时针顺序,则计算V(y,-x).然后您有四个点定义:v0,v0 + V*linewidth,v1和v1 + V*linewidth.通过沿边缘插值来栅格化四边形.但是如果你已经想要走得那么远,你可能会编写一个三角形光栅化器.

typedef struct Point 
{
    int x, y;
} Point;

typedef struct Color {
    unsigned char r,g,b;
} Color;

#define RGB(x) (x->r << 16) | (x->g << 8) | (x->b)

int DrawLinestrip(int width, int height, unsigned int* buffer,
    Color* color, Point* verts, int count)
{
    int i, x,y,xbegin, xdelta, ydelta, xdiff, ydiff, accum, sign;
    Point *p1, *p2;
    if(!verts || count < 2)
        return -1;

    for(i=1; i<count; ++i){
        if(verts[i].y > verts[i-1].y){ /* sort by y */
            p1 = &verts[i-1];
            p2 = &verts[i];
        } else {
            p1 = &verts[i];
            p2 = &verts[i-1];
        }

        xdelta = p2->x - p1->x;
        ydelta = p2->y - p1->y;
        accum = 0;
        sign = 0;

        if(!xdelta && !ydelta)
            continue;
        else if(!xdelta && ydelta){ /* Special case: straight vertical line */
            x = p1->x;
            for(y=p1->y; y<(p1->y + ydelta); ++y){
                buffer[x + y*width] = RGB(color);
            }
        }
        else if(xdelta && !ydelta){ /* Special case: straight horisontal line */
            y = p1->y;
            xbegin = (p1->x < p2->x ? p1->x : p2->x);
            for(x=xbegin; x<=xbegin+abs(xdelta); ++x){
                buffer[x + y*width] = RGB(color);
            }
        }
        else {
            xdiff = (xdelta << 16) / ydelta;
            ydiff = (ydelta << 16) / xdelta;

            if( abs(xdiff) > abs(ydiff) ){ /* horizontal-major */
                y = p1->y;
                if(xdelta < 0){ /* traversing negative x */
                    for(x=p1->x; x >= p2->x; --x){
                        buffer[x + y*width] = RGB(color);
                        accum += abs(ydiff);
                        while(accum >= (1<<16)){
                            ++y;
                            accum -= (1<<16);
                        }
                    }
                } else { /* traversing positive x */
                    for(x=p1->x; x <= p2->x; ++x){
                        buffer[x + y*width] = RGB(color);
                        accum += abs(ydiff);
                        while(accum >= (1<<16)){
                            ++y;
                            accum -= (1<<16);
                        }
                    }
                }
            } else if( abs(ydiff) > abs(xdiff) ){ /* vertical major */
                sign = (xdelta > 0 ? 1 : -1);
                x = p1->x;
                for(y=p1->y; y <= p2->y; ++y){
                    buffer[x + y*width] = RGB(color);
                    accum += abs(xdiff);
                    while(accum >= (1<<16)){
                        x += sign;
                        accum -= (1<<16);
                    }
                }            
            } else if( abs(ydiff) == abs(xdiff) ){ /* 45 degrees */
                sign = (xdelta > 0 ? 1 : -1);
                x = p1->x;
                for(y=p1->y; y <= p2->y; ++y){
                    buffer[x + y*width] = RGB(color);
                    x+= sign;
                }
            }
        }
    }
    return 0;
}