path: root/dda.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include "testdata.c"

typedef int32_t			fixed_t;

#define FIXED_BITS		(8)

#define fixed_e                 ((fixed_t) 1)
#define fixed_1                 (int_to_fixed(1))
#define fixed_1_minus_e         (fixed_1 - fixed_e)
#define fixed_to_int(f)         ((int) ((f) >> FIXED_BITS))
#define int_to_fixed(i)         ((fixed_t) ((i) << FIXED_BITS))
#define fixed_frac(f)           ((f) & fixed_1_minus_e)
#define fixed_floor(f)          ((f) & ~fixed_1_minus_e)
#define fixed_ceil(f)           fixed_floor ((f) + fixed_1_minus_e)
#define fixed_mod_2(f)          ((f) & (fixed1 | fixed_1_minus_e))
#define fixed_max_int           ((fixed_t)((0xffffffff << FIXED_BITS) & ~0x80000000))

#define fixed_to_double(f)      ((double) ((f) * (1 / (double) fixed_1)))
#define double_to_fixed(d)      ((fixed_t) ((d) * fixed_1))

#define MAX_ALPHA(n)    ((1 << (n)) - 1)
#define N_Y_FRAC(n)     ((n) == 1 ? 1 : (1 << ((n)/2)) - 1)
#define N_X_FRAC(n)     ((n) == 1 ? 1 : (1 << ((n)/2)) + 1)

#define STEP_Y_SMALL(n) (fixed_1 / N_Y_FRAC(n))
#define STEP_Y_BIG(n)   (fixed_1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))

#define Y_FRAC_FIRST(n) (STEP_Y_SMALL(n) / 2)
#define Y_FRAC_LAST(n)  (Y_FRAC_FIRST(n) + (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))

#define STEP_X_SMALL(n) (fixed_1 / N_X_FRAC(n))
#define STEP_X_BIG(n)   (fixed_1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))

#define X_FRAC_FIRST(n) (STEP_X_SMALL(n) / 2)
#define X_FRAC_LAST(n)  (X_FRAC_FIRST(n) + (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))

#define N_GRID_X               N_X_FRAC(8)
#define N_GRID_Y               N_Y_FRAC(8)

#define BIG_STEP_Y             STEP_Y_BIG(8)
#define SMALL_STEP_Y           STEP_Y_SMALL(8)
#define FIRST_STEP_Y           Y_FRAC_FIRST(8)

#define BIG_STEP_X             STEP_X_BIG(8)
#define SMALL_STEP_X           STEP_X_SMALL(8)
#define FIRST_STEP_X           X_FRAC_FIRST(8)

/* A sample_t is a fixed_t where the fractional bits are replaced with
 * a small integer indicating the sample number in the pixel.
 */
typedef int32_t sample_t;

static fixed_t
sample_to_pos_x (sample_t x)
{
    return fixed_floor (x) + FIRST_STEP_X + fixed_frac (x) * SMALL_STEP_X;
}

static fixed_t
sample_to_pos_y (sample_t y)
{
    return fixed_floor (y) + FIRST_STEP_Y + fixed_frac (y) * SMALL_STEP_Y;
}

static sample_t
next_sample_y (fixed_t y)
{
    fixed_t f = fixed_frac (y);
    fixed_t i = fixed_floor (y);
    int sample_no;

    sample_no = ((f - FIRST_STEP_Y + SMALL_STEP_Y - fixed_e) / SMALL_STEP_Y);

    if (sample_no > N_GRID_Y - 1)
    {
	/* FIXME: i can overflow here, but we should probably just
	 * reject edges that close to the border
	 */
	sample_no -= N_GRID_Y;
	i += fixed_1;
    }

    return i + sample_no;
}

static sample_t
next_sample_x (fixed_t x)
{
    fixed_t f = fixed_frac (x);
    fixed_t i = fixed_floor (x);
    int sample_no;

    sample_no = ((f - FIRST_STEP_X + SMALL_STEP_X - fixed_e) / SMALL_STEP_X);

    if (sample_no > N_GRID_X - 1)
    {
	/* FIXME: i can overflow here, but we should probably just
	 * reject edges that close to the border
	 */
	sample_no -= N_GRID_X;
	i += fixed_1;
    }

    return i + sample_no;
}

typedef struct
{
    sample_t xi;
    sample_t bottom;
    int64_t e;
    int64_t delta_e_big_x;
    int64_t delta_e_small_x;
    int64_t delta_e_big_y;
    int64_t delta_e_small_y;
} edge_t;

