Primitivas Gráficas - Algoritmo DDA para Líneas

En este post explicaré el algoritmo para lineas DDA (Digital Differential Analyzer) en 2D:

DEMOSTRACIONES

Primero de la ecuación general de la recta:

y=mx+b

sabiendo que

m=△y/△x

Si la pendiente es 0≤m≤1:

calculamos el pixel actual y el siguiente:

yi=xi m + b ...(1)

yi+1=xi+1m+b ...(2)

De la ecuación (1) obtenemos:

b=yi - xi m

De la ecuación (2) obtenemos:

yi+1=xi+1m+b

yi+1=xi+1m+(yi - xi m)

yi+1=xi+1m+yi - xi m

yi+1=yi+ xi+1m - xi m

yi+1=yi+ m (xi+1 - xi )

yi+1=yi+ m △x ...(3)

Si la linea se procesa de izquierda a derecha:

Entonces △x=1

Por lo que la ecuación (3) se reemplaza △x por 1 quedando:

yi+1=yi + m ...(4)

Si la línea se procesa de derecha a izquierda:

Entonces △x = -1
Por lo que la ecuación (3) se reemplaza △x por -1 quedando:

yi+1=yi - m ...(4.5)

Cada pixel es calculado con el anterior y no es necesario sabe el valor de la constante 'b'.

Si la pendiente m>1.

Primero cambiamos variables x por y.

xi=(yi-b)/m ...(5)

xi+1=(yi+1-b)/m ...(6)

De la ecuación (5) obtenemos:

b=yi-xim

De la ecuación (6) obtenemos:

xi+1=(yi+1 - b)/m

xi+1=(yi+1 - (yi-xi m))/m

xi+1=(yi+1 - yi+xi m))/m

xi+1=(△y + xi m))/m

xi+1=xi + (△y/m) ...(7)

Si la linea se procesa de abajo a arriba:

Entonces △y=1
Por lo que la ecuación (7) se reemplaza △y por 1 quedando:

xi+1=xi + (1/m) ...(8)

Si la linea se procesa de arriba a abajo:

Entonces △y=-1
Por lo que la ecuación (7) se reemplaza △y por -1 quedando:

xi+1=xi - (1/m) ...(8.5)

Ecuaciones:

yi+1=yi + m            → 0≤m≤1 y △x = 1
yi+1=yi - m             → 0≤m≤1 y △x = -1
xi+1=xi + (1/m)      → m>1 y △y = 1
xi+1=xi - (1/m)       → m>1 y △y = -1

Inconvenientes:

• Existen errores de acumulación
•  El redondeo es muy lento

ALGORITMO GENERAL

De las ecuaciones podemos deducir:

• si 0≤|m|≤1:

|△y|/|△x|≤1

|△y|≤|△x|

→ |△x| = 1=|△x|/|△x|

- yk = xk m + b

- yk+1 = (xk +△x) m + b

 yk+1 = xkm +△xm + b

 yk+1 = yk +m△x
 yk+1 - yk =m△x
 △y =m△x

⇒ |△y| =|m||△x|

• si m>1

|△y|/|△x|>1

|△y|>|△x|

→ |△y| = 1

- yk = xk m + b

- yk +1 = (xk+1) m + b
 yk +  △y = (xk+1) m + b
 (xk m + b ) + △y= xk+1 m + b

 xk m + △y = xk+1 m

 (xk m +△y)/m = xk+1
 xk+1 = xk +(△y/m)
 xk+1 - xk = △y/m
 △x = △y/m

⇒ |△x| = |△y|/|m|

Ecuaciones Generales

0≤|m|≤1

• |△x| = 1 = |△x|/|△x|
• |△y| =|m||△x|

|m|>1

• |△x| = |△y|/|m|
• |△y| = 1 = |△y|/|△y| 

Codificando:

	void DDA (GLint x1,GLint y1,GLint x2,GLint y2)
	{
	float ax,ay,x,y,res;
	GLint i;
	if(abs(x2-x1)>=abs(y2-y1))
	//si la variacion en x es mayor o igual que la variacion en y
	res=abs(x2-x1);
	else
	//si la variacion en y es mayor que la variacion en x
	res=abs(y2-y1);
	ax=(x2-x1)/res;//el valor a aumentar en x
	ay=(y2-y1)/res;//el valor a aumentar en y
	//se realiza casteo a float porque los resultados de la división es un real
	x=(float)x1;
	y=(float)y1;
	i=0;
	while(i<=res)
	{
	setPixel(roundf(x),roundf(y));
	x=x+ax;
	y=y+ay;
	i++;
	}
	}

view raw DDA.cpp hosted with ❤ by GitHub

Aquí una explicación con ejemplo:


Código fuente aqui

Video Explicación Código:

ENLACES RELACIONADOS

Computación Gráfica
Clases