Benchmark of EFLA Variation E, Wu, Bensenham, and DDA
The following is the source for benchmarking EFLA Variation E, Wu, Bensenham, and DDA
Return to Line Algorithms
/* ------------------------------------------- */
/* 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 <stdio.h>
#include <time.h>
#include <stdlib.h>
/* ---------------------------------- */
/* */
/* 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 {
Byte *name;
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);
/* --------------------------------------- */
/* 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 },
{ "bresenham","Bresenham", bresenham },
{ "dda","DDA", dda },
/* { "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 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;
}
}
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] );
}
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;
}