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;}
  }

}