Resumen

Algoritmos DDa y Bresenham

ALGORITMO BRESENHAM

#include "stdafx.h"
#define BLACK 0
#include <GL/glut.h>
#include <stdio.h>

void draw_pixel(int ix, int iy, int value)
{
glBegin(GL_POINTS);
glVertex2i( ix, iy);
glEnd();
}

void bres(int x1,int y1,int x2,int y2){ //algoritmo Bresenham
int dx, dy, i, e;
int incx, incy, inc1, inc2;
int x,y;
dx = x2 - x1;
dy = y2 - y1;
if(dx < 0) dx = -dx;
if(dy < 0) dy = -dy;
incx = 1;
if(x2 < x1) incx = -1;
incy = 1;
if(y2 < y1) incy = -1;
x=x1;
y=y1;
if(dx > dy) {
draw_pixel(x,y, BLACK);
e = 2*dy - dx;
inc1 = 2*( dy -dx);
inc2 = 2*dy;
for(i = 0; i < dx; i++)
{
if(e >= 0){
y += incy;
e += inc1;
} else
e += inc2;
x += incx;
draw_pixel(x,y, BLACK);
}

}
else {
draw_pixel(x,y, BLACK);
e = 2*dx - dy;
inc1 = 2*( dx - dy);
inc2 = 2*dx;
for(i = 0; i < dy; i++){
if(e >= 0) {
x += incx;
e += inc1;
}
else e += inc2;
y += incy;
draw_pixel(x,y, BLACK);
}
}

}

void display()
{
glClear(GL_COLOR_BUFFER_BIT);
bres(200, 200, 100, 100);
glFlush();
}
void myinit()
{

glClearColor(1.0, 1.0, 1.0, 1.0);//color
glColor3f(0.5, 0.3, 0.2);
glPointSize(1.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0, 300.0, 0.0, 300.0);

}

void main(int argc, char** argv)
{ // Inicializacion GLUT estándar
glutInit(&argc,argv);
glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);
glutInitWindowSize(400,400); //tamaño ventana
glutInitWindowPosition(0,0); /* coloca la ventana de despliegue en esq. sup. izq */
glutCreateWindow("Algoritmo Bresenham"); //titulo
glutDisplayFunc(display); //se llama al metodo Display
myinit(); //estableciendo tributoas
glutMainLoop();//ciclo de evento
}


ALGORITMO DDA

 

#include "stdafx.h"

#include "stdafx.h"

#include <GL/glut.h>

#include <stdlib.h>

#include <math.h>

 

typedef struct {

       float x, y;

}

Punto;

Punto vertices[2];

int numPuntos;

int screen[640][480];

 

void inicializar (void);

void redimensiona (int alto, int ancho);

void dibuja (void);

void teclado (unsigned char key, int cx, int cy);

void raton (int boton, int estado, int cx, int cy);

void ddaAlgorithm(int, int, int, int);

void limpiaScreen();

int my_round(float);

 

int main(int argc, char* argv[]) {

       glutInit(&argc, argv);

    glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);

    glutInitWindowSize (640, 480);

    glutInitWindowPosition (100, 105);

    glutCreateWindow ("Algoitmo DDA");

    inicializar();

       glutDisplayFunc(dibuja);

       glutReshapeFunc(redimensiona);

       glutKeyboardFunc(teclado);

       glutMouseFunc(raton);

    glutMainLoop();

    return 0;

}

void inicializar () {

       glClearColor(0.0f, 0.0f, 0.0f, 0.0f);

       numPuntos = 0;

}

 

void redimensiona (int ancho, int alto) {

 

    glViewport(0, 0, ancho, alto);

    glMatrixMode(GL_PROJECTION);

    glLoadIdentity();

    gluOrtho2D(0.0, (double)ancho, 0.0, (double)alto);

}

 

void teclado (unsigned char key, int cx, int cy) {

 

       switch (key) {

       case 27:

             exit(0);

             break;

             default: break;

       }

       glutPostRedisplay();

}

void raton (int boton, int estado, int cx, int cy) {

       if (boton == GLUT_LEFT_BUTTON && estado == GLUT_DOWN) {

             if (numPuntos == 2) {

                    numPuntos = 0;

             }

             vertices[numPuntos].x = cx;

             vertices[numPuntos].y = 480 - cy;

             numPuntos++;

       }

       glutPostRedisplay();

}

 

void dibuja (void) {

       int i, j;

       glClear(GL_COLOR_BUFFER_BIT);

       glMatrixMode(GL_MODELVIEW);

       glLoadIdentity();

       limpiaScreen();

       if (numPuntos == 2) {

             ddaAlgorithm((int)vertices[0].x, (int)vertices[0].y, (int)vertices[1].x, (int)vertices[1].y);

       }

 

       glPointSize(1.0);

       glColor3f(1.0, 0.0, 0.0);

       glBegin(GL_POINTS);

             for(i = 0; i < 640; i++) {

                    for(j = 0; j < 480; j++) {

                           if (screen[i][j]) {

                                  glVertex2i(i, j);

                           }

                    }

             }

       glEnd();

       glPointSize(4.0);

       glColor3f(1.0, 1.0, 0.0);
       glBegin(GL_POINTS);
             for (i = 0; i < numPuntos; i++) {
                    glVertex2f(vertices[i].x, vertices[i].y);
             }
       glEnd();
       glFlush();
}

 

 

