브레슨햄 동영상 강의
http://forum.falinux.com/zbxe/?document_srl=406146
http://blog.naver.com/nowcome/130019875263
#include <iostream>
using namespace std;
#define max( x, y) (((x) > (y)) ? (x) : (y)) // 큰수 찾는거 당연히 아시겠줘?
#define abs( x ) (((x) > 0) ? (x) : -(x)) // 절대값.
#define sign( x ) ((x) > 0 ? 1 : ((x) == 0 ? 0: (-1))) // 양수:1, 0, 음:-1
#define WIDTH 30
#define HEIGHT 25
char array[HEIGHT][WIDTH]={{'\0',},};
void show(){
for (int j=0;j<HEIGHT;++j)
{
for (int i=0;i<WIDTH;++i)
{
cout<<array[j][i]<<" ";
}
cout<<"\n";
}
}
void initial(){
for (int j=0;j<HEIGHT;++j)
{
for (int i=0;i<WIDTH;++i)
{
array[j][i]=' ';
}
}
}
void drawPoint(int x,int y){
array[y][x]='*';
}
void line(int x1,int y1,int x2,int y2){
int x,y;
int dx = x2 - x1;
int dy = y2 - y1;
int ix = abs(dx);
int iy = abs(dy);
int inc = max(ix, iy);
int plotx = x1;
int ploty = y1;
x = y = 0;
for(int I = 0; I <= inc ; I++)
{
x += ix;
y += iy;
if( x > inc)
{
x -= inc;
plotx += sign(dx);
}
if( y > inc )
{
y -= inc;
ploty += sign(dy);
}
drawPoint(plotx, ploty);
//그리는 함수 ( plotx, ploty);
}
}
int main(){
initial();
//line( 0,0,10,10 );
show();
return 0;
}
http://withwani.springnote.com/pages/159993
브레슨햄 알고리즘
컴퓨터 화면에 선을 빠르게 그리는 방법 중에 하나가 브레슨햄(Bresenhan) 알고리듬이 있습니다. 실수 나누셈을 사용하는 직선 공식보다 정수 계산만을 하는 브레슽핸 알고리듬이 매우 빠르죠.
이번에 임데디드 포럼에 그래픽 관련 문서를 만들면서 브레슨햄 선긋기 알고리듬을 정리해 보았습니다. 포럼에는 동영상까지 올렸으므로 관심있는 분은 방문해 보시기 바랍니다.
브레슨햄(Bresenham)알고리듬
직선의 공식을 사용하여 머릿 속으로 그래프를 그려 보면, 무수히 많은 점을 생각할 수 있읍니다만, 컴퓨터 그래픽에서는 스크린 좌표가 모두 정수이므로, 복잡하고 계산을 느리게 만드는 실수 계산을 정수 계산 만으로도 구현할 수 없을까하는 생각에서 만들어진 것이 브레슨햄 알고리듬입니다.
직선의 공식을 이용하여 계산된 좌료값이 소주점 이하 몇개의 자리로 된 실수값을 어렵게 구했다고 하더라도 컴퓨터화면에 출력할 때에는 소수점이하를 모두 버림한단든지 반올림해서 정수로 만들게 됩니다. 이렇게 버려지는 소수점 이하의 복잡한 계산을 브레슨햄 공식을 이용하여 없애 보도록 하겠습니다.
*** 이하의 설명은 dx 가 dy 보다 큰 경우일 때 입니다. ***
컴퓨터 화면에 직선을 긋기위해 이미 (xi, yi) 좌표에 점을 찍었습니다. 브레슨햄의 기본 원리는 선의 공식에 따라 다음 좌표값을 구하는 것이 아니라 현재 점의 위치에 대해서 어느 좌표에 다음 점을 찍을 지를 판단하는 알고리듬입니다.
그림에서 (xi,yi)의 다음 점의 위치는 녹색점(xi+1, yi+1) 보다는 빨강색점(xi+1, yi) 가 실제 점에 가깝습니다. 그렇다면 여기서 녹색점과 빨강색점에 대해 실제 직선의 위치와의 차이 d1, d2를 구해 보겠습니다.
d1, d2를 구하는 이유는, d1 < d2 라면 실제 y 점이 yi에 가깝다는 얘기가 되고, yi 에 점을 찍으면 됩니다. 반대로 d1 > d2 라면 yi+1에 점을 찍으면 되기 때문입니다.
즉, 0 < d1-d2 이면 yi+1 에, 0 > d1-d2 이면 yi 에 점을 찍으면되므로 (1) d1 과 d2의 차, 특히 (2) 차이값이 양수인지, 음수인지를 구하면 되겠습니다.
d1 = y -yi
여기서 y=m(xi+1) +b 이므로,
d1 = m(xi+1) +b -yi
d2 는,
d2 = (yi+1) -y
= yi +1 -( m(xi+1)+b)
= yi -m(xi +1) -b +1
두 거리의 차이를 구해 보겠습니다.
d1 - d2 = m(xi+1) +b -yi -(yi -m(xi +1) -b +1)
= m(xi+1) +b -yi -yi +m(xi+1) +b -1
= 2 m(xi+1) -2yi +2b -1
m 은 기울기를 dy/dx 이므로,
d1 - d2 = 2(dy/dx)(xi+1) -2yi +2b -1
여기서 다음 점을 찾기 위해서는 두 거리의 차이가 궁굼한 것이 아니라 두 차이에 대한 부호, 즉 양수인지 음수인지만이 필요하므로 정수 나눗셈이 있는 부분을 양편에 dx를 곱해서 없애겠습니다.
dx(d1-d2) = 2dy(xi+1) -2dxyi +2dxb -dx
= 2dyxi +2dy -2dxyi +2dxb -dx
다시 이 공식에서 변수 부분인 xi 또는 yi 가 들어간 부분과 한번 계산되면 다시 계사할 필요가 없는 부분으로 정리해 보겠습니다. 그리고 부호값 만을 생각할 수 있는 변수 pi 로 정리해 보겠습니다.
dx(d1 - d2) = pi = 2dyxi +2dy -2dxyi +2dxb -dx
= 2dyxi -2dxyi +2dy +2dxb -dx
= 2dyxi -2dxyi +2dy +dx(2b -1)
상수부분인 2dy +dx(2b-1)를 C 로 대치하면,
pi = 2dyxi -2dxyi +C <--- 공식 1
가 됩니다.
우리가 이 알고리듬을 이용해서 선을 긋게 되면, 루프를 이용하게 될 것이고, 이전에 계산된 pi 값을 이번 계산에 대입하고 적용할 수 있습니다.
그러므로 다음 pi 값인 pi+1 값을 아래와 같이 구할 수 있습니다.
pi+1 = 2dyxi+1 -2dxyi+1 +C
이전 p 값을 계속 참조하여 계산 하므로 pi 와 pi+1 값의 차를 구하겠습니다.
pi+1 - pi= 2dyxi+1 -2dxyi+1 +C - 2dyxi +2dxyi -C
= 2dy(xi+1-xi) - 2dx(yi+1-yi)
여기서 xi+1 와 xi는 서로 이웃하는 점이므로 xi+1 - xi는 1입니다.
그러므로 아래와 같이 정리할 수 있습니다.
pi+1 - pi= 2dy - 2dx(yi+1-yi)
이제 pi+1 값만 구한다면,
pi+1 = pi + 2dy - 2dx(yi+1-yi)
아직까지 복잡하게 보이지만 역시 스크린 좌표는 정수이고 yi+1와 yi 의 차이가 0 또는 1이라는 점을 상기한다면,
- 계산된 pi 값이 양수라면 d1이 더 크므로 다음 점은 현재의 yi 보다 1 만큼 크게되므로,
pi+1 = pi + 2dy - 2dx
가 되며,
- pi 값이 음수라면 d1이 더 작으므로 yi 값과 같아지므로 yi+1 - yi 는 0이 되므로,
pi+1 = pi + 2dy
값이 됩니다.
여기서 계산된 pi+1은 다음 루프의 pi 값이 되므로 이를 루프에서 계속 계산되고 다음 계산에 대입된다면 처음 p0 값을 구하고 점을 찍고 다음 pi 값으로 대입하면서 점 위치를 찾아 점을 찍으면 됩니다.
p0 구하기
p0값을 구하기 위해 공식 1 에 처음 좌표 (x1, y1)을 대입하고, 다음 예상 좌표를 (x1+1, y1+1/2)로 생각하고 p0을 구합니다..
p(x1, y1) = 2dyx1 -2dxy1 +C
p(x1+1, y1+1/2)= 2dy(xi+1) -2dx(yi+1/2) +C
p0 = p(x1+1, y1+1/2) - p(x1, y1)
= 2dy(xi+1) -2dx(yi+1/2) +C - ( 2dyx1 -2dxy1 +C)
= 2dyx1 +2dy -2dxy1 -dx -2dyx1 +2dxy1 +C -C
= 2dy(x1-x1) +2dy -2dx(y1-y1) -dx
= 2dy -dx
p0 을 구하기 위해 x1 의 다음 좌표는 당연히 1 을 증가한 x1+1 이 되겠지만 , y1 축의 값은 y1 이 될지 y1+1이 될지 모르므로 확률 상의 경우를 1/2로 보고 계산한 것입니다.
선을 긋기 전에 필요한 상수 값
- 최초의 p0 을 구합니다.
- pi 의 부호 값에 따라 아래의 2가지 값이 필요합니다.
이후 선을 긋는 루프에서
- 계산된 p 값이 양수이면,
- y 좌표값을 1 증가하고,
- p 값에 2(dy-dx) 값을 더합니다.
- 음수 이면,
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // abs
#include <unistd.h> // open/close
#include <fcntl.h> // O_RDWR
#include <sys/ioctl.h> // ioctl
#include <sys/mman.h> // mmap PROT_
#include <linux/fb.h>
int screen_width;
int screen_height;
unsigned short *fb_mapped;
void dot( int x, int y)
{
unsigned short *ptr;
ptr = fb_mapped + screen_width * y + x;
*ptr = 0xffff;
}
void line( int x1, int y1, int x2, int y2)
{
int dx, dy;
int p_value;
int inc_2dy;
int inc_2dydx;
int inc_value;
int ndx;
dx = abs( x2 -x1);
dy = abs( y2 -y1);
if ( dy <= dx)
{
inc_2dy = 2 * dy;
inc_2dydx = 2 * ( dy - dx);
if ( x2 < x1)
{
ndx = x1;
x1 = x2;
x2 = ndx;
ndx = y1;
y1 = y2;
y2 = ndx;
}
if ( y1 < y2) inc_value = 1;
else inc_value = -1;
dot( x1, y1);
p_value = 2 * dy - dx;
for (ndx = x1; ndx < x2; ndx++)
{
if ( 0 > p_value) p_value += inc_2dy;
else
{
p_value += inc_2dydx;
y1 += inc_value;
}
dot( ndx, y1);
}
}
else
{
inc_2dy = 2 * dx;
inc_2dydx = 2 * ( dx - dy);
if ( y2 < y1)
{
ndx = y1;
y1 = y2;
y2 = ndx;
ndx = x1;
x1 = x2;
x2 = ndx;
}
if ( x1 < x2) inc_value = 1;
else inc_value = -1;
dot( x1, y1);
p_value = 2 * dx - dy;
for (ndx = y1; ndx < y2; ndx++)
{
if ( 0 > p_value) p_value += inc_2dy;
else
{
p_value += inc_2dydx;
x1 += inc_value;
}
dot( x1, ndx);
}
}
}
int main( int argc, char **argv)
{
int fb_fd;
struct fb_var_screeninfo fbvar;
struct fb_fix_screeninfo fbfix;
int bytes_per_line;
int mem_size;
if ( access( "/dev/fb", F_OK))
{
printf( "프레임 버퍼 장치가 없습니다.\n");
return 0;
}
if ( 0 > ( fb_fd = open( "/dev/fb", O_RDWR)))
{
printf( "프레임 버퍼에 접근할 수 없습니다.\n");
return 0;
}
if ( ioctl( fb_fd, FBIOGET_VSCREENINFO, &fbvar))
{
printf( "FBIOGET_VSCREENINFO를 실행하지 못했습니다.\n");
return 0;
}
if ( ioctl( fb_fd, FBIOGET_FSCREENINFO, &fbfix))
{
printf( "FBIOGET_FSCREENINFO 실행하지 못했습니다.\n");
return 0;
}
screen_width = fbvar.xres; // 스크린의 픽셀 폭
screen_height = fbvar.yres; // 스크린의 픽셀 높이
bytes_per_line = fbfix.line_length; // 한개 라인 당 바이트 개수
mem_size = bytes_per_line * screen_height;
fb_mapped = ( unsigned short *)mmap( 0,
mem_size,
PROT_READ|PROT_WRITE,
MAP_SHARED,
fb_fd,
0);
if ( 5 != argc)
{
printf( "사용방법: $]./sample x1 y1 x2 y2 \n");
}
else
{
line( atoi( argv[1]), atoi( argv[2]), atoi( argv[3]), atoi(argv[4]));
}
munmap( fb_mapped, mem_size);
close( fb_fd);
return 0;
}
void bs_BresenhamLine(vector2i s, vector2i e, CImage* img, COLORREF color)
{
vector2i vStart = s;
vector2i vEnd = e;
int dx = vEnd.x-vStart.x;
int dy = vEnd.y-vStart.y;
int stepx = 1;
int stepy = 1;
if(dx<0)
{
dx = -dx;
stepx = -1;
} if(dy<0)
{
dy = -dy;
stepy = -1;
} int x = vStart.x;
int y = vStart.y; int eps = 0; if(dx>dy)
{
do
{
//m_vLinelist[m_nLineSize++] = vector2f((float)x,(float)y);
img->SetPixel(x,y,color);
if(dx==0)
break;
if((eps+=dy) << 1 >= dx)
{
y += stepy;
eps -= dx;
}
} while((x+=stepx)!=vEnd.x);
}
else
{
do
{
//m_vLinelist[m_nLineSize++] = vector2f((float)x,(float)y);
img->SetPixel(x,y,color);
if(dy==0)
break;
if((eps+=dx) << 1 >= dy)
{
x += stepx;
eps -= dy;
}
} while((y+=stepy)!=vEnd.y);
}
}
2007/03/26 11:08  http://blog.naver.com/bbosasi8/110015833947
|
Bresenham Algorithm
간단히 말해 선그리는 알고리즘이다.
(Side Note. 1965년에 발표됐단다 ㅡㅡ; 짱오래뎄네...)
그냥...
y = mx + b
(m은 기울기 y/x, b는 y축을 통과하는 점)
이렇게 for로 x쭉 돌리면 나온다.
근데 문제는 기울기에 나누기 and x곱하기 게다가 실수 ㅡㅡ;
느릴것이 자명하다.
그래서 나온것이 이 알고리즘이다.
(브레젠햄, 브레슨햄, 브렌센햄 뭐 다양하게 불리는데 별로 관심없고...)
간단한 pseudo code로 표현해보자면.
1. 에러항(error term) 변수를 하나 만들어 0을 집어 넣는다.
2. x와 y의 길이값을 가져온다.
int delta_x = x2-x1; // 단, x2>=x1
int delta_y = y2-y1; // 단, y2>=y1
3. delta_x의 절반값을 들고있는다.
int half_x = delta_x/2; // 소수점이하는 버린다.
4. x에 대해 x++씩 루프를 돌리면서 ...
y길이를 에러항에 더해주고...
에러항이 half_x보다 크다면 y++시켜준다.
for( ;x1<=x2;x1++)
{
errterm += delta_y;
if ( errterm > halfx )
{
errterm -= delta_x;
y1++;
}
}
나누기, 곱하기~ 이놈들을 없앴다. ^^
으흐흐...
어디선가 긁은 더 깔끔한한 코드
#define max( x, y) (((x) > (y)) ? (x) : (y)) // 큰수 찾는거 당연히 아시겠줘?
#define abs( x ) (((x) > 0) ? -(x) : (x)) // 절대값.
#define sign( x ) ((x) > 0 ? 1 : ((x) == 0 ? 0: (-1))) // 양수:1, 0, 음:-1
두점 ( x, y ) (x2, y2)
dx = x2 - x1;
dy = y2 - y1;
ix = abs(dx);
iy = abs(dy);
inc = max(ix, iy);
plotx = x1;
ploty = y1;
x = y = 0;
for( I = 0; I <= inc ; I++)
{
x += ix;
y += iy;
if( x > inc)
{
x -= inc;
plotx += sign(dx);
}
if( y > inc )
{
y -= inc;
ploty += sign(dy);
}
그리는 함수 ( plotx, ploty);
인 결과 즉 사원수3개의 곱으로(또는 p 가 w=0 인 벡터여도 상관없다) 나온 결과들을 
이다.
이 부분의 본문은 
는 다음과 같이 정의된다.
가 성립한다. 즉, 
라는 라디안 값을 얻을 수 있습니다.
가 됩니다.
,
