Primitivas Gráficas - Algoritmo BRESENHAM para Líneas

Por


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;
    }
    view raw BRESENHAMline.cpp hosted with ❤ by GitHub

    RELACIONADOS

    Comentarios

    Publicar un comentario

    Popular Posts

    Sistemas Distribuidos - Tolerancia a fallos

    Por
    Imagen
    INTRODUCCIÓN A LA TOLERANCIA A FALLOS INTRODUCCIÓN Una característica donde los sistemas distribuidos difieren de un sistema de una sola máquina es la noción de fallo parcial . En un sistema distribuido una falla puede afectar la operación de algunos componentes y otros no verse afectados. En un sistema no distribuido, una falla afecta todos los componentes. Un objetivo importante en el diseño de Sistemas Distribuidos es construirlos de manera que puedan recuperarse de fallas parciales sin que se afecte. Siempre que ocurra una falla, el Sistema Distribuido debe continuar operando de modo aceptable mientras se soluciona, es decir, tolerar las fallas . CONCEPTOS BÁSICOS Ser tolerante a fallas está fuertemente relacionado a los sistemas fiables, y ello involucra lo siguiente: DISPONIBILIDAD Propiedad por la cual, una sistema está listo para ser utilizado inmediatamente . Probabilidad de que un sistema esté operando correctamente en cualquier momento dado y disponible a ...
    Ver mas »

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

    Por
    Imagen
    En este post explicaré paso a paso como crear un autómata finito determinista a partir de una expresión regular. Primero necesitaremos esta tabla para el cálculo de la primerpos y la ultimapos: Ejemplo: De la expresión regular crear su autómata finito determinista: a(bc*)*+a primero se concatena el símbolo # al final de la expresión regular como delimitador. a(bc*)*+a# Ahora al trabajar el árbol sintáctico se debe tener en cuenta la prioridad de los operadores: Paréntesis cerradura de klein (*), cerradura positiva (+) concatenación (.) disyunción (|) Según estas prioridades se procede a crear el árbol sintáctico de la expresión regular. y se enumeran los nodos hojas (nodos que no tienen hijos). Cálculo de anulables, primerapos y ultimapos usando la tabla anterior: pp: primerapos up: ultimapos Ahora hallamos la siguientepos(i): Si n es un nodo concatenación (.) con hijo izquierdo c1 e hijo derecho c2, e i es una posición dentro de la ...
    Ver mas »

    Instalar OpenGL en Linux

    Por
    Imagen
    Comando para instalar freeglut en linux: sudo apt-get install g++ freeglut3 freeglut3-dev Si la terminal pide alguna confirmación, escriben 'Y' si su sistema operativo se encuentra en inglés o 'S' si su sistema operativo está en español. Consideré Zinjai como IDE por su simplicidad y es más fácil de entender, tanto en Windows como en Linux. Instalación de Zinjai Video de explicación: Enlaces relacionados Computaación Gráfica Instalación
    Ver mas »