/* pdline.c : PUBLIC DOMAIN - Jon Mayo - July 1, 2003 * - You may remove any comments you wish, modify this code any way you wish, * and distribute any way you wish.*/ /* 3D and 2D line drawing routines using Bresenham's line algorithm * the 2D line routine has an enhancement that does an inexpensive distance * estimation. some stand-alone distance calculations are included for * comparison with the distance estimate in line2d * the distance can be pretty far off (often 5% off), because of the very * simple way it estimates. but the calculation is extremel cheap if you had to * draw a line anyways. */ #include #include #include /* needed for sqrt(), remember to link to math libraries */ void putpixel2d(int x, int y) { fprintf(stderr, "point: %4d, %4d\n",x,y); } void putpixel3d(int x, int y, int z) { fprintf(stderr, "point: %4d, %4d, %4d\n",x,y,z); } /* gives approximate distance with only overestimations, and never by more * than (9/8) + one bit uncertainty */ static int inaccurate_distance(int x1, int y1, int x2, int y2) { int dx,dy; dx=abs(x2-x1); dy=abs(y2-y1); return dx + dy - (dx>dy?dy:dx)/2; } static int accurate_distance(int x1, int y1, int x2, int y2) { int dx,dy; dx=x2-x1; dy=y2-y1; return sqrt(dx*dx + dy*dy); } static double fdistance(int x1, int y1, int x2, int y2) { int dx,dy; dx=x2-x1; dy=y2-y1; return sqrt(dx*dx + dy*dy); } /* draw a line from (x1,y1) to (x2,y2). return the estimate distance */ int line2d(int x1, int y1, int x2, int y2) { int x, y; int ddx, ddy; /* 2 * delta x, 2 * delta y */ int sx, sy; /* step x, step y */ int dist; /* current distance traveled */ /* the absolute distance in X,Y we must move */ ddx=2*abs(x2-x1); ddy=2*abs(y2-y1); /* set up the stepping depending on the direction for the line */ sx = (x2x1) ? 1 : 0; sy = (y2y1) ? 1 : 0; /* pen location */ x=x1; y=y1; dist=0; if(ddx>=ddy) { /* X is the indepedent */ int ydp; /* decision parameter for Y */ ydp=ddy-ddx; while(putpixel2d(x, y), x!=x2) { if(ydp>=0) { y+=sy; ydp-=ddx; dist+=27145; } dist+=65536; x+=sx; ydp+=ddy; } } else { /* Y is the indepedent */ int xdp; /* decision parameter for X and Z */ xdp=ddx-ddy; while(putpixel2d(x, y), y!=y2) { if(xdp>=0) { x+=sx; xdp-=ddy; dist+=27145; } dist+=65536; y+=sy; xdp+=ddx; } } #ifndef NDEBUG double exact_dist; exact_dist=fdistance(x1,y1,x2,y2); if(dist/65536 != (int)exact_dist) { printf("(%d,%d - %d,%d) ext:%f est:%f\n",x1,y1,x2,y2, exact_dist, dist/65536.); } #endif return (dist)/65536; } /* draw a line from (x1,y1,z1) to (x2,y2,z2) */ void line3d(int x1, int y1, int z1, int x2, int y2, int z2) { int x, y, z; int ddx, ddy, ddz; /* 2 * delta x, 2 * delta y, 2 * delta z */ int sx, sy, sz; /* step x, step y */ printf("(%d,%d,%d - %d,%d,%d)\n",x1,y1,z1,x2,y2,z2); /* the absolute distance in X,Y we must move */ ddx=2*abs(x2-x1); ddy=2*abs(y2-y1); ddz=2*abs(z2-z1); /* set up the stepping depending on the direction for the line */ sx = (x2x1) ? 1 : 0; sy = (y2y1) ? 1 : 0; sz = (z2z1) ? 1 : 0; /* pen location */ x=x1; y=y1; z=z1; if(ddx>=ddy && ddx>=ddz) { /* X is the indepedent */ int ydp, zdp; /* decision parameter for Y and Z */ ydp=ddy - ddx; zdp=ddz - ddx; while(putpixel3d(x, y, z),x!=x2) { if(ydp>=0) { y+=sy; ydp-=ddx; } if(zdp>=0) { z+=sz; zdp-=ddx; } x+=sx; ydp+=ddy; zdp+=ddz; } } else if(ddy>=ddx && ddy>=ddz) { /* Y is the indepedent */ int xdp, zdp; /* decision parameter for X and Z */ xdp=ddx - ddy; zdp=ddz - ddy; while(putpixel3d(x, y, z),y!=y2) { if(xdp>=0) { x+=sx; xdp-=ddy; } if(zdp>=0) { z+=sz; zdp-=ddy; } y+=sy; xdp+=ddx; zdp+=ddz; } } else { /* Z is the indepedent */ int xdp, ydp; /* decision parameter for X and Y */ xdp=ddx - ddz; ydp=ddy - ddz; while(putpixel3d(x, y, z),z!=z2) { if(xdp>=0) { x+=sx; xdp-=ddz; } if(ydp>=0) { y+=sy; ydp-=ddz; } z+=sz; xdp+=ddx; ydp+=ddy; } } } #ifdef STAND_ALONE /* this just runs a test on all the line algorithms */ int main(void) { int x, y, z; /* 3D tests */ for(z=0;z<3;z++) { for(y=0;y<3;y++) { for(x=0;x<3;x++) { line3d(-x,-y,-z,x*2,y*2,z*2); } } } /* 2D tests */ for(y=0;y<100;y++) { for(x=0;x<100;x++) { line2d(-x,-y,x,y); } } return 0; } #endif