CODEWITHSUNDEEP
c++openglglut
The Rationalist
The Rationalist

Reputation: 753

Why doesn't this midpoint line algorithm draw vertical lines (or diagonals that approach the vertical)?

I implemented this algorithm I found online, and it draws horizontal lines and half of all diagonals just fine. But as the diagonal line passes the "halfway" mark to becoming vertical, it doesn't update y and only draws the line with a smaller slope. It does draw it all the way to x2, but draws a line sloped to a different y2 coordinate. And if you try to draw a vertical line, nothing is drawn. Can anyone find the bug?

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;
}

Upvotes: 4

Views: 8091

Answers (3)

Sudip Bhattarai
Sudip Bhattarai

Reputation: 1154

I was getting the same problem and solution seems quiet simple.The while loop is the key to get the vertical line rendered correctly.

The code below is code from my graphics project with Java. z coordinate is for z buffer.

Notice that the loop runs dx times when sampling is along x-axis and it runs dy times when sampling is along y-axis

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);
    }
}

Upvotes: 0

Rini Joymon
Rini Joymon

Reputation: 31

Bresenham's line drawing algorithm can't plot vertical lines. To plot vertical line use DDA line drawing algorithm. But the problem with DDA is that, it won't be accurate.

Upvotes: 3

Daniel
Daniel

Reputation: 1527

Following Wikipedia's definition the implementation would look like:

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();
}

(couldn't test yet but fixed in regard to aschepler's comment)

Upvotes: 0

Related Questions