Primitivas Gráficas - Algoritmo BRESENHAM para Líneas
En este post explicaré el algoritmo para lineas BRESENHAM en 2D:
DEFINICIÓN
- Algoritmo preciso y efectivo para la generación de líneas de rastreo.
- Con el apoyo de un parámetro de decisión, elige de entre dos pixeles el que más se acerca a la trayectoria de la recta.
- Dado un punto (xk, yk), se predice el punto (xk+1, yk+1), teniendo en cuenta el parámetro de decisión pk.
DEMOSTRACIÓN
Consideraciones previas
Una recta es la representación de un lugar geométrico definido por:
y = mx + b ... (1)
Dicho lugar geométrico tiene extremos (x0, y0) y (xf, yf):
m=(yf - y0)/(xf - x0)
m=∆y/∆x ...(2)
m=∆y/∆x ...(2)
De donde:
y = (∆y/∆x)x + b ...(3)
0<m<1
Tenemos:
(xk, yk)
(xk + 1, yk) o (xk + 1, yk + 1)
Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
d1 = y - yk = m(xk + 1) + b - yk
d2 = (yk+1) - y = yk + 1 - m(xk + 1) - b
d1 - d2 = 2m(xk + 1) - 2yk + 2b - 1
El parámetro de decisión pk indica el paso k en el algoritmo.
pk =∆x(d1 - d2)
pk =∆x(d1 - d2)
pk =∆x(2m(xk + 1) - 2yk + 2b - 1)
pk =∆x(2m(xk + 1) - 2yk + 2b - 1)
pk =∆x(2(∆y/∆x)(xk + 1) - 2yk + 2b - 1)
pk = 2∆y(xk + 1) - 2∆xyk + 2∆xb - ∆x
pk = 2∆yxk + 2∆y - 2∆xyk + 2∆xb - ∆x
pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb - ∆x
pk = 2∆yxk - 2∆xyk + C
pk = 2∆yxk - 2∆xyk + C
Donde:
- pk tiene el signo de d1 - d2
- xf > x0
- C=2∆y+2∆xb-∆x (Independiente del pixel)
- yk está más cerca de la trayectoria de la recta
- pk es negativo
- yk+1 está más cerca de la trayectoria de la recta
- pk es positivo
pk+1 = 2∆yxk+1 - 2∆xyk+1 + C
Al sustraer pk:
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
Si xk+1 = xk + 1
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
pk+1 - pk = 2∆y(xk + 1 - xk) - 2∆x(yk+1 - yk)
pk+1 - pk = 2∆y - 2∆x(yk+1 - yk)
pk+1 = pk + 2∆y - 2∆x(yk+1 - yk)
De donde:- Si yk+1 = yk + 1
pk+1 = pk + 2∆y - 2∆x
- Si yk+1 = yk
pk+1 = pk + 2∆y
Esto depende del parámetro p0:
pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb - ∆x
p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb - ∆x
De la ecuación 3 despejo b:
y0 = (∆y/∆x)x0 + b
b = y0 - (∆y/∆x)x0 ...(4)
Reemplazo en p0:
p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb - ∆x
p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆x(y0 - (∆y/∆x)x0) - ∆x
Resolviendo la ecuación:
p0 = 2∆y - ∆x
Finalmente, para este caso tenemos:
p0 = 2∆y - ∆x
Si pk < 0
- Trazar (xk+1, yk)
- pk+1 = pk + 2∆y
Caso contrario
- Trazar (xk+1, yk + 1 )
- pk+1 = pk + 2∆y - 2∆x
-1<m<0
Tenemos:
(xk, yk)
(xk + 1, yk) o (xk + 1, yk - 1)
Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
d1 = y - yk+1 = m(xk + 1) + b - (yk - 1) = m(xk + 1) + b - yk + 1
d2 = yk - y = yk - m(xk + 1) - b
d1 - d2 = 2m(xk + 1) - 2yk + 2b + 1
El parámetro de decisión pk indica el paso k en el algoritmo.
pk =∆x(d1 - d2)
pk =∆x(d1 - d2)
pk =∆x(2m(xk + 1) - 2yk + 2b + 1)
pk =∆x(2m(xk + 1) - 2yk + 2b + 1)
pk =∆x(2(∆y/∆x)(xk + 1) - 2yk + 2b + 1)
pk = 2∆y(xk + 1) - 2∆xyk + 2∆xb + ∆x
pk = 2∆yxk + 2∆y - 2∆xyk + 2∆xb + ∆x
pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb + ∆x
pk = 2∆yxk - 2∆xyk + C
pk = 2∆yxk - 2∆xyk + C
Donde:
- pk tiene el signo de d1 - d2
- xf > x0
- C=2∆y+2∆xb+∆x (Independiente del pixel)
- yk - 1 está más cerca de la trayectoria de la recta
- pk es negativo
- yk está más cerca de la trayectoria de la recta
- pk es positivo
pk+1 = 2∆yxk+1 - 2∆xyk+1 + C
Al sustraer pk:
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
Si xk+1 = xk + 1
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
pk+1 - pk = 2∆y(xk + 1 - xk) - 2∆x(yk+1 - yk)
pk+1 - pk = 2∆y - 2∆x(yk+1 - yk)
pk+1 = pk + 2∆y - 2∆x(yk+1 - yk)
De donde:- Si yk+1 = yk - 1
pk+1 = pk + 2∆y + 2∆x
- Si yk+1 = yk
pk+1 = pk + 2∆y
Esto depende del parámetro p0:
pk = 2∆yxk - 2∆xyk + 2∆y + 2∆xb + ∆x
p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb + ∆x
Reemplazo en p0 por la ecuación (4):
p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆xb + ∆x
p0 = 2∆yx0 - 2∆xy0 + 2∆y + 2∆x(y0 - (∆y/∆x)x0) + ∆x
Resolviendo la ecuación:
p0 = 2∆y + ∆x
Finalmente, para este caso tenemos:
p0 = 2∆y + ∆x
Si pk < 0
- Trazar (xk+1, yk - 1)
- pk+1 = pk + 2∆y + 2∆x
Caso contrario
- Trazar (xk+1, yk)
- pk+1 = pk + 2∆y
1<m
(xk, yk)
Los posibles puntos a pintar serian:
(xk, yk + 1) o (xk + 1, yk + 1)
Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
d1 = x - xk = (yk + 1 - b)/m - xk
d2 = xk+1 - x = xk + 1 - (yk + 1 - b)/m
d1 - d2 = 2(yk + 1 - b)/m - 2xk - 1
El parámetro de decisión pk indica el paso k en el algoritmo.
pk =∆y(d1 - d2)
pk =∆y(d1 - d2)
pk =∆y(2(yk + 1 - b)/m - 2xk - 1)
pk =∆y(2(yk + 1 - b)/m - 2xk - 1)
pk =∆y(2(yk + 1 - b)/(∆y/∆x) - 2xk - 1)
pk =∆y(2(yk + 1 - b)/(∆y/∆x) - 2xk - 1)
pk =∆y(2∆x(yk + 1 - b)/∆y - 2xk - 1)
pk =2∆x(yk + 1 - b) - 2∆yxk - ∆y
pk =2∆xyk + 2∆x - 2∆xb - 2∆yxk - ∆y
pk =2∆xyk - 2∆yxk + 2∆x - 2∆xb - ∆y
pk =2∆xyk + 2∆x - 2∆xb - 2∆yxk - ∆y
pk =2∆xyk - 2∆yxk + 2∆x - 2∆xb - ∆y
pk =2∆xyk - 2∆yxk + 2∆x - 2∆xb - ∆y
pk =2∆xyk - 2∆yxk + C
pk =2∆xyk - 2∆yxk + C
Donde:
- pk tiene el signo de d1 - d2
- yf > y0
- C=2∆x - 2∆xb - ∆y (Independiente del pixel)
- xk está más cerca de la trayectoria de la recta
- pk es negativo
- xk+1 está más cerca de la trayectoria de la recta
- pk es positivo
pk+1 =2∆xyk+1 - 2∆yxk+1 + C
Al sustraer pk:
pk+1 - pk = 2∆x(yk+1 - yk) - 2∆y(xk+1 - xk)
Si yk+1 = yk + 1
pk+1 - pk = 2∆x(yk+1 - yk) - 2∆y(xk+1 - xk)
pk+1 - pk = 2∆x(yk + 1 - yk) - 2∆y(xk+1 - xk)
pk+1 - pk = 2∆x - 2∆y(xk+1 - xk)
pk+1 = pk + 2∆x - 2∆y(xk+1 - xk)
De donde:pk+1 = pk + 2∆x - 2∆y(xk+1 - xk)
- Si xk+1 = xk + 1
pk+1 = pk + 2∆x - 2∆y
- Si xk+1 = xk
pk+1 = pk + 2∆x
Esto depende del parámetro p0:
pk =2∆xyk - 2∆yxk + 2∆x - 2∆xb - ∆y
p0 =2∆xy0 - 2∆yx0 + 2∆x - 2∆xb - ∆y
Reemplazo en p0 por la ecuación (4):
p0 =2∆xy0 - 2∆yx0 + 2∆x - 2∆xb - ∆y
p0 =2∆xy0 - 2∆yx0 + 2∆x - 2∆x(y0 - (∆y/∆x)x0) - ∆y
p0 =2∆xy0 - 2∆yx0 + 2∆x - 2∆x(y0 - (∆y/∆x)x0) - ∆y
Resolviendo la ecuación:
p0 = 2∆x - ∆y
Finalmente, para este caso tenemos:
p0 = 2∆x - ∆y
Si pk < 0
- Trazar (xk, yk + 1)
- pk+1 = pk + 2∆x
Caso contrario
- Trazar (xk+1, yk + 1)
- pk+1 = pk + 2∆x - 2∆y
m<-1
(xk, yk)
Los posibles puntos a pintar serian:
(xk, yk + 1) o (xk - 1, yk + 1)
Para elegir el píxel correcto, medimos la distancia de la recta a esos dos puntos:
pk =2∆yxk - 2∆xyk - 2∆x + 2∆xb + ∆y
d1 = xk - x = xk - (yk + 1 - b)/m
d2 = x - xk+1 = (yk + 1 - b)/m - xk + 1
d1 - d2 = 2xk - 2(yk + 1 - b)/m + 1
El parámetro de decisión pk indica el paso k en el algoritmo.
pk =∆y(d1 - d2)
pk =∆y(d1 - d2)
pk =∆y(2xk - 2(yk + 1 - b)/m +1)
pk =∆y(2xk - 2(yk + 1 - b)/m +1)
pk =∆y(2xk - 2(yk + 1 - b)/(∆y/∆x) +1)
pk =2∆yxk - 2∆y∆x(yk + 1 - b)/∆y + ∆y
pk =∆y(2xk - 2(yk + 1 - b)/(∆y/∆x) +1)
pk =2∆yxk - 2∆y∆x(yk + 1 - b)/∆y + ∆y
pk =2∆yxk - 2∆x(yk + 1 - b) + ∆y
pk =2∆yxk - 2∆xyk - 2∆x + 2∆xb + ∆y
pk =2∆yxk - 2∆xyk + C
pk =2∆yxk - 2∆xyk + C
Donde:
- pk tiene el signo de d1 - d2
- yf > y0
- C= - 2∆x + 2∆xb + ∆y(Independiente del pixel)
Si d1 < d2
- xk está más cerca de la trayectoria de la recta
- pk es negativo
- xk+1 está más cerca de la trayectoria de la recta
- pk es positivo
pk+1 =2∆yxk+1 - 2∆xyk+1 + C
Al sustraer pk:
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
Si yk+1 = yk + 1
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x(yk + 1 - yk)
pk+1 - pk = 2∆y(xk+1 - xk) - 2∆x
pk+1 = pk + 2∆y(xk+1 - xk) - 2∆x
De donde:pk+1 = pk + 2∆y(xk+1 - xk) - 2∆x
- Si xk+1 = xk
pk+1 = pk - 2∆x
- Si xk+1 = xk - 1
pk+1 = pk - 2∆y - 2∆x
Esto depende del parámetro p0:
pk =2∆yxk - 2∆xyk - 2∆x + 2∆xb + ∆y
p0 =2∆yx0 - 2∆xy0 - 2∆x + 2∆xb + ∆y
p0 =2∆yx0 - 2∆xy0 - 2∆x + 2∆xb + ∆y
Reemplazo en p0 por la ecuación (4):
p0 =2∆yx0 - 2∆xy0 - 2∆x + 2∆xb + ∆y
p0 =2∆yx0 - 2∆xy0 - 2∆x + 2∆x(y0 - (∆y/∆x)x0) + ∆y
Resolviendo la ecuación:
p0 = - 2∆x + ∆y
Finalmente, para este caso tenemos:
p0 = -2∆x + ∆y
Si pk < 0
- Trazar (xk, yk + 1)
- pk+1 = pk - 2∆x
Caso contrario
- Trazar (xk-1, yk + 1)
- pk+1 = pk - 2∆x - 2∆y
Casos Especiales
m=0
- Tenemos:
(xk, yk)
- El siguiente punto a pintar es:
(xk + 1, yk)
- Siempre que:
xf > x0
m=1
- Tenemos:
(xk, yk)
- El siguiente punto a pintar es:
(xk + 1, yk + 1)
- Siempre que:
xf > x0
m=-1
- Tenemos:
(xk, yk)
- El siguiente punto a pintar es:
(xk + 1, yk - 1)
- Siempre que:
xf > x0
m= ∞
- Tenemos:
(xk, yk)
- El siguiente punto a pintar es:
(xk , yk + 1)
- Siempre que:
yf > y0
ECUACIONES
CREANDO CÓDIGO
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <math.h> | |
#include <GL/glut.h> | |
#include <windows.h> | |
using namespace std; | |
void initialize() { | |
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); | |
glutInitWindowSize (680, 680); | |
glutInitWindowPosition (30,30); | |
glutCreateWindow ("LINEA BRESENHAM"); | |
glClearColor(1.0,1.0,1.0,1.0); | |
glMatrixMode(GL_PROJECTION); | |
gluOrtho2D(-60,60,-60,60); | |
} | |
void rectareferencial(GLint x0,GLint y0,GLint xf,GLint yf) | |
{ | |
/* ----RECTA REFERENCIA---- */ | |
glLineWidth(0.1); | |
glBegin(GL_LINES); | |
glColor3f(0.2, 1, 0.2); | |
glVertex2f(x0,y0); | |
glVertex2f(xf,yf); | |
glEnd(); | |
glFlush(); | |
} | |
void ejecoordenadas() | |
{ | |
glLineWidth(0.1); | |
glBegin(GL_LINES); | |
glColor3f( 1, 0, 0); | |
/*eje y*/ | |
glVertex3f(0,60,-1); | |
glVertex3f(0,-60,-1); | |
/*eje x*/ | |
glVertex3f(60,0,0); | |
glVertex3f(-60,0,0); | |
glEnd(); | |
} | |
void cudriculafondo() | |
{ | |
for(float i=-59.5;i<60;i+=1) | |
{ | |
glLineWidth(1); | |
glBegin(GL_LINES); | |
glColor3f( 0, 255, 255); | |
glVertex3f(i,100,-1); | |
glVertex3f(i,-100,-1); | |
glVertex3f(100,i,-1); | |
glVertex3f(-100,i,-1); | |
glEnd(); | |
} | |
} | |
void setPixel(GLint x, GLint y) | |
{ | |
glPointSize(5); | |
glBegin(GL_POINTS); | |
glVertex2i(x,y); | |
glEnd(); | |
glFlush(); | |
} | |
void lineaBresenham(GLint x0, GLint y0, GLint xf, GLint yf) | |
{ | |
GLint dx = xf - x0; | |
GLint dy = yf - y0; | |
GLint contador; | |
GLfloat m = (float)dy/dx; | |
GLint p0,pk,a,b; | |
GLint e1; | |
GLint e2; | |
GLint x,y; | |
GLboolean band; | |
if(m>=0 && m<1) | |
{ | |
if(x0 > xf) | |
{//invertir valores | |
a=x0; | |
b=y0; | |
x0=xf; | |
y0=yf; | |
xf=a; | |
yf=b; | |
dx = xf - x0; | |
dy = yf - y0; | |
} | |
p0 = 2*dy - dx; | |
x = x0; | |
y = y0; | |
pk=p0; | |
e1 = 2 * dy; | |
e2 = 2 * ( dy - dx ); | |
band = 0 ; | |
contador = x0; | |
} | |
else | |
{ | |
if(m>=1) | |
{ | |
if(x0 > xf) | |
{ | |
//invertir valores | |
a=x0; | |
b=y0; | |
x0=xf; | |
y0=yf; | |
xf=a; | |
yf=b; | |
dx = xf - x0; | |
dy = yf - y0; | |
} | |
p0 = 2*dx - dy; | |
x = x0; | |
y = y0; | |
pk=p0; | |
e1 = 2 * dx; | |
e2 = 2 * ( dx - dy ); | |
contador = y0; | |
band = 1 ; | |
} | |
else | |
{ | |
if(m>-1 && m<0) | |
{ | |
dx = x0 - xf; | |
dy = yf - y0; | |
if(x0 < xf) | |
{//invertir valores | |
a=x0; | |
b=y0; | |
x0=xf; | |
y0=yf; | |
xf=a; | |
yf=b; | |
dx = x0 - xf; | |
dy = yf - y0; | |
} | |
p0 = 2*dy - dx; | |
x = x0; | |
y = y0; | |
pk=p0; | |
e1 = 2 * dy; | |
e2 = 2 * ( dy - dx ); | |
band = 2 ; | |
contador = x0; | |
} | |
else | |
{ | |
if(m<-1) | |
{ | |
dx = x0 - xf; | |
dy = yf - y0; | |
if(x0 < xf) | |
{ | |
//invertir valores | |
a=x0; | |
b=y0; | |
x0=xf; | |
y0=yf; | |
xf=a; | |
yf=b; | |
dx = x0 - xf; | |
dy = yf - y0; | |
} | |
p0 = 2*dx - dy; | |
x = x0; | |
y = y0; | |
pk=p0; | |
e1 = 2 * dx; | |
e2 = 2 * ( dx - dy ); | |
band = 3 ; | |
contador = y0; | |
} | |
} | |
} | |
} | |
setPixel(x,y); | |
//cout<<x<<" , "<<y<<"\n"; | |
if(band==1) | |
{ | |
while(contador<yf) | |
{ | |
y++; | |
if(pk<0) | |
{ | |
pk += e1; | |
} | |
else | |
{ | |
pk += e2; | |
x++; | |
} | |
contador++; | |
setPixel(x,y); | |
//cout<<x<<" , "<<y<<"\n"; | |
} | |
} | |
else | |
{ | |
if(band==0) | |
{ | |
//cout<<"hola"; | |
while(contador<xf) | |
{ | |
x++; | |
if(pk<0) | |
{ | |
pk += e1; | |
} | |
else | |
{ | |
pk += e2; | |
y++; | |
} | |
contador++; | |
setPixel(x,y); | |
//cout<<x<<" , "<<y<<"\n"; | |
} | |
} | |
else | |
{ | |
if(band==2) | |
{ | |
while(contador>xf) | |
{ | |
x--; | |
if(pk<0) | |
{ | |
pk += e1; | |
} | |
else | |
{ | |
pk += e2; | |
y++; | |
} | |
contador--; | |
setPixel(x,y); | |
//cout<<x<<" , "<<y<<"\n"; | |
} | |
} | |
else | |
{ | |
if(band==3) | |
{ | |
while(contador<yf) | |
{ | |
y++; | |
if(pk<0) | |
{ | |
pk += e1; | |
} | |
else | |
{ | |
pk += e2; | |
x--; | |
} | |
contador++; | |
setPixel(x,y); | |
//cout<<x<<" , "<<y<<"\n"; | |
} | |
} | |
} | |
} | |
} | |
} | |
void drawMyLine(void) | |
{ | |
glClear(GL_COLOR_BUFFER_BIT); | |
// MODIFICAR PUNTOS | |
GLint x0 = 2; | |
GLint y0 = 8; | |
GLint xf = -32; | |
GLint yf = -34; | |
cudriculafondo(); | |
ejecoordenadas(); | |
glColor3f(1.0,0.0,0.0); | |
lineaBresenham(x0,y0,xf,yf); | |
glColor3f(0.0,0.0,1.0); | |
rectareferencial(x0,y0,xf,yf); | |
} | |
int main (int argc, char **argv) { | |
glutInit (&argc, argv); | |
initialize(); | |
glutDisplayFunc(drawMyLine); | |
glutMainLoop(); | |
return 0; | |
} |
Comentarios
Publicar un comentario