Graphics Programming: Fast Arbitrary Lines

Fast Arbitrary Lines

Table of Contents:
It's about time!
How we do it: High level
The real one: Into Assembly
A example program for lines

FINALLY, after all of this, we are ready to assemble a completed line function. No longer will we be constrained to horizontal or vertical or X-Major etc.... The following routine encapsulates all of the FAST line functions we have developed before, and it puts them in an easy to call procedure that has very little overhead. After this, we're done with silly little line routines!

How we do it: High Level

All our "Line" procedure has to do now is distribute calls to it among the line subroutines... This allows us to get great speed with convienient calling conventions... Here's the Pascal equivilant of the real assembly routine...

PROCEDURE Line(X1, Y1, X2, Y2 : INTEGER; Color : BYTE);
VAR DeltaX, DeltaY : INTEGER;
BEGIN
  DeltaX := ABS(X2-X1);
  DeltaY := ABS(Y2-Y1);
  IF DeltaY = 0 THEN 
    { Sort points }
    HLine(X1, Y1, X2, Color)
  ELSE IF DeltaX = 0 THEN
    { Sort points }
    VLine(X1, Y1, Y2, Color)
  ELSE IF DeltaY > DeltaX THEN
    { Sort points }
    YMajorLine(X1, Y1, X2, Y2, Color)
  ELSE
    { Sort Points }
    XMajorLine(X1, Y1, X2, Y2, Color);
END;

The { Sort Points } mean that there we would sort the points so that they are in the correct order for the line subroutine... I didn't include them, because it just convolutes otherwise simple code.

The real one: Into Assembly

Okay, the following is the real routine that we will add to our GraphPro library... It is very fast and very (I hope) optimized.

PROCEDURE Line(X1, Y1, X2, Y2 : INTEGER; Color : BYTE); ASSEMBLER;
ASM
  mov AX, Y2; sub AX, Y1
  cwd; xor AX, DX; sub AX, DX  { DeltaY := ABS(Y2-Y1) }
  jz @DeltaYIsZero
  mov BX, AX
  and DL, 2
  mov CL, DL  { Set bit #1 if Y's are backwards }

  mov AX, X2; sub AX, X1
  cwd; xor AX, DX; sub AX, DX  { DeltaX := ABS(X2-X1) }
  jz @DeltaXIsZero
  and DL, 1
  or CL, DL   { Set bit #0 if X's are backwards }

  cmp AX, BX
  jae @XMajorLine      { IF DeltaY > DeltaX THEN }

  and CL, 2
  jz @NoSwap3
  mov AX, X1
  xchg X2, AX
  mov X1, AX
  mov AX, Y1
  xchg Y2, AX
  mov Y1, AX
@NoSwap3:
{ push X1 push Y1 push X2 push Y2 push WORD [Color]
  call YMajorLine      { YMajorLine(X1, Y1, X2, Y2, Color) }
  pop BP
  jmp YMajorLine   { Everything is already pushed!  Just jmp to proc! }

@XMajorLine:           { IF DeltaX >= DeltaY THEN }
  and CL, 1
  jz @NoSwap4
  mov AX, X1
  xchg X2, AX
  mov X1, AX
  mov AX, Y1
  xchg Y2, AX
  mov Y1, AX
@NoSwap4:
{ push X1 push Y1 push X2 push Y2 push WORD [Color]
  call XMajorLine      { XMajorLine(X1, Y1, X2, Y2, Color) }
  pop BP
  jmp XMajorLine   { Everything is already pushed!  Just jmp to proc! }

@DeltaYIsZero:
  mov AX, X1
  mov CX, X2
  mov BX, Y1
  cmp AX, CX
  jb @NoSwap1
  xchg AX, CX
@NoSwap1:
  push AX
  push BX
  push CX
  push WORD [Color]
  call HLine        { HLine(X1, Y1, X2, Color) }
  jmp @Done

@DeltaXIsZero:
  mov AX, X1
  mov BX, Y1
  mov DX, Y2
  and CL, 2
  jz @NoSwap2
  xchg BX, DX
@NoSwap2:
  push AX
  push BX
  push DX
  push WORD [Color]    { VLine(X1, Y1, Y2, Color) }
  call VLine

@Done:
END;

Notice that when calling XMajorLine and YMajorLine, I just pop BP, and jmp to the procedure. The reason that I can get away without pushing all of the values back onto the stack is that they already ARE on the stack. When calling the Line procedure, the correct values for the procedures were pushed... I simply simulate that and let the line subroutine do my ret for me. If you don't get it, then don't worry about it... It's just a minor optimization.

Example Program

The following program draws lines in a circle from the middle of the screen. It utilizes the entire line routine, calling each sub-procedure at some point... It then times it, for comparison to the HLine and VLine tests earlier: (Note: You need the new version of the GraphPro library for this program to work)

-----------------] Example Starts here [-----------------

PROGRAM RunLengthTester;
USES GraphPro;

VAR
  I, J : INTEGER;
  LineTimer : LONGINT;
  LineTime  : REAL;
  NumLines  : LONGINT;
  NumPixels : LONGINT;
BEGIN
  InitGraph;
  LineTimer := ReadTimer;

  FOR J := 1 TO 255 DO
  BEGIN
    FOR I := 0 TO 319 DO
      Line(159, 99, I, 0, (I AND 1)*J);
    FOR I := 0 TO 199 DO
      Line(159, 99, 319, I, (I AND 1)*J);
    FOR I := 319 DOWNTO 0 DO
      Line(159, 99, I, 199, (I AND 1)*J);
    FOR I := 199 DOWNTO 0 DO
      Line(159, 99, 0, I, (I AND 1)*J);
  END;
  LineTimer := ReadTimer - LineTimer;
  LineTime := LineTimer / 18.2;

  CloseGraph;
  NumLines  := 255*(320+200+320+200);
  NumPixels := 255*(320*100+200*160+320*100+200*160);
  WRITE('I just drew ', NumLines, ' lines ');
  WRITELN('and ', NumPixels, ' pixels!');

  WRITELN('Line time: ', LineTime :4:4, ' seconds');
  WRITELN('Millions of pixels per second: ', NumPixels / LineTime / 1000000:4:6);
  WRITELN('Lines per second: ', NumLines / LineTime :4:6);
END.

-----------------] Example Ends here [-----------------

Created by Chris Lattner