User Tools

Site Tools


base:bresenham_s_line_algorithm

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

base:bresenham_s_line_algorithm [2015-04-17 04:30] (current)
Line 1: Line 1:
 +====== Bresenham'​s line algorithm ======
  
 +Here is a C program using the allegro library that I pout up and ported to 6502 assembler. This implementation was designed by Janusz Ganczarski.
 +
 +<code c>
 +#include "​allegro.h"​
 +
 +void init();
 +void deinit();
 +void B_Line (int x1, int y1, int x2, int y2);
 +void PutPixel (int x,int y);
 +
 +int main() {
 +    ​
 +    init();
 +
 +    B_Line (1, 1, 50, 10);
 + 
 + while (!key[KEY_ESC]) {
 + /* put your code here */
 + }
 +
 + deinit();
 + return 0;
 +}
 +END_OF_MAIN()
 +
 +void init() {
 + int depth, res;
 + allegro_init();​
 + depth = desktop_color_depth();​
 + if (depth == 0) depth = 32;
 + set_color_depth(depth);​
 + res = set_gfx_mode(GFX_AUTODETECT_WINDOWED,​ 640, 480, 0, 0);
 + if (res != 0) {
 + allegro_message(allegro_error);​
 + exit(-1);
 + }
 +
 + install_timer();​
 + install_keyboard();​
 + install_mouse();​
 + /* add other initializations here */
 +}
 +
 +void deinit() {
 + clear_keybuf();​
 + /* add other deinitializations here */
 +}
 +
 +void PutPixel (int x,int y)
 +{
 +    putpixel(screen,​x,​y,​makecol(255,​255,​255));​
 +}
 +
 +//​---------------------------------------------------------------------------
 +// rysowanie linii algorytmem Bresenhama
 +//​---------------------------------------------------------------------------
 +void B_Line (int x1, int y1, int x2, int y2)
 +{
 +  // zmienne pomocnicze
 +  int d,​dx,​dy,​ai,​bi,​xi,​yi;​
 +
 +// dy - "​dlugosc"​ y
 +// dx - "​dlugosc"​ X
 +// xi , yi - kierunek rysowania w osi x , y
 +// 
 +
 +  // ustalenie kierunku rysowania oraz kroków zmiennych
 +  if (x1 < x2)
 +    {
 +      xi = 1;
 +      dx = x2 - x1;
 +    }
 +  else
 +    {
 +      xi = -1;
 +      dx = x1 - x2;
 +    }
 +
 +  // ustalenie kierunku rysowania oraz kroków zmiennych
 + if (y1 < y2)
 +   {
 +     yi = 1;
 +     dy = y2 - y1;
 +   }
 + else
 +  {
 +     yi = -1;
 +     dy = y1 - y2;
 +  }
 +
 + // pierwszy piksel
 + ​PutPixel (x1,y1);
 +
 + // oś wiodąca OX
 + if (dx > dy)
 +   {
 +     ai = (dy - dx) * 2;
 +     bi = dy * 2;
 +     d = bi - dx;
 +
 +     // warunek != zamiast < umożliwia rysowanie "pod górkę"​
 +     while (x1 != x2)
 +       {
 +         // przejście NE
 +         if (d > 0)
 +           {
 +             y1 += yi;
 +             d += ai;
 +           }
 +         // przejście E
 +         else
 +           d += bi;
 +         x1 += xi;
 +         ​PutPixel (x1,y1);
 +       }
 +   }
 + // oś wiodąca OY
 + else
 +   {
 +     ai = (dx - dy) * 2;
 +     bi = dx * 2;
 +     d = bi - dy;
 +
 +     // warunek != zamiast < umożliwia rysowanie "pod górkę"​
 +     while (y1 != y2)
 +       {
 +         // przejście NE
 +         if (d > 0)
 +           {
 +             x1 += xi;
 +             d += ai;
 +           }
 +         // przejście E
 +         else
 +           d += bi;
 +         y1 += yi;
 +         ​PutPixel (x1,y1);
 +       }
 +   }
 +}
 +
 +</​code>​
 +
 +6502 code was written using 6502sim and debugged here too , it's not optimized in any way and entire code uses only accumulator - it was written to represent that C program'​s B_Line function completely and needs further optimization to be really useful. it also uses 8bit variables only so lenght of line is limited too , and so on. '​debug'​ call should be exchanged with proper putpixel routine, in simulator '​debug'​ routine is used to watch how coords of pixels are chagning with line being drawn. after all this code is good for beginners I hope :)
 +
 +<​code>​
 +
 +
 +; defines for 6502 simulator debugging
 +io_area = $e000
 +io_cls = io_area + 0 ; clear terminal window
 +io_putc = io_area + 1 ; put char
 +io_putr = io_area + 2 ; put raw char (doesn'​t interpret CR/LF)
 +io_puth = io_area + 3 ; put as hex number
 +io_getc = io_area + 4 ; get char
 +
 +
 + *= $c000
 +
 + LDA #10 
 + STA l_x1
 + lda #4
 + STA l_y1
 + LDA #0
 + STA l_x2
 + lda #0
 + STA l_y2
 + jmp do_line
 +
 + *= $c100
 +do_line
 +; // zmienne pomocnicze
 +;//  int d,​dx,​dy,​ai,​bi,​xi,​yi;​
 +
 +;U2 = two's compliment
 +;ZU = normal binary
 +
 +;var name       ​type ​ desc
 +l_dx = $10      ; ZU - "​dlugosc"​ x (rozpietosc na osi)
 +l_dy = l_dx + 1 ; ZU - "​dlugosc"​ y 
 +l_xi = l_dx + 2 ; U2 xi,yi - kierunek rysowania w osi x , y
 +l_yi = l_dx + 3 ; U2
 +l_ai = l_dx + 4 ; U2 step
 +l_bi = l_dx + 5 ; U2 step
 +l_d  = l_dx + 6 ; U2 '​error'​
 +
 +;points
 +l_x1 = l_dx + 7 ; ZU poczatek linii
 +l_y1 = l_dx + 8 ; ZU
 +l_x2 = l_dx + 9 ; ZU koniec linii
 +l_y2 = l_dx +10 ; ZU
 +
 +
 +; // ustalenie kierunku rysowania oraz kroków zmiennych
 +;// deciding what direction to draw + steps
 +;  if (x1 < x2)
 +
 + ;if
 +x1mx2 LDA l_x1
 + CMP l_x2
 + BCC x1mx2_ ​
 + jmp x1wx2
 +
 +x1mx2_
 + ;then [x1<x2]
 + LDA #1
 + STA l_xi ; xi = 1;
 +
 + LDA l_x2
 + SEC
 + SBC l_x1
 + STA l_dx ; dx = x2 - x1
 +
 + jmp y1my2
 +
 + ;else [x1=>x2]
 +x1wx2   lda #255 ; -1 U2
 + STA l_xi ; xi = -1;
 +
 + LDA l_x1
 + SEC
 + SBC l_x2
 + STA l_dx ; dx = x1 - x2
 +
 +;// ustalenie kierunku rysowania oraz kroków zmiennych
 +;// deciding what direction to draw + steps
 +;if (y1 < y2)
 +
 +y1my2 ; [y1<y2]
 +
 + ;if
 + LDA l_y1
 + CMP l_y2
 + Bcc y1my2_
 + jmp y1wy2
 +
 +y1my2_
 + ;then
 + LDA #1
 + STA l_yi ; yi = 1;
 +
 + LDA l_y2
 + SEC
 + SBC l_y1
 + sta l_dy ; dy = y2 - y1
 +
 + jmp skok1
 +
 + ;else [y1>y2]
 +y1wy2
 + lda #255 ; -1 U2
 + STA l_yi ; yi = -1;
 +
 + LDA l_y1
 + SEC
 + SBC l_y2
 + STA l_dy ; dy = y1 - x2
 +
 +skok1
 +
 +;;;;;
 +; postaw pierwszy pixel
 +; put first pixel
 +
 +; putpix(x1,​y1);​
 +
 + jsr debug
 +
 +
 +; spr ktora os jest wiodaca
 +; check '​primary axis' (longer distance)
 + ; if (dx>​dy) ​ // (dy<dx)
 + LDA l_dx
 + CMP l_dy
 + BCC wiod_oy ; wiodaca jest OY (dy>dx)
 +
 +;// oś wiodąca OX
 +wiod_ox
 + ;ai
 + LDA l_dy
 + SEC
 + SBC l_dx
 + CLC
 + ROL ;a
 + STA l_ai ; ai = (dy-dx)*2
 +
 + ;bi
 + LDA l_dy
 + CLC
 + ROL ;a
 + STA l_bi ; bi = dy * 2
 +
 + ;d
 + LDA l_bi
 + SEC
 + SBC l_dx
 + STA l_d ; d = bi - dx
 +
 +whx1rx2 ;// while (x1 != x2)
 + LDA l_x1
 + CMP l_x2
 + BEQ l_end
 +
 +;        if (d > 0)
 +
 + LDA l_d
 + CMP #0
 + beq _a
 + BPL _else
 +_a ; <0
 + ; przejscie E
 +
 + LDA l_d
 + CLC
 + ADC l_bi
 + sta l_d ; d += bi;
 +
 + jmp _reszta
 +
 + ;else [d>0]
 +_else
 +;   // przejście NE
 +
 + LDA l_y1
 + CLC
 + ADC l_yi
 + sta l_y1 ;y1 += yi;
 +
 + LDA l_d
 + CLC
 + ADC l_ai
 + sta l_d ; d += ai;
 +
 +;end else
 +
 +_reszta
 +
 + LDA l_x1
 + CLC
 + ADC l_xi
 + sta l_x1 ; x1 += xi;
 +
 +;;// putpix(x1,​y1);​
 +
 + jsr debug
 +
 + jmp whx1rx2 ; (petla while)
 +
 + jmp l_end
 +
 +;// os wiodaca OY (dy > dx)
 +wiod_oy
 + 
 + ;ai
 + LDA l_dx
 + SEC
 + SBC l_dy
 + CLC
 + ROL ;a
 + STA l_ai ; ai = (dx-dy)*2
 +
 + ;bi
 + LDA l_dx
 + CLC
 + ROL ;a
 + STA l_bi ; bi = dx * 2
 +
 + ;d
 + LDA l_bi
 + SEC
 + SBC l_dy
 + STA l_d ; d = bi - dy
 +
 +why1ry2 ;// while (y1 != y2)
 + LDA l_y1
 + CMP l_y2
 + BEQ l_end
 +
 +
 + ; ​       if (d > 0)
 + ; then
 + LDA l_d
 + CMP #0
 + BEQ _b
 + BPL _elsey
 +_b ; <0
 +
 + LDA l_d
 + CLC
 + ADC l_bi
 + sta l_d ; d += bi;
 +
 +
 + jmp _resztay
 +
 + ;else [d>0]
 +;   // przejście NE
 +_elsey ; >0
 +
 +
 + LDA l_x1
 + CLC
 + ADC l_xi
 + sta l_x1 ;x1 += xi;
 +
 + LDA l_d
 + CLC
 + ADC l_ai
 + sta l_d ; d += ai;
 +
 +
 +;end else
 +
 +_resztay
 +
 + LDA l_y1
 + CLC
 + ADC l_yi
 + sta l_y1 ; y1 += yi;
 +
 +;;// putpix(x1,​y1);​
 +
 + jsr debug
 +
 + jmp why1ry2
 +
 +
 +; koniec ​
 +l_end
 + RTS
 +
 +; PUTPIXEL should be called instead of this debug stuff for 6502sim
 +debug ;rts
 +
 + LDY #10
 + STy io_putc
 + LDy #13
 + STy io_putc
 +
 + LDY l_x1
 + STy io_puth
 +
 + LDy #' '
 + STy io_putc
 +
 + LDy l_y1
 + STy io_puth
 +
 + rts
 +</​code>​
base/bresenham_s_line_algorithm.txt · Last modified: 2015-04-17 04:30 (external edit)