UNIDAD II Graficación 2D.

Algoritmo DDA para generación de rectas.

Este algoritmo sirve para generar lineas rectas haciendo uso de la pendiente Y y de los incrementos en X,Y.
Es un algoritmo de digitalización de líneas basado en calcular dy y dx usando cualquiera de las dos ecuaciones (dy = m * dx) o (dx = m * dy).

El codigo es:
void DDA(int x_0,int y_0, int x_fin, int y_fin){
glClear ( GL_COLOR_BUFFER_BIT );
glPointSize(3.0);
glScalef(4.0, 4.0, 2.0);
glBegin(GL_POINTS);
glVertex2i(x_0,y_0);
int vx=(int)fabs(x_fin-x_0);
int vy=(int)fabs(y_fin-y_0);
int dx,dy;
int m = (int)(y_fin-y_0)/(x_fin-x_0);
if(m==1)m++;
if(m==0)m=-1;
if(m>0&&m<1){
if(x_0<x_fin){
dx=1;
dy=m;
}else{
dx=-1;
dy=-m;
}
}
else
if(m>0&&m>1){
if(m>1){
if(x_0<x_fin){
dy=1;
dx=(int)1/m;
}else{
dy=-1;
dx=(int)-1/m;
}
}else
if(m<0&&fabs(m)<1){
if(x_0>x_fin)
{
dx=-1;
dy=-m;
}else
{
dx=1;
dy=-m;
}
}
else{
if(x_0>x_fin){
dy=1;
dx=-1/m;
}
else {
dy=-1;
dx=1/m;
}
}
if(m>0&&m<1){
for(int i=1;i<=vx;i++)
{
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;
}
}
else
if(m>0&&m>1){
for(int i=1;i<=vy;i++){
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;}
}else
if(m<0&&fabs(m)<1){
for(int i=1;i<=vx;i++)
{
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;
}
}
else{
for(int i=1;i<=vy;i++){
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;
}
}
}
glEnd();
glFlush();
}

Algoritmo de Bresenham para trazar líneas.

Es un algoritmo que determina los puntosen un mapa de bits de n dimensiones que son trazados con el fin de formar una aproximación a una línea recta entre dos puntos dados.
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.

Las ecuaciones necesarias son:

Y - Y0 = X - X0
Y1-Y0    X1-X0
    
     Y1-Y0
y = ------- (X - X0) + Y0
     X1-X0

El código es:
void brenenham(int x1, int y1, int x2, int y2)
{
int slope;
int dx, dy, incE, incNE, d, x, y;
// Reverse lines where x1 > x2if (x1 > x2)
{
brenenham(x2, y2, x1, y1)
;return;
}
dx = x2 - x1;
dy = y2 - y1;
// Adjust y-increment for negatively sloped lines
if (dy < 0)
{
slope = -1;
dy = -dy;
}
else
{
slope = 1;
}
// Bresenham constants
incE = 2 * dy;
incNE = 2 * dy - 2 * dx;
d = 2 * dy - dx;y = y1;
// Blit
for (x = x1; x <= x2; x++)
{
putpixel(x, y, 15);
if (d <= 0)
{
d += incE;
}
else
{
d += incNE;
y += slope;
}
}
}

Algoritmo de Bresenham para el trazo de 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.

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

Si elegimos D, entonces el próximo pixel es P

e

Si elegimos S el proximo pixel es P

e=x

 







Fuentes de información:
http://compugrafica.wordpress.com/2008/12/03/algoritmo-dda-para-generacion-de-rectas/
issuu.com/uvitzel/docs/eva_y_chava
http://es.scribd.com/doc/59563233/Algoritmo-Bresenham

= x2+ (y+1)2-r2 = e+2y+1D=(x-1, y+1) = (x-1)2+ (y+1)2-r2 = x2-2x +1+y2+2y+1-r2 = eS -2x+1S=(x, y+1) entonces:2+ y2-r2.