Zeichnen von Linien mit dem Bresenham-Line-Algorithmus

Finden Sie den kompletten code in C++ eine Linie ziehen mit Bresenham-Algorithmus an 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);
  }
 }
}

Implementiert habe ich den originalen Bresenham-Algorithmus in C++ und versucht zu optimieren, so viel wie ich konnte (vor allem in Bezug auf das entfernen der, WENN aus der inneren Schleife).

Zieht es in einen linearen Puffer anstelle von einer Oberfläche, und für diese Sache, diese Umsetzung war fast so schnell wie EFLA (Extrem Schnell-Line-Algorithmus) (vielleicht 5% langsamer).

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

Des EFLA-Implementierung, die ich verwende, ist:

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