In high school geometry, we all learned that the formula for a line is:
Here is an implementation of Bresenham's line algorithm:
In the next article, I will start an unit that has all of the common code. This will eliminate
copying of the same code for each example program.
Last time, we wrote routines that drew vertical and horizontal lines. Although vertical and horizontal lines are very useful, arbitrary lines are more so. Where axial lines are useful for user interfaces, arbitrary lines are useful for 3 dimensional wire frame stuff. They give more flexibility and more control to the programmer. We will start with simple floating point lines...
In this section we will derive how to use floating point numbers to draw lines...
y = mx + b
Where m is the slope, and b is the Y-Offset. To make this more computer applicable, we can do this to it:
Y - Y1 = m(X - X1)
This is commonly known as the point-slope formula for lines. Now, to get a line, all we have to do is know Y1, X1, and m. We then vary x from 0 to X2 - X1. We take the resultant Y value and plot the pixel at (X, Y). Here is some pseudo-code:
PROCEDURE Line(X1, Y1, X2, Y2 : Real; Color : BYTE);
VAR m, X, Y : Real;
BEGIN
m := (Y2-Y1) / (X2-X1);
IF (X2-X1) > (Y2-Y1) THEN
FOR X := X1 TO X2 DO { X-Major }
BEGIN
Y := m*(X-X1) + Y1; { Could be incrementally calculated... }
SetPixel(INT(X), INT(Y), Color);
END
ELSE
FOR Y := Y1 TO Y2 DO { Y-Major }
BEGIN
X := (Y-Y1) / m + X1; { This is just Y := m*X + Y1 }
SetPixel(INT(X), INT(Y), Color); { rearranged to solve for X }
END;
END;
As you can see, we have to split the line up into two cases, X-Major and Y-Major. An X-Major line
is longer horizontally than vertically. A Y-Major line is longer vertically that horizontally. If
we didn't make this distinction, then the routine would skip pixels. Here is a Y-Major Line:
* *
*
*
* *
*
*
* *
*
*
* *
*
*
Drawn with a Drawn with a
Y-Major Loop X-Major Loop
As you can see, the difference is emmense. The problem with this routine is that being floating
point, it is very slow. There are a number of alternatives to floating point lines though:
A man by the name of Bresenham developed a line algorithm in 1965 that uses no floating point at all. In it's inner loop, it consists of compares, jumps, and adds. It is a very common line implementation. Although it is a LOT faster than a floating point algorithm, it is ineffiecient on 80x86 processors because of the jump required in it's inner loop. This can be eliminated by using the fixed point algorithm described in the next section. Because of this, I won't really describe how it works...
PROCEDURE BresenhamLine(X1, Y1, X2, Y2 : INTEGER; Color : BYTE);
VAR
DeltaX, DeltaY, { Change in X and Y }
Inc1, Inc2, { Amount to increment }
D, { Decision variable }
X, Y : INTEGER; { Current position }
BEGIN
DeltaX := X2-X1; DeltaY := Y2-Y1;
Inc1 := DeltaY SHL 1; { Increment value 1 }
Inc2 := (DeltaY-DeltaX) SHL 1;{ Increment value 2 }
D := Inc1-DeltaX; { Initial d value }
X := X1; Y := Y1;
SetPixel(X, Y, Color);
WHILE X < X2 DO
BEGIN
IF D < X1 THEN
BEGIN
D := D + Inc1;
INC(X);
END
ELSE
BEGIN
D := D + Inc2;
INC(X);
INC(Y);
END;
SetPixel(X, Y, Color);
END;
END;
This is the same program as last time, but it includes the Bresenham line routine and does a
timing test on it. The Bresenham routine is unoptimized, but it isn't too bad...
PROGRAM ArbitraryLineExample;
USES CRT; { Include the "ReadKey" function }
TYPE
ScreenBufferType = ARRAY[0..63999] OF BYTE;
ScreenBufferPtr = ^ScreenBufferType;
ScreenType = RECORD
Buffer : ScreenBufferPtr;
YTable : ARRAY[0..199] OF WORD; { Y can range from 0 - 199 }
Width : WORD;
END;
VAR
Screen : ScreenType;
PROCEDURE CalcScreenY(Width : WORD); { Allow for future expansion }
VAR I : INTEGER;
BEGIN
FOR I := 0 TO 199 DO
Screen.YTable[I] := I*Width;
END;
PROCEDURE InitGraph;
BEGIN
ASM
mov AX, 0013h { Function 0, mode 13h }
int 10h
END;
Screen.Buffer := PTR($A000, 0); { Set up the screen buffer pointer }
Screen.Width := 320;
CalcScreenY(320);
END;
PROCEDURE CloseGraph; ASSEMBLER;
ASM
mov AX, 0003h { Function 0, Mode 3}
int 10h
END;
PROCEDURE SetPixel(X, Y : INTEGER; Color : BYTE); ASSEMBLER;
ASM
les DI, Screen.Buffer
add DI, X
mov BX, Y { Y is an index into the ScreenY array }
add BX, BX { Multipy by two because each entry is a word }
add DI, DS:[BX+OFFSET Screen.YTable]
mov AL, Color
mov ES:[DI], AL
END;
PROCEDURE HLine(X1, Y, X2 : INTEGER; Color : BYTE); ASSEMBLER;
ASM
les DI, Screen.Buffer { Only load ES and DI at the start }
add DI, X1
mov BX, Y { Y is an index into the ScreenY array }
add BX, BX { Multipy by two because each entry is a word }
add DI, DS:[BX+OFFSET Screen.YTable]
{ At this point, DI points to the first pixel in the line. }
{ Now we will calculate how many times to loop (X2-X1+1)... }
mov CX, X2
mov AL, Color { Load the color }
mov AH, AL
sub CX, X1
inc CX
test DI, 1 { Are we on an odd address? }
jz @Even
stosb { Store the first byte }
dec CX { Decrement the counter one }
@Even: { Even address }
shr CX, 1 { Do half as many transfers }
rep stosw { Copy all of the even words }
adc CX, 0 { If there is a pixel left over, set CX to 1 }
rep stosb { If there is a pixel left over, fill it! }
END;
PROCEDURE VLine(X, Y1, Y2 : INTEGER; Color : BYTE); ASSEMBLER;
ASM
les DI, Screen.Buffer { Only load ES and DI at the start }
add DI, X
mov BX, Y1 { Y1 is an index into the ScreenY array }
add BX, BX { Multipy by two because each entry is a word }
add DI, DS:[BX+OFFSET Screen.YTable]
{ At this point, DI points to the first pixel in the line. }
{ Now we will calculate how many times to loop (Y2-Y1+1)... }
mov CX, Y2
sub CX, Y1 { Calculate the Delta X }
inc CX
mov DX, Screen.Width { 320 }
mov AL, Color { Load the color }
mov BX, CX
and BX, 3 { Get remainder of CX DIV 4 }
shr CX, 2 { Repeated four times }
add BX, BX { Index into a word table}
jmp WORD PTR CS:[@JumpTable+BX]
@JumpTable:
dw OFFSET @Iteration1
dw OFFSET @Iteration4
dw OFFSET @Iteration3
dw OFFSET @Iteration2
@Iteration1:
mov ES:[DI], AL { Set a pixel }
add DI, DX { Increment address }
@Iteration2:
mov ES:[DI], AL { Set a pixel }
add DI, DX { Increment address }
@Iteration3:
mov ES:[DI], AL { Set a pixel }
add DI, DX { Increment address }
@Iteration4:
mov ES:[DI], AL { Set a pixel }
add DI, DX { Increment address }
dec CX { Decrement loop counter }
jns @Iteration1 { Repeat if neccesary }
END;
PROCEDURE BresenhamLine(X1, Y1, X2, Y2 : INTEGER; Color : BYTE);
VAR
DeltaX, DeltaY, { Change in X and Y }
Inc1, Inc2, { Amount to increment }
D, { Decision variable }
X, Y : INTEGER; { Current position }
BEGIN
DeltaX := X2-X1; DeltaY := Y2-Y1;
D := 2*DeltaY-DeltaX; { Initial d value }
Inc1 := DeltaY SHL 1; { Increment value 1 }
Inc2 := (DeltaY-DeltaX) SHL 1;{ Increment value 2 }
X := X1; Y := Y1;
SetPixel(X, Y, Color);
WHILE X < X2 DO
BEGIN
IF D < X1 THEN
BEGIN
D := D + Inc1;
INC(X);
END
ELSE
BEGIN
D := D + Inc2;
INC(X);
INC(Y);
END;
SetPixel(X, Y, Color);
END;
END;
FUNCTION ReadTimer : LONGINT; ASSEMBLER;
ASM mov AX, 40h; mov ES, AX; mov AX, ES:[6Ch]; mov DX, ES:[6Eh] END;
VAR
I, J : INTEGER;
BresTimer,
HLineTimer,
VLineTimer : LONGINT;
BresTime,
HLineTime,
VLineTime : REAL;
BEGIN
InitGraph;
HLineTimer := ReadTimer;
FOR J := 0 TO 99 DO
FOR I := 0 TO 199 DO
HLine(0, I, 319, I);
HLineTimer := ReadTimer - HLineTimer;
HLineTime := HLineTimer / 18.2;
VLineTimer := ReadTimer;
FOR J := 0 TO 99 DO
FOR I := 0 TO 319 DO
VLine(I, 0, 199, I);
VLineTimer := ReadTimer - VLineTimer;
VLineTime := VLineTimer / 18.2;
BresTimer := ReadTimer;
FOR J := 0 TO 99 DO
FOR I := 0 TO 199 DO
BresenhamLine(0, 0, 319, 199, I);
BresTimer := ReadTimer - BresTimer;
BresTime := BresTimer / 18.2;
{ WHILE NOT KeyPressed DO; {}
CloseGraph;
WRITELN('HLine time: ', HLineTime :4:4, ' seconds');
WRITELN('Number of pixels in HLine test: ', 100*200*320);
WRITELN('Millions of pixels per second: ', (100*200*320) / HLineTime / 1000000:4:6);
WRITELN;
WRITELN('VLine time: ', VLineTime :4:4, ' seconds');
WRITELN('Number of pixels in VLine test: ', 100*320*200);
WRITELN('Millions of pixels per second: ', (100*320*200) / VLineTime / 1000000:4:6);
WRITELN;
WRITELN('BresenhamLine time: ', BresTime :4:4, ' seconds');
WRITELN('Number of pixels in BresLine test: ', 100*320*200);
WRITELN('Millions of pixels per second: ', (100*320*200) / BresTime / 1000000:4:6);
WRITELN;
WRITELN('Press any key to continue or any other key to quit');
ReadKey;
END.