Algoritmo de Bresenham y DDA


Algoritmo de Bresenham

Es un algoritmo que determina los puntos en un mapa de bits de n-dimensiones que deben ser trazados con el fin de formar una aproximación a una línea recta entre dos puntos dados.

Es uno de los primeros algoritmos desarrollados en el campo de gráficos por ordenador, también se ocupa de dibujar círculos.

 Partimos de que las coordenadas de los pixeles en una imagen son coordenadas enteras y que conocemos los extremos del segmento que forma la línea siendo sus coordenadas (x0,y0) y (x1,y1).

El algoritmo de Bresenham selecciona el entero 'y' correspondiente al pixel central que está más cercano del que sería calculado con fracciones y lo mismo para la coordenada 'x'. En las sucesivas columnas la coordenada 'y' puede permanecer con el mismo valor o incrementarse en cada paso a una unidad.
La ecuación general de la línea que pasa por los extremos conocidos es:

Puesto que conocemos la columna, 'x', la fila 'y' del pixel se calcula redondeando esta cantidad al entero más cercano según la siguiente fórmula:



La pendiente (y1-y0) / (x1-x0) depende sólo de las coordenadas de los extremos y puede ser previamente calculada, y el valor ideal de 'y' para los sucesivos valores enteros de 'x' se puede calcular a partir de  e ir añadiendo en varias ocasiones la pendiente.

Algoritmo DDA

Digital Differential Analyzer, es un algoritmo de línea de conversión de rastreo que se basa en el cálculo ya sea en el incremento de X o en el incremento de Y. La finalidad de este algoritmo es determinar los valores enteros correspondientes más próximos a la trayectoria de la línea para la otra coordenada.
Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determinan los valores enteros correspondientes más próximos a la trayectoria de la línea para la siguiente coordenada.
Se aceptan como datos de entradas las dos posiciones de los pixeles correspondientes a los extremos de la línea P1(Xinicial,Yinicial) y P2(Xfinal,Yfinal). Las diferencias horizontal y vertical entre las posiciones de los extremos dados, se asignan a las varialbles DeltaX y DeltaY respectivamente. La diferencia con la mayor magnitud determina el valor del parámetro Pasos. Se procede a determinar la compensación necesaria(incremento), para generar la posición del pixel siguiente a lo largo de la trayectoria de la línea. Luego, se ilumina la posición en la pantalla y se repite este proceso cíclico Pasos Veces, hasta obtener la línea deseada.

PSEUDOCÓDIGO

Leer Coordenadas P1(Xinicial, Yinicial)

Leer Coordenadas P2(Xfinal,Yfinal)
Asignar a DeltaX la diferencia de Xfinal - Xinicial
Asignar a DeltaY la diferencia de Yfinal - Yinicial
Si ABS( DeltaX) > ABS(DeltaY)
Asignar a Pasos el ABS(DeltaX)
De lo contrario
Asignar a Pasos el ABS(DeltaY)
Asignar a Xincremento el resultado de DeltaX / Pasos
Asignar a Yincremento el resultado de DeltaY / Pasos
Asignar a X el valor de Xinicial
Asignar a Y el valor de Yinicial
Iluminar pixel en coordenada X,Y
Desde k=1 hasta Pasos
Asignar a X la suma de X + Xincremento
Asignar a Y la suma de Y + Yincremento
Iluminar pixel en Coodenada X,Y
Fin de Algoritmo(DDA)



Comentarios

Publicar un comentario

Entradas populares de este blog

Código Capitán América Diana Vargas

Imagen
#include <windows.h> #include <math.h> #ifdef _APPLE_ #include <GLUT/glut.h> #else #include <GL/glut.h> #include <math.h> #define PI 3.1415926 #endif float x,y; float radio=0; float cx=0; float cy=0; float dx, dy; void estrella(float r, float g, float b){     glColor3f(r,g,g);     glBegin(GL_POLYGON);     glVertex2f(-2,2);     glVertex2f(2,2);     glVertex2f(3,-1);     glVertex2f(0,-3);     glVertex2f(-3,-1);     glEnd();     glBegin(GL_TRIANGLES);     glVertex2f(-2,2);     glVertex2f(2,2);     glVertex2f(0,6);     glVertex2f(2,2);     glVertex2f(3,-1);     glVertex2f(5.5,2);     glVertex2f(-2,2);     glVertex2f(-3,-1);     glVertex2f(-5.5,2);     glVertex2f(3,-1);     glVertex2f(0,-3);     glVertex2f(3.8,-4.7)...
Leer más

Reflejo | Diana Vargas

Imagen
#include <windows.h> #include <math.h> #include <GL/glut.h> float salto = 0.0;//esferita q rebota float anguloLuz = 0.0, alturaLuz = 15; float c=1,dia=-0.1; float angle = 0,angle2 = 0; int moving, startx, starty; static GLdouble tamanio = 4.0;//radio de la esfera static GLfloat posicionLuz[4]; static GLfloat colorLuz[] = {1, 1, 1, 1.0}; static GLfloat planoPiso[4]; static GLfloat sombraPiso[4][4]; enum {X, Y, Z, W}; enum {A, B, C, D}; char *textura[] = {//textura dibujada     "oooooooooooooooo",     "o...............",     "o..xxxxxxxxxxxx.",     "o..xxxxxxxxxxxx.",     "o..xxxxxxxxxxxx.",     "o..xxx......xxx.",     "o..xxx......xxx.",     "o..xxx.o.o..xxx.",     "o..xxx..o.o.xxx.",     "o..xxx......xxx.",     "o..xxx......xxx.",     "o..xxxxxxxxxxxx.",     "o..xxxxxxxxxxxx.",     "o..xxxxxxx...
Leer más

Cámara | Israel González de la Peña

Imagen
#include <windows.h> #include <GL/glut.h> GLfloat ang1 = 0,ang2 = 0; int moviendo, startx, starty; float angulo = 0; static GLdouble tamanio = 10.0; GLUquadric *figura; void dibujaObjeto(){     gluQuadricDrawStyle(figura, GLU_FILL);     glClear( GL_COLOR_BUFFER_BIT );     glColor3f(0.0, 0.0, 0.0);     glPushMatrix();     glRotatef(angulo+2, 0, 1, 0);     //Cabeza     glPushMatrix();     glTranslatef(0,2,0);     glRotatef(90,1,0,0);     glScalef(1.5,0.7,1);     glutSolidSphere(0.6,30,30);     glPopMatrix();     //Cuerpo     glPushMatrix();     glTranslatef(0,1,0);     glRotatef(90,1,0,0);     glScalef(1.5,0.7,1);     glutSolidTorus(0.5,0.5,30,30);     glPopMatrix();     //Cuerpo     glPushMatrix();     glTranslatef(0,0,0...
Leer más