제목 : 안녕하세요 허르미입니다. 오늘은 Line 과 Circle 에 대 해서 알아보도록 하겠읍니다. Line 의 알고리즘은 몇가지가 있지 만 가장 접하기 쉬운 알고리즘인 Bresenham's Algorithm 을 사용 하였읍니다. 이 알고리즘의 주요 특색은 해상도가 제한되어 있는 디스플레이 시스템에서 덧셈만으로 좌표를 결정하여 선을 그릴수 있게 해주므로 빠른 속도를 구현할 수 있다는 장점이 있읍니다. 그럼 Pseudo Code 를 보겠읍니다. (x1,y1)~(x2,y2) 까지 선을 긋는 알고리즘 dx = x2-x1 dy = y2-y1 ix = absolute value of dx iy = absolute value of dy inc = MAX(ix,iy) plotx = x1 ploty = y1 x = 0 y = 0 putpixel(plotx,ploty) for i=0 to inc { x+=ix y+=iy plot=FALSE if (x>inc) { plot=TRUE x-=inc if (dx>0) plotx++ if (dx<0) plotx-- } if (y>inc) { plot=TRUE y-=inc if (dy>0) ploty++ if (dy<0) ploty-- } if (plot) putpixel(plotx,ploty) } Line 루틴을 만드는데 있어서 위의 알고리즘을 거의 그대로 구현 하는데 역점을 두었으므로 이해하기가 어렵지는 않을 듯합니다. 알고리즘 자체에 대한 설명은 다소 전문적인 내용이 될 것같아서 생략하도록 하겠읍니다.그럼 문제는 위의 알고리즘을 Inline Assembly 로 Implement 하는 방법이 되겠읍니다. 이것도 역시 허 큘레스 버전과 VGA 버전이 있는데 점을 찍는 것 자체를 저번 강 좌의 hgVPlotXy 등을 이용하는 것이 아니고 내부에 직접 포함하 고 있읍니다. 그럼 소스를 보시겠읍니다. 차례로 VGA 루틴, HERC 루틴입니다. * VGA 루틴 * void hgVLineG(int x1,int y1,int x2,int y2,char color) { int vdx,vdy,vix,viy,vinc; asm mov ax,0a000h /* setment */ asm mov es,ax asm mov dx,03ceh asm mov ax,0205h /* write mode 2 */ asm out dx,ax asm mov ax,x2 /* calculate vdx,vdy,idx,idy */ asm sub ax,x1 asm mov vdx,ax asm test ax,0x8000 asm jz n1 asm neg ax n1: asm mov vix,ax asm mov ax,y2 asm sub ax,y1 asm mov vdy,ax asm test ax,0x8000 asm jz n2 asm neg ax n2: asm mov viy,ax asm mov ax,vix /* vinc is MAX of vix & viy */ asm cmp ax,viy asm jc n3 asm mov vinc,ax asm jmp next2 n3: asm mov ax,viy asm mov vinc,ax next2: asm mov ax,WORD PTR y1 /* calculate bx */ asm mov bx,80 asm mul bx asm mov bx,ax asm mov dx,WORD PTR x1 asm mov ax,dx asm shr dx,1 asm shr dx,1 asm shr dx,1 asm add bl,dl asm adc bh,0 asm and al,07h asm mov cl,al asm mov ah,080h asm shr ah,cl /* ah is bitmask */ asm mov dx,03ceh asm mov al,8 /* first plot */ asm out dx,ax asm mov al,es:[bx] asm mov al,color asm mov es:[bx],al asm mov si,0 /* si is X */ asm mov di,0 /* di is Y */ asm mov cx,vinc /* loop counter */ loops: asm mov al,0 /* al is plot */ asm add si,vix /* x+=ix; */ asm add di,viy /* y+=iy; */ asm cmp si,vinc /* si > inc ? */ asm jle yproc asm mov al,1 /* plot is 1 */ asm sub si,vinc asm cmp WORD PTR vdx,0 asm jle next3 asm shr ah,1 /* plotx++ */ asm jnz yproc asm mov ah,080h /* mask reset */ asm inc bx /* incre offset */ asm jmp yproc next3: asm shl ah,1 /* plotx-- */ asm jnz yproc asm mov ah,01h asm dec bx /* decre offset */ yproc: asm cmp di,vinc asm jle lpend asm mov al,1 /* plot is 1 */ asm sub di,vinc asm cmp WORD PTR vdy,0 asm jle next4 asm add bx,80 /* ploty++ */ asm jmp lpend next4: asm sub bx,80 lpend: asm cmp al,1 asm jnz end asm mov al,8 /* plot */ asm out dx,ax asm mov al,es:[bx] asm mov al,color asm mov es:[bx],al end : asm loop loops } * HERC 루틴 */ #define ZERO 13 void hgHLineG(int x1,int y1,int x2,int y2,char color) { int vdx,vdy,vix,viy,vinc; unsigned offset=ret_herc_offset(y1); asm mov ax,0b000h /* segment */ asm mov es,ax asm mov ax,x2 /* calculate vdx,vdy,idx,idy */ asm sub ax,x1 asm mov vdx,ax asm test ax,0x8000 asm jz n1 asm neg ax n1: asm mov vix,ax asm mov ax,y2 asm sub ax,y1 asm mov vdy,ax asm test ax,0x8000 asm jz n2 asm neg ax n2: asm mov viy,ax asm mov ax,vix /* vinc is MAX of vix & viy */ asm cmp ax,viy asm jc n3 asm mov vinc,ax asm jmp next2 n3: asm mov ax,viy asm mov vinc,ax next2: asm mov bx,offset asm mov dx,WORD PTR x1 asm mov ax,dx asm shr dx,1 asm shr dx,1 asm shr dx,1 asm add bl,dl asm adc bh,0 asm and al,07h asm mov cl,al asm mov ah,080h asm shr ah,cl /* ah is bitmask */ asm cmp BYTE PTR color,ZERO asm jz n4 asm or es:[bx],ah asm jmp n5 n4: asm not ah asm and es:[bx],ah asm not ah n5: asm mov si,0 /* si is X */ asm mov di,0 /* di is Y */ asm mov cx,vinc /* loop counter */ loops: asm mov al,0 /* al is plot */ asm add si,vix /* x+=ix; */ asm add di,viy /* y+=iy; */ asm cmp si,vinc /* si > inc ? */ asm jle yproc asm mov al,1 /* plot is 1 */ asm sub si,vinc asm cmp WORD PTR vdx,0 asm jle next3 asm shr ah,1 /* plotx++ */ asm jnz yproc asm mov ah,080h /* mask reset */ asm inc bx /* incre offset */ asm jmp yproc next3: asm shl ah,1 /* plotx-- */ asm jnz yproc asm mov ah,01h asm dec bx /* decre offset */ yproc: asm cmp di,vinc asm jle lpend asm mov al,1 /* plot is 1 */ asm sub di,vinc asm cmp WORD PTR vdy,0 asm jle next4 asm add bx,02000h /* ploty++ */ asm cmp bx,08000h asm jb noadd asm sub bx,07fb0h noadd: asm jmp lpend next4: asm sub bx,02000h asm cmp bx,08000h asm jb lpend asm add bx,07fb0h lpend: asm cmp al,1 asm jnz end asm cmp BYTE PTR color,ZERO asm jz n6 asm or es:[bx],ah asm jmp end n6: asm not ah asm and es:[bx],ah asm not ah end : asm loop loops } 조금 길지만 알고리즘을 그대로 구현했으므로 다른 책등에서 나 온 선 알고리즘 보다 느릴지도 모르지만 보기는 편하실 겁니다. 주석과 알고리즘을 비교해 보시면 이해에는 그다지 어려움이 없 을 겁니다. 그럼 알고리즘을 구현함에 있어 약간 차이가 있는 부 분만을 살펴보겠읍니다. 알고리즘에서 보면 잘 나타나지 않지만 구현함에 있어 가장 시간이 많이 걸리는 부분은 점을 찍는 부분 입니다. 알고리즘에서 보면 plotx,ploty 를 점을 찍는 위치로 두 고 있는데,plotx,ploty 를 직접 계산하여 (x,y) 에 점을 찍어주 는 루틴으로 넘겨주어 점을 찍는 것입니다. 하지만 실제 구현에 서는 속도의 향상을 위해서 다음과 같이 하고 있읍니다. plotx 는 mask 로 대신합니다. ploty 는 화면옵셋으로 대신합니다. 즉 (x1,y1) 을 가지고 mask 와 offset 을 계산합니다. 이 계산식은 다음과 같습니다. offset=y1*80+x1; ( VGA 의 경우 ) ( 허큘레스는 ret_herc_offset 함수 이용 ) mask =0x80 >> (x1%8); 이것을 Inline Assembly 로 표현한 식을 위의 소스에서 볼 수 있 읍니다. 일단 계산해놓으면 plotx,ploty 를 따로 계산하는 것이 아니라 이 값을 곧바로 이용합니다. plotx++ 는 mask 를 오른쪽 으로 한번 쉬프트 합니다. 단 mask 가 0 이 되면 (Carry 발생) offset 을 오른쪽으로 1 더하고 mask 는 0x80 ( 2 진수 10000000 ) 으로 해줍니다. plotx-- 는 반대로 mask 를 왼쪽으로 한번 쉬 프트 합니다. 단 mask 가 0 이 되면 (Carry 발생) offset 에서 1 을 빼고 mask 를 1 ( 2 진수 00000001 ) 로 해줍니다. ploty++ 는 offset+=80 으로 해결합니다. ploty-- 는 offset-=80 입니다. 이 값을 알고 있으므로 비트 마스크를 mask 로 하고 쓰기모드 2 번에서 A000:Offset 에 씀으로써 점을 찍을 수 있는 것입니다.( 허큘레스는 컬러가 ZERO 가 아니면 OR,ZERO 이면 반전해서 AND 한다.즉 ZERO 컬러 처리 ) 이것은 독립된 점찍는 모듈인 hgPlotXy 를 이용할때에 비해서 몇가지 장점이 있읍니다. 우선 그래픽 좌표를 비트 마스크로 계산하는 루틴을 중복해서 계산할 필요가 없읍니다. 또한 포트 세팅,초기화를 한번만 해주면 되므 로 이 처리를 해주는 것은 plotx,ploty 를 계산하는 방식보다 50 % 정도 빠른 속도를 보여줍니다. 다른 부분도 옵티마이징할 부분 이 많이 보입니다. 우선 곳곳에 나타나 있는 불필요한 jmp 를 없 애줄 수 있읍니다. jmp 는 느린 명령입니다. 이러한 jmp 를 옵티 마이징함으로써 속도를 높일 수 있겠읍니다. 또한 점을 하나씩 찍는 것이 아니라 offset 이 바뀔때마다 한번에 모아서 찍어주는 방법을 택할 수도 있읍니다. 하지만 여기에서는 알고리즘의 표현 방법등 간결한 소스를 보이기 위해서 불필요한 부분을 삭제하였 읍니다. 그럼 이번에는 원을 그리는 알고리즘을 보겠읍니다. 원을 그리기 위해서는 cos,sin 등 삼각함수의 계산이 필요합니다. 이 삼각함 수는 내장함수를 이용해서 구할 수 있지만 사실 Coprocessor 가 없고서는 엄청나게 느립니다. 보통 테일러 급수등을 이용해서 cos,sin 등을 근사치계산을 해서 쓰는데 이경우도 역시 실수의 누승을 계산해야 하므로 그다지 좋은 알고리즘이라고 할 수는 없 겠읍니다. Bresenham's circle Algorithm 은 이것을 해결한 알고 리즘으로 놀라울만치 간단한 계산으로 원을 그려줍니다.간단한 곱셈과 덧셈만으로 원을 그릴 수 있읍니다. 그럼 알고리즘을 보 겠읍니다. x=0,반지름을 y 라 하면 d=3-y*2 while (x