void ddaAlgorithm(int x0, int y0, int x1, int y1) {

      int longitudX, longitudY, longitud, i;
       float Dx, Dy, x, y;
      longitudX = x1 - x0;
       longitudY = y1 - y0;
       longitud = (abs(longitudX) > abs(longitudY)) ? abs(longitudX) : abs(longitudY);
       Dx = (float) longitudX / (float) longitud;
       Dy = (float) longitudY / (float) longitud;
      x = x0;
       y = y0;

 

       for(i = 0; i <= longitud; i++) {

             screen[my_round(x)][my_round(y)] = 1;

             x += Dx;

             y += Dy;

       } 

}

void limpiaScreen() {

       int i, j;
       for (i = 0; i < 640; i++) {
             for (j = 0; j < 480; j++) {
                    screen[i][j] = 0;
             }
       }
}
int my_round (float n) {
       return floor(n + 0.5);
}

Investigacion

Investigue sobre los siguientes temas:
publique su investigación el blog
nota: considere que debe implementar los algoritmos con la ayuda opengl por lo que debe comprender los algoritmos).

 

1. Algoritmo DDA para generación de líneas

Podemos eliminar la multiplicación de la siguiente manera:
Sabemos que   = + b
Entonces =  + b = … -> =     + m
Como Δx=1, llegamos a la fórmula final --- =   + m
Cada pixel se calcula en función del anterior
No hace falta calcular b
Este algoritmo presenta un inconvenientes:

– Existen errores de acumulación.

– El redondeo es muy lento.

 

ALGORITMO DDA

Funcion Linea_DDA (int x0, y0, x1, y1)

dx = x1 – x0

dy = y1 – y0

Si abs(dx) > abs(dy) entonces steps = abs(dx)

Si no steps = abs(dy)

xinc = dx / steps

yinc = dy / steps

x = x0

y = y0

Pintar Pixel (round(x), round(y))

Para k=1 hasta k=steps

x = x + xinc

y = y + yinc

Pintar Pixel (round(x), round(y))

 

2.     Algoritmo de Bresenham para trazar líneas. Es un algoritmo creado para dibujar rectas en los dispositivos de gráficos rasterizados, como por ejemplo un monitor de ordenador, que determina qué pixeles se rellenarán, en función de la inclinación del ángulo de la recta a dibujar.

 

ALGORITMO Bresenham:

Si 0<|m|<1

  *Se capturan los extremos de la línea y se almacena el extremo izquierdo en (x₀,y₀).

  *Se carga (x₀,y₀) en el bufer de estructura (se traza el primer punto)

  *Se calculan las constantes Δx,Δy, 2Δy y 2Δy-Δx y se obtiene el valor inicial para el

    parametro de decisión p₀=2Δy-Δx.

  Para j=0 mientras j<Δx

  *En cada x_k a lo largo de la línea, que inicia en k=0 se efectúa la prueba siguiente:

      Si p_k<0

          *Trazamos (x_k+1,y_k).

          *Asignamos p_k+1= p_k+2Δy.

      Sino

          *Trazamos (x_k+1,y_k+1).

          *Asignamos p_k+1= p_k+2Δy-2Δx.

  Fin Para

Si |m|>1

   *Recorremos la dirección en pasos unitarios y calculamos los valores sucesivos   

     de x que se aproximen más a la trayectoria de la línea.

 

 

3. algoritmo de Bresenham para trazar circunferencias.

Se basa en analizar el error entre la verdadera circunferencia y su discretización. En cada paso elige como próximo pixel a aquel que minimice el error.

 

 

Para cada pixel P en el arco definido

por x³0, y³0, x³y; el pixel siguiente

sólo puede ser S (sur) o D (diagonal)

PICTURE

 

En este caso se toma como error la distancia al cuadrado del pixel (x,y) a la circunferencia de centro en el origen y radio r:    

e=x2+ y2-r2.

 

 

Si elegimos S el proximo pixel es PS=(x, y+1) entonces:

eS = x^2+ (y+1)^2-r^2 = e+2y+1
 Si elegimos D, entonces el próximo pixel es PD=(x-1, y+1).
eD = (x-1)2+ (y+1)2-r2 = x2-2x +1+y2+2y+1-r2 = eS -2x+1.

 

Entonces la elección del pixel PS o PD dependerá de cual de los dos

errores tiene menor módulo

Si ½e+2y+1½>½e+2y+1-2x+1½ Þ D

Es lo mismo que

Si ½eS½>½eS-2x+1½ Þ D

Además –2x+1 £ -1 y 0< eS< 1 entonces
Si eS>-eS+2x-1 Þ D y por lo tanto
Si 2eS>2x-1 Þ D
El algoritmo utiliza solo operaciones enteras

ALGORITMO

CirculoBressenham (radio, col)
{ int x,y ,e ;

                x = radio; y = 0 ; e = 0;

while(y<=x){

putpixel(x,y,col); putpixel(y,x,col);

putpixel(-x,y,col); putpixel(-y,x,col);

putpixel(x,-y,col); putpixel(y,-x,col);

putpixel(-x,-y,col); putpixel(-y,-x,col);

e = e +2y+1;

y=y+1;

if(2e >2x-1){

x=x-1;
e=e-2x+1;}
  }

}