Very Computer

People who crave speed and competition,

There has been a lot of talk to who or how to create the fastest line
drawing routine. Well I think its time to put our code where our postings
are (money where our mouth is). We could have a contest or something. I've
writen a program to profile line drawing under two methods (fixed and
bresenham). Both of my routines are witten completly in C. The rules for
the contest should be as follows:

For the DOS clones

Almost anything goes in software (no hardware).
You can use asm, C pascal....
You can use any amount of memory for tables and code.
Flat mode should be used to avoid far jumps and far memory access.
Lines should be drawn to 320x200x256 graphics mode to avoid bank switches
Lines should also be tested in a local memory buffer to avoid outs.
All lines should reside in the window no cliping should be done.
Random points should be in a table of 10000 points
Otherwise it should follow the calling conventions shown in the main part
of the attached program.

For any other computers use your judgment..

Good luck

Andrew Hallendorff
Andyr...@aol.com

Sample output from my program compiled with watcom C/C++ 10a.
Compiler swithces /oneatx /zp4 /5r

On a 486dx2 80 with ATI pci graphics pro ultra 2m

Using fixed routines
 120000 lines drawn in video memory 4.12 sec. 29126 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in video memory 5.66 sec. 21201 lines a sec.
 all random.
 120000 lines drawn in local memory 2.30 sec. 52174 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in local memory 3.63 sec. 33058 lines a sec.
 all random.
Using bresnham routines
 120000 lines drawn in video memory 4.78 sec. 25105 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in video memory 5.60 sec. 21429 lines a sec.
 all random.
 120000 lines drawn in local memory 3.40 sec. 35294 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in local memory 4.01 sec. 29925 lines a sec.
 all random.

 Total test time 33.56 sec

On my 386 20 with Diamond Speedstar 24x ISA 1m

Testing local memory line draw

Using fixed routines
 120000 lines drawn in video memory 22.79 sec. 5265 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in video memory 36.91 sec. 3251 lines a sec.
 all random.
 120000 lines drawn in local memory 20.60 sec. 5825 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in local memory 33.94 sec. 3536 lines a sec.
 all random.
Using bresnham routines
 120000 lines drawn in video memory 30.43 sec. 3943 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in video memory 44.93 sec. 2671 lines a sec.
 all random.
 120000 lines drawn in local memory 28.18 sec. 4258 lines a sec.
 1/3 horizontal 1/3 vertical 1/3 sloped
 120000 lines drawn in local memory 42.40 sec. 2830 lines a sec.
 all random.

 Total test time 260.18 sec

As you can see my fixed routine is faster in 3/4 of the tests on my 486
and 4/4 tests on my 386. I'm sure memory timings on my video card had
something to do with the bresnham winning the random test to video memory.

My code fastline.c Writen by Andrew Hallendorff

#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <i86.h>
#include <time.h>

int sum,off,dx,dy,lxdraw,linex[10000],liney[10000];
char oldmode, *plane[200], *poff1, *poff2;

