/* ------------------------------------------- */ /* World fastest line benchmark */ /* ---------------------------- */ /* */ /* Best regards - Alexnader Voronin */ /* ------------------------------------------- */ /* Enhanced by Po-Han Lin */ /* */ /* Latest version available at: */ /* http://www.edepot.com/algorithm.html */ /* */ /* Includes source of EFLA Variation E */ /* Copyright 2001-2002 By Po-Han Lin */ /* Visit website for use permissions */ /* POHANL@YAHOO.COM */ /* */ /* ------------------------------------------- */ #include #include #include /* ---------------------------------- */ /* */ /* READ THIS BEFORE BEGIN! */ /* ----------------------- */ /* */ /* NOTE: you have to add just three */ /* things here: */ /* */ /* 1) line routine proto */ /* 2) record to benchmarks array */ /* 3) line routine body */ /* */ /* Note that line proto should be the */ /* same as described in example! Dont */ /* use non ANSI or non POSIX function */ /* calls there! Dont use any OS or */ /* hardware dependent calls! Use */ /* predefined types in your routines */ /* (Byte instead of char, Word */ /* instead of short, etc) to avoid */ /* architecture incompatibitily. */ /* ---------------------------------- */ /* ---------------------------------- */ /* This is obvious for almost any */ /* 32-bit architecture, but you can */ /* change this. */ /* ---------------------------------- */ typedef char Byte; typedef unsigned char UByte; /* ---------------------------------- */ /* Virtual frame buffer. */ /* Please use pixel routine to set it */ /* ---------------------------------- */ #define fb_width 1024 #define fb_height 1024 static UByte frame_buffer[fb_width * fb_height]; void pixel ( int x, int y, UByte clr ) { frame_buffer[ y * fb_width + x] = clr; } /* --------------------------------------- */ /* benchmark structure */ /* name - algorithm name */ /* comments - any comments here */ /* line - pointer to line routine */ /* --------------------------------------- */ struct benchmark { const Byte *name; const Byte *comments; void (*line) ( int, int, int, int, UByte ); }; /* --------------------------------------- */ /* Line prototypes there (add your one) */ /* --------------------------------------- */ void efla_addition_fp_precalc (int, int, int, int, UByte); void wu (int, int, int, int, UByte); void bresenham (int, int, int, int, UByte); void dda (int, int, int, int, UByte); void naive (int, int, int, int, UByte); void abrash (int, int, int, int, UByte); /* --------------------------------------- */ /* Benchmark records (add you one here) */ /* Do not remove last record - this is end */ /* limiter */ /* --------------------------------------- */ struct benchmark bencharks[] = { { "efla_addition_fp_precalc","Extremely Fast Line Algorithm Variation E", efla_addition_fp_precalc }, // { "wu","Wu", wu }, { "dda","DDA", dda }, { "naive","naive", naive }, { "bresenham","Po-Han Lin Bresenham", bresenham }, { "abrash", "Michael Abrash Bresenham", abrash }, /* { "your_line_name", "Your description", pointer_to_routine }, */ /* ... */ { 0, 0, 0 } }; /* --------------------------------------- */ /* At last - LINES section. */ /* Place your lines code here */ /* --------------------------------------- */ void wu(int x0, int y0, int x1, int y1,UByte clr) { //int pix = color.getRGB(); int dy = y1 - y0; int dx = x1 - x0; int stepx, stepy; if (dy < 0) { dy = -dy; stepy = -1; } else { stepy = 1; } if (dx < 0) { dx = -dx; stepx = -1; } else { stepx = 1; } pixel( x0, y0,clr); pixel( x1, y1,clr); if (dx > dy) { int length = (dx - 1) >> 2; int extras = (dx - 1) & 3; int incr2 = (dy << 2) - (dx << 1); if (incr2 < 0) { int c = dy << 1; int incr1 = c << 1; int d = incr1 - dx; for (int i = 0; i < length; i++) { x0 += stepx; x1 -= stepx; if (d < 0) { // Pattern: pixel( x0, y0,clr); // pixel( x0 += stepx, y0,clr); // x o o pixel( x1, y1,clr); // pixel( x1 -= stepx, y1,clr); d += incr1; } else { if (d < c) { // Pattern: pixel( x0, y0,clr); // o pixel( x0 += stepx, y0 += stepy,clr); // x o pixel( x1, y1,clr); // pixel( x1 -= stepx, y1 -= stepy,clr); } else { pixel( x0, y0 += stepy,clr); // Pattern: pixel( x0 += stepx, y0,clr); // o o pixel( x1, y1 -= stepy,clr); // x pixel( x1 -= stepx, y1,clr); // } d += incr2; } } if (extras > 0) { if (d < 0) { pixel( x0 += stepx, y0,clr); if (extras > 1) pixel( x0 += stepx, y0,clr); if (extras > 2) pixel( x1 -= stepx, y1,clr); } else if (d < c) { pixel( x0 += stepx, y0,clr); if (extras > 1) pixel( x0 += stepx, y0 += stepy,clr); if (extras > 2) pixel( x1 -= stepx, y1,clr); } else { pixel( x0 += stepx, y0 += stepy,clr); if (extras > 1) pixel( x0 += stepx, y0,clr); if (extras > 2) pixel( x1 -= stepx, y1 -= stepy,clr); } } } else { int c = (dy - dx) << 1; int incr1 = c << 1; int d = incr1 + dx; for (int i = 0; i < length; i++) { x0 += stepx; x1 -= stepx; if (d > 0) { pixel( x0, y0 += stepy,clr); // Pattern: pixel( x0 += stepx, y0 += stepy,clr); // o pixel( x1, y1 -= stepy,clr); // o pixel( x1 -= stepx, y1 -= stepy,clr); // x d += incr1; } else { if (d < c) { pixel( x0, y0,clr); // Pattern: pixel( x0 += stepx, y0 += stepy,clr); // o pixel( x1, y1,clr); // x o pixel( x1 -= stepx, y1 -= stepy,clr); // } else { pixel( x0, y0 += stepy,clr); // Pattern: pixel( x0 += stepx, y0,clr); // o o pixel( x1, y1 -= stepy,clr); // x pixel( x1 -= stepx, y1,clr); // } d += incr2; } } if (extras > 0) { if (d > 0) { pixel( x0 += stepx, y0 += stepy,clr); if (extras > 1) pixel( x0 += stepx, y0 += stepy,clr); if (extras > 2) pixel( x1 -= stepx, y1 -= stepy,clr); } else if (d < c) { pixel( x0 += stepx, y0,clr); if (extras > 1) pixel( x0 += stepx, y0 += stepy,clr); if (extras > 2) pixel( x1 -= stepx, y1,clr); } else { pixel( x0 += stepx, y0 += stepy,clr); if (extras > 1) pixel( x0 += stepx, y0,clr); if (extras > 2) { if (d > c) pixel( x1 -= stepx, y1 -= stepy,clr); else pixel( x1 -= stepx, y1,clr); } } } } } else { int length = (dy - 1) >> 2; int extras = (dy - 1) & 3; int incr2 = (dx << 2) - (dy << 1); if (incr2 < 0) { int c = dx << 1; int incr1 = c << 1; int d = incr1 - dy; for (int i = 0; i < length; i++) { y0 += stepy; y1 -= stepy; if (d < 0) { pixel( x0, y0,clr); pixel( x0, y0 += stepy,clr); pixel( x1, y1,clr); pixel( x1, y1 -= stepy,clr); d += incr1; } else { if (d < c) { pixel( x0, y0,clr); pixel( x0 += stepx, y0 += stepy,clr); pixel( x1, y1,clr); pixel( x1 -= stepx, y1 -= stepy,clr); } else { pixel( x0 += stepx, y0,clr); pixel( x0, y0 += stepy,clr); pixel( x1 -= stepx, y1,clr); pixel( x1, y1 -= stepy,clr); } d += incr2; } } if (extras > 0) { if (d < 0) { pixel( x0, y0 += stepy,clr); if (extras > 1) pixel( x0, y0 += stepy,clr); if (extras > 2) pixel( x1, y1 -= stepy,clr); } else if (d < c) { pixel( stepx, y0 += stepy,clr); if (extras > 1) pixel( x0 += stepx, y0 += stepy,clr); if (extras > 2) pixel( x1, y1 -= stepy,clr); } else { pixel( x0 += stepx, y0 += stepy,clr); if (extras > 1) pixel( x0, y0 += stepy,clr); if (extras > 2) pixel( x1 -= stepx, y1 -= stepy,clr); } } } else { int c = (dx - dy) << 1; int incr1 = c << 1; int d = incr1 + dy; for (int i = 0; i < length; i++) { y0 += stepy; y1 -= stepy; if (d > 0) { pixel( x0 += stepx, y0,clr); pixel( x0 += stepx, y0 += stepy,clr); pixel( x1 -= stepy, y1,clr); pixel( x1 -= stepx, y1 -= stepy,clr); d += incr1; } else { if (d < c) { pixel( x0, y0,clr); pixel( x0 += stepx, y0 += stepy,clr); pixel( x1, y1,clr); pixel( x1 -= stepx, y1 -= stepy,clr); } else { pixel( x0 += stepx, y0,clr); pixel( x0, y0 += stepy,clr); pixel( x1 -= stepx, y1,clr); pixel( x1, y1 -= stepy,clr); } d += incr2; } } if (extras > 0) { if (d > 0) { pixel( x0 += stepx, y0 += stepy,clr); if (extras > 1) pixel( x0 += stepx, y0 += stepy,clr); if (extras > 2) pixel( x1 -= stepx, y1 -= stepy,clr); } else if (d < c) { pixel( x0, y0 += stepy,clr); if (extras > 1) pixel( x0 += stepx, y0 += stepy,clr); if (extras > 2) pixel( x1, y1 -= stepy,clr); } else { pixel( x0 += stepx, y0 += stepy,clr); if (extras > 1) pixel( x0, y0 += stepy,clr); if (extras > 2) { if (d > c) pixel( x1 -= stepx, y1 -= stepy,clr); else pixel( x1, y1 -= stepy,clr); } } } } } } void dda(int x1,int y1,int x2, int y2, UByte clr) { int length,i; double x,y; double xincrement; double yincrement; length = abs(x2 - x1); if (abs(y2 - y1) > length) length = abs(y2 - y1); xincrement = (double)(x2 - x1)/(double)length; yincrement = (double)(y2 - y1)/(double)length; x = x1 + 0.5; y = y1 + 0.5; for (i = 1; i<= length;++i) { pixel((int)x, (int)y, clr); x = x + xincrement; y = y + yincrement; } } void naive(int x1,int y1,int x2, int y2, UByte clr) { int dx = abs(x2 - x1); int dy = abs(y2 - y1); int length = dx > dy? dx : dy; for (int i = 1; i <= length; ++i) { double t = (double)i / length; int x = x1 + (int)(t * (x2 - x1)); int y = y1 + (int)(t * (y2 - y1)); pixel(x, y, clr); } } void bresenham(int x1, int y1, int x2, int y2, UByte clr) { int x, y; int dx, dy; int incx, incy; int balance; if (x2 >= x1) { dx = x2 - x1; incx = 1; } else { dx = x1 - x2; incx = -1; } if (y2 >= y1) { dy = y2 - y1; incy = 1; } else { dy = y1 - y2; incy = -1; } x = x1; y = y1; if (dx >= dy) { dy <<= 1; balance = dy - dx; dx <<= 1; while (x != x2) { pixel(x, y,clr); if (balance >= 0) { y += incy; balance -= dx; } balance += dy; x += incx; } pixel(x, y,clr); } else { dx <<= 1; balance = dx - dy; dy <<= 1; while (y != y2) { pixel(x, y,clr); if (balance >= 0) { x += incx; balance -= dy; } balance += dx; y += incy; } pixel(x, y,clr); } } // THE EXTREMELY FAST LINE ALGORITHM Variation E (Addition fixed point precalc) void efla_addition_fp_precalc(int x, int y, int x2, int y2, UByte clr) { bool yLonger=false; int shortLen=y2-y; int longLen=x2-x; if (abs(shortLen)>abs(longLen)) { int swap=shortLen; shortLen=longLen; longLen=swap; yLonger=true; } int decInc; if (longLen==0) decInc=0; else decInc = (shortLen << 16) / longLen; if (yLonger) { if (longLen>0) { longLen+=y; for (int j=0x8000+(x<<16);y<=longLen;++y) { pixel(j >> 16,y,clr); j+=decInc; } return; } longLen+=y; for (int j=0x8000+(x<<16);y>=longLen;--y) { pixel(j >> 16,y,clr); j-=decInc; } return; } if (longLen>0) { longLen+=x; for (int j=0x8000+(y<<16);x<=longLen;++x) { pixel(x,j >> 16,clr); j+=decInc; } return; } longLen+=x; for (int j=0x8000+(y<<16);x>=longLen;--x) { pixel(x,j >> 16,clr); j-=decInc; } } /** Added Michael Abrash's version from http://www.phatcode.net/res/224/files/html/ch35/35-03.html */ /* * Draws a line in octant 0 or 3 ( |DeltaX| >= DeltaY ). */ void Octant0(int X0, int Y0, int DeltaX, int DeltaY, int XDirection, UByte Clr) { int DeltaYx2; int DeltaYx2MinusDeltaXx2; int ErrorTerm; /* Set up initial error term and values used inside drawing loop */ DeltaYx2 = DeltaY * 2; DeltaYx2MinusDeltaXx2 = DeltaYx2 - (int) ( DeltaX * 2 ); ErrorTerm = DeltaYx2 - (int) DeltaX; /* Draw the line */ pixel(X0, Y0, Clr); /* draw the first pixel */ while ( DeltaX-- ) { /* See if it’s time to advance the Y coordinate */ if ( ErrorTerm >= 0 ) { /* Advance the Y coordinate & adjust the error term back down */ Y0++; ErrorTerm += DeltaYx2MinusDeltaXx2; } else { /* Add to the error term */ ErrorTerm += DeltaYx2; } X0 += XDirection; /* advance the X coordinate */ pixel(X0, Y0, Clr); /* draw a pixel */ } } /* * Draws a line in octant 1 or 2 ( |DeltaX| < DeltaY ). */ void Octant1(int X0, int Y0, int DeltaX, int DeltaY, int XDirection, UByte Clr) { int DeltaXx2; int DeltaXx2MinusDeltaYx2; int ErrorTerm; /* Set up initial error term and values used inside drawing loop */ DeltaXx2 = DeltaX * 2; DeltaXx2MinusDeltaYx2 = DeltaXx2 - (int) ( DeltaY * 2 ); ErrorTerm = DeltaXx2 - (int) DeltaY; pixel(X0, Y0, Clr); /* draw the first pixel */ while ( DeltaY-- ) { /* See if it’s time to advance the X coordinate */ if ( ErrorTerm >= 0 ) { /* Advance the X coordinate & adjust the error term back down */ X0 += XDirection; ErrorTerm += DeltaXx2MinusDeltaYx2; } else { /* Add to the error term */ ErrorTerm += DeltaXx2; } Y0++; /* advance the Y coordinate */ pixel(X0, Y0, Clr); /* draw a pixel */ } } /* * Draws a line on the EGA or VGA. */ void abrash(int X0, int Y0, int X1, int Y1, UByte Clr) { int DeltaX, DeltaY; int Temp; /* Save half the line-drawing cases by swapping Y0 with Y1 and X0 with X1 if Y0 is greater than Y1. As a result, DeltaY is always > 0, and only the octant 0-3 cases need to be handled. */ if ( Y0 > Y1 ) { Temp = Y0; Y0 = Y1; Y1 = Temp; Temp = X0; X0 = X1; X1 = Temp; } /* Handle as four separate cases, for the four octants in which Y1 is greater than Y0 */ DeltaX = X1 - X0; /* calculate the length of the line in each coordinate */ DeltaY = Y1 - Y0; if ( DeltaX > 0 ) { if ( DeltaX > DeltaY ) { Octant0(X0, Y0, DeltaX, DeltaY, 1, Clr); } else { Octant1(X0, Y0, DeltaX, DeltaY, 1, Clr); } } else { DeltaX = -DeltaX; /* absolute value of DeltaX */ if ( DeltaX > DeltaY ) { Octant0(X0, Y0, DeltaX, DeltaY, -1, Clr); } else { Octant1(X0, Y0, DeltaX, DeltaY, -1, Clr); } } } int main ( int argc, Byte **argv ) { int bench = 0; int loops = 200; int loop = 0; int z = 0; int line_counter = 0; int begin, end; float total_time; if ( argc > 1 ) { loops = atoi ( argv[1] ); } /* naive2(5, 5, 8, 1, 0); printf("--\n"); bresenham2(5, 5, 8, 1, 0); printf("--\n"); naive2(8, 1, 5, 5, 0); printf("--\n"); bresenham2(8, 1, 5, 5, 0); return 0; */ while ( bencharks[bench].name != 0 ) { line_counter = 0; fprintf ( stdout, "Examining: %s, %s with %d loops...\n", bencharks[bench].name, bencharks[bench].comments, loops ); fflush ( stdout ); begin = clock (); for ( loop = 0; loop < loops; loop ++ ) { for ( z = 0; z < fb_width; z++ ) { // Draws in all directions bencharks[bench].line(0,0, fb_height-1, z, 128 ); bencharks[bench].line(0,0, z, fb_height-1, 128 ); bencharks[bench].line(fb_height-1,0, z,fb_height-1, 128 ); bencharks[bench].line(fb_height-1,0, 0,z, 128 ); bencharks[bench].line(fb_height-1,fb_height-1, 0, z, 128 ); bencharks[bench].line(fb_height-1,fb_height-1, z, 0, 128 ); bencharks[bench].line(0,fb_height-1, z, 0, 128 ); bencharks[bench].line(0,fb_height-1, fb_height-1, z, 128 ); line_counter += 8; } } end = clock (); total_time = ( float ) ( end - begin ) / ( float ) CLOCKS_PER_SEC; fprintf ( stdout, "Made %d lines in %3.3f seconds, avg %3.3f lps\n\n", line_counter, total_time , ( float ) line_counter / total_time ); fflush ( stdout ); bench ++; } return 0; }