/* 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 <stdlib.h>
#include <stdio.h>
#include <math.h> /* 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 = (x2<x1) ? -1 : (x2>x1) ? 1 : 0;
    sy = (y2<y1) ? -1 : (y2>y1) ? 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 = (x2<x1) ? -1 : (x2>x1) ? 1 : 0;
    sy = (y2<y1) ? -1 : (y2>y1) ? 1 : 0;
    sz = (z2<z1) ? -1 : (z2>z1) ? 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