메뉴 Graphics\Algorithms\Bresenham's Algorithms에서 bres.txt +----------------------------------------+ | Bresenham의 선 및 원 알고리즘 | +----------------------------------------+ Mark Feldman이 PC-GPE를 위해 작성 e-mail address : u914097@student.canberra.edu.au myndale@cairo.anu.edu.au +-------------------------------------------+ | 이 파일은 전체 PC-GPE파일 모음집과 | | 따로 분리되어 배포되는 것을 금합니다. | +-------------------------------------------+ +------------+------------------------------------------------------------ | 포기성명서 | +------------+ 이 파일이 내적으로 포함하고 있거나 사용이 여러분과 여러분의 정신건강, 컴 퓨터, 배우자, 자녀, 애완동물 등 기타 여러분과 여러분의 존재와 관련된 모든 것에 끼치는 영향에 대한 그 어느것도 저는 책임이 없음을 가정합니다. 이 내용 으로 인해 파생될 수 있는 어떤 보증도 제공되지 않습니다. +-------+----------------------------------------------------------------- | 소 개 | +-------+ Bresenham은 상당히 솜씨 좋은 여성입니다.("is"라는 단어의 사용으로 보아 듣 기에 그가 아직 IBM에서 일하고 있다는 것을 알 수 있습니다.) 이 파일은 VGA와 같은 화상표시장치에 선과 원을 그리기 위해 개발된 알고리즘을 담고 있습니다. +-------------------+----------------------------------------------------- | 선그리기 알고리즘 | +-------------------+ 선그리기의 기본 알고리즘 수행은 다음과 같습니다.: o------- + p1 -------- | dy(델타y) ------- p2 | -------o + +----------------------------+ dx(델타x) p1 = (x1,y1), p2 = (x2, y2), x 와 y 는 둘다 p1에서 p2까지 증가합니다. dx = x2 - x1, dy = y2 - y1 and dx >= dy. 라고 하면, 다른 모든 유형의 선들도 이런 유형에서 파생될 수 있습니다. 나중에 좀더 자 세히 하도록 하죠. 우선 여러분은 다음 초기화를 해야할 필요가 있습니다.: x = x1 y = y1 d = (2 * dy) - dx x는 현재 x 위치입니다. 모든 점들이 그려질 때까지 각점을 그린 후에는 이 변 수를 1씩 증가시킵니다. y는 현재 y 위치입니다. 증분 변수(dx, dy)는 이 값을 1 증가시킬 순간을 결정 하는데 사용됩니다. d는 무엇을 하는지 흔적을 남기는데 사용되는 증분 변수입 니다.(?) 이제 여러분은 x1부터 x2까지 화면을 가로질러 루프를 실행하고 각각의 루프에 대해 다음과 같은 각점의 연산을 합니다.: PutPixel(x, y); { 현재 위치에 점을 찍습니다. } if d < 0 then d := d + (2 * dy) else begin d := d + 2 * (dy - dx); y := y + 1; end; x := x + 1; 간단하죠! +-------------------------------+----------------------------------------- | 선그리기 알고리즘 빠르게 하기 | +-------------------------------+ Bresenham 선 알고리즘을 빠르게 하는 여러 가지 쓸만한 기법들이 있습니다. 우선 2를 곱하는 법을 가르쳐드리죠. 이것은 간단히 왼쪽 비트이동 명령어로 해결됩니다.(파스칼에서는 Shl 이고, C에서는 << 입니다.) 다음 증분 변수 -더해지는 값-을 루프에서 매번 계산하지 마세요. 그러니까 미 리 계산되어 있어야 겠죠. 선의 한가지 특성은 중점에 대해 대칭이라는 것이고, 우리는 이 특성을 살려서 알고리즘을 빠르게 할 수 있습니다. 두 개의 x와 y값 (xa, ya)와 (xb, yb)를 저 장합니다. 각 쌍을 선의 시작점과 끝점으로 잡습니다. 두 점에서 점찍기를 반복 하여 선을 긋기 위해, xa에는 1을 더하고 xb에서는 1을 빼줍니다. d >= 0이면 ya에는 1을 더하고 yb에서는 1을 빼줍니다. 그다음은 xa = xb가 될 때까지 반복 하는 일만이 필요합니다. 분명한 것은 만약 증분 변수가 같은 값이 되면 초기화되었을때이며, 선의 나머 지는 단지 여러분이 점으로 이미 다 그린 선이 됩니다. 요로뷴운 y를 변형하는 방법의 배열을 가지고 알고리즘을 빠르게 할 수 있으며, 만약 선이 스스로 반복 하여 시작할 경우 이 배열을 사용합니다. 만약 여러분이 모든 값을 저장하기 위 해 Intel 레지스터를 사용한다면 아마 썩 좋을만큼 빠르게 할 수는 없을 것입니 다.(사실 속도가 더 느려질 것입니다.) 하지만 선형 텍스쳐 매핑과 같은 것을 할 때에는 유용하겠죠.(아래에서 논의되고 있습니다.) 저는 실제로 이 기법을 개선하려고 하지 않았고, 어떤 이가 해냈다는 소리를 들으면 좋겠군요. 무엇보다 기억할 것은 이들 최적화가 전체가 어셈블리로 이루어진다면 선그리 기 알고리즘의 속도를 상당히 빠르게 할 수 있다는 것입니다. 이 파일의 끝에 있는 예제 프로그램들은 제가 느린 PutPixel 루틴에서 반복 기법과 증분 변수의 부호를 판별하는데 CPU 타이밍의 40%를 소비합니다. +-------------------------------+----------------------------------------- | 선그리기 알고리즘의 다른 용도 | +-------------------------------+ 선은 m = dy / dx 일 때, y = mx + c의 방정식으로 표현되어집니다. 이것은 표 준 선형 방정식 ax + bx + c = 0의 변형입니다. 이 방정식을 사용하는 알고리즘 이 많습니다. bresenham 선그리기 알고리즘을 사용하기 좋은 것중 하나는 삼각형과 같은 오 목 다각형을 빠르게 채워넣기 하는 것입니다. 여러분은 화면삼각형의 모든 수평 선에 대해 최소값과 최대값의 배열을 설정하면 됩니다. 그런 다음 다각형의 모 든 선위의 x값을 찾아 최소값과 최대값이 적절히 조정된 상태에서 다각형의 각 변을 따라 bresenham의 알고리즘을 사용하면 됩니다. 여러분이 모든 선에 대해 작업을 마쳤다면 각각의 선의 최소값과 최대값사이의 화면수평선그리기 루프를 종료합니다. 또다른 용도는 선형 텍스쳐 매핑에 있습니다.(PC-GPE 텍스쳐 매핑관련 기사를 참조) 이 방법은 문자열 비트맵 픽셀을 사용하게 되며, 화면위의 점으로 구성된 선으로 표현되어집니다. 대체로 화면상의 수직선을 그리는데 있어 각 화면 점에 서 그려지는 비트맵 점들을 계산하는데 Bresenham의 알고리즘을 사용할 것입니 다. +-------------------+----------------------------------------------------- | 원그리기 알고리즘 | +-------------------+ 원은 상당히 대칭적인 특성을 가지고 있어서, 화면에 표시할 때 간편합니다. |y (이 도표가 50라인 모드에서 볼수 있는 원이라고 가정합시 | 다.) \ ..... / . | . 우리는 원에서 360도의 각이 있다는 걸 압니다. 우선 우리는 . \ | / . 원이 x축을 기준으로 대칭이라는 점을 알 수 있어서, 180도 . \|/ . 의 계산만이 필요하게 됩니다. 다음은 y축에 대해서도 대칭 --.---+---.-- 인 것을 알 수 있으므로, 이제 90도 각에 대한 값만을 계산 . /|\ . x 하면 됩니다. 마지막으로 45도 대각선 축에 대해 대칭이므로 . / | \ . , 45도 각에 대한 계산만 하면 되겠군요. . | . / ..... \ | | Bresenham의 원 알고리즘은 처음 45도 각도의 점들의 위치를 계산합니다. 원은 원점에 중심을 두고 있는 것으로 가정합니다. 따라서 모든 점 (x,y)에 대해서 원의 8군데에 에 그릴 점들을 계산합니다. PutPixel(CenterX + X, Center Y + Y) PutPixel(CenterX + X, Center Y - Y) PutPixel(CenterX - X, Center Y + Y) PutPixel(CenterX - X, Center Y - Y) PutPixel(CenterX + Y, Center Y + X) PutPixel(CenterX + Y, Center Y - X) PutPixel(CenterX - Y, Center Y + X) PutPixel(CenterX - Y, Center Y - X) 그럼 실제 알고리즘으로 들어가봅시다. 초기화를 할 원에 라디안값을 줍니다.: d := 3 - (2 * RADIUS) x := 0 y := RADIUS 이제 각점에 대해 다음과 같은 연산을 합니다.: 8개 반원의 점을 그립니다. if d < 0 then d := d + (4 * x) + 6 else begin d := d + 4 * (x - y) + 10 y := y - 1; end; 그리고 우리는 x = y가 될 때까지 이것을 계속합니다. 이 알고리즘에서 증분 변수에 더해지는 값(x와 y값)은 계속 바뀌므로, 우리는 이것을 미리 계산할 수 없습니다. 그러나 4로 곱셈이 되며, 이것은 비트를 왼쪽으로 두 번 이동하면 됩 니다. +---------------------+--------------------------------------------------- | 파스칼 일반 선 함수 | +---------------------+ 기본 Bresenham의 선 알고리즘은 모든 유형의 선을 다루도록 수정될 수 있습니 다. 이 부분은 dx = abs(x2 - x1)과 dy = abs(y2 - y1)을 가정합니다. 우선 dx >= dy일 때의 선을 사용합시다. 자, 만약 x1 > x2이면 여러분은 루프 를 실행하는 모든 과정에서 x로부터 1을 빼야 할 것입니다. 비슷하게 만약 y1 > y2이면 또한 d < 0 일 때 루프를 실행하는 모든 과정에서 y로부터 1을 빼야 할 것입니다. dx < dy인 선은 같은 방법으로 다루어질 수 있습니다. 여러분은 모든 dx와 dy 의 상황을 바꾸면 됩니다. 모든 경우를 다루는 가장 빠른 방법은 각각의 8개 선 유형을 위해 나름대로의 루틴을 작성하는 것입니다. 1) x1 <= x2, y1 <= y2, dx >= dy 2) x1 <= x2, y1 <= y2, dx < dy 3) x1 <= x2, y1 > y2, dx >= dy 4) x1 <= x2, y1 > y2, dx < dy 5) x1 > x2, y1 <= y2, dx >= dy 6) x1 > x2, y1 <= y2, dx < dy 7) x1 > x2, y1 > y2, dx >= dy 8) x1 > x2, y1 > y2, dx < dy 이것은 여러분에게 가장 빠른 결과를 가져다 줄 것입니다만, 또한 여러분의 코 드를 8배로 커지게 만들겠군요! 양자택일로 여러분은 여분의 변수를 선언하고 모든 선에 대한 일반 내부 루프를 사용할 수 있습니다.: numpixels = number of pixels to draw = deltax if dx >= dy or = deltay if dx < dy dinc1 = the amount to add to d when d < 0 dinc2 = the amount to add to d when d >= 0 xinc1 = the amount to add to x when d < 0 xinc2 = the amount to add to x when d >= 0 yinc1 = the amount to add to y when d < 0 yinc2 = the amount to add to y when d >= 0 다음은 이런 기법을 사용하는 간단한 예제 프로그램입니다. -------------------------------------------------------------------------- { BRESLINE.PAS - Mark Feldman에 의한 일반 선그리기 함수 이것은 최적화가 되어있지 않은 bresenham의 선그리기 알고리즘의 가장 단순한 변형입니다. 이것은 아주 아주 느린 파라다이스 확장 VGA를 가진 저의 486SX33 에서 실행할 때 모드 13h에서 초당 약 6000개의 무작위 선들을 그릴 것입니다. } procedure Line(x1, y1, x2, y2 : integer; color : byte); var i, deltax, deltay, numpixels, d, dinc1, dinc2, x, xinc1, xinc2, y, yinc1, yinc2 : integer; begin { 초기화를 위한 deltax와 deltay를 계산합니다. } deltax := abs(x2 - x1); deltay := abs(y2 - y1); { 독립변수에 기초한 모든 변수들을 초기화합니다. } if deltax >= deltay then begin { x 는 독립변수입니다. } numpixels := deltax + 1; d := (2 * deltay) - deltax; dinc1 := deltay Shl 1; dinc2 := (deltay - deltax) shl 1; xinc1 := 1; xinc2 := 1; yinc1 := 0; yinc2 := 1; end else begin { y 는 독립변수입니다. } numpixels := deltay + 1; d := (2 * deltax) - deltay; dinc1 := deltax Shl 1; dinc2 := (deltax - deltay) shl 1; xinc1 := 0; xinc2 := 1; yinc1 := 1; yinc2 := 1; end; { 오른쪽 방향으로 x와 y가 이동하는 것을 확인하세요. } if x1 > x2 then begin xinc1 := - xinc1; xinc2 := - xinc2; end; if y1 > y2 then begin yinc1 := - yinc1; yinc2 := - yinc2; end; { 에 그리기를 시작합니다. } x := x1; y := y1; { 점들을 그립니다. } for i := 1 to numpixels do begin PutPixel(x, y, color); if d < 0 then begin d := d + dinc1; x := x + xinc1; y := y + yinc1; end else begin d := d + dinc2; x := x + xinc2; y := y + yinc2; end; end; end; -------------------------------------------------------------------------- 만약 여러분이 (예를 들어) 모드 13h를 위한 선그리기 루틴을 작성한다면 어셈 블리로 내부 루프를 변환해서 모드 13h 특정 코드를 포함하여 속도를 증가시킬 수 있을 것입니다. 이번 부분은 위의 루틴과 같이 작동하지만 값은 현재 점의 메모리 주소를 담는 단일 변수(화면)에 저장됩니다. screeninc1과 screenc2는 화면의 값을 갱신합니다. -------------------------------------------------------------------------- var screen : word; screeninc1, screeninc2 : integer; . . . { 에 그리기를 시작합니다. } screen := word(y1) * 320 + x1; screeninc1 := yinc1 * 320 + xinc1; screeninc2 := yinc2 * 320 + xinc2; { 점을 찍습니다. } asm { 가능한 많은 레지스터를 사용합니다. } push $A000 pop es mov di, screen mov dx, d mov al, color mov cx, numpixels mov bx, dinc1 @bres1: { 현재 점을 찍고 증분변수가 0인지를 검사합니다. } mov es:[di], al cmp dx, 0 jnl @bres2 { D < 0 } add dx, bx { bx = dinc1 } add di, screeninc1 jmp @bres3 @bres2: { D >= 0 } add dx, dinc2 add di, screeninc2 @bres3: loop @bres1 end; --------------------------------------------------------------------------