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"
 +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)