void drawbres(xt1,yt1,xt2,yt2,color)
int xt1,yt1,xt2,yt2;
char color;
{
  /* global variables used
    off,dx,dy,lxdraw,*plane[200];
  */
  if(yt1>yt2) {
    dy=yt2;
    yt2=yt1;
    yt1=dy;
    dy=xt2;
    xt2=xt1;
    xt1=dy;
  }
  if(dy=yt2-yt1) {
    if(off=abs(dx=xt2-xt1)) {
      if(off>dy) {
        if(dx>0) {
          dx<<=1;
          dy<<=1;
          sum= -off;
          off++;
          for(lxdraw=0;lxdraw<off;lxdraw++) {
            *(plane[yt1]+xt1)=color;
            xt1++;
            if( (sum+=dy) >=0 ) {
              yt1++;
              sum-=dx;
            }
          }
        } else {
          dy<<=1;
          dx=off<<1;
          sum= -off;
          off++;
          for(lxdraw=0;lxdraw<off;lxdraw++) {
            *(plane[yt1]+xt1)=color;
            xt1--;
            if( (sum+=dy) >=0 ) {
              yt1++;
              sum-=dx;
            }
          }
        }
      } else {
        if(dx>0) {
          sum=-(off=dy);
          off++;
          dy<<=1;
          dx<<=1;
          for(lxdraw=0;lxdraw<off;lxdraw++) {
            *(plane[yt1]+xt1)=color;
            yt1++;
            if( (sum+=dx) >=0 ) {
              xt1++;
              sum-=dy;
            }
          }
        } else {
          dx=off<<1;
          sum=-(off=dy);
          dy<<=1;
          off++;
          for(lxdraw=0;lxdraw<off;lxdraw++) {
            *(plane[yt1]+xt1)=color;
            yt1++;
            if( (sum+=dx) >=0 ) {
              xt1--;
              sum-=dy;
            }
          }
        }
      }
    } else {  /* draw vertical line */
      do {
        *(plane[yt1]+xt1)=color;
        yt1++;
      } while(yt1<yt2);
    }
  } else { /* draw horzontal line */
    if(xt1>xt2) {
      poff1=(plane[yt1]+xt2);
      poff2=(plane[yt1]+xt1);
    } else {
      poff2=(plane[yt1]+xt2);
      poff1=(plane[yt1]+xt1);
    }
    while(poff1<=poff2)
      *(poff1++)=color;
  }

void drawline(xt1,yt1,xt2,yt2,color)
int xt1,yt1,xt2,yt2;
char color;
{
  /* global variables used
    off,dx,dy,lxdraw,*plane[200];
  */
  if(yt1>yt2) {
    dy=yt2;
    yt2=yt1;
    yt1=dy;
    dy=xt2;
    xt2=xt1;
    xt1=dy;
  }
  if(dy=yt2-yt1) {
    dy++;
    yt2++;
    if(off=abs(dx=xt2-xt1)) {
      if(off>dy) {
        xt2++;
        xt2=xt2<<18;
        xt1=xt1<<18;
        dx=(xt2-xt1+(1<<9))/dy;
        lxdraw=(xt1>>18);
        if(xt1<xt2) {
          do {
            xt1+=dx;
            poff1=(plane[yt1]+lxdraw);
            poff2=(plane[yt1]+(lxdraw=xt1>>18));
            while(poff1<poff2)
              *(poff1++)=color;
            yt1++;
          } while(yt1<yt2);
        } else {
          lxdraw++;
          do {
            xt1+=dx;
            poff2=(plane[yt1]+lxdraw);
            poff1=(plane[yt1]+(lxdraw=xt1>>18));
            while(poff1<poff2)
              *(poff1++)=color;
            yt1++;
          } while(yt1<yt2);
        }
      } else {
        xt2=xt2<<18;
        xt1=xt1<<18;
        if(dx>0) {
          dx=(xt2-xt1+(1<<18))/dy;
        } else {
          dx=(xt2-xt1)/dy;
        }
        do {
          *(plane[yt1]+(xt1>>18))=color;
          yt1++;
          xt1+=dx;
        } while(yt1<yt2);
      }
    } else {  /* draw vertical line */
      do {
        *(plane[yt1]+xt1)=color;
        yt1++;
      } while(yt1<yt2);
    }
  } else { /* draw horzontal line */
    if(xt1>xt2) {
      poff1=(plane[yt1]+xt2);
      poff2=(plane[yt1]+xt1);
    } else {
      poff2=(plane[yt1]+xt2);
      poff1=(plane[yt1]+xt1);
    }
    while(poff1<=poff2)
      *(poff1++)=color;
  }

int setmres()
{
  union REGS r;
  r.h.ah=0x0F;
  int386(0x10,&r,&r);
  oldmode=r.h.al;
  r.w.ax=0x0013;
  int386(0x10,&r,&r);
  return(1);

int setoldmode()
{
  union REGS r;
  r.h.ah=0x00;
  r.h.al=oldmode;
  int386(0x10,&r,&r);
  return(1);

void clearvidbuf()
{
  memset( plane[0],(char)0,320*200);

void makeplanetable()
{
  int i;
  plane[0]=(char *)0xa0000;
  for(i=1;i<200;i++)
    plane[i]=(plane[0]+(i*320));

void makelocaltable()
{
  int i;
  plane[0]=(char *)malloc(320*200);
  for(i=1;i<200;i++)
    plane[i]=(plane[0]+(i*320));

void main()
{
  FILE *fp;
  int i,j,k;
  clock_t t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;
  makeplanetable();
  setmres();
  clearvidbuf();
  for(i=0;i<10000;i++) {
    linex[i]=rand()%320;
    liney[i]=rand()%200;
  }
  t1=clock();
  for(i=0;i<2;i++) {
    k=9999;
    for(j=0;j<10000;) {
      drawline(linex[k],liney[k],linex[j],liney[j],liney[j]);
      drawline(linex[k],liney[j],linex[j],liney[k],liney[j]);
      drawline(linex[k],liney[k],linex[j],liney[k],liney[j]);
      drawline(linex[k],liney[j],linex[j],liney[j],liney[j]);
      drawline(linex[j],liney[k],linex[j],liney[j],liney[j]);
      drawline(linex[k],liney[j],linex[k],liney[k],liney[j]);
      j++;k--;
    }
  }
  t2=clock();
  for(i=0;i<12;i++) {
    k=9999;
    for(j=0;j<10000;) {
      drawline(linex[k],liney[k],linex[j],liney[j],liney[j]);
      j++;k--;
    }
  }
  t3=clock();
  for(i=0;i<2;i++) {
    k=9999;
    for(j=0;j<10000;) {
      drawbres(linex[k],liney[k],linex[j],liney[j],liney[j]);
      drawbres(linex[k],liney[j],linex[j],liney[k],liney[j]);
      drawbres(linex[k],liney[k],linex[j],liney[k],liney[j]);
      drawbres(linex[k],liney[j],linex[j],liney[j],liney[j]);
      drawbres(linex[j],liney[k],linex[j],liney[j],liney[j]);
      drawbres(linex[k],liney[j],linex[k],liney[k],liney[j]);
      j++;k--;
    }
  }
  t4=clock();
  for(i=0;i<12;i++) {
    k=9999;
    for(j=0;j<10000;) {
      drawbres(linex[k],liney[k],linex[j],liney[j],liney[j]);
      j++;k--;
    }
  }
  t5=clock();
  setoldmode();
  printf("Testing local memory line draw\n\n");
  makelocaltable();
  t6=clock();
  for(i=0;i<2;i++) {
    k=9999;
    for(j=0;j<10000;) {
      drawline(linex[k],liney[k],linex[j],liney[j],liney[j]);
      drawline(linex[k],liney[j],linex[j],liney[k],liney[j]);
      drawline(linex[k],liney[k],linex[j],liney[k],liney[j]);
      drawline(linex[k],liney[j],linex[j],liney[j],liney[j]);
      drawline(linex[j],liney[k],linex[j],liney[j],liney[j]);
      drawline(linex[k],liney[j],linex[k],liney[k],liney[j]);
      j++;k--;
    }
  }
  t7=clock();
  for(i=0;i<12;i++) {
    k=9999;
    for(j=0;j<10000;) {
      drawline(linex[k],liney[k],linex[j],liney[j],liney[j]);
      j++;k--;
    }
  }
  t8=clock();
  for(i=0;i<2;i++) {
    k=9999;
    for(j=0;j<10000;) {
      drawbres(linex[k],liney[k],linex[j],liney[j],liney[j]);
      drawbres(linex[k],liney[j],linex[j],liney[k],liney[j]);
      drawbres(linex[k],liney[k],linex[j],liney[k],liney[j]);
...

read more »

Quote:>There has been a lot of talk to who or how to create the fastest line
>drawing routine. Well I think its time to put our code where our postings
>are (money where our mouth is). We could have a contest or something. I've
>writen a program to profile line drawing under two methods (fixed and
>bresenham). Both of my routines are witten completly in C. The rules for
>the contest should be as follows:

Add a bonus round to the competition; include anti-aliasing.  :-)

--
===============================================================
= Reid M. Pinchback                                           =
= Senior Faculty Liaison                                      =
= Academic Computing Services, MIT                            =
=                                                             =

= URL:     http://web.mit.edu/user/r/e/reidmp/www/home.html   =
===============================================================

        Great idea.. I'll take part in this one...

Quote:

>For the DOS clones

>Almost anything goes in software (no hardware).
>You can use asm, C pascal....
>You can use any amount of memory for tables and code.
>Flat mode should be used to avoid far jumps and far memory access.
>Lines should be drawn to 320x200x256 graphics mode to avoid bank switches
>Lines should also be tested in a local memory buffer to avoid outs.
>All lines should reside in the window no cliping should be done.
>Random points should be in a table of 10000 points
>Otherwise it should follow the calling conventions shown in the main part
>of the attached program.

        How about drawing lines from center of the screen to every corner
of screen and all pixels between them. Like first line going from
(0,0) to (160,100) and next from (1,0) to (160,100) etc... do this for
all sides of screen. One screen (320*200) is thus 1040 linez...

        Also these routines should be tested on SAME computer and one
should take account that QEMM/386MAX/EMM386 etc slow your computer down
if installed.

        - Asmu / Wild Light -

Fine.  Just document the machine we're doing this on, and the
relative cycle times of integer ops, floating point ops, cache
cycle time, main memory cycle time, frame buffer cycle time,
cache size, frame buffer organisation, TLB organisation, stall
cycles, required delay slots, condition codes.......... all of
which impact the implementation.....

(-:(-:(-:  Probably Somebody's Law:  All fast implementations
of a graphics primtive are equivalent, because they're all faster
than the frame buffer cycle time:-):-):-)

--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ian Kemmish                     18 Durham Close, Biggleswade, Beds SG18 8HZ

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Quote:>    How about drawing lines from center of the screen to every corner
>of screen and all pixels between them. Like first line going from
>(0,0) to (160,100) and next from (1,0) to (160,100) etc... do this for
>all sides of screen. One screen (320*200) is thus 1040 linez...

I believe this is called a morie pattern. I guess it wouldn't be that hard
to add. To get a good sample we would have to loop it a bunch of times.
Other suggestions have been anti-aliasing for extra credit.

Quote:>    Also these routines should be tested on SAME computer and one
>should take account that QEMM/386MAX/EMM386 etc slow your computer down
>if installed.

Different computers will get different results and that's a good thing. If
you looked at my results of my bresenham vs fixed. Bresenham actualy won
on one of my tests on my 486 and lost on my 386. This is probally due to
the timming of my video card. One of my limitations was...

Quote:>Flat mode should be used to avoid far jumps and far memory access.

Flat mode (or protected mode) should always win against a segmented mode
because of the way adresses are decoded for cross segment addressing. If
you are using an extender (like dos4g or TNT), your memory manager should
not affect your performance. If you want to compare real mode line drawing
algorithms feel free, but I doubt you'll get better results than the
protected mode tests. My fixed line routine will not run in segmented mode
because of the need for 32 bit ints. (I haven't tested it but it might if
I declared long ints. The performance would be nullified on a 16 bit
memory model. So why try.)

Andrew Hallendorff

No, it's better to use random lines since this reflects 'real'
usage better. When you have about 10000 lines the test program
will give a good approximation on how fast the line algoritm is
on average.

Where should the line programs be uploaded or posted? It's better
if all programs are tested on the same machine.

Jesper Nordenberg

        Yeah, I guess it's so... but then I have to write random number
routine also ;)

Quote:>Where should the line programs be uploaded or posted? It's better
>if all programs are tested on the same machine.

        Very true.

Quote:>Jesper Nordenberg

        - Asmu / Wild Light -

-> >>  How about drawing lines from center of the screen to every corner >> of
-> screen and all pixels between them. Like first line going from >> (0,0) to
-> (160,100) and next from (1,0) to (160,100) etc... do this for >> all sides
-> of screen. One screen (320*200) is thus 1040 linez... >>

-> >No, it's better to use random lines since this reflects 'real' >usage
-> better. When you have about 10000 lines the test program >will give a good
-> approximation on how fast the line algoritm is >on average.

I like the idea of drawing from the center to all corners - this way, all
slopes are tested in equal amounts - eg, someone may implement a routine which
works great for slopes < 1.000 but not for slopes greater than 1.000 (rep
stosb)

Also, this may sound wierd.  But if you draw from the center of the screen to
all edges - you get a clear picture of the expected result.  You KNOW that the
line routine is doing the correct thing.

If someone wanted to be really sneaky, and he knew that random lines would be
drawn, he could make the routine skip every 10'th line.  This would make
the routine 10% faster, but if the lines are random, the user/tester may not
notice the missing lines - :)

Then, if he wins the compo, remove the "skip 10'th line" code and everyone
thinks "wow - great code"

Also, a predictable pattern of lines will show any irregularities in the line
drawing routine.  If I knew the routine would be for a compo, I may avoid
having a "perfect" and "exception free" routine if it would add an extra hint
of speed.  A random distribution of lines may not show the irregularities.

 eg: line1   ****                 line2    *****
                 ****                          *****
                     ****                          *****

line2 looks "nicer", but line1 is faster

Just my 2c worth - I must write a line draw routine in the next few weeks, and
am interested in entering it in the compo.