/*---------------------------------------------------------------------------- bresen.asm: Bresenham Line Drawing ------------------------------------------------------------------------------ Description: Implements Bresenham Line Drawing Algorithm, a line-drawing algorithm which draws pixels approximating a line between two specified endpoints. Since the algorithm is working in pixel coordinates, it is basically an integer operation. The set_pixel macro, used to turn on the chosen pixel, is application-dependent. Andrew Glassner's book "Graphics Gems", cited in the References section below, gives an implementation of this algorithm in which both pixel calculations and accumulation of an error term are done in fixed-point, for a total of four fixed-point operations in the inner loop. Although the ADSP-21020 is a floating-point processor, the ability to use both the ALU and Data Address Generators in parallel allow the required four fixed-point operations to be done in two cycles. The following paragraphs explain this operation. If the inner loop of the Bresenham algorithm is implemented in a straightforward way, with all calculations performed in the ALU, it would require 5 instructions (not including the set_pixel operation). In this straightforward implementation, all macro registers (ERR, Y, X, SX, SY, AX, AY) are in register file, and four fixed-point ALU operations are required, 2 of which are conditional, 2 unconditional. The five instructions necessary are: do lp until lce; if lt jump noyinc; Y = Y + SY; ERR = ERR - AX; noyinc: X = X + SX; ERR = ERR + AY; lp: set_pixel(X,Y); /* application-dependent macro */ If the inner loop is implemented with the error term ERR calculated in the ALU and the X and Y coordinates calculated in DAG1, the loop can be implemented in two instructions: do lp until lce; if ge ERR = ERR - AX, modify(Y,SY); ERR = ERR + AY, modify (X,SX); lp: set_pixel(X,Y); ----------------------------------------------------------------------------- NOTE on the set_pixel MACRO: For some graphics applications, the set_pixel macro may be nothing more than setting a memory location to a constant value. The constant value may simply be 1, or it may be a 24-bit integer indicating the line color. The inner loop used in this application could be as simple as a single instruction: do lp-1 until lce; if ge ERR = ERR - AX, modify(P,SY); ERR = ERR + AY, modify (P,SX); dm(P) = CONST; lp: If image memory was in Data Memory and was organized as M rows each N pixels long, P would be a DAG1 index register, SY would be +/-N, SX would be +/-1, and CONST would be a register file register containing the constant value which the pixel should be set to. This implies that the entire Bresenham inner loop, including setting the chosen pixel, could be performed in as few as three instructions. ----------------------------------------------------------------------------- Program Characteristics: Calling Registers: r0 = x1 = x coord on line start r1 = y1 = y coord on line start r2 = x2 = x coord on line end r3 = y2 = y coord on line end l2 = 0 l3 = 0 Registers Altered: r0-r11, i2, m2, i3, m3 Computation Time = 2N + set_pixel*(N+1) + 25 cycles where N = number of points = max (abs(x2-x1),abs(y2-y1)) = 326 cycles for a 100-pixel line = 76,700 100-pixel lines/second @ 25MHz ----------------------------------------------------------------------------- Author: Jim Donahue, Analog Devices DSP Division References: Glassner, Andrew S. (1990), "Graphics Gems", Academic Press, Inc. p.99-100 Revised: 9-MAY-91 ----------------------------------------------------------------------------*/ /* set_pixel is a user-defined macro. Currently, it just writes out the generated X,Y pairs to data memory for inspection. */ #define set_pixel(x,y) r0=x; dm(i0,m0)=r0; r0=y; dm(i0,m0)=r0 #define X1 r0 #define Y1 r1 #define X2 r2 #define Y2 r3 #define X i2 #define Y i3 #define XLEN l2 #define YLEN l3 #define XSTP 1 #define YSTP 1 #define SX m2 #define SY m3 #define DX r4 #define DY r5 #define AX r6 #define AY r7 #define RSX r8 #define RSY r9 #define ERR r11 #define NEG_ONE r10 #define LEFT by 1 #define RIGHT by NEG_ONE /*---------------------------------------------------------------------------- Bresenham Line Drawing Function Label Meaning --------- ------------------------------- bresen start of function oct1 octant 1 line-drawing algorithm lp1 octant 1 loop oct2 octant 2 line-drawing algorithm lp2 octant 2 loop ----------------------------------------------------------------------------*/ .SEGMENT /pm pm_code; .GLOBAL bresen; bresen: NEG_ONE = -1; XLEN = 0; YLEN = 0; RSX = 0; RSY = 0; DX = X2 - X1; if ge RSX = RSX + XSTP; /* if ( x2>x1 ) step x-coord up */ if lt RSX = RSX - XSTP; /* if ( x2>x1 ) step x-coord down */ DY = Y2 - Y1; if ge RSY = RSY + YSTP; /* if ( y2>y1 ) step y-coord up */ if lt RSY = RSY - YSTP; /* if ( y2>y1 ) step y-coord down */ AX = abs DX; AX = ashift AX LEFT; /* X error term = 2 * ( abs(x2-x1) ) */ AY = abs DY, SX = RSX; /* save register-SX into modify register */ AY = ashift AY LEFT; /* Y error term = 2 * ( abs(y2-y1) ) */ comp(AX,AY), SY = RSY; /* save register-SY into modify register */ if lt jump oct2(db); /* if ( abs(x2-x1) > abs(y2-y1) ) { */ X = X1; /* computeOctant1; */ Y = Y1; /* } else { computeOctant2; } */ oct1: set_pixel(X,Y); /* initial error = 2 * ( abs(y2-y1) - abs(x2-x1) ) */ ERR = ashift AX RIGHT; ERR = AY - ERR, lcntr=ERR; do lp1-1 until lce; if ge ERR = ERR - AX, modify(Y,SY); ERR = ERR + AY, modify (X,SX); set_pixel(X,Y); lp1: rts; oct2: set_pixel(X,Y); /* initial error = abs(x2-x1) - abs(y2-y1))*2 */ ERR = ashift AY RIGHT; ERR = AX - ERR, lcntr = ERR; do lp2-1 until lce; if ge ERR = ERR - AY, modify(X,SX); ERR = ERR + AX, modify (Y,SY); set_pixel(X,Y); lp2: rts; .ENDSEG;