Dibujando líneas con el algoritmo de línea de Bresenham

Question

Mi tarea de gráficos por computadora es implementar algoritmos OpenGL utilizando solo la capacidad de dibujar puntos.

Así que obviamente necesito hacer que drawLine() funcione antes de que pueda dibujar algo más. drawLine() tiene que hacerse usando enteros solamente. Sin punto flotante

Esto es lo que me enseñaron. Básicamente, las líneas se pueden dividir en 4 categorías diferentes, empinadas positivas, positivas superficiales, negativas empinadas y negativas superficiales. Esta es la imagen que debo dibujar:

y esta es la imagen de mi programa está llegando:

Los colores se hacen por nosotros. Nos dan vértices y necesitamos usar el algoritmo Bresenham's Line para dibujar las líneas basadas en los puntos de inicio y final.

Esto es lo que tengo hasta ahora:

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

Sé que mi error va a ser algo tonto, pero sinceramente no puedo averiguar lo que estoy haciendo mal. ¿Por qué algunas de las líneas se dibujan incorrectamente como se muestra arriba?

Answer 1

Por si alguien se preguntaba cuál era el problema, todavía no sé de qué se trataba. Lo que terminé haciendo fue volver a factorizar mi código para que el -shallow y -steep usaran el mismo algoritmo que + shallow y + steep, respectivamente. Después de ajustar las coordenadas x, y (anulando la coordenada xoy), cuando fui a trazarlas negué mi negación original para que se trazara en el lugar correcto.

Answer 2

Puede encontrar el código completo en C++ para dibujar una línea usando Bresenham Algoritmo en el 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); 
    } 
} 
}