为什么这个中点线算法不绘制垂直线(或接近垂直线的对角线)？

Question

我实现了我在网上找到的这个算法，它画出了水平线和一半的对角线。但是，当对角线经过"中间"标记变为垂直时，它不会更新y，只会绘制斜率较小的线。它确实一直画到x2，但画了一条倾斜到不同y2坐标的线。如果你试图画一条垂直线，什么也画不出来。有人能找到虫子吗？

void init()
{
    glClearColor(0.0, 0.0, 0.0, 0.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, 500.0, 0.0, 500.0);
}
void midPoint(int x1, int y1, int x2, int y2)
{
    if (x1 > x2)
    {
        midPoint(x2, y2, x1, y1);
        return;
    }
    int slope;
    int dx, dy, d, x, y;
    dx = x2 - x1;
    dy = y2 - y1;
    d = dx - 2 * dy;
    y = y1;
    if (dy < 0) {
        slope = -1;
        dy = -dy;
    }
    else {
        slope = 1;
    }
    for (x = x1; x < x2; x++) {
        glBegin(GL_POINTS);
        glVertex2f(x, y);
        if (d <= 0) {
            d += 2 * dx - 2 * dy;
            y += slope;
        }
        else {
            d += -2 * dy;
        }
        glEnd();
    }
}
void display()
{
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glColor3f(1.0, 0.0, 0.0);
    midPoint(10, 10, 110, 210);
    glColor3f(0.0, 1.0, 0.0);
    midPoint(10, 10, 210, 110);
    glColor3f(1.0, 1.0, 0.0);
    midPoint(210, 10, 10, 110);
    glFlush();
}
int main(int argc, char *argv[])
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowPosition(50, 50);
    glutInitWindowSize(500, 500);
    glutCreateWindow("Bresenham's midpoint line algorithm");
    init();
    glutDisplayFunc(display);
    glutMainLoop();
    return 0;
}

Answer 1

Bresenham的线条绘制算法无法绘制垂直线。要绘制垂直线，请使用DDA线条绘制算法。但DDA的问题是，它不会准确。

Answer 2

根据维基百科的定义，实现看起来像：

void midPoint(int x1, int y1, int x2, int y2)
{
    bool steep = abs(y2 - y1) > abs(x2 - x1);
    if(steep) {
        // swap x1 and y1
        int tmp = x1;
        x1 = y1;
        y1 = tmp;
        // swap x2 and y2
        tmp = x2;
        x2 = y2;
        y2 = tmp;
    }
    if(x1 > x2) {
        // swap x1 and x2
        int tmp = x1;
        x1 = x2;
        x2 = tmp;
        // swap y1 and y2
        tmp = y1;
        y1 = y2;
        y2 = tmp;
    }
    int dx, dy, error, ystep, y;
    dx = x2 - x1;
    dy = abs(y2 - y1);
    error = dx / 2;
    y = y1;
    if(y1 < y2)
        ystep = 1;
    else
        ystep = -1;
    glBegin(GL_POINTS);
    for (x = x1; x <= x2; x++) {
        if(steep)
            glVertex2f(y, x);
        else
            glVertex2f(x, y);
        error -= dy;
        if (error < 0) {
            y += ystep;
            error += dx;
        }
    }
    glEnd();
}

（无法测试，但已修复aschepler的评论）

Answer 3

我遇到了同样的问题，解决方案似乎很简单。while循环是正确渲染垂直线的关键。

下面的代码是我的Java图形项目中的代码。z坐标用于z缓冲区。

请注意，当采样沿着x轴时，循环运行dx次，当采样沿y轴时，它运行dy次

display.setColor(Color.BLACK);
dx=x2-x1;
dy=y2-y1;
if(dx<0)
    xinc=-1;
else
    xinc=1;
if(dy<0)
    yinc=-1;
else
    yinc=1;
zinc=z2-z1;

dx=Math.abs(dx);dy=Math.abs(dy);
if(dx>dy){
    zinc/=dx;
    dy=dy<<1;
    p=dy-dx;
    y2=dx;
    dx=dx<<1;
    display.drawPixel(x1, y1, z1);
    for(j=0;j<y2;j++){
        z1+=zinc;
        if(p>=0){
            p-=dx;
            y1+=yinc;
        }
        x1+=xinc;
        p+=dy;
        display.drawPixel(x1, y1, z1);
    }

}
else{
    zinc/=dy;
    dx=dx<<1;
    p=dx-dy;
    x2=dy;
    dy=dy<<1;
    display.drawPixel(x1, y1, z1);
    for(j=0;j<x2;j++){
        z1+=zinc;
        if(p>=0){
            p-=dy;
            x1+=xinc;
        }
        y1+=yinc;
        p+=dx;
        //System.out.println("Pixel : "+x1+" ,"+y1);
        display.drawPixel(x1, y1, z1);
    }
}