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 ...(2)
De la ecuación (1) obtenemos:
b=yi - xi m
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 - (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 = 1yi+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+1 = (xk +△x) m + b
yk+1 = xkm +△xm + b
Aquí una explicación con ejemplo:
Código fuente aqui
Video Explicación Código:
Clases
yk+1 = yk +m△x
yk+1 - yk =m△x
△y =m△x
⇒ |△y| =|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
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
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:
Aquí una explicación con ejemplo:
Código fuente aqui
Video Explicación Código:
ENLACES RELACIONADOS
Computación GráficaClases
Comentarios
Publicar un comentario