Drawing lines with Bresenham's Line Algorithm

问题:

My computer graphics homework is to implement OpenGL algorithms using only the ability to draw points.

So obviously I need to get drawLine() to work before I can draw anything else. drawLine() has to be done using integers only. No floating point.

This is what I was taught. Basically, lines can be broken up into 4 different categories, positive steep, positive shallow, negative steep and negative shallow. This is the picture I am supposed to draw:

and this is the picture my program is drawing:

The colors are done for us. We are given vertices and we need to use Bresenham's Line algorithm to draw the lines based on the start and end points.

This is what I have so far:

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

I know my error is going to be something silly, but I honestly cannot figure out what I am doing wrong. Why are some of the lines drawn incorrectly as shown above?

回答1:

You can find the complete code in C++ to draw a line using Bresenham Algorithm at http://www.etechplanet.com/codesnippets/computer-graphics-draw-a-line-using-bresenham-algorithm.aspx:

/*BRESENHAAM ALGORITHM FOR LINE DRAWING*/
#include<iostream.h>
#include<graphics.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<dos.h>
void bhm_line(int,int,int,int,int);
void main()
{
 int ghdriver=DETECT,ghmode,errorcode,x1,x2,y1,y2;
 initgraph(&ghdriver,&ghmode,"..\\bgi");
 errorcode = graphresult();
 if(errorcode !=grOk)
 {
  cout<<"Graphics error:%s\n"<<grapherrormsg(errorcode);
  cout<<"Press any key to halt:";
  getch();
  exit(1);
 }
 clrscr();
 cout<<"Enter the coordinates (x1,y1): ";
 cin>>x1>>y1;
 cout<<"Enter the coordinates (x2,y2): ";
 cin>>x2>>y2;
 bhm_line(x1,y1,x2,y2,1);
 getch();
}
void bhm_line(int x1,int y1,int x2,int y2,int c)
{
 int x,y,dx,dy,dx1,dy1,px,py,xe,ye,i;
 dx=x2-x1;
 dy=y2-y1;
 dx1=fabs(dx);
 dy1=fabs(dy);
 px=2*dy1-dx1;
 py=2*dx1-dy1;
 if(dy1<=dx1)
 {
  if(dx>=0)
  {
   x=x1;
   y=y1;
   xe=x2;
  }
  else
  {
   x=x2;
   y=y2;
   xe=x1;
  }
  putpixel(x,y,c);
  for(i=0;x<xe;i++)
  {
   x=x+1;
   if(px<0)
   {
    px=px+2*dy1;
   }
   else
   {
    if((dx<0 && dy<0) || (dx>0 && dy>0))
    {
     y=y+1;
    }
    else
    {
     y=y-1;
    }
    px=px+2*(dy1-dx1);
   }
   delay(0);
   putpixel(x,y,c);
  }
 }
 else
 {
  if(dy>=0)
  {
   x=x1;
   y=y1;
   ye=y2;
  }
  else
  {
   x=x2;
   y=y2;
   ye=y1;
  }
  putpixel(x,y,c);
  for(i=0;y<ye;i++)
  {
   y=y+1;
   if(py<=0)
   {
    py=py+2*dx1;
   }
   else
   {
    if((dx<0 && dy<0) || (dx>0 && dy>0))
    {
     x=x+1;
    }
    else
    {
     x=x-1;
    }
    py=py+2*(dx1-dy1);
   }
   delay(0);
   putpixel(x,y,c);
  }
 }
}

回答2:

In case anyone was wondering what the problem was, I still don't know what it was. What I ended up doing was re-factored my code so that the -shallow and -steep used the same algorithm as +shallow and +steep, respectively. After adjusting the x,y coordinates (negating the x or y coordinate), when I went to plot them I negated my original negation so that it plotted in the right spot.

回答3:

I implemented the original Bresenham's algorithm in C++ and tried to optimize as much as I could (especially regarding removing the IF from the interior loop).

It draws in a linear buffer instead of a surface, and for this matter, this implementation was almost as fast as EFLA (Extremely Fast Line Algorithm) (maybe 5% slower).

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

The EFLA implementation that I am using is:

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