Primitivas Gráficas - Algoritmo BRESENHAM para Líneas



En este post explicaré el algoritmo para lineas BRESENHAM en 2D:

DEFINICIÓN

  • Algoritmo preciso y efectivo para la generación de líneas de rastreo.
  • Con el apoyo de un parámetro de decisión, elige de entre dos pixeles el que más se acerca a la trayectoria de la recta.
  • Dado un punto (xk, yk), se predice el punto (xk+1, yk+1), teniendo en cuenta el parámetro de decisión pk.

DEMOSTRACIÓN

Consideraciones previas

Una recta es la representación de un lugar geométrico definido por:
y = mx + b ... (1)

Dicho lugar geométrico tiene extremos (x0, y0) y (xf, yf):
m=(yf y0)/(xf x0)
m=∆y/∆x ...(2)
De donde:
y = (∆y/∆x)x + b ...(3)

    0<m<1

    Tenemos:
    (xk, yk)
    Los posibles puntos a pintar serian:
    (xk + 1, yk) o (xk + 1, yk + 1)
    Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
    d1 = y - yk = m(xk + 1) + b - yk
    d2 = (yk+1) - y = yk + 1 - m(xk + 1) - b
    d1 - d2 = 2m(xk + 1) - 2yk + 2b - 1

    El parámetro de decisión pk indica el paso k en el algoritmo.

    pk =∆x(d1 - d2)

    pk =∆x(d1 - d2)
    pk =∆x(2m(xk + 1) - 2yk + 2b - 1)

    pk =∆x(2m(xk + 1) - 2yk + 2b - 1)
    pk =∆x(2(∆y/∆x)(xk + 1) - 2yk + 2b - 1)

    pk = 2∆y(xk + 1) - 2∆xyk + 2∆xb - ∆x
    pk = 2∆yxk + 2∆y - 2∆xyk + 2∆xb - ∆x

    pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb - ∆x
    pk = 2∆yxk - 2∆xyk + C

    pk = 2∆yxk - 2∆xyk + C
    Donde:
    • pk tiene el signo de d1 - d2
    • xf > x0
    • C=2∆y+2∆xb-∆x (Independiente del pixel)
    Si d1 < d2
    • yk está más cerca de la trayectoria de la recta
    • pk  es negativo
    Caso contrario
    • yk+1 está más cerca de la trayectoria de la recta
    • pk  es positivo
    En el paso k+1, el parámetro de decisión se evalúa con base en la ecuación anterior:
    pk+1 = 2∆yxk+1 - 2∆xyk+1 + C
    Al sustraer pk:
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
    Si xk+1 = xk + 1
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
    pk+1 - pk = 2∆y(xk + 1 - xk) - 2∆x(yk+1 - yk)
    pk+1 - pk = 2∆y - 2∆x(yk+1 - yk)
    pk+1 pk 2∆y - 2∆x(yk+1 - yk)
    De donde:
    • Si yk+1 = yk + 1
    pk+1 pk 2∆y - 2∆x
    • Si yk+1 = yk
    pk+1 pk 2∆y
    Esto depende del parámetro p0:
    pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb - ∆x
    p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb - ∆x

    De la ecuación 3 despejo b:
    y0 = (∆y/∆x)x0 + b
    b = y0 - (∆y/∆x)x0   ...(4)
    Reemplazo en p0:
    p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb - ∆x
    p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆x(y0 - (∆y/∆x)x0) - ∆x
    Resolviendo la ecuación:
    p0 = 2∆y ∆x
    Finalmente, para este caso tenemos:
    p0 = 2∆y ∆x
    Si pk < 0
    • Trazar (xk+1, yk)
    • pk+1 pk 2∆y
    Caso contrario
    • Trazar (xk+1, yk + 1 )
    • pk+1 pk 2∆y - 2∆x

    -1<m<0

    Tenemos:
    (xk, yk)
    Los posibles puntos a pintar serian:
    (xk + 1, yk) o (xk + 1, yk - 1)
    Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
    d1 = y - yk+1 = m(xk + 1) + b - (yk - 1) = m(xk + 1) + b - yk + 1
    d2 = yk - y = yk - m(xk + 1) - b
    d1 - d2 = 2m(xk + 1) - 2yk + 2b + 1

    El parámetro de decisión pk indica el paso k en el algoritmo.

    pk =∆x(d1 - d2)

    pk =∆x(d1 - d2)
    pk =∆x(2m(xk + 1) - 2yk + 2b + 1)

    pk =∆x(2m(xk + 1) - 2yk + 2b + 1)
    pk =∆x(2(∆y/∆x)(xk + 1) - 2yk + 2b + 1)

    pk = 2∆y(xk + 1) - 2∆xyk + 2∆xb + ∆x
    pk = 2∆yxk + 2∆y - 2∆xyk + 2∆xb + ∆x

    pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb + ∆x
    pk = 2∆yxk - 2∆xyk + C

    pk = 2∆yxk - 2∆xyk + C
    Donde:
    • pk tiene el signo de d1 - d2
    • xf > x0
    • C=2∆y+2∆xb+∆x (Independiente del pixel)
    Si d1 < d2
    • yk - 1 está más cerca de la trayectoria de la recta
    • pk  es negativo
    Caso contrario
    • yk está más cerca de la trayectoria de la recta
    • pk  es positivo
    En el paso k+1, el parámetro de decisión se evalúa con base en la ecuación anterior:
    pk+1 = 2∆yxk+1 - 2∆xyk+1 + C
    Al sustraer pk:
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
    Si xk+1 = xk + 1
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
    pk+1 - pk = 2∆y(xk + 1 - xk) - 2∆x(yk+1 - yk)
    pk+1 - pk = 2∆y - 2∆x(yk+1 - yk)
    pk+1 pk 2∆y - 2∆x(yk+1 - yk)
    De donde:
    • Si yk+1 = yk - 1
    pk+1 pk 2∆y + 2∆x
    • Si yk+1 = yk
    pk+1 pk 2∆y
    Esto depende del parámetro p0:
    pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb + ∆x
    p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb + ∆x

    Reemplazo en p0 por la ecuación (4):
    p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb + ∆x
    p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆x(y0 - (∆y/∆x)x0) + ∆x
    Resolviendo la ecuación:
    p0 = 2∆y + ∆x
    Finalmente, para este caso tenemos:
    p0 = 2∆y + ∆x
    Si pk < 0
    • Trazar (xk+1, yk - 1)
    • pk+1 pk 2∆y + 2∆x
    Caso contrario
    • Trazar (xk+1, yk)
    • pk+1 pk 2∆y

    1<m

    Tenemos:
    (xk, yk)
    Los posibles puntos a pintar serian:
    (xk, yk + 1) o (xk + 1, yk + 1)
    Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
    d1 = x - xk = (yk + 1 - b)/m - xk
    d2 = xk+1 - x = xk + 1 - (yk + 1 - b)/m
    d1 - d2 = 2(yk + 1 - b)/m - 2xk - 1

    El parámetro de decisión pk indica el paso k en el algoritmo.

    pk =∆y(d1 - d2)

    pk =∆y(d1 - d2)
    pk =∆y(2(yk + 1 - b)/m - 2xk - 1)

    pk =∆y(2(yk + 1 - b)/m - 2xk - 1)
    pk =∆y(2(yk + 1 - b)/(∆y/∆x) - 2xk - 1)
    pk =∆y(2∆x(yk + 1 - b)/∆y - 2xk - 1)

    pk =2∆x(yk + 1 - b) - 2∆yxk - ∆y
    pk =2∆xyk + 2∆x - 2∆xb - 2∆yxk - ∆y
    pk =2∆xyk - 2∆yxk 2∆x - 2∆xb ∆y

    pk =2∆xyk - 2∆yxk 2∆x - 2∆xb ∆y
    pk =2∆xyk - 2∆yxk C

    pk =2∆xyk - 2∆yxk C
    Donde:
    • pk tiene el signo de d1 - d2
    • yf > y0
    • C=2∆x - 2∆xb ∆y (Independiente del pixel)
    Si d1 < d2
    • xk está más cerca de la trayectoria de la recta
    • pk  es negativo
    Caso contrario
    • xk+1 está más cerca de la trayectoria de la recta
    • pk  es positivo
    En el paso k+1, el parámetro de decisión se evalúa con base en la ecuación anterior:
    pk+1 =2∆xyk+1 - 2∆yxk+1 C
    Al sustraer pk:
    pk+1 - pk = 2∆x(yk+1 - yk) - 2∆y(xk+1 - xk)
    Si yk+1 = yk + 1
    pk+1 - pk = 2∆x(yk+1 - yk) - 2∆y(xk+1 - xk)
    pk+1 - pk = 2∆x(yk + 1 - yk) - 2∆y(xk+1 - xk)
    pk+1 - pk = 2∆x - 2∆y(xk+1 - xk)
    pk+1 = pk + 2∆x - 2∆y(xk+1 - xk)
    De donde:
    • Si xk+1 = xk + 1
    pk+1 = pk + 2∆x - 2∆y
    • Si xk+1 = xk
    pk+1 pk 2∆x
    Esto depende del parámetro p0:
    pk =2∆xyk - 2∆yxk 2∆x - 2∆xb ∆y
    p0 =2∆xy0 - 2∆yx0 2∆x - 2∆xb ∆y

    Reemplazo en p0 por la ecuación (4):
    p0 =2∆xy0 - 2∆yx0 2∆x - 2∆xb ∆y
    p0 =2∆xy0 - 2∆yx0 2∆x - 2∆x(y0 - (∆y/∆x)x0) ∆y
    Resolviendo la ecuación:
    p0 = 2∆x  - ∆y
    Finalmente, para este caso tenemos:
    p0 = 2∆x  - ∆y
    Si pk < 0
    • Trazar (xk, yk + 1)
    • pk+1 pk 2∆x
    Caso contrario
    • Trazar (xk+1, yk + 1)
    • pk+1 pk 2∆x - 2∆y

    m<-1

    Tenemos:
    (xk, yk)
    Los posibles puntos a pintar serian:
    (xk, yk + 1) o (xk - 1, yk + 1)
    Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
    d1 = xk - x = xk - (yk + 1 - b)/m
    d2 = x - xk+1 = (yk + 1 - b)/m - xk + 1
    d1 - d2 = 2xk - 2(yk + 1 - b)/m + 1

    El parámetro de decisión pk indica el paso k en el algoritmo.

    pk =∆y(d1 - d2)

    pk =∆y(d1 - d2)
    pk =∆y(2xk - 2(yk + 1 - b)/m +1)

    pk =∆y(2xk - 2(yk + 1 - b)/m +1)
    pk =∆y(2xk - 2(yk + 1 - b)/(∆y/∆x) +1)
    pk =2∆yxk - 2∆y∆x(yk + 1 - b)/∆y + ∆y



    pk =2∆yxk - 2∆x(yk + 1 - b) + ∆y
    pk =2∆yxk - 2∆xyk - 2∆x + 2∆xb + ∆y

    pk =2∆yxk - 2∆xyk  - 2∆x + 2∆xb + ∆y
    pk =2∆yxk - 2∆xyk  C

    pk =2∆yxk - 2∆xyk  C
    Donde:
    • pk tiene el signo de d1 - d2
    • yf > y0
    • C= - 2∆x + 2∆xb + ∆y(Independiente del pixel)
    Si d1 < d2
    • xk está más cerca de la trayectoria de la recta
    • pk  es negativo
    Caso contrario
    • xk+1 está más cerca de la trayectoria de la recta
    • pk  es positivo
    En el paso k+1, el parámetro de decisión se evalúa con base en la ecuación anterior:
    pk+1 =2∆yxk+1 2∆xyk+1 C
    Al sustraer pk:
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
    Si yk+1 = yk + 1
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk + 1 - yk)
    pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x
    pk+1 = pk + 2∆y(xk+1 - xk) - 2∆x
    De donde:
    • Si xk+1 = xk
    pk+1 = pk - 2∆x
    • Si xk+1 = xk - 1
    pk+1 = pk - 2∆y - 2∆x
    Esto depende del parámetro p0:
    pk =2∆yxk - 2∆xyk - 2∆x + 2∆xb + ∆y
    p0 =2∆yx0 - 2∆xy0 - 2∆x + 2∆xb + ∆y

    Reemplazo en p0 por la ecuación (4):


    p0 =2∆yx0 - 2∆xy0 - 2∆x + 2∆xb + ∆y

    p0 =2∆yx0 - 2∆xy0 - 2∆x + 2∆x(y0 - (∆y/∆x)x0) + ∆y
    Resolviendo la ecuación:
    p0 = - 2∆x + ∆y
    Finalmente, para este caso tenemos:
    p0 = -2∆x + ∆y
    Si pk < 0
    • Trazar (xk, yk + 1)
    • pk+1 pk - 2∆x
    Caso contrario
    • Trazar (xk-1, yk + 1)
    • pk+1 pk 2∆x - 2∆y

    Casos Especiales

    m=0


    • Tenemos: 
    (xk, yk) 
    • El siguiente punto a pintar es: 
    (xk + 1, yk)
    • Siempre que:
    xf > x0

    m=1


    • Tenemos: 
    (xk, yk) 
    • El siguiente punto a pintar es: 
    (xk + 1, yk + 1)
    • Siempre que:
    xf > x0

    m=-1

    • Tenemos: 
    (xk, yk) 
    • El siguiente punto a pintar es: 
    (xk + 1, yk - 1)
    • Siempre que:
    xf > x0

    m= ∞

    • Tenemos: 
    (xk, yk) 
    • El siguiente punto a pintar es: 
    (xk , yk + 1)
    • Siempre que:
    yf > y0


    ECUACIONES

    CREANDO CÓDIGO

    #include <math.h>
    #include <GL/glut.h>
    #include <windows.h>
    using namespace std;
    void initialize() {
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowSize (680, 680);
    glutInitWindowPosition (30,30);
    glutCreateWindow ("LINEA BRESENHAM");
    glClearColor(1.0,1.0,1.0,1.0);
    glMatrixMode(GL_PROJECTION);
    gluOrtho2D(-60,60,-60,60);
    }
    void rectareferencial(GLint x0,GLint y0,GLint xf,GLint yf)
    {
    /* ----RECTA REFERENCIA---- */
    glLineWidth(0.1);
    glBegin(GL_LINES);
    glColor3f(0.2, 1, 0.2);
    glVertex2f(x0,y0);
    glVertex2f(xf,yf);
    glEnd();
    glFlush();
    }
    void ejecoordenadas()
    {
    glLineWidth(0.1);
    glBegin(GL_LINES);
    glColor3f( 1, 0, 0);
    /*eje y*/
    glVertex3f(0,60,-1);
    glVertex3f(0,-60,-1);
    /*eje x*/
    glVertex3f(60,0,0);
    glVertex3f(-60,0,0);
    glEnd();
    }
    void cudriculafondo()
    {
    for(float i=-59.5;i<60;i+=1)
    {
    glLineWidth(1);
    glBegin(GL_LINES);
    glColor3f( 0, 255, 255);
    glVertex3f(i,100,-1);
    glVertex3f(i,-100,-1);
    glVertex3f(100,i,-1);
    glVertex3f(-100,i,-1);
    glEnd();
    }
    }
    void setPixel(GLint x, GLint y)
    {
    glPointSize(5);
    glBegin(GL_POINTS);
    glVertex2i(x,y);
    glEnd();
    glFlush();
    }
    void lineaBresenham(GLint x0, GLint y0, GLint xf, GLint yf)
    {
    GLint dx = xf - x0;
    GLint dy = yf - y0;
    GLint contador;
    GLfloat m = (float)dy/dx;
    GLint p0,pk,a,b;
    GLint e1;
    GLint e2;
    GLint x,y;
    GLboolean band;
    if(m>=0 && m<1)
    {
    if(x0 > xf)
    {//invertir valores
    a=x0;
    b=y0;
    x0=xf;
    y0=yf;
    xf=a;
    yf=b;
    dx = xf - x0;
    dy = yf - y0;
    }
    p0 = 2*dy - dx;
    x = x0;
    y = y0;
    pk=p0;
    e1 = 2 * dy;
    e2 = 2 * ( dy - dx );
    band = 0 ;
    contador = x0;
    }
    else
    {
    if(m>=1)
    {
    if(x0 > xf)
    {
    //invertir valores
    a=x0;
    b=y0;
    x0=xf;
    y0=yf;
    xf=a;
    yf=b;
    dx = xf - x0;
    dy = yf - y0;
    }
    p0 = 2*dx - dy;
    x = x0;
    y = y0;
    pk=p0;
    e1 = 2 * dx;
    e2 = 2 * ( dx - dy );
    contador = y0;
    band = 1 ;
    }
    else
    {
    if(m>-1 && m<0)
    {
    dx = x0 - xf;
    dy = yf - y0;
    if(x0 < xf)
    {//invertir valores
    a=x0;
    b=y0;
    x0=xf;
    y0=yf;
    xf=a;
    yf=b;
    dx = x0 - xf;
    dy = yf - y0;
    }
    p0 = 2*dy - dx;
    x = x0;
    y = y0;
    pk=p0;
    e1 = 2 * dy;
    e2 = 2 * ( dy - dx );
    band = 2 ;
    contador = x0;
    }
    else
    {
    if(m<-1)
    {
    dx = x0 - xf;
    dy = yf - y0;
    if(x0 < xf)
    {
    //invertir valores
    a=x0;
    b=y0;
    x0=xf;
    y0=yf;
    xf=a;
    yf=b;
    dx = x0 - xf;
    dy = yf - y0;
    }
    p0 = 2*dx - dy;
    x = x0;
    y = y0;
    pk=p0;
    e1 = 2 * dx;
    e2 = 2 * ( dx - dy );
    band = 3 ;
    contador = y0;
    }
    }
    }
    }
    setPixel(x,y);
    //cout<<x<<" , "<<y<<"\n";
    if(band==1)
    {
    while(contador<yf)
    {
    y++;
    if(pk<0)
    {
    pk += e1;
    }
    else
    {
    pk += e2;
    x++;
    }
    contador++;
    setPixel(x,y);
    //cout<<x<<" , "<<y<<"\n";
    }
    }
    else
    {
    if(band==0)
    {
    //cout<<"hola";
    while(contador<xf)
    {
    x++;
    if(pk<0)
    {
    pk += e1;
    }
    else
    {
    pk += e2;
    y++;
    }
    contador++;
    setPixel(x,y);
    //cout<<x<<" , "<<y<<"\n";
    }
    }
    else
    {
    if(band==2)
    {
    while(contador>xf)
    {
    x--;
    if(pk<0)
    {
    pk += e1;
    }
    else
    {
    pk += e2;
    y++;
    }
    contador--;
    setPixel(x,y);
    //cout<<x<<" , "<<y<<"\n";
    }
    }
    else
    {
    if(band==3)
    {
    while(contador<yf)
    {
    y++;
    if(pk<0)
    {
    pk += e1;
    }
    else
    {
    pk += e2;
    x--;
    }
    contador++;
    setPixel(x,y);
    //cout<<x<<" , "<<y<<"\n";
    }
    }
    }
    }
    }
    }
    void drawMyLine(void)
    {
    glClear(GL_COLOR_BUFFER_BIT);
    // MODIFICAR PUNTOS
    GLint x0 = 2;
    GLint y0 = 8;
    GLint xf = -32;
    GLint yf = -34;
    cudriculafondo();
    ejecoordenadas();
    glColor3f(1.0,0.0,0.0);
    lineaBresenham(x0,y0,xf,yf);
    glColor3f(0.0,0.0,1.0);
    rectareferencial(x0,y0,xf,yf);
    }
    int main (int argc, char **argv) {
    glutInit (&argc, argv);
    initialize();
    glutDisplayFunc(drawMyLine);
    glutMainLoop();
    return 0;
    }

    RELACIONADOS

    Comentarios

    Popular Posts

    Sistemas Distribuidos - Tolerancia a fallos

    Crear Autómata Finito Determinista desde una Expresión Regular

    Instalar OpenGL en Linux