static void
edge_init (edge_t *edge, fixed_t x0, fixed_t y0, fixed_t x1, fixed_t y1)
{
    int64_t dx = (x1 - x0);
    int64_t dy = (y1 - y0);
    int yi = next_sample_y (y0);

    edge->xi = next_sample_x (x0);
    edge->bottom = next_sample_y (y1);
    edge->e =
	(int64_t)(sample_to_pos_x (edge->xi) - (int64_t)x0) * dy -
	(int64_t)(sample_to_pos_y (yi) - (int64_t)y0) * dx;
    edge->delta_e_big_x = BIG_STEP_X * dy;
    edge->delta_e_small_x = SMALL_STEP_X * dy;
    edge->delta_e_big_y = BIG_STEP_Y * dx;
    edge->delta_e_small_y = SMALL_STEP_Y * dx;
}

typedef void (* emitter_t) (sample_t x, sample_t y, void *data);

/* FIXME:
 *
 * When updating the xi, we are stepping one sample at a time, but we
 * can do better because we know how the minimum damage that is done on every Y
 * step. This means we know we have to undo at least that much damage, so
 * we can step much more than one sample if the edge is close to horizontal.
 *
 * The first micro-step is an exception - it may not do as much damage as
 * normal.
 */
static void
edge_step (edge_t *edge, int *yi, emitter_t emit, void *data)
{
    if (edge->delta_e_small_y >= 0)
    {
	while (edge->e <= 0)
	{
	    if (fixed_frac (edge->xi) == N_GRID_X - 1)
	    {
		edge->e += edge->delta_e_big_x;
		edge->xi += fixed_1;
		edge->xi = fixed_floor (edge->xi);
	    }
	    else
	    {
		edge->e += edge->delta_e_small_x;
		edge->xi++;
	    }
	}
    }
    else
    {
    begin:
	if (fixed_frac (edge->xi) == 0)
	{
	    if (edge->e > edge->delta_e_big_x)
	    {
		edge->e -= edge->delta_e_big_x;
		edge->xi -= fixed_1;
		edge->xi |= (N_GRID_X - 1);
		goto small;
	    }
	}
	else
	{
	small:
	    if (edge->e > edge->delta_e_small_x)
	    {
		edge->e -= edge->delta_e_small_x;
		edge->xi--;
		goto begin;
	    }
	}
    }

    emit (edge->xi, *yi, data);

    if (fixed_frac (*yi) == N_GRID_Y - 1)
    {
	edge->e -= edge->delta_e_big_y;
	(*yi) += fixed_1;
	(*yi) = fixed_floor (*yi);
    }
    else
    {
	edge->e -= edge->delta_e_small_y;
	(*yi)++;
    }
}

static void
emit (sample_t xi, sample_t yi, void *data)
{
#if 0
    double *points = data;
#endif

    printf ("sample %x %x (%f %f)\n",
	    xi, yi,
	    fixed_to_double (sample_to_pos_x (xi)),
	    fixed_to_double (sample_to_pos_y (yi)));

    return;
}

static void
dda (test_data_t *testdata)
{
    fixed_t x0 = double_to_fixed (testdata->segment.x0);
    fixed_t y0 = double_to_fixed (testdata->segment.y0);
    fixed_t x1 = double_to_fixed (testdata->segment.x1);
    fixed_t y1 = double_to_fixed (testdata->segment.y1);

    printf ("f = = = %f %f %f %f = = = = \n",
	    fixed_to_double (x0),
	    fixed_to_double (y0),
	    fixed_to_double (x1),
	    fixed_to_double (y1));

    edge_t edge;
    int i = 0;
    int yi;

    edge_init (&edge, x0, y0, x1, y1);

    yi = next_sample_y (y0);
    while (yi < edge.bottom)
    {
	edge_step (&edge, &yi, emit, &(testdata->points[i]));

	i += 2;
    }
}

static test_data_t td[] =
{
    { -1.917969, 1.980469, -0.937500, 2.855469 }
};

int
main ()
{
    int i;

    dda (&td[0]);
    
    for (i = 0; i < 1000; ++i)
    {
	test_data_t tt;

	tt.segment.x0 = 5 * (drand48() - 0.5);
	tt.segment.y0 = 5 * (drand48() - 0.5);
	tt.segment.x1 = tt.segment.x0 + (drand48() - 0.5) * 4;
	tt.segment.y1 = tt.segment.y0 + drand48() * 4;

	dda (&tt);
    }

    return 0